Exploration via Feature Perturbation in Contextual Bandits

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.

[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.

Our 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.

To 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.

• [a] Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits, Jun et al., 2021
• [b] Jointly Efficient and Optimal Algorithms for Logistic Bandits, Faury et al., 2022

Our 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.

Our 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.

Practically, 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.

In 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.

[Q1] Our method is effective for overparameterized bandits in practice, both conceptually and empirically.

Conceptually, 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.

Empirically, 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.

To 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:

• MLP-100 (M1): A two-layer MLP with hidden dimension 100 ($p=88{,}701$)
• 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$)
• 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$)

The 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.

These 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.

[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.

we 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.

As 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.

[L] We will do our best to make appropriate modification in presentation to improve our presentation in the revision.

We sincerely appreciate your prompt reply and the time you invested in reviewing our detailed rebuttal. We are delighted that our theoretical contributions were acknowledged, and we thank you for updating your score. We will make the necessary revisions to further enhance the completeness of the paper.

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.

We 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.

Although 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.

The Source of the $\sqrt{d}$ Factor: Algorithmic and Analytical Differences The 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:

$

(\text{TS})\quad\quad |x_{ti}^\top(\tilde{\theta}_t-\hat{\theta}_t)|_2&\leq |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}\\ &=\beta_t(\delta')\cdot|x_{ti}|_{V_t^{-1}}\cdot|\zeta_t|_2,\\ (\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|\\ &\leq\beta_t(\delta')\cdot|x_{ti}|_{V_t^{-1}}\cdot(u^\top\zeta_t),

$

where $\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|$).

To 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:

$

\mathbb{P}\left(|\zeta_t|_2\leq\sqrt{2d\log\frac{2d}{\delta'}}\right) \geq\mathbb{P}\left(\forall1\leq i\leq d,~|(\zeta_t)_i|\leq\sqrt{2\log\frac{2d}{\delta'}}\right) \geq 1-d\mathbb{P}\left(|(\zeta_t)_i|\geq\sqrt{2\log\frac{2d}{\delta'}}\right)

$

(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')}$.)

As 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.

Comparison with Abeille et al. [1] Thank 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).

The 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.

Our 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.

Thank you again for highlighting this recent result. We will happily include a discussion of this comparison in the final version of our paper.

Thank you for your detailed answer. I'm expecting the revised paper to:

• Detail the source of the $\sqrt{d}$ factor in the main body, and to take the time to explain the differences like in the answer provided.
• Include the discussion of Abeille et al. [1].

Great work. It is a really good paper overall and I'm supporting its acceptance.

For neural networks, similar ideas were explored in practice, only perturbing the latent representation in neural networks instead of the raw features to define policies. For example see:

[2] Sakhi et al. Fast Slate Policy Optimization: Going Beyond Plackett-Luce. TMLR

This can be relevant to motivate the core analysis.

Thank you very much for your encouraging and constructive comments. We appreciate your suggestions and confirm that we will clarify Section 6 and add a discussion of [1], as recommended. Thank you also for the pointer to [2]—it helps contextualize our theoretical results. We are grateful for your support and look forward to incorporating these improvements in the final version.

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:

[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.

One 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.

[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).

In 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.

Importantly, 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.

Given 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.

[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.

That 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.

• [A] Randomized Prior Functions for Deep Reinforcement Learning, Osband et al., 2018
• [B] (More) Efficient Reinforcement Learning via Posterior Sampling, Osband et al., 2013
• [C] Why is Posterior Sampling Better than Optimism for Reinforcement Learning?, Osband et al., 2017
• [D] Thompson Sampling for Learning Parameterized Markov Decision Processes, Gopalan & Mannor, 2015
• [E] Frequentist Regret Bounds for Randomized Least-Squares Value Iteration, Zanette et al., 2023
• [F] Randomized Exploration for Reinforcement Learning with General Value Function Approximation, Ishfaq et al., 2021
• [G] Noisy Networks for Exploration, Fortunato et al., 2019
• [H] An Information-Theoretic Analysis of Thompson Sampling, Russo & Roy, 2015

Thank you for highlighting this important point. While our method doesn’t explicitly aim to sample informative suboptimal actions, we see this as a promising direction to explore in future work. We’re also grateful for your positive evaluation and for your support in advancing this line of research.

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.

We 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.

[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.

We 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.

Our 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.

Therefore, 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.

[W2] We are more than happy to elaborate on our key contributions on randomized exploration.

In 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].

Our 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.

In our approach, the regret naturally decomposes into two components:

(1) the parameter estimation error ($\text{Reg}\_{\text{EST}}$), and

(2) the error introduced by randomized perturbations in the feature space ($\text{Reg}\_{\text{FP}}$).

Controlling 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.

Importantly, 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.

To 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$.

[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.

In 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.

The 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.

(Time is reported for $d=50$ setting.)

[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.

However, 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.

In 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.

We appreciate the suggestion and will incorporate this discussion into the final version of the paper.

[W5] We confirm that the dependence of our regret bound on $S$ is standard and polynomial, not exponential.

We 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.

If 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)$.

[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.

We sincerely appreciate your time and patience in reviewing our detailed response. We’re glad to hear that most of your concerns have been addressed, and we thank you for your thoughtful follow-up. As you pointed out, the bonus is arm-dependent, and as we detail in Section 6, Eq. (FP) of our paper, the selection rule for the linear variant is equivalent to solving: $\arg\max\_{x\_{ti}} (x\_{ti}^{\top}\hat{\theta}\_t + c\_t \cdot z\_t ||x\_{ti}||\_{V\_t^{-1}})$.

Because the bonus term $||x\_{ti}||\_{V\_t^{-1}}$ is specific to each arm, a naive implementation would indeed require iterating through the entire action set. a naive implementation would require iterating over the entire action set. However, this issue is not unique to our method—it arises in many linear bandit algorithms, including [1, 2, 19]. While our main contribution lies in improving statistical efficiency—achieving the optimal $\mathcal{O}(d\sqrt{T})$ regret and closing a long-standing theoretical gap—we acknowledge that we did not sufficiently discuss the per-round computational trade-offs.

We appreciate your feedback and will address this point more thoroughly in the final version of the paper, including a more explicit connection to related work. Thank you again for your valuable input, which will significantly strengthen the paper.

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.

[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.

Any 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.

We 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.

[W2] Thank you for your thoughtful feedback. I will gladly revise the final version of the papaer as suggested.

[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.

The 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.

Applications to Image and Language Data For 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. In 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.

Broader Insight for Deep Learning Exploration Our 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?” This 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.

We will incorporate this discussion into the final version to better highlight the generality and conceptual contribution of our work.

[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].

In 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.

We 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.

[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.

For 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.

[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.

In 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$.

Regarding 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.

[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.

• [A] Deep Residual Learning for Image Recognition, He et al., 2016
• [B] An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale, Dosovitskiy et al., 2020
• [C] BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, Devlin et al., 2019
• [D] Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning, Gal & Ghahramani, 2016
• [E] Deep Exploration via Bootstrapped DQN, Osband et al., 2016
• [F] A survey on Image Data Augmentation for Deep Learning, Shorten & Khoshgoftaar, 2019
• [G] The Effectiveness of Data Augmentation in Image Classification using Deep Learning, Perez & Wang, 2017
• [H] Explaining and Harnessing Adversarial Examples, Goodfellow et al., 2015
• [I] Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards, Xue et al., 2023
• [J] Bandits with heavy tail, Bubeck et al., 2012
• [K] Jointly Efficient and Optimal Algorithms for Logistic Bandits, Faury et al., 2022