In the kernelized bandit problem, a learner aims to sequentially compute the optimum of a function lying in a reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims to minimize regret, which is a measure of the suboptimality of the choices made. Arguably the most popular algorithm is the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm, which involves acting based on a simple linear estimator of the unknown function. Despite its popularity, existing analyses of GP-UCB give a suboptimal regret rate, which fails to be sublinear for many commonly used kernels such as the Mat\'ern kernel. This has led to a longstanding open question: are existing regret analyses for GP-UCB tight, or can bounds be improved by using more sophisticated analytical techniques? In this work, we resolve this open question and show that GP-UCB enjoys nearly optimal regret. In particular, our results yield sublinear regret rates for the Mat\'ern kernel, improving over the state-of-the-art analyses and partially resolving a COLT open problem posed by Vakili et al. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel $k$. Applying this key idea together with a largely overlooked concentration result in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide a tighter analysis of the GP-UCB algorithm.
Paper
Similar papers
Peer review
Summary
The paper proposes a new analysis for the popular GP-UCB algorithm. Under this new approach, it is shown that GP-UCB achieves a sub-linear regret (though not optimal), partially resolving the question of whether GP-UCB can achieve optimal regret.
Strengths
The paper proposes a new self-normalized martingale type inequality for infinite dimensional Hilbert spaces, which might be of independent interest to the community. The sub-linear convergence of GP-UCB shown by the paper is indeed of interest to better understand the observed performance of popular algorithm.
Weaknesses
I can see that there is clearly certain improvement over the existing result. However, my concern is whether the result warrants a full publication. From what I understand, the important trick is to analyse in the Hilbert space representation, which allows for a tighter analysis and a cleaner dependence on the regularization parameter. I don't think that the approach taken in Chowdhury and Gopalan is incompatible with the philosophy presented in this paper, although I do agree that reaching this conclusion (specifically dependence on the regularization parameter) might not be as easy. So overall, I feel there is certainly _some_ novel contribution here, especially with regards to understanding the behaviour of GP-UCB. However, I don't think there is sufficient contribution for a full paper at NeurIPS. I feel the result is more appropriate for a shorter paper or a letter to a journal. I would encourage the authors to submit to such a venue.
Questions
No particular question.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Yes.
Summary
This is a very well written paper with nice, clean results on self-normalised concentration for seperable RKHS. The paper claims two contributions: 1. A new self-normalised concentration result for seperable RKHSs. 2. Improving the regret of GP-UCB by tuning the regularisation parameter.
Strengths
The write-up is of excellent quality. The bounds derived are very neat and strong. The trick used to get better regret is neat and easy to use.
Weaknesses
The result claimed in point 1 is actually well known, and has been for over a decade. See Theorem 4.1 in [1]. Indeed, the authors of the submitted manuscript state: "To the best of our knowledge, Fact 6 is the only existing result on self-normalised, time-uniform concentration in RKHS's [sic]", where Fact 6 is from [2], and Fact 6 is implied by (and strictly weaker than) Theorem 4.1 of [1]. This is unfortunate, and completely not the authors fault ([2] should not have been accepted in the first place). However, this isn't an issue that can be resolved by adding a citation to [1] in a camera ready version: even the paper's title is, after all, "Improved Self-Normalized Concentration in Hilbert Spaces". For this reason, I recommend that the paper is rejected. The result claimed in point 2 relies on trading off the effective dimension term versus the regularisation term. This is a neat idea and very much ought to be published, by itself, in a paper that doesn't claim 1 as a contribution. Point 2 is very similar to Theorem 31 and 32 of [3]. There, the effective dimension is likewise traded off, but with RKHS norm (which the regularisation multiplies). Theorem 31 uses this trick to achieve a weaker result (the resulting implied regret is not sublinear for all $\nu, d$ for the Mat\'ern kernel); under an additional assumption, which has only been established for a particular choice of $d, \nu$ (uniform boundedness of kernel eigenfunctions). Theorem 32 would give the same result for the Mat\'ern kernel as in the submitted manuscript. There, the trade-off is done by changing lengthscale---doing it via regularisation, as done in the submission, is a much better idea. A rewrite of this paper that makes clear what is previous work and what is the authors contribution would warrant a strong accept. [1] Abbasi-Yadkori, Yasin. Online learning for linearly parametrized control problems. Diss. 2013. [2] Chowdhury, Sayak Ray, and Aditya Gopalan. "On kernelized multi-armed bandits." International Conference on Machine Learning. PMLR, 2017. [3] Janz, David. Sequential decision making with feature-linear models. Diss. 2022.
Questions
None
Rating
1: Very Strong Reject: For instance, a paper with trivial results or unaddressed ethical considerations
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
4 excellent
Presentation
1 poor
Contribution
1 poor
Limitations
None
Summary
This paper addresses the kernelized bandit problem and focuses on improving the regret bounds of the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm. The authors introduce novel techniques to achieve nearly optimal regret rates for GP-UCB. These improvements surpass previous state-of-the-art analyses and partially resolve an open problem posed by Vakili et al.
Strengths
The paper suggest a new analysis the leads to improved regret bounds for the GP-UCB algorithm. The technique used in the paper is based on a novel concentration inequality (Theorem 1) that may be of independent interest. In addition, they demonstrate that the consideration of regularization based on kernel smoothness contribute to the nearly optimal regret rates as well.
Weaknesses
The main weakness is perhaps clarity of presentation that renders the paper less accessible to a non-expert in the field. For example, the authors refer to the Matern kernel as a commonly used kernel, yet to someone not as familiar with the specific literature it is harder to interpret the result. Perhaps consider providing a bit more background on it. (e.g., it was not mentioned in [4]) Why is it commonly used and what are trade-offs with other kernels? Also consider including a table comparing the bounds with previous analysis, similar to Table 1 in [27], that would be helpful as well.
Questions
see above
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
none
Summary
This paper re-investigates the upper bound analysis of the popular GP-UCB algorithm (in its vanilla version), focusing on the cumulative regret for Matern kernel (and more generally, kernels with polynomial decay). The study reveals that the previous non-sub-linear regret bounds can be surpassed.
Strengths
From the overall achieved result of this paper, I would say the authors have made a great contribution to this community, addressing an existing major concern that GP-UCB on Matern kernel fails to achieve sub-linear cumulative regret. This finding would have a significant impact on tons of exisintg upper bounds based on IGP-UCB (Chowdhury & Gopalan, 2017), and its certain variants. The behind insights may also inspire future improvements, to see if this bound can be finally optimal that counteracts the lower bound in (Scarlett et.al, 2017).
Weaknesses
However, I have some reservations about their technical details, particularly regarding their derivation of Theorem 1. Here are several reasons: * The technical contribution of this paper appears to be non-significant, as it essentially extends a well-known result from linear bandits (Abbasi-Yadkori et.at, 2011), by fusing several exsiting results/facts. * The extension starts with assuming a finite-dimensional RKHS (with dimension N) and then somehow lets $N\to\infty$. * Though the truncation technique is widely used in analyzing infinite-dimensional spaces, it usually involves rigorous analysis of the residual term, which is not seeing to be well-treated in this paper. * In Appendix, line 461, the statement "there exists some..." seems to compress a lot of information. While I understand the existence of such $N_t$ should be due to eigenvalue decays, such existence should be proven or more thoroughly discussed. * It is confusing to write $||A||_H \overrightarrow{dim(H)\to\infty} ||A||_H$, as the two RKHS spaces are essentially not the same (finite v.s. infinite), where they are both being denoted by the same $H$. * Overall, I was expected to see a more formal proof by properly handling the residual error term, but what I see is more like "spamming" $N\to\infty$. On the other hand, the presentation is not appealing due to: * Section 1 lacks intuitions about the tools/ideas to be used, which is essential for a technical paper. * Section 2 is too long, and could be significantly reduced either by moving some less-important content to Appendix, or just providing informal results. * Some terminologies, like "double mixture," are not explained, leaving readers without clear understanding. Miscellaneous minor issues: * The templates seem to be from NeurIPS 2020, not 2023 * line 182: "We can then making..." * Appendix line 471: "so so" * What is $\rho \downarrow 0$? * "Holder" should be Hölder * No formal definition of RKHS norm?
Questions
Since the self-normalized concentration can also be used to show bounds for GP-TS, as was done by (Chowdhury & Gopalan, 2017), does the improved Theorem 1 result in similar improved results for GP-TS?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
3 good
Presentation
2 fair
Contribution
4 excellent
Limitations
NA
Summary
This paper addresses the open question of Vakili et al, on the possibility of obtaining rate-optimal regret bounds for kernelized bandits under the RKHS assumption. Authors present a slightly different RKHS martingale bound, which allows them to obtain a regret of the form $\rho\sqrt{\gamma_TT}+ \gamma_T\sqrt{T}$. By carefully choosing the regularization parameter $\rho$ corresponding to the smoothness of the kernel, they are able to improve the rate of regret of the well known GP-UCB. This is particularly important in the case of rough Matern kernels, where the classic bounds become vacuous, while this paper still shows sublinearity.
Strengths
1. The paper gives non-vacuous regret bounds for GP-UCB under RKHS assumption, despite many of the classical prior works (e.g. Srinivas et al or Chowdhury & Gopalan). 2. I think the key strength is the nice and simple idea of tuning the regularization parameter according to the smoothness of the kernel. This choice makes a lot of sense and I am surprised that we have not been doing so all along. 3. The proof technique (truncation trick) for obtaining the $\mathcal H$-valued bound is also quite intuitive and interesting. I think the approach say in Lemma 2 may be used in other applications, to easily go from finite-dimensional analysis to kernels. 4. The paper is very well written, its clear and has a great flow. It gives good education!
Weaknesses
1.This paper does not resolve the open question of Vakili et al. As far as I know, the key question within the field is to whether we can get a $\sqrt{T\gamma_T}$ bound on the regret in the RKHS setting, as we do in the GP setting. Effectively, this paper improves the dependency of $\gamma_T$ on $T$, so that while we still have a $\gamma_T\sqrt{T}$ bound, the gap with the lower bound [Scarlet et al 2017] and the GP upper bound is reduced. The authors conjecture in the conclusion that fully closing this gap may not be possible in the Conclusion section. I believe that is correct. In fact, the paper "A Lower Bound for Linear and Kernel Regression with Adaptive Covariates" [Lattimore, COLT 2023] addresses the same open problem, and shows that such confidence sets cannot be improved by any estimator. 2.I should also point out Chowdhurry & Gopalan is not the only result for bounding $\mathcal H$-valued martingales. As far as I know, this was first introduced in Theorem 3.11 in the PhD Thesis of Yasin Abbasi Yadkori in 2013, titled "Online Learning for Linearly Parametrized Control Problems" published by University of Alberta. Could you please compare the Theorem 1 in the paper with Theorem 3.11 of Abbasi-Yadkori? Due to difference in notation I can rigorously compare the bounds. How do the proof techniques differ?
Questions
In Chowdhurry and Gopalan's paper, what would happen if we set $\eta$ also as a function of $\eta$? Could we in the end obtain the same rate for regret? The bounding process (rhs of the inequality) in Theorem 1, is similar to that of Lemma 1 in Chowdhurry & Gopalan, while I can see that the martingale is slightly different. Is this slight difference actually stopping them from getting the same rates? Or could it be that by tuning $\eta$ different than them (the simply set it to $1/t$) a similar rate as Cor 2 may be obtained?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
2 fair
Limitations
Limitations are adequately addressed. The paper "A Lower Bound for Linear and Kernel Regression with Adaptive Covariates" Lattimore COLT 2023 should be mentioned.
Summary
This paper investigates the performance of the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm in kernelized bandit problems, focusing on the minimization of regret. The authors present a novel, self-normalized concentration inequality and a technique to regularize in proportion to the kernel's smoothness, which significantly simplifies the analysis of GP-UCB. The study reveals that GP-UCB, when properly regularized, provides nearly optimal, sublinear regret for kernels experiencing polynomial eigendecay, including the Matern kernel. The results validate the empirical performance of GP-UCB and emphasize the importance of thoughtful regularization in online learning problems.
Strengths
NA
Weaknesses
NA
Questions
NA
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
NA
Response to Authors Rebuttal
Thank you for your response. I understand that the PhD Thesis of Abbasi-Yadkori is not a common read, and did not have necessarily expected the authors to be aware of it. Overall, since the authors have added the missing important references (and hopefully a discussion on them) I think this paper will be a valuable reference on H-valued Martingale bounds, and the proof techniques presented here have the potential of being used in other applications.
We thank the reviewer for their support of our work. We indeed hope our work will be a useful reference for concentration in Hilbert spaces, and hope the simple idea of regularizing in proportion to the eigendecay of the underlying kernel will be applied in other bandit problems as well.
Thank you for your reply. It appears that we agree on the substance of my review, but (unsurprisingly) not on the outcome it warrants. **I will not adjust my score,** in that I stand by my opinion that without the possibility of a second round of review, this paper should not be accepted. At the same time, if the AC were to be satisfied with accepting the authors promise to do justice to previous work and significantly rewrite the paper (and on the condition that the title may be edited, as to which I am unsure), **my hypothetical score for such a rewritten paper would likely be an 8.**
Also, I have just seen an arxiv version of this work cited elsewhere. For the sake of respect for Yasin's contribution, I would urge the authors to make haste in correcting the record on this on arxiv.
*1. Thank you for your reply. It appears that we agree on the substance of my review, but (unsurprisingly) not on the outcome it warrants. I will not adjust my score, in that I stand by my opinion that without the possibility of a second round of review, this paper should not be accepted. At the same time, if the AC were to be satisfied with accepting the authors promise to do justice to previous work and significantly rewrite the paper (and on the condition that the title may be edited, as to which I am unsure), my hypothetical score for such a rewritten paper would likely be an 8.* We thank the reviewer greatly for their hypothetical score. We have already fully edited the manuscript to reflect the promised changes, and thus disagree that another review cycle is necessary. We nonetheless respect the reviewer’s decision to maintain their original score. *2. Also, I have just seen an arxiv version of this work cited elsewhere. For the sake of respect for Yasin's contribution, I would urge the authors to make haste in correcting the record on this on arxiv.* Arxiv has been correspondingly updated to reflect the promised changes.
Response to Author Feedback
Thanks for the feedback. Please see my latest response. Let's leave behind the questions regarding the first point, as it is no longer considered a contribution of this paper. Forgive me that I was also not aware of the existence of Theorem 1, so that the previous assessment, which was based on regarding point 1 as a major contribution (though I questioned some of the technical details), is now invalid. This leads me to conclude that, in its current state, the paper **needs a major revision**. While the idea behind the second point is intriguing, regrettably, I would only be able to recommend the acceptance of this paper if: - A significant amount of rewriting of the full paper. - A deeper discussion/exploration of varying $\rho$ with $T$. See the details below: - Generally speaking, the idea of treating the regularization parameter $\rho$ as a variable is not new in Bayesian learning, e.g., in Baeysian quadrature (BQ), the optimal $\rho$ is related to the fill distance $h_X$, and in case of Matern-$\nu$ kernel, $\rho = h_X^{\nu}=\Theta(T^{-\frac{\nu}{d}})$. For a concrete example, see Wynne’s paper “Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness”. - Given this context, I have actually contemplated a variable $\rho$ in a BO setting. However, one common challenge is the lack of well-defined constraints on the upper limit of $\rho$. This is where this paper provides a unique perspective, by deriving a two-term upper bound that relies on $\rho$ and then equating the two. Consequently, **I acknowledge the paper's contribution** in clarifying a possible optimal value of $\rho$. - However, I have the following question that hope the authors can answer: Since the regret improvement relies heavily on treating $\rho$ as a variable, specifically $\rho = T^{\frac{d}{2\nu+2d}}$ for Matern kernel. I'm actually surprised to see that no order notation is included here, since the resulting $\rho$ would be excessively large either for theory or practice (and can grow with $T$...). For example, if we set $T=1000$, $\nu=1.5$, $d=3$, we will get $\rho=10$. As far as my understanding goes, GP-based algorithms would stop working if we ever set the regularization parameter to beyond, say $0.1$ or so. As a counterexample to the BQ case I gave earlier, letting $\rho = \Theta(1000^{-1.5/3})\approx c*0.03$ appears to be much more reasonable. - So, if your theory indicates that a larger $\rho$ can lead to a better regret bound, it would be interesting to see this experimentally. Or is this because there is a mistake of not using $\rho=\Theta(T^{\frac{1}{1+\beta}})$? In that case, you should indicate that the implied constant has to be polynomially small for the algorithm to actually work. - Conducting comprehensive experiments to support the theoretical finding in Theorem 2, which suggests that a larger value of $\rho$ results in an improved convergence rate. , which I believe any of these three can’t be done properly without another reviewing process.
We thank the reviewer for their positive and constructive feedback. *1. While the idea behind the second point is intriguing, regrettably, I would only be able to recommend the acceptance of this paper if: A significant amount of rewriting of the full paper.* The paper has been rewritten to properly attribute the existing result, focusing on presenting just the regret bound as a contribution. We believe that this contribution on its own is significant enough to warrant an acceptance due to solving a long-standing multi-armed bandit problem, which is of significant importance in the theoretical ML community. *2. A deeper discussion/exploration of varying $\rho$ with $T$. See the details below:* We emphasize that our paper provides regret guarantees, which are typically provided up to absolute constants (i.e. constants independent of the time horizon $T$). Thus, to demonstrate the regret bound, it suffices to provide just a single, valid regularization parameter. In fact, taking $\rho = \Theta(T^{d/(2d + 2\nu)})$ will provide exactly the same regret guarantee. We have updated our manuscript to reflect the fact that *any* choice of $\rho$ proportional to chosen regularization parameter will be valid. Moreover, in terms of the earlier-provided counterexample of Wynne, the regularization parameters $\lambda_T$ chosen in the kernel least-squares objective (which the reviewer mentions are of the form $\lambda_T = O(T^{-p})$ for some power $p$) seem to be chosen with respect the normalized objective function $\frac{1}{T}\sum_{i = 1}^T (g(x_i) - y_i)^2 + \lambda_T \|g\|^2$, whereas the least-squares objective function used for the construction of our kernel ridge estimators is of the form $\sum_{i = 1}^T (g(x_i) - y_i)^2 + \lambda_T \| g\|^2$. Regularization parameters in the first objective can be mapped to parameters in the second objective via multiplying by $T$. Correspondingly, dividing our regularization parameter by the time-horizon $T$ would result in a parameter for the normalized objective function. Thus, due to the difference in the normalization of the objective function, we don’t see it as an issue that $\rho$ is chosen in direct proportion to (as opposed to inversely proportional to) the time horizon $T$. *3. Conducting comprehensive experiments to support the theoretical finding in Theorem, which suggests that a larger value of rho results in an improved convergence rate.* We believe that the results presented in this paper are of significant *theoretical* value, and thus we do not intend to include significant experimentation. The validity of the regret bounds follows directly from the validity of the arguments made in the proofs. The reviewer’s concerns about the magnitude of the regularization parameter are addressed in the preceding paragraph.
Response to Rebuttal
Thank you for your response. As mentioned before, I agree that the contribution is novel and technique of trading off regularization with effective dimension is indeed neat. After reading the other reviewer comments, I feel that my estimate of the relevance to the NeurIPS community might have been misplaced. At the same time, based on the comments by Reviewer x2D4 (and certain references that I was unaware of) and the follow-up discussion, I feel that a major revision of the paper would better serve both the authors and the community. As a result, I would like to keep my score. I do encourage the authors to resubmit as this paper has interesting results and seems to be relevant to community (definitely more so than I initially estimated).
*1. Thank you for your response. As mentioned before, I agree that the contribution is novel and technique of trading off regularization with effective dimension is indeed neat. After reading the other reviewer comments, I feel that my estimate of the relevance to the NeurIPS community might have been misplaced. At the same time, based on the comments by Reviewer x2D4 (and certain references that I was unaware of) and the follow-up discussion, I feel that a major revision of the paper would better serve both the authors and the community. As a result, I would like to keep my score. I do encourage the authors to resubmit as this paper has interesting results and seems to be relevant to community (definitely more so than I initially estimated).* We thank the reviewer for their follow up to our rebuttal, and agree that the result is relevant to the Neurips community. We have fully revised the manuscript to reflect the promised changes, but respect the reviewer’s choice to maintain their initial score.
Decision
Accept (poster)