Generalized Kernelized Bandits: Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds

We thank the Reviewer for the feedback and for having recognized that the paper is well-written and teachnically sound. Below we address the Reviewer's concerns.

Weaknesses

Although we believe that the core contributions of the paper are mainly theoretical and algorithmic, we agree that some numerical simulations comparing the two versions of our algorithm, as well as comparisons with existing ones for KBs and GLBs, would be of interest. We are running these simulations, and we will include them in the final version of the paper.

Questions

1. Yes, especially in the case of sub-Gaussian noise, we incur an additional $\log(\delta^{-1})$ factor (see line 340). We believe this is due to the use of Bernstein-like concentration bounds, which are suboptimal when dealing with sub-Gaussian noise. In this case, Hoeffding-like concentration bounds would be more appropriate. However, for our purposes, we need to use Bernstein-like bounds in order to highlight the dependence on the variance—specifically, to obtain tight bounds that depend on $\kappa_*$ in the dominating term.

2. This is necessary because the confidence radius $B_t(\delta; f)$ is instantiated for different functions $f$, specifically the optimistic ones $\widetilde{f}_t$ (see, for instance, Equation 105). To avoid a dependence on the sequence $(\\widetilde{f}\_t)\_{t \in [T]}$, which is random, in the regret bound, we chose to use the worst-case version with respect to the choice of $f$, i.e., $B_t(\delta, \mathcal{H})$. This phenomenon does not arise in generalized linear bandit algorithms, since the corresponding confidence radius does not explicitly depend on $\theta$ (the counterpart of $f$ in that setting); see, for instance, [A, Section 3.1]. In other words, those algorithms already consider the worst-case confidence radius by design.

3. Informally, our inequality can be seen as an extension of those mentioned by the Reviewer, allowing us to achieve a tight dependence on the square root of the cumulative variance $V_t = \sum_{s=1}^t \mathbb{E}[X_s^2 \mid \mathcal{F}_{s-1}]$. Specifically:

