Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
Authors: Shogo Iwazaki
Venue: NeurIPS 2025 oral ()
Keywords: Gaussian process bandits
regret analysis
Bayesian optimization
Primary area: theory

Abstract: This paper addresses the Bayesian optimization problem (also referred to as the Bayesian setting of the Gaussian process bandit), where the learner seeks to minimize the regret under a function drawn from a known Gaussian process (GP). 
Under a Mat\'ern kernel with some extent of smoothness, we show that the Gaussian process upper confidence bound (GP-UCB) algorithm achieves $\tilde{O}(\sqrt{T})$ cumulative regret with high probability. Furthermore, our analysis yields $O(\sqrt{T \ln^2 T})$ regret under a squared exponential kernel. These results fill the gap between the existing regret upper bound of GP-UCB and the current best upper bound provided by Scarlett [2018]. The key idea in our proof is to capture the concentration behavior of the input sequence realized by GP-UCB, enabling us to handle GP's information gain in a refined manner.

Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
Shogo Iwazaki
LY Corporation
Tokyo, Japan
siwazaki@lycorp.com
Abstract
This paper addresses the Bayesian optimization problem (also referred to as the Bayesian setting of the Gaussian process bandit), where the learner seeks to mini- mize the regret under a function drawn from known Gaussian process (GP). Under Matérn kernel with a certain degree of smoothness. show that the Gaussian process upper confidence bound (GP-UCB) algorithm achieves Ö cumulative
regret with high probability. Furthermore, our analysis yields O ((VT In 7) regret under a squared exponential kernel. These results fill the gap between the existing regret upper bound for GP-UCB and the best-known bound provided by Scarlett [46]. The key idea in our proof is to capture the concentration behavior the input sequence realized by GP-UCB, enabling more refined analysis of the GP's information gain.
Introduction
We study the Bayesian optimization (BO) problem, where the learner seeks to minimize the regret under random function drawn from a known Gaussian process (GP) [8] 19 Throughout this paper, focus the GP-UCB algorithm [51]. which combines the posterior distribution of GP with the optimism principle. Due to its simple algorithm construction and general theoretical framework provided by Srinivas et al. [51], GP-UCB has played an important role in the advancement of the BO field. On the other hand, our theoretical understanding the performance of GP-UCB has not been improved from [51) in the Bayesian setting, while its frequentist counterpart is studied in several existing works 11 61]. Specifically, the current regret upper bound for GP-UCB, as provided by Srinivas et al. [51] is known be worse than that of the algorithm in [46. which achieves state- of-the-art O O cumulative regret. Then, the natural question is whether there is further room for improvement in the existing regret upper bound of GP-UCB, This paper provides an affirmative answer to this question by showing that GP-UCB achieves O(VT) regret with high probability.
Contribution. We summarize our contributions as follows.
We show that the GP-UCB proposed by Srinivas al. [51 achieves Ō (T) regret with high probability under a Matérn kernel with certain degree of smoothness (precise condition is provided in Theorem dependence. This result is comparable to state-of-the-art O(VT regret provided by Scarlett 466 up a polylogarithmic factor and strictly improves upon the existing Ö vnd upper bound of GP-UCB [51] (58). Here, d and denote the dimension of the input domain and smoothness parameter, respectively.
Here, O(.) is the order notation that hides polylogarithmic
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Furthermore, for a squared exponential kernel, we establish (vThn²) cumulative regret
of GP-UCB. This improves the existing O (VTIn upper bound provided by Srinivas al. [5] for any d 1.
The key idea behind our analysis to refine the existing information gain bounds by leveraging algorithn-dependent behavior and sample path properties of the GP. We also discuss the applicability of this technique to other algorithms and settings Section
1.1
Related Works
BO has been extensively studied in the past few decades. Some of them are constructed so to maximize the utility-based acquisition function defined through the GP posterior, including expected improvement [37]. knowledge gradient [17]. and the entropy-based algorithms [24]. The theoretical
aspect of BO has also been actively studied through the lens of the bandit algorithms, such as GP-
UCB [5]] Thompson sampling [43] and information directed sampling 44 In contrast to the noisy observation setting, which these algorithms focus on, algorithms for the noise-free setting form a separate line of research [14 32) Extensions of these algorithms to more advanced settings have also been well-studied, c.g., contextual 34], parallel observation [15), high- high-dimensional [29], time- varying (6), and multi-fidelit setting (30] Unlike the Bayesian assumption the objective function adopted this paper, existing works also extensively study the frequentist assumption of the function, which is also referred to the frequentist setting of BO or GP bandits 7 9 II
26 35
56 59].
Among the existing studies, [46] is closely related to this paper, which propose a successive climination- algorithm and shows an O D(VTIn upper bound and an 22( lower bound of the cumulative regret for one-dimensional BO problem. The fundamental theoretical assump- tions and the high-level idea of our analysis are built on the proof provided by Scarlett [46). Following 46). Wang al. [60] also proves similar regret guarantees under the one-dimensional Brownian motion.
In addition to [46] some parts of our analysis are inspired by the technique leveraged in g Firstly, Cai et al. 8 studies the GP-UCB algorithm through relaxed version regret, which is called lenient regret. In our analysis, the cumulative regret is decomposed into the lenient regret- based term, and we leverage their technique to analyze it. Secondly, Janz et al. (28) proposed the input partitioning- speaking, the high-level idea of their analysis is based on the fact that tighter information gain bounds can be obtained within properly shrinking partition of the input. The key idea provided
28
algorithm for obtaining superior regret in the frequeentist setting. Roughly
in Section 3.1 motivated by this fact, while our analysis itself substantially different from that in (28
2 Preliminaries
Let f X be a black-box objective function whose input domain X is X [] with some r > 0. At each step / E N., the learner chooses query point æ; E X, and then receives a noisy observation y, f(,, ét- Here, E, is mean-zero noise random variable. We consider Bayesian setting, where the objective function f and the noise sequence (Ez) ) are drawn from known zero-mean Gaussian process (GP) and a Gaussian distribution, respectively. We formally describe using the following assumptions.
Assumption 1. Let k X x - R. be the known positive definite kernel with Ya X, ka x)) s 1. Then, assume f GP(O,, k), where GP(O. k) denotes the mean-zero GP characterized by the covariance function k.
Assumption 2. The noise sequence (E))N,, is mutually independent. Furthermore, assume E, (0, r²), where o > 0 is the known constant. Here, N(u, o2) denotes the Gaussian distribution with mean μ and variance 2
These are standard sets of assumptions in the existing theory of BO 43 Specifically, in Assumption 1 we focus on the following squared exponential (SE) kernel ÈSE and Matérn kernel

---

Algorithm Gaussian process upper confidence bound
Require: Kernel k, confidence width parameters (B) IIEN. (EEN.
1: for / 1,2.... do
2: 3₁ t arg max m (x; 91-1) + + (æ;; X,-1).
3: Observe y, and update the posterior mean and variance.
4: end for
Matérn:
|| =1 2
21-v M (x. -))
V2r ar
Tb12 V2rll |
(2E 2:) =exp
Jv
T(v) f
(1)
where and y are the known lengthscale and smoothness parameters, respectively. In addition, (.) and r(-) respectively denote modified Bessel and Gamma functions. Under As- sumptions [ and 2 the learner can infer the function / through the GP posterior distribution. Let
H, == (m), Viiss be the history that the learner obtained up to the end of step Given H,. the posterior distribution of f is again GP, whose posterior mean and variance are respectively defined
p(a; Xr, yr) = k(X,, 2) (K(X,, o 11) yr. (2: = k(x, x) k(X,, x) (K(X, X,) (X),,)
(2)
(3)
where k(X,, 2)) ()) and y, yy yT are the 1-dimensional kernel and output
vectors, respectively. Here, we set X, = (2),..., .y). Furthermore, K(X,, X,) = [k(x, 2)) 12, and I, denote I-gram matrix and r-identity matrix, respectively.
Learner's goal. Under the total step size T E N,, the learner's goal is to minimize the cumulative regret Ry == EIe(T) f(x') f(x,), where x² argmax fxx and [7'] .1).
Maximum information gain. To quantify the regret, the existing theory utilizes the following coormation-thooette quantity yr (X) arising from GP:
1 1(X,), where ((x,) = det Iy + o - (((x,,X))).
(r(X)=
sup my
(4)
The quantity (x( is referred to as the maximum information gain (MIG) over X 51 since 1(X,) equals the mutual information between the function values (f(x)))r(T) and the outputs (yz)re(7) under Assumptions [ [ and the input sequence X, = (#I..... xt). MIG plays vital role the theoretical analysis of BO, and its increasing speed is analyzed in several commonly used kernels.
For example, yr (XX) = 0IId 7") as T
under & kSF [51] For the notational convenience, Ytv (X) for any non-integer
we also define y:
Probabilistic property of GP sample path. The existing theory of GP-UCB under the Bayesian setting utilizes the regularity conditions of the realized sample path of GP. We summarize the existing known properties of the GP sample path in the following lemmas.
Lemma 1 (Lipchitz condition of sample path, e.g., (51)). Suppose k = KSE or k -Matém with > 2. Assume Assumption
7
Then, there exist the constants b > 0 such that
1.2
VL > 0, P PV (f(x) f(a) < L|| T111) ) da exp
(5)
b2
Lemma (Sample path condition for the global maximizer, e.g., 13 14 46) Suppose = KSF or
k Matrrn with 2. Assume Assumption 7 Then, for any dGP E (0. 1), there exist the strictly
positive constants Cgap. Suup= Cquad Pquad > such that the following statements simultaneously hold with probability at least 1 ōGP:
The function f has a unique maximizer any local maximizer "" E X of f.
such that f(x") > f(x") + Cgap holds for
3

---

2. The sup-norm of the sample path is bounded as llf S Csup.
3. The function f satisfies Væ BylP x'), f(x") - Cquad Equaallæ" æ112 2 f(x), where B2 Pr(uud x²) == {x E X ||<² $ Pquad is the L2-ball on X, whose radius and center are Pquad and x", respectively.
Lemma [ states that the sample path f of GP is a Lipschitz function with high probability. This property leveraged in the theory of GP-UCB control the discretization error arising from the
confidence bound construction in the continuous input domain. As described in [51], Lemma iis
direct consequence of Theorem 5 in [2]] under the existence of foddt mixed partial derivatives of the kernel, which are satisfied under k ÈSE and k = Mattm with y > 1 Lemma specifies the regularity condition of f related to the maximizer x. Here, property is implied from the fact that the Ga-sample path has a unique maximizer almost surely under KSE and Maaém [c.g.. Lemma 2.6 in 331. Property 2 implied from, e.g., the compactness of and the almost-sure continuity of the sample path under kSE and kMarm Property 3 also holds automatically under k = kSE and Matéér with v and is used existing works. See Theorem 5 in [3]. Assumption in [46], and the discussions provided by them for further details. Note that the properties in Lemma are not used the existing proof of GP-UCB [- As described in the next section, we analyze the realized input sequence Xy of GP-UCB by relating it to conditions in Lemma
Summary of existing analysis of GP-UCB. We briefly summarize the existing analysis of GP- UCB (Algorithm [ provided by Srinivas et al. [5]]. Based on Assumptions [ and 2 we can construct the srobbprbbablltty confidence bound of the underlying function value f(x) for each æ and N, through the posterior distribution of f(x). Specifically, by choosing a properly designed finite representative input set X, c and taking into account the discretization error with Lemma Srinivas et al. 51 showed the following events hold simultaneously with probability at least
1. Confidence bound. For any E N4. the function value at the queried point æ, satisfies ; 31-1) - -B value f(x) on X, satisfies f(x) S p( X, 3/-1) ",,""'((;;;, (xxx;1,11)
& f(x,). Furthermore, for any / E N,, any function
2. Discretization error. The discretization error arising from X₁ is at most 1/12. Namely, (f) f([=)] s 1/r² holds for any æ E X and E N,. where [æ], denotes one of the closest points of x on X,
In the above statements, f1/²2 is chosen based on the constants a, b in Lemma and the length r of
X, and is defined as
2x2x² + 2d In Pdb
4da
B, = 21n
(6)
36
The above two events and the UCB-selection rule for æ, imply
Ry Σ f(x))) f(0)) Σ f(x'))) f(x,)
T
- 2 Σ
x²
1/2
T
(7)
In the above expression, the upper bound VT= f<x') ΣT 1/72 s x² follows from the second event (discretization error). The inequality Σ/=, f(=))))((()) s 2B ΣT o x1)
also follows from the first event (confidence bound) and the definition of xt. See the proof of Theorem 2 in [51] for details. The above inequality suggests that the regret upper bound of GP-UCB depends on the sum of the posterior standard deviations Σ (x,; 1)) Srinivas et al. [5]
provides the upper bound of this term by leveraging the information gain 1(X)) as follows:
r (rax; VCTI(XT) & (CTy((X),
(
and 8 we conclude that the regret upper bound of GP- UCB is (BTTYT(X) with probability at least I - 6. By combining the explicit upper bound
where C. 2
From Eqs.
In(1+er
DDifferentiability of KMatem is derived in the existing works, e.g., Chapter 2.7 in 52

---

of yr( 51 58
we also obtain 0 (vrIn++3 and θ ( regret upper bounds for SE and Matérn kernels, respectively.
3 Improved Regret Bound for GP-UCB
The following theorem presents our main result: a new regret upper bound for GP-UCB
Theorem 3 (Improved regret upper bound for GP-UCB). Suppose Assumptions 7 and hold. Ser k = kSE or k = Maáé with y > 2. Furthermore. assume that d, y, f, r, and o² are fixed constants. Fix any dcp E (0, and set the confidence width parameter B, of GP-UCB as defined in Eq. O with any fixed 6 (0, - dcp). Then, with probability at least 1 dGP 6, the cumulative regret of
GP-UCB (Algorithm) T satisfies
if k Matéé with 2y d S x2
R1
(9)
O Tn
if k KSE.
d, v. v,C,r, 02, and the constants The hidden constants in the above expressions may depend on (n(1/6), d, Csup= Cgap. Pquad, Cquad corresponding with öGP, which are guaranteed to exist by Lemma 2
We would like to note the following three aspects of results. First, the constants associated with the sample path properties defined in Lemma are used solely for analyzing the regret. On the other hand, the existing algorithm provided by Scarlett [46], which shows the same O VT) regret as ours, requires prior information about these constants for the algorithm run. This is often unrealistic in practice. Secondly, our result does not imply the upper bound of Bayesian expected regret E| B[Ry]. The main issue is that the dependence of the constants in Lemma on SGP is not explicitly known. We leave future work to break this limitation; however, note that the same limitation exists in the algorithm provided by Scarlett (46). Thirdly, our results in Theorem focus on the dependence of the total step size T' in the regret. Therefore, we cannot claim any improvements of the regret on
the dependence of the other parameters. For example, compared to the existing Ry = In T)
regret under k = kSE. our regret upper bound R₃ = O In2 T) indeed avoids the dependence of d in the logarithmic factor; however, under the joint limit of d and T (d, T - oo), it easily behaves super-linearly even under the slowly increasing d (e.g., d = O(In In 7)) due to the hidden constants in the regret.
3.1 Intuitive Explanation of our Analysis
Before we describe the proof, we provide an intuitive explanation of why GP-UCB achieves tighter regret than the existing O( yrrT upper bound. The motivation for our new analysis comes from the observation that the upper bound of the information gain: 1(Xy) yr (x(X) in Eq. (8) is not always tight depending on the specific realization of the input sequence Xy. To see this, let us observe the following two simple extreme cases of Xy where the inequality 1(X7) S yr is loose and tight:
Case I: 1(X7) (T(X) is loose: Let assume all the input is equal to the unique maximizer x" (namely, VI E [T], = x*). Then, when the kernel function satisfies Vx E X, k(x, 1 as with KSE and kMaam. we have:
1 Σ In(1 + o -2)= In(1 o -T), (10) 2
I(Xr) Indet([I + - ((((,.,)))
where d; is the i-th eigenvalue of ((X,, Xy) 11 with (I...., 1)T E CR. The third equation uses the fact that 11 is rank 1, and its unique non-zero eigenvalue is T.
Case II: I(Xy) S (X) is tight: Let us assume that (xx) is the same as the input sequence generated by the maximum variance reduction (MVR) algorithm (namely, Vr E [7], argmax o (w;; X,-1)) [5] 56). Then, from the discussion in Sections and 5 in (51), we already know that (X) & (1 - (XX)). This suggests that 1(X,) $ yr tight up constant factor when Xy is realized by MVR.
5

---

20.0
GPJUCB
17.5
Case
Case (MVR)
15.0
gain
12.5
0.0
0.2
0.4
0.6
0.8
1.0
realtzed le
100
GI-UCB
7.5
MVR
5.0
50-
2.5
0.4 0.5
0.8
1.0
26
50 7%
100
175
Number of time steps
Figure 1: The behavior of the realized input sequence Xy (left) and the corresponding information gain / ((x)) (right) in the 1-dimensional BO problem with o² = 33 The top left figure shows the objective function ff realized by GP under k = Maaén with v = 5/2. The bottom left figure shows the histogram of the realized inputs: (200) with GP-UCB (blue) and MVR (orange) under in the top left figure. Furthermore, the right plot shows the corresponding information gain ((x,) under GP-UCB MVR. We also plot /(X,) 0.5 In(1 o 21)), corresponding to Case described in Section 3.1 We can observe that the inputs selected by GP-UCB are concentrated around the maximizer from the left figure. Then, from the right figure, we also observe that the corresponding information gain increases more slowly than that of MVR, and behaves similarly to Case on f 2 30. More comprehensive empirical results are also provided in Appendix D
From Case I, observe that 1(xx) satisfies O(In 1(x,) yr (X))) depending Xy. Further- more, by comparing the input sequences in cases I and II, we expect that / ((yy) becomes small Xy concentrates around the neighborhood of z", while /(Xy) becomes large if Xy spreads over the entire input domain X. Then, from the fact that the worst-case regret of GP-UCB increases sub-linearly with the speed of ((V)rTyr(X)), we can deduce that the input sequence X, of GP-UCB will eventually concentrate around the maximizer x" if x² is unique and Il is not extremely smal We provide an illustrative image in Figure [ Our proof designed so as to capture the above intuition that /(Xr) could be improved from yr (X) to O(In 7) under "favorable" sample path f.
3.2 Proof of Theorem
Let A be an event such that the two high-probability events of the original GP-UCB proof (described in the last paragraph in Section [ and Lemma with with the confidence level бGP simultaneously hold. Note that event A occurs with probability at least - ôGP 5 from the union bound. Therefore, it is enough to prove our upper bound under A. To encode the high-level idea in the previous section, we need to capture the concentration behavior of the input sequence X7 around the maximizer x". From
this motivation, given some constant & > we decompose the regret as R₁ R (e) ) R (8), where:
R (8)
Σ f(x') f(x') f(x)), (6) (ET(8)
f(x) - f(x)). Σ IEVC(8)
(11)
We set T(E) fre E [T] f(x')-f(z) E} and (T(() [7] T()) in the above definition. key observation that, if we set sufficiently small depending on the constants in Lemma 2
the inputs (xz) in R(2) (8) (namely, inputs (æ,) such that f(x') - f(æ,) s holds) are on the
locally quadratic region around the maximizer x" due conditions and in Lemma The formal
descriptions are provided in Lemma 20 in Appendix C This fact is originally leveraged in [46] to analyze the successive climination-bass algorithm. In the analysis of GP-UCB, it enables to
2Specifically, Il S ((V we cannot make any claims about Xy based on the worst-case bound since any sequence Xy satisfics the worst-case hound without concentrating around maximizer. This is why analysis technique does not improve the worst-case regret in the frequentist setting. Indeed, in the proof of the worst-case lower bound for the frequentist setting 47 the existence of the function with T|lf O({BTTyr(X)) is guaranteed.

---

analyze the behavior of the sub-input sequence (z, f(x')- - f(x,) s E} through the regularity constant Equad- Below, formally give the upper bound for R (E).
Lemma 4 (General upper bound of R Suppose (œ))) is the input query sequence realized by the GP-UCB algorithm. Furthermore, let y, is the upper bound of MIG y (x) such that y is non-increasing on [T, 00) with some T E N. Then, under event A, we have
x² (log, T 1) 2v2CBTT
( (8) S 20xpp T+
max iE(0]
B2 V11/2-11
3
v2
2/2
17 of
where C = 2/In(1 + 2) i = [logz [ + m1
and 8
(1/2--1)
min Cgaps CquadP Pqudd quad
We give the full proof in Appendix A.1 Here, the dominant term in the above lemma is given as:
1 (2) (e) ()) = δ max TTor/22-11 B2 (V quanlit x ar))
(12)
Note that 77, is decreasing as the time index 7/2 of MIG increases. In other words, the input domain B2 ( "i of MIG shrinks as the time index T/2 increases. This property is beneficial for obtaining tighter upper bound than that from the existing technique. For example, under & Matér with 2r + d s v², we can confirm that the dominant polynomial term in MIG is canceled out by the shrinking of the input domain in MIG. Namely, we can obtain the following result under Maaém
max 711/2--1) B2 (V qua x0) Ō(1) (as T T oo).
(13)
which leads to Ry (E) Ō(VT). This strictly improves the trivial upper bound R (8) O(VTyr(X)) under k- = kMatérn The formal descriptions are given in the next lemma.
R(2
Lemma 5 (Upper bound of R()) under KSE and MMaém). Suppose (α))re(T) is the input sequence realized by the GP-UCB algorithm. Furthermore, set as that in Lemma 4 Then, under event A,
(Ō(VT)
k = kMatér with 2v + d v
R
(e) o (T
(14)
k = KSE-
The full proof is given in Appendix
A.2 The remaining interest is the upper bound of R (s).
The definition of R (s) is the same as the lenient regret [ which is known to be smaller than the original regret Ry GP-UCB. Although Cai et [8 studies the frequentist setting, their proof strategy is also applicable to the Bayesian setting as described in Section 3.4 in [8). The following
lemma provides the formal statement about the upper bound of R(() (s).
())(()))
Lemma 6 (Upper bound of RL" adaptation of the proof of Theorem 1 in 8 Fix any 0.
(E) = Õ(1) holds under event Suppose k = KSE or k = Maaém- Then, when running GP-UCB, R A.
We provide the proof in Appendix A.3 for completeness. For both kernels, R (x) is dominated by the upper bound of R2 (s). Finally, we obtain the desired results by aggregating the inequalities in Lemmas 5 and 6
4 Discussions
Below, we discuss the limitations of our results and outline possible directions for future research.
Namely, Vi 2 Ve 0,7,/1 /t e) and Vi 2 (X):()) 7, hold for some 7 e N..
7

---

Optimality. Based on the 92( (2(V)) lower bound on the expected regret provided by Scarlett [46]. we conjecture that our ((V)) high-probability regret bound for GP-UCB is near- optimal. However, it is not straightforward to extend the lower bound for the expected regret in [46] to high probability result. Specifically, the lower bound in [46) is quantified by mutual information term (Lemma [46);; however, to our knowledge, the technique used to handle this term appears to be specific to the expected regret setting. We believe that the rigorous optimality argument for the Bayesian high probability regret is an important direction for future research.
our result for the Matérn kernel, we require an additional smoothness constraint to obtain a ((v7) regret bound To overcome this issue our proof, we believe that we need stronger regularity conditions the sample path around the maximizer than those assumed in Lemma 2
Smoothness condition.
Extension to the expected regret. Our regret bounds involve regularity constants that depend on the sample path. However, to our knowledge, there is no existing research that rigorously analyzes how these constants depend on the confidence level 9GP. This makes it difficult to obtain the expected regret guarantees as with the original GP-UCB, whose expected regret bounds are established by properly decreasing the confidence level as function of T' (e.g., 40 53)). To overcome this issue, further analysis for Lemma P or another idea to quantify the sample path regularities, required.
Extension to other algorithms. One limitation of our technique is its restricted applicability to other algorithms. To apply our proof, at least the algorithm should satisfy the following two conditions: (i) on any index subset, the sub-linear cumulative regret is obtained with high probability (Lemma 21), and (ii) the high probability lenient regret bound is provided (Lemma 6 The existing analysis of the other major algorithms in the Bayesian setting (e.g.. Thompson sampling [43), information directed sampling (44)) does not provide these properties. Nevertheless, we believe that the high-level ideas in our proof (see Section 3.1 could be beneficial for future refined analyses of other algorithms.
Instance dependent analysis in the frequentist setting. As described in the footnote in Section 3.1 we believe that our analysis does not improve the worst-case regret upper bound in the frequentist setting. On the other hand, our technique can be applied to the instance-dependent analysis (49 for GP-UCB. We expect that our proof strategy could yield a ((V)) instance-dependent regret for GP-UCB by replacing the sample path condition 3 in Lemma 2 with the growth condition (Definition [4 of the function. It is an interesting direction for future research.
5 Conclusion
We provide refined analysis of GP-UCB in the BO problem. For both SE and Matérn kernels, our results improve upon existing regret guarantees and fill the gap between the existing regret of GP-UCB and the current best upper bound in [46). The core idea of our analysis is to capture the shrinking behavior of the input sequence by relating to the worst-case upper bound and the sample path regularity conditions. Although our current analysis is limited to GP-UCB in the Bayesian setting, we believe it lays the foundation for several promising future research directions.
Acknowledgments
We thank Jonathan Scarlett and Shion Takeno for their valuable comments on revising the manuscript.
References
[1] Kendall Atkinson and Weimin Han. Spherical harmonics and approximations the unit sphere: an introduction, volume 2044. Springer Science & Business Media, 2012.
we focus on the setting where the resulting regret becomes θ(vT) under Maném- This arises the requirement of the additional smoothness condition 2y + d 5 y2. On the other hand, we can also apply the same technique even under 2y d > v². In this case, resulting regret becomes strictly larger than Ō(VT), while it is strictly smaller than ÕT 2odd ) of the original GP-UCB's analysis.
*For simplicity, in Theorem 3
8

---

[2] Douglas Azevedo and Valdir Antonio Menegatto. Sharp estimates for cigenvalues of integral operators generated by dot product kernels on the sphere. Journal of Approximation Theory, 2014.
[3] Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Reseurch, 2017.
[4] Felix Berkenkamp, Angela Schoellig, and Andreas Krause, No-regret Bayesian optimization with unknown hyperparameters. Journal of Machine Learning Research, 2019.
[5] Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. International Conference on Learning Representations, 2021.
[6] Iliaa Bogunovic, Jonathan Scarlett, and Volkan Cevher. Time-varying Gaussian process ban- dit optimization. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2016.
[7] Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Reseurch, 2011.
[8] Xu Cai, Selwyn Gomes, and Jonathan Scarlett. Lenient regret and good-action identification in Gaussian process bandits. In International Conference on Machine Learning, pages 1183-1192. PMLR, 2021.
[9] Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental design and kernel bandits. In Proc. International Conference on Machine Learning (ICML), 2021.
[10] Alexandre Capone, Armin Lederer, and Sandra Hirche. Gaussian process uniform error bounds with unknown hyperparameterss for safety-critical applications. In International Conference on Machine Learning. 2022.
[11] Sayak Ray Chowdhury and Aditya Gopalan. kernelized multi-armed bandits. In Pruc. International Conference on Machine Learning (ICML), 2017.
[12] Andreas Christmann and Ingo Steinwart. Support vector machines. 2008.
[13] Nando de Freitas, Alex Smola, and Masrour Zoghi. Regret bounds for deterministic Gaussian process bandits. arXiv preprint 1203 2012.
[14] Nando De Freitas, Alex J. Smola, and Masrour Zoghi. Exponential regret bounds for Gaussian process bandits with deterministic observations. In Proceedings of the 29th International Conference on International Conference on Machine Learning, page 955-962. Omnipress, 2012.
[15] Thomas Desautels, Andreas Krause, and Joel W. Burdick. Parallelizing exploration-exploitaaion tradeoff's in Gaussian process bandit optimization. Journal of Machine Learning Research, 2014.
[16] Costas Efthimiou and Christopher Frye. Spherical harmonics in dimensions. World Scientific, 2014.
[17] Peter Frazier, Warren Powell, and Savas Dayanik. The knowledge-gradient policy for correlated normal beliefs. INFORMS journal on Computing, 21(4):599-613, 2009.
[18] Peter Frazier. A tutorial on Bayesian optimization. arXiv preprint arXiv:1807.028111 2018.
[19] Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
[20] Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the Laplace and neural tangent kernels. Advances in Neural Information Processing Systems, 2020.
[21] Subhashis Ghosal and Anindya Roy. Posterior consistency of Gaussian process prior for nonparametric binary regression. 2006.

---

[22] Andrew Gray and George Ballard Mathews, A treatise on fisntiinn and their applications to physics. Macmillan, 1895.
[23] Steffen Grünewälder, Jean-Yves Audibert, Manfred Opper, and John Shawe-Taylor. Regret bounds for Gaussian process bandit problems. In Proc. International Conference on Artificial Intelligence and Statisties (AISTATS). JMLR Workshop and Conference Proceedings, 2010.
[24] Philipp Hennig and Christian J Schuler. Entropy search for information-efficien global opti- mization. The Journal of Machine Learning Research,
2012.
[25] Shogo Iwazaki and Shinya Suzumura. No-regret bandit exploration based on soft tree ensemble model. Advances in Neural Information Processing Systems, 2024.
[26] Shogo Iwazaki and Shion Takeno. Improved regret analysis in Gaussian process bandits: Opti- mality for noiseless reward, RKHS norm, and non-stationary variance. In Proc. International Conference Muchine Leurning (ICML), 2025.
[27] David Janz. Sequential decision making with feature- -ineer models. PhD thesis, 2022.
[28] David Janz, David Burt, and Javier Gonzalez. Bandit optimisation of functions in the Matérn kernel RKHS. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2486-2495. PMLR, 2020.
[29] Kirthevasan Kandasamy, Jeff Schneider, and Barnabas Poczos. High dimensional Bayesian optimisation and bandits via additive models. In Proc. International Conference Machine Learning (ICML), 2015.
[30] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabas Poczos. Multi- folti-fideeity Gaussian process bandit optimisation. Journal of Artificial Intelligence Research, 2019.
[31] Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. International Conference Artificial Intelligence and Statistics, pages 240-278. PMLR, 2022.
[32] Kenji Kawaguchi, Leslie Kaelbling, and Tomás Lozano-Pérn Bayesian optimization with exponential convergence. Advances in neural information processing systems, 28, 2015.
[33] Jeankyung Kim and David Pollard. Cube root asymptotics. The Annals of Statistics, pages 191-219, 1990.
[34] Andreas Krause and Cheng Ong. Contextual Gaussian process bandit optimization. In Proc. Neural Information Processing Systems (NeurIPS), 2011.
[35] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[36] Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's s theorem, feature maps, and smoothing. In International Conference on Computational Learning Theory. Springer, 2006.
[37] Jonas Močkus. On Bayesian methods for secking the extremum. In Optimization Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974 pages 400-404. Springer, 1975.
[38] Francis J Narcowich and Joseph D Ward. Scattered data interpolation on spheres: error estimates and locally supported basis functions. SIAM Journal Mathematical Analysis, 33 36):1393-1410, 2002.
[39] Francis Narcowich, Xinping Sun, and Joseph D Ward. Approximation power of RBFs and their associated SBFs: a connection. Advances in Computational Mathematics, 2007.
[40] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi-objective Bayesian optimization using random scalarizations. In Uncertuinty in Artificial Intelligence, 2020.
10

---

[41] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[42] Gabriel Riutort-Mayol, Paul-Christian Bürkner, Michael R Andersen, Arno Solin, and Aki Vehtari. Practical hilbert space approximate Bayesian Gaussian processes for probabilistic programming. Statistics and Computing, 3371):17, 2023.
[43] Daniel Russo and Benjamin Van Roy. Learning optimize via posterior sampling. Mathematics of Operations Research, 19(4):1221-1244 2014.
[44] Daniel Russo and Benjamin Van Roy. Learning to optimize via information- dirreced sampling. Advances in neural information processing systems, 27, 2014.
[45] Sudeep Salgia, Sattar Vakili, and Qing Zhao. Random exploration in Bayesian optimiza- tion: Order-optimal regret and computational efficiency. In Proc. International Conference on Machine Learning (ICML), 2024.
[46] Jonathan Scarlett. Tight regret bounds for Bayesian optimization in one dimension. In Proceed- ings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4500-4508. PMLR, 2018.
[47] Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proc. Conference on Learning Theory (COLT), 2017.
[48] Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. International conference on artificial intelligence and statistics, 2021.
[49] Shubhanshu Shekhar and Tara Javidi. Instance dependent regret analysis of kernelized bandits. In International Conference on Machine Learning, 2022.
[50] Arno Solin and Simo Särkkä. Hilbert space methods for reduced-rank gaussian process regres- sion. Statistics and Computing, 2020.
[51] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. International Conference on Machine Learning (ICML), 2010.
[52] Michael I. Stein. Interpolation of spatial data: some theory for kriging. Springer Science & Business Media, 1999.
[53] Shion Takeno, Yu Inatsu, and Masayuki Karasuyama. Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 33490-33515. PMLR, 2023.
[54] Filip Tronarp. Toni Karvonen, and Simo Särkkä. Mixture representation of the matérn class with applications in state space approximations and Bayesian quadrature. In 2018 IEEE 28th International Workshop Machine Learning for Signal Processing (MLSP), 2018.
[55] Sattar Vakili and Julia Olkhovskaya. Kernelized reinforcement learning with order optimal regret bounds. Advances in Neural Information Processing Systems, 2023.
[56] Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da shan Shiu. Optimal order simple regret for Gaussian process bandits. In Proc. Neural Information Processing Systems (NeurIPS), 2021.
[57] Sattar Vakili, Michael Bromberg, Jezabel Garcia, Da-shan Shiu, and Alberto Bernac- chia. Uniform generalization bounds for overparameterized neural networks. arXiv preprint wwXiv:219.006090 2021.
[58] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.

---

[59] Michal Valko, Nathan Korda, Rémi Munos, Ilia Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, 1AI' page 663. AUAT Press, 2013.
[60] Zexin Wang, Vincent YF Tan, and Jonathan Scarlett. Tight regret bounds for noisy optimization of Brownian motion. IEEE Transactions on Signal Processing, 70:1072-1087, 2022.
[61] Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas. Improved serf-normalized concen- tration in Hilbert spaces: Sublinear regret for GP-UCB. Proc. Neural Information Processing Systems (NeurIPS), 2023.
[62] Yun Yang, Anirban Bhattacharya, and Debdeep Pati. Frequentist coverage and sup-norm convergence rate in gaussian process regression. arXiv preprint arXiv: 0475530.8.773,, 2017.
[63] Fuzhen Zhang. Matrix theory: basic results and techniques. Springer Science Business Media, 2011.
12

---

A Proofs in Section
A.1 Proof of Lemma
Proof. From Lemma
21
have the following upper bound for any index set T c [7]] under A:
E((x)) f(x,) s 2 CBrl x²
(15)
IET
Here, for any such that 7/2/-1 1 2 T, we set (17:) as
Ji ( (T/2
))
(16)
As described the proof below, these (111) are designed so that we can obtain the upper bound of IT (m)) in a dyadic manner. Here, we consider the upper bound of [T (n:) based on the worst-case
upper bound in Eq. (15). From the definition of (17) and Eq. (15) with T [T], the condition
IT (n))mn & TT + x2/6 must be satisfied: otherwise, we have [ f(x") - f(x,) z
Ee) f(x) f(x,) 2 (T())l 2VCBrTy, + x2/6, which contradicts worst-case upper bound in Eq. 15 Therefore, we can obtain the following upper bound:
IT (m)) & max [SS m S S2CBIITY + 6 2
x²
(17)
Furthermore, since ni is monotonic due to the condition about y,, we have S m., which implies (12)) (m)) From Eq. (15) with T (m)). Eq. and ((2)) c T (()), we further obtain
[T()) s max ( s 7/21 m7 s 2 (Br(122)7ar)) + 6 6 4
(18)
Similarly to (T(12) we have T(13) (T2) and
x²
[T())) $ max s T/4 177 S 2, (Br(T/4) +
(19)
By repeating this argument times while 7/2/-1 T holds, we have the following inequality for any i s [log2
- +
IT() s max
| i s (Br((/22-1)
x²
T
(20)
2
Then, we have
(8)
Σ
f(x') f(xx)
(21)
(ET
Σ
f(x') f(x)) +
Σ
f(x") f(x,)
(22)
(()N(())
(SIT()))
Σ
f(x') - f(x,)
Σ
f(x²) f(x,)
=
(e)
(23)
Σ
f(x)) (((x))
(e)T())))
2
= Σ f(x') f(x,) +
Σ
Σ
f(x') - f(x,),
(24)
(8)NT(I))
1=1 TET (0
where the last line follows from T(p) T(m). In the above inequality, we define T(po) as T(p) [T] for notational convenience. By repeatedly applying the above decomposition,
13

---

obtain
Σ
f(x') f(x,,)
Σ
f(x)) f(a)))
(25)
reT (8)
i=l 1ET (s))T (0-0770m)))700
Σ
f(x') f(x,) +
Σ
f(x') - f(x))
(26)
(B)
1=1 1ET (8))T
Σ -(x)) ((a,) Σ
Σ
f(x) - f(x)),
(27)
(E)N
where = [log2 LJ + 1. Regarding the first term in Eq. (27 we have
E f(x') f(x,) S 20 (n:)1 2c sup
(28)
1ET' (E)ATT))))
where the last inequality follows from (T) s T, which is implied by (T())) S T/2 from
Eq. (20 and the definition i. Next, regarding the second term in Eq. 27 we first define Ti and
x as T. (x) ((i-)) n (T() and X (æ, Ti), respectively. Then, by applying
Lemma with Tr we have
Σ
- f(x,)) = Σ f(x') f(x,)
(29)
IET1
x² $ 2 CBBITII(X(0)++
(30)
6
x²
22
(B
(31)
π²
s 2 (B
(32)
2 (B
(33)
where the third inequality follows from [7 s (1)()-))) and the last inequality follows from Eq.
20
By aggregating Eqs. 27
28 and (33).
we obtain the following inequality under A:
x² 6
R ( (E) = 20sup T + 2
(34)
i=1
x²
S 20sup T+ +
(log, 7 + 2v/BBT 211-11/2 (((1211)((11)
(35)
3
x²
2 2CBBT
$
2c T+
+
(log, 7' +++1 +
max ie(ū]
(X(0)
(36)
3
v2 -
The last line follows from Σ 20-172 to specify the radius of the ball B2(+;²)) such that ()) is included in it.
00 1y-
v2
The last part of the proof is
1-1/v2
V2-1"
Conversion of the sub-optimality gap into the upper bound input radius. From condition 3 in Lemma 2 the definition of (x))), 8, and Lemma 20 have (2 xx) for any æ (1) This implies Yx (1), f(x') f(x) 2 Cquadl| 113 from condition 3 in Lemma Since Va (()))(())-))) f(x) s y from T. c (n)),, we have π) Cquad faa xx = / 2 || x= 112.
which implies (i) c B,( |-- "iuaaa x²). Therefore, we have
((T/2-1))( (x S ((T/2-11) B2 (Vozl (ogulaliii x*"
(37)
14

---

Finally, combining Eq. (3)
with Eq. 37
we have
R (8) 20 sup T
x²
(log, T 1)
2/2CB,T
max Marzii-
[B2 (Vogua)ri
(38)
12 -2-1 re[(]
A.2 Proof of Lemma
To prove Lemma we require the upper bound of MIG with the explicit dependence on the radius of the input domain. CorollaryBiin Appendix we provide it with full proof. Below, we establish the proof of Lemma 5
based on Corollary
When k = Mattrn
Set Maa > O as the constant such that the following inequalities hold:
Vr 2. (x); Maat Sroad In Serd I,
(39)
||m||| s m/ Vr 2 2. Vn > 0. {I Rd
CMuu
Sred
In Sood + In²
(40)
The existence of Cat guaranteed by the upper bound of MIG established in Corollary Note that
CMai is the constant that may depend on d, f, r,d,and Furthermore, we = CMal Iiid For function g()) == 7,/t, we have
In 2040
Joed
g' (r) = 2vCMat, r
aid -
2v Aved aeid
CMat
4y + 1
2v -1 avdd
In
2v 2vdd
(41)
2v d
2y + d
CMnt 1 Iiia (In Srea
1) (-2y y In 4y d).
(42)
2v + d
From the above expression, if Inr 2 4v + d exp(2 + d/(2)), y,/t is non-increasing. Therefore, we set [exp(2 + d/ which independent of Here, for any > 0 and 2 2, have
(B2 (1)x²)) (or Rd
|| x n)
(43)
Yi (x E Rd
||0||| S n)
(44)
CMat 27 Irend
In Seed
In² In²1).
(45)
where the second line follows from the fact that kMaém is the stationary kernel (namely, Matérn transition invariant against any shift of inputs). Regarding πi in Lemma
by setting T; as
T; = T/2 we have
2 22 C2VCBBTTT +
=
(46)
T; 4/CBTTiTT
π²²
(47)
Ti
3T;
CBTT.CMal
T In Soed Ti
π²
+
(48)
Ti
37;
2
= 4CCMMBB (1, Ivra In
aveed T;
Gund
(49)
37;
s Mia BT (r, aund In Anve T:).
(50)
'If' we rely on the result in (88 we can tighten the logarithmic term from In 3red to In 22t however, due the technical issue of (58) described in Appendix B
4xad
we proceed proof based Corollary
15

---

where CMal > is a sufficiently large constant such that CMai vBT
( 201d deid Ti
4VCCMaBBr TT; Iand In
svrld
ayed
Ti
for any T 2 2. Note that we can choose EMai > with- and (50). for any i, have 45
37,
out depending on T. From Eqs.
(Vo
YT/2/-1
[
c
quadd quad"lii x
(51)
vd Sward
vdl sone T
S Mat
c
quad
ni
In
Ti + In Ti
(52)
$ CMa
By
TT, arnd In awadd
Arrked
Ti
T
In
Auee
Ti In
(53)
"quad
Furthermore, by noting condition 2v + d v2, we have
vil Sved
20nd
Ti
T lord
T
(54)
d(2redi- vdd
0
T
(2ved)²
(55)
d(2red-2)
0
T,
(2+d)
(56)
Ō(1).
(57)
From the above inequalities, we have 7r/2-1 B2 Voglaull: a²)) Ō(1). Therefore, Lemma implies
R (E) 2cupp T+ x²² (log, T+ 2/2CBTT V2-1 x x
(58)
=((VT)
(59)
When kSE- The proof for kSE is not as straightforward the proof for k Matér- Specifically, we have choose a proper T so as to obtain an (InT) upper bound MIG. Let CSE 0 be the constant such that the following inequalities hold:
(X) CSE In
(60)
28
In Ind+1_
Vr 2 2. Vn E (0, V e'cd ) (1 E ||m||| n))
CSE
In
(61)
In
rpeeca
The existence of such CSE is guaranteed by Corollary 8 the above inequalities, Ca is the constant defined in Corollary 8 We also set 7, as 7, = CSE d+1 s. We choose later such that we can leverage the second statement in the above inequalities. Under k KSE, we have
222VCBITiTn +
n
(62)
T;
//CBTTiT
x²
(63)
T,
3T;
4 CBrTICSE
d+1 TV
x²
+
(64)
Ti
3T,
=4VCCsEBT T
In
del
Ti
+
π²
(65)
3T,
CB
1,
In
del
T;
(66)
16

---

where CSE
>
is
sufficiently
large constant such that CSE [ In In Ti
4CCCBBB
Ti
t
del
Tj
for any T; 2 Hereafter, we define πi = VBT (T Ti)
37,
Then, to apply Eq.
61..
we consider the lower bound of Ti such that /quund < (2222(e²ca)) hold.
From the condition
"quaa"
(22=))) we have
26
e'ca
del CSE BT In : Ti < T
quad 7 < VV c²cd
3 quual
(67)
2F2
e'ca
CSE BT In del
<
(68)
quail 2F2
e'coCSFR Cyuul
Br Bn T Tí.
(69)
From the above inequality, we set 7 such that
e² Cs
BT Bn T TTT.
(70)
28 Cquad
Then, from T; 2 T and Eqs. (67). and (70).
Yr/21-1
B2 (Ve quad Dii x
s snn Yr, 00 E Rdd ||0012 $
"quua Mi
(71)
In Ti
S CSE
+ InT
(72)
In
2igud Thecs
Based on Eq.
772 we further consider the lower bound of T; such that
In T; (lnT).
(73)
In
(2quaal2) Tiers
For the condition in Eq. 773 we have
20 quqadd 2
2c Aqquad ec CEaCsE 1/2 In del Ti
T
T///4
(74)
NcECs
ecaEsH VBT In Ti 2Cqund
T:1/4
(75)
ec es VBT In del 2Cquaa
t ////4 2
(76)
lec BB T
t T 2
(77)
20 Ququall2
Hence, if
ec SE vo in T 2
we have
dn Vi Ind 2camsl meecs
In T; 4-d Ind Tj
CSE
+ InT
CSE
In T
(78)
s CsE (4 In InT).
(79)
17

---

By aggregating the conditions following inequalities hold:
70 and 77 we set as the smallest natural number such that the
T
c CSB
Br In
T, and T
ecd 2Qqual
CEBA (n2(d11) T.
(80)
2
Then, from Eqs.
72 and 79)..
have
V /(r/2-1>>
(32 (V (Qquee ax) O(Vin)..
(81)
Finally, by noting T OIn 2d+4
T), we obtain the following result from Lemma
(e) 0 Id= T VT'n2T).
(82)
Since is a fixed constant, the above equation implics (5) = O(VTh2T)
A.3 Proof of Lemma 6
Proof. From the upper bound of the discretization error in event A, we have VI 2 v2 Va: (x) [((a))) s s/2. Here, we set (()) (I e N, | 2 v2/z). By relying on the standard
argument of MIG 51. we observe the following inequality for any realizations and > 0:
min (TT(E)T(()) oe2;; X,-)) (XTTIenTTo)))
(83)
(T())
where T(E) E [7) f(z) - f(z)
$) and = 22nn2/n1111 o the following inequalities for any ( o (zy X,-1
Under A, we further have
M 11 + 8 X
(84)
= = : - p or (zf X7-1) 20 o (77;
(85)
f((x)) + 220""0(0;; o(o;;
(86)
<f(x') - 2 (T(E)
(87)
(()
s s1f(x') - f((x'())))))) (((=)) - 2
(88)
B. (1[ (| B 0(x 1; +2
(89)
(T(ET(())
where the second inequality follows from the definition of (f)) and the last inequality follows from
T ((e) and event A. Therefore, under A, the inequality - 2 (Br
> must
(T(ein(())
hold; otherwise, (( X + 1 (a77: X ) < u([ 1 X 97 + B o[ (1,,,,,;,,, 1)
which contradicts x7 E argmax 1u X w7-1) 1) + B o(x; 1,- This further implies
16CBryiTeentee (X)
(90)
82
82
T(E) 0, the theorem's statement clearly holds; therefore, we suppose ((c) # 0 in this proof.
18

---

for any & > 0. Furthermore,
R (8) (s)
Σ (ET(E)
f(x') - f(x))
(91)
2 Σ
2Csu
+
f(x") f(z,)
(92)
(ET(e)TT(a)
2 + 6
π
$ 20sup'
(93)
for any & > O. In the above expressions, the last inequality follows from Lemma 21 The remaining part of the proof to substitute the quantity (T( [+)] Eq. (3) into its upper bound, which is deduced from Eq. (90) depending on the kernel.
For k kSR. Under k = kSE, we crudely take the upper bound of (T(E) as
(T)))(()) (nCentttt
16CBryr(X)
(94)
g2
g2
The above upper bound implies kSE. Eq. (93) implies
(T(e) 0 (Bryr(X)). Since yr(X) = OInd T) under
2 x² + (Br(8rr((X))
R (8) s 20sup
+
(95)
6
o Bry (rn((nd In (I 1)
(96)
o ((n
(97)
Ō(1)
(98)
For k = Mattém- Set Maat > 0 as the constant such that the following inequality holds:
Vr 2. y1 (X) Caat 20 30rd 1.
(99)
The existence of CMai is guarnnteed by the upper bound of MIG established in Corollary (())) 2 2 holds, Eq. (90) implies
Then, if
16CBrCMal ((E
((E))(())
{+))
(100)
16CBTCMal 7 (e)
2ved T
= (())) 5
(101)
doed 16CByCMr In
3ord
= (()) Feed s
(102)
82
1+
16CB Mat Inaved T
= (()))
(103)
8²
Therefore, have (()) =(1) under fixed d, and Hence, from Eq. 93 obtain
R( (z)=
B Information Gain Upper Bound
Our analysis requires the upper bound of MIG with explicit dependence on the radius of the input
domain. Several existing works [4] 27 28 established such result by extending the proof in (51).
did+i)
However, the proof strategy in 51 result in Ö(T 2rid(d11) upper bound of MIG in Matérn kernel,
19

---

which is strictly worse than the best achievable Ö(T5A)) upper bound. Vakili et al. 158 shows Ö si-) upper bound of MIG with v > 1/2 under the uniform boundness assumption of the eigen-
functions. Furthermore, the following work [55] shows (r(( e Idd || s 17)) = ( and T avdd for any radius 17 > O if there exist eigenfunctions uniformly bounded without depending Some of the related results supports the uniform boundness assumption under d
2vd
rj 0. 62 or
27
under the approximated version of the original Matérn kernel [42 55 however, our knowledge, we are not aware of any literature that rigorously support uniform boundness assumption under the general compact input domain with d 2 2 and 1/2. See Chapter 4.4 in 22 for the detailed
discussion. Therefore, this section's s goal is twofold: (i) prove Ö upper bound as claimed in [58] without relying the uniform boundness assumption, and (ii) clarify the explicit dependence on the input radius in the upper bound proved in (i).
Below, we formally describe our MIG upper bound.
Theorem 7. Fix any d N., o² O, and T E N.. Let us assume X = foc E Rd ||æl|2 s 1}. Then,
For k KSE, yr(X) satisfies
c(I)
yr(X)
d
In
+
T o²
In
In
T o²
c exp
2
- 02
1
(104)
@d
if0 s e'ca and T/(e- 1)2 0². Furthermore, for any 0 > e²ca, we have
c(3)
yr(N)s
In
1+
T x2 + (4) In 1
T
+c(.
(105)
Ind eca
x2
Here, we set 0 2B and
max 11, exp
(
Furthermore,
c() C2) c c(4) c are the constants only depending on d.
For k Matér with v 1/2, Yr (X) satisfies
Yr (x) S VC
(106)
+ +1} and > 0 the constant that only depends on and absolute constant, respectively. Furthermore, Yr is defined as
where C(T, V(T,v,0))= max log, (1+
C, In + logz
72
Here, C. >
[[([]
81 = cl In
1
2T 0²
((2)
T
Inzved
|
2T o²
(107)
222
where d,y; c(2) > 0 are the constants only depending on d and v.
We also obtain the following corollary by adjusting the lengthscale parameter & > 0 based on the radius the input domain.
Corollary 8. Fix any N.. 0² 7 17 O. Let us assume X (x Rd || S 1)) Then,
For KSE, (r(X) satisfies
c(3)
(x)))
d+
T |
r d
c(4)
In
1
T -²
+
+c(5)
(108)
Ind
212 17eccd
2 /172 e2ca-
For k kMatér with y 1/2, Yr (X) satisfies Eq. (066), with
Tr
(1) In d,y
1+
2T
+
d,v
2vd
22
T
2ved
In
2v
|
2T
(109)
20

---

The constants in the above statements are the same as those in Theorem 7
While the above results ignore the explicit dependence on d and v, all the other parameters are explicitly stated in our upper bound of MIG. We would like to emphasize that we do not rely on the uniform boundness assumption of the eigenfunctions prove the above results. In the above results for k kSE, obtain the same 0In 7) upper bound as that in (58) except for the constant factor. For = Matêm we also obtain the same ((T ( upper bound as that in [58], while the logarithmic dependence get worse from 0 (Ind/(2+*d) 7) to (In44v T). Furthermore, the above result reveals the explicit dependence of the radius 17 of the input domain. Regarding the case (())2//)) T Ivia)) upper bound of MIG, which is consistent with that with uniform boundness assumption.
k Matérn: our result suggests (11 2nd
in 155
Proof overview. The basic proof strategy follows that in [58, which leverages the Mercer decom- position of the kernel. To bypass the uniform boundness assumption in the proof of [58], we must resort to other specific properties of the eigenfunction. However, except for some exceptional cases, the eigenfunction of the kernel on the general compact domain is difficult to specify in an analytical form and complex analyze. To avoid this issue, instead of studying the original definition of the MIG on R4, we consider reducing the original MIG on X = {ær E Rd ||æ:|| S 1} to that on a hypersphere sd {a Rd+1 ||| 1} defined in Rd+1, The eigensystems on sd are one of the exceptional cases, whose eigenfunctions are specified as a special function on sd, called spherical harmonics I6.. Indeed, by using the addition theorem of the spherical harmonics (Theorem [4), the existing works [25] 31 [5] already demonstrated that the upper bound of MIG on 3 is proved as with [58) without the uniform boundness assumption. We use their technique show the upper bound of MIG under SE and Matérn kernels on Rd, while the original motivation of these existing works is to study the MIG under the neural tangent kernel on a hypersphere. The remaining parts of this section are constructed as follows:
In Section B.
we show our core result (Lemma that guarantees the MIG on {æ e Rd
|| || -
1} i8 bounded from above by that on gd up to logarithmic factor.
In Section B.2
we summarize the basic known results about Mercer decomposition on sd, which is the foundation of the following subsections.
In Section B.3
we provide the general upper bound of the information gain on gd (Lemma 15 represented by the kernel function's eigenvalues. This subsection's 's result has no intrinsic change from those in 31 57]; however, we provide details for complete- ness.
In Section B.4
we provide the upper bound of the decaying rate of the eigenvalues in SE and Matérn kernels.
In Section B.5 establish the full proof of Theorem 7 based on the results in Sections B.I
B.4
B.1 Reduction of the MIG on Rdd gd
Lemma 9 (Reduction to the hypersphere in Rd+1), Fix any d E N+, 0² > 0, and T e N,. Suppose
X = {(x),..,,.. O)T E Rd+1 EE & 1}, and define 3d as sd = {x E Rd+1 ||0||| = 1}. Then,
For k KSE, we have
max dedet( I + K(X,, X7)) s max In dn +o -iai--o--XX,,,,--0 -K(Y, X7)). (110) 2ye8
XXX
For k Matérn we have
max
Indet(Ir - EXX
(111)
< CCT,v,
max 2rE4
In In (1 + 20 (K(X).Xy)) + C,
(112)
where C(T, v. 0.) max f0. log, is the constant that only depends 0. Furthermore, C > 0 is an absolute constant.
(1+ [(v) In 7 C,
o² + ,
! logz
[v(()o))) + Here, C,>0 >
12
21

---

Proof. For any 21, 21,...,27 E X, we construct the new imput sequence ......, By on 8 where T. Miill....Nidd
25=1 +1.)
Under k kSE. It is enough to show the following inequality:
det I + or " X7)) z det(IT K((T, Xr)),
(113)
From the definition of T we rewrite R.H.S. in the above inequality as TT). where Xy = (x1,...,
det( I " K(X,, X))) det(K (Ir + "ooo""KXX KK(r, Xy)),
(114)
where [K],,] k žj) (a;; 2;). Here, A O B denotes the Hadamard product of the matrices A and B. Then, Oppenheim inequality (e.g.. Theorem 7.27 in (63) implies det( A B) det(B) πI. Ai for any positive semi-definis definie matrices A and B. Therefore, if K is positive semi-definite matrix, Eq. (14) immediately implies
det -K(t, Xy)) 2 det(II K(X,, X7))
K +et K(Xy,Xr)) (115)
ic ic[7
From the definition kSE and Ti, we have
(Vi
|| 2r112
||
112
||
k k(T;, Ft)) exp
| 2,
(116)
k (zi, xzj)
202
20
|00112 112
V
||
exp
(117)
2(
The above equation suggests that K is equal to the kernel matrix of the one-dimensional SE-kernel, whose inputs are transformed by V || 112- Since the SE kernel is positive definite, the matrix K also positive semi-definite, and we complete the proof for k kSE.
Under & = Maáóm- Similarly to the proof for kSE- consider the application of Oppenheim inequality; however, the positive semi-definiteness of element- -iiee quotient matrix K. is unknown for & Aaaém- To avoid this problem, we leverage the following representation of Matém. which is given the form of the lengthscale mixture of the SE kernel [54]
| T 20-zv-1
k(ar 3. r(y) Jo
e² exp
dz.
(118)
Based the above representation, decompose the original kernel function into the following three components:
k(x, ②) (1 k2(2, 3) k3(2, x),
(119)
where:
[ z"- c exp
a T
ki (x, ))) [(v) J0
dz,
(120)
28-
| T
k2 ))
v-1 exp
dz,
(121)
[(v)
2F
|| - कं
kz )))
[(v) y- -
dz
(122)
28-
22

---

with some 1/2 Then, as with the proof of Theorem 3 in [3
we have
In IT + - ((T, XT))
s In IT K (Xr, X7))
Indel((I + K Xr)) Inndei(I (x,
(
(00
(ii)
(123)
where (X7, X7), (2r, Xy), and K3 Xr) are the kernel matrix of k1, h2, and k3, respec- tively. We set sufficiently small !/1 and large 7/2 so that the crude upper bound of the first term (i) and the third term (iii are sufficiently small. For this purpose, the following settings of 171 and 172 sufficient (we confirm in the next paragraphs):
1 (V)
r(v) T 12 max 1, In C2 02
(124)
where C, is the constant such that Vz 1, z² C Hereafter, suppose that
2)1 < 1/2 holds with the above definition. The case 1)1 2 172 is considered in the last parts of the proof.
Upper bound for the first term (i).
From the definition of kj. we have
1 z--le- - exp
|| - 21
(1 x0
Jo
dz
(125)
T(v)
2822v-1
1
m 22
(126)
[(y)
Jo
1 11
22
(127)
[(v) Jo
[z']]]
(128)
vT(r)
r[(r) 7.
(129)
Then, from the definition of 17,, we have
v(() " vT(v)
(130)
T2
7
Therefore, by denoting the eigenvalues of (X,, Xy) with decreasing order (Ai)iejr
we have
In (,)x)))7)) In | (1 o 2
(131)
i=1
In(1 -2 $ Inn1 In(1+7-17
(132)
(133)
where the last inequality follows from d1 S v ET. x | X7) = Ei. ki (x xz)² <
2 IT Since In(1 T-1) - as T co, there exists constant C > 0 such that In det( Iy + (r X7)) & C for all T N,.
Note that the linear combination the positive definite kernel neg-negetive coefficients limit are also positive definite. Therefore, &j, k2, and K3 are also positive definite as far as f/2 > m/- Note that d is non-negative from the positive semi-detiniteness of K₁ (Xy. Xr).
23

---

Upper bound for the third term (iii). From the definition of K3, we have
| Ø112
(xx, 3))
=
[(x)
2" v- e eeep
exp
2
dz
(134)
$ [(y)
v-1 e =d
(135)
Cv 000
$ (()) J
e dz
(136)
22
((v)
[e 12
11
(137)
2C,
112
((y) (-2
exp
(138)
Then, from the definition of 1/2, we have
2C, ((v)
2C, ((v)
((v) 2C,
7 o²
exp
exp
In
(139)
o+2
T2
By following the same arguments after Eq. (33 in the upper bound of the first term (i), we conclude that there exists constant C > such that In det Iy + "3 Xy)) s for all T E N..
Upper bound for the second term (ii). We further divide k2 with dyadic manner:
(a,, σ)
k (x. 3).
(140)
4=l
where:
1 min(m 2m.)
| 21
k2 (4) (x, ②)-
2" v e exp
dz.
(141)
r(v)
m
2f2zy-1
Here, N, is the minimum number such that 12 1/2 holds. Then, with Eq.
123
we have
de + o K, Xy)) det [r + (x, (xy.
(142)
where K,0) (Xr, X7) is the kernel matrix of k Next, for any q, define new kernel function (44)) (x. T) as
||
|
[(4) (x. k/ (x. Tt) exp
(143)
2 min (1, (72)7)
We further denote the kernel matrix of k by K. (Xr. Xy). Then, from Oppenheim's incquality,
we have
In det IT + 2 (g) (X.. X7) det Ir o - (Xr,
(144)
Furthermore, for any 29-1, min (n) 29, 12]]. the following kernel function [(4) (ar, क. z) is
positive definite (c.g., Lemma A.5 [T]:
||0:|3
|
( ||0||
| |ل
F(q)
(x, z) = 2 exp k2
exp
-22
2 -1 min( 29,29,10 m9))
(145)

---

Note that 2k (T;, T.j) k24) (æ; aij) j) is represented as
(4)
2k (Ti, F)) k2d (Ii, 2;,)
(146)
min(m .p
||=; - 2. 22
z=-le e- exp
k (æ,, 2);
(147)
[(v) 27/2-1
28--y-1
By noting that the product of positive definite kernels is also positive definite, the above expression (4) (Xr, Xy) is the positive semi-definite matrix. Therefore, we have
implies that 2K (9)
Xy,X,
Q
In + -K (Xr, Xr)
In det
[T [ 20 2k! (8..8y)
(148)
4=1
Q det
Ir + 20 20r22-22( 2K(r, Xr))
(149)
where the second inequality follows from the fact that K(X,, X7) k!!) (Xr, X7) positive semi- definite. From the definition of Q, we have
72
Q s log2
+
(150)
7/1
log: /2
log2 7/1 +
(151)
1
[(v)
T
(v
log2 max
1,
In
log2
+1
(152)
Cy
T
[(v)
72
72
S log2
In
log2
+1.
(153)
Cr
v[(v)o
By combining Eqs.
142
144
149
and (133). conclude
In In IT +
K2 Xr))
(154)
s logz
| r(v)
22
+
loga
vI(v)o
7.2
+ Indet (I, 20 22-222200 -x((xx
(155)
By aggregating the upper bounds (i), (ii), and (iii), we have the following inequality under 171
<
det( I o K((r, X,)) s C(T, v, 0 Indet [I +2 2 K((r, (x)Xxxx)))) 2C.
20
(156)
Finally, if m 172, we have
Indet( 1 + K
(157)
x In Iy
(Xy, Xy) (K) Kx X7)))
(158)
Indet IT o - (XT, X7)) In (T o Kr XT).
(159)
2C
(160)
s CCT.,,, Indet I + 20 - "((y, + 2C,
(161)
where the last inequality follows from In det [I + 20 22 "Kx,, Xx) z O and C(T, v, v, 2 0. The desired result obtained by setting new absolute constant C as 2C the above inequality.
For any positive semi-definite matrices A. that is positive semi-definite, have x(4)) 2 (B)
where (1(5)) and (2(²) is non-negative cigenvalues A and with decrcasing order. (This is consequence Fischer's
of Courant-Fischer's min man-max theorem.) Therefore, we have det(A) = l(2,4) a det( B) for such and B.
25

---

B.2 Summary of Mercer Decomposition for Dot-Product Kernel on Sphere
In this subsection, we summarize the basic known results of the Mercer decomposition on $ The content of this subsection is related to the analysis of the spherical harmonics. We refer to [T [6] as the basic textbook. In the kernel method literature, the Mercer decomposition of the dot-product kernel and its eigendecay have been studied. See, e.g., P 36 48). Furthermore, the existing analysis of the neural tangent kernel also leverages the Mercer decomposition based on the spherical harmonics. We also refer to the appendix of 3 as the related works of this subsection.
5
We first describe Mercer's theorem. Let (2) (f X
fx f (()) oo) be the qquare-integratee functions on X under the measure μ. Furthermore, let define the kernel integral operator Tx (2 ()) - L2 μi) of a square-integrable kernel function
X Xx X - as (+x))))) fx k f())))((() Then, Mercer's theorem guarantees that the positive kernel is decomposed based on the eigenvalues and eigenfunctions sequence of Ta with absolute and uniform convergence on X x X. We give the formal statement below.
Theorem 10 (Mercer's theorem, e.g., Theorem 4.49 in [2]). Let X be compact metric space, μ be a finite Borel measure whose support is X, and k : X x X - R be a continuous and square integrable-posifie definite kernel on (X. Suppose that (di))eN and (Ai)teN are eigenfunctions and eigenvalues of the kernel integral operator Th. respectively. Namely, (ói)i is an orthonormal bases of the eigenspace { $ (x) such that Tedi(-) 2;0i(()) for all E N. Then, we have
k(x, a)
Σ (1) iEN
(162)
where the convergence absolute and uniform on X x X.
Specifically, our interest the Mercer decomposition of the kernel on gd. This given as spherical harmonics on sd, which we define below.
Definition 1 (Spherical harmonics, e-g-- Definition 2.7 in [1). Fix any d 1 and (Rd+)) be the all homogeneous polynomials of degree m Rd+1 that are also harmonid 10 The space yd+1= = Ym Yn (Rd+1) lsd is called the spherical harmonic space of order m in d + 1 dimensions. Any function in yd+ is called spherical harmonic of order in d dimensions.
N. Let
The following lemmas provide the properties of the spherical harmonics, which guarantee that the Mercer decomposition the continuous dot-product kernel on 3d is defined based on spherical harmonics.
Lemma 11 (Dimension and completeness of sphererical harmonics, e-g., Chapter 2.1.3, Corollary 2.15, and Theorem 2.38 in (). Fix any d 2 1. Then, the following statements hold:
For any m e N, we have dim (ddll) = Na+1,m with Na+1.m (2m+d-11(mdd Further- more, For any m. N with m # n, we have yd++ 1 yd+
mi(d-13 1)]
Let us define (Zm.)je(NNa-anl be an orthonormal bases of yd+1 Then, UneeN(Y..))jENN.. becomes an orthonormal bases of 12($d.o7) where o()) is the induced Lebesgue measure on 3d.
Lemma 12 (Funk-Hecke Formula, e.g., Theorem 2.22 in 11 Theorem 4.24 in 16).. Fix any 2nd22
2 1. Let f: [-1, - B. be a continuous function. Define |gd=l|= := T(d/2] as the surface area of gd-1 Then, for any m E N and Ym, E Yd+1, we have
[
Am)m(z),
(163)
where (-)) is the induced Lebesgue measure on 3d, Furthermore, Am is defined Am = =13d-11 J[ P Pm,dei ())0)()0((11))))))))))))
(164)
A polynomial H(x).... is called homogeneous of degree m if H(t (xa+1)
H(x ...g.....xx..1)). Furthermore, polynomial H(xI....xx4)) called harmonic if Agnif O. where A is the Laplace operator. See Chapter in (16) or Chapter 2 in (I].
Here, as with the second statement, we consider L2(8". Therefore, the inner product for any f.g ad - R is defined on L (3(3".0) .o) Jos f())g()))
26

---

where pm.d+1(1) (7) is the Legendre polynomial of degree m in d + dimensions, which is defined as
Lm/2] Σ k=0
(1 (1-13)&mm-2
Pm,a+1(1) m!'
(-1)
(165)
4*k!(m 26)!T a
Lemma 12 suggests that the spherical harmonics are eigenfunctions of the continuous dot-product kernel ((x, Φ)) = T(x 2) on sd. Furthermore, Lemma 11 guarantees the Ume (Naa..m)) forms orthonormal bases of L' .r), which implies that they are the orthonormal bases of the eigenspace of TR. These facts give the following explicit form of Mercer decomposition for continuous dot-product kernel.
Corollary 13. Fix any N.. Suppose X = = Furthermore, assume the kernel function : x X - R. is the positive definite kernel such that Va, X, ((x, =(xx σ)) with some continuous function [-1,1] B. Then, have the following Mercer decomposition k:
Natllm
k 26
Am
(m.,(2))m..(3))
(166)
j=l
where jE denotes the spherical harmonics, which consist of orthonormal bases of gd++ Furthermore, Am 2 defined as
Am = 1 S (maa)()((((111) dr.
(167)
2x: for any 3d Therefore, represent kSE and Matém on gd by Eq. (166). Finally, we describe the following addition theorem of the spherical harmonics, which plays central role in avoiding the uniform boundness assumption in the existing proof of MIG on gd.
Note that || 2: V2
Lemma 14 (Addition theorem, e.g., Theorem 2.9 in 1 or Theorem 4.11 in (6). Fix any d 2 and N. Let (e be an orthonormal bases of 4d+1 Then, we have
Na-L.m
Σ Y Ym.j(x)) = Nd+1.
Vz, E E gd
Pm.d+1 T),
(168)
|gd|
where Pm.d+1(t) is the Legendre polynomial of degree m in d dimensions, which is defined in Eq. (15)..
B.3 Upper Bound of MIG with Mercer Decomposition
By using Corollary [3 and Lemma 14iin the previous subsection, we can derive the following general form of the upper bound of MIG.
Lemma 15 (Adapted from (57). Suppose the kernel functiion k satisfies the condition in Corollary 13
Furthermore, assume (xx, x) for all æ, x E X. Then, for any M E N, MIG on Sd satisfies
1 max
o - s NM In 1+
T
T
Σ m=M+1
Am (169)
2
#y.....EE ESS
18d102
where NM Em=o Na+1,m
The proof almost directly follows from 58 while minor modification is required to deal with the unboundness the eigenfunctions through the addition theorem. The same proof strategy is already provided in [31 57 for analyzing the MIG of the neural tangent kernel on the sphere. Although our proof has no intrinsic change from their proof, we give the details below for completeness of our paper.
27

---

Proof. We first decompose the kernel matrix XT), Khead + Kiail, where [Kheadli.
-m= Am jj=1 -/att Ym (x; (2x) and [Kailii 2 2m=M+1 Am > 2=²= as with the proof in [58), the MIG is decomposed as
Nattim (2; (21).. Then,
max In + K((r,
(170)
2 ........ 27. rrE
1 In det Ir + Khead
=
2
In det Ir + @
Ir
0²
Knead
K
(171)
Based on the feature representation of the kernel, the first term is further bounded from above as follows (see [57 (
T s NM In
In det
Ir
+
- Khead s NM In 1+
+
(172)
T2NM
o²
where the second inequality follows from N'
1. Regarding the second term, as with 58 we have
-1
2 In det
I7 + σ²
I
Khead
K mill
(173)
σ²
1
-1 Kaii
$ T In
T TT
I
I
Khead
(174)
o²
o2
$ Tl
T-1
T+
o2 (T(Kia)))
(175)
where the first inequality follows from In det(A) s T (I(((())) for any positive definite matrix Txx (e.g.. Lemma in (58)). Then, from addition theorem (Theorem 14), have
Nd
Tr (aaii)
Am
Ym, (T.
(176)
[=l m==+1
Na+L.
Am
P
(m xi))
(177)
[8d]
[=1 m=M+1
T
AmN.+
(178)
M=M+1
where the last line use (x. xx,) Pm.a(1 (1) By combining the above equation with Eq. we have
175
2 In det
Ir
1 1 o2
Ir+
+
Khoud
K
In
1+
Σ
Am
(179)
r²
M=
T
AmNa+tmm
(180)
Sd
m==+1
where the last line use Vz e R, In(1 S
To obtain the explicit upper bound of Eq. (169). we introduce the following lemma.
Lemma 16 (Upper bound of Nat1,m and NM). Fix any N.. Then, for any m N., we have
Na (d + 1) d- m1
(181)
Futhermore, for any E N, we have
NM 1 + (d 1- Md.
(182)
28

---

Proof. Recall Ndt1.m
())(dd))))) ml(d-1)!
Under d 1, we have
(2m) - 1)! 2 (d 1)e mm=1
Na+1.
(183)
m!!
for any N4. Under 2, since Nd+1,m
(2m+d-1) (mm=dd2)) m!(d-1)!
2m+d-1 (maa1 and ("
d-1
(m) d-1
we have
2m + d - 1
(m + d 2)e d-1
Na S
(184)
m
in + d -
d-1
$ (2 d - 1)e d-1
(185)
d
$ (d 1)e m
(186)
Finally, since Nat1.0 = 1, we have
M
M
NM = 1 Σ
Na+t.m S 1 + (d + I)e d-1
Σ
m
d-1
1 +
(d+ 1)e 10-1
(187)
m=
m=
B.4 Eigendecay of SE and Matérn Kernel
To obtain the explicit upper bound of Eq. 169 we need the upper bound of the eigenvalue in Eq. (167) under SE and Matérn kernel. Regarding SE kernel, several existing works have already studied 36 39). We formally provide the following lemma from [6).
Lemma 17 (Eigendecay for k kSE sd, Theorem 2 in (3)). Fix any d N,, 0 O, and define ||--
X sd. Suppose that k XXXX - R is defined k(æ, σ)) exp
Then, the eigenvalues
(Am)meN, defined in [167 satisfy
(2e)
del
d+l
2e
2
1 02)
Am < |3d1
exp
(188)
(2m + m+
Regarding Matérn kernel, we provide the upper bound of Am for v > 1/2 by extending the proof in
200, which studies Am for Laplace kernel (Matérn with 1/2). As with the proof in 200, leverage the following lemma, which relates the spectral density of the kernel to 2m-
Lemma 18 (Eigenvalues and spectral density, Theorem 4.1 in
Fix any d E N,, Suppose that k Rd+1 x Rd++1 - R is a positive definite, stationary, and isotropic kernel function on Rd+1 such ②) for some function (b-)) Furthermore, suppose ((.) represented
that Va, H., k(x, 3) 4b x
as
((x) (2x)d=1
JRdr1
@(11ml12)e "nd'dnn ædn.
(189)
for some function + such that Va 2 0, ②(a) 0 and fram @(llall)ddn Then, there exists function Te [] + R such that Vx, x E T<xx""" () k(x, Furthermore, Am in Eq. [167]
given by
Am =
(T)
m+ d=1 (f)dr,
(190)
where B B (.) is the usual Bessel function of the first kind and of order d-1
In the Matern kernel, the spectral density that satisfies the conditions the lemma is defined when > 1/2. Then, the explicit form of ((1) given as:
(v+d1))
Ca.v
1y
T =
,2
(191)
fDy
29

---

where
2d+1 2 2 y++ 1/21 (2v)
Ca.v
(192)
r())
See, Chapter 4.2 in 41). By using Lemma 18 we obtain the following lemma.
Lemma 19 (Eigendecay for kMaérr on Sd). Fix any Suppose that k X x
E No. l O. and define X sd. defined as (xx Hi -iyl|a-Mill Jv (2 Then, the
eigenvalues (Am)mers, defined in 167 satisfies
Ca.y 22-- for
Am
(193)
ifm 2v and v 1/2. Here, Cd.y is defined as
I(2v + d)
Cay Cd.v
exp
2v + d
(194)
r v r2(m+
Proof. From Lemma 18
we have
( B2
Am
30 m+ m (t)dr
(195)
(2)
Cd.v
for Jo (
2y
[ c
+P))
B² m+
dله (1)dr
(196)
S (2v ( 1-2r-
Cd.v
B²
m+ d-1 (f)dr.
(197)
As with the proof of Theorem 7 in [20). we evaluate the integral 10") 22 mt
(f)dr by using
the following identity (Chapter 13.4.1 in (22
[(a
[(2) 1pp + f/- 1 +
B (a(at)Ba((n dr [
12
2r [t
17 tp 1 r 22 1pp tqq 1) [ 10 1
(198)
where p q + 0. By setting p q m + 111 2v d, and
1, we have
p p+q+ + 2 m Hence, for any m > v, we have
2v+d-1
T(2v + d)r (m - v)
2v B2 m+ d= (1)dr-
(199)
2
21 v+ d+1
r [mm + +
Stirling's formula implies that there exists a constant C > 0 such that
I (m -v s C(m -- exp(-m v) exp
(200)
12(m v)
T (m + + d) 2 C(m + d) m exp (-(m + d))
(201)
30

---

Therefore, for any 2 2y with <> > 1/2, we have
(m v) -- exp(-m=+ exp(-m- v) exp
r (m- v) [ + d)
12(m-v)
(202)
(m + v d) m exp (-(m v d))
(m v)
1
exp
+ + + ))
(203)
(m + V d) m+
(m - -)
(m v) wtrrdd
exp
2v + d
6
(204)
(m v) 2v-d exp
2v + d +
(205)
6
1
$ 22 2v exp
2v d + 6
(206)
where the second inequality follows from 2 due to 2 2y = m-y 2 v, the third incquality follows from aggregating Eq. (97). (199, and (266). we have
+ d
and the last inequality follows from y m/2 2 m m/2. 2. By
Cd.v par
2v+d-1
[(2v + d)
22 m 2v exp 2v + d 1 6
Am -
(207)
2
21
d+1 v
2
Čd.v 2v
(208)
foy
B.5 Proof of Theorem 7
Squared exponential kernel.
From Lemma 17 we have
(2e) :
d+1
2e'
2 +
Am < [3d
exp
(209)
0
(i + d - 1ym+
8
0²
(2e)
del
d+1 2
2_2
1
2e
m
|
exp
(2m) -m-
(210)
Vx
Ø2
(2e) del
d+1
I |gd]
2
exp
+
1
e
m
m
(211)
Vx
Ø
0
Here, we set Cd,e as
(2e)
del
d+1
2
1
Ca.o =
exp
-
(212)
VI
g²
Then,
(r(X) < NM In
1+
T
+
T
Σ
AmNa+
(213)
1dd
M=M+1
$ NM In
1+ σ
T
+
Co.oT
Σ
oo
e
m
Na+1.
(214)
o²
m- M=M+1
[1 (d + d- Mal
In
1
T
Ca.oT o²
(d a-1
m
4
(215)
Qm
M+1
where the first and last inequalities follow from Lemmas and Lemma 16 respectively. Here, for
any d N, and m N., we have m & c7 with ca max exp
1 o - -))]. Indeed, when
31

---

d s 2, we have md/2-1 2 1 = ca. When d 2 3, the function g(m) m _ (4-1) attains maximum
at m e on oo), which implies g(m) - exp 1 _ - 1)) m exp ( ( -1) 1 cd
Hence, we have
vr(x) s |1+ (d + 1)e--1 -Me In (1 |+
(1+ σ²
+
Ca.oT
o² (d + D)
ecd
(216)
fm
m
In the remaining proof, we consider the upper bound of (mm)) m separately based on > O s cd, we have
ecd m 6m
6m
exp
-m In
S exp (-m)
(217)
ecc
for any m such that
Then, by noting that the condition T/(e- 1) 0² implies 2 1, we have the following inequalities by setting M In 1 + +
9m acd 2 e +
d'es
e'ca In 1 1
ecd 9m
exp(-m)
(218)
DI
M==++
exp(-m)dm
(219)
cxp(
(M)
(220)
e²ca
T
$ exp
+
(221)
r
T
5e
1
+
(222)
T
-1
se
1
+
(223)
0²
se se
(224)
T
Therefore, for 0 e2ca, the following inequality holds from Eqs. of M:
216 and 224). and the definition
yr(X) s + (d 1) (Eea In
_
1
In
1 σ²
+
eCa.old + d-1
(225)
Next, if > e'ca, we have
eCd m 0m
8m
θ -
exp
mm In
exp
-m In
(226)
eca
eca
for any N.. Then, similarly to the proof under any M E N:
eZca, we have the following inequalities for
ecd m Qm
0
exp
In
(227)
ecd
ME=M +1
m=M++
0
exp
-m In
dm
(228)
ecd
0
exp
M
In
(229)
In
0
eca
ecd
0
< exp
-M In
(230)
ecd
32

---

where the last inequality follows from 0/eca > e + > e'ca. setting M
In
|
In| Fcd
we have
ecd m 9m
T 1+ σ
T
σ²
S exp
In
(231)
o
T
M+
Hence, for > c'ca, we have
T o2
+ T x² +
yr < 1+ +d+ Dea-1
In
1 +
+ 1
In
Ca.old+ + 1) (232)
In
eca
Finally, aligning Eqs. (25 and 232 desired result.
by focusing on the dependence on T, 0², and 0, we obtain the
Matérn kernel.
Similarly to the proof for the SE kernel, for any M 2 2v, we have
2
max #88
In I7 + o -2
K(x,,Xy))
(233)
s NMM In
1+
T
+
T
Σ
80
Nd=1mm
(234)
σ²
13102
M=M+1
$ $11+ + (d+ 1)ed
In
1
+
T
T(d + D)
Σ
Ammd-1
(235)
(r2
13d102 M=
T(d+ I)Caved-1
T
s [1 + (d+ 1)ed d- -dd In
+
x²
13
m
2
(236)
M=M++
= =|1+ + (d+ (d+1)ed MMd In
1+
T
JC..
Σ
m -2v-1
(237)
x2
222
m=M+1
where the second inequality follows from Lemma
16
and the third inequality follows from M 2 2y
Cd+1)Ca
and Lemma 19 In the last equation, we set Ca.v
Furthermore,
[39]
80
- S / m 2v 1m
M 2v
m
(238)
M
2v
M=
By balancing Md In(1 + T/O2) and TM-2r max
pep under the condition 2 2v, we set M
T In 1 (1+ 33 1/(2xe)) pp
2v,
Then,
max
In 0 2 X7))
(239)
2 m By By...... egd
T
Tea. --
$ [1 + (d+ -e In
1
(240)
σ²
2222 2v
T
Cur Md
T
$ [1 + (d 1)e
In
1+
In 1 +
(241)
2y
|+ =In(1+
=In
T
Cd.
(d+ + d-
Md In
1
+
T
(242)
2y
x
| =m(1+
T وي
T
T
=
+
(2r) CCa,
+
2222
In
Xped
1
In
|
(243)
(2)) +1) In
T
T
2v Fend
1 T
=
|+
+
C²
In
(244)
x2
0262x
33

---

where we set Ca," = Cd. 2v
+ (d+ 1)ed-1
In the above equations, the second inequality follows from
TM
0262
1dIn In(1 + +T/02)
In(1 + (Ml+T//07)
2 M M-2v-d
(245)
(22
T
o2
20ed
In( I (11++//0))
S SM
(246)
T
T
In (1+
S M.
(247)
Finally, combining Eq. (244 with Lemma
we obtain the desired result 12
C
Auxiliary Lemmas
Lemma 20 (Sub-optimality gap and the neighborhood around the maximizer). Suppose f is contin-
uous. Then, under conditions I and 3 Lemma 2 x: E (P x²) holds for any x X such that f(x") - f(x)
z & with & = min(Cgap- Cqund quad
Proof. When B2(pquad; x²) = X, the statement is trivial. Hereafter, we assume B2 Pu(Pu x²) # X. Here, note that f(x") - -( 2 Cquad quad holds for any o E B (Pquzdi x*) from condition Lemma 2 where B/ (Pquadi x²) {ær E X || - x' = Pquaa). Furthermore, from the continuity of f and the compactness of (X B2 (pqudd: x')) U 2h (pqund:")) there exists T. argmax (Apuai)))
(Pquaiar") f(x)). Then, we consider the following two cases separately.
quad holds. If there exists a E X (2 x') such quad' we can choose V. such that H. E B2 (Pqudd x"" ) 2 Cquad quad holds for any 0 ε Bhy (quadi x"). Furthermore, such T. is the local maximizer on X, which satisfies f(x') - f(ã.) S f(x') - f(x) S 81 S Cgup- This contradicts condition 1 in Lemma
When Cgap 2 CquadP quad' Cqund euan
that f(x') f(x)= S & = Cquaap? since f(x') - f())
When Cyap Cquadd quad" & Cyap holds. If there exists X (2(P x²) such that f(x") - f(x) $ E = Cgups we can choose T. such that T. X \ Br (2 x") since f(x") - f()) 2 CquadP quad > Cgup holds for any 2 B (Pquadi x²). Furthermore, such 2. is the local maximizer X, which satisfies f(x") ((.) s f(x)) f(x)
Cgap
This contradicts condition in Lemma
From the above two arguments, we have Vx E X B2 (pquad: x²), ), fx=' f(x) > 6. This implies that it is necessary to satisfy B2 x²)) under f(x") f(x) S E.
Lemma 21 (Upper bound of regret of GP-UCB for any index subset). Fix any index set T c [T).
Then, when running GP-UCB, we have the following inequality under A:
E(x)) ffa)) (CCBIITI((X)) n² IET
x²
CBr 6
(248)
where C = 2/1n(1 2 and Xy (x,)
Proof.
By following the proof strategy of GP-UCB, we have
f((x)) f(x,) s Σ f((')))--
f(x,) s 22p
x² X1
(249)
6
1E7
lef
1ET
Note that need adjust the noise variance parameter by factor 1/v2 from Lemma
34

---

d-1,
experentiol
19/8 GRUca
JVVB
25-
GPUCI
GFUcs
20-
10
Informetnn gats
10
100
200
330
400
500
100
200
330
400
500
100
200
300
400
500
Nummerr
strps
steps
time steps
2-2, sqquaeedd esporential
MV2
40-
GPUCS
GFUCC
-00
Infurmdeen Oae
30
10
Wnfrrmeton
20
20
10
100
200
320
400
505
100
200
320
400
505
100
302
300
400
500
(aumber steps
Nkmmbrr steps
Nummbe oftime steps
Figure 2: Average results of information gain under 20 different sample paths. The top shows the results for the input space X = [0. 1] with lengthscale parameter = 0.1. The bottom row corresponds to the input space X = [0. 1]2 with lengthscale ( = 0.25, and from left right, use the SE kernel, the Matérn 5/2 kernel, and the Matérn 7/2 kernel. The shaded regions indicate one standard error.
due to event A. Here, we define new input sequence (āt)rsITI as H, zi where is the 3-th element in T. Furthermore, we define X, (")....,āp)) ,,)). Then, from X, X,, and the monotonicity of the posterior variance against the input data, we have
00( 1ST
or ( X j--1)
(250)
o ( X,-1)
(251)
1=1
S (
(252)
= VCITI((TT)
(253)
(CTTlxm())
(254)
where the second inequality follows from Theorems 5.3 and 5.4 in 51
D Numerical Simulation for Information Gain
In addition to the simple example provided in Figure T we empirically confirm the gap between the worst-case (MVR) and GP-UCB's information gain under the Bayesian assumption. In Figures and 3 we report the average and the quantile realized information gain with GP-UCB, over 20 different sample paths, generated by changing the random seed, respectively. We conduct experiments under the same settings as in Figure of the main text. We also report the information gain corresponding to the sequence of maximum variance reduction (MVR), following the same setup as Figure [ In all cases, consistent with Figure I in the main text, we observe a noticeable gap in information gain between UCB and MVR.
35

---

Matóri
squaaeed esporentao
25-
25-
(NNDIIS-52
20
0P-00-1--35
0817
Information
0
100
200
300
400
505
100
200
300
400
500
100
200
300
400
500
steps
steps
de?, Squareed entelnaa
MX
40-
40-
044 1052
alton Qpen (2K0
54V3012 12-311--3
SPU0810-33
20-
20
10
0
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Quantiles of information gain over 20 different sample paths. We report the 10%, 25%. 50%, 75%, and 90% quantiles information gain of GP-UCB.
Figure 3:
36

---

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

---

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

---

Answer:
[No]
Justification: The main contribution of this paper is on the theoretical side, and open-access code is not essential.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips.c// cc. http:ppullllggggleee / ssi ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The detailed experimental settings in Appendix Dree provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental
material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
report
Answer:
[Yes]
Justification:
The experiments in Appendix Doandixxppoa provide one standard error bar.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
39

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπтоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments in Section D are minimal, and the computing resources are not significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We reviewed the NeurIPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper diseuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper only focuses on the theoretical aspect, does not propose new algorithm, and does not relate specific applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
40

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
42

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
that the method development in this research does involve LLMs as any important, original, or non-standard components.
The answer NA
Please refer to our LLM policy for what should should not be described.
2LLL
43


Reviews:
[{"review_id": "J7dAiamxBp", "reviewer": "Reviewer_aVgd", "summary": "The paper improves the regret bound for the GP-UCP algorithm.\n\nThe algorithm applies to the following framework. There is a domain ${\\cal X}$ (restricted to $[0,1]^d$ in the paper) and a zero-mean Gaussian random field on it (sorry, I prefer a field to a process in this context). For every $x\\in{\\cal X}$ there is a fandom value $f(x)$ so that all joint distributions of $(f(x_1), f(x_2),\\ldots,f(x_n))$ are Gaussian, the means $Ef(x)$ are 0, and the covariances $\\mathrm{cov}(x_1,x_2)$ are given by a known kernel function ${\\cal K}(x_1,x_2)$. The learner can request a value at $x\\in {\\cal X}$ and get $f(x)+\\varepsilon$ corrupted by i.i.d.\\ Gaussian noise $\\varepsilon=\\varepsilon(x)$. Given a set of pairs $(x_i,f(x_i)+\\varepsilon)$, the conditional mean $\\mu(x)$ of $f(x)$ at an arbitrary $x$ is then given by the well-known kernel ridge regression formula $Y'(\\lambda I +K)^{-1}k(x)$ . \n\nHere the goal of the learner is to choose $x_t$ sequentially aiming to hit near $x^* \\in\\arg\\max f $ as soon is possible. The learner's performance is measured by the cumulative regret $\\sum_t (f(x^*) - f(x_t))$.\n\nA natural approach here is to choose $x_t$ maximising $\\mu$ as worked out on the basis of the previously observed values at $x_1,x_2,\\ldots,x_{t-1}$. However, this suffers from the usual optimism under uncertainty faults: the value $\\mu(x)$ may be high due to insufficient exploration. So instead of $\\mu(x)$ Srinivas et al (2010) suggest optimising an upper confidence bound $\\mu+\\beta$. \n\nThis paper tunes the algorithm to improve the regret bounds of Srinivas et al (2010) for the rbf and Matern kernels. The resulting bounds get within the logarithmic factor to the known lower bounds. \n\nThe authors try to explain the intuition behind the improvement through information gain on a sequence.", "questions": "None", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper improves on state-of-the-art results, which are quite fundamental to machine learning. It does not quite match the lower bounds, but is really close. As a downside, I would mention that the analysis only applies to specific kernels.", "was_revised": true, "final_justification": "Upon reading the discussion, I am inclined to keep my assessment of the paper.", "rebuttal": "Thank you for your overall positive assessment. We will carefully incorporate the corrections for typos that the reviewer pointed out."}, {"review_id": "G9mPR6zcYo", "reviewer": "Reviewer_UNfA", "summary": "The paper studies the standard Bayesian optimization problem under the assumptions that the objective function is sampled from a Gaussian Process prior and the noise is Gaussian. It focuses on the standard GP-UCB algorithm and provides an improved regret bound under certain assumptions that hold for the Matérn family of kernels. Specifically, the paper removes the dependence on the maximum information gain $\\gamma_T$—which can grow polynomially with $T$—and replaces it with logarithmic terms, leading to tighter theoretical guarantees.", "questions": "1. Can the authors explain why the assumptions on the smoothness parameter of the kernel are necessary? Specifically, where does the proof break down if these assumptions are not satisfied?\n\n2. Can the authors elaborate on why the proof technique used in Section 3.2 does not extend to GP-TS, in contrast to GP-UCB?\n\n3. Can the authors comment on the noise-free setting? How would the results change if the noise variance were zero?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper fills a significant gap in the literature by deriving regret bounds for GP-UCB that match the known lower bound. I consider this a substantial contribution to the field.\n\nA limitation is the assumption on the smoothness parameter of the kernel in Theorem 3, which the authors themselves acknowledge. However, the reason for this restriction is not clearly discussed, and it is difficult to understand the necessity of this assumption from either the main text or the appendix.\n\nThe main parts of proof are well explained in Section 3.2.\n\nA very minor comment: the quotation marks around favorable on line 191 should be corrected.", "was_revised": true, "final_justification": "After reading the rebuttal and other reviews, I maintain my recommendation for acceptance of the paper.", "rebuttal": "Thank you for your overall positive assessments.\n\n**Q. Can the authors explain why the assumptions on the smoothness parameter of the kernel are necessary? Specifically, where does the proof break down if these assumptions are not satisfied?**\n\nThese smoothness conditions are employed to derive upper bounds that match the \\$\\tilde{O}(\\sqrt{T})\\$ expected regret lower bound proven by [Scarlett, 2018], but they are not essential assumptions for the analysis itself. In order to claim $R\\_T = \\tilde{O}(\\sqrt{T})$, the information gain-based term must become polylogarithmic order. For this, we require that the input space over which the information gain is defined decrease sufficiently fast. Here, the decreasing speed of the input domain of the information gain is derived from the worst-case upper bounds of GP-UCB. Therefore, greater smoothness guarantees faster convergence of this input space (more precisely, the decreasing speed of the input domain is governed by $\\eta\\_i$ in Lemma 4, which decays more quickly to zero as the smoothness increases). Based on these observations, to ensure a polylogarithmic information gain in Lemma 4, the input domain of the information gain must shrink quickly such that the effect of the dominant polynomial term of information gain vanishes, which leads to the condition $2\\nu + d \\leq \\nu^2$. These points are also described in Lines 214-215 of the main paper. \n\nOn the other hand, importantly, the analytical framework we propose can still be applied even when the smoothness condition in Theorem 3 is violated. In such cases, although a $\\tilde{O}(\\sqrt{T})$ regret is no longer guaranteed, our result still strictly improves upon the \\$O(T^{\\frac{\\nu + d}{2\\nu + d}})\\$ bound originally provided by [Srinivas et al., 2010]. Concretely, when the smoothness condition is not satisfied, \nthe term \\$\\tilde{O}(T^{\\frac{d}{2\\nu + d} \\cdot \\frac{2\\nu + d - \\nu^2}{2\\nu + d}}) $ in Eq. (63) appears in the regret bound as a replacement for the standard maximum information gain bound \\$\\gamma\\_T(\\mathcal{X}) = \\tilde{O}(T^{\\frac{d}{2\\nu + d}})$ used in existing GP-UCB analyses. \nConsequently, even if the smoothness condition does not hold, \nwe can derive $\\tilde{O}(\\sqrt{T^{1 + \\frac{d}{2\\nu + d} \\cdot \\frac{2\\nu + d - \\nu^2}{2\\nu + d}}}) $ regret, which is strictly tighter than $\\tilde{O}(T^{\\frac{\\nu + d}{2\\nu + d}}) := \\tilde{O}(\\sqrt{T^{1 + \\frac{d}{2\\nu + d}}})$ regret provided by [Srinivas et al., 2010].\n\nWe focused on the \\$\\tilde{O}(\\sqrt{T})\\$ case in the main presentation for simplicity. Still, as the reviewer points out, this may have caused some confusion about whether the smoothness assumption is strictly necessary. We will therefore clarify this point in a revision by adding remarks to Theorem 3.\n\n\n**Q. Can the authors elaborate on why the proof technique used in Section 3.2 does not extend to GP-TS, in contrast to GP-UCB?**\n\nThe primary reason we can not extend our analysis to GP-TS is due to the unknown dependence of the constants in Lemma 2 on $\\delta\\_{GP}$. In Bayesian analyses of GP-TS (e.g., [Russo & Roy, 2014]), the expected regret is typically considered, which requires understanding how the regret scales with respect to the confidence level $\\delta\\_{GP} + \\delta$. However, because the dependence of the constants in Lemma 2 on $\\delta\\_{GP}$ is unknown, such an analysis becomes technically challenging. To the best of our knowledge, no existing work in the literature has discussed this dependence, and therefore, within the limits of currently known theoretical tools in the Bayesian optimization field, our proof techniques cannot be straightforwardly extended to GP-TS. This issue is discussed in detail in Lines 250-264 of the main text.\n\n- Russo, D., & Van Roy, B. (2014). Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4), 1221-1243.\n\n**Q. Can the authors comment on the noise-free setting? How would the results change if the noise variance were zero?**\n\nRegarding the noise-free setting, at least one can reduce the analysis to that of the standard noisy GP-UCB and recover the same regret rate we establish. This can be done by considering a fixed, small positive noise variance in the GP prior and using the monotonicity of the posterior variance. This reduction has been analyzed in the frequentist setting (e.g., [Lyu et al., 2019]) and is also applicable to the analysis in the Bayesian setting. On the other hand, recent works in the frequentist GP-bandit literature have shown that one can achieve stronger regret by letting the noise variance \\$\\sigma^2 > 0\\$ decay with the time horizon $T$ (e.g., [Flynn & Reeb, 2024; Iwazaki & Takeno, 2025; Iwazaki, 2025]). Combining such an approach with our analysis would require a nontrivial investigation into how the information gain behaves under the decaying noise variance parameter of GP. We believe that integrating our theory with existing noise-free analyses such as [Flynn & Reeb, 2024; Iwazaki & Takeno, 2025; Iwazaki, 2025] is a promising direction for future work.\n\n- Lyu, Y., Yuan, Y., & Tsang, I. W. (2019). Efficient batch black-box optimization with deterministic regret bounds. arXiv preprint arXiv:1905.10041.\n- Flynn, H., & Reeb, D. (2024). Tighter confidence bounds for sequential kernel regression. arXiv preprint arXiv:2403.12732.\n- Iwazaki, S., & Takeno, S (2025). Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance. In Forty-second International Conference on Machine Learning.\n- Iwazaki, S. (2025). Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free Gaussian process bandits. arXiv preprint arXiv:2502.19006."}, {"review_id": "v8NSU1oc3l", "reviewer": "Reviewer_Mw5W", "summary": "The paper presents an improved regret bound for the famous GP-UCB algorithm under Bayesian setting (i.e. Gaussian-Process Bandits). While standard GP-UCB uses the worst-case maximum information gain (MIG), corresponding to the scenario where the algorithm always queries the maximum variance, the paper observes that this worst-case bound will be very loose in the later stage of optimisation, where the algorithm queries point around the optimum. Authors split the total regret of the algorithm into two parts and show that the regret of this \"later\" stage asymptotically dominates the regret of the \"early\" stage. Then, due to the fact that the radius of the region in which the algorithm queries points in the \"later\" stage is smaller than that of full domain, this results in substantial reduction in MIG. Importantly, the resulting bound for SE kernel does not depend on dimensionality (previous bound had exponential dependance) and for the Matern kernel, the dependance of the bound on the dimensionality is significantly improved.", "questions": "- The authors present a very detailed analysis regarding the MIG in the reduced search space. I wonder is it really necessary to go through it and instead think about reducing the search space as increasing the length scale. Clearly if the radius of input space shrinks from $1$ to $\\eta < 1$, then we could define a GP on the original space with radius $1$ with a longer length scale $\\hat{l} = \\frac{l}{\\eta} $ and then map the points from the reduced space to the original space as $\\hat{x} = \\frac{x}{\\eta}$. We can easily check that for a stationary kernel $k_{\\hat{l}}(\\hat{x},\\hat{x}^\\prime) = k(\\frac{\\hat{x}}{\\hat{l}},\\frac{\\hat{x}^\\prime}{\\hat{l}}) = k(\\frac{x}{l},\\frac{x^\\prime}{l}) = k_{l}(x,x^\\prime)$ and thus $\\max_{x:||x||\\le \\eta} \\sigma_{l}(x)  = \\max_{\\hat{x}:||\\hat{x}||\\le 1} \\sigma_{\\hat{l}}(\\hat{x})$. We could then just plug the MIG bounds with explicit dependence on lengthscale [1,2] and obtain the results that $\\gamma_T(\\{x: ||x||\\le \\eta\\}) = \\eta^d \\gamma_T(\\{x: ||x||\\le 1\\})$, which I believe is much stronger than $\\frac{1}{\\log^d(\\frac{1}{\\eta})}$ that authors derive. Is the analysis above correct for the problem setting authors consider? If so, would it make your final bound even stronger?\n\n- Is it correct to think that the proposed result effectively says BO can \"escape\" the curse of dimensionality? This seems to contradict the common knowledge. Could authors explain whether this is what their result implies and if so, why it seems to contradict the empirical experience.\n\n- In theorems authors state they treat dimensionality $d$ as constant. However, since the derived results seems monumental it terms of reduced dimensionality dependence, I would like to see the full order scaling with $d$ of the bound. I assume, for large enough $T$ this scaling will be dominated by the stated bound, but it would still give more context if authors were able to provide an explicit bound.\n\n[1] Berkenkamp, Felix, Angela P. Schoellig, and Andreas Krause. \"No-regret Bayesian optimization with unknown hyperparameters.\" Journal of Machine Learning Research 20.50 (2019): 1-24.\n\n[2] Ziomek, Juliusz, Masaki Adachi, and Michael A. Osborne. \"Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal.\" The Thirty-eighth Annual Conference on Neural Information Processing Systems (2024).", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n+ The bound seems monumental, as it significantly improves the dependance on dimension of the problem. Previously it was believed that exponential scaling of the bound with dimensionality for more complex kernels is unavoidable due to the curse of dimensionality. \n+ Although GP-UCB was known for years, it seems like no-one was able to significantly improve on the initial regret bound derived by (Srinivas et al, 2010). The fact that for this relatively simple algorithm one can derive much better regret guarantees than previously thought, is definitely very important to the community.\n+ As far as I understand, the paper also presents the first non-worst case analysis of the MIG, which seems like a very important step for the community that was essentially relying on the worst-case analysis of (Srinivas et al, 2010) for the last 15 years.\n+ I believe due to the novelty of the approach, the work has the potential to inspire a number of follow-up works, rethinking the regret bounds in BO in general\n\nWeaknesses:\n- For Lemmas 1 and 2, authors just state that these properties are existing and known, do not provide any proof for them and just cite other paper. The problem, however, is that none of the cited papers actually proved these properties (to the best of my knowledge), they merely used them as assumptions. As such it would appear, Lemmas 1 and 2 are Assumptions that have to be made for the presented analysis to hold, rather than being results that follow from previous assumptions. I thus believe that these Lemmas should be changed into Assumptions.\n- In Corollary 8, page 23, just above equation 123, authors write $\\gamma_T(\\lambda^2)$. I believe in the adopted notation, $\\gamma_T(\\cdot)$ took a set of points as an argument, but $\\lambda$ is a number, so not sure what is meant by that.\n- (minor) I believe the formula for Matern kernel on page 3 is wrong, I believe the distance between points should be raised to the power of $\\nu$", "was_revised": true, "final_justification": "My main issue was the fact that authors did not provide any reference for Lemmas 1 and 2. With those included, I do not have any serious criticism regarding the paper that was left unanswered, hence I decided to increase my score.", "rebuttal": "Thank you for your overall positive assessments.\n\n**Q. For Lemmas 1 and 2, authors do not provide any proof for them and just cite other paper.  None of the cited papers actually proved these properties.**\n\nWe agree that the referenced prior works do not provide fully self-contained proofs of these points, which may impose a burden on readers attempting to verify the soundness of Lemmas 1 and 2. To address this, we will add clarifications in the revision to specify exactly which parts of the prior works support the claims in Lemmas 1 and 2.\n\n**Regarding Lemma 1:**\n  Lemma 1 holds for stationary kernels of the form \\$k(x, x') = \\tilde{k}(|x - x'|)\\$, provided that \\$\\tilde{k}\\$ is four times differentiable, as shown in Theorem 5 of [Ghosal & Roy, 2006].\n  For the squared exponential (SE) kernel, \\$\\tilde{k}(t) = \\exp(-t/(2\\ell^2))\\$ is clearly infinitely differentiable, and for the Matérn kernel, it is known that if \\$\\nu > k\\$ for some integer \\$k\\$, then the kernel is \\$2k\\$-times differentiable (e.g., see Chapter 2.7 of [Stein, 1999]). Therefore, Lemma 1 holds for SE and Matérn kernels with $\\nu > 2$. These descriptions are also stated in the last parts of Appendix A.2 of [Srinivas et al., 2010].\n\n**Regarding Lemma 2:**\n  The conditions stated in Lemma 2 are discussed in prior works such as [De Freitas et al.,2012, Scarlett, 2018], which confirm their validity for SE and Matérn kernels with \\$\\nu > 2\\$. In addition, we will supplement references to fill in some missing details in these prior works:\n\n  - Property 1 is implied by the fact that the GP sample path has a unique maximizer almost surely under SE and Matérn kernels. This ensures the existence of a \\$\\delta\\_{\\mathrm{GP}}\\$-dependent constant $c\\_{\\mathrm{gap}}$ satisfying Property 1. \nThe fact that GP sample paths under SE and Matérn kernels almost surely have unique maxima is confirmed from existing results, such as Chapter 2.7 of [Garnett, 2023]\n- Property 2 follows from, e.g., the compactness of the domain $\\mathcal{X}$ and the almost sure continuity of GP sample paths. These guarantee that the function values do not diverge on $\\mathcal{X}$, implying the existence of an upper bound $c\\_{\\mathrm{sup}}$ that depends on \\$\\delta\\_{\\mathrm{GP}}\\$. Since GP sample paths are almost surely continuous under SE and Matérn kernels, Property 2 holds automatically in these cases.\n- Properties 3 and 4 are discussed in detail following Theorem 5 of (the arXiv version of) [De Freitas et al., 2012], along with additional references. Like Properties 1 and 2, these properties hold almost surely using constants that depend on any realized sample path, which ensures the existence of constants (dependent on $\\delta\\_{\\mathrm{GP}}$) satisfying Properties 3 and 4 with high probability.\n\n**Referencese**\n- De Freitas, N., Smola, A. J., & Zoghi, M. (2012). Exponential regret bounds for Gaussian process bandits with deterministic observations.\n- De Freitas, N., Smola, A., & Zoghi, M. (2012). Regret bounds for deterministic Gaussian process bandits. arXiv preprint.\n- Ghosal, S., & Roy, A. (2006). Posterior consistency of Gaussian process prior for nonparametric binary regression.\n- Scarlett, J. (2018). Tight regret bounds for Bayesian optimization in one dimension. \n- Stein, M. L. (1999). Interpolation of spatial data: some theory for kriging. Springer Science & Business Media.\n- Garnett, R. (2023). Bayesian optimization. Cambridge University Press.\n\n**Q. Authors write $\\gamma_T(\\lambda^2)...$**\n\n**Q. The formula for Matérn kernel on page 3 is wrong.**\n\nWe correct these typos in the revision. Thank you for pointing these out.\n\n**Q. Could we just plug the MIG bounds with explicit dependence on lengthscale [1,2]  and obtain the stronger results ?**\n\nWe would like to correct a misunderstanding. The existing upper bound of information gain for the squared exponential kernel, $\\gamma\\_T = O(\\theta^{-d} \\ln^{d+1} T)$, is derived under the assumption that the lengthscale parameter $\\theta \\coloneqq 2\\ell^2$ satisfies $\\theta \\to 0$. Consequently, this rate is not applicable to our setting, where we must consider the case $\\theta \\to \\infty$ for the analysis under the shrinking input domain. Specifically, in the proof of Proposition 2 in [Berkenkamp et al., 2019] (Appendix B.1), the validity of Eq. (21) requires that $\\theta$ be upper bounded by some constant $\\theta\\_0$. Therefore, even for the squared exponential kernel, if the input space radius shrinks (i.e., the lengthscale grows), the result $\\gamma\\_T = O(\\theta^{-d} \\ln^{d+1} T)$ from existing work cannot be applied.\n\n- Berkenkamp, F., Schoellig, A. P., & Krause, A. (2019). No-regret Bayesian optimization with unknown hyperparameters.\n\n**Q. Is it correct to think that the proposed result effectively says BO can \"escape\" the curse of dimensionality?**\n\nAt present, our analysis does not circumvent the curse of dimensionality. While we did not explicitly state this due to assuming $d$ is fixed, the implicit constants in our regret bounds do depend on $d$, and this dependence, as in existing GP-UCB results from [Srinivas et al., 2010], may grow exponentially with $d$. Hence, our theorems do not provide guarantees in high-dimensional regimes where $d, T \\to \\infty$. More precisely, as shown in Eq. (103) of the Appendix, if $d$ is not fixed, the joint dependence on $d$ and $T$ becomes $O(\\ln^{2d+4} T + \\sqrt{T \\ln^4 T})$. Thus, in high-dimensional settings with $d \\to \\infty$ (as $T \\to \\infty$), the first $O(\\ln^{2d+4} T)$ term becomes dominant, indicating that our bound is exposed to the curse of dimensionality. That said, our result still improves upon existing bounds by removing the exponential dependence on $d$ from the leading-order term of the regret bound. This makes our result stronger in fixed-dimensional settings. However, unlike existing works for high-dimensional settings that analyze simultaneous limits of $T \\to \\infty$ and $d \\to \\infty$, we do not claim to have resolved the curse of dimensionality.\n\n**Q. I would like to see the full order scaling with $d$ of the bound.**\n\nFor the squared exponential kernel, the joint dependence on $T$ and $d$ can be deduced from Eqs. (103) and (115) in the appendix of our paper, resulting in a regret bound of \\$R\\_T = O(\\ln^{2d+4} T + \\sqrt{T \\ln^4 T})\\$. Furthermore, constants such as \\$C\\_d^{(3)}, C\\_d^{(4)}, C\\_d^{(5)}\\$—which appear in the information gain bound—are also present in the regret bound as implicit constants and may exhibit exponential dependence on $d$, similar to the original analysis by [Srinivas et al., 2010]. Explicitly stating the dependence of these constants on $d$ would clutter the theorem unnecessarily. In fact, most previous works (including [Srinivas et al.,2010]) have chosen to hide the dependence on $d$. Following this precedent, we have opted not to detail the dependence of these constants on $d$ in our statements."}, {"review_id": "H4VB1mFRAZ", "reviewer": "Reviewer_ETNr", "summary": "This paper studies the theoretical performance of the GP-UCB algorithm in Bayesian Optimization, which presents a refined analysis showing that the existing GP-UCB achieves\n$\\tilde{O}(\\sqrt{T})$ regret for Matérn kernels and $O(\\sqrt{T \\ln^{4} T})$ regret for the squared exponential kernel under certain conditions. The core contribution lies in analyzing the actual input sequence generated by GP-UCB rather than relying solely on worst-case information gain bounds, and thus improves the analytical performance of GP-UCB.", "questions": "Could the authors provide more precise characterizations or examples where the realized information gain $I(X_T)$ deviates substantially from $\\gamma_T$​? Are there quantifiable metrics for how close GP-UCB is to the ideal case in practice?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. This paper establishes new high-probability regret bounds for the standard GP-UCB algorithm, which improve over the classic bounds in Srinivas et al. [1] and match or approach state-of-the-art [2].\n\n2. One advantage is that the algorithm analyzed in the paper does not require prior knowledge of regularity constants around the maximizer compared to state-of-the-art [2], making the result more practically relevant.\n\n3.  The presentation is very clear and easy to follow. The core proof  idea of capturing the concentration behavior of the input sequence by GP-UCB is well illustrated.\n\n\n**Weaknesses**\n\n1. While the paper provides a refined regret analysis, the algorithm itself seems to remain the standard GP-UCB without modification. As such, the contribution is best viewed as an analytical extension rather than a methodological advance. It illustrates that an existing algorithm can achieve near-optimal performance under more careful analysis, but does not propose new algorithmic ideas or frameworks.\n\n2. Aside from the regret decomposition built on the core insight of leveraging the concentration behavior of the input sequence under GP-UCB, the overall proof strategy appears to rely heavily on established techniques from prior work. While well-executed, this may limit the broader technical novelty of the paper.\n\n3. The improved bound for the Matérn kernel holds only under specific smoothness conditions (e.g., $2v + d \\leq v^2$, shown in Theorem3), which may not hold in many practical settings, especially in high dimensions.\n\n4. While the paper is theoretical, a small empirical experiment could help illustrate how the actual information gain or input concentration behaves in practice, supporting the core intuition beyond the single example in Figure 1.\n\n[1] Srinivas, Niranjan, et al. \"Gaussian process optimization in the bandit setting: No regret and experimental design.\" ICML (2010).\n[2] Jonathan Scarlett. \"Tight regret bounds for Bayesian optimization in one dimension.\" ICML (2018).", "was_revised": true, "final_justification": "The authors have carefully addressed my questions. They emphasize that their main contribution is the derivation of Lemma 4, which they claim is the first non-worst-case information gain-based regret analysis for GP-UCB. While I'm not a 100% sure of this, this appears to be true and since it has been over 15 years since the original analysis in Srinivas et al. (2010), the contribution could be quite significant.", "rebuttal": "Thank you for taking the time to review our paper. However, we believe that we can resolve the reviewer's concerns that the reviewer raised at points 2-4 in \"Weaknesses\". We hope that the reviewer will reconsider the current score if our comments resolve the reviewer's initial concerns.\n\n**Regarding weakness 2: Aside from the regret decomposition built on the core insight of leveraging the concentration behavior of the input sequence under GP-UCB, the overall proof strategy appears to rely heavily on established techniques from prior work. While well-executed, this may limit the broader technical novelty of the paper.**\n\nOur novel technical contribution is not the regret decomposition but the derivation of Lemma 4, which provides a tighter regret based on a tighter quantification of the information gain terms. To our knowledge, there are no existing results or techniques to obtain such results. To obtain our result, we combine the sample path properties provided in Lemma 2 with worst-case regret upper bounds, leading to the first non-worst-case information gain-based regret analysis in the field. As detailed in Appendix A.1, to our knowledge, no existing work employs the same technical approach, and we believe the novelty in the derivation of Lemma 4 is clear and indisputable.\n\nFurthermore, as Reviewer Mw5W kindly pointed out, it has been over 15 years since the maximum information gain-based analysis for GP-UCB was introduced in [Srinivas et al., 2010], with no major updates to the theoretical analysis for GP-UCB since. Therefore, we believe that the new analytical approach proposed in this paper represents a significant milestone and could serve as a foundation for future refined analysis of BO algorithms.\n\n**Regarding weakness 3: The improved bound for the Matérn kernel holds only under specific smoothness conditions (e.g., $2\\nu + d \\leq \\nu^2 $, shown in Theorem 3), which may not hold in many practical settings, especially in high dimensions.**\n\nThese smoothness conditions are employed to derive upper bounds that match the \\$\\tilde{O}(\\sqrt{T})\\$ expected regret lower bound proven by [Scarlett, 2018], but they are not essential assumptions for the analysis itself. In order to claim $R\\_T = \\tilde{O}(\\sqrt{T})$, the information gain-based term must become polylogarithmic order. For this, we require that the input space over which the information gain is defined decrease sufficiently fast. Here, the decreasing speed of the input domain of the information gain is derived from the worst-case upper bounds of GP-UCB. Therefore, greater smoothness guarantees faster convergence of this input space (more precisely, the decreasing speed of the input domain is governed by $\\eta\\_i$ in Lemma 4, which decays more quickly to zero as the smoothness increases). Based on these observations, to ensure a polylogarithmic information gain in Lemma 4, the input domain of the information gain must shrink quickly such that the effect of the dominant polynomial term of information gain vanishes, which leads to the condition $2\\nu + d \\leq \\nu^2$. These points are also described in Lines 214-215 of the main paper. \n\nOn the other hand, importantly, the analytical framework we propose can still be applied even when the smoothness condition in Theorem 3 is violated. In such cases, although a $\\tilde{O}(\\sqrt{T})$ regret is no longer guaranteed, our result still strictly improves upon the \\$O(T^{\\frac{\\nu + d}{2\\nu + d}})\\$ bound originally provided by [Srinivas et al., 2010]. Concretely, when the smoothness condition is not satisfied, \nthe term \\$\\tilde{O}(T^{\\frac{d}{2\\nu + d} \\cdot \\frac{2\\nu + d - \\nu^2}{2\\nu + d}}) $ in Eq. (63) appears in the regret bound as a replacement for the standard maximum information gain bound \\$\\gamma\\_T(\\mathcal{X}) = \\tilde{O}(T^{\\frac{d}{2\\nu + d}})$ used in existing GP-UCB analyses. \nConsequently, even if the smoothness condition does not hold, \nwe can derive $\\tilde{O}(\\sqrt{T^{1 + \\frac{d}{2\\nu + d} \\cdot \\frac{2\\nu + d - \\nu^2}{2\\nu + d}}}) $ regret, which is strictly tighter than $\\tilde{O}(T^{\\frac{\\nu + d}{2\\nu + d}}) := \\tilde{O}(\\sqrt{T^{1 + \\frac{d}{2\\nu + d}}})$ regret provided by [Srinivas et al., 2010].\n\nWe focused on the \\$\\tilde{O}(\\sqrt{T})\\$ case in the main presentation for simplicity. Still, as the reviewer points out, this may have caused some confusion about whether the smoothness assumption is strictly necessary. We will therefore clarify this point in a revision by adding remarks to Theorem 3.\n\n**Regarding weakness 4: While the paper is theoretical, a small empirical experiment could help illustrate how the actual information gain or input concentration behaves in practice, supporting the core intuition beyond the single example in Figure 1.**\n\nWe provide the additional experimental results, which empirically verify our claim that the information gain of GP-UCB is quite smaller than that of maximum variance reduction beyond the single example in Figure 1.\n\n**Table 1 below**. Average results of information gain under different sample paths.\n We report the information gain of GP-UCB and MVR, averaging over the 20 different runs under different sample paths, using the same settings as in Figure 1 of the main text. In addition, we also report the ratio between MVR and GP-UCB's information gains.\nThe results are reported under the input space $\\mathcal{X} = [0,1]$ with lengthscale parameter $\\ell = 0.1$ and $\\mathcal{X} = [0,1]^2$ with $\\ell = 0.25$. We use the SE kernel, Mat\\'ern 5/2 kernel, and Mat\\'ern 7/2 kernel. In all cases, consistent with Figure 1 in the main text, we observe noticeable gaps in information gain between GP-UCB and MVR, and these gaps diverge as $T$ increases.\n| | T=100 | T=200 | T=300 | T=400 | T = 500 |\n| --- | --- | --- | --- | --- | --- |\n| Matern 5/2 (d=1) MVR | 13.989 | 19.970 | 24.088 | 27.292 | 29.917 |\n| Matern 5/2 (d=1) GP-UCB | 9.839 | 12.829 | 14.428 | 15.563 | 16.381 |\n| Matern 5/2 (d=1) MVR/GP-UCB | 1.422 | 1.557 | 1.669 | 1.754 | 1.826 |\n| Matern 7/2 (d=1) MVR | 13.677 | 19.371 | 23.247 | 26.240 | 28.677 |\n| Matern 7/2 (d=1) GP-UCB | 9.735 | 12.742 | 14.526 | 15.580 | 16.393 |\n| Matern 7/2 (d=1) MVR/GP-UCB | 1.405 | 1.520 | 1.600 | 1.684 | 1.749 |\n| Squared exponential (d=1) MVR | 12.915 | 17.948 | 21.283 | 23.810 | 25.840 |\n| Squared exponential (d=1) GP-UCB | 8.910 | 11.542 | 12.847 | 13.820 | 14.453 |\n| Squared exponential (d=1) MVR/GP-UCB | 1.449 | 1.555 | 1.657 | 1.723 | 1.788 |\n| Matern 5/2 (d=2) MVR | 17.940 | 27.503 | 34.605 | 40.406 | 45.327 |\n| Matern 5/2 (d=2) GP-UCB | 13.015 | 17.152 | 19.630 | 21.322 | 22.572 |\n| Matern 5/2 (d=2) MVR/GP-UCB | 1.378 | 1.603 | 1.763 | 1.895 | 2.008 |\n| Matern 7/2 (d=2) MVR | 17.520 | 26.588 | 33.226 | 38.588 | 43.101 |\n| Matern 7/2 (d=2) GP-UCB | 12.431 | 16.282 | 18.275 | 19.626 | 20.641 |\n| Matern 7/2 (d=2) MVR/GP-UCB | 1.409 | 1.633 | 1.818 | 1.966 | 2.088 |\n| Squared exponential (d=2) MVR | 16.431 | 24.299 | 29.836 | 34.189 | 37.783 |\n| Squared exponential (d=2) GP-UCB | 11.437 | 15.204 | 17.274 | 18.640 | 19.679 |\n| Squared exponential (d=2) MVR/GP-UCB | 1.437 | 1.598 | 1.727 | 1.834 | 1.920 |\n\n\n**Table 2 below**.  90\\% percentile of information gain under different sample paths.\nWe report 90\\% quantiles of the information gain of GP-UCB under 20 different sample paths generated with different seeds, using the same settings as in Figure 1 of the main text. Note that the information gain for MVR is completely determined only by the kernel and input space choice and is the same as those in Table 1 above, since the MVR algorithm is not dependent on the randomness of the underlying function and observation noises in the experiment.\nFrom these results, we can empirically confirm consistent gaps in information gain between GP-UCB and MVR under the sample paths generated with high probability.\n| | T=100 | T=200 | T=300 | T=400 | T = 500 |\n| --- | --- | --- | --- | --- | --- |\n| Matern 5/2 (d=1) MVR | 13.989 | 19.970 | 24.088 | 27.292 | 29.917 |\n| Matern 5/2 (d=1) GP-UCB | 12.110 | 16.764 | 18.720 | 19.964 | 20.965 |\n| Matern 5/2 (d=1) MVR/GP-UCB | 1.155 | 1.191 | 1.287 | 1.367 | 1.427 |\n| Matern 7/2 (d=1) MVR | 13.677 | 19.371 | 23.247 | 26.240 | 28.677 |\n| Matern 7/2 (d=1) GP-UCB | 11.722 | 15.895 | 18.245 | 20.203 | 21.264 |\n| Matern 7/2 (d=1) MVR/GP-UCB | 1.167 | 1.219 | 1.274 | 1.299 | 1.349 |\n| Squared exponential (d=1) MVR | 12.915 | 17.948 | 21.283 | 23.810 | 25.840 |\n| Squared exponential (d=1) GP-UCB | 10.655 | 14.805 | 16.902 | 17.777 | 18.652 |\n| Squared exponential (d=1) MVR/GP-UCB | 1.212 | 1.212 | 1.259 | 1.339 | 1.385 |\n| Matern 5/2 (d=2) MVR | 17.940 | 27.503 | 34.605 | 40.406 | 45.327 |\n| Matern 5/2 (d=2) GP-UCB | 15.764 | 20.887 | 25.024 | 27.206 | 28.872 |\n| Matern 5/2 (d=2) MVR/GP-UCB | 1.138 | 1.317 | 1.383 | 1.485 | 1.570 |\n| Matern 7/2 (d=2) MVR | 17.520 | 26.588 | 33.226 | 38.588 | 43.101 |\n| Matern 7/2 (d=2) GP-UCB | 14.443 | 19.860 | 22.577 | 23.740 | 25.186 |\n| Matern 7/2 (d=2) MVR/GP-UCB | 1.213 | 1.339 | 1.472 | 1.625 | 1.711 |\n| Squared exponential (d=2) MVR | 16.431 | 24.299 | 29.836 | 34.189 | 37.783 |\n| Squared exponential (d=2) GP-UCB | 14.235 | 19.312 | 22.091 | 24.240 | 26.316 |\n| Squared exponential (d=2) MVR/GP-UCB | 1.154 | 1.258 | 1.351 | 1.410 | 1.436 |"}]

Author rebuttal:

Meta-review: This paper improves the regret bound for GP-UCB. This paper fills a significant gap in the literature between known upper and lower bounds. The way the improvement was done avoids the worst-case information gain, which is quite interesting on its own. 

It seems that the paper is following the NeurIPS'25 formatting correctly. The line spacing is too large. Note:
> Use 10 point type, with a vertical spacing (leading) of 11 points

The vertical spacing seems off. Please fix this for the final version.
Decision: Accept (oral)