On the Sublinear Regret of GP-UCB
Authors: Justin Whitehouse
Aaditya Ramdas
Steven Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: Kernel Bandits
Online Learning
Self-Normalized Concentration
Online Regression

Abstract: 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 Matern 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 Matern 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.

On the Sublinear Regret of GP-UCB
Justin Whitehouse Carnegie Mellon University jwhi jwhitehooandrew. umu.edu.
Zhiwei Steven Wu
Carnegie Mellon University
zstevensu@cmu.c edu
Aaditya Ramdas
Carnegie Mellon University aramdas@cmu. edu
Abstract
In the kernelized bandit problem, a learner aims to sequentially compute the op- timum of function lying reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims min- imize regret, which measure of the suboptimality of the choices made. Ar- guably the most popular algorithm is the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm, which involves acting based on simple linear es- timator 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 the Matérn kernel. This has led to longstanding open ques- tion: 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érn kernel, improving over the state-of-ther theth-rrt art analyses and partially resolving COLT open problem posed by Vakili al. Our improvements rely on 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 re- sult in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide tighter analysis of the GP-UCB algorithm.
Introduction
An essential problem in areas such as econometrics [12, 13), medicine [22, 23], optimal control [4, 3], and advertising [21] to optimize an unknown function given bandit feedback, in which algorithms only get to observe the outcomes for the chosen actions. Due to the bandit feedback, there is fundamental tradeoff between exploiting what has been observed about the local behavior of the function and exploring to learn more about the function's 's global behavior. There has been long line of work on bandit learning that investigates this tradeoff across different settings, including multi-armed bandits [29, 19, 37], linear bandits [2, 30], and kernelized bandits [5, 26, 32).
In this work, foeus the kernelized bandit framework, which be viewed of the well-studied linear bandit setting to an infinite-dimensionall reproducing kernel Hilbert space (or RKHS) (H, (:, -))). In this problem, there is some unknown function f" X - IR. of bounded norm in H. where X' C IRd is bounded set. In each round f E [7'] the learner uses previous observations to select an action X, E X, and then observes feedback Y := (X,) ct. where 6; is mean noise variable. The learner aims to minimize (with high probability) the regret at time
extension
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