• [1, Theorem 1]: In the first inequality, the dependence is on a free parameter $V'$ that must be chosen deterministically, and thus independently of $V_t$, which is a random quantity. The second inequality instead depends directly on the cumulative variance $V_t$, rather than its square root—as ours does—which is necessary for achieving tight regret bounds.
• [2, Lemma 3]: This provides an inequality that depends on a parameter $\eta$, which (similarly to $V'$ in [1]) must be chosen deterministically and independently of $V_t$. Our bound can be viewed as an extension that allows $\eta$ to depend on the cumulative variance, enabled by the stitching technique.

References

[A] Abeille, Marc, Louis Faury, and Clément Calauzènes. "Instance-wise minimax-optimal algorithms for logistic bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

Thank you for your responses. They have addressed all my concerns, and I strongly maintain my score of 5.

I have read through all the discussions, especially with Reviewer nkzS. I have some comments of my own on some of the controversies, much of which as comment/question to the authors and some of which as response to Reviewer nkzS.

Heteroskedasticity

• I didn't get the "explicitly told by agent" heteroskedastic noise part, but because we are in a parametric setup (at least in the context of noise distribution), I don't see why this is a problem.
• $\sqrt{T / \kappa\_*}$ is precisely of the form $\sqrt{\sum\_t \sigma\_t^2}$ of variance-aware linear bandits. Namely, by definition, as the "optimal" variance (at the optimal arm) across the iterations is the same as $\dot\mu(f^\*(x^\*))$, the "analogous" form would be $\sqrt{\sum\_t \dot\mu(f^\*(x^\*))} = \sqrt{T \dot\mu(f^\*(x^\*))} =: \sqrt{T / \kappa\_\*}$.
• Question to the authors Is it straightforward for the results in this paper to be extended to time-varying arm-sets? In that case, one would obtain a regret bound that scales as $\sqrt{\sum\_t \dot\mu(f^\*(x\_t^\*))} = \sqrt{T \sum\_t \frac{1}{T} \dot\mu(f^\*(x\_t^\*))} =: \sqrt{T / \kappa\_\*}$, where $x\_t^\* := \mathrm{argmax}_{x \in X_t} f^*(x)$.

Regarding the controversy on the effective dimension, I looked into it myself by checking relevant kernel/neural bandits literature [1,2,3,4,5] as well as a dueling bandit paper [6] and a logistic bandit paper [7]. Here are my opinions:

• Just in case I was wrong, I , and it seems that the effective dimension is (or should be) non-stochastic, as it takes into account the entire context(arm) sets throughout the horizons, and to my knowledge in contextual bandits, the randomness or adversarialness of the arm sets should be independent from the algorithm's randomness. [4, Sec 4.2] first defines this by taking the worst-case over all possible context set sequences; subsequent works [5, Def 3.2] [3, Def 4.3] [1, Def 5.3] doesn't explicitly take the worst-case, but it still constructs (weighted/Hessian-like) design matrix over the entire context set sequence. [1, Def 5.3] even explicitly states "design matrix containing all possible context-arm feature vectors over the $T$ rounds"
• [2] is a bit confusing, as it states that "Note that placing an assumption on $\tilde{d}$ above is analogous to the assumption on the eigenvalue of the matrix $M_t$ in the work on linear dueling bandits Bengs et al. (2022)," but then [2]'s definition of $\tilde{d}$ (see their Eqn. (4)) seems to be in line with the above; considering the entire context set sequence. I believe this is a typo(..?) on [2]'s side, as Bengs et al. (2022) [6] have two assumptions on the eigenvalues: one critical (Sec. 3.2.1. (A1)) and one not so critical (Corollary 3.3). I believe that [2] was referring to the critical one, which originates from [7], is again independent of the algorithm and is only there to ensure that the context set is sufficiently spanning the whole space.
• Anyhow, long story short, I agree with nkzS that the authors should be a bit more careful when adding in discussions regarding the effective dimension, as I believe that the effective dimension of prior works do NOT depend on the specific algorithm's randomness. The authors should definitely include more detailed discussions regarding comparison of their information gain to prior notions discussed during the rebuttal.

Minor stuff

• I believe that the authors have indeed cited Srinivas et al. (2010) as [29] (cited in the Appendix footnote 10, but still included in the main text's references)
• This is something that I missed as well, but as correctly pointed out by nkzS, the authors should take more care in making the exposition more rigorous, especially regarding infinite-dimensional notions such as Fredholm determinants throughout the main text and the proof.
• (line 245) "The fundamental result in the GLB literature is the bound of [9, Theorem 1]:" => should make it clear that the concentration holds only for Bernoulli.
• (should not impact the decision at all) about a week ago, a preprint (https://arxiv.org/abs/2507.20982) came out that provide some nice overview of the missing references as well as new dimension-free concentration for kernelized logistic regression. For the camera-ready, relevant discussions to this would be nice as well.

P.S. I may be wrong on some stuff, especially regarding the quick literature review. Please feel free to let me know if there are anything that I missed or misinterpreted or mistaken in my response. Thanks!

[1] https://arxiv.org/abs/2505.02069

[2] https://openreview.net/pdf?id=VELhv9BBfn

[3] https://proceedings.mlr.press/v119/zhou20a/zhou20a.pdf

[4] https://proceedings.mlr.press/v119/yang20h/yang20h.pdf

[5] https://arxiv.org/pdf/2010.00827

[6] https://proceedings.mlr.press/v162/bengs22a/bengs22a.pdf

[7] https://proceedings.mlr.press/v70/li17c/li17c.pdf

We thank the Reviewer for the feedback and for appreciating the clarity of the mathematical derivations and the effort in deriving an efficient implementation. Below, we address the Reviewer's concerns.

Weaknesses on Credit Assignment and Over-claiming

• We thank the Reviewer for reference [1]. First of all, we note that, according to the NeurIPS Call for Papers, [1], being made available online after March 1st, must be considered contemporaneous work. Therefore, the presence of [1] cannot be used as an argument to diminish the novelty of our paper. Nevertheless, we provide below a comparative discussion with our work, which we will include in the final version of the paper:

1. Section 3 of [1] provides a concentration bound (Theorem 3.1) similar to our Theorem 6.2. However, their result (i) assumes a finite-dimensional decision set; and (ii) exhibits a worse dependence on $t$, being of order $\log(t)$, whereas ours is of order $\log\log(t)$. Looking at Appendix A of [1], it can be observed that their proof technique is very similar to ours, as both are inspired by Zhou et al. (2022). Thus, [1] is not using simpler techniques, except for avoiding the stitching/peeling argument, which we specifically use to reduce the $\log(t)$ dependence to $\log\log(t)$.

2. The effective dimension $\widetilde{d}$ in Definition 5.3 of [1] is not the same as our maximal information gain $\gamma_T$. Indeed, Definition 5.3 of [1] does not consider the exact variance term $\dot{\mu}(f^*(x_t))$, which is instead upper bounded by its maximum value $R$ (denoted as $R_{\dot{\mu}}$ in our notation). In contrast, in our definition in Section 5, we retain the variance terms $\dot{\mu}(f(x_t)) \le R$ within the definition of information gain, which leads to the bound $\widetilde{\Gamma}_t(f) \le \widetilde{d}$. Even when considering the worst-case sequence of decisions, leading to the maximal information gain $\gamma_T$, we still retain the variance factors. Finally, $\widetilde{d}$ is a random quantity that depends on the specific realization of the algorithm's execution (i.e., the sequence of decisions). For this reason, it is inappropriate to present a regret bound, such as in Theorem 5.5 of [1], that depends on it. Instead, a maximal version based on the worst-case sequence of decisions should be considered (like $\gamma_T$), as is standard in approaches like [2].

3. The regret bound of [1, Theorem 7.2] holds under Condition 5.4, which in turn involves several assumptions (5.1 and 5.2) that are not required by our algorithm. Before comparing the regret bounds, a few considerations:

(i) [1, Theorem 7.2] does not show a dependence on the norm of the decisions $\\|x\\|_2$, since under their Assumption 5.2 it is assumed to be 1. This corresponds, in our notation, to setting $K=1$;

(ii) [1, Theorem 7.2] depends on $S$, which is defined in Definition 6.2 and is therefore related to the bound on the norm of the parameters $\theta$. Thus, apart from constants (like $m$, the number of hidden neurons in the network), $S$ corresponds to our parameter $B$.

Given these considerations, we can effectively compare our regret bound with that of [1] (setting $K=1$ and assuming $\widetilde{d} \approx \widetilde{\gamma}_T$ for a fair comparison):

$

\text{Our bound:} \qquad \widetilde{O}\left( B \widetilde{\gamma}_T \sqrt{\frac{T}{\kappa_*}} + B^2 \sqrt{\frac{\widetilde{\gamma}_T T }{{\kappa_{*}}}} \right).

$

$

\text{Bound of [1, Theorem 7.2]:} \qquad \widetilde{O}\left(B^2 \widetilde{\gamma}_T \sqrt{\frac{T}{\kappa_{*}}} + B^{2.5} \sqrt{\frac{\widetilde{\gamma}_T T}{\kappa_{*}}} \right).

$

Thus, our bound exhibits a better dependence on $B$.

• Regarding the heteroschedasticity, the goal of our Table 1 is to compare the approaches able to tackle generalized linear bandits or kernelized bandits. We thank the Reviwer for the references, however, we think they do not consider these settings. Indeed, [3] focuses on dueling bandits that differ from our setting from the interaction protocol (although a link function is present as well), whereas [4] focuses on linear bandits. Nevertheless, we will cite them in the related works section to mention further works that focus on the heteroschedastic case.

• As the Reviewer noted, we acknowledged the non-tight dependence on $K$ and $B$ in the conclusions. In the abstract, we intended to specify the tightness of the dependence only with respect to $\gamma_T$, $T$, and $\kappa_*$. To avoid any risk of overclaiming, we will rephrase the sentence in the abstract as:
  "Our results match, up to multiplicative constants and logarithmic terms, the state-of-the-art bounds for both KBs and GLBs with respect to $\gamma_T$, $T$, and $\kappa_*$, while showing suboptimal dependence on $B$ and $K$."

• First of all, we clarify that the term stitching is widely used in the community dealing with confidence sequences [e.g., A, B]. More importantly, we never claimed that our empirical Freedman inequality in Theorem 6.1 is of independent interest. Indeed, we are aware that similar results already exist, and this is evidenced by the sentence between lines 282 and 283, where we cite a result, [12, Theorem 12], analogous to those provided by the Reviewer (Theorem 9 of [6] and Appendix A of [7]). We will include the references suggested by the Reviewer in the final version. However, we highlight that they compare analogously to [12, Theorem 12] in relation to our inequality. Specifically, as stated between lines 283–284, "our result allows tuning the parameters $\eta$ and $v_0$ to tighten the bound, ultimately leading to an improvement of the constants." We emphasize once again that this is the only improvement over the state of the art that we claim for Theorem 6.1, namely, generality in $\eta$ and $v_0$, and better constants ($\sqrt{2}$ in our case, compared to $3$ in Theorem 9 of [6], and $\sqrt{8}$ in Appendix A of [7]). We will further clarify this in the final version. The phrase independent interest appears in our manuscript at lines 10 and 346, and in both cases, it unequivocally refers to the self-normalized bound of Theorem 6.2, which is novel.

Weaknesses on Rigorousness and Correctness

Thank you for pointing out the issue. As we mentioned in Footnote 12, we focused on the setting of paper [32], as our derivations are valid under Assumptions 1 and 2 of [32], which are the same as those considered in our paper. As the Reviewer correctly points out, in [32], the determinant used is the Fredholm determinant. We will clarify this in our manuscript. Regarding the specific derivation in line (196), we note that the same argument (in the infinite-dimensional case) is employed in the "Proof Sketch for Theorem 2," which relies on Lemma 5 of [32], a result that holds in infinite-dimensional Hilbert spaces. For this reason, we will replace the citation to [8] with a reference to [32, Lemma 5] and mention that we are working with Fredholm determinants.

References

[1] Bae, S., & Lee, D. (2025). Neural Logistic Bandits. arXiv preprint arXiv:2505.02069.

[2] Faury, L., Abeille, M., Calauzènes, C., & Fercoq, O. (2020, November). Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning (pp. 3052-3060). PMLR.

[3] Zhao, H., He, J., Zhou, D., Zhang, T., & Gu, Q. (2023, July). Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4977-5020). PMLR.

[4] Di, Q., Jin, T., Wu, Y., Zhao, H., Farnoud, F., & Gu, Q. (2023). Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.00968.

[5] Lee, J., Yun, S. Y., & Jun, K. S. (2024). A unified confidence sequence for generalized linear models, with applications to bandits. arXiv preprint arXiv:2407.13977.

[6] Zimmert, J., & Lattimore, T. (2022, June). Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory (pp. 3285-3312). PMLR.

[7] Li, G., Cai, C., Chen, Y., Wei, Y., & Chi, Y. (2021). Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis. arXiv preprint arXiv:2102.06548.

[8] Abeille, M., Faury, L., & Calauzènes, C. (2021, March). Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics (pp. 3691-3699). PMLR.

[A] Kuchibhotla, Arun K., and Qinqing Zheng. "Near-Optimal Confidence Sequences for Bounded Random Variables." International Conference on Machine Learning. PMLR, 2021.

[B] Chugg, Ben, Hongjian Wang, and Aaditya Ramdas. "Time-Uniform Confidence Spheres for Means of Random Vectors." Transactions on Machine Learning Research.

[32] Justin A. Whitehouse, Aaditya Ramdas, and Zhiwei S. Wu. On the sublinear regret of GP-UCB. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 35266–35276, 2023.

But in the finite-dimensional setting, no matter you are using [32, Lemma 5] or [8, Lemma 12], how could the $\log\det$ stuff in the proof be dimension-free?

• If you use [8, Lemma 12] directly in the finite-dimensional setting, there should be a linear dependency on $d$, right?
• If you use [32, Lemma 5], how could it be applicable for the finite dimensional setting?

To be more concrete, in the finte-dimensional setting, $\det(\lambda I)$ is $\lambda^d$ and $\log (\det (\lambda I))^{-1}$ will be linear in $d$.

References

[8] Abeille, M., Faury, L., & Calauzènes, C. (2021, March). Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics (pp. 3691-3699). PMLR.

[32] Justin A. Whitehouse, Aaditya Ramdas, and Zhiwei S. Wu. On the sublinear regret of GP-UCB. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 35266–35276, 2023.

Thank you for your answer, your concern is now clearer to us. We take this opportunity to further clarify:

• When claiming the dimension-free property, we were referring to the explicit dependence on $d$ in the concentration inequality. Our Theorem 6.2 does not exhibit such a dependence.

• The Reviewer is referring, instead, to an implicit dependence on $d$, which appears in the bound of the log-determinant term $\log \det (\lambda^{-1}\widetilde{V}_t(\lambda))$ in Theorem 6.2. Specifically,

  $$\log \det (\lambda^{-1}\widetilde{V}_t(\lambda)) = \log \det (I + \lambda^{-1} \widetilde{V}_t) \le d \log \left( 1 + \frac{K^2 R\_{\dot{\mu}} }{\mathfrak{g}(\tau) \lambda d} (t-1) \right),$$

  which can be derived analogously to Lemma C.7. This bound applies to finite-dimensional feature spaces; but other bounds for the term $\log \det (\lambda^{-1}\widetilde{V}_t(\lambda))$ for example, using the information gain, are also possible and meaningful even in the finite-dimensional case.

• Nevertheless, for generalized linear bandits, it has been shown that dependence on the dimensionality $d$ is unavoidable in the worst-case scenario (see, for instance, Theorem 2 of [2]). This is the reason why the bound to $\log \det (\lambda^{-1}\widetilde{V}_t(\lambda))$ contains a dependence on $d$ and, in this sense, cannot be dimension-free.

• Finally, we remark that, even the seminal inequality of Abbasi-Yadkori et al. (2011) [1], which we also classified as "dimension-free" in Table 1, contains a log-determinant term, whose bound depends on $d$ (see Theorem 2 of [1] statements 1 and 2).

We hope this clarifies the issue. We will make sure to include this discussion on this point.

References

[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems (NIPS), pages 2312–2320, 2011

[2] 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 (AISTATS), pages 3691–3699. PMLR, 2021.

Let us say just for linear logistic bandits with feature dimension $d$. No matter how you redefine the $\log\det$ stuff into new quantities like "maximal information gain", both the self-normalized concentration bounds in this submission and [F] scale with $\mathrm{poly}(d)$, right? But [F] is classified as "not dimension-free" in Table 1 of this submission. Is that my misunderstanding???

References

[F] Faury, L., Abeille, M., Calauzènes, C., & Fercoq, O. (2020, November). Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning (pp. 3052-3060). PMLR.

First of all, let us remark that the reason why we classified [F] as "non-dimension-free" is because of the explicit dependence on $d$ in the last addendum of Theorem 1: $\frac{2}{\sqrt{\lambda}} \boldsymbol{\color{red}d} \log(2)$ and not because the log-determinant is bounded by to $\text{poly}(d)$. That said, [F] and our inequality, when restricted to logistic bandits, contain precisely the same log-determinant term: $\log \det (\lambda^{-1} \widetilde{V}\_t(\lambda)) = \log \det (I + \lambda^{-1} \widetilde{V}_t)$ with \\widetilde{V}\_t = \\sum\_{s=1}^{t-1} \\dot{\\mu}(\\theta^\\top x\_s) x\_s x\_s^\\top.

Now, the question becomes whether $\log \det (\lambda^{-1} \widetilde{V}\_t(\lambda))$ is always $\text{poly}(d)$ , or only bounded to $\text{poly}(d)$ in certain cases. Consider the following example, where we assume $\\dot{\\mu}(\\theta^T x\_s) = 1$ for simplicity (i.e., linear bandits). Suppose x_s = (1,0,\dots,0)^\\top for every $s \\in \\{1,\dots,t-1\\}$, we have that: \\widetilde{V}\_t = \\begin{pmatrix} t-1 & 0 & \\dots & 0 \\\\ 0 & 0 & \dots & 0 \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ 0 & 0 & \dots & 0 \\end{pmatrix}, \qquad \\lambda^{-1} \\widetilde{V}\_t(\lambda) = I + \\lambda^{-1} \\widetilde{V}\_t = \\begin{pmatrix} 1 + \\lambda^{-1}(t-1) & 0 & \\dots & 0 \\\\ 0 & 1 & \dots & 0 \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ 0 & 0 & \dots & 1 \\end{pmatrix}. As a consequence, $\log \det (\lambda^{-1} \widetilde{V}\_t(\lambda)) = \log(1 + \\lambda^{-1}(t-1) )$, which shows no dependence on $d$. Clearly, this is a rather unrealistic case when applying our inequality or that of [F] in a regret minimization algorithm. Still, restricted to the discussion of the properties of the concentration inequality, this provides an example in which our inequality shows no dependence on $d$ at all, whereas that of [F] does, due to the presence of the term $\frac{2}{\sqrt{\lambda}} \boldsymbol{\color{red}d} \log(2)$.

Nevertheless, if the Reviewer believes that our definition of dimension-free as lack of explicit dependence on $d$ may be misleading, we are open to changing it (including also implicit dependencies on $d$) in the manuscript to avoid any confusion.

• I believe I have understood what the authors try to claim about the reason behind why they sometimes give a worst-case bound an executation-dependent quantity but in some other cases (in the finite-dimensional setting) are in need of manifesting that the $\log\det(...)$ quantity is not always as bad as $\mathrm{poly}(d)$.
• If my understanding is correct, then, let us now focus on the penultimate column of Table 1 of this submission, whose title is "Heterosc."; my concerns are as follows.
  • Following the authors' reasoning about what the authors intended by heteroscedasticity, then may I ask which paper on generalized linear bandits (under assumptions similar to this submission) cannot deal with heteroscedastic feedback noise? For example, it seems that the authors' reasoning implies that all published papers by far on logistic bandits can deal with heterscedasticity.
  • According to the explanation by the authors on what they intended by heteroscedasticity, the check marks in the penultimate column of Table 1 are only because the data model of interest is generalized linear models, and the contrast between the cross marks and check marks in this column is not a part of the "new knowledge" introduced by this submission.

I have read the authors elaboration on what they intend to claim by "dimension-free" and believe I have understand what they want to claim about it. Regarding other technical parts of the rebuttal. I have the following viewpoints as a follow-up.

1. Based on my understanding, in the rebuttal and subsequent responses, the authors try to battle with themselves as follows.
   • The authors consider it to be inappropriate the place the executation-dependent quantity $\\tilde{d}$, which is termed as the "effective dimension" in standard neural bandits literature [Z, V, 1], in the upper bounds and claim that their worst-case quantity $\gamma_T$ (the maximal information gain) to be more appropriate than that in [1] when comparing these two concurrent works.
   • On the other hand, when the authors discuss about their "worst-case $\mathrm{poly}(d)$" quantity $\\log\\det(\\lambda^{-1}\tilde{V}\_t(\\lambda))$, they try to justify that this executation-dependent quantity can be dimension-free when the executation has nice $\\{x_s\\}\_{s=1}^{t-1}$.
   • Overall, I suggest the authors to have a consistent tone when discussing their work and others. By the way, a minor point is that, if it is indeed the case that $\tilde{d} \lesssim \gamma_T$, it is not very appropriate to claim the introduction of $\gamma_T$ to be a key difference of that $\tilde{d}$ in [1].
2. In the authors' rebuttal bullet "Regarding the heteroschedasticity ...", there are several points to remind.
   • The authors claim that "[3] focuses on dueling bandits", which is not true. [3] focuses on linear bandits.
   • Also, as a minor point, at least two papers on linear bandits appear in Table 1 of this submission, but in the rebuttal, the authors state that "the goal of our Table 1 is to compare the approaches able to tackle generalized linear bandits or kernelized bandits".
   • Most importantly, the authors claim that they method can tackle heteroscedastic noise, but only when the heteroscedastic variance is explicitly told to the agent. This is considered a significant drawback because such a "explicit variance revealing" is already not needed for the linear and generalized linear settings, at least several years ago, see, e.g., [3,4].
     • I definitely know that "dueling ... are not exactly genearlized linear ..." and "kernel ... is not exactly linear ...", but technically speaking, since "explicit varaince revealing" can be avoided in linear bandits or bandits with link functions; it should be, mathematically, not needed for at least the finite-dimensional case in this submission.
     • Since "heteroscedasticity" is really an application-inspired concept, it is not very clear why could the agent see the heteroscedastic variance by explicitly know $g(\tau)\dot{\mu}(f(\mathbf{x}))$, where we know that the noise variance is exactly $g(\tau)\dot{\mu}(f(\mathbf{x}))$.

References

[Z] Zhou, D., Li, L., & Gu, Q. (2020, November). Neural contextual bandits with ucb-based exploration. In International conference on machine learning (pp. 11492-11502). PMLR.

[V] Verma, A., Dai, Z., Lin, X., Jaillet, P., & Low, B. K. H. (2024, January). Neural dueling bandits. In ICML 2024 Workshop: Foundations of Reinforcement Learning and Control--Connections and Perspectives.

[1] Bae, S., & Lee, D. (2025). Neural Logistic Bandits. arXiv preprint arXiv:2505.02069.

[3] Zhao, H., He, J., Zhou, D., Zhang, T., & Gu, Q. (2023, July). Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4977-5020). PMLR.

[4] Di, Q., Jin, T., Wu, Y., Zhao, H., Farnoud, F., & Gu, Q. (2023). Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.00968.

We thank the Reviewer for the feedback and for appreciating the technical solidity of the paper. In the final version, we will make use of the additional page to introduce the discussion earlier and provide more details on the important concepts. Below, we provide answers to the Reviewer's questions.

1. We believe that this assumption is quite mild. As we discuss immediately below the assumption, for $\nu^2$-sub-Gaussian noise $\epsilon_t$ (which includes Gaussian noise), we can always set $R = \nu\sqrt{2\log(2T/\delta)}$, which guarantees that $|\epsilon_t| \le R$ uniformly for all $t \in [T]$ with probability at least $1 - \delta$. This follows from a union bound argument:

where the second inequality follows from the union bound, and the last one from Hoeffding's inequality for sub-Gaussian random variables. We will include this elaboration in the final version.

2. This is desirable because many link functions used in practice, such as the sigmoidal one, have a bounded maximum slope (e.g., $R_{\dot{\mu}} = 1$ for the sigmoid and the identity function), while their minimum slope can approach zero (i.e., $\kappa_{\mathcal{X}} \approx 0$ for the sigmoid function). Therefore, a dependence on $1/\kappa_{\mathcal{X}}$, as found in early works on generalized linear bandits [e.g., A], is undesirable.

3. In a kernel space, the dimensionality $d$ of the feature map $\phi$ induced by the kernel $k$ can be infinite. Thus, assuming $d$ to be finite would reduce the setting to the already studied generalized linear bandit case. Moreover, even under the assumption of finite $d$, it would not be possible to remove Assumption 3.1, which—in the generalized linear bandit case—reduces to requiring a bounded norm of the parameter $\theta$ [see B, Assumptions 1 and 2].

4. The heteroscedasticity of the noise is directly related to the noise model, which is based on a canonical exponential family. Under this model, the variance of the noise is proportional to the slope of the link function, i.e., $\text{Var}[\epsilon_t] \propto \dot{\mu}(f(x))$. We will emphasize this point in the final version.

5. We introduce two versions, $B_t(\delta, f)$ and $\beta_t(\delta, f)$, which differ in the use of the information gain: $\widetilde{\Gamma}_t(f)$ versus the maximal information gain $\widetilde{\gamma}_t(f)$. Consequently, $B_t(\delta, f) \le \beta_t(\delta, f)$, where the former is a random variable and the latter is a deterministic quantity. Moreover, we consider their worst-case versions over the choice of $f$: namely, $B_t(\delta, \mathcal{H})$ and $\beta_t(\delta, \mathcal{H})$, respectively. These quantities satisfy the following relations:

In principle, we could use the largest one, $\beta_t(\delta, \mathcal{H})$, from the beginning. However, using the former ones allows us to obtain tighter bounds, which improve the theoretical guarantees and may also lead to practical improvements. We will include a clarification on that in the paper.

6. Although we believe that the core contributions of the paper are mainly theoretical and algorithmic, we agree that some numerical simulations comparing the two versions of our algorithm, as well as comparisons with existing ones for KBs and GLBs, would be of interest. We are running these simulations, and we will include them in the final version of the paper.

References

[A] Jun, Kwang-Sung, et al. "Scalable generalized linear bandits: Online computation and hashing." Advances in Neural Information Processing Systems 30 (2017).

[B] Abeille, Marc, Louis Faury, and Clément Calauzènes. "Instance-wise minimax-optimal algorithms for logistic bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

Thanks for including the experiments! Minor comments (for camera-ready revision mostly):

• OFULog-r (Abeille et al., 2021) is for logistic bandits, not generalized linear bandits
• Can the authors consider the current SOTA logistic bandit algorithm, OFUGLB, due to Lee et al. (2024)? Their algorithm, I believe, is applicable to any generalized linear bandits as well. If the time allows for the camera-ready revision, {linear, logistic, Poisson} bandit experiments would further strengthen the paper.
• Although it is true that the pseudocode in Appendix A is more efficient than Algorithm 1, it still requires solving the MLE each iteration. I believe a more suitable terminology is "tractable implementation." The authors should carefully include discussions such as space/time complexity. Some relevant references: [1,2,3].

[1] https://arxiv.org/abs/2507.11847

[2] https://openreview.net/forum?id=ofa1U5BJVJ

[3] https://openreview.net/forum?id=Q4NWfStqVf