Exploration via Feature Perturbation in Contextual Bandits
Authors: Seouh-won Yi
Min-hwan Oh
Venue: NeurIPS 2025 spotlight ()
Keywords: Generalized Linear Bandits
Contextual Bandits
Thompson Sampling
Feature Perturbation
Primary area: theory
TL;DR: We study the feature-perturbing exploration method applicable to various bandit settings, and prove that our randomized method achieves optimal regret guarantee.

Abstract: We propose *feature perturbation*, a simple yet effective exploration strategy for contextual bandits that injects randomness directly into feature inputs, instead of randomizing unknown parameters or adding noise to rewards. Remarkably, this algorithm achieves $\widetilde{\mathcal{O}}(d\sqrt{T})$ worst-case regret bound for generalized linear contextual bandits, while avoiding the $\widetilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ regret typical of existing randomized bandit algorithms. Because our algorithm eschews parameter sampling, it is both computationally efficient and naturally extends to non-parametric or neural network models. 
We verify these advantages through empirical evaluations, demonstrating that feature perturbation not only  surpasses existing methods but also unifies strong practical performance with the near-optimal regret guarantees.

Exploration via Feature Perturbation in Contextual Bandits
Seouh-won Yi Seoul National University uniqueseouh@snu.c ac kr
Min-hwan Oh Scoul National University minoh@snu. ac kr
Abstract
We propose feature perturbation, simple yet effective exploration strategy for contextual bandits that injects randomness directly into feature inputs, instead randomizing unknown parameters adding noise to rewards. Remarkably, this algorithm achieves (dvVT) worst-case regret bound for generalized linear contex- tual bandits, while avoiding the ((d5/2/T) regret typical of existing randomized bandit algorithms. Because our algorithm eschews parameter sampling, it is both computationally efficient and naturally extends to non- panaameraeticc or neural network models. We verify these advantages through empirical evaluations, demonstrating that feature perturbation not only surpasses existing methods but also unifies strong practical performance with the near-optimal regret guarantees.
Introduction
Multi-armed bandits (MABs) provide the canonical model for sequential decision-making under uncertainty: at each round a decision-making agent selects one several arms to maximize cumu- lative reward while balancing exploration and exploitation. However, classical MABs ignore side information that often accompanics decisions in practice. Contextual bandits address this limitation by allowing the agent to first observe contextual information and then choose action tailored to that context-ea. e.g., features of users and/or items inform which arm to pull. This contextualized formulation has become pivotal framework in online learning and sequential a rich literature on algorithms and guarantees 2
making, with
38
A widely studied formulation of contextual bandits is the (generalized) linear contextual bandit, where the expected reward modeled by linear function 2 38
11 1 or, more generally, by generalized linear model (GLM) [17] 39 26 (37. In both linear and GLM settings, deterministic
methods based on optimism in the face of uncertainty (OFU) 7 38 39 and randomized approaches
such Thompson Sampling (TS) [10 6 3 Perturbed History Exploration (PHE)
[3] 32 35) have
been extensively studied. Notably, OFU-type algorithms achieve near-optimal regret of (dvT)) in linear contextual bandits (and likewise in GLM bandits (39). yet often underperform compared to TS and PHE in practice. In contrast, randomized exploration methods typically exhibit superior empirical performance but suffer from sub-optimal theoretical guarantees: standard analyses confirm regret bound of (dd3/2 3 in the frequentist (worst-case) setting Crucially, this gap is not merely an artifact of analysis: Hamidi and Bayati [2I] show it reflects an inherent cost of randomization in (generalized) linear Thompson sampling. This result highlights a fundamental mismatch between the
'LinTS 3 O achieves regret of O(min(d dy K)). While Kveton et 31 originally showed that LinPHE has regret of Ö(d T log K). where K is the number of arms, recent work 335 proves that LinPHE also satisfies ((/3/2 VT) regret. For further discussion trading off factors of O vs.O Vlog K), see Agrawal and Goyal 6 In this work, we consider even a large action space with K > so (22 regret of randomized (generalized) linear bandit algorithms is the main focus discussion.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

existing randomized exploration and the tighter optimism mechanism in OFU-based approaches. This dichotomy prompts natural question: is it possible to close the gap between randomized exploration and (T) worst-case regret? If one adheres strictly to randomly sampling the parameters (as in TS) perturbing the observed rewards (as in PHE), there appears fundamental barrier [21] preventing regret from achieving (dvTT)
In this work, we propose a simple yet effective alternative: instead of sampling parameters or perturbing rewards, randomly perturb the observed features (or contexts). By shifting the focus of exploration from parameter space to feature space, we circumvent the limitations that impose higher regret existing randomized algorithms. Remarkably, our analysis shows that this new approach not only retains the empirical advantages of randomization but also achieves (dv worst-case regret in (generalized) linear bandit settings, with no additional dependence on the number of arms. Furthermore, our method avoids the computational overhead of sampling parameters, making attractive for wide range of real-world applications.
Beyond theoretical efficiency, feature perturbation can seamlessly extend to more flexible non- parametric reward models, including neural networks. We demonstrate this empirically, showing that feature- based randomization can drive effective exploration assumptions may not hold. Hence, our proposed approach unifies strong theoretical guarantees with practical efficacy in (generalized) linear contextual bandits, and extends practically more complex models. Our main contributions are summarized as follows:
when specific parametric model
Feature perturbation for contextual bandits. We introduce a new class of algorithms for randomized exploration, termed feature perturbation, which focuses perturbing feature inputs rather than parameters or rewards. This approach is straightforward to implement and conceptually distinct from existing randomized exploration strategies.
Tight regret bounds. To the best of our knowledge, our work is the first randomized algorithm for generalized linear contextual bandits that achieves: (i) a regret bound of Ö(dvT), matching the best-known guarantees of deterministic (OFU-based) methods; and simultancously (ii) benefiting from an instance-dependent constant k. Notably, our algorithm's 's regret does not increase (even logarithmically) with the number of arms.
Empirical validation. Through extensive experiments on both synthetic and real-world data, we show that feature perturbation not only performs competitively against existing randomized methods but also generalizes beyond parametric models (e.g.. deep neural networks), demonstrating robustness even when linear assumptions do not hold.
Related works
Contextual bandits have been extensively investigated under various modeling assumptions. In the linear bandit setting, deterministic methods based on OFU [T] 7 achieve near-optimal ((dTT) regret, but often exhibit conservative exploration in practice. By contrast, randomized algorithms typically show better empirical performance yet suffer from a
such as TS higher (d (T) regret bound. Notably, Hamidi and Bayati [21 demonstrated that the extra vd inflation in TS-type algorithms is unavoidable in worst-case scenarios: eliminating this factor would lead to linear dependence on T. Consequently, parameter- based randomization cannot, in general, achieve ((d/T) regret without further modifications.
3 6 10 and PHE BI 32
Generalized linear bandits (GLB; [1 39 extend linear bandits to settings where rewards follow a nonlinear link function. UCB- and TS-based approaches [3 17
32 46 have also been applied here, displaying the same contrast between deterministic and randomized exploration. While UCB- type methods reach Ö(d/T) regret, they tend to over-explore in practice; randomized strategies mitigate this over-explooe wer-exploration but retain an additional vd penalty in the worst case. Like their linear counterparts, these methods rely on sampling the unknown parameter or perturbing rewards rather than altering the feature representation.
By contrast, our work introduces a new class of feature-perturbation (FP) algorithms designed to circumvent the dimensional penalty inherent in standard randomized approaches. Instead of randomizing parameters rewards, we propose to perturb the features directly. This perspective not

---

only preserves the empirical robustness associated with randomized strategies but also achieves tight regret bound both linear and generalized linear and practical advantages of contextual bandit exploration.
reconciling the theoretical
3 Preliminaries
Notations. For vectors x; y IRd, let ||r|| denote the 2-norm and | Vx Ax the weighted norm for positive definite matrix version is x Ay = (z, v) A- The notation Ö hides logarithmic factors in big-O notation, retaining instance-dependent constants. For a real-valued function f. we write f and f to denote its first and second derivatives. The set (I,..., : K} is abbreviated as [K].
Rdxd, The inner product y (z, y). and the weighted
Generalized linear contextual bandit. A generalized linear model (GLM; (41) describes a response R drawn from an exponential-famie distribution with mean μux=' 8*), where R is feature vector and 0 _d is unknown parameter. Given differentiable functions g and h, and base measure v, the conditional density r given æ takes the form:
dp(r 1x;0 0*) exp (rx' T 8r g(x'' ((xT0)) + h(r)) dv,
where the derivative of defines the link function μu Let H == ofl( r-) }= denote the
filtration up round 1. We define Pc(-) == P- 11-11 and E, [:] == E H4-1). The negative
log- ligllikelhhood and the maximum likelihood estimate (MLE) at round t are then given by:
1-1 (0) = Σ (g(=T0) - r,, 0. == argmin (0))
oE
T=1
In the generalized linear contextual bandit (GLB) setting, the agent observes context U, E C and a corresponding set of feature vectors X₂ C Rd representing each allowable arm a E A(v)) at each round. Upon selecting I; X, the agent receives stochastic reward it p(- #1;0)).
The learner aims minimize the regret: R(T) Σ (m(xTT00) - p(x, 0*)), where It. =
argmax eX f(x 0*) is the optimal arm at round f, which depends on the context Ct-
Algorithm: GLM-FP
Algorithm GLM-FP: Feature Perturbation Generalized Linear Bandits
1: Input: Regularization parameter À > 0, tuning parameter {ca}
2: for t = 1, 1,2,...,7 do
3: Compute ô, argmingeR Le(8; (2,,r,y<11
4: Sample C. 10,
| ||+1|
5: Compute T. +
G. for all
6: Choose i; ar[ (. and observe reward rt
Let Fy = Ft,
7:
end for
At each step t, given the filtration H4-1, the algorithm computes the MLE (line 3). Since MLE lacks a closed-fome solution, we employ Sequential Quadratic Programming (SQP; (14) or Iteratively Reweighted Least Squares (IRLS; [47]). Instead of perturbing rewards or parameters, the algorithm injects controlled randomness into feature vectors using perturbing distribution DD. By default, we use a multivariate normal distribution (line 4), but any distribution satisfying concentration and anti-concentration properties can be employed, as analyzed in Section 5.2
fundamental property of the GLB is that the strictly increasing link function simplifies the problem structure, making it resemble linear bandits. While prior works 3
39 46 adopt near-identical
We normalize the reward model so that Varir, x = [axx 6*). Scaling the variance by o² (by inserting a in the denominator of the exponential term of Eq. accordingly yields i-inflated regret bound.

---

methods to linear bandits bandits-typically using the vanilla Gram matrix Vi XI Er= .,,;; our approach takes more refined direction. To precisely control the perturbation magnitude for each feature representation, our approach utilizes a weighted Gram matrix, H, == XI L.
This adaptive structure, modulated by a tunable parameter c2, enables a more targeted perturbation strategy. Using the resulting scaling factors, the algorithm perturbs each feature vector construct a set of perturbed vectors, { J for reachable arms at round & (line 5). Importantly, the perturbation noise Ç. is shared across all arms, coupling each feature vector with the same random variable. This design eliminates the explicit dependence on K in the regret bound, thereby yielding stronger theoretical guarantees and improved empirical performance. Finally, the algorithm selects the arm that maximizes (() and updates its history upon observing the reward Ty (lines 6).
4.1 Extension to general function class
The algorithm extends naturally to more flexible function classes, as described Algorithm C.T Under the realizability assumption (i.e., FF), the estimate ft E is obtained via a least squares oracle the history H4-1 [19 45 49) Given the structural of the bandit reward model, sampling distribution is then defined for each arm and used to construct a set of perturbed contexts {Tt: The algorithm selects the arm that maximizes (Trs), thereby balancing exploration and exploitation.
The proposed GLM-FP algorithm is an instance of this framework, characterized by two specific design choices: (i) Gaussian sampling distribution D(#,, Σ.,) - N(rr, Exi) centered at Tai with elliptical covariance scaling with the uncertainty in the direction of zea and normalized by the estimated parameter norm; and (ii) a coupled perturbation scheme, where single shared random vector Se perturbs all arms simultaneously, in contrast to perturbing each arm independently.
4.2 Intuition behind the algorithm
In contextual bandit problems, randomized algorithms can be broadly categorized into two types: those that introduce randomness into the underlying model and those that inject randomness directly into the estimated expected rewards. The former category includes methods such as PHE [3] and TS [3] 6), which compute perturbed model parameters induce exploration. However, as noted by Hamidi and Bayati (21), this approach can be suboptimal even in linear settings. The latter category includes algorithms such as RandUCB [46), where the model trained deterministically and randomness is introduced by adding stochastic bonuses to the estimated rewards of each arm. While effective in inducing exploration, such reward perturbation can violate the inductive bias of the function class, since the resulting scores for arms may not be realized simultaneously by any single model f E eveven in simple linear cases.
To address these limitations, we propose an alternative strategy that retains the estimated model from past data and introduces randomness through input perturbations at decision time. Exploring directly in the feature space preserves the structural assumptions of the function class and remains effective even in overparameterized settings where >> d, such as neural bandits. It also aligns naturally with world scenarios in which contextual features contain inherent noise 29
TS / PHF
RondUCB
Expected rewer
Nive
((s))
fixs
f(a))
Feature space
Feature space
Figure 1: (Left) Model perturbation methods randomize rewards via off-estimated models Jr. (Right)
Feature Perturbation (FP) perturbs inputs and evaluates them with fixed model f..

---

As illustrated in Figure whereas UCB, TS, PHE, and RandUCB randomize parameters reward estimates via modified models ft. GLM-EP explores through feature-space perturbations evaluated under fixed f. This structural shift preserves the inductive bias of the model class and decouples exploration from parameter uncertainty, a property that becomes crucial in high-dimensional regimes.
Regret analysis of GLM-FP
In this section, establish the regret guarantee for the proposed algorithm, GLM-FP, and outline the key steps in its proof. We introduce fundamental concepts and lemmas that form the backbone of our analysis. We begin by presenting the standard assumptions commonly adopted in the analysis of generalized linear bandit algorithms 13
15
17
32
37
52)
Assumption 1 (Boundedness). The feature space X and the parameter space O are compuct subsets of IRd. For any x E Xiry and 0* E O, we have | S and |00|| < 1.
Assumption 2 self-cooncrd.ncce. The function g is three times differentiable, and its derivative 9 μ is strictly increasing and L Lyp-ichchitz continuous. Furthermore, 9 is self-concordant, characterized by the constant M, := supxexx,ee. [ū((a, //(l 8)).
Many widely studied GLB instances naturally satisfy these assumptions [43] For example, the triple (p(z), Lus My) takes the form (2, 1, 0) in linear, = : 1. 1) in logistic, and (e",e,
,e, 1) in Poisson.
5.1 Confidence bound for the true parameter
An important step in analyzing the regret bound of the algorithm is to establish a confidence set for the underlying parameter 0*, This involves constructing a region that reliably contains 0* throughout the learning process. To obtain practical and tighter bound, we adopt confidence sets derived from the log-like likelihood function using an ellipsoidal relaxation. The confidence width provided by recent work (37], which can be substituted with alternative, potentially tighter bounds.
Lemma (Adapted from Theorem 3.2. in Lee al. (37)). Let L, := maXage || (L,( denote the Lipschitz constant of the loss function Lz(-) For any X >>> O, define the regularized Hessian matrix at 0, as H. 2 T. (+:) AI. Then, with probability least
for all t 1, it holds that
8" (8. = {A Rd
||0 d,ll S (8)), where
(2eLe)
))
(6) = 4A + 2(1 + Mp) (lo + dlog d
5.2 Concentration and anti-concentratioon
In addition to ensuring that Ó remains close to the true parameter 8", it is crucial to balance the degree of randomization in the algorithm. Our regret analysis relies on showing that, with appropriate choice of the tuning parameter Cr, the perturbed feature H, is stochastically optimistic, while concentrated around its estimated value p(z; 0z). These properties are fundamental to the analysis, and we introduce the relevant components in this section.
Definition 1. Lett E [T]. We define the following events:
(i) P:: 0 remains close to 0* for all steps S t.
(i) E. all perturbed vectors Z.z concentrated around their corresponding for all steps T S
For given confidence level 8 (0, 1), define 8' 8/(4T) and ((6)) ( where e and è are constants consistent with Eq. ( The events are formally defined as:
E = (Vr S |10.
0" 0l, S (80) and E, = (VT S 1, Xr; Tri E E (wri))
|| Jr, 0.)1 S (6(88) (18))) |= represents high-probability region for the perturbed feature vector associated with each arm x.
where E,(x) = tT e Rdd
It has been shown Lee et al. 37 that L. O(t) for linear, logistic, and Poisson bandit instances.
5

---

A key requirement for the perturbation distribution D is the following concentration property: for some constants c, 0 and any unit vector u. have
PEND (Iu Velog(</6)) 21-6. /
(2)
Remark 1. The perturbing distribution of IS on B is described Appendix B Unlike in TS, the concentration here is evaluated along fixed direction u, not over all coordinates. This avoids the need for a union bound over d dimensions, and the resulting bound independent of d. This dimensionality reduction is a key advantage of perturbing features instead of parameters.
By construction, the events satisfy the nested structure For C... En and ET C.... Ej. Building on these definitions, we show that the proposed perturbation distribution induces an appropriate balance between exploration and exploitation, formalized in the following lemmas.
Lemma (Concentration). Under Assumptions
F 2 with ca B,(,",, P(E ET)
Lemma 3 (Stochastic optimism). For each round t, given that the events Eg and Ég occur, the probability anti-concentration, conditioned on the filtration H4-1 and under Assumptions and is lower bounded as
P. (e 0.) 2 p(zTT0)) E, E,)
1
AVER
In our construction, the concentration term in Eq. induces only constant-order inflation, yiclding both 3r and scaling (vdd). In contrast, TS incurs an extra vd factor, resulting in (d). This leads to a tighter exploration term our algorithm and improved regret performance.
5.3 Regret bound of GLM-FP
The complexity of the GLB problem is fundamentally determined by the following quantities, which captures the degree nonlinearity in the reward function:
N6x Els O() K== xxX oce
T
min
0), where
X(r) =
U
Xe.
(3)
T
(=1
These may scale exponentially small, particularly in the case of logistic bandits theorem presents the regret guarantee for our algorithm.
15
The following
Theorem 1. For all E (0, 1). define 8' 8/ (4T'. Under Assumptions and and À = (d), the cumulative regret R(T) is bounded with probability at least
with ct 3,(6')
as follows:
R(T) = H (dV R...T (dv..T+&P)) +
Discussion of Theorem 1 The leading term of the regret guarantee is O(dvni,T), which matches the minimax optimal regret bound terms of the dimensionality d. the horizon T, and the instance- dependent constant [4] 371. While RandUCB [46), another randomized algorithm, also achieves regret bound of (dvT)), it is penalized by its inverse dependence K, lacking adaptation to instance-dependen complexity. In contrast, to the best of our knowledge, our result is the first to show that a randomized algorithm achieves a regret bound with linear d-dependency, without additional dependence on the number of arms, benefiting form K, in GLB problems.
5.4 Proof sketch of Theorem 1
Our proof begins by decomposing the instantaneous regret into components: Regyp- the regret which arises from the randomization through FP, and RegEST. the regret accounting for the estimation error. By bounding each component separately, we derive the overall regret bound:
Optimism
Peruuration Concentration
R(T) Σ u(xTT.0)) u(5 6.) u( 0.) - u(x 0.)
Σ (ulx) 0.) -a(x) (4)
Reyep
Regest

---

To bound Regep. we rely on two key properties: (i) optimism induced by selecting the best estimated arm, and (ii) concentration of the perturbation around the original context. Under the high- prob-bbbbbillityy events Er and ÉT, both properties are well controlled, leading to the following bound:
CPT
Regrr S (8yeT + 1)
Σ
max plxx ulx= - ulaz (EL)(1)
(.( (0)))(xx +
X2
where the Ō()) term results from an Azuma Hoeffdiin concentration and becomes negligible under the choice À (d). Note that since the stochastic optimistic probability in Lemma 3 is lower bounded by a constant, Regpp can be effectively bounded by the sum of per-round concentration widths, multiplied by constant that is independent of d and T.
Unlike previous randomized algorithms B 32 46] that linearize the reward function and thereby suffer regret bounds inversely proportional to K, analysis avoids such linearization. Instead, we directly utilize the gradient of the link function μ to characterize the shape of the elliptical confidence region, enabling more efficient exploration tailored to the reward model. This is reflected in the weighted Gram matrix H7, where the curvature of y enters via the term j01xr; 0.).
However, this construction introduces dependency on (rather than solely on 7) in the weighted Gram matrix, which precludes direct application of the standard Elliptical Potential Lemma (EPL). To address this, we build upon recent analytical developments 4 15 355, and introduce a lower envelope of derivatives by defining O, as the minimizer of ( 0) over the union Ur X).
This yields matrix He == AI E the application of EPL. We bound RegesT in a similar fashion and show that both Regrp and RegEST admit the same upper bound. This reduces the analysis to solving a quadratic inequality of the form:
(xx_ , which satisfies A. 2 He, thereby enabling
Reg S AAVB + CRegmax + D, where Regmax = max RRegrr, RegEsTh-
The constants A, B, C, and D are explicitly analyzed in the full proof, deferred to Appendix
6 Carving off the dd factor compared to TS
The proposed algorithm, GLM-FP, adopts a novel exploration strategy by perturbing the input feature vectors, in contrast to conventional randomized algorithms such as Thompson Sampling (TS), which introduce randomness into the model parameter 0. This design yields regret bound with linear dependence on d, whereas TS incurs a higher (dd//2) dependence. We examine the origin of this discrepancy by comparing the linear variants of both algorithms (see Appendix C.2) how each introduces randomness to facilitate exploration.
highlighting
The randomized evaluation score F(( (either 0 for TS or Z, for FP) for each arm used for action selection in both algorithms is straightforward to compute as follows:
(TS) = -, = x7.0 2.00+to +o x =
1/2
(FP) F((z.) = āī = x. ze zellx:illv,
where G. ~ N( and x, N' 1). Thus, for each arm individually. both methods induce the same Gaussian distribution f((z)) ~ (xTT0 ~f .). However, the object of perturba- tirn-ear in TS versus feature in FP fundmanmmmentally alters how exploration bonuses are assigned and how arm comparisons are coupled at each timestep.
In TS, the bonus (mN, St)v, 1/2 projects each arm onto shared random direction &. in the V. 1/2 transformed space. As conceptually illustrated in Figure 2a] this shared dependence can produce counterintuitive effects: well-explored arms may occasionally receive large bonuses simply due to alignment with G. while under-explored ones may be neglected. Because the same Çe governs all arms, the analysis must ensure uniform reliability of exploration across directions, requiring high-probability control of the d-dimensional Gaussian vector G. Applying a union bound over coordinates introduces an additional Vd factor into the regret bound.
'In the linear bandit setting. this distribution also matches RandUCB 46 though its derivation is conceptually distinct and diverges beyond the GLB case; Section 4.2 and Appendix
7

---

(Unz: 101)
LinfP
An Anya
Cumulative Rogret
LinT5
211
10
APM
Aze
0
3
9
11
13
15
(a) Illustration of the transformation of the feature vectors in TS.
(b) Cumulative regret vs. d.
Figure (a) Transformation of the well-explored arm 21 and under-explored arm Fr2 using
1/2 A = DT where V/-1/2 PDPT. Left: Ç1 induces proper bonus. Right: {2 reverses the
effect. (b) Average terminal regret R(T) over 100 runs with 200,000, K 50, and varying
FP, in contrast, decouples exploration from directional uncertainty. Its bonus 2, || scales directly with per-arm uncertainty, ensuring under-explored arms systematically receive larger bonuses. Since randomness enters only through the scalar 2,, the analysis reduces to bounding a one- dimensional Gaussian projection C. for some fixed unit vector u.
From an equation-level viewpoint, the regret of TS also admits the decomposition in Eq. For both algorithms, the estimation component RegEsT is bounded in the same manner, and the anti-concentration event occurs with the same probability p. Consequently, the optimism-driee term in the regret scales with the concentration width divided by p. The essential difference therefore lies in the concentration width-or, equivalently, in how each algorithm controls the perturbation magnitude that also determines the second part of the decomposition. We express the upper bound for each perturbation term
(TS)
|r,_ (0c 0e) c 1/2 S aa aall 11V, 1/2
112 Sellv. cellxuslvy' ||selle.
0T ce callaally. . TcT
(FP) (Tz - 21) TT) e. celllzally.
10.12
The concentration width in TS depends on 1|5el12, the norm of d-dimensional Gaussian vector, whereas that of FP scales with the one-dimensional projection | G//- To obtain uniform high- probability guarantee across all coordinates, a union bound over the d-dimensional perturbation space introduces an additional ((vd) factor for TS. Thus, despite having identical marginal distributions for individual arms, the algorithms differ fundamentally in how their perturbations couple across arms: TS requires concentration over all directions in Rdd whereas FP relies on a single scalar randomization. This structural decoupling eliminates the extraneous vd factor, yielding linear (d) dependence the regret bound and clarifying the geometric origin of FP's improvement over TS.
7 Experiments
We conduct experiments in two contextual bandit settings: (i) generalized linear bandits (GLBs), including linear and logistic models, and (ii) nonlinear contextual bandits based on neural networks. In each setting, we compare the proposed method with state-of-the-an baselines across varying feature dimensions and datasets. All results are averaged over 100 independent runs to ensure robustness. Detailed experimental setups are provided in Appendix H
7.1 Generalized linear bandits
We evaluate GLM-FP in both linear and logistic contextual bandit settings, where the expected reward follows a generalized linear model. the linear bandit case, the reward is generated as r, = x 0* + with E, ~ (00 1), while the logistic bandit case, rt ~ Bernoulli(u(z) 0*)) with the logistic function μr. We compare against widely used baselines including e-greedy, UCB, TS, PHE, and RandUCB. Parameter estimation is performed via regularized weighted least squares (WI.S) in linear bandit setting or IRLS in logistic bandit setting.

---

d 10
d 20
4
1300
Camelebve Regret
750+
730
1000
500
2504
10000 Round
1900
20000
10:00
15:00
70000
56000
10000
Round
Round
Greedy
(ours)
Comibtiie legett
410
200
0-
100
200
300
500
1000
1500
Round
Round
Round
2- G-rreddy
OFUGLB-
LogTS
Logf PL
RandUCBLog
CLM (ours)
shuttle (K 7,
isolet [K of 6177
mushroum (K 2. 116)
Cumilatie Regret
300
0004)
10000
20000
20000
Round
Round
clsp (-Gready
MuurlUCB
Nearal
FIPL
DeaptP(ours)
Figure 3: Comparison of cumulative regret across contextual bandit algorithms: linear (top), logistic (middle), and neural (bottom).
As shown in Figure 3 (top and middle), GLM-FP consistently achieves the lowest regret across all tested dimensions. While RandLinUCB performs competitively in the linear case, GLM-FP exhibits superior robustness, particularly in fixed-arm settings or environments with non-stationary arm sets (see Appendix for more details). In the logistic setting, GLM-FP outperforms all baselines across all tested configurations, demonstrating
effectiveness even when the utility scale (i.e., TT 0", , the inner product term inside μu-)) the reward noise variance is varied. These results highlight the reliability and adaptability of our approach across diverse GLB scenarios.
7.2 Neural bandits
We extend the feature perturbation framework to the neural contextual bandit setting through simple and scalable algorithm, DeepFP. At each round, DeepFP injects independent, arm-wise Gaussian noise into the input features before prediction: TÚ = Tzi + Cri. where &. ~ (0, l/t). The variance decay 1/t reflects the diminishing feature uncertainty over time, analogous to the confidence scaling || in GLBs. This approach enables exploration without requiring access to model parameters gradients. We evaluate DeepFP three UCI benchmark datasets: shuttle (7 classes, 9 features), isolet (26 classes, 617 features), and mushroom (binary, 112 features). Baselines include e-greedy, NeuralUCB, NeuralTS, and Follow-the-Pettubeed---c Perturbed-Leader (FTPL).
Unlike NeuralTS, which adds randomness to predicted rewards (essentially functioning as a ran- domized UCB variant), or FTPL, which perturbs historical rewards, DeepFP directly perturbs the features. This structural distinction simplifies implementation and preserves the exploration intent in more principled way. Furthermore, unlike parameter-sampling--e application becomes increasingly unstable in high-capacity models where p > d, DeepFP perturbs much nower-dimension space, making it scalable and numerically stable.
approaches whose

---

As shown in Figure (bottom), DeepFP outperforms all baselines across the three datasets. Notably, achieves strong performance without relying on posterior upproximations or gradient-based confi- dence intervals, demonstrating that simple feature perturbation can remain effective even in complex, high-dimensional settings.
Conclusion
We introduced paradigm for randomized exploration in contextual bandits. By shifting stochasticity to feature space, FP bridges the gap between randomized and optimistic methods while achieving optimal regret. This perspective offers broadly applicable exploration principle and invites future work on leveraging structured randomness for efficient decision making.
Acknowledgements
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR07188 08007853300 and RS-2023-00222663), by Institute of Information communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2025-000 0025-00223354 and ES-2025-254663
and by AI-Bio Research
Grant through Seoul National University
References
[1] Yasin Jabasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011.
[2] Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In International conference muchine learning, pages 3-11, 1999.
[3] Marc Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 176-184. PMLR, PMLR, 20-22 Apr 2017.
[4] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, 2020.
[5] Marc Abeille, David Janz, and Ciara Pike-Burke. When and why randomised exploration works (in linear bandits). In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 22. PMLR, 24-27 Feb 2025.
[6] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135. PMLR, 2013.
[7] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-25 -266, 2002.
[8] Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Oper. Res., (81):276-294, January 2020. ISSN 0030-364X.
[9] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and TrendsS in Machine Learning, 5(1):1-122, 2012. ISSN 1935-8237.
[10] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
[11] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 24. JMLR Workshop and Conference Proceedings, 2011.
10

---

[12] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
[13] Jacob Devlin, Ming- deep bidirectional transformers for language understanding. In North American Chapter of the Association for Computational Linguistics, 2019.
Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of
[14] Jean Bosco Etoa Etoa. A globally convergent sequential linear programming algorithm for mathematical programs with linear complementarity constraints. Journal of Information & Optimization Sciences, 31, 09 2010.
[15] Louis Faury, Mare Abeille, Clement Calauzenes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3052-3060. PMLR, 13-18 Jul 2020.
[16] Louis Faury, Mare Abeille, Kwang-Sune -ung Jun, and Clement Calauzenes. Jointly efficient and optimal algorithms for logistic bandits. In Gustau Camps-Vall Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 546-580. PMLR, 28-30 Mar 2022.
[17] Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Proceedings of the 23rd International Conference on Neural Information Processing Systems- - Volume NIPS' 10, page 386-594, Red Hook, NY, USA, 2010. Curran Associates Inc.
[18] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In International Conference on Learning Representations, 2018
[19] Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th In- termational Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 3199-3210. PMLR. 13-18 Jul 2020.
[20] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv: 14/2.657, 2014.
[21] Nima Hamidi and Mohsen Bayati. On frequentist regret of linear thompson sampling. arXiv preprint 00060090066 2020.
[22] Osama A. Hanna, Lin Yang. and Christina Fragouli. Efficient batched algorithm for con- textual linear bandits with large action space via soft elimination. In Proceedings of the 37th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2023. Curran Associates Inc.
[23] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2015.
[24] Osband Ian, Van Roy Benjamin, and Russo Daniel. (more) efficient reinforcement learning via posterior sampling. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 13, page 3003-3011, Red Hook, NY, USA, 2013. Curran Associates Inc.
[25] David Janz, Shuai Liu, Alex Ayoub, and Csaba Szepesvári. Exploration via linearly perturbed loss minimisation. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 721-729. PMLR, 02-04 May 2024.

---

[26] Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable gen- eralized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
[27] Kwang- Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5148-5157. PMLR, 18-24 Jul 2021.
[28] Sampath Kannan, Jamie Morgenstem, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 2211-224, Red Hook, NY, USA, 2018. Curran Associates Inc.
[29] Jung-Huu Hun Kim, Se- Young Yun, Minchan Jeong, Junhyun Nam, Jinwoo Shin, and Richard Combes. Contextual linear bandits under noisy features: Towards bayesian oracles. In Francisco Ruiz, Jennifer Dy, and Jan-Wille Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 1624-1645. PMLR, 25-27 Apr 2023.
[30] Alexander Kolesnikov, Alexey Dosovitskiy, Dirk Weissenborn, Georg Heigold, Jakob Uszkoreit, Lucas Beyer, Matthias Minderer, Mostafa Dehghani, Neil Houlsby, Sylvain Gelly. Thomas Unterthiner, and Xiaohua Zhai. An image is worth 16x16 words: Transformers for image recog- nition at scale. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[31] Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Uncertainty in Artificial Intelligence, pages 530-540. PMLR, 2020.
[32] Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh. and Craig Boutilier, Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2066-2076. PMLR, 2020.
[33] John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
[34] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[35] Harin Lee and Min-hwan Oh. Improved regret of linear ensemble sampling. In Advances in Neural Information Processing Systems, volume 38, 2024.
[36] Junghyun Lec, Se- Young Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial) logistic bandits via regret-to-contiienne-ss conversion. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 4474 4482. PMLR, 02-04 04 May 2024.
[37] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. A unified confidence sequence for generalized linear models, with applications to bandits. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[38] Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual-bandde approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[39] Lihong Li, Yu Lu, and Dengyong Zhou Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[40] Kolby Nottingham Markelle Kelly, Rachel Longjohn. The uci machine learning repository, 2017. URL /tllttt:://arrhve.ics. uci.ccs...i...... edu/ml
12

---

[41] P. McCullagh and J.A. Nelder. Generalized Linear Models. Monographs on statistics and applied probability. Champman and Hall/CRC, 2001.
[42] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforce- ment learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 8626 66688, Red Hook, NY, USA, 2018. Curran Associates Inc.
[43] Ayush Sawarni, Nirjhar Das, Siddharth Barman, and Gaurav Sinha. Generalized linear bandits with limited adaptivity. In Proceedings of the 38th International Conference on Neural Informa- fion Processing Systems, NIPS '24, Red Hook, NY, USA, 2025. Curran Associates Inc. ISBN 9798331 1313131145..
[44] Connor Shorten and Taghi Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 07 2019.
[45] David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizabilityy Math. Oper. Res., 4703):1904-1931, August 2022. ISSN 0364-765X.
[46] Sharan Vaswani, Abbas Mehrabian, Audrey Durand, and Branislav Kveton. Old dog learns new tricks: Randomized uch for bandit problems. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1988-1998. PMLR, 26-28 Aug 2020.
[47] R. Wolke and H. Schwetlick. Iteratively reweighted least squares: Algorithms, convergence analysis, and numerical comparisons. SIAM Journal on Scientific and Statistical Computing, (5):907-922 921, 1988.
[48] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. ArXiv, abs/1708.07747, 2017.
[49] Yunbei Xu and Assaf J. Zeevi. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. ArXiv, abs/2007.07876 2020.
[50] Andrea Zanette, David Brandfonbrener. Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Confer- ence on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1954-1964. PMLR, 26-28 Aug 2020.
[51] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference Learning Representution (ICLR), 2021.
[52] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 11492 11502. PMLR, 13-18 Jul 2020.
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately describe the proposed exploration scheme (feature perturbation), theoretical contribution (an (dd'T) regret bound for randomized algorithm, benefiting from ri), and extensibility beyond GLBs, which are elaborated Sections and 7
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Appendix G
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper states assumptions (Assumption 1 and 2 and provides detailed proofs for the main theoretical results (Theorem
Section and Appendix |
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The paper describes the experimental setup, datasets (UCI benchmarks and MNIST datasets) Section and Appendix H The appendix provides network architecture and hyperparameter details.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
15

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We have included the code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: It is stated in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are reported in Section 7 and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:///rrrrsscccaaal//ccccccaaa
Answer: [Yes]
Justification: Our work fully adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical results and therefore does not discuss socictal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Not using existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www contett datasets,paperswi has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The study does not involve human participants or sensitive data.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We used LLMs only for writing and editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy htttps://neurips. httererrrpp..c///ottfaeeress//// for what should or should be described.
20

---

Appendix
Table of Contents
A Further related wokrs
21
B Properties of FP distributions
23
Application of FP algorithm
24
Generalized version of GLM-FP
24
Application to the linear handit problem
24
D Table of notations
25
E Proof main theorem
26
Lemma
26
Proof Lemma
26
Proof Lemmal
27
E.4
Proof Theorem
28
F Proof supplement and Lemmas
36
F11 Supporting Lemmas for main proof
36
F2 Auxiliary bounding incqualities
38
G
Liiitations
38
H Experimental settings and additional results
39
1 Experimental details
39
Additional experiments
40
A Further related wokrs
Landscape of GLB Algorithms. Generalized linear bandit (GLB) algorithms can be broadly divided into deterministic OFU-type and randomized exploration--asse based methods. OFU approaches such GLM-UCB 17 and Logistic-UCB (26] achieve the tight ((d/T) or Ö(dVT/k) regret bound, and refinements further improve confidence construction (27. achieving ((VTT log K) in the finite-K K arm setting. Abeille et al. 4 provided instance analysis showing that the
regret can benefit from the curvature constant K,, achieving Dddvn.T Subsequent works [36]] 37 relaxed the dependence on S or improved computational efficiency [16] while preserving the same order. Randomized methods such Thompson Sampling (TS) and Perturbed History Exploration (PHE)
3
6
31 32
as well as more recent algorithms like EVILL 25 and RandUCB [46), typically
achieve superior empirical performance but incur an additional vd penalty in the worst case, yielding D(d3/2VT) for infinite arms (d log K k) for finite arms. Our proposed feature perturbation (FP) departs from parameter- or pertrd-petturbation by randomizing the input features, thereby closing this gap: as summarized in Table A.I. FP is the first randomized algorithm for GLBs to provably achieve O(d/R, d² (//s) regret with dependence K, unifying the tight guarantees of OFU-type methods with the empirical robustness randomized exploration.
Comparison to RandUCB Algorithm. Our linear variant LinFP (see C.2) and RandUCB [46
coincide in the linear bandit setting. Both sample randomized scores fi (æx) (2 3 | |= and couple the arms identically, yielding matching ((dvT) regret bounds. The difference lies only
21

---

Table A.1: Representative GLB algorithms: regret bounds and source of stochasticity.
Type
Algorithm
Regret Upper Bound
Stochasticity
GLM-UCB [17
Ö(dVT/k)
Deterministic
Logistic-UCB-2 26
O(dvT+ +
OFUGLB 37
OldERT + /k))
LinTS 8
O(d//3/T/K)
Parameter (#)
GLM-TSL 32
O(d//VT/Kk) O(891///RK)
Parameter (9)
Randomized
GLM-FPL 32
Reward (r)
RandUCB
O(dVT/6) O OdvVR.++&PM
Linear utility (x: ToTo ()
GLM-FP (Ours)
Feature vector (x)
in the source of randomness: FP perturbs the input features, whereas RandUCB perturbs the reward estimate itself. These distinet mechanisms collapse to the same Gaussian rule under linear models, though they have been analyzed through different theoretical perspectives. Equivalently, one may view RandUCB as a special instance FP with an identical perturbation distribution, differing only in interpretation and analytical framework.
In generalized linear bandits (GLBs), however, the two algorithms diverge fundamentally. RandUCB extends its linear recipe by linearizing the link functtio, introducing multiplicative x penalty and yielding regret bound of (dvVT/ss) In contrast, GLM-FP perturbs the inputs directly using curvature-aware Gram matrix that weights past features by (uxx'' (.), enabling both anti-coneentration (for exploration) and concentration (for confidence). This yields tighter regret of (dd/k,7) linear in d and directly in K., Conceptually, FP injects stochastieity before inference, that each sampled reward f(ō) remains within the hypothesis glass-preservingg inductive bias and reflecting epistemic uncertainty. RandUCB, in contrast, adds randomness after inference, producing post hoc scores that may not correspond to any F. As result, in expressive models FP remains aligned with the model structure, while RandUCB may misalign exploration incentives, leading to divergent empirical and theoretical behaviors.
Geometry and Scalability in Randomized Exploration. Recent studies have examined when ran- domized exploration can match the Ö(dVT) guarantees of optimistic approaches. Abeille et al. (5) strongly convex, and smooth action sets-unde
identified a class of geometric conditions-aasobble which Thompson Sampling (TS) achieves optimal dependence on d. While these conditions provide valuable insights into the role of geometry, they often fail to hold in high- nigh-dimensional or unstructured settings. Subsequent works 32] further clarified that posterior variance inflation can inherently introduce the extra Vd factor observed in randomized methods. In contrast, feature-level perturbation achieves similar statistical optimality under the standard boundedness assumption, bridging geometric optimality with more general feature-level regularity. From a computational standpoint, randomized exploration in large or continuous action spaces raises significant scalability challenges. Several strategies have been proposed to mitigate this issue, including lazy or delayed updates of the Gram matrix M. two-stage candidate selection using approximate nearest neighbors, and optimization- oracle-based methods such as batched soft elimination [22). These approaches highlight a trade-off between statistical tightness and computational efficiency: while algorithms like FP prioritize theoret- ical optimality in the online setting, batched or oracle-bace based techniques offer scalable alternatives for large-scale practical applications.
Connections to Feature Perturbation in Broader ML Feature perturbation is a common idea in other areas of machine learning, most notably in computer vision and natural language process- ing, where it is employed for robustness or regularization during training. Examples include data augmentation (4), adversarial training (20), or NoisyNets for exploration deep reinforcement learning [18]. In these contexts, perturbations are introduced at training time to improve model generalization or robustness. contrast, our algorithm introduces perturbations at decision time principled mechanism for exploration in online learning. This distinction highlights the novelty
22

---

of FP: rather than making a static predictor robust, we leverage feature perturbations dynamically to induce stochasticity in action selection, enabling efficient exploration. The same principle applies naturally when contextual information comes from high-dimensional embeddings, such as ResNet or ViT features for images [23 30 or BERT embeddings for language [T3, where FP can induce semantically meaningful exploration by perturbing compact representations. Thus, FP not only closes a theoretical gap in contextual bandits but also suggests a unifying exploration paradigm that resonates with broader trends in modern ML. Finally, this perspective also provides bridge to reinforcement learning (RL), where perturbing the state-action feature representation can serve as an efficient alter- native to parameter-space randomization used in posterior sampling Noisy Networks [24] 42 [50]. Extending feature perturbation to structured settings such as Linear MDPs or value- funleffnntionn approxi- mation promising direction for future work, potentially unifying exploration principles across bandit and reinforcement learning paradigms.
B Properties of FP distributions
Perturbation in Thompson Sampling The perturbation distribution utilized in the TS algorithm bring randomness to the parameter, as described by Abeille and Lazaric [3] is followed:
Definition B.1 (Definition 1. in Abeille and Lazaric (3.. DJS is a multivariate distribution on IR4, absolutely continuous with respect to the Lebesgue measure, and satisfies the following properties:
(Anti-concentrattinn) There exists a positive probability > such that for any unit vector u E RR
Pe-DIS ( 2 1) Pp
(Concentration) There exist positive constants and d' such that for all ô (0,
PENDE (I51 S vedlog(dd/0)) 2 1 5.
Below, we provide examples of distributions satisfying these anti-concenttaaion and concentration properties, with the latter condition restated in Eq. (2) in Section 5
Example 1: Gaussian distribution Ç ~ NO, I) The concentration property comes directly from
Lemma F.6 as the inner product of standard multivariate normal random variable Ç and an arbitrary unit vector u follows a standard normal distribution. In the same manner, for unit vector u,
PC (n 1) = 12~A11.11 (= 2 1) = erfe(
(B.1)
4VER
Thus, the standard Gaussian distribution satisfies the concentration property with c = = 2 and anti-concentration property with p 4.ear Adjusting the scale of the covariance matrix, we can easily prove other variants satisfy the conditions.
Example 2: Uniform distribution Ç (o, Let the random variable Ç = rv, where r = KK E j0, V and v = </l<| is unit vector. Then, T ( can be expressed as the product of two independent random variables, r and Tu (~ Beta(} 2 variables follow the distributions:
d-1 )), as r. (u v). These two random
fr(r) dr
r(g)
r [0, Vdl. and fuT,(x)
(1 23) x x-
= r r d r
Based on these random variables, we can write:
fat(())= 1: [" (ee-rr)f((() (x--
Using Monte Carlo simulations, we observe that u TC has a lighter tail distribution compared standard normal distribution. Accordingly, proposition 9 and 10 in Abeille and Lazaric (3],
è' 2 satisfies the concentration property. By
P(u < 1211= 1
d
16
where (a, b) the incomplete regularized beta function. This suggests that the Uniform distribution satisfics the anti-comeentration property with 16V37"
23

---

C Application of FP algorithm
C.1 Generalized version of GLM-FP
In Section 4 we introduced how FP can be applied to the contextual bandit settings in which the reward model extends beyond generalized linear models. We provide the general algorithmic framework below.
Algorithm C.1 Feature Perturbation in Bandit Problems
1: Input: Regularization parameter À > 0, tuning parameter {ct}
2: for 1, 1.2..... T do
3: Compute = argmin fer Σ (f(zra,)) -r,)² via a least squares oracle P e.g., D(a En,) = Na I/t)
4: Sample Tыi ~ D(r 2xi) for all
5: Select arm in = arg max f(TH:)
D either i.i.d. or via shared perturbation
6: Observe reward ra = f (xt,ii) +
7:
end for
C.2 Application the linear bandit problem
While line in Algorithm C.I merely defines the sampling distribution for each arm, in prac- tice tice-mirroring the design of GLM-FP-one may introduce shared perturbing factor that is first sampled and then applied to all arms. This construction induces dependencies across the perturbed arms and can serve as the basis for the arm selection mechanism.
Algorithm C.2 LinFP: Feature Perturbation Linear bandits
1: Input: Regularization parameter À > O, tuning parameter {c
2: Initialize: Vi < AI, bi <- 0,2
3: for = 1, ...,..... do
4: Compute = -,
5: Sample ~ N/ (0,
Shared perturbing factor
|
6:
Compute T. = Iti +
Ge for all
16.11
7: Choose i, arg m TT
xT (I for all i.
8: Observe reward rt- = ,,,,, 8" &
9: UpdateVi41 V 21,;, -
bit1 be + Pt,i
end for
In Section 6 we compare LinFP, the linear variant of our approach, to LinTS 3 6). The primary algorithmic difference lies in lines 6-7 of Algorithm C.2 In our method, the shared random vector Se used to perturb each feature vector. In contrast, LinTS perturbs the model parameter as = + c: V 1/2 Se. and selects the arm maximizing 0; For LinTS, we have:
1/2 B[2 IT + G. xT VTVVV / = xT
Var Var = a Varl 1/2c)] ot x.. V. Je -011001111
While the marginal distribution of N, 0 under both methods is identical, the use of shared perturba- tion & in LinFP induces algorithmic coupling across arms. This distinction is further discussed in Section
24

---

D Table of notations
This section introduces additional notations and concepts essential for the analysis. For ease of reference, Table D.1 summarizes the key notations defined in this paper, along with newly introduced notations. Conventional concepts such as d, T, A. C, X, K are omitted here. The concepts will be reintroduced as needed in subsequent sections.
Table D.I: Notations and concepts for the analysis of the main theorem
Notation
Definition
M
Self-concordance constant
Lipschitz constant of the link function
C.
Lipshitz constant of the negative log- log-likelihood function
(,
probability ellipsoidal relaxed confidence with regularization true parameter
48=A 2(1 5M,) /1g) dlog((2 Ō(v
((6/447)) (c, d': constant satisfying concentration property)
((())
E I 0,11 (4T
6.
Average derivative of link function the optimal rounds
Minimum reachable derivative of link function
Warm-up stage
IT
te [T] (IV 01)
0.) aap 2 1) (lady, 2 1)}
Taylor remainder term
(e(x)
Jo w)i 0. u(x T0, - aTd.
(0)
fo w) (x] 0 u(xlv v- x. x)) du
Matrices
V,
D + AI
V.
Σ
r=1 R + +l/R
A.
Σ
MoT d.a AI
H:
Σ
Mr] O, 0, +
(,,0,))
Σx as (0, D
Other notations
R"
maxrex |n(2 (0))
6.
(6) [xx [x=T0)
(r()),
(.y | 0) ulx 0+)
(g))))
constants related to standard normal distribution (p = 1/(4/e/))..oooo = 2og (2/8))
25

---

E Proof of main theorem
The first step in proof is to derive the high-probability confidence bound for the estimate d.. Using this bound, we ensure that the events defined in Definition occur with high probability. Finally, we compute the regret bound of our algorithm under these events.
E.1 Proof of Lemma T
We rederived Theorem 3.2 of Lee al. 37 obtain tighter bound with improved dependence on the regularization parameter X, such that the À term no longer scales with Mμ-
By Theorem 3.1. in 371. with probability least 1 8, for all 1, the following inequality holds:
2eSLL
1,(0*) - (x() log dllog
Wa(
d
Then observe:
1 (1 V) (0,+ 0.))du (/¹ (1-1))
t-1 Σ (x0 (0: + uu00 a du u)
Σ (1 - u) (0, + u(f - ( x, = He, 0*)
a (-)
where the second equality follows from Fubini's theorem, where the order of the integral and the summation can be switched. Using Taylor's ss theorem with integral remainder (Proposition F2 we can further deduce that, with probability 1 - 8:
W.(d)² > L.(0)) - Lo.
=(VL,(0), 0" - 0.) + (8* 0,)T (L, (1 ([ uL)-v + u(0 -b)))du) (0r -.).
As the optimality condition Ú, infers that (VLr(0.), - 2 and by equation we have that
Proposition F.1
2 > 10 - 0.11 (., 2 2 2SM,
-
110 - 0, -0,1 0.112,-AX
(Proposition F.1
where the last inequality holds, since
((x 0c)
H.,00, 0*) -
(E AT).
2 + 25M
2 2SMH
Accordingly,
|00- -. S =110 -0.1 - +
45 -
2(1 SMM,) =8,(8)²
and by Assumption 1 finish proof.
E.2 Proof of Lemma
Let the event E, be defined as E, = { (M 0.) 2 {()T0)). This event corresponds to the case where the chosen perturbed feature vector yields an optimistic expected reward relative to the true optimal arm at step To bound the anti-concentration probability required in Lemmal aim to
26

---

lower bound Ee Ec, Et), conditioned on the events E, and E, For any t E [T], we have:
Pr Fg Rrg Fs)
Pr [m(r. 0.) 2 (( E Fe)
Pt aī 2 =T=00' Er, Eii)
(:' p is strictly increasing)
P.
(IT,b. = 2 x1 x1/00e Ec, E1)
(.114 argmax xT(..) &El|Xt!
P.
(ih- T 0e) 2 Kiren 0- - 0- -bill
Er. Eri Ei)
(B.187) |0
Pr
01 2 1xce|l87,1 10 50
0 18.
Ec, Es
1del
2 IP ((((8") l A,
(St, ue) 2 B((8') pr
1A, 1 BB, Fa
= ((G un) 2 21) 4 :=
where the third inequality follows from the Cauchy-Schwand Schwarz inequality, and the fourth from the assumption that under the event Ec, we have 10 - 0el1 A. < (8)). The final inequality follows from the naticooncentration property of the standard normal distribution, as detailed in (B.I). For simplicity, we henceforth fix p= 1/(4 /eT) the corresponding lower bound on this probability.
E.3 Proof of Lemma
We now proceed to establish how the probability of each event defined in Definition can be ensured using the confidence bound (5) derived Appendix F.1 Each event is analyzed and bounded individually, and the results are then combined to complete the proof of the lemma.
Bounding ËT
Let 8 = -4/(4T). By the choice of B,(ō) in Lemma have that
ST P (10 0- Il s <3((0') 2 21-8
T
T
from union bound, P
n (10, 0r 11. S SA(68))
21 Σ
P (10
11 2 2x(('))
00
-=
P
n {166 111,, S SB(0)))
21 1 -
Σ
8'
t=1
8 4
P(ÉT) 2 1- - T8' =
Bounding Es The expression for the perturbed feature vector Tii is given as the expression 2Z a- S. with the choice of ct = (e where S. is drawn i.i.d. from (0, T). 1o.1
Fe Fi (8')
Note that the constants e and c' indicated in (2) are both 2, as proved in (B.I). from now on for simplicity, we let cæ == /2 (og/8") Since all arms are coupled with same Ge, we can write
V1 < t TT P YEN E Xei
(āu Iei, 0o)l s <=(66)))2))))=))))
(E.1)
dr 0.) S Scx (.(0'))=ala) )
P
Van E X;; (6(6')
(Ge, 10.1
(E.2)
= (((G ui)l S cx) 2 - 8¹,
(E.3)
'Uncoupled sampling means Cee's are sampled for each arm respectively and it results in extra log K term in the regret bound because of the union bound over the number of arms at each step.
27

---

where is unit vector. The first equality holds by the definition of cø and Definition 1 and the inequality follows from the concentration property. The cancellation in the second equality plays critical role in removing arm-wise dependence in GLB setting. A union bound over 7 rounds yields
P( 1 T8 - = 4
Finally, applying the union bound across the events Ey and Er, we have that
P(ÊT ETT) 2 2
Remark. To guarantee the same probability level 1 - 8' as in equations E..1
E.3 which bound the randomness arising from perturbations the feature vectors, Thompson Sampling requires the confidence parameters | and ry to be inflated by an additional factor of Vd. This inflation arises due to the right-hand side of the concentration bound in Definition B.1, which scales with vd. Such adjustment is necessary to control the deviation in the perturbed estimated expected reward, which takes the form
(0 0). This is consistent with the reasoning discussed in Section
E.4 Proof of Theorem
In this section, we establish the regret guarantee for our algorithm. Given the complexity of the analysis, we divide the proof into multiple steps. Supporting lemmas and their proofs are deferred to Appendix
Step 1 (Warm-up) We begin by partitioning the rounds into "warm-up" stage and the primary stage. The set of time steps corresponding to the primary stage is defined as:
(IVMloT 0c)
$1) H
(lecle, : {1)
IT tE [r]
where Hy Ve, and 0g are given by:
H. = + Σ (x 0
V= XI/K+ Σ 7=1
0;:= argmin úax 0).
The introduction of He is crucial because A, = + E Mxx 0z) x, depends on f, which prevents direct application of the Elliptical Potential Lemma (EPL; Lemma F.I.. as discussed in Section[5] To address this, we leverage H,, which incorporates the minimum derivative of within future confidence sets (0z), ensuring it serves smaller Gram matrix suitable for bounding the regret. Similarly, V is introduced to directly apply EPL.
Next, bound each weighted 2-norm using the Elliptical Potential Count Lemma (EPCL; Lemma F2), which guarantees that the regret incurred during the warm-up phase remains man- ageable. Consequently, the cumulative regret over T rounds is decomposed follows:
R(T) = Σ (M(xTT)) M(xT00) + Σ (u(xTT p(x, 0*))
IT
Reg(T)
warm-up regret
T Σ1
| ulzz 0.)xz.
T Σ
2 21})
< Reg(T") + 2R"
21
I
1=1
4d
Cu
K
Reg(T)) + log 2
log
1
+ log
1
A llg 2
X log
where Rº maxzex |u(x 0*) the maximum expected reward achievable under the underlying model.Tho The first and the second inequalities hold from the definition of I, and by EPCL (Lemma respectively. Note that the warm-up regret is Ödd), which is independent of T.
28

---

Step 2-1 (Decomposition) components:
We decompose the cumulative regret for the primary stage into three
u(5, 0:) (Tg(T) = Σ {u(IIT))
[a 0c) ua(a, 0z) + { {ula, 0c) ulax 87)
IETT
Ag
Here, A, and B, relate to the perturbations' effect the estimated reward, while C2 concerns the closeness of 0g 0*, We will bound each term under the events E, and Ec.
Bounding C. Bounding Ct is straightforward. Using the confidence set (r X), abbreviated as O we define (r()) as the pair maximizing the confidence width computed on the selected action 0.){
round 2t, after round know that 0 E 6r for all t < - T. Thus,
| 0) -=x:0,)) Under the event E,,
G.1 c E Ed) (M(_T0.)m(xTo0))) 1 Be E.) s ulxt we) - ulxt (0o0) / nEBn
Bounding B, Let के == argmax [u(xT0,) - mlz,T 0.) Under the event E,, T. Ex,,)
holds and we can write:
B.1 B. = (u(T, 0.) --xxxxxxx 1f Enj s |u T.)) - m(xT0.) Er B
Before proceeding, note that for T. Ex(2)), with an integral remainder (Proposition) F.2). Define ā, for (1 u)),),((,, + (uxxxx 0g To,
derive upper bound using Taylor's theorem
xx 0.) dd, which accounts for higher-order terms based the estimated parameter Or and feature vectors and Tr. The difference px 0.) - pxxx 0.) then can be bounded as:
22.0. ( (n(TTT 0.) - =))((
|M(TT 0.) uxx77 uxxTT00)] = iM 0.) -x,,0) +
SaTo.
+ ( xe, 02) 1 (1 (1-u) [x] 0, u(( 0, xx7 0.)) du
(To Ize 0c)
+ M₂ (T. x:. 0i) ('(1 (1 u)j [1] 0, + u 0. x 81) du
s A1xxT
(3. - (82-21,00) 0e)
s iisx (ix- -xx,b,)
+ (f, zr, 0z)
S Ma (1))) (B. (6')
where the second and the last inequalities hold from Assumption 2 the definition of (xx)) in Definition [] This bound captures both the linear and higher-order contributions to the regret from perturbations in the feature vectors.
29

---

Bounding A With E, = (p(oT 2 u(x))00) and 3 defined above, we write:
A, E1 n }.} (u(x)0) ((1 1 E
(1 81) 1 Es n }.} p ((xTT0)) inf
(.EE((1)))
- E,
[ 0z) 8.EE((m))
inf
11 6i) I n Eig 1ig
(u(z) 0.) ul2, u()) ( 3.Ee((Ee) p6 Bi)
E Er, Es P(É: n Ed)
E,
inf
( ( sup
| 0.) m(xT Er, Er, Es P(B, E.)
$ 2E,
(..E((o)))
2 p
[ -1xx 0.) 11 ((BnnE.))
< Br
We justify the second inequality under the specified event, and the final inequality follows from the following reasoning: we use the bound C - [ Z 2 C]. and compensate for introducing the conditional expectation by incorporating the inverse of the probability of the conditioning
event. Specifically, define C' := (u(x,T_0*) inf,, μ(z T 6.) 1(0 É, n E,) and Z == (n(#, 0,)
inf, ju(x 0.) 1( Es n Ez). Then the second inequality holds. To compensate for conditioning on the favorable event, the following logic:
E3 {
E., E.
2 E
E. Er Es Pr(Ee
E,, E.)
2 E, Er, E. Ee) p.
(Lemma 3
The upper bound for this term is similar the previous part (Bt), differing only by constant and the inclusion of the expectation over the filtration. However, since our goal is to bound the cumulative sum over T rounds rather than the expectation itself, directly handling the expectation complicates the application of the Elliptical Potential Lemma (EPL). To address this, we eliminate the expectation at the cost of introducing a concentration error, which we control using Azuma- coema--offddig''s 's inequality.
Step 2-2 (Azuma-Hoffdding inequality) Unless otherwise specified, we now analyze the regret bound under the assumption that events ËT and Er hold.
P
Σ A
S Σ Ee
[1(3 0.) (xxxT00))
2
1ETT
tETr
< (ō') Σ
ja 0.)) + (T()
Σ E1
Be
( (e)lell, . Aaxx7 0.) l CeallA,
tEfT
11
(orr(
Σ AE
aataallllll + (
Bg ( Pa. -
te
Note that R1 and R2 are constructed as martingales. Since the norm of each feature vector satisfies |ar < 1, and given i1,1 3 ir,1 I/> and jixx]] 0.) < Cy. the following bounds hold:
Cn. VX
0 S [xx 0,) S C. x7 i x, S Cu |
This provides an upper bound for each instantaneous element of R₁ as L./VV. Applying Azuma- Hoeffding's 's inequality (Proposition F.3 with probability at least 8/4, we obtain:
2T #
Rí
S
log
8
30

---

Due to the convexity of e the term ji in ār (2+) is bounded by L/.. Consequently, we obtain:
(x(x) = [ (1- u)j (xr O. + u(x' 0z -x 0.)) du S [ (1 u) fp/ (E.4)
Similarly, show that
a #7 S fu (2]111
2
Lx Li 2x
S
|011
22
This provides upper bound for each instantaneous element of R2 (2A( Applying Proposi- tion F3 with probability at least 1 5/4, we have:
CT 8
R2
log 8
4X2
By applying a union bound, we conclude that with probability at least 1 - 5/2, both Ri and R2 are bounded. Therefore, the regret term Eier, At can be bounded by:
A NETT
Σ
2 P
(8') Σ j(s, (xxx00)) 0.) + (xrr(6') Σ IETT
as (r) [rd E,
1Elr
where a function T' and defined as:
2
2T
8 log MMrr(8))2
2T
8
=
T
& = (T,
ro (5 p
log
dg X2
412
8
In summary, combining this result with Lemma 3/2 and the bounds for Br and Cr, the total regret Reg(T) can be bounded with probability at least ō as:
2 p
Reg S
+1
Σ El
pr (8))) 0.) M.M + M1 M
Reasp
Σ EE2T
[MxT wi) plxz (x
+e
ReRest
Here, Regep captures the regret arising from perturbing the feature vectors, while RegesT accounts for the estimation error Ó, compared to the true parameter 0"
Step (Bounding Regrp) The presence of मr in the weighted norm makes it challenging to directly apply the Elliptical Potential Lemma (EPL: Lemma F.I. To address this, we introduce H,, which allows to leverage EPL by splitting i= (c) into two components: leading term based on 0, (used in defining Hz₂) and transient term that accounts for deviations from d..
Regep = 2r()") Σ (a 0.) (aelll, + (5')
Σ (xr EEI
(E/r
I 17()") Σ
(i(x, 0.) + (a( - M[x, 0.)) | |, + M (,)
Σ (f
SELT
EEIT
Σ Ma (rr lorll leelll
Σ sEI7
Max Ma 0.) pT (8))
Σ
(
1E17
te
DEP
Bounding Σ, D We define H, == XI E1=1
Then for all T S t. as the
equation jaxx, 0,) < Úū(,, 0.) holds, write:
Å, = XI (.,, = AI Σ M(x x 1 AI + Σ
Mxx 0, 1. 2 H,, (E.5)
31

---

Then, we can bound
E, D as following:
ΣD & vr((')
Σ j 0.) 1z)
rT(0")
Σ IE/T
O1) 0z),
Σ Úa 0s) ( A.
(Cauchy-Schwartz ineguuulllliiiulliiyyyyy
V
V
lElr
Σ
Σ lETT
úa 0s) 0e)
(By (..5
IE
}
$ (T(8")
ju(TT EE
Σ
Σ min L.lly plao 0z)
(Definition of IT)
Applying Lemma F.
the second square-root term is bounded by
{
} $ 2d (1+ CxT)
Σ min
dd
To handle the first term in the square root, we decompose it as:
Σ Mix 00 EETT
EMCITO)+ tET
I
E(1e -
tETT
Note that 0, := uugmingguuee m (8.A) (ax, 0). Let T' be an arbitrary T whose (6 A) contains
d, Then, the latter term in the square root is then bounded as follows:
Σ (ū(a 0.) (((T00))
Σ EE!r
Lú(æ, 0.) ((xTT0)) + Σ (
EE
< M
Σ
| 0c) 1xx1 00)
Σ
|nxo 0*) u(=To')
(Lemma F33
LETT
< MMp
Σ
|xxx 00) -mxx -lxxTo.))
Σ
|lle (((x)0r)) u(xT + Σ - ((0T00))
IETT
1E2r
IETT
< <M,
2
Σ
pt wi) - ulxr Orco)) Reg(T)) S My (2ReBEST + Reg(T))
IEIT
where the second inequality holds from triangular inequality. For the last inequality, we leverage the definition of Og and the pair(T((), wt), as shown below:
p 0.) - p(x] 0.:) S
|aao 0) plxz 0,-)
max (0
pax TEE,
u(xx ((x.TO0) |u(x, - M(TT (rw))/
max
and that under the event E, as 8* E Ure(e.T (7, A), we can easily show that the second term |u(x:] 0..)) uax:] (*)] can be upper bounded by |n(x; w,) =xxx.T0.0))))) (e))) Note that after decom- posing Reg(T),
currently in the process of bounding its individual components. However, during this process, Reg(T)) itself appears in the upper bound. This issue will be addressed in Step 5, where we will provide strategy to effectively resolve this recursive dependency.
Bounding E. FP We define the Gram matrix V. == AI/K + 1 I. The introduction of this matrix is to apply EPL as in the previous section. As the weight pi= on the weighted Gram matrix H, greater than or equal to k == min ju(x T 0), we have:
A, = XI Σ (ax O 0.)...T 2 K
I +
Σ
x
2 RV.
(E.6)
32

---

Then, we can bound
E, E as following:
Σ E S rT('))
Σ
ci(xz 0c) in(2ré 0c) Ikoill
Ellr
s M, (T
Σ
[x 0c) m1(0 0a)l lall
(Lemma H3
1ETT
I
S M
Σ
[a wi) ulz, (r(0)) leclo-"
R
(Lemma F.4
IET
where the third inequality holds from the definition of the pair (r(t), and by (F.6) Here, Lemma F.4 plays crucial role by introducing the weighted norm [ which enables the application of Lemma F.I. Utilizing this lemma, further proceed to bound as:
2
Σ tETT
Et" S ( K
Σ min 1, |2
12
(Definition of Ir)
1=1
4 dM,C NT (8') log
RT
1+
(Lemma F.I
dd
where the final inequality use the fact that (r()") cs (T((')) 2 (T()') as cs 2 1.
Bounding E.
The process closely resembles that of bounding E.P. we have:
Σ rt < (5TT(6')² sElr
Σ
ā (T+)
s fu (8))
|xc 1
(By E.44 and (E.6)
2x
tetT
< fu M vrr (5')²
Σ min
(Definition of Ip)
2x
d < M, MaC log (1+
RT
(Lemma
d)
Combining all three terms, we derive an upper bound for Regyp S E, (DFP + ETP + FPP) as follows:
C.T
Regep S (r((0)
2dlog
1+
RR.T + M, {2RegEsT + Reg(T))
di
5d + k
KT
McCurT
log [+
(E.7)
dd
Step 4 (Bounding RegEsT) Next, we proceed to bound RegEST The overall process closely mirrors that of Regep- To begin, decompose each instantaneous regret term. Let ā.(0), 02) E - (x; 0, + uxx 0g - x. 0g )dd,, which is derived from Taylor's theorem when estimating the regret for the selected arm 2, using two parameter vectors, 01 and 0g. Using Proposition F2
33

---

expand the instantaneous regret term as:
|n(a wi) - 1(xx 0-())] = ju(x; (rr)) f-(1)= srim (u(a, 2)((()ddz
$ i1x (r(1)) (1re, - -dress + (rr, - -r(o)) I (1 (1-w)) u1-uw]p j x.
(x,T00(e) 0 + ulxz wi - 2, 0r(e))) du
s úd (,)
- Brcoi + -
- 0210)2 /'" (1 - (1-w)j x Oris) + =u(x] we 2 0r(o))) du
(.,(0.
[i(x:Tbr 0,) + [i(x;] 0.) -M(x) 0r(0))) - -0-())
+ M)0ar(0(0)::))a:::
0r(1)) -
[xx 01) + ji(z) 0.) - -u(xx -(xTT=(0)) Kreewe --()))
+ +M wr) (8') 177.70
where the second inequality follows from Assumption 2 and the last inequality results from the Cauchy-Schwartz inequality. The key distinction between bounding Reg,r and Reggst lies the use of B(6') instead of ((8). The first term then can be upper bounded by the following terms, using triangular inequality:
(pxx) 0.) + |i(x7 0.) iña 0r(0)) I Iaza laz - 0-(olA
$ ji(o (.) (8 Iorel + ||((x 0.) jn(o 0.) 1x
DEST
FEST
Bounding E, DEST By the equation to upper bound each term. We have:
E.5
instead of t-dependent He, we use only dependent He
EDST
D.ST= < 3T(0') Σ
Max 0.)1
(1 (t) T)
1EI9
CpT
S $T(0')
2d
1+
Σ MxI0+++ Σ (M(xT - ((zT,0))) tE
dd
FppT) dA
V T + Mp (2RegEsT + Reg(T)).
S $
2d
1+
Since the derivation proceeds identically to the case of Σ, D.P. with the only difference being the use of Br in place of ?/, we omit the detailed derivation here for brevity.
Bounding E. FEST
Following the bounding process of E, FFP. and using the equation E.6
Σ LEIT
EST < Br 36')
Σ
(a 0c) (1 0+) |Ialla,
(1 (1))(1)) ()
LETT
4d M, 3r log (1+
KT d)
Bounding E, PEST For ai (,(0)(),, :=
:0 S/' uIx 0r(0) + u(aJ wi [.] xxTT0(())))))))))))))) as shown
in (.4), it follows that (,,00 wi) S 22p/2. Following the bounding process of E, FFP.
FEST S M ( Σ
ae (Tie)
|x 18
(1 S ((1) S T)
NEIT
IE
d <
KT
Br (r
log 1
k
dA
34

---

In summary, combining three regret components, we bound RegesT S E, (Di + E + F as follows:
(1+ V
CxT) di
Regre S (r(6") 2dlog
/RTIT + Mn {2RegEST + Reg(T)}
+ Mn MrL,BBT(8) log
1+
KT
(E.8)
Step (Solving equation) The equation (E.8) is indeed cj. times the equation E..p. There- fore, both Regpp and RegesT can be bounded using the regret bound of Regpp- Let Regmax = max (Regpp: RegEst). and we can bound Regmax with the equation E.7
Then we have,
(1+1)
_ +2 Regmax + E;
Reg RTg(T) S
Regrp RegEST + +
and accordingly, we get the following inequality:
(1+
CnT
NR.T+ Mn (
Reg S Strlld) 2d log
)
+4 Regmax +
dA
5d
1+ KT
(6') log
dd
Now, The bound takes the form of Reg Regmax defined:
S AABB B + &.Regeaa
D. where the following quantities
C.T 1+
A: 700'0 2d
Ö (d)
di
B = K.T + My5= =
KoT + dv X2
2
C = Mp
+4 = -1(1)
P
D = 5d
( log (1
RT
d
dA
focusing on the terms involving d,T, and k. With the choice of A = (dd) and applying Lemma F.5 the upper bound for Reg simplifies
Reg - (ō(KRTTT&
de
-0=0 d
K
Now, combining all terms, the cumulative regret R(T) can be bounded as:
4dR
Cu
R(T)= < Reg(T") +
log
1
+ log
[+
log 2
Alog 2
X log 2
+ Regmax +E
= dv K.T + d² + dg
δ ( A./K.++ d²
(Choose = O(d)
K
X2
Our derived regret bound, δ (dvRi R.T + d
/x), +d//x).
aligns with state-of-the-ard regret guarantee
15
36
37
35

---

F Proof supplement and Lemmas
In this section, provide key propositions, lemmas, and inequality bounds that essential for the main proof. These results serve as the mathematical foundation for the regret analysis and other theoretical guarantees established in this work.
F.1 Supporting Lemmas for main proof
Proposition E.1 (Lemma D.I. Lee (77) Lel p be increasing and self-concordant with M Let 2 C ((S) = (= R | S {} in R. Then for any 21, 22 E Z, the following holds:
L. (1 (1- (i-w)A(zi + u222 - -11) 2
id(21)
2 2+ 2SM
This proposition establishes a lower bound for the integral involving a self coff-ooncordnnt, particularly useful for controlling weighted norms and derivatives in regret analysis. The following proposition provides the well-known Taylor's 's expansion expression with integral remainder. We highlight specific cases that frequently used throughout the main proof.
Proposition F.2 (Taylor's Theorem with Integral Remainder Form). Let n 2 be an integer and let the function f R + R be (n + 1) times differentiable at the point zo R. Let f(n) to denote its n-th derivatives, then (x) can be expressed as:
f(x) (100
(x (x-xo)² =o)² 1
["
{ f(u+t)(t((z
tt"
i!
no. ao
Especially for n by letting t = xo + uls - xo), (xx) can be expressed as:
=(=)= f(oo) + I" (()dtt f(1o) + (x - xo) 1/" f
f'(2o (zo + u(x zo)) du
(F.1)
Especially for n = by letting t = 2o + u(x - Io): f(x) can be expressed as:
f(x) = f(zo) + f (2) - x00++ + I" ("()(x=- - t)dt
100
f((o) (z - x0) {²² (" + u(x zo)) ((1 u)(x xo)) (x zo)du
= =((o)) + (z - 2o) + (x - zo)² x0)² f f" (xo + u(x - zo)) (1 - uddu
(F.2)
Similarly, with multivariate function f R.a IR and n we have that:
0
( z0)? f (1 - u) Ou?
8²
f(x) = f(xo) +
f(z0) - x00) +
Σ
fao + u(x - xo))du
1=1
i=1
+ Σ 2(x zo)i(x -xo)s //' (1 u)
fwo + u(x xo))du
Daz axr
itj
= + ( (o)- -x-xoo) To)T (f. (f(1-w)7²) + u(x moo) (x xo).
The following lemmas provide critical tools for analyzing regret bounds in the context of bandit algorithms. Specifically, they focus on bounding terms that involve weighted norms of feature vectors under Gram matrices. These results are pivotal in deriving efficient bounds on cumulative regret and exploration.
Lemma F.1 (Elliptical Potential Lemma). let {5r)TE) be a sequence RRd satisfying |x S Ro all t < T. For gram matrix V₁ == AI + Σ1=1 IT we have that
R²T
min 11, 12s 1 2d log
1+
d)
36

---

Lemma F.2 (Elliptical Potential Count Lemma). For R,c > 0, let {ae be sequence in R
satisfying lael I for all S T. For gram matrix V, == AI Et 2 the length of the sequence Nr E [2] | > of is bounded as:
2d
R
W v
log (1 Alog(1 + c²)
log(1 (1 + c²)
The following connects the smoothness of the difference in μ. Lemma F.3. For v.yE R, la(xx) ju())l Mp lu(x) p(y)).
Proof.
li(x)) - /((0) = (xr y) I july + u(x u)
(By F. with = ji)
S 8l S' lily + u(x --)) du
s My la - ya S iuly + ulx - v))
(Assumption 2
= ~Mp (xr y) ( iuly + u(x - vu
= =M (m(x) - u(y)
(By F.1 with f ())
where the second equality holds since the integral term is positive as j 2
The following lemma bounds the difference in values, using linearization as in the previous works.
Lemma F4. For any t 2 1 and 01. 02 E Or()), we have the following:
|u(xT 01) plx1 02) s 2Tr (8) A
Proof.
|u(x 01) -n(== 02) [00,00 01 - 02) / is 02 + ulxT 01 x 02) )du
(By F.1
-10 - } 1, Cydu
- |Ialll
(Cauchy-Schwardd C, Lipschitzsesss)
S Cu bel
{10- - - ( + 102 dr
(Triangle inequality)
s (8') Collaalll
< (2
|xel Lxclvzz
(By E..6)
s 287 C.,
|2
(t (()) T
Lemma F.5. Let A, B, D, e Rt. The following implication holds:
x A D x APC + D)
Proof. let f: + x² - pz for p.q > 0. Then the roots for f(x) = 0 are:
p -
22 4g
I 22
2
37

---

Now, as is a convex function, x² - pz + implies:
p+ vp² 4q
p (D=2 = -+ V
x S max (2) S
(triangle inequality)
2
And accordingly, we have:
ESpVE +
Vospt V/
(p vq) S 2p² 2
(F:3)
where the inequality holds from (x + y)² - 2(x² + 3²). Then according to the equation (F3
x AVB+CX+
X 5 + AVB+1
(triangle incquality)
2 -)
F.2 Auxiliary bounding inequalities
We introduce key probabilistic inequalities and bounds frequently used in the analysis of randomized algorithms. These results provide tools bound the probabilities of deviations and concentration of random variables, which are essential for deriving high-probability guarantees in the main analysis.
Proposition F.3 (Azuma's inequality). Ifa super-martinged (Xi)120 corresponding to a filtration H4-1 satisfies [X, X4-11 < for some constant for all t 1,..., T then for any >> O,
a²
P(XT Xo 2 a) 2exp
2 2I ct
Proposition F.4 (Chernoff bound). For random variable X and its moment-generating function M(t) E [e
P(X S inf (t)e-
1>0
Accordingly, for random variable following standard normal distribution (i.e. X ~ NO,
12
PP( 2 a.) < inf expl lox) =
120
Lemma F.6. Let z be random variable sampled the standard Normal distribution. Then for all E (0, 1),
P([2 S /21og(2/6)) 2 8.
PP[[ a:) 2P(2> 0) 2e- x? Set the right-hand side
Proof. By proposition Proposition F.4 as 8, and get / (og(/)).
G Limitations
Our analysis focuses structured settings such as generalized linear bandits (GLBs), where feature perturbation achieves both strong empirical performance and provable regret guarantees. While same principle shows promise in more flexible non-linear models, theoretical guarantees in these broader settings remain open. The current formulation, though practically effective, is heuristic outside the GLM framework and lacks formal justification under complex function classes. Extending the theory to overparameterizee or general Lipschitz models represents an important direction for future work, where feature-level stochasticity may offer stable alternative to parameter perturbation.
38

---

H Experimental settings and additional results
H.1
Experimental details
The GLB experiments entirely synthetic and computationally lightweight. All GLB runs were performed on a standard CPU server equipped with an Intel Xeon Silver 4210R processor (40 threads), with each run completing within few minutes. The neural bandit experiments were conducted using a single NVIDIA RTX 3090 GPU. Due to the moderate model size and limited data horizon, neural runs for each algorithm completed in under one hour. Overall, the compute requirements were modest, and no large-scale pretraining or extensive hyperparameter tuning was necessary for any of the experiments.
H.1.1 Generalized linear bandit settings
We consider time-varying set of K = 100 arms per round over horizon of T = 20,000 (linear) or T= 10,000 (logistic). Context vectors and the true parameter vector 6* are sampled from a standard multivariate Gaussian distribution and normalized to satisfy the boundedness assumption. In the logistic case, we use the sigmoid link function μ(x) = 1/(1 + =)*) and constrain ||0*|| S 4 so that the logits lie in [-4, 4]. For the linear bandit, the reward noise is sampled from (O, 1). We vary the
feature dimension d over {10, 20, 403. The confidence level is set as 6 = 1/T, and the regularization
parameter is fixed À 10
Baselines and tuning. For linear bandits, we compare against e-greedy 33.. LinUCB D.
LinTS 6). LinPHE (31], and RandLinUCB [46). For logistic bandits, we include s-greedy, OFUL- GLB-e (77. LogTS (32). LogPHE (32), and RandUCBLog. All hyperparameters, such as inflation
factors and learning rates, are tuned according to the original papers. We fix Lu 0.25 and use minimum link derivative of 0.25 for numerical stability in the logistic setting. For TS- TS-based algo- rithms and our method, we set the inflation parameter as c 1. For e-greedy, we use an annealing schedule & = /Tt with & 0.05.
H.1.2 Neural bandit settings
Objective. Following Zhang et al. [51] evaluate neural contextual bandits using classifica- tion tasks on UCI benchmark datasets 440]: shuttle, isolet, and mushroom. These tasks are transformed into multi-armed bandit problems via disjoint model construction (cf. Li al. (38)). For k-class classification problem with input dimension d, we construct a kd-dimensional feature representation by placing the input vector x into the corresponding class slot: x1 (1:; O:..... 0),
I2 = 10 z :)) and so on. Each x; is treated as the feature vector for the i-th arm. A neural model predicts the reward for each Ty and the agent selects the arm with the highest predicted reward. A reward of is given if the selected arm corresponds to the correct label, and 0 otherwise. Regret is measured the cumulative number of classification errors. All experiments are repeated five times with shuffled data. The time horizon is set to T = 10,000 for all datasets.
Neural networks. To study the effect of model capacity, we evaluate two neural network archi- tectures: shallow and deep model. The shallow network consists of single hidden layer with fully connected layer of size d x 100, followed by a ReLU activation, a final fully connected layer of size 100 x 1, and softmax output layer, following the design used in Zhang et al. [51]. The deep network, in contrast, uses two hidden layers with a fully connected layer of size d x 50, a ReLU activation, another fully connected layer of size 50 x 50 followed by ReLU, and a final output layer of size 50 x 1 with softmax. Both models are trained online using the Adam optimizer with a learning rate of 0.001 and batch size of 32. Training is performed at each round using the most recent 32 observed examples. Figure (bottmm is a result with a deeper model.
Baselines and tuning. We compare against several baselines including e-greddy, NeuralUCB [2 NeuralTS [5T], and FTPL B2]. To accelerate training for NeuralUCB and NeuralT', we approximate the confidence matrix inverse using only the reciprocals of the diagonal entries. In our proposed algorithm, DeepPP, instead of perturbing the full ked-dimensional parameter space, we selectively perturb only the d-dimensional subspace corresponding to the chosen arm. This masking avoids interference from other arms, ensuring more accurate value estimation for the selected action.
39

---

H.2 Additional experiments
We provide additional experiments by varying the norm of the true parameter and the cardinality of the context set [C]. The specific configurations are provided in each figure caption.
To further validate algorithm in neural contextual bandit setting, conduct additional exper- iments using the MNIST [1] and Fashion-MNIST [88] datasets. Fach instance represented as 28 28 grayscale image with label size K 10, naturally forming K-armed classification bandit problem. At each round, the agent receives a context composed of image tensors, where the i-th arm corresponds to the image being placed in the i-th channel slot, and all others set zero. This yields K x 28 x 28 lensor input for each arm. The model f used to estimate the expected reward is shared convolutional neural network that takes the entire K K-channel tensor as input and outputs scalar score for each arm, promoting parameter sharing across arms.
The architecture of the model is follows: two convolutional layers applied with ReLU activation and 2 max pooling after each. The first layer uses 32 filters and the second 64 filters, both with kernel size 3 and stride 1. The resulting 64
7 feature map is flattened and passed through two fully connected layers with hidden size 128, followed by ReL. and a final output scalar. This design enables efficient learning of visual features while maintaining compatibility with the bandit framework through arm-wise shared representation.
10
20
1300
Combattio Regie
800
800-
1000
200
15000
15000
8000
10000
15000
Grredyy
LinUCB
LinT5
LiPHEE
RandLinUCB
GLM-FP (ours)
Figure H.l: Linear Bandit, |C| = 1, (5, 10,20, K 100, S
40
Cumiltiia Begen
1000
300
200
5000
10000
15000
20000
5000
10000 Round
15000
20000
50.0
10000
15000
23000
Round
Round
c-Greedy
TUUC
LinTS
LiPHE
Randi inUCR
GI G-M-FF (eum)
Figure H.2: Linear Bandit. |C| = T, d (10, 20, K 100, S
100
155
Berget
60
5000
10000
15000
20003
5000
13030 Round
15000
20000
3000
10000 Round
15000
20000
Round
Grreedy
LinUCB
LinT5
LinPHE
RandLinUCB
LinfP (ours)
Figure H.3: Linear Bandit with noise N(000..13) |C| = =T T, {10, 40), = -100, S 2.
40

---

10
d 20
d= 40
Combaatio Regget
1001
600
300
200
200
3000
10000 Round
15000
20000
5000
10003 Round
15:00
20000
5000
10000 Roand
15000
3000
G-Gnwdy
LogTS
LogPHE
RandUCBBog
(ours)
Figure H.4: Logistic Bandit. |C] 1, d 15, 10,20. K = 100, S =.
d'
10
20
50
150
302
Comuattve Reggrtt
60
1/14
200
40
100
2000
1000
6000
5000
10000
2000
4000
10.00
8000
10000
2000
4000
6000
5000
10000
Roand
Round
Round
G-Gmedy
LogTS
LogPHE
RandUCCR og
M-FP (nurs)
Figure H.5: Logistic Bandit. |C| 1, d (5, 10, 20, K 100. S
shuttle (K 7,
isolet (K 26, 617)
mushroum (K 22d 116)
Cimiletae Reggee
0000
200
1000
200-
50
10000 Round
20000
200000
found
deep G-eedy
NeuralUCB
DeepFP(ours)
Figure H.6: Neural Bandit. Multi-layer perceptron model with one hidden layer and output layer.
FASHION (K 10.d= 781)
MNIST (A 10,d 784)
10000
Regre
6000
6000
4000
4007
7000
7000
5000
10000 Round
15000
20000
10000
20000
30000
40000
50000
Round
2 Greedy
NeuralUCB
NeuralTS
FTPL
DeepfP (ours)
Figure H.7: Neural Bandit. Experiments MNIST dataset with CNN model.
41


Reviews:
[{"review_id": "TidvM0Y6A5", "reviewer": "Reviewer_QY8k", "summary": "This paper studies the problem of regret minimization for contextual bandits via feature perturbation. Contrarily to usual sampling method that perturb the parameter space, they show that by directly injecting randomness in the feature space, they can recover a $O(d\\sqrt{T})$ bound for generalized linear models, matching the performances of UCB-like algorithms and improving on existing sampling-based algorithms. They provide empirical evidence of their theoretical results as well as empirical evidence that their method can be applied beyond the setting of generalized linear models.", "questions": "- Do you think there is a way to extend this type of method beyond the setting of bandits(For instance for Reinforcement learning, one could perturb the feature of the state action pair to make a decision)\n- Do you think this type of method is limited to greedy action selection or could be suitable to more complex sampling methods such as Information Directed Sampling ?\n- Do you think these type of methods are limited to these generalized linear settings or could be adapted without too much effort to more general parametrized settings (For instance finite action and lipschitzness of the reward function) ?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper is very well written and clear. The setting, assumptions and results are well stated and clearly demonstrated both in the proofs and the empirical demonstration. The setting considered is of great importance in practice. Moreover some care is given to explaining how their proposed methods overcomes the limitation of Thompson Sampling to get the extra $\\sqrt{d}$ factor.\nWhile their method matches the theoretical guarantees of UCB-based methods for linear bandits, they show that their algorithm adapts to the curvature of the space leading to tighter guarantees for Generalized-Linear-Bandits.\nOn the empirical side, one of the main appeal is that their method is directly applicable to very general function classes in a principled and scalable way.\n\nThe main limitation of the theoretical results is that they are limited to the Generalized-Linear-Settings. However, this is a very common setting for this kind of theoretical guarantees and their experimental guarantees extend beyond this setting.\nIt would be extremely interesting to see if the methods and algorithm they propose can be extended beyond the settings of bandits (For  Decision-Making with Side Observations for instance).\n\nI think that this paper is a valuable contribution for our community.", "was_revised": true, "final_justification": "The author have clarified my questions and I maintain my good opinion of the paper.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We appreciate your positive recognition of our work and the constructive comments you have provided regarding the potential applicability of our methodology across various domains. Below, we address each of your comments and questions in detail:\n \n---\n\n**[Q1]** Extending our Feature Perturbation (FP) method to Reinforcement Learning (RL) is a promising and natural direction for future work. Similar to how randomized algorithms such as Thompson Sampling (TS) [A–E] and Perturbed-History Exploration (PHE) [F] have been successfully adapted to RL settings, our FP framework is well-suited for analogous extensions. In particular, we believe that FP can be directly applied in structured settings like Linear MDPs. For model-based algorithms, one could consider perturbing the state-action feature representation $\\varphi(s,a)$ used in computing the transition dynamics.\n\nOne of the core challenges in RL is that randomness introduced by exploration at an earlier state propagates through the trajectory, affecting future Q-value estimates. Therefore, carefully designing perturbation strategies that remain effective over temporally extended decision-making will be interseting future work. Nevertheless, this approach offers a key potential advantage: compared to injecting noise into high-dimensional neural network parameters (e.g., NoisyNets [G]) or maintaining an ensemble of models [A], perturbing the lower-dimensional input feature space can be significantly more efficient and stable in practice.\n\n**[Q2]** Our Feature Perturbation (FP) method is not limited to greedy action selection and is naturally compatible with advanced exploration strategies such as Information Directed Sampling (IDS).\n\nIn our work, FP generates stochastic estimates of each action’s expected reward by perturbing the input features into ${\\tilde{x}_{ti}}$, followed by a simple argmax selection. This is analogous to TS, which selects actions greedily based on perturbed parameters $\\tilde{\\theta}_t$. Both methods induce exploration through randomized estimates.\n\nImportantly, GLM-FP already embeds in a way an information-theoretic principle: the perturbation magnitude is scaled by the elliptical potential, guiding exploration toward actions with higher potential for information gain. This mechanism effectively balances exploration and exploitation.\n\nGiven this structure, a formal information-theoretic analysis of FP—similar to analyses developed for TS [H]—is a compelling direction for future work. FP can be seen as implicitly defining a belief over action values, with IDS offering a more formal decision rule that aligns with the principles already present in our design.\n    \n**[Q3]** Extending our method to finite action spaces is relatively straightforward. On the other hand, generalizing to broader function classes—such as those satisfying only Lipschitz continuity—poses more substantial challenges. In particular, our current regret analysis relies on structural properties of (generalized) linear models, such as the use of the weighted Gram matrix to quantify uncertainty and obtain anti-concentration guarantees. These techniques do not easily extend to general function classes without additional assumptions or new analytical tools.\n\nThat said, our method itself is not inherently limited to the generalized linear setting. A key advantage of Feature Perturbation (FP) is that it operates in the input feature space rather than the model parameter space, making it highly adaptable and model-agnostic. Exploring how FP can be combined with potential-based analyses or adapted to settings with weaker assumptions (e.g., Lipschitz continuity) is a promising direction for future work.\n    \n---\n \n- [A] Randomized Prior Functions for Deep Reinforcement Learning, Osband et al., 2018\n- [B] (More) Efficient Reinforcement Learning via Posterior Sampling, Osband et al., 2013\n- [C] Why is Posterior Sampling Better than Optimism for Reinforcement Learning?, Osband et al., 2017\n- [D] Thompson Sampling for Learning Parameterized Markov Decision Processes, Gopalan & Mannor, 2015\n- [E] Frequentist Regret Bounds for Randomized Least-Squares Value Iteration, Zanette et al., 2023\n- [F] Randomized Exploration for Reinforcement Learning with General Value Function Approximation, Ishfaq et al., 2021\n- [G] Noisy Networks for Exploration, Fortunato et al., 2019 \n- [H] An Information-Theoretic Analysis of Thompson Sampling, Russo & Roy, 2015"}, {"review_id": "XzPclPyZKu", "reviewer": "Reviewer_GCSM", "summary": "1. Authors propose a new randomized algorithm for generalized linear contextual bandits (GLB) based on feature perturbation.\n2. Prior randomized algorithms for linear bandits (LB) and GLB perturb model parameters instead and incur regret that scales as $d^{3/2}$ where $d$ is dimensionality of the feature space. On the other hand, the proposed algorithm's regret scales linearly with $d$.\n3. By using appropriately scaled gram matrices, the authors are also able to remove unwanted dependency on a non-linearity parameter, similar to other recent deterministic GLB algorithms. However, they claim this has not been achieved by randomized algorithms in the literature.\n4. They provide theoretical analysis of their regret guarantee (outlining the assumptions made) and also demonstrate strong empirical performance in multiple settings.", "questions": "All my questions are in the Strengths and Weaknesses part.", "limitations": "Please see strengths and weaknesses", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths of the paper:\n\n1. Introduces a new randomized algo paradigm for contextual bandit problems. Since it is based on feature perturbation it is advantageous to Thompson sampling (TS) in many scenarios where computing posterior distributions could be challenging.\n\n2. Provides optimal regret guarantees that match the state-of-the-art deterministic algos and is a $\\sqrt{d}$ factor better than TS algos.\n\n3. The writing is decent. Intuition in 4.2, proof sketch in 5 and comparison to TS (for LB) in Section 6 are all helpful. Though I think 4.2 and 6 can be made more concise and crisper. Another feedback here would be to make the contributions section more compact and focused mainly on the results. E.g., bullet 3 and 4 can be merged to focus on empirical results.\n\n4. A reasonable amount of empirical validation is provided covering many known baselines. However, some more recent OFU based algorithms focused on GLB seem to be missing (See below).\n\nWeaknesses:\n\n1. While the algorithm is a new randomized algorithm for GLB, essentially (in its arm selection policy) it multiplies the exploration bonus of OFU algorithms (such as LinUCB [1], Logistic-UCB-1, Logistic-UCB-2[13]) with a random scalar (also mentioned in the paper in line 256). This in my opinion makes the algorithm and its analysis pretty much like the OFU counterparts. Therefore, it can be argued while the algorithm is randomized, it's not much different from OFU algorithms. This reduces the novelty aspect of the paper (a little) in my opinion.\n\n2. The main idea is essentially captured in the Linear Bandit problem. To me there does not seem to be any specific new contributions for GLB. Both the confidence bound (wrt scaled gram matrices) and the regret calculation thereof is pretty much what prior works ([13], [3], [A]) have already done to achieve (1/$\\kappa$ independence). Hence, even though this is the first randomized algorithm with regret that is independent of the non-linearity, the paper does not make novel contributions towards that. The authors can please correct me about this, if they think I am mistaken.\n\n3. In the empirical comparisons, I think the authors should also compare to state-of-the-art logistic bandit algorithms such as ada-OFU-EcoLog [A] and subsequent improvements to it ([B], [C] etc). Empirically these seem to be doing really well in the logistic case compared to the OFU and TS algorithms that are among the baselines in this paper. Also, in the experiments section, the authors should explain the instances a little bit.\n\n4. The paper does not discuss the limitations of feature perturbation. For eg., in large action spaces, this would amount to scanning the entire action space before selecting the action to play. The TS algorithm on the other hand can be more efficient by using Linear Optimization oracles? There is literature on deterministic algorithms which explores large action spaces using such oracles [D].\n\n5. In Assumption 1, authors assume both the features and parameters are inside the unit ball. While this is fine for LB, for GLB one would typically assume the parameter space to be contained in an S-ball and the regret should not scale badly with $S$ as $exp(S)$ can be proportional to the non-linearity $1/\\kappa$. I'm assuming that such dependence does not come in the proof. It would be great if the authors can confirm.\n\n6. The self-concordance assumption in Assumption 2 might not be explicitly needed. See [B].\n\n[A] Jointly Efficient and Optimal Algorithms for Logistic Bandits, L Faury, M Abeille, KS Jun, C Calauzènes, AISTATS 2022.\n\n[B] Generalized Linear Bandits with Limited Adaptivity, A Sawarni, N Das, S Barman, G Sinha, NeurIPS 2024.\n\n[C] Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost, Yu-Jie Zhang, Masashi Sugiyama, NeurIPS 2023.\n\n[D] Efficient batched algorithm for contextual linear bandits with large action space via soft elimination, O Hanna, L Yang, C Fragouli, NeurIPS 2023.", "was_revised": true, "final_justification": "The paper proposes an interesting new approach to contextual bandits. From the analysis perspective I see less novelty (the point I was trying to discuss in [W1]) and so I am keeping my score., Having said that the algorithm is definitely interesting and can be useful.  I have followed up with the authors regarding [W4] in my reply to their rebuttal.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We appreciate your positive recognition of our work and the constructive comments you have provided regarding the organization of the paper and its comparison with related prior work. \n\nWe appreciate your suggestion regarding the clarity of our contribution section. We have consolidated the third and fourth bullet points and also plan to revise the ambiguous statements in Sections 4.2 and 6 to make them more concise and precise in conveying their intended messages.\n    \n**[W1]** Our algorithm is not OFU-like in nature; rather, it represents a novel class of randomized exploration based on perturbing the features, rather than the model or rewards. While it may apear to bear a resemblance to OFU in the linear setting (so do many randomized linear bandit algorithms, such as LinTS) due to structural properties of the model, the underlying mechanism and interpretation are fundamentally different.\n\nWe appreciate the opportunity to clarify this point. In the (generalized) linear bandit literature, it is indeed common for both OFU-based algorithms [1, 3, 13, 14, 23-27] and randomized methods such as Thompson Sampling to rely on the elliptical potential [2, 4, 19, 20, 30] to guide exploration. This term helps scale uncertainty and supports efficient learning, but its presence does not imply that the underlying algorithm is OFU in spirit.\n\nOur method introduces a new type of randomness by directly perturbing the input features. In the linear case, this structure induces a behavior that coincides with randomized-scalar variant of OFU, but this is a byproduct of the linear model's geometry—not necessarily our design goal. As we discuss in Section 4.2, once the model departs from linearity (e.g., GLM, neural networks), this resemblance breaks down, and the distinct behavior of feature perturbation becomes more evident.\n\nTherefore, apart from elliptical geometry, our method does not use optimism-based action selection as OFU. Instead, it proposes a randomized feature exploration strategy with its own theoretical justification. We hope this clarification helps position our contribution more accurately within the broader landscape of exploration algorithms.\n\n**[W2]** We are more than happy to elaborate on our key contributions on randomized exploration. \n    \nIn both linear and generalized linear contextual bandits, there has been a long-standing tradeoff between the tight regret guarantees of optimism-based (OFU) algorithms [1, 3, 13, 14, 23-27] and the favorable empirical performance of randomized algorithms [2, 4, 19, 20, 30].\n   \nOur work aims to bridge this longstanding gap. Specifically, we propose **feature perturbation**, a novel form of randomization that is fundamentally distinct from prior approaches based on parameter or reward perturbation. While the analysis of deterministic algorithms in the GLB setting is well established, extending such techniques to randomized algorithms has remained an open challenge. Our contribution lies in adapting and unifying these analytical tools—particularly those involving wighted Gram matrices—to analyze a new class of randomized algorithms.\n\nIn our approach, the regret naturally decomposes into two components:\n\n(1) the parameter estimation error ($\\text{Reg}\\_{\\text{EST}}$), and\n\n(2) the error introduced by randomized perturbations in the feature space ($\\text{Reg}\\_{\\text{FP}}$).\n\nControlling both simultaneously required new analysis to handle the interaction between stochastic perturbations of context vectors and the evolving model estimates. In particular, bounding the $\\text{Reg}_{\\text{FP}}$ term involved applying concentration inequalities to perturbed prediction errors (Appendix F.4, Step 2-2), and ensuring that the weighted Gram matrix could effectively control both sources of uncertainty.\n\nImportantly, **perturbing the input features before the link function with controlled magnitude**, combined with the use of a weighted Gram matrix to achieve $\\kappa_*$-dependent bounds, is novel both in concept and in proof strategy. To the best of our knowledge, no prior randomized algorithm achieves this level of control in the GLB setting.\n\nTo be clear, we emphasize that our contribution lies in designing and establishing new type of exploration, and adapting the analyticial tools to a new randomized exploration strategy. As a result we propose the **first randomized GLB algorithm that matches the regret guarantees of the best deterministic methods—without inverse dependence on the non-linearity parameter $\\kappa$**.\n\n**[W3]** Due to space constraints, we moved some experimental details to the appendix. In response to your Strength 3 comment, we will revise earlier sections to include a clearer and more detailed experimental description.\n    \nIn preparing our experiments, We selected the Algorithm from Lee et al. [25] as our main OFU-style GLB baseline, based on their empirical results showing performance comparable to or better than [A] and [B]. That said, we agree that including direct comparisons strengthens the evaluation.\n\nThe table below presents results on a fixed-arm logistic bandit setting with $S=4$, $K=100$, and $T=3{,}000$, averaged over 20 random instances. We include RS-GLinCB [B] and ada-OFU-EcoLog [A] as OFU-based baselines, and use OFUGLB-e (a much more efficient variant of OFUGLB) for computational feasibility. Our method shows robust performance across settings, and we believe this comparison further supports the empirical validity of our approach.\n\n|Algorithm|Regret($d=10$)|Regret($d=50$)|Time(sec)|\n|-|-|-|-|\n|GLM-TSL|$68.95\\pm3.61$|$361.75\\pm11.33$|$56$|\n|LogPHE|$76.20\\pm2.39$|$289.15\\pm8.71$|$18$|\n|RandUCBLog|$52.40\\pm6.05$|$287.10\\pm12.00$|$36$|\n|RS-GLinCB|$1294.05\\pm26.32$|$900.55\\pm19.15$|$28$|\n|ada-OFU-EcoLog|$506.15\\pm14.86$|$756.90\\pm18.56$|$232$|\n|OFUGLB-e|$264.45\\pm8.94$|$838.30\\pm17.19$|$1462$|\n|GLM-FP (ours)|$\\mathbf{51.85\\pm8.05}$|$\\mathbf{171.10\\pm8.40}$|$28$|\n\n(Time is reported for $d=50$ setting.)\n\n**[W4]** Thank you for pointing out the computational aspect and for the helpful reference [D]. Indeed, [D] presents an practical solution to the large action space problem by introducing an efficient batched algorithm. This approach significantly reduces computational cost by limiting the frequency of policy updates, which is a meaningful contribution from a systems perspective.\n\nHowever, as also noted in [D], this computational efficiency comes with a trade-off. Their algorithm achieves a regret of $\\tilde{O}(d^{3/2}\\sqrt{T})$, which is suboptimal with respect to the dimension $d$. This contrasts with our work, where the primary focus is on achieving the theoretically optimal $\\tilde{O}(d\\sqrt{T})$ regret bound for a randomized algorithm in the standard (non-batched) online setting.\n\nIn addition, regarding the point on linear optimization oracles in the linear setting, if such an oracle is available, it can efficiently solve problems of the form $x^\\top \\theta$. We would like to emphasize that this structure is also compatible with our approach. Since our method perturbs the features and selects actions based on $(x+\\zeta)^\\top\\hat{\\theta}$, it preserves the linear structure and can similarly benefit from the oracle—effectively optimizing over $x$ with a shifted parameter vector. In this sense, the use of a linear optimization oracle is not specific to Thompson Sampling and could likewise enhance the efficiency of our method in relevant settings.\n\nWe appreciate the suggestion and will incorporate this discussion into the final version of the paper.\n\n**[W5]** We confirm that the dependence of our regret bound on $S$ is standard and polynomial, **not exponential**.\n\nWe assume the unit ball boundness purely for notational simplicity, so as to highlight our main contribution—the feature perturbation mechanism and its improvement in dimensionality dependence. However, this assumption can be relaxed without affecting the nature of our results.\n\nIf we instead assume $|\\theta^*|\\leq S$, the confidence width $\\beta_t$ scales with $\\sqrt{S}$. The polynomial dependence on $S$ arises from the ellipsoidal relaxation used to ensure computational efficiency. This dependence then propagates through the analysis, leading to a regret bound that scales with $\\sqrt{S}$—not with $\\exp(S)$.\n\n**[W6]** Thank you — you are right. As noted in [B], self-concordance is a sufficient condition for obtaining tight regret bounds that depend on the problem-specific constant $\\kappa_*$. In fact, the instances considered in the GLB setting already satisfy this property. Our assumption of self-concordance was not essential, but rather introduced for convenience to facilitate the definition of $M_\\mu$. We will revise this part by presenting $M_\\mu$ as a formal definition instead. We appreciate your suggestion, which helps to clarify and strengthen our presentation."}, {"review_id": "xNG6SDX9Az", "reviewer": "Reviewer_yZ7j", "summary": "* This paper describes a new bandit learning algorithm by injecting noise directly into the context vectors. Specifically, at each round, the algorithm adds a random gaussian vector sample to every arm's feature vector.\n* The paper provides a tight regret bound ($\\widetilde{O} (d \\sqrt{T}) $), matching the best-known rates without relying on arm counts or parameter-space sampling.", "questions": "* Can the proposed method and analysis be applied to satisficing bandits and other domains in ML?\n* What happens if the link function is not self-concordant (e.g., heavy-tailed rewards)?", "limitations": "The paper briefly discusses its limitations in Appendix D, admits that the proposed analysis may not work for more general cases like non-GLM. It would be nice to discuss some future works beyond the current package.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "---\nQuality (3): \n* Strength: The proposed method is easy to implement, and new in the specific line of contextual bandit literature. The proposed regret analysis is tight and does not dependent on the number of ars.\n* Weakness: Overall, computing and inverting the weighted Gram matrix may be very costly, which potentially hinders the scalability.\n\n---\n\nClarity (3):\n* Strengths: The paper is well-written and easy to read. The figures are clearly plotted.\n* Weaknesses: The authors may consider improving their notations for better readability. For example, using \\mathbf for random vectors, \\bm for vectors. In addition, adding toy calculation in $d = 2$ may be helpful to illustrate the analysis of the confidence ellipsoid.\n\n---\n\nSignificance (3):\n* Strengths: It matches the best known bound for GLMs and directly extends to last-layer features in deep nets. This is a non-trivial improvement.\n* Weaknesses: It is unclear how the principles/insights in this paper can be applied to other domains or data type (e.g., images, language). It would be nice to add more discussions related to that. Also, it may be helpful to add more discussions on how the proposed method and analysis can shed light on other domains.\n\n---\n\nOriginality (3): \n* Strengths: As the authors mentioned, adding noise to features is relatively new in the domain of contextual bandits.\n* Weaknesses: Feature perturbation is commonly used in other areas like computer vision. Please consider adding more discussion on such related works.", "was_revised": true, "final_justification": "The authors have addressed the questions, and I would maintain my score.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We appreciate your positive recognition of our work, as well as your constructive comments on various aspects of the paper and its potential applicability to other domains. We address your comments point by point below.\n    \n**[W1]** The computational challenge of adapting a weighted Gram matrix in the GLB setting is not unique to our randomized approach. Some methods [14, 2, 27, 30] use an unweighted (vanilla) Gram matrix and leverage the Sherman-Morrison formula for computational efficiency. However, such approaches typically suffer in their regret guarantees, incurring losses in the condition number $\\kappa$ term, and fail to fully capture the curvature of the link function, which can degrade empirical performance.\n\nAny GLB algorithm [3, 13, 19, 24, 25] that relies on a data-dependent weighted Gram matrix—often the Hessian of the log-likelihood—to achieve tighter theoretical guarantees, including state-of-the-art OFU-based methods, faces the same computational burden. Typically, the GLM parameters $\\hat{\\theta}_t$ are estimated via iterative methods like IRLS, during which the weighted Gram matrix is naturally computed. While inverting this matrix entails additional computational cost, this cost represents a fundamental trade-off for obtaining more refined, instance-dependent regret bounds. To address a similar challenge, the (ada-)OFU-ECOLog algorithm [K] utilizes the Sherman–Morrison formula by maintaining a Gram matrix of the form $\\hat{H}\\_t := \\sum\\_{\\tau=1}^{t-1} \\dot{\\mu}(x\\_\\tau^\\top \\hat{\\theta}\\_{\\tau}) x\\_\\tau x\\_\\tau^\\top$, which allows for efficient updates. Following this approach, our algorithm can also be implemented efficiently.\n    \nWe will add a discussion on these computational considerations in the final version, emphasizing that this challenge is common among high-performance GLB algorithms and outlining potential strategies for mitigation.\n    \n**[W2]** Thank you for your thoughtful feedback. I will gladly revise the final version of the papaer as suggested.\n    \n**[W3]** Thank you for the positive feedback on our work and for recognizing it as a non-trivial contribution, and also appreciate the insightful suggestion to discuss the broader applicability of our method, which we agree will strengthen the final version.\n\nThe central idea of our approach—exploring in the feature representation space instead of the high-dimensional parameter space—is model-agnostic and naturally extends to a wide range of modern machine learning settings, particularly in deep learning.\n\n**Applications to Image and Language Data**\nFor high-dimensional inputs like images or text, a common pipeline uses powerful pre-trained feature extractors (e.g., ResNet, ViT [A, B] for images, or BERT [C] for language) to transform raw inputs into compact embeddings. Our FP method can be applied directly to these embedding vectors.\nIn image-based tasks, instead of perturbing raw pixels, we inject controlled noise into the feature vectors prior to decision-making layers, enabling semantically meaningful exploration. In NLP tasks, applying FP to BERT-based sentence embeddings enables exploration over semantically similar but syntactically distinct contexts. As a natural extension, developing domain-adapted algorithms with provable guarantees would be a compelling direction for future research.\n\n**Broader Insight for Deep Learning Exploration**\nOur work contributes a simple yet effective mechanism for exploration that avoids the computational burden of modeling uncertainty over millions of parameters [D, E]. Instead, we propose a shift in perspective: rather than asking “How uncertain are my model’s parameters?”, we ask “How sensitive is the model to small changes in its input context?” \nThis input-space exploration offers a practical proxy for model uncertainty and provides a scalable principle that can be broadly useful in deep reinforcement learning and other settings requiring efficient exploration.\n\nWe will incorporate this discussion into the final version to better highlight the generality and conceptual contribution of our work.\n    \n**[W4]** Our work fundamentally reinterprets the role of feature perturbation: rather than using it for robustness or regularization during training, as is common in fields like computer vision, we employ it as a principled mechanism for exploration in online decision-making. In traditional applications, feature perturbation is used during training to help models generalize better by making predictions invariant to input noise—this includes techniques such as data augmentation [F,G] and adversarial training [H].\n\nIn contrast, our method introduces noise at inference time, not to regularize the model but to induce structured stochasticity in action selection. This allows the learning agent to explore its environment by probing the model’s sensitivity to perturbations in the input space, rather than relying on uncertainty in the parameter space. The goal is not to build a more robust static model, but to enable efficient exploration in an adaptive, sequential learning setting, such as contextual bandits.\n\nWe appreciate the reviewer’s suggestion and will add a discussion in the related work section to clarify this distinction and better situate our contribution within the broader literature.\n    \n**[Q1]** For satisficing bandits, our exploration mechanism is directly applicable. The only change would be to replace the reward-maximizing argmax policy with a rule that terminates once an arm's confidence bound reliably exceeds the satisficing threshold.\n\nFor other domains like computer vision and language, FP can be applied to the feature embeddings generated by large models. This offers a key advantage over other methods: it provides a practical and scalable exploration strategy that sidesteps the often-intractable problem of exploring in a massive parameter space.\n    \n**[Q2]** Self-concordance is a sufficient condition for obtaining tight regret bounds that depend on the problem-specific constant $\\kappa_*$. It characterizes the geometry of the link function $\\mu$, which is naturally satisfied by the instances considered in the GLB setting. Many recent GLB algorithms [3, 13, 24, 25] focus on such self-concordant link functions, including linear, logistic, and Poisson models. Our assumption of self-concordance was not essential but introduced mainly for convenience, to facilitate the definition of $M_\\mu$ used in the proof analysis.\n\nIn our analysis, the self-concordance assumption plays a critical role. Earlier works [14, 2, 27, 30, 20] often linearized the problem, which incurred additional regret reverse-proportional on the condition number $\\kappa$. In contrast, we leverage self-concordance to tightly control higher-order terms in the Taylor expansion of the loss, enabling improved regret bounds with favorable $\\kappa$-dependence while simultaneously managing the stochastic perturbations of the feature vector. For example, our analysis uses the Mean Value Theorem to reduce second-order error terms to first-order ones via $M_\\mu$. Combined with the Lipschitz continuity of $\\mathcal{L}_\\mu$, this permits the application of elliptical potential lemmas and results in sharper confidence bounds. Without self-concordance, these tools are not applicable, making it difficult to achieve improved regret dependence on $\\kappa$.\n\nRegarding heavy-tailed rewards, this refers to the data distribution, which directly contradicts our assumption of $R$-subgaussian (light-tailed) noise. Handling heavy-tailed rewards would require a fundamentally different theoretical framework, such as those developed in the robust bandit literature [I, J], which is beyond the scope of this paper. Nevertheless, we believe that analyses addressing heavy-tailed settings could be naturally combined with our Feature Perturbation approach.\n    \n**[L]** Developing theoretically grounded algorithms beyond GLMs—such as those accommodating only Lipschitz-continuous link functions—is an important direction for future work. In parallel, extending the feature perturbation framework to domains such as vision and language, where more structured or semantic noise may better capture domain-specific inductive biases, could further enhance exploration. We appreciate the reviewer’s suggestion and will incorporate a broader discussion of these potential extensions into the final version.\n    \n---\n    \n- [A] Deep Residual Learning for Image Recognition, He et al., 2016\n- [B] An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale, Dosovitskiy et al., 2020\n- [C] BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, Devlin et al., 2019\n- [D] Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning, Gal & Ghahramani, 2016\n- [E] Deep Exploration via Bootstrapped DQN, Osband et al., 2016\n- [F] A survey on Image Data Augmentation for Deep Learning, Shorten & Khoshgoftaar, 2019\n- [G] The Effectiveness of Data Augmentation in Image Classification using Deep Learning, Perez & Wang, 2017\n- [H] Explaining and Harnessing Adversarial Examples, Goodfellow et al., 2015\n- [I] Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards, Xue et al., 2023\n- [J] Bandits with heavy tail, Bubeck et al., 2012 \n- [K] Jointly Efficient and Optimal Algorithms for Logistic Bandits, Faury et al., 2022"}, {"review_id": "WMXDgG8fbf", "reviewer": "Reviewer_NnNz", "summary": "This paper proposes feature perturbation, a novel and simple technique that injects noise in the feature space. Contrary to known randomised bandit algorithms, this new algorithm achieves the worst case regret bound for generalised linear bandits. The paper also tries to provide the intuition behind the superior regret of the proposed algorithm compared to TS-like methods. The proposed approach is straightforward to apply, even for deep neural networks, and shows strong empirical performance compared to existing methods.", "questions": "In the linear case, the algorithms of TS and FP are equivalent with an appropriate choice of noise. \n\nIn the discussion, the authors state that \" To achieve this (TS regret), a union bound over d coordinates is typically applied, introducing an additional $\\sqrt{d}$ factor into the regret analysis.\" \n\n- What do the authors mean here? Is $\\sqrt{d}$ an artefact of the proof?\n- In the linear case, what are the main algorithmic differences between TS and FP? If the algorithm is the same, why the regret is different?\n\nThese points should be clarified more in the paper, and the emphasis should be on **why we are getting an improved regret**. \n\nIn addition, a relatively recent paper [1] discusses conditions where TS can achieve a regret with optimal dependence on $d$. A discussion of these results and comparison with the obtained guarantees for FP should be included.\n\nClarifying these points will increase my confidence.\n\n[1] When and why randomised exploration works (in linear bandits). Marc Abeille, David Janz, Ciara Pike-Burke", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- The paper is well written and accessible.\n- The proposed method closes a known gap between OFU based methods and TS-like method for GLMs.\n- The method is simple and even applies to overparametrised models.\n- The method shows good empirical performance.\n\n\n**Weaknesses:**\n- In the linear setting, feature perturbation is formally equivalent to TS with a well chosen noise. The paper tries to give intuition why FP has a lower regret than TS in this case but this needs to be clarified more. See questions please.", "was_revised": true, "final_justification": "This is a great paper. It is well-written and solves an interesting problem using a simple yet clever idea. The authors' rebuttal successfully clarified some points and added a discussion of Abeille et al. [1]. I support its acceptance.", "rebuttal": "Thank you for your thoughtful feedback. We appreciate the opportunity to elaborate on the differences between Feature Perturbation (FP) and Thompson Sampling (TS), particularly in the linear bandit setting, and to clarify the source of the improved regret bound.\n\nWe appreciate your insightful question, which gives us a valuable opportunity to clarify a nuanced point. While the marginal distribution of the score for any individual arm is the same in both TS and FP, the algorithms are not equivalent. The key difference lies in the joint distribution across all arms in each step $t$, which is determined by how the shared randomness couples their scores. This coupling structure is what fundamentally drives the improvement in regret, as we discuss in Section 6 of the paper and further below.\n    \nAlthough both TS and FP generate score functions that follow the same marginal distribution, $\\tilde{f}\\_t(x\\_i)\\sim\\mathcal{N}(x\\_{ti}^\\top\\hat{\\theta}\\_t,c\\_t^2\\|x\\_{ti}\\|\\_{V\\_t^{-1}}^2)$, the mechanisms behind this sampling differ. In TS, the score is obtained via $\\tilde{f}\\_t(x\\_i)=x\\_{ti}^\\top\\tilde{\\theta}\\_t=x\\_{ti}^\\top\\hat{\\theta}\\_t+c\\_t\\cdot x\\_{ti}^\\top V\\_t^{-1/2}\\zeta\\_t$, while in FP, it is computed as $\\tilde{f}\\_t(x\\_i)=\\tilde{x}\\_{ti}^\\top\\hat{\\theta}\\_t=x\\_{ti}^\\top\\hat{\\theta}\\_t+c\\_t\\cdot z\\_t\\|x\\_{ti}\\|\\_{V\\_t^{-1}}$. Although both methods result in the same marginal distribution for each arm, the coupling structure induced by shared randomness (i.e., a single $\\zeta_t$ used across all arms) leads to different joint distributions over scores ${\\tilde{f}_t(x_i)}$, resulting in algorithmic differences that impact regret.\n\n**The Source of the $\\sqrt{d}$ Factor: Algorithmic and Analytical Differences**\nThe difference in regret stems from how each algorithm's structure affects the concentration bounds required by the analysis. The exploration bonus for each algorithm can be expressed as:\n\\begin{align}\n(\\text{TS})\\quad\\quad \\|x\\_{ti}^\\top(\\tilde{\\theta}\\_t-\\hat{\\theta}\\_t)\\|\\_2&\\leq\n    \\|x\\_{ti}^\\top(\\beta\\_t(\\delta')\\cdot V\\_t^{-1/2}\\zeta\\_t)\\|\\leq\\beta\\_t(\\delta')\\cdot\\|x\\_{ti}\\|\\_{V\\_t^{-1}}\\|V\\_t^{-1/2}\\zeta\\_t\\|\\_{V\\_t}\\\\\\\\\n    &=\\beta\\_t(\\delta')\\cdot\\|x\\_{ti}\\|\\_{V\\_t^{-1}}\\cdot\\|\\zeta\\_t\\|\\_2,\\\\\\\\\n(\\text{FP})\\quad \\|(\\tilde{x}\\_{ti}-x\\_{ti})^\\top\\hat{\\theta}\\_t\\|\\_2&\\leq\\left\\|\\beta\\_t(\\delta')\\cdot\\|x\\_{ti}\\|\\_{V\\_t^{-1}}\\frac{\\hat{\\theta}\\_t^\\top\\zeta\\_t}{\\|\\hat{\\theta}\\_t\\|\\_2}\\right\\|\\\\\\\\\n    &\\leq\\beta\\_t(\\delta')\\cdot\\|x\\_{ti}\\|\\_{V\\_t^{-1}}\\cdot(u^\\top\\zeta\\_t),\n\\end{align}\nwhere $\\zeta_t \\sim \\mathcal{N}(0, I_d)$, $\\beta_t(\\delta') = \\mathcal{O}(\\sqrt{d})$, and $u = \\hat{\\theta}_t / \\|\\hat{\\theta}_t\\|_2$. The key difference is that the bonus for TS scales with the norm of a $d$-dimensional random vector ($\\|\\zeta_t\\|_2$), while the bonus for FP scales with a 1-dimensional random projection ($|u^\\top\\zeta_t|$).\n    \nTo guarantee a high-probability bound for the TS bonus, the analysis must control the $\\|\\zeta_t\\|_2$ term with high probability $1-\\delta'$, typically requiring a union bound across $d$ coordinates:\n\\begin{equation}\n\\mathbb{P}\\left(\\|\\zeta_t\\|_2\\leq\\sqrt{2d\\log\\frac{2d}{\\delta'}}\\right)\n    \\geq\\mathbb{P}\\left(\\forall1\\leq i\\leq d,~|(\\zeta_t)_i|\\leq\\sqrt{2\\log\\frac{2d}{\\delta'}}\\right)\n    \\geq 1-d\\mathbb{P}\\left(|(\\zeta_t)_i|\\geq\\sqrt{2\\log\\frac{2d}{\\delta'}}\\right)\n\\end{equation}\n(With $\\mathbb{P}((\\zeta_t)_i\\geq\\alpha)\\leq2 e^{-\\alpha^2/2}=\\delta'/d$ by the choice of $\\alpha=\\sqrt{2\\log(2d/\\delta')}$.)\n    \nAs a result, this introduces an **extra $\\sqrt{d}$ factor** in the effective bonus beyond the $\\beta_t(\\delta') = \\mathcal{O}(\\sqrt{d})$ scaling. As discussed by Hamidi and Bayati [16] (and cited in our paper), this additional $\\sqrt{d}$ is inherent in the worst-case analysis of standard TS. In contrast, FP only requires controlling a 1-dimensional Gaussian random variable ($u^\\top \\zeta_t$), avoiding the need for such a union bound. This tighter control leads to a smaller bonus term and ultimately a tighter regret bound. Thus, despite having the same marginal distributions for individual arms, the different coupling structures of TS and FP result in different high-probability regret guarantees. \n\n**Comparison with Abeille et al. [1]**\nThank you for pointing us to this relevant work. We have reviewed the paper by Abeille et al. [1]. Their work shows that the standard TS algorithm can indeed achieve the optimal $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ regret, but this requires the action set to satisfy strong geometric conditions (e.g., being an \"absorbing set,\" strongly convex, and smooth).\n\nThe authors of [1] rightly note that their conditions do not hold for the worst-case instances identified by Hamidi and Bayati [16]. While their assumptions may be met in certain synthetic settings (e.g., $\\ell_p$ balls), they may not hold for more general, arbitrary action sets encountered in practice. \n    \nOur contribution is complementary. We show that the FP algorithm achieves the same optimal $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ regret under much milder assumptions: we require only that the action set is bounded, a standard and broadly applicable condition used in many TS papers (e.g., [2, 4]). Thus, our theoretical guarantees apply to a wider class of problems without relying on specific geometric structure.\n    \nThank you again for highlighting this recent result. We will happily include a discussion of this comparison in the final version of our paper."}, {"review_id": "vHMYS3YWNq", "reviewer": "Reviewer_yKuD", "summary": "The paper studies a contextual bandit algorithm adapted to Gaussian Linear Models (i.e. the density of the reward given context $x$ and parameter of interest $\\theta^\\star$ has a density exp$(r x^T \\theta^\\star - g(x^T \\theta*^\\star) + h(r))$ and a mean being the derivative $\\mu$ of the link function $g$). The novelty of the proposed method is to add randomness in the features instead of adding it to the reward. The contribution of the paper is to achieve the same regret bound as optimism-based algorithms ($O(d\\sqrt{T}), d$ being the dimension of the context space) while relying on a randomized-like approach and similar practical performance (better in practice). Hence, the paper claims to bridge the gap between theoretical and practical performances of these two kinds of approaches, \"By shifting the focus of exploration from parameter space to feature space\", line 33.", "questions": "The authors suggest that it can happen to work with overparametrized bandits, is it actually the case in practice?\n\nIt might be a stupid question but since $\\mu$ is Lipschitz, is there a form of equivalence (or maybe inequalities) between randomly perturbing $x_{ti}$ and randomly perturbing the reward $\\mu(x_{ti}\\hat{\\theta}_t)$?", "limitations": "It is more a suggestion but I have the feeling that section 4.2 is very important to understand the method (and interesting in itself): I think that it could be even more detailed.\n\nPart 6 of the main text is interesting (and almost represents the most important part of the paper to me) but I believe that it could be made clearer (for instance, elements from B.2. could be added there).", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I would summarize the strengths of the paper as follows:\n- the paper is clear and goes straight to the point, which is pleasant.\n- many experimental setups are provided\n\nHowever, I believe that the following point represent weaknesses of the paper:\n- the idea of randomizing the features is nice but it does not outperform the state-of-the-art guarantees for contextual bandits and does not  induce major technical challenges, see below.\n- the theoretical work in the proofs is mostly a combination of pieces of proofs that already exist, typically, almost all the elements in appendix \"G - Proof supplement and Lemmas\" come from existing results. Once they are given, combining them in the proof of Theorem 1 does not appear extremely challenging.\n- all together, the contributions of the paper seem quite incremental to me.", "was_revised": true, "final_justification": "The detailed authors` answers to my review raised my concerns and convinced me about the paper. This is why I increased my rating accordingly and I support its acceptance.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback, particularly your recognition of the paper's clarity and the breadth of our experimental setups. We appreciate the opportunity to clarify the significance and novelty of our contributions. \n    \n**[W1-W3]** We would like to emphasize that successfully adapting existing theoretical tools has long been central to many advances in the (generalized) linear bandit literature [2, 3, 13, 14, 20, 24, 25, 27, 30]. For example, Thompson Sampling [4] has inspired reinterpretations (e.g., Abeille et al. [2]) and practical variants such as PHE [19] and RandUCB [30]. While these methods share core analytical components, they were recognized not just for introducing entirely new analytical techniqes, but for effectively adapting established tools to either analyze novel exploration strategies, achieve new bounds, or provide new interpretation.\n\nOur key contribution lies in introducing a fundamentally different form of randomization—feature perturbation—which departs from prior approaches based on parameter or reward perturbation. This new source of randomness enables tighter regret analysis in the GLM bandit setting. Adapting technical tools to control the stochastic dependencies induced by feature perturbations and integrating them with estimation error terms in a weighted Gram matrix framework are highly nontrivial. We sincerely believe that they should not be treated as just a simple combination.\n\nTo contextualize, Table 1 summarizes representative GLM bandit algorithms. Italicized methods are randomized but exhibit suboptimal regret rates or fail to capture problem-dependent constants such as $\\kappa_*$. In contrast, all OFU-based methods rely on a shared analytical backbone modified for each algorithm’s specifics.\n\n|**Algorithm**|**Regret Upper Bound**|**Note**|\n|-|-|-|\n|GLM-UCB [14]|$\\tilde{\\mathcal{O}}(d\\sqrt{T}/\\kappa)$||\n|*LinTS [2]*|$\\tilde{\\mathcal{O}}(d^{3/2}\\sqrt{T}/\\kappa)$||\n|SupCB-GLM [27]|$\\tilde{\\mathcal{O}}(\\sqrt{dT\\log K}/\\kappa)$|$\\sqrt{d\\log K}$ dependency under finite arms|\n|Logistic-UCB-2 [13]|$\\tilde{\\mathcal{O}}(d\\sqrt{T}+d^2/\\kappa)$||\n|*GLM-TSL, GLM-FPL [20]*|$\\tilde{\\mathcal{O}}(d^{3/2}\\sqrt{T}/\\kappa)$||\n|*RandUCB [30]*|$\\tilde{\\mathcal{O}}(d\\sqrt{T}/\\kappa)$||\n|SupLogistic [a]|$\\tilde{\\mathcal{O}}(\\sqrt{dT\\log K}+d^3/\\kappa^2)$|$\\sqrt{d\\log K}$ dependency under finite arms|\n|OFULog, OFULog-r [3]|$\\tilde{\\mathcal{O}}(d\\sqrt{\\kappa_\\star T}+d^2/\\kappa)$|Mitigates $\\kappa$-dependence by constructing tighter confidence intervals|\n|ada-OFU-ECOLog [b]|$\\tilde{\\mathcal{O}}(d\\sqrt{\\kappa_* T}+d^2/\\kappa)$|Improves computational efficiency|\n|OFULog+ [24]|$\\tilde{\\mathcal{O}}(d\\sqrt{\\kappa_* T}+d^2/\\kappa)$|Reduces the dependence on $S$ in the confidence bound|\n|OFUGLB [25]|$\\tilde{\\mathcal{O}}(d\\sqrt{\\kappa_* T}+d^2/\\kappa)$|Extends the MNL setting in [c] to general GLMs|\n|**GLM-FP (Ours)**|$\\mathbf{\\tilde{\\mathcal{O}}(d\\sqrt{\\kappa_*T}+d^2/\\kappa)}$|**First randomized algorithm to prove $O(d)$ dependence in the leading term benefiting from $\\kappa_*$**|\n\n- [a] Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits, Jun et al., 2021\n- [b] Jointly Efficient and Optimal Algorithms for Logistic Bandits, Faury et al., 2022\n\nOur algorithm, GLM-FP, is the first randomized method in the GLM setting to provably achieve the optimal $\\tilde{\\mathcal{O}}(d\\sqrt{T})$ regret while adapting to the problem-dependent constant $\\kappa_*$. Existing randomized methods either suffer from worse dimension dependence (e.g., GLM-TSL) or do not capture $\\kappa_*$ (e.g., RandUCB). This closes a long-standing gap between the empirical success of randomized approaches and the strong theoretical guarantees previously exclusive to OFU-based algorithms. The key enabler is our novel randomization via feature perturbation instead of parameter or reward perturbation, allowing sharper analysis and tighter regret bounds.\n\nOur analysis confronts the unique challenges posed by feature perturbations, which induce different stochastic dependencies compared to parameter sampling methods like TS. We develop new techniques to control correlations across arms and to ensure a valid regret decomposition separating estimation error ($Reg_{EST}$) and feature perturbation effects ($Reg_{FP}$). Perturbing the input features before the link function with controlled magnitude, along with the use of a weighted Gram matrix to achieve $\\kappa_*$-dependent bounds, is novel both in concept and proof strategy.\n\nPractically, our approach offers flexibility and scalability advantages. TS-based methods often struggle in high-dimensional parameter regimes, such as neural function classes where parameter dimension $p$ far exceeds feature dimension $d$. Our feature perturbation directly randomizes the low-dimensional input, making it well-suited for such settings. This is supported by empirical results where GLM-FP consistently outperforms OFU-, TS-, and PHE-based baselines across various scenarios.\n\nIn summary, our work builds on existing foundations (and so do many seminal works in this field!) but makes a distinct and substantial contribution by introducing a novel randomized exploration scheme with the first optimal regret guarantee for randomized GLM bandits. We believe this represents a meaningful step beyond prior work, both in theory and practice.\n    \n**[Q1]** Our method is effective for overparameterized bandits in practice, both conceptually and empirically.\n\nConceptually, our Feature Perturbation (FP) approach avoids the key challenge in overparameterized settings. Existing methods that perturb the parameter space often become computationally infeasible as model size grows. Even practical baselines like NeuralTS add noise only to the final rewards rather than perturbing the model itself, effectively functioning as PHE. In contrast, our FP method drives exploration directly in the low-dimensional feature space, making it inherently scalable and stable regardless of model size.\n\nEmpirically, this advantage is supported by strong experimental results. In Section 7.2, we demonstrate the practical effectiveness of our approach using neural networks. As shown in Figure 3 (bottom) and Figures 9–10 in the appendix, our DeepFP algorithm consistently outperforms standard neural bandit baselines on several real-world benchmark datasets.\n\nTo further validate this, we conducted additional experiments on the MNIST dataset ($d=784$) using four neural network architectures of varying size and type. The models (with $p$: number of parameters) are:\n\n- MLP-100 (**M1**): A two-layer MLP with hidden dimension 100 ($p=88{,}701$)\n- CNN-Small (**M2**): A small CNN with two convolutional layers (32 and 64 filters) and a two-layer fully connected head, as described in Appendix H.2 with learning rate 0.001 ($p=423{,}073$)\n- CNN-Large (**M3**): A deeper CNN with four convolutional layers (64 to 256 filters) and a three-layer fully connected head with dropout ($p=7{,}455{,}169$)\n\nThe results from 10 independent runs are summarized below. Here, [F] refers to the Fashion-MNIST dataset, and \"Time\" denotes the runtime for the M3[F] experiment.\n|Algorithm|M1|M2|M3|M2[F]|M3[F]|Time(sec)|\n|-|-|-|-|-|-|-|\n|$\\varepsilon$-greedy|$3040\\pm21.8$|$\\mathbf{2271\\pm49.7}$|$1627\\pm14.2$|$6133\\pm30.9$|$2947\\pm14.4$|$1044$|\n|DeepFPL|$2432\\pm30.4$|$7174\\pm716.6$|$1601\\pm65.8$|$8150\\pm1559.1$|$2643\\pm36.3$|$965$|\n|NeuralUCB|$3047\\pm210.6$|$3100\\pm78.3$|$8358\\pm246.2$|$8820\\pm670.5$|$4758\\pm132.9$|$4446$|\n|NeuralTS|$3335\\pm53.3$|$6086\\pm376.1$|$8923\\pm60.7$|$13205\\pm1107.4$|$3895\\pm73.3$|$4387$|\n|DeepFP(ours)|$\\mathbf{2426\\pm10.6}$|$3713\\pm565.2$|$\\mathbf{1513\\pm38.1}$|$\\mathbf{5578\\pm33.3}$|$\\mathbf{2634\\pm24.8}$|$981$|\n\nThese results confirm the effectiveness of our algorithm in highly overparameterized regimes ($d \\ll p$), where feature-space exploration remains both scalable and robust across model sizes.\n    \n**[Q2]** In short, the answer is **generally no** — perturbing the input $x_{ti}$ and perturbing the reward $\\mu(x\\_{ti}^\\top\\hat{\\theta}\\_t)$ are not equivalent, even if $\\mu$ is Lipschitz. While the Lipschitz continuity of $\\mu$ does imply the inequality $|\\mu(x^\\top\\hat{\\theta})-\\mu((x+\\zeta)^\\top\\hat{\\theta})|\\leq\\mathcal{L}\\_\\mu|\\zeta^\\top\\hat{\\theta}|$, this only gives an upper bound; it does not imply equivalence between the two types of perturbations. In fact, the two approaches introduce fundamentally different exploration behaviors and uncertainty structures.\n\nwe note that relying on this inequality effectively linearizes the GLM model, reducing it to an approximate linear bandit problem. As discussed in our paper, such linearization sacrifices the curvature of $\\mu$, and leads to weaker regret bounds—specifically, a $1/\\kappa$ dependence in the leading term, which our algorithm avoids. Indeed, existing randomized methods such as RandUCB and PHE fall into this category: they perturb rewards directly or equivalently rely on a linearized analysis. In contrast, our algorithm perturbs the input features, and our analysis preserves the curvature of the link function, which is critical for achieving the tighter, instance-dependent $\\kappa_*$ regret bound.\n\nAs a result, perturbing $x$ before applying $\\mu$ (i.e., $\\mu((x+\\zeta)^\\top\\hat{\\theta})$) is not equivalent to applying $\\mu$ first and then perturbing its output. The resulting exploration behavior is fundamentally different, both in distributional structure and in the way uncertainty is introduced. We discuss this nuance in Appendix C, which helps explain our algorithm’s strong guarantees and performance and this difference underpins the novelty and strength of our approach.\n    \n**[L]** We will do our best to make appropriate modification in presentation to improve our presentation in the revision."}]

Author rebuttal:

Meta-review: This paper on contextual bandits takes an unusual and interesting approach to solving the standard problem, by adding noise in the context instead of the underlying parameter.

This is interesting and original, and all reviewers were very positive about it. 

I am happy to recommend acceptance at NeurIPS 2025 !
Decision: Accept (spotlight)