T, which is defined as
T R ((())
where x" := arg m (*) The goal is to develop simple, efficient algorithms for the kernel- ized bandit problem that minimize regret Ry. We make the following standard assumption. We also make assumptions on the underlying kernel k, which we discuss in Section 2.
Assumption 1. We assume that (a) there some constant > known to the learner such that || S D and (b) for every 2 1, is o-subGaussian conditioned on a (Y1a-1,, X1a))
Arguably the simplest algorithm for the kernelized bandit problem is GP-UCB (Gaussian process upper confidence bound) [31, 5]. GP-UCB works by maintaining kernel ridge regression estima- tor of the unknown function f alongside a confidence ellipsoid. optimistically selecting in each round the action that provides the maximal payoff over all feasible functions. Not only is GP-UCB efficiently computable thanks to the kernel trick, but it also offers strong empirical guarantees [5]. The only seeming deficit of GP-UCB is its regret guarantee, existing analyses only show that, with high probability, RT VT). where "r is a kemelldeependnt measure of complexity known as the maximum information gain [31. 6]. In contrast, more complicated, less computation- ally efficient algorithms such as SupKernelUCB [34, 25] have been shown obtain regret bounds of Ö(VrrT), improving over the amalysis of GP-UCB by a multiplicatiie factor of VTT. This gap is stark as the bound Ö TT) fails, in general, to be sub-linear for the practically relevant Matérn kernel, whereas T(VrrT) is sublinear for any kernel experiencing polynomial eigendecay [32].
This discrepancy has prompted the development of many variants of GP-UCB that, while less com- putationally efficient, offer better regret guarantees in some situations [17, 27, 28]. (See detailed discussion of these algorithms along with other related work in Appendix A.) However, the fol- lowing question remains an open problem in online learning [33]: are existing analyses of vanilla GP-UCB tight, or can an improved analysis show GP-UCB enjoys sublinear regret?
1.1 Contributions
In this work, show that GP-UCB obtains almost optimal, sublinear regret for any kernel experi- encing polynomial eigendecay. This, in particular, implies that GP-UCB obtains sublinear regret for the commonly used Matérn family of kernels. We provide brief roadmap of our paper below.
1. In Section 3, we provide background into self-normalizer concentration in Hilbert spaces. In particular, in Theorem 1, we provide an independent, simplified derivation of a bound due to Abbasi- cess in separable Hilbert spaces. This bound has been largely overlooked in the kernel bandit literature, ther kernel-based learning problems. As opposed to the existing bound of Chowdhury and Gopalan [5], which involves employing complicated "double mixture" argument, the bound we present follows directly from applying the well-studied finite-dimensional method of mixtures alongside simple truncation argument [7-9, 2]. These bounds clean and show simple dependence on the regularization parameter.
[1]. which concerns to self-normalized concentration of certain pro-
draw attention to it in hopes it can be leveraged in solving fur-
2. In Section 4, we use leverage the self-normalized concentration detailed Theorem to provide improved regret analysis for GP-UCB, By carefully choosing regularization parameters based on the smoothness of the underlying kernel, we demonstrate that GP-
UCB enjoys sublinear regret of Ô [ 3+
2422
for any kernel experiencing (C,,))-olynomii
eigendecay. As a special case of this result, we obtain regret bounds of Ō ( 2-122 for
the commonly used Matérn kernel with smoothness in dimension d. Our new analysis improves over existing sfate-of-the-art analysis for GP-UCB, which fails to guarantee sub- linear regret in general for the Matérn kernel family [5], and thus partially resolves an open problem posed by [33] on the suboptimality of GP-UCB
In sum, our results show that GP-UCB, the go-to algorithm for the kernelized bandit problem, nearly optimal, coming close to the algorithm-independde lower bounds of Scarlett et al. [25]. Our

---

work thus can be seen as providing theoretical justification for the strong empirical performance of GP-UCB [31]. Perhaps the most important message of our work is the importance of careful regularization in online learning problems. While many existing bandit works treat the regularization parameter as small, kernel-independent constant, we are able to obtain significant improvements by carefully selecting the regularization parameter. We hope our work will encourage others to pay close attention to the selection of regularization parameters in future works.
Background and Problem Statement
Notation. We briefly touch on basic definitions and notational conveniences that will be used throughout our work. 01,... ar E R. we d1 == (a1....,..) at) Let (H, (ss:)) be a re- producing kernel Hilbert space associated with a kernel k X X' + R. We refer to the identity operator on H as id This is distinct from the identity mapping on IR which we will refer to as la. For elements fig E H, we define their outer product as fg := fg, -) and inner product as 9 = (f. H. For any t 2 1 and sequence of points FI,...,22 Lt E X' (which will typically be understood from context), let 4, := (k(-,z1),.. k(-, x4)) We can respectively define the Gram matrix Kg R' + R' and covariance operator Vi : H - H as K, ==
= Φ & d. These two operators essentially encode the same information about the observed data points, the former being easier to work with when actually per- forming computations (by use of the well known kernel trick) and latter being easier to algebraically manipulate.
and 1 == Σ == ((,, (,))((,,z))) xz)
Suppose A H - H is Hermitian operator of finite rank; enumerate its non-zero eigenvalues as (A), ........... >x (A). We can define the Fredholm determinant of T+ A as det (T + A) = - + (A)) [20]. For any t 2 p > 0, and 21...., 34 E X, one can check via a straightforward det(idæ + p-)),, where K₁ and Vi are the Gram matrix and covariance operator defined above. We, again, will use these two quantities interchangeably in the sequel, but will typically prefer the latter in our proofs.
computation that det + K,)
If (H, {ss ()) is a (now general) separable Hilbert space and (pn))21 is an orthonormal basis for H, for any N 2 1
define the orthogonal projection operator NN H - span(f1,,.. (NN) C H by f = Em= (n) We can correspondingly the define the projection onto the re- maining basis functions to be the map π H -> span ,.,,.... N given by N := f= f. Lastly, if A: И - H is a symmetric, bounded linear operator, we let Amax(() denote the maximal eigenvalue of A, when such value exists. In particular, Amax (A) will exist whenever has a finite rank, as will typically be the case considered in this paper.
Basics on RKHSs. Let X C Rd be some domain. A kernel is a positive semidefinite map k X' x X + R that is square inttre-it,egrabee i.e Sx Sxx [k(2, y)l < co. Any kernel l has an associated reproducing kernel Hilbert space or RKHS (H, (;-) (1) containing the closed span of all partial kernel evaluations k(,,,), x E X. In partieular, the inner product (s-) и on H satisfies the reproducing relationship f(x) = (f, x)) h for all x E X.
A kernel & can be associated with corresponding Silberr-Schhidl operator, which is the Hermitian operator T : (²(X)) + (2(x)) given by (Tx))(x) == fx f())k(x, y)dy for any x E X. In short, Th can be thought of "smoothing out" or "mollifying" function f according to the similarity metric induced by k. Ta plays a key role in kernelized learning through Mercer's 's Theorem, which gives explicit representation for H in terms of the eigenvalues and eigenfunctions of Tu-
Fact 1 (Mercer's Theorem). Let (H, ()) be the RKHS associated with kernel k, and let (nn)n21 and (#n)n2) be the sequence of non-increasing eigenvalues and corresponding eigen- functions for Tg. Let (Pw)221 be the sequence of rescaled functions &n == vP, &n- Then,
Onpn ESh<
n=1
and (ff))221 forms an orthonormal basis for (H, (.)
We make the following assumption throughout the remainder of our work, which standard and comes from Vakili et al. [32].
3

---

Assumption 2 (Assumption on kernel k). The kernel k: X x & - R satisfies (a) [k(z, v) - L for all x, y E X, for some constant and (b) O (z) S B for all X. for some B
"Complexity" of RKHS's. By the eigendecay of a kernel k we really mean the rate of decay of the sequence of eigenvalues (f4))211 In the literature, there are two common paradigms for studying the eigendecay of k: (C1. C2. C2,3)eexeeeeeeee eexxonennttt eigendecay, under which vn 2 1. Mn I C exp(-C2n²) and (C, -ppolyoolml eigendecay, under which Vn 2 1, S Cn- For ker- nels experiencing exponential eigendecay, of which the squared exponential is the most important example, GP-UCB is known to be optimal up to poly-logarithmic factors. However, for kernels experiencing polynomial eigendecay, of which the Matérn family common example, existing analyses of GP-UCB fail to yield sublinear regret. It is this latter case we focus on in this work.
Given the above representation in Fact 1, it is clear that the eigendecay of the kernel & governs the "complexity" or "size" the RKHS H. We make this notion of complexity precise by discussing maximum information gain, a sequential, kermel-dependent quantity governing concentration and hardness of learning in RKHS's [6, 31, 32].
Let / 2 1 and p > 0 be arbitrary. The maximum information gain at time / with regularization the scalar (p) given by
1 log det (id + VV) = sup 3. 2.
rel)) == sup
log det p
21 2 xx 2
Our presentation of maximum information gain differs from some previous works in that we encode the regularization parameter p into notation. This inclusion is key for our results, improvements by carefully selecting p. Vakili et al. [32] bound the rate growth of (p(p) in terms of the rate of eigendecay of the kernel k. We leverage the following fact in main results.
obtain
Fact 2 (Corollary 1 in Vakili et al. [32]). Suppose that kernel k satisfies Assumption 2 and experi- ences (C, 3)-polynomial eigendecay. Then, for any t I, we have
Te(p)= -
CB
log 1/3
1
Lt p
+1
+1
log 1
Lt p
We last define the practically relevant Matérn kernel and discuss its eigendecay. Definition/Fact 3. The Matérn kernel with bandwidth a >> and smoothness v > 1/2 is given by
1
22 x yll2
/2vl1z y/l2
Ku, (x, v)
B.
((w)2K-1
where I is the gamma function and B, is the modified Bessel function of the second kind. It is known that there some constant >> that may depend on but not on d or v such that kano experiences (C, _ eigenddecay [24, 32].
filtration (Fr)zz is sequence of a-algebras satisfying F, C Fet1 for all 2 1. If (M))2o is H-valued process, we say (Mr) is martingale with respect (Fi)ezo if (a) (M) (Fd)s2o-ddapted and (b) E(M, Fi-1) M,-1 for all t 2 1. An R-valued process is called supermartingale if the equality in (b) is replaced with "s", i.. supermartingales tend decrease. Martingales are useful in many statistical applications due to their strong concentration of measure properties [15, 36). The follow fact can be leveraged to provide time-uniform bounds on the growth of any non-negative supermartingale.
Basics martingale concentration:
Fact 4 (Ville's Inequality). Let (Me)r20 be non-negative supermartingale with respect some filtration. Suppose EMM- = 1. Then, for any E (0, 1), we have
0 Mr 1)) So.
IP
31
See Howard et [14] for self-contained proof of Ville's inequality, and many applications. If F is a o-algebra, and is an R-valued random variable, we say is o-subGaussian conditioned on FF if, for any X E. have log E (e F) X² in particular this condition implies

---

that e is mean zero. With this, we state the following result on self-normalized processes. To our understanding, the following result was first presented in some form as Example 4.2 of de la Peña et al. [8] (in the setting of continuous local martingales), and can be derived leveraging the argument of Theorem I in de la Peña et al. [9]. The exact form below was established (in the setting of discrete-time processes) in Theorem of Abbasi- Yadkori et al. [2], which is commonly leveraged to construct confidence ellipsoids in the linear bandit setting.
Fact 5 (Example 4.2 from [8], Theorem from [2]). Let (Fi)ezo be filtration, let (Xt)e21 be an (Fe))zo 2 sequence in R. and let (G)))2 be a real-valued -addptted sequence such that conditional on Ft-1, Ct is mean zero and o-subGaussian. Then, for any p O, the process (M))oo given by
{ M dee (Ta + + exp 1 (Cla Vo)- ( {3]
is non-negative supermartingale with respect to (Fi)ezo, where St == C.=nteX, and V, == E. X.X. Consequently, by Fact 4, for any confidence probability at least - 8, simultaneously for all t 2 1, we have
(0, 1), the following holds: with
( + pla) pla)
1/25: 1/2 S S 2og
det(la + +
Note the simple dependence the regularization parameter p 0 in the above bound. While the regularization parameter p doesn't prove important in regret analysis for linear bandits (where is treated constant), the choice for p will be critical in our setting. In the following section, we will discuss how Fact can be extended to the setting of separable Hilbert spaces essentially verbatim (an observation first noticed by Abbasi- Yadkori [1]).
3 A Remark on Self-Normalized Concentration in Hillbert Spaces
We begin by discussing a key, self-normalized concentration inequality for martingales. We use this bound in the sequel to construct simpler, more flexible confidence ellipsoids than currently exist for GP-UCB. The bound we present (in Theorem 1 below) is, more or less, equivalent to Corollary 3.5 in the thesis of Abbasi- Yadkori [1]. Our result is mildly more general in the sense that it directly argues that a target mixture process is nonnegative supermartingale. The result in Abbasi- Yadkori [1] is more general in the sense it allows the regularization (or shift) matrix to be non-diagonal. Either concentration result sufficient for the regret bounds obtained in the sequel.
The aforementioned corollary in [1], quite surprisingly, has not been referenced in central works on the kernelized bandit problem, namely Chowdhury and Gopalan [5] and Vakili et al. [32, 33). In fact, strictly weaker versions of the conclusion have been independently rediscovered in the context of kernel regression [10]. We emphasize that this result of Abbasi- Yadkori [1] (and the surrounding technical conclusions) are very general and may allow for further improvements in problems related to kernelized learning.
We now present Theorem 1, providing a brief sketch and full proof in Appendix B. We believe our proof, which directly shows a target process nonnegative supermartingale, is of independent interest when compared to that of Abbasi- Yadkori [1] due to its simplicity. In particular, our proof follows from first principles, avoiding advanced topological notions of convergence (e.g. in the weak operator topology) and existence of certain Gaussian measures on separable Hilbert spaces, which were heavily utilized in the proof of Corollary 3.5 in Abbasi-Yadkori [1].
Theorem 1 norma-zor concentration in Hilbert spaces). Let (Fi)120 be a filtration, (f()z1 be an preredittie sequence in a separable Hilbert space' H such that [|fx и < oo a.s. for all t > O, and (cx)121 be -adapted sequence in IR such that conditioned F,-1, is mean zero and o-subGaussian. Defining S, = CsIs and V -' Sale, have that for any p > O, the process (M)) defined by
ded + IV,) exp {1 (pid + V.) 112- -
M,
A space is separable if it has countable, dense set. countable basis, whose first N elements project onto.
Separability is key. because it means we have
5

---

is nonnegative supermartingale with respect to (Fi)ezo. Consequently, by Fact 4, for any å E (0, 1), with probability at least 6, simultaneously for all 1, we have
(vV + pIa) 2 / log ( (Vetttid p-vvi)
We can summarize our independent proof in two simple steps. First, following from Fact 5, the bound in Theorem holds when we project S; and Vi onto finite number N of coordinates, defining a "truncated" nonnegative supermartingale M, Secondly, we can make a limiting arugment, showing (N) is "essentially" M, for large values of N.
Proof Sketch for Theorem I. Let (pn)n21 be orthonormal basis for H, and, for any N > 1, let N denote the projection operator onto H == spanff)..... (t)25 is an H-valued martingale with respect to (Fi)120- Further, note that the projected variance process (I V satísfies
Note that the projected process
NN VIT ((NNS)(NNTA.
Since, for any N 2 1, H a finite-dimensional Hilbert space, it follows from Lemma 1 that the process (M,
(N) (M) Je20 given by
M
(pid + AN V AN (.r
exp
2
V det(idd + p- I V
nonnegative supermartingale with respect to (Fi) One check that, for any 2 0.
M (N)
N + M, Thus, Fatou's Lemma implies
E (M, Ft-1) = inf M(N) |F
N-000
S lim inf E (M (N)
1F
S lim inf M(
Mr-1
which proves the first part of the claim. The second part of the claim follows from applying Fact to the defined nonnegative supermartingale and rearranging. See Appendix B for details.
The following corollary specializes Theorem (and thus Corollary 3.5 of Abbasi-Yadkori the case where H a RKHS and ft = k(- Xt), for all 2 1. this special case, we can reframe the above theorem in terms familiar Gram matrix K,, assuming the quantity is invertible. While we prefer the simplicity and elegance of working directly in the RKHS H the sequel, the follow corollary allows to present Theorem in way that is computationally tractable.
Yadkori [1]) to
Corollary 1. Let assume the same setup Theorem 1, and additionally assume that (a) (H, (v)) is a RKHS associated with some kernel i, and (b) there some X-valued (Fr)ezo- predictable process (Xt)121 such that (ft) = (K(-, X1))21 Then, for any p 0 and 8 (0, we have that, with probability at least 8, simultaneously for all t 0.
[(v + pid -1/2
(0((((+(1KKK)) + p-1 (V)
S 1
2 2
If. in addition, the Gram matrix K; (k(X, ,, X jejj is invertible, have the equality
11(4, pK, 1 $ ||2 [p + v.) 1/)

---

We prove Corollary 1 in Appendix B. With this reframing of Theorem 1, we compare the concen- tration results of Theorem (and thus Abbasi- Yadkori [1]) to the following, commonly leveraged result from Chowdhury and Gopalan [5].
Fact 6 (Theorem from Chowdhury and Gopalan [5]), Assume the same setup as Fact 5. Let lj > O be arbitrary, and let K₁ == (K(X,, je) be the Gram matrix corresponding to observations made by time t 2 L. Then, with probability at least 1 8, simultaneously for all t 2 L, we have
[[CK + + 1.) 1/2
(
[ det ((1+ +1 K.)
2 2 E1st S 1
To make comparison with this bound clear, we parameterize the bounds in the above fact in terms of 7 0 instead of p >> 0 to emphasize the following difference: both sides of the bound presented in Theorem 1 shrink as p is increased, whereas both sides of the bound in Fact increase as 1) grows. Thus, increasing p in Theorem I should be seen decreasing 7) in the bound of Chowdhury and Gopalan [5]. The bounds in Corollary and Fact 6 coincide when - = and 7j 4 (per Lemma in Chowdhury and Gopalan [5]), but are otherwise not equivalent for other choices of p and 17.
We believe Theorem 1 and Corollary 3.5 of Abbasi-Yadkori [1] to be signficantly more usable than the result of Chowdhury and Gopalan [5] for several reasons. First, the aforementioned bounds directly extend the method of mixtures (in particular, Fact 5) to potentially infinite-dimensional Hilbert spaces. This similarity in form allows us to leverage existing analysis of Abbasi- Yadkori et al. [2] to prove our regret bounds, with only slight modifications. This is in contrast to the more cumbersome regret analysis that leverages Fact 6, which is not only more difficult to follow, but also obtains inferior, sometimes super-linear regret guarantees.
Second, we note that Theorem 1 provides a bound that has simple dependence on P > 0. In more detail, directly as a byproduct of the simplified bounds, Theorem 2 offers a regret bound that can readily be tuned in terms of p. Due to their use of "double mixture" technique in proving Fact 6, Chowdhury and Gopalan [5] essentially wind up with a nested, doubly-regularized matrix ((K++ + 174,) + 1,) -1/2 with which they normalize the residuals f1:t. In particular, this more complicated normalization make it difficult to understand how varying 17 impacts regret guarantees, which we find to be essential for proving improved regret guarantees.
We note that the central bound discussed in this section does not provide an improvement in depen- dence maximum information gain in the sense hypothesized by Vakili et al. [33]. In particular, the authors hypothesized the possibility of shaving a VTT multiplicative factor off of self-normalized concentration inequalities in RKHS's. This was shown in a recent work (see Lattimore [18) to be impossible in general. Instead, Theorem I and Corollary 3.5 of Abbasi Yadkori [1] give one access Abbasi-Yadkori to family of bounds parameterized by the regularization parameter p > As will be seen in the sequel, by optimizing over this parameter, one can obtain significant improvements in regret.
4 An Improved Regret Analysis of GP-UCB
In this section, we provide the second of our main contributions, which is an improved regret analysis for the GP-UCB algorithm. We provide description of GP-UCB in Algorithm 1. While state the algorithm directly in terms of quantities in the RKHS H, these quantities can be readily converted to those involving Gram matrices Gaussian processes for those who prefer that perspective [5, 38).
As seen in Section 3, by carefully extending the "method of mixtures" technique (originally by Robbins) of Yobasi-Yadkon et al. [2], Yadkori [1] and de la Peña et al. [7, 8] to Hilbert spaces, we can construct self-normalized concentration inequalities that have simple dependence on the regularization parameter p. These simplified bounds, in conjunction with information about the eigendecay of the kernel & [32], can be combined to carefully choose p to obtain improved regret. We now present our main result.
Theorem 2. Let T > 0 be fixed time horizon, p > 0 a regularization parameter, and assume Assumptions& and hold. Let 8 E (0, 1), and for 2 1 define
U. = 2 2
det(idy + +p-11)) + 1/D/DD
8
7

---

Algorithm Gaussian Process Upper Confidence Bound (GP-UCB)
Input: Regularization parameter p 0, norm bound D, confidence bounds (Ut)21, and time
horizon T.
Set Vo 0, fu = 0, Eu {f H 1lfll S D}
for = 1,.... do
Let (Xe, fi) arg max (f, (a.kk(()))))) xx)))
Play action Xx and observe reward Y = (Xx) +
Set Vi == Vi-1 + kl:, x,) and ft (V: + pidæ) - Y1:t
Set & = { H ([( + pidи)
( (2
fl S Uz}
Then, with probability at least the regret of Algorithm run with parameters p. (U1) satisfies
R1 = 0 VpYr(p)T)
where in the big-Oh notation above we treat D, o, B, and being held constant. If the kernel experiences (C, (C.3))polyeel B)--polmoomiill eigendecay for some C > 0 and B > 1, taking (T yields
RT Ō 2128
which is always sub-linear in T.
While we present the above bound with a fixed fime-horizon, it can be made anytime by carefully applying standard doubling argument (see Lattimore and Szepesvári [19], for instance). We spe- cialize the above theorem to the case of the Matérn kernel in the following corollary.
Corollary 2. Definition 3 states that the Matérn kernel with smoothness > 1/2 in dimension d
experiences (C, 2y+d
eigendecay, for some constnat C > 0. Thus, GP-UCB obtains a regret rate
of RT = 204-22
We note that regret analysis is the first show that GP-UCB attains sublinear regret for general kernels experiencing polynomial eigendecay. Of particular import that Corollary 2 of Theorem yields the first analysis of GP-UCB that implies sublinear regret for the Matérn kernel under general settings of ambient dimension and smoothness v. recent result by Janz [16], using a uniform lengthscale argument, demonstrates that GP-UCB obtains sublinear regret for the specific case of the Matérn family when the parameter v and dimension satisfy a uniform boundedness condition independent of scale. Our results are (a) more general, holding for any kernel exhibiting polynomial eigendecay, (b) don't 't require checking uniform boundedness independent of scale condition, and (c) follow from simple regularization based argument. In particular, the arguments of Janz [16] require advanced functional analytic and Fourier analytic machinery.
We note that our analysis does not obtain optimal regret, as the theoretically interesting but computa- tionally cumbersome SupKemneUCCB algorithm [25, 34] obtains a slightly improved regret bound of
T 23
for (C, (C.3))poolyomiill eigendecay and Ô ( (22244 for the Matérn kernel with smooth-
ness v in dimension d. Due to the aforementioned result of Lattimore [18], which shows that im- proved dependence on maximum information gain cannot generally obtained Hilbert space concentration, we believe further improvements regret analysis for GP-UCB may not possible.
To wrap up this section, we provide a proof sketch for Theorem The entire proof, along with full statements and proofs of the technical lemmas, can be found in Appendix C.
Proof Sketch for Theorem 2. Letting, for any t E [T], the "Instantaneous regret" be defined as T: = fx""))) (X,), a standard argument yields that, with probability at least 8, simultane- ously for all E [T).
Tt 20-11 (nider V2-1) 1/2k(,
"The notation Ô suppresses multiplicative, poly-logari factors in 2'

---

when & experiences (CC.3)-ollynomic eigendecay, and regret Ô (T 22 for the A further standard argument using Cauchy-Schwand and an elliptical potential argument yields
T
RT =
r I UT 27 log ded + Vv-)
1=1
/ log / delelidd 1-) + /1/2 22 + Vr)
1
(loggg()) a (p) + /2/2 V4Trr(0) o (pr(p)VT+ pTT())T)
which proves the first part of the claim. If, additionally, h experiences (C, 3) polynomial eigende-
1/8
cay, we know that 7r (p) Ö
I
by Fact 2. Setting = O(T thus yields
(rr(D)VT+ O
Ry = O
t V = (1zize)
proving the second part of the claim.
5 Conclusion
In this work, we present improved analysis for the GP-UCB algorithm in the kernelized ban- dit problem. We provide the first analysis showing that GP-UCB obtains sublinear regret when the underlying kernel l experiences polynomial eigendecay, which in particular implies sublinear regret rates for the practically relevant Matérn kernel. In particular, we show GP-UCB obtains re-
gret Ō
T 2123
142d
Matérn kernel with smoothness in dimension d.
Our contributions are twofold. First, we show the importance of finding the "right" concentration inequality for tackling problems in online learning in this case the correct bound being a self- normalized inequality originally due to Abbasi-Yadkori
[1]. We provide an independent proof of a result equivalent to Corollary 3.5 of Abbasi Yadkori [1] in Theorem 1, and hope that our simplified, truncation-base analysis will make the result more accessible to researchers working on problems in kernelized learning. Second, we demonstrate the importance of regularization in the kernelized bandit problem. In particular, since the smoothness of the kernel governs the hardness of learning, by regularizing in proportion to the rate of cigendecay of k, one can obtain significantly improved regret bounds.
Abbasi-Yadkori
A shortcoming of our work is that, despite obtaining the first generally sublinear regret bounds for GP-UCB, our rates are not optimal. In particular, there are discretization-bant based algorithms, such as
SupKemelUUCB [34], which obtain slightly better regret bounds of Ô ( 1+2 " for (C, polyynnmlla
eigendecay. We hypothesize that the vanilla GP-UCB algorithm, which involves constructing confi- dence ellipsoids directly in the RKHS H. cannot obtain this rate.
The common line of reasoning [33] is that because the Lin-UCB (the equivalent algorithm in Rd) obtains the optimal regret rate of ((dVT) in the linear bandit problem setting, then GP-UCB should attain optimal regret well. In the linear bandit setting, there is subtlety between estimating the optimal action and unknown slope vector, as these are one and the same. In the kernel bandit setting, estimating the function and optimal action are not equivalent tasks. In particular, the former serves in essence as nuisance parameter in estimating the latter: tight estimation of unknown function under the Hilbert space norm implies tight estimation of the optimal action, but not the other way around. Existing optimal algorithms are successful because they discretize the input domain, which has finite metric dimension [26]. and make no attempts to estimate the unknown function RKHS norm. Since compact sets in RKHS's do not, in general, have finite metric dimension [35], this makes estimation of the unknown function a strictly more difficult task. In fact, recent work by Lattimore [18] demonstrate that self- nermanoora concentration in RKHS's, in general, cannot exhibit improved dependence on maximum information gain. This further supports our hypothesis on the further unimprovability of the regret analysis of GP-UCB past the improvements made in this paper.

---

Acknowledgements
AR acknowledges support from NSF DMS-23107IS and NSF IIS-2229881. ZSW and JW were supported in part by the NSF CNS2120667, a CyLab 2021 grant, a Google Faculty Research Award, and Mozilla Research Grant. JW also acknowledges support from NSF GRFP grants DGE1745016 and DGE21 140739.
We also would like to thank Xingyu Zhou and Johannes Kirschner for independently bringing to our attention the result from Abbasi- Yadkori [1] (Corollary 3.5) on self-normalized concentration in Hilbert spaces which is essentially equivalent Theorem We have rewritten the paper in way that emphasizes the importance of this result and provides proper attribution to the original author.
References
[1] Yasin Abbasi Yadkori. Online learning for linearly parametrized control problems. 2013.
[2] Yasin stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear
[3] Rajeev Agrawal. The continuum-armed bandit problem. SIAM Journal on Control and Opti- mization, 3366)19266-1951, 1995.
[4] Andrew G Barto. Reinforcement learning control. Current Opinion in Neurobiology, 4(6): 888-893, 1994.
[5] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armes bandits. Interna- tional Conference Machine Learning, pages 844-853, PMLR, 2017.
[6] Thomas M Cover and Joy A Thomas. Information theory and statistics. Elements of Informa- tion Theory, 1(1):279-335, 1991.
[7] Victor de la Peña, Michael Klass, and Tze Leung Lai. Self-normalized processes: Exponen- tial inequalities, moment bounds and iterated logarithm laws. The Annals of Probability, 32, 07 2004. doi: 10. 10.1214/009 17904000000397.
[8] Victor de la Peña, Michael J Klass, and Tze Leung Lai. Dexudomaximizztton and self- normalized processes. Probability Surveys Vol, 4:172-192, 09 2007. doi: 10.1214/07-PSI19
(9] Victor de la Peña, Michael J Klass, and Tze Leung Lai. Theory and applications of multi- variate normalzedd processes. Stochastic Processex and their Applications, 119(1 2):4210- 4227, 2009.
[10] Audrey Durand, Adblric-Ambrym Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. The Journal of Machine Learning Research, 19(1)650-663) 0835000683.200 2018.
[11] Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
[12] Vivek Farias, Ciamac Moallemi, Tianyi Peng, and Andrew Zheng. Synthetically controlled bandits. arXiv preprint arXiv:2202.000779 2022.
[13] Matthew Hoffman, Eric Brochu, and Nando De Freitas. Portfolio allocation for Bayesian optimization. In UAL, pages 327-336, 2011.
[14] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform Cher- noff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
[15] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, non- parametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2), 2021.
[16] David Janz. Sequential decision making with feature-linear models. PhD thesis, 2022.
[17] David Janz, David Burt, and Javier González. Bandit optimisation of functions in the matérn kernel RKHS. In International Conference on Artificial Intelligence and Statistics, pages 2486-2495. PMLR, 2020.
10

---

[18] Tor Lattimore. A lower bound for linear and kernel regression with adaptive covariates. In The Thirty Sixth Annual Conference on Learning Theory, pages 2095-2113. PMLR, 2023.
[19] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[20] Peter D Lax. Functional Analysis, volume 55. John Wiley Sons, 2002.
[21] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bande approach to personalized news article recommendation. In Proceedings of the 19th International Confer- ence World Wide web, pages 661-670, 2010.
[22] Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatible bandit exploration. Operations Research, 68(4): 132- 11611111,1100 2020.
[23] Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health intervention. Advances in Neural Information Processing Systems, 33:15639-15650, 2020.
[24] Gabriele Santin and Robert Schaback. Approximation of eigenfunctions in kernel-based spaces. Advances in Computational Mathematics, (2(4):9339993 2016.
[25] Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Conference on Leurning Theory, pages 1723-1742.
PMIR, 2017.
[26] Shubhanshu Shekhar and Tara Javidi. Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics, 12(2):3829 - 3874, 2018.
[27] Shubhanshu Shekhar and Tara Javidi. Multi-scale vedo- optimization of smooth functions in an RKHS. 2022 IEEE International Symposium on Information Theory (ISIT), pages 288-
293, 2020.
[28] Shubhanshu Shekhar and Tara Javidi. Instance dependent regret analysis of kernelized bandits.
In International Conference Machine Learning, pages 19747-19772. PMLR, 2022.
[29] Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 121-2))1-286, 2019.
[30] Marta Soare, Alessandro Lazaric. and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
[31] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. International Confer- ence on Machine Learning. 2009.
[32] Sattar Vakili, Kia Khezeli, and Victor Picheny. information gain and regret bounds in Gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
[33] Sattar Vakili, Jonathan Scarlett, and Tara Javidi. Open problem: Tight online confidence in- tervals for RKHS elements. In Conference on Learning Theory, pages 4647-4652. PMLR, 2021.
[34] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. Proceedings of the 29th Conference Uncertainty in Artificial Intelligence, 2013.
[35] Martin J Wainwright. High-diienssionl Statistics: A Non-asymptotic Viewpoint, volume 48. Cambridge university press, 2019.
[36] Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society, Series B, 2023.
[37] Peter Whittle. Multi- bandits and the Gittins index. Journal of the Royal Statistical Society: Series B (Methodological), 42(2):143- 1980.
[38] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learn- ing, volume 2. MIT press Cambridge, MA, 2006.


Reviews:
[{"review_id": "w4wJ0F1bzz", "reviewer": "Reviewer_J83V", "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.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "NA", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their overall positive reviews."}, {"review_id": "sDTB6wL2l0", "reviewer": "Reviewer_CiaU", "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.", "questions": "In Chowdhurry and Gopalan's paper, what would happen if we set $\\eta$ also as a function of $\\eta$?\nCould 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.\nIs 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?", "limitations": "Limitations are adequately addressed. The paper \"A Lower Bound for Linear and Kernel Regression with Adaptive\nCovariates\" Lattimore COLT 2023 should be mentioned.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "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). \n\n2. 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.\n\n3. 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.\n\n4. The paper is very well written, its clear and has a great flow. It gives good education!\n", "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.\nEffectively, 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.\n\nThe 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. \n\n2.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?\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the overall positive reviews and constructive feedback.\n\n[*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  bound on the regret in the RKHS setting, as we do in the GP setting.*]\n\nWe agree that we do not derive confidence bounds that shave a $\\sqrt{\\gamma_T}$ factor off the existing bounds, but our bounds allow a user to optimize tightness (in terms of a regularization parameter) for a target time horizon. Importantly, we do address the question raised in the abstract of Vakili’s open problem paper of the fact that GP-UCB fails to obtain sublinear regret. We have now clarified our contributions towards resolving the open problem (that of showing improved regret bounds for GP-UCB, but not improving dependence on $sqrt{\\gamma_T}$). \n\n[*2. 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.*]\n\nWe thank the reviewer for this reference. We have added a proper citation and discussion to the COLT’23 paper to address how this resolves the conjecture we posed.\n\n[*3. I should also point out Chowdhurry & Gopalan is not the only result for bounding 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?*]\n\nWe thank the reviewer for this reference, as we were unaware of this reference upon submitting. Upon inspection, the bound presented in Abbasi-Yadkori’s thesis is equivalent to our bound (it is slightly more general in that it allows the shift matrix to not just be $\\rho id_H$, but our result can be readily extended to this setting). We are surprised that this result has not been referenced by existing works in the literature, as it is neither mentioned in the Chowdhury Gopalan paper nor the Vakili paper. In line with reviewer x2D4, we will no longer claim the concentration result as a major contribution (though we will leave it in the paper’s appendix as a self-contained proof in our notation), but our regret analysis of GP-UCB regret bounds remains a novel and significant contribution. We have appropriately revised our work to reference this citation.\n\nIn terms of the difference in proof techniques – our proof is a ground-up proof in the sense that it does not depend on the existence of certain classes of Gaussian measures (Lemmas 3.1 and 3.2) nor on advanced topological notions of convergence (e.g. weak operator topology convergence, Corollary 3.5) – only on elementary functional analytic techniques, like truncation-based arguments. We believe that our proof is more instructive, but we no longer believe it is a major contribution.\n\n[* 4. In Chowdhurry and Gopalan's paper, what would happen if we set also as a function of ? 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 different than them (the simply set it to ) a similar rate as Cor 2 may be obtained?*]\n\nTo the best of our knowledge, the inequality constructed by Chowdhury and Gopalan cannot be used to achieve the same regret guarantee (at least non-trivially). Here is a heuristic justification. Increasing $\\eta$ in the CG bound can be viewed as decreasing $\\rho$ in our bound, with bounds coinciding when $\\eta = 0$ and  $\\rho = 1$, and being not equivalent for other values. We take $\\rho = O(p(T))$, where $p(x) = x^\\beta$ for some $\\beta \\in (0, 1/2)$. Since increasing $\\rho$ in our bounds corresponds to decreasing $\\eta$ in the CG bounds, and $p(T) >> 1$, we would need to select $\\eta < 0$ to obtain a similar level of regularization, which is not permitted in the bound of CG, which stipulates $\\eta > 0$. This is just a heuristic justification, of course, and perhaps with more effort the regret guarantees can be recovered from this bound, but we failed to do so, and in our opinion this is non-trivial and non-obvious. \n"}, {"review_id": "1Moa8RqzYV", "reviewer": "Reviewer_e62U", "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.", "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?", "limitations": "NA", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 4, "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.\n\nThis 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:\n* 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.\n* The extension starts with assuming a finite-dimensional RKHS (with dimension N) and then somehow lets $N\\to\\infty$.\n* 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.\n* 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.\n* 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$.\n* 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$.\n\nOn the other hand, the presentation is not appealing due to:\n* Section 1 lacks intuitions about the tools/ideas to be used, which is essential for a technical paper.\n* Section 2 is too long, and could be significantly reduced either by moving some less-important content to Appendix, or just providing informal results.\n* Some terminologies, like \"double mixture,\" are not explained, leaving readers without clear understanding.\n\nMiscellaneous minor issues:\n* The templates seem to be from NeurIPS 2020, not 2023\n* line 182: \"We can then making...\"\n* Appendix line 471: \"so so\"\n* What is $\\rho \\downarrow 0$?\n* \"Holder\" should be Hölder\n* No formal definition of RKHS norm?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*1. 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.*]\n\nWe believe the simplicity of our arguments are what make the technical contributions significant. For instance, the fact that regularization can be used to greatly improve regret rates is intuitive and follows from stat/ML dogma, but has been largely ignored for this basic problem for over a decade. We show that applying a simple technique can actually make significant improvements on a long open ML problem.\n\n[*2. The extension starts with assuming a finite-dimensional RKHS (with dimension N) and then somehow lets /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. It is confusing to write, as the two RKHS spaces are essentially not the same (finite v.s. infinite), where they are both being denoted by the same./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\nWe formally and rigorously show that such a limiting argument holds in the appendix, including the justification of the existence of all limits. Moreover, such limiting notations are fully justified since they are just concerning the convergence of sequences of scalars (i.e. it is not a problem that the dimensions of the spaces are changing). Due to our use of an analytic limiting argument, there is no need to explicitly bound error terms. We are happy to further discuss any questions with the proofs if the reviewer is not fully convinced, especially if there is a particular step in the proof that the reviewer does not understand or agree with, but barring a concrete objection the reviewer may have, we believe it is unfair to call our proof “spamming”.\n\n[*3. In Appendix, line 461, the statement \"there exists some...\" seems to compress a lot of information. While I understand the existence of such  should be due to eigenvalue decays, such existence should be proven or more thoroughly discussed.*]\n\nThe existence of such $N$ does not depend on eigendecay, but rather on the assumption that the elements being summed (the $f_t$) have finite norm almost surely. We have made this more explicitly clear in the proof/theorem statement.\n\n[*4. Miscellaneous minor issues:*]\n\nWe thank the reviewer for pointing out the miscellaneous issues and have added corrections/clarifications. In particular, the notation $\\rho \\downarrow 0$ means “the limit as $\\rho$ is taken to monotonically decrease towards zero from above”.\n\n[*5. 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.*]\n\nWe provide a brief description of our arguments (improved concentration and using simple regularization) in the contribution section of the paper and provide a high-level, intuitive sketch of our techniques in each of the main result sections (sections 3 and 4). We have now added an additional description of our technique to Section 1 for clarity. We believe the material discussed in Section 2 is essential for understanding our technique, results, and notation used throughout the main body of the paper. We have added a more detailed description of the double mixture technique to aid the reader in their understanding.\n\n[*6. 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?*]\n\nWe believe that our results can equally be applied to GP-TS, and leave it as future work to investigate this result.\n"}, {"review_id": "i1HSJt6v95", "reviewer": "Reviewer_GVZJ", "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.\n", "questions": "see above ", "limitations": "none", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper suggest a new analysis the leads to improved regret bounds for the GP-UCB algorithm. \n\nThe technique used in the paper is based on a novel concentration inequality (Theorem 1) that may be of independent interest.\nIn addition, they demonstrate that the consideration of regularization based on kernel smoothness contribute to the nearly optimal regret rates as well.\n", "weaknesses": "The main weakness is perhaps clarity of presentation that renders the paper less accessible to a non-expert in the field. \n\nFor 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]) \nWhy is it commonly used and what are trade-offs with other kernels? \n\nAlso consider including a table comparing the bounds with previous analysis, similar to Table 1 in [27], that would be helpful as well.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*1. 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?]\n\nThe Matern kernel is used in practice due to its ability to capture and approximate ``rougher’’ functions than the typically used squared exponential kernel. We have added some more intuition to describe this kernel and aid the reader.\n\n[*2. Also consider including a table comparing the bounds with previous analysis, similar to Table 1 in [27], that would be helpful as well.*]\n\nWe did not add a table as there are only three points of comparison for our paper — the previous regret bound for GP-UCB under polynomial eigendecay, our result, and the optimal regret bound. Per this comment we have more explicitly presented the comparison between these results to aid the reader.\n\n"}, {"review_id": "GzHtc0MofB", "reviewer": "Reviewer_x2D4", "summary": "This is a very well written paper with nice, clean results on self-normalised concentration for seperable RKHS. The paper claims two contributions:\n1. A new self-normalised concentration result for seperable RKHSs.\n2. Improving the regret of GP-UCB by tuning the regularisation parameter.\n\n", "questions": "None", "limitations": "None", "rating": 1, "confidence": 5, "soundness": 4, "presentation": 1, "contribution": 1, "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.\n\nThe 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.\n\nA rewrite of this paper that makes clear what is previous work and what is the authors contribution would warrant a strong accept.\n\n[1] Abbasi-Yadkori, Yasin. Online learning for linearly parametrized control problems. Diss. 2013.\n\n[2] Chowdhury, Sayak Ray, and Aditya Gopalan. \"On kernelized multi-armed bandits.\" International Conference on Machine Learning. PMLR, 2017.\n\n[3] Janz, David. Sequential decision making with feature-linear models. Diss. 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*1. 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.*]\n\nWe thank the reviewer for bringing attention to this result, as we were unaware of the thesis upon submitting. Moreover, we are surprised it has not been mentioned in the existing literature (e.g. the Chowdhury/Gopalan paper or Vakili open problem paper on RKHS concentration). Upon inspection, we agree that the mentioned result is essentially equivalent to what we have presented (it seems the result holds under a slightly more general setting in which the shift matrix is non-diagonal and just of trace class, but our argument can be readily extended to this setting as well). While we believe our proof is of independent interest due to its simplicity and lack of reliance on advanced functional analytic results/tools, we believe it is no longer fair to claim this bound as a primary contribution. We still believe our regret bounds are of significant interest due to their improvement over key results in the literature. We have now shifted the structure of our paper to present this as a primary result.  We believe that by downgrading the claimed novelty of the concentration result and focusing on the novel regret guarantees, the paper still deserves to be accepted under the new title of “On the Sublinear Regret of GP-UCB”, with the contribution of the existing bound properly acknowledged.\n\n\n\n[*2. 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 for the Mat'ern kernel); under an additional assumption, which has only been established for a particular choice of (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.*]\n\nWe thank the reviewer for this reference, as the approach used is very interesting. We agree our presented result is more general, more robust to choice of kernel, and the argument is more approachable. We have appropriately added a citation to this thesis and provided a comparison in the main body.\n"}, {"review_id": "6biVZBspFO", "reviewer": "Reviewer_uTye", "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.", "questions": "No particular question.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\nI 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.\n\nSo 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*1. 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.*]\n\nWe believe that our result warrants publication due to obtaining improved regret bounds on a problem that has been open for many years. In particular, we obtain the first sublinear regret bounds in a very general setting that is of practical significance (i.e. the kernels for which our bounds apply are regularly used in ML/Data science in practice).\n\n[*2. 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. *]\n\nTo the best of our knowledge, the inequality constructed by Chowdhury and Gopalan cannot be used to achieve the same regret guarantee (at least non-trivially). Here is a heuristic justification. Increasing $\\eta$ in the CG bound can be viewed as decreasing $\\rho$ in our bound, with bounds coinciding when $\\eta = 0$ and  $\\rho = 1$, and being not equivalent for other values. We take $\\rho = O(p(T))$, where $p(x) = x^\\beta$ for some $\\beta \\in (0, 1/2)$. Since increasing $\\rho$ in our bounds corresponds to decreasing $\\eta$ in the CG bounds, and $p(T) >> 1$, we would need to select $\\eta < 0$ to obtain a similar level of regularization, which is not permitted in the bound of CG, which stipulates $\\eta > 0$. This is just a heuristic justification, of course, and perhaps with more effort the regret guarantees can be recovered from this bound, but in our opinion this is non-trivial and non-obvious. In our opinion, the presented concentration bound, which as some reviewers pointed out was obtained in Abbasi-Yadkori’s PhD thesis, is somehow the “right” concentration bound, while the Chowdhury-Gopalan bound is not, which then leads to a suboptimal regret bound.\n\n\n\n[*3. 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.*]\n\nWe believe the improved understanding of GP-UCB is (by itself) worthy as a contribution to the Neurips community, given that there were basic questions about its frequentist regret bound that were open but the original paper received a test-of-time award a few years ago. In particular, this algorithm has been investigated in many papers, but none has obtained sublinear regret for general kernels experiencing eigendecay. We find that the simplicity of our results is a feature of our results, as they are straightforward and easy for a reader with familiarity on the topic to parse. That is, a result can be important and useful without having a long proof or complicated analysis (and in fact, the simple proof can be more useful than a complex one because it can be adapted to other settings by followup work).\n"}]

Author rebuttal:
We would like to thank all reviewers for their thoughtful comments and feedback on our paper. We have responded to each of your comments, and we hope to address any follow-up questions you may have in the discussion.

Several reviewers have pointed out the existence of a bound in the thesis of Yasin Abbasi Yadkori that is equivalent to Theorem 1 of our work (the result on RKHS concentration). We were not aware of this result until recently, and are very surprised that this result has not been properly attributed in many central works on the kernel bandit problem. To address this, we have shifted the focus of our work to just being an improved regret analysis of GP-UCB (appropriately, we have retitled the paper “On the Sublinear Regret of GP-UCB”), with proper attribution to the result in Yasin’s thesis. We still include our independent proof of the bound in the appendix as we believe it to be of independent interest due to its simplicity. Given the overall positive feedback regarding the regret bounds (and the fact that our analysis resolves a question on the sub-linear regret of GP-UCB), we believe that our paper still warrants an accept.


Meta-review: There has been quite a bit of discussion on the missed citation and thus incorrectly claiming the novelty. The authors acknowledged it and provided sufficient evidence and commitment for the revision for the final version. Since the paper still makes a solid contribution in improving the regret bound, I recommend an accept decision.
Decision: Accept (poster)