Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
Authors: Shogo Iwazaki
Venue: NeurIPS 2025 poster ()
Keywords: Gaussian process bandits
regret analysis
near optimality
Primary area: theory

Abstract: We study the noise-free Gaussian Process (GP) bandit problem, in which a learner seeks to minimize regret through noise-free observations of a black-box objective function that lies in a known reproducing kernel Hilbert space (RKHS).
The Gaussian Process Upper Confidence Bound (GP-UCB) algorithm is a well-known approach for GP bandits, where query points are adaptively selected based on the GP-based upper confidence bound score.
While several existing works have reported the practical success of GP-UCB, its theoretical performance remains suboptimal. However, GP-UCB often empirically outperforms other nearly-optimal noise-free algorithms that use non-adaptive sampling schemes.
This paper resolves the gap between theoretical and empirical performance by establishing a nearly-optimal regret upper bound for noise-free GP-UCB. Specifically, our analysis provides the first constant cumulative regret bounds in the noise-free setting for both the squared exponential kernel and the Matérn kernel with some degree of smoothness.

Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
Shogo Iwazaki
LY Corporation
Tokyo. Japan
siwazaki@@ycorppco co.
Abstract
We study the noise-free Gaussian Process (GP) bandit problem, in which learner seeks minimize regret through noise-free observations of black-box objec- tive function that lies in known reproducing kernel Hilbert space (RKHS). The Gaussian Process Upper Confidence Bound (GP-UCB) algorithm a well-known approach for GP bandits, where query points are adaptively selected based on the GP-based upper confidence bound score. While several existing works have reported the practical success of GP-UCB, its theoretical performance remains sub- optimal. However, GP-UCB often empirically outperforms other nearly-optimal noise-free algorithms that use non-adaptive sampling schemes. This paper re- solves the gap between theoretical and empirical performance by establishing a nearly-optimal regret upper bound for frese-free GP-UCB. Specifically, our anal- ysis provides the first constant cumulative regret bounds in the noise-free setting for both the squared exponential kernel and the Matérn kernel with some degree smoothness.
Introduction
This paper studies the noise-free Gaussian Process (GP) bandit problem, where the learner seeks to minimize regret through noise-free observations of the black-box objective function. Several existing works tackle this problem, and some of them [Iwazaki and Takeno, 2025a Salgia et al., 2024] propose algorithms whose regret nearly matches the lower bound of [Li and Scarlett 2024]. For ease of theoretical analysis, these algorithms rely the non-adaptive sampling scheme, whose query points are chosen independently of the observed function values, such as the uniform sampling (Salgia al., 2024] maximum variance reduction [lwazaki and Takeno 2025a]. Although the theoretical superiority of such non-adaptive algorithms is shown, in existing noisy setting literature [Bogunovic al.) 2022, Iwazaki and Takeno 20256 Li and Scarlett [022], their empirical performance has been reported to be worse than that of fully adaptive strategies such as GP upper confidence bound (GP-UCB) (Srinivas al. 2010). Unsurprisingly, we also observe such empirical and practical gaps in noise-free setting, as shown in Figure [ These observations suggest the possibility of further theoretical improvement in the practical fully adaptive algorithm. From this motivation, our work aims to establish the nearly-optimal regret for GP-UCB, which is one of the well-known adaptive GP bandit algorithms, and its existing guarantees only show strietly sub-optimal regret in noise-free setting [im and Sanz-Alonso 2024 Lyu et al. 2019].
Contributions. Our contributions are summarized below:
We give a refined regret analysis of GP-UCB (Theorems and 2 which matches both the cumulative regret lower bounds of [Li and Scarlett 2024 and the simple regret lower bound
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Squared exponential
Matérn (v= 5/2)
Matérn (u = 3/2)
Cumulative regret
HELDS
Cumulotivve regret
-13
PE
PE
GP UCB
GP-UCB
Cumulativee
Number steps
Number steps
Number steps
Figure 1: Empirical performance comparison of GP-UCB and two existing nearly- algo- rithms: random exploration with domain shrinking (REDS) [Salgia et al.] [024] and phased elimi- nation (PE) [Iwazaki and Takeno 2025a]. From left to right, the plots show the average cumulative regret over 3000 independent runs under the squared exponential kernel, Matérn kernel (v 5/2), and Matérn kernel (v 3/2) with d 2, respectively. Here, d and represent the dimension of the input and the smoothness parameter, respectively. Detailed experimental settings are provided in Appendix B
of [Bull 2011 up to polylogarithmic factors in the Matérn kernel. Regarding cumulative regret, our analysis shows that GP-UCB achieves the constant (11) regret under the squared exponential and Matérn kernel with v. The results are summarized Tables and
Our key theoretical contribution is the observed posterior standard deviations (Lemmas 3 by bridging the information gain- based analysis in the noisy regime to the noise-free setting. Furthermore, discussed in Section 3 these results have the potential to translate existing confidence bound-based algorithms for noisy settings into nearly-optimal noise-free variants beyond the analysis of GP-UCB.
upper bounds for the
Related works. Various existing works study the theory for the noisy GP bandits (Chowdhury and Gopalan, 2017, Li and Scarlett 2022, Scarlett et al., 2017 Srinivas et al., 2010 Valko et al. 2013). Regarding noise-free settings, to our knowledge, Bull 2011 is the first work that shows both the upper bound and the lower bound for simple regret via the expected improvement (EI) strategy. After that, the analysis of the cumulative regret shown in [Lyu et al. 2019 with GP- UCB. Recently, Vakili [2022] conjectures the lower bound of the cumulative regret in the prise-free setting, suggesting superior algorithm exists in the noise-free setting. Later, the following work (Li and Scarlet 2024) formally validates the conjectured lower bound of [Vakili 2022 [ Motivated by the lower bounds, several works [Flynn and Reeb 2024 Kim and Sanz-Alome 2024 Iwazaki and
Takeno 2025a Salgia et al. 2024] studied the improved algorithm to achieve superior regret to the result of Lyu et al. 2019]. Although some of them propose the nearly-optimal algorithms [Iwazaki and Takeno 2025a Salgia et al. 2024]. their algorithms are based on non-adaptive sampling scheme, whose inferior performance has been reported in the cxisting work [Bogunovic et al., 2022. Iwazaki and Takeno 2025b Li and Scarlett 2022). Here, motivation is to establish the nearly- optimal theory under the fully adaptive nature of GP-UCB; however, our proof relates to the analysis in [lwazaki and Takeno 2025a for the non-adaptive maximum variance reduction algorithm. Their analysis includes the noise-free setting as a special case and provides nearly-optimal regret under broader varying noise variance settings. However, its applicability is limited the maximum variance reduction algorithm. Our analysis can be interpreted as a refined version of that in [lwazaki and Takeno 2025a by focusing on the noise-free setting. Finally, although our paper studies the frequentist assumption that the underlying function is fixed, our core results (Lemmas) (155 are also applicable to the regret analysis in the Bayesian setting, whose underlying function is drawn from known GP [De Freitas et al. 2012 Grünewälder et al. 2010 Russo and Van Roy 2014a Scarlett 2018 Srinivas et al. 2010
AAthoogh Li and Scarlett [0244] considers the cascading structure of the observation process, the standard noise-free free setting is the special of their setting.

---

Table 1: Comparison between existing noise-free algorithms' guarantees for cumulative regret and our result (adapted from [lwazaki and Takeno 2025a)). ). As with the table [Twazaki and Takeno 2025a]. the smoothness parameter of the Matern kernel and a > 0 in PE are assumed to be y 1/2 and an arbitrary fixed constant, respectively. Furthermore, all the parameters (d, Y, and B) except for T are assumed to be @(1). "Type" column shows that the regret guarantee is (D)eterministic or (P)robabilistic.. Here, a regret bound is labeled "deterministic" if holds for all possible realizations of the inputs, without relying on probabilistic assumptions. Here, Ō() hides polylogarithmic factors in T.
Regret (Matérn) y ==
Algorithm
Regret (SE)
Type
v v<
y
GP-UCB
Lyu et al. 2019
(Vr
yed T 2ved
D
Kim and Sanz-Alons Alonso
2024
Explore- then-Comn-t
d T
Vakiii 2022
N/A
vail
P
Kernel-AMM--U
(nn++1 r)
volte? o T iutebrded?
D
Flynn and Reeb 2024
REDS
N/A
1 T
0 In r)
0 ( r)
P
Salgia et al.
2024
PE
0 (In 7)
Ô r day
IIn2a r)
0 (In T)
D
[wwzaki and Takeno 2025a
GP-UCB
0 (1)
Ô T +
o In
(
D
(Our analysis)
Conjectured Lower Bound
N/A
Ω +
2(InT)
22(1)
N/A
Vakili 2022
Lower Bound
N/A
2
(T")))
22(1)
22(1)
N/A
Li and Scarlett 2024
2
Preliminaries
Noise-free GP bandit problem. We study the GP bandit problem under noise-free observations. Let X C Rd be compact input domain, and consider a black-box objective function : X - R that can only be evaluated point-wise. At each step r E N+, the learner selects a query point 2, E X and observes its function value f(x)). After 7 steps, the performance of the learner is measured using either the cumulative regret R or the simple regret rr, which are respectively defined as follows:
I
Ry = E((x' f(x,), T=1
rr == f(x') f(x'))((()))
(2)
Here, x= arg max / is allobal maximizer, and Ty denotes the estimated maximizer by the algorithm at the end of the final step T.
construct the GP-bandit algorithm, the GP model Rasmussen and Williams 2005) plays central role in balancing the trade-off between exploration and exploitation. First, we adopt a Gaussian process prior with zero mean and covariance (kernel) function k XxX + R. Then, given sequence of queried points X, (æ)..... Ix,) and their corresponding evaluations f(X,) = (f())...... (xx,), the posterior mean (æ X,) and variance o²; of f(x) at a new
Gaussian process model.
point E X are
u(æ; X,) k( &(X,) (,,,:K))__.B88)))))(.X......C,.
(3)
?²;;;; X,) k(x, k ((X,)) K(8()))))))) (I,,))X))))--00,,0000 ((x,,(())))
(4)
where &(X,) [k( 8 is the kernel vector, ((E
is the Gram matrix,
and f(E(X)) = [f()) In the above definition, &(X,) denotes the subset of X, obtained by removing any fully correlated inputs (i.e., with zero posterior variance) with previous ones. Namely, we define E(X,) inductively as E(X,) E(X,1) U (m,) if 2 X, O; otherwise,
3

---

Table 2: Comparison between existing noiseless algorithms' guarantees for simple regret and our result (adapted from [wazaki and Takeno, 2025a ) In the regrets of GP-UCB+, EXPLOIT+, MVR, and GP-UCB, 0 and C > Oare arbitrary fixed constants and some positive constants, respectively.
Algorithm
Regret (SE)
Regret (Matérn)
Type
GP-EI
N/A
0
D
Bull 201
GP-ET with G-Greeyy
N/A
T
Buul
2011
GP-UCE
Lyu et 2019
3ond
D
KKm and SSnn-Alinn Alonso,
2024
Kernel-AMMM-UC
0 Indel
Ö(T arreandedd
D
FFyyn and Reeb
2024
GP-UCB+ EXPLOIT
0 exp
-CT
T Xta
Kim and Sanz-Alonso
2024
MVR
0 exp
-- In T)
D
Iwazaki and Takeno
2025a
GP-UCB
exp (-fCT
σ (
D
(Our analysis)
Lower Bound
N/A
Q T
N/A
Bull 2011
E(X,) E(X,-1). Here, we define E(X,) X Note that if there are no duplications in the input sequence ....... 2,, then &(X,) X, holds under commonly used kernel (covariance) functions, such as squared exponential and Matérn kernels (precisely defined in the next paragraph).
Furthermore, for the ease of notation, we set u(æ; X)= 0 and o²; X) k(x, x) for X = 0.
Kernel function and information gain. the squared exponential (SF) kernel
Regarding the choice of the kernel function, we focus on
| -
ksE 2)) = exp
(5)
20
and the Matérn kernel
21-v <2v [(v)
x
2
12
V2v x
Matté (x. .))
(6)
where é > O and v > 0 are the lengthscale and smoothness parameter, respectively. Furthermore, J, and I' are the modified Bessel and Gamma functions, respectively. These two kernels are commonly used and analyzed in GP-bandits (Scarlett et al. 2017 Srinivas et al. 2010]. The convergence rate of the function estimation GP regression depends on the choice of kernel, which turn affects the resulting regret upper bound. Therefore, to capture the problem complexity in kernel-dependent manner, the following kernel-dependent information theoretic quantity yr (2²) is often employed in the analysis of GP bandits:
yr(2?) = sup
Zy 2 In + K(X,
(7)
where > O and IT are any positive parameter and T x T-identity matrix. respectivel.. The quantity yr (22) is called maximum information gain (MI)) Srinivas et al. 2010 since the quantity In det( Iy -22,,Xr, X7)) represents the mutual information between the underlying function and training outputs under the noisy-GP model with variance parameter 2², The increasing speed of MIG is analyzed in several commonly used kernels. For example, yr O(In (T[nd(((T//3)) (T/2²)) and
(22) = (( THAT) under = kSE and & = kaaén with y > 1/2, respectively (akili et al,
2021e
These orders hold T 00, +

---

Algorithm Gaussian process upper confidence bound (GP-UCB) for noise-free setting.
Require: Compact input domain X c RR, Kernel function k, and RKHS norm upper bound
(0, oo).
1: Xg < 0, B.1212 B.
2: for 11,...... do
3: F; < arg max se x -11 (x; (11))
4: Observe f(x,) and update the posterior mean and variance.
5: end for
Regularity assumption. is hopeless to derive meaningful guarantees without further assumptions about f. To obtain a valid estimate of through the GP-model, we assume that f lies in the known reproducing kernel Hilbert space (RKHS) [Aronszajn, 1950 corresponding to the kernel k and has bounded norm. The formal description given below.
Assumption 1. The objective function f lies in the reproducing kernel Hilbert space (RKHS) associated with known positive definite kernel k X x - R. We assume that k( x) 1 for all a E X. and that the RKHS norm fl satisfies II S B
This is a standard assumption in the GP-bandit literature [Chowdhury and Gopalan 2017 Scarlett
et al. 2017 [rinivas et al.) 2010]. and is leveraged to derive the confidence bound of f Kanagawa
et al. 2018 Lyu et 2019 Vakili et al. 202 Here, RKHS associated with kernel is given as
closure of the linear span: H
H (pre) == {Σ (i n
E R, ()) x (n)
X} [annaaawa et al. 2018 Therefore, intuitively, under Assumption [ can interpret that the basic properties of the objective function f, such as continuity and smoothness, are encoded through
the choice of the kernel function k.
Gaussian process upper confidence bound. GP-UCB (Srinivas al. 2010 is widely used algorithm for the noisy GP bandit setting. Its noiseless variant was proposed by Lyu et al. [019]. and is outlined in Algorithm I Their analysis largely follows the framework developed for the noisy case [Srinivas et al., 2010], but differs in the confidence bound, which is strictly tighter than that in the noisy setting. Although this refinement of the confidence bound leads to superior regret compared with the noisy setting, the resulting regret is still strictly sub-optimal in the noise-free setting. This fact suggests that require the other fundamental modification from the proof in [Srinivas et al. 2010
3 Refined Regret Upper Bound for Noise-Free GP-UCB
The following theorem describes our main results, which show the nearly-optimal regret upper bound for GP-UCB.
Theorem (Retined cumulative regret upper bound for GP-UCB), Fix any compact input domain X c Rd. Suppose B, d, l, and y are fixed constants. Then, when running Algorithm | Assumption 7 the following two statements hold for any T N.:
under
Ifk k KSE, the regret Rr satisfies Ry 0(1).
If k Mater with 1/2, the regret Ry satisfies
o T
if d > v. if d v.
R7
0(n2T)
(8)
0(1)
if V.
The implied constants may depend on B, d, E, v, and the diameter of
Theorem 2 (Refined simple regret upper bound for GP-UCB). Fix any compact imput domain X c Rd. Suppose B, L, d, t, and are fixed constunts. Then, when running Algorithm 7 under Assumption 7 the following two statements hold by setting the estimated maximizer कr as f()):
Øy E
5

---

Ifk KSB, rr = O
O (VT exp (- -3CTd.))
If Matér with 1/2, (
The implied constants depend on B, d, l, and the diameter of X. Furthermore, the constant C > depends on d, t, v. and the diameter of X
Proof sketch. Our key technical results are the new analysis of the cumulative posterior standard deviation Σ/=1 (x,;;X,-1) and its minimum min (zz;;X,,1)) which plays an important role in the theoretical analysis of GP bandits. Indeed, following the standard analysis of GP-UCB, we have the following upper bounds of regrets by combining the UCB-selection rule with the existing noise-free confidence bound (e.g., Lemma 11 in [Lyu et al. 2019 or Proposition [Vakili al.
1a2
RT Σ f(x') f(z') f(x,) s 2B Σ o (æ,; ozz;; X,-),
(9)
:=1
TT min f(x')-(() f((x)) s 2B min or (æy (a=;X,,1)). [E[T]
(10)
re[7]
From the above inequalities, we observe that the tighter upper bounds of Σ/ (x,;; X, -1) and minye[7] or (ay;; X,-)) directly yield the tighter regret upper bounds of GP-UCB. Lemma below our main technical contribution, which gives the refined upper bounds of >x (r (x,; x,)) and el o (z,; X,-))
Lemma (Posterior standard deviation upper bound for SE and Matérn kernel). Fix any compact input domain X c Rd, and kernel function k X x - R that satisfies k(x, x)) S 1 for all E X. Then, the following statements hold for any N+ and any input sequence TI...., By E E
For k KSE, we have
min (a,; = cxp exp (-2 rE[T]
and Σ (1) 0(I).
(1I)
For k kMutém with 1/2, have
min (a,;; X,,1) = 0 ( in inår). tE[T]
(12)
0 T In a)
if v. if d d=v. v. if d d<v.
Σ (ax;;X,-1))
o In
(13)
0(1)
The constant C > and the implied constants depend on v, and the diameter of X.
The full proof of Lemma is given in Appendix A.2 We will also provide the proof sketch in the next section. Combining the above equations with Eqs. and (T)). we obtain the statements in Theorems
2
As described in Section 3.1 the constant C arises from the implied constants in the upper bound of MIG (Vakili al. 2021c which depends d, E, and the diameter of X
*Our results (Thoorems I and 2 hcavily rely on the upper bound of the MIG provided /akilli et al,
2021c). which relies on the uniform boundness assumption of the eigenfunctions of the kernel. Thh validity
of the uniform boundness assumption is doubted by Janz 2022 under general compact input domain X.
Although our results are based the upper bound of MIG Vakili al. 2021c,. our proof strategy is also applicable for deriving rearly-optimal regrets based on recent analysis MIG [wazaki] 20255 without the uniform boundness assumption. Specifically, then, the orders of the resulting regrets are the same as those in Theorems and 2 for KSE and kMacu with df < v. As for the case under & &aaáro with d 2 v. we can also obtain Ry O d-))d and OT vid), while they suffer from additional polylogarithmie terms.

---

Relation to the existing research in noise-free sefting, by the existing noise-free setting literature (Li and Scarleti 2024 Vakili [022]. First, Vakil [022]
Lemma 3 resolves the open problem raised
conjectured that the quantity 2/ (2,; x)) under k kaatém can attain the following upper bound:
0 (r("")) 0 (l
if d v, if d v, if d <.
Σ o oa 11)
(14)
((1)
Although the above conjecture partially validated under a specific non-adaptive algorithm [Li and Scarlett [2024] [wazaki and Takeno 2025a Salgiaa et al. [024]] the correctness of this conjecture under a general algorithm has been an open problem [Li and Scarlett, 2024]. Lemma 3 answers this
open problem with Eq. [3) which matches conjectured upper bound up to polylogarithmic factors.
Generality of Lemma We would like to highlight that Lemma always holds for any input sequence, in contrast to the existing algorithm-specific upper bounds wazaki and Takeno 2225a Salgia et al. 2024). Since the cxisting noisy GP bandits theory often leverage the upper bound of [ o (zy; x,) or Σ/=1 -1)) from [Srinivas al. 2010], we expect that many existing theoretical results in the noisy setting can be extended to the corresponding noise-free setting by directly replacing the existing noisy upper bounds of (Srinivas al. [010] with Lemma 3 For example, the analysis for GP-Thompson sampling (GP-TS) [Chowdhury and Gopalan 2017 7J. GP-
UCB and GP-TS under Bayesian setting [Russo and Van Roy 2014a| Srinivas et al. 2010)) contextual setting Krause and Ong 2011). GP-based level-set estimation [ootovos al. 2013 ]. multi-objective setting Zuluaga et al.
2016 robust formulation [Bogunovic et al. 2018 and so on.
Lemma Bs limited to the SE and Matérn kernels. However, our stratte in [.I]ain be applied to any kernel function if we know the joint dependence of T and the noise-variance parameter 2 in MIG. For example, we can apply our proof strategy for the neural tangent kernel (NTK) (Jacot et al. 2018) by leveraging the existing upper bound of MIG under NTK [Iwazaki and Suzumural [024 Kassraie and Krause 2022 Kassraie et al. 2022 Vakili et al. 2021b]. We expect that such an extension will benefit the theoretical guarantees of neural network-based bandit algorithms under noise-free setting and will be one of the interesting research directions.
Extension to other kernel functions.
3.1 Proof Sketch of Lemma
In this subsection, describe the proof sketch of Lemma while we give its full proof in Appendix A.2 Below, to prove Lemma 3 we consider the more general lemmas, which bridge the MIG to noise-free posterior standard deviations.
Lemma 4 (General upper bound for the minimum posterior standard deviation). Fix any imput domain X and any T 2 2. Let (27) be a strictly positive sequence such that y (2)) - 113 for all 1 2 T. Then, min or (Z,;; X,-1) S dr holds for any T 2 T and any sequence $1...., 2r E Lemma 5 (General upper bound for the cumulative posterior standard deviations). Fix any input domain X, any T 2 2, and any kernel function k X x X R that satisfies k k(æ, x) for all X. Let (24) be a strictly positive sequence such that y, (d?) (131)/3 for all 2 T. Then, the following inequality holds for any T E N. and any sequence 11...... ..,.... 27 E X:
I Σ
T
ST 1+ Σ d
(15)
These lemmas hold for any kernel k satisfying k(x. x) S 1, which includes most standard kernels after normalization. Roughly speaking, the above lemmas suggest that min (2,; X,-1) x dy and ΣT= oæ,;; z ET1 A, holds as far as the corresponding MIG y, (2,) does not increase super- linearly. Note that the MIG y, (4?) monotonically increases as 2² decreases, which implies that the tightest upper bound is obtained by setting X3 as yr (2²) (1/3))3. By relying on the existing upper bound of MIG (akili et al. 2021c we can confirm that the condition Vi 2 T, (23) (t 1)/3
7

---

of the above lemmas holds with ,द (1 exp(-C1 and = - (In/) ) for k = kSF and
k Mattém, respectively. Here, the constants C and T are determined based on the implied constant of the upper bound of MIG. See Appendix(A.2foor details. Lemmaßfollows from the aforementioned
setting of 27. and Lemmas 4 and 5 Below, we give the proofs for Lemmas 4 Handd
Proof of Lemma 4 Instead of directly treating the noise-free posterior standard deviation, we study its upper bound with the posterior standard deviation of some noisy GP model. Here, let us denote of (x; X,-) as the posterior variance under the noisy GP-model with the strictly positive variance parameter 2² > O, which is defined as (2; = k(x, k(x, X,-
- X1-11)
(16)
Since the posterior variance monotonic for the variance parameter, we have o ( X11) E 2..
(m,;X,-1) for all I E [7]. Next, we obtain the upper bound of o² (æ;; x1) based on the 2
following lemma, which is the main component of the proof of Lemmas 4 and 5
Lemma 6 (Elliptical potential count lemma, Lemma D.9 in (lynn and Reeb 2024 Lemma 3.3
in Iwazaki and Takeno 2025a ). Fix any T E Nr, any sequence ........ 2r X, and A > O. Define as 7 fr E [T] (
x x1-) > 13, where X,-1 (T)...... 11-)). Then, the number of elements T satisfies IT| S (y².
The above lemma implies that the set T == {r E [T] xg X,-) s Ar} satisfies 17
[[7] T 2 T 3yr(1f). Therefore, for any T 2 1 2 I holds from the condition yr yr( 5
(T- 1)/3. This implies there exists some E [T] such that oz7; X--1) x2.. (a7, X7-1) A7; therefore, mi] o (x olz 1-1) s dr holds for all T 2 T.
Proof of Lemma 5 Overall, the proof strategy of this lemma is to repeatedly apply the proof of
Lemma 4 by leveraging the monotonicity of the posterior variance against training inputs. First, if
T < T, Eq. 15) is clearly holds from the assumption Væ e X, kar, x)) s 1. Hereafter, we focus
on T 2 T. By following the same argument of Lemma we can confirm that there exists the
index T S T such that o (z;;," -1) 1) S x2 (Rir (i dr. Here, we define the new sequence
(xx) (T-1) -e] as the sequence that 27 is eliminated from (æ)))t(z1; namely, we set v; (T-1) 111 < Tr, I[ E2,1 for any I E [T- 1]. Furthermore, we define x(T-1) (x= (T= x, (T (1-))).
From this construction of x (T-1), can observe the following two facts:
For any f < fr, we have (xx;;X1-1) = o (2, (T-)) ((T-":((T--1) x(_""). since x; x1 (T-1) x
22 and
((T-1) 1-1 X,-1-
For any f > Tr. we have oxx;; X,-1) S o
(T-1) (0 2 (T-1); x((="))) since x,- D, and
x(r-") X,- from the definition of x (T-1)
From the above two facts, we have
Σ (a):
Σ (xx [E(
Σ r ( /E[7-1]
(T-1), ((--))
x(T-1)) + d7.
(17)
Then, we observe that there exists the index 7--1 S T I such that o (T((T-)), x(r-1)) S
Fr-1
TRp_, (x. (7-1), (I(-1) ( S Ar-1 by the application of Lemma ofoo the new sequence (x) (T-1) Again,
Fr-1
by setting x; (T-2) 1l1 < < + 1lt Fr
(T-T) and ((T-2) (x) (T-2) x
(T (T-2))
for any 1 E [/' - 2], we have
Σ o [
(T-1), (T-1)) 1-1
Σ
o 00 (Tx (T-))) + d
s
(18)
rE[T-1]
Σ o x
(T-2), x( + ---1-
(19)
f-1
re 21
8

---

We can repeat the above arguments until we reach 7 - 1. Then, the resulting upper bound becomes
Σ oa 111
Σ a
7-
x 11)) Σ
4 ST - 1+ Σ A
(20)
T=T
1=7
where the last inequality follows from o (T-)) x x(T-1))
s k ((a(T-1) 11
(T-1)
(T-1)) S 1.
1-1
4 Discussion
Below, we discuss the remaining open questions in the noise-free setting.
Lower bound for squared exponential kernel. While our results establish near-optimality for the Matérn kernel, the optimal simple regret rate under the SE kernel remains unknown. Since the existing upper bound O(Id+11) 7) for MIG (Vakili et al. 2021c] does not matches (In4/2 7) lower bound we conjecture that further room for improvement also exists in the noise-free setting. Specifically, the exponent d 1 of the MIG is reflected in the denominator the exponential factors in our regret Eq. ( Therefore, we conjecture that O(VT cxp(-CT2/d) regret is the best guarantee for the simple regret in the SE kernel.
Constant cumulative regret in Bayesian setting. By using Lemma we can prove the same cumulative regret as Eq. (T) up to a logarithmic factor in noise- free GP-UCB or GP-TS the Bayesian setting [Srinivas al. 2010 Russo and Van Roy 2014a] However, the confidence width parameter in the Bayesian setting must scale as B 12 O(VIn to
construct a valid confidence bound. This leads to O (I regret in SE and Matérn kernel with d y under the Bayesian setting, whereas the frequentist counterpart guarantees constant (1) regret (Theorem D]. This is counterintuitive, since, as shown in existing analyses for noisy settings (Scarlett 2018 Srinivas et al.] 2010), Bayesian regret often achieves smaller values than the worst-case regret in the frequentist setting. An interesting direction for future work is to either design Bayesian algorithm with constant regret or prove an 22 T) lower bound in the Bayesian setting.
GP-UCB in simple regret minimization. Our analysis shows that GP-UCB achieves nearly optimal simple and cumulative regrets under the Matérn kernel. On the other hand, several algorithms have been proposed that focus minimizing the simple regret. One of the most well-known examples is EI, which greedily minimizes the simple regret under a Bayesian modeling assumption of GP, and has demonstrated good empirical performance in various applications [Brochu et al. 2010 Snoek et al. 2012). Based on our theoretical results. there exists algorithm that achieve strictly better simple regret than that of GP-UCB in the worst-case sense. Nevertheless, as far as we are aware, GP-UCB tends to exhibit inferior empirical performance compared to El in simple regret minimization. See, Appendix B.2 It remains unclear whether this phenomena arises from constant factors or additional logarithmic terms in the theoretical regret upper bounds, whether it reflects more fundamental gap between worst-case analysis and empirical behavior.
5 Conclusion
This paper shows that GP-UCB achieves neariy-optimal regret by proving new regret upper bound for noise-free GP bandits. The key theoretical component of our analysis is a tight upper bound on the posterior standard deviations of GP tailored noise-free setting (Lemma 3 As remarked in Section 3 Lemma 3 can be applicable beyond the analysis of GP-UCB. Specifically, we expect that many existing theoretical results for noisy GP bandit settings can be translated to the noise- free setting by replacing the existing noisy upper bound of the posterior standard deviations with Lemma 3 For this reason, we believe that our result marks an important step toward advancing the theory for noise-free GP bandit algorithms.
5 This derived from the best- known cumulative regret upper bound Rī ((vT)T(1))) Li and Scarlett
2022
Salgia et al. 2021 Valko et al. 2013 and lower bound Ry = 22(V 4/2 /2 T) in the noisy setting (Sarlett
2017].

---

References
Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office. 1968.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337-404, 1950.
Iliaa Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. In Proc. Neural Information Processing Systems (NeurIPS), 2018.
lija Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett. A robust phased elimination algo- rithm for corruption-tolerat Gaussian process bandits. In Proc. Neural Information Processing Systems (NeurIPS), 2022.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application active user modeling and hierarchical reinforcement learning. 2010.
arXiv preprint arXiv:
Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 2011.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi- armed bandits. In Proc. Interna- tional Conference on Machine Learning (ICML), 2017.
Nando De Freitas, J. 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 Machine Learning, page 355- Omnipress, 2012.
Hamish Flynn and David Reeb. Tighter confidence bounds for sequential kernel regression. arXiv preprint arXiv:2401.1703. 2024.
Alkis Gotovos, Nathalic Casati, Gregory Hitz, and Andreas Krause. Active learning for level estimation. In Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, 2013.
Steffen Grünewälder, Jean-Yves Audibert, Manfred Opper, and John Shawe-Taylor. Regret bounds for Gaussian process bandit problems. Proc. International Conference on Artificial Intelligence and Statistics (AISTATS). JMLR Workshop and Conference Proceedings, 2010.
Shogo Iwazaki. Improved regret bounds for Gaussian process upper confidence bound in Bayesian optimization. arXiv preprint arXiv:2506.013 2025.
Shogo Iwazaki and Shinya Suzumura. No-regret bandit exploration based on soft tree ensemble model. Advances in Neural Information Processing Systems, pages 20982-21033, 2024.
Shogo wazaki and Shion Takeno. Improved regret analysis in Gaussian process bandits: Optimality for noiseless reward, RKHS norm, and non-stationary variance. Proc. International Conference Machine Learning (ICML), 2025a.
Shogo wazzak and Shion Takeno. Near-optimal algorithm for non-stationary kernelized bandits. In The 28th International Conference on Artificial Intelligence and Statistics, 2025b.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and
generalization in neural networks. Advances in neural information processing systems, 2018.
David Janz. Sequential decision making with feature- -lieer models. PhD thesis, 2022.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv: 02582 2018.
Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, pages 240-278. PMLR, 2022.
10

---

Parnian Kassraie, Andreas Krause, and Iija Bogunovic. Graph neural network bandits. Advances in Neural Information Processing Systems, 2022.
Hwanwoo Kim and Daniel Sanz-Alonso. Enhancing Gaussian process surrogates for optimization and posterior approximation via random exploration. arXiv preprint 17X1: 2024.
Andreas Krause and Cheng Ong. Contextual Gaussian process bandit optimization. In Proc. Neural Information Processing Systems (NeurIPS), 2011.
Zihan Li and Jonathan Searlett. Gaussian process bandit optimization with few batches. In Proc.
International Conference Artificial Intelligence and Statistics (AISTATS), 2022.
Zihan Li and Jonathan Scarlett. Regret bounds for noise-free cascaded kernelized bandits. Transac-
tions on Machine Learning Research, 2024.
Yueming Lyu, Yuan Yuan, and Ivor W Tsang. Efficient batch black-box optimization with determin- istic regret bounds. arXiv preprint arXiv: 1004, 2019.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-1243 2014a.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Advances in neural information processing systems, 27, 2014b.
Sudeep Salgia, Sattar Vakili, and Qing Zhao. A domain-shrinkin based Bayesian optimization algorithm with order-optimal regret performance. In Proc. Neural Information Processing Systems (NeurIPS), 2021.
Sudeep Salgia, Sattar Vakili, and Qing Zhao. Random exploration in Bayesian optimization: Order- optimal regret and computational efficiency. In Proc. International Conference on Machine Learning (ICML), 2024.
Jonathan Scarlett. Tight regret bounds for Bayesian optimization in one dimension. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4500-4508. PMLR, 2018.
Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds regret for noisy Gaussian process bandit optimization. Proc. Conference on Learning Theory (COLT), 2017.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. In Proc. Neural Information Processing Systems (NeurIPS), 2012.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimiza- tion in the bandit setting: No regret and experimental design. In Proc. International Conference on Machine Learning (ICMI.,, 2010.
Sattar Vakili. Open problem:
Regret bounds for noise-free kernel-based bandits. In Proc. Conference on Learning Theory (COLT), 2022.
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), 2021a.
Sattar Vakili, Michael Bromberg, Jezabel Garcia, Da-shan Shiu, and Alberto Bernacchia. Uniform generalization bounds for overparameterized neural networks. arXiv preprint 1rXi:2209900009, 2021b.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaus- sian process bandits. In Proc. International Conference on Artificial Intelligence and Statisties (AISTATS), 2021c.
11

---

Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, UAI'13, 13, page 654 663. AUAT Press, 2013.
Marcela Zuluaga, Andreas Krause, and Markus Püschel. e-pal: An active learning approach to the oulti-objective optimization problem. Journal of Machine Learning Research, 2016.
12

---

A Proofs for Section 3
A.1 Proof of Theorems and 2
We first formally describe the existing noise-free confidence bound.
Lemma 7 (Deterministic confidence bound for noise-free setting, e.g., Corollary 3.11 in Kanagawa ct al. 2018 Lemma in [yu et al. 2019], or Proposition in [Vakili et al.] [2021a]. Suppose Assumption 7 holds. Then, for any sequence (æt)reN, on X, the following statement holds:
Vt E+, Vx E E. (f(x) ,(x;X, X,) (x;
(21)
where X, (x)......E)) Rt).
Although the remaining parts of the proofs are well-known results of GP-UCB, we provide the details for completeness. Based the above lemma, we show Eqs. (9) and (TO). Regarding Rr, have
Ry Σ f(x") - f(())
(22)
[ X,) Bor(x";;,,) [a(æ;; X,) - Bar X,)]
(23)
1=1
>
[M(a;; X,) Bor(x;; [u(x;;X)) Ber X,))
(24)
[=1
2B o (x);
(25)
where the first inequality follows from Lemma and the second inequality follows from the UCB- selection rule for æ,. Similarly to the case of cumulative regret, we have
= f(x') ) f(ār)
(26)
$ min f(x")(x))))) - f(x))
(27)
x([
s min [u(="; ;X) + (o X,)] [μ(œ;; X,) Bu (ox;;; rc[7]
(28)
s min [μ(æ;; X,) + (x X,) - [μ(æ;; X,) (x, rc[7]
(29)
= 2B min (x);
(30)
re[7]
where the first inequality follows from the definition of Ty. Finally, the desired results are obtained by combining the above inequalities with Eqs. (3).
A.2 Proof of Lemma
We prove the following Lemma against constant factors.
8 which is a detailed version of Lemma including the dependence
Lemma (Detailed version of posterior standard deviation upper bound for SE and Matérn kernel), Fix any compact input domain X c Rd, and and kernel furnttiiittiionn k X XXX - R that satisfies k(x, x)) s 1 for all x E X. Furthermore, let CSE, CMati ASE AMat > 0, SEF T Ma 2 be the constant that satisfies
VA (0, 2 T (2?) S CsE(In(1/2²)dd+ and Vd E (0.2Mal.V 2 TMax y, (22) s Cma (1/ sita (In(1 (2)) stia for k KSE and k k respectively. Then, the following statements hold for any T E N, and any input sequence EI...., I7 E X:
TThe existence of these constants are guaranteed by upper bound of MIG [Vakili al. 2021c which 2v
shows (r()²) OIId=I (T/2)((T and (T?) ((TT/2)) seaa In 3 (T/2²)) (as T - oo, 0) under k = kSE and = Maacn, respectively. Note that these constants do not depend on T, but may depend on d. t, and the diameter of X.
13

---

For k = kSE.
if 7 T
min o(x;;; < vT VTeepp exp (- ( SE[7]
(31)
if 7 2 TSE.
Σ oa x1) s TSE (d (d+1) 1) x(11)
CSE 2
3d +3
(32)
where ÜSE = (6CsE) - मत and SE max T(a) [[d + 1)
/Cst-1 SE
13 with T
SE
SE
min(T EN Vr T, rexp 1
For k = kMaté with v 1/2.
if T Mats if T 2 Maa.
min -(11; s SE[T]
22/2 a (In
(33)
T Mat C:122 dtv TT (In ()n
if d V, if d = v, d <
T or (a x,) v
T Mat + Ci T)²
(34)
T Mat + G1/2 +(2+1)
Mat (g-1)
max (2+ 2/) 3/4 (6C 1+ ++ and T max(4, T I(d) with T [(Al min e N. Vr T, CMall 3/ (Inr) 3े s M
where
Caat
The upper bound in Lemma 8 depends on the quantities ČSE. SE. EMas. Mai > O, which are related to the implied constants in the upper bounds of the MIG. However, under the fixed d, E, and v, CSE. 0 are also constants, which implies the conclusions of Lemma
TEE CMau. Mat
Proof of Lemma 8 When kSE. we set A? r exp(( T TsE == max I(D [(d 1)d+1/ /Cd+ '1 1). From the definition of 27 and TSE, for any T TSE, have
d+1
(x3) CSE In f
(35)
exp (Tatt के
)att d+l
CSE
(36)
CsE Cs ld+1
/.
(37)
Furthermore,
Fdd+1 CSE SE
1-1
(38)
3CSel
(39)
60SE
0 ČSE S
(40)
60SsE
where the second line follows from the inequality / 2 1/2 for 2 TSE 2 2. By noting the definition of CSE. we conclude that Vi 2 TSE y, (43) s CSE ld+1, / i l from the above inequalities,
SE which implies that Lemmas and hold with x2 exp( al)) and == T Eq. (T directly
follows from Lemma 4 using the fact a (x,;; X, 11 k(æ,, x,) 1. As for Eq. 32 Lemma
14

---

implies
T
Σ o & TEE
Σ 4
(41)
s=
$ TSE {'
Vi exp
CsEt
1
CsEt aों dr
(42)
TsE
[
1 C-Errdd dr,
S TE
Vi exp
(43)
where the second line follows from the fact that the function g(1) == I eexp(- (exp(-CsE!/ld+t)) is non- increasing f TSE 1. In fact, have
g'(1) = exp (-CsEr (1-
ESE d +
(44)
which implies g'(1) S O for TSE -
(d 1) /Cdel
To bound the quantity
Si Vrexp (-1Cserati dr, we further derive the following upper bound with = CSE/2 > 0:
S (Texp(-Cratn dr c
CrIiide
(c)
(d+1//2 e e"(d+) 1) (c)
1 du (: (+1((++))
(45)
(d + -)CC-13443))
edu u (3d41)/2 e "du
(46)
C
(d + I)C (3d43)/2
u1 (3d+1))22 "du
(47)
3d +
= (d + I)C (3d+3)/22
(34-3))
(48)
2
Next, when k kMatérn: set 13 "Mai!" (In 3 and 7 max T Mar ( with Emu 3
12+ + 2/) (6CMa) Then, for any 2 Mat. holds that
(2,) z CMat
In
(49)
2
CMat C aedd
((In r)
2r Seea
In
Maad"
detr
2v #) (Inr)
Ired
(50)
Mat
CMal C 2ord (In
In 5--1
d + 2v
(In
2y
(In Inf)
3red
(51)
Mal
d
d
2v Drrd
2d 2v
CMat C- 2rid
r(I
(Inr)
(52)
(2d 2v
20ed
CMatt C Ived
(53)
Mat
d
where the fourth line follows from CMat
1 = CMal 2 1/1 In( (-1))) s for/ 2 1. Furthermore,
2v Innd
2v Iord
d
12d 2v
1-1 1
2d
2v
CMat Mat
C Foad
{
3CMat
C Sred Mat
(54)
3
1+
y/2
3CMal
2v
0
2++ +
S CMat
(55)
f 1
d
= (6C 1+
2+ 2v
$ C
(56)
15

---

Combining the above inequalities, we can confirm Vr 2 Mat. 7x(2 3 Therefore, Lemmas
and holds with 2? = CMat á (In मे and T Mat- Here, Eq. 33 is the direct consequence of
Lemmas 4 As for Eq. (34) we have
Σ
o (x s Mat +
4
(57)
1=1
t=T
Mu
7 Mat C//2 ['
1 (
(58)
Muu-1
J, (In
Mat +
Mat
(59)
where the second line follows from the fact that the function g(1) == - (In 3ेr is non-increasing
for 2 Mat 1 3> Indeed, we have
g'(1) 2v - ((nn))
(60)
which implies g'(1) & for 1 2 e. The desired results are obtained by bounding the quantity J (1an) dr from above. When d > have
J (1rr) (ITT)å [ r = (InT)²
d de 7
S d (InT)².
1
(61)
d-v
1 d-v
When d=
frr (ann)ads (In')) S," r ridd= (1n7)
(62)
When d < we have
J r 3 (In))
e du u In.)
(63)
$ (3
(64)
r 1)
(65)
3+1
where the last line follows from the standard property of Gamma function: l-d e-
e- a du
[[b +
1)/2h+1 for any > and b - (e.g., Equation 6.1.1 in [Abrmmoiitz and Stegun 1968
B Detail of the Experiment
B.1 Experimental settings for Figure
We give the detailed experimental settings used to plot Figure
Objective function. We define the true underlying objective function as f() I (x)()), ,)), where Cm Uniform(I-1,.... 1J) and x (m)) ~ Uniform( [0, 1J3) are inde- pendently generated random variables. Note that by the definition the RKHS, f e H₁
with |1/1| 5 E CmCak k (m)) ( (m)).
Kernel. We fix the lengthscale parameter as f = 0.25 in all experiments. We use the same kernel function in the GP-model used the algorithms as the kernel leveraged to generate the objective function.
Other parameters. We define the input domain X as the uniformly aligned 50 x 50 grid points on [O, 1J2. all algorithms, we set the confidence width parameter /1 to the exact RKHS norm. Furthermore, we set the initial batch size in PE and REDS as 5. Finally, we define the common initial point œ1 for all the algorithms as the uniformly sampled point from X.
In the above-described setting, conduct experiments with 3000 different seeds.
16

---

Matérn (v= 3/2)
Matérn (v = 5/2)
100
GP-UCB EI
GP-UCB
Ei
Simple regret
Simple regret
18"3
1074
20"
10
101
20
Number of steps
Number of steps
Figure 2: Comparison between GP-UCB and in simple regret minimization over 100 different seeds. We conduct experiments with Matérn kernel under = 3/2 (left) and v = 5/2 (right).
B.2 Comparison between El and GP-UCB
Under the same setting as the previous subsection. we also compare GP-UCB ' empirical performance with that of El in simple regret minimization. Figure B.2 shows the results. We can confirm that, although GP-UCB achieves nearly-optimal worst-case regret, the empirical performance of GP-UCB consistently worse than that of El.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide "contribution" paragraph in the introduction, which summarizes
our main contributions. The generality of our results is also discussed in Section 3
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 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.
It 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 remaining open questions that this paper cannot resolve.
Guidelines:
The answer NA means that the paper has 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 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-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-te tetecttt--tetttt 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 be used by reviewers as grounds for rejection, a 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 an 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 a complete (and correct) proof?
18

---

Answer: [Yes]
Justification:
Regarding Theorems !
??, and Lemma B
we describe the complete proofs
in the appendix, while proof sketches provided in the main paper. Regarding Lemmas and 5 we provide complete proofs in the main paper.
Guidelines:
The answer NA means that the paper does 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 proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
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 be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the detailed setting reproduce Figure in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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, deseribing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to 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 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 model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue reproducibility, 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) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way access this model for reproducing the results or way 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 authors are welcome to 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 (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results. 5. Open access to data and code
19

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We do not provide code since the central contribution on the theoretical
aspect.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.ce
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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:
(eddeSo ssi onPolicy) 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 should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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?
Question:
Answer: [Yes]
Justification:
All the parameters plot Figure are described in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paperreport error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We do not provide an error bar to enhance the clarity of Figure I This is not related to our contribution.
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 run with given experimental conditions).
20

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
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тror rates).
If error bars 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: We do not provide computer resource information since the computational time is unrelated our contribution.
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 the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wwwr....ccooo/oc/cccctaa
Answer: [Yes]
Justification:
We have reviewed the Code of 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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on the theoretical aspect, and does not relate to any particular 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 or why the paper does not address societal impact.
21

---

Examples of negative societal impacts include potential malicious 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.
The conference expects that many papers will be foundational research and not tied to 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses 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 use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.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 package should be provided. For popular datasets, paperswithcode com danttttsstss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
22

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced 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/codemmodel 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as 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 the NeurlPS Code of 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23

---

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


Reviews:
[{"review_id": "lUL1Th7be8", "reviewer": "Reviewer_UxhJ", "summary": "This paper resolves a significant gap between the empirical performance and theoretical understanding of the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm for noise-free bandit optimization. Although GP-UCB is a popular and practically effective adaptive algorithm, its existing regret guarantees were suboptimal. This work provides a new, refined analysis that proves GP-UCB achieves nearly-optimal regret, aligning its theoretical guarantees with its strong empirical results. The core technical contribution is a new, algorithm-independent upper bound on the sum of posterior standard deviations, derived by connecting analysis techniques from the noisy GP setting (specifically, the Maximum Information Gain) to the noise-free case.\n\nThe new analysis establishes significantly tighter regret bounds that match known lower bounds up to polylogarithmic factors. For cumulative regret, the paper shows that GP-UCB achieves constant $O(1)$ regret for the squared exponential (SE) kernel, and different near-optimal rate for the Matérn kernel depending on the relationship of the input dimension $d$ and the smoothness parameter $v$ (summarized in Table 1). For simple regret, the analysis provides rates of $O(\\sqrt{T} exp(-\\frac{1}{2} CT^{\\frac{1}{d+1}})$ for the SE kernel, and $\\tilde{O}(T^{-\\frac{v}{d}})$ for the Matérn kernel (summarized in Table 2). Based on the summary in the literature review, these two results advance the state-of-the-art regret bounds and are near-optimal compared to the best-known lower bounds.\n​ \nBecause the main technical lemmas are algorithm-independent, this work not only solidifies the theoretical foundation of GP-UCB but also provides a powerful new tool that could be used to improve the analysis of many other GP-based bandit algorithms.\n\nI have checked the proofs in the main paper and the proofs are sound to me. The new analysis on the posterior standard deviation is also neat and new to me. I think the paper is a solid contribution to the analysis of GP-UCB regret with a simple yet new idea.", "questions": "Nothing specific in my mind. The paper is very clear and well-structured. It would be great if the authors can also briefly share the results of applying the same idea to RBF and linear kernels, and if this idea advances the best-known regret bounds for these kernels.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Very clear presentation and neat idea.\n- Solid improvement of the regret bound in both the simple and cumulative settings.\n- Very clear summary of the literature\n\nNeutral feedback:\n- As the authors mention, the idea can also be applied to other kernels. It would be great if the results of other kernels can also be shown or briefly summarized in the paper.", "was_revised": true, "final_justification": "I have read the authors' responses and I keep my assessment.", "rebuttal": "Thank you for your overall positive assessments.\n\n**Q. It would be great if the authors could also briefly share the results of applying the same idea to RBF and linear kernels, and if this idea advances the best-known regret bounds for these kernels.**\n\nFor the linear kernel, we can obtain $\\min \\sigma(x_t; X_{t-1}) = O(\\sqrt{T} \\exp(-\\frac{T}{2d}))$ and \n$\\sum_{t=1}^T \\sigma(x_t; X_{t-1}) = O(1)$, since we can set $\\lambda_t = \\Theta(\\sqrt{T} \\exp(-\\frac{T}{2d}))$ from $\\gamma_T(\\lambda^2) = O(d \\ln (T/\\lambda^2))$ [Srinivas et al., 2010]. However, under the linear kernel with noiseless setting, if the input sequence is not redundant, we can immediately obtain $\\min \\sigma(x_t; X_{t-1}) = 0$ for $t > d$ and $\\sum_{t=1}^T \\sigma(x_t; X_{t-1}) = O(1)$ without using our lemmas. Therefore, we believe that our results do not provide any advanced insight under the linear kernel so far. \nThe results for the RBF kernel are the same as the results for the SE kernel, as long as the reviewer adopts the standard definition of the RBF kernel, which is the same as the SE kernel.\n\n- Srinivas, N., Krause, A., Kakade, S., & Seeger, M (2010). Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design."}, {"review_id": "PcqEYyutMz", "reviewer": "Reviewer_TJZH", "summary": "**Setting**  \nThis paper considers the noise-free Gaussian Process Bandit setting, where in each round, an arm $x_t$ is selected and the corresponding reward is $f(x_t)$. The function $f(\\cdot)$ is unknown, and only function values can be observed. Since the observation is exactly the function value, this constitutes a noise-free scenario. Two performance measures are considered: one is the standard cumulative regret  and the other is the simple regret of the final round. The paper analyzes two types of kernel functions: the squared exponential (SE) kernel and the Matérn kernel.\n\n**Approach**  \nThe paper does not propose a new algorithm, but instead provides a refined theoretical analysis for the classical GP-UCB method. In the case of the squared exponential kernel, it improves the previously known regret bound from $\\mathcal{O}(\\ln T)$ to $\\mathcal{O}(1)$. For the Matérn kernel, the analysis also yields improved regret bounds. The theoretical improvement mainly comes from a tighter control of the posterior standard deviations, specifically the term $\\sum_{t=1}^T \\sigma(x_t| X_{t-1})$.", "questions": "I'm confused about why GP-UCB can achieve exponentially decaying simple regret, since the UCB strategy is fundamentally designed for balancing exploration and exploitation, rather than for pure exploration. In the context of pure exploration or Best Arm Identification (BAI), wouldn't existing BAI strategies be more suitable or more effective than UCB? Are there BAI algorithms that can achieve even better convergence rates? Or are UCB-based methods and pure exploration algorithms essentially equivalent in this noise-free setting?", "limitations": "The main limitation lies in the fact that the analysis is restricted to only two kernel functions, and there is no algorithmic innovation throughout the paper. The contribution is primarily a refined theoretical analysis of an existing algorithm rather than the proposal of a new method. But I believe the contribution of this work is sufficient.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n\n- The theoretical analysis is very solid, with clearly stated improvements and contributions.\n- A key strength of the paper is its effective exploitation of structural properties in the noise-free setting. Previous works that considered the noise-free case typically focused on refining the estimation error $\\beta$, which, in the absence of noise, becomes a constant instead of a time-dependent term, thereby improving the regret order from a factor of $\\log T$. This paper goes further by observing that the cumulative posterior standard deviation $\\sum_{t=1}^T \\sigma(x_t, X_{t-1})$ can also be more tightly controlled in the noise-free setting. This observation is very reasonable: in the noise-free case, once an arm $x$ is queried, its uncertainty $\\sigma(x)$ drops immediately to zero. Therefore, each arm only needs to be explored once to determine its value, significantly reducing the amount of exploration required.\n\n**Weakness**:\n\nI did not find any obvious weaknesses. If the theoretical results hold as claimed, I believe this is a highly meaningful and valuable contribution.", "was_revised": true, "final_justification": "This paper provides a clearly improved analysis and better theoretical guarantees for GP-UCB.\nMy main concern was whether a regret minimization algorithm can indeed perform well in terms of simple regret (i.e., in pure exploration settings). In their rebuttal, the authors addressed this concern by presenting experimental results showing that regret minimization algorithms still underperform compared to pure exploration methods for minimizing simple regret. This resolves my concern, and I therefore recommend acceptance.", "rebuttal": "Thank you for your overall positive assessments.\n\n**Q. I'm confused about why GP-UCB can achieve exponentially decaying simple regret, since the UCB strategy is fundamentally designed for balancing exploration and exploitation, rather than for pure exploration. In the context of pure exploration or Best Arm Identification (BAI), wouldn't existing BAI strategies be more suitable or more effective than UCB? Are there BAI algorithms that can achieve even better convergence rates? Or are UCB-based methods and pure exploration algorithms essentially equivalent in this noise-free setting?**\n\nIt is an insightful question. At least in the worst-case regret under Matern kernels, GP-UCB also achieves nearly-optimal regret, which indicates that we cannot obtain strictly superior BAI or pure exploration algorithm to GP-UCB in the worst-case sense. However, as far as we know, the empirical performance of GP-UCB for the simple regret tend to be worse than those of the algorithms tailored for simple regret, such as the expected improvement (EI) algorithm. \nActually, we conducted an experiment under the same setting as Figure 1 in the main text, and observed that EI outperforms GP-UCB in terms of simple regret. The results are summarized in the table below.\n\n| | t=10 | t=20 | t=30 | t=40 | t=50 |\n| --- | --- | --- | --- | --- | --- |\n| GP-UCB under Mat'ern 5/2 | 0.1319 | 0.04241 | 0.0131 | 0.00316 | 0.0006518 |\n| EI under Mat'ern 5/2 | 0.09675 | 0.003263 | 0.0006412 | 4.563e-05 | 5.648e-06 |\n| GP-UCB under Mat'ern 3/2 | 0.125 | 0.05118 | 0.01957 | 0.01051 | 0.005216 |\n| EI under Mat'ern 3/2 | 0.1055 | 0.003216 | 0.0008133 | 0.0003194 | 2.152e-05 |\n\nIt remains unclear whether this performance gap arises from differences in constants or logarithmic factors in the worst-case regret bounds, or whether it reflects a more fundamental mismatch between worst-case analysis and practical performance. In the latter case, instance-dependent analyses—-such as those proposed in [Shekhar & Javidi, 2022] for GP bandits—-may provide deeper insights into the differences between GP-UCB and other algorithms specifically designed for BAI and pure exploration. To the best of our knowledge, in the context of GP bandits, there has been little evidence suggesting a fundamental difference in the analysis of cumulative regret versus simple regret. Therefore, we believe that the question raised by the reviewer points to an important open problem in the field.\nWe are happy to include a discussion of these points in Section 4 in the revision.\n\n- Shekhar, S., & Javidi, T. (2022, June). Instance dependent regret analysis of kernelized bandits. In International Conference on Machine Learning (pp. 19747-19772). PMLR."}, {"review_id": "aM3NMJUDzA", "reviewer": "Reviewer_5t4c", "summary": "This paper improves upon the regret analysis of [Iwazaki and Takeno, 2025a] for the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm in the noise free GP bandits. In particular, the authors consider squared exponential and Matérn kernels, where they manage to improve the existing upper bounds on regret.", "questions": "I suggest extending the applications to other kernels, such as the Neural Tangent Kernel (NTK), which would broaden the impact and relevance of the proposed technique.\n\nI find the presentation of the paper to be visually very similar to [Iwazaki and Takeno, 2025a]. I recommend revising the manuscript to better emphasize the originality of the contribution and to avoid potential plagiarism.\n\nAdditionally, in the contributions section, it is stated that GP-UCB achieves constant regret for $d > \\nu$; however, according to Table 1 and as also indicated by Figure 1, it should be $d < \\nu$. I assume this is a typo.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I find the problem addressed in the paper to be important, and the proposed method interesting, particularly because it enables the translation of noisy-regime guarantees to the noise-free setting. The paper is clearly written and generally easy to understand. Moreover, the technique has the potential to be generalized to a broader class of kernels.\n\nHowever, I find the contribution, in its current form, insufficient for publication. While the refined analysis is valuable, it does not appear to be technically challenging and relies heavily on existing works. The scope of applications seems limited, and the difference from the prior work [Iwazaki and Takeno, 2025a] appears to be incremental.\n\nIn addition, I have concerns regarding the originality of the writing. Specifically, several parts of the manuscript—including the formulations of main theorems: Theorem 1 and Theorem 2, Table 1 and Table 2 (including their captions), Assumption 1, problem setting, and the subsections “Gaussian Process Model” and “Maximum Information Gain”—appear almost identical to the corresponding sections in [Iwazaki and Takeno, 2025a], without proper acknowledgment. This raises potential plagiarism concerns that should be carefully addressed.", "was_revised": true, "final_justification": "This paper improves upon the regret analysis of [Iwazaki and Takeno, 2025a] for the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm in the noise-free GP bandit setting.\n\nThe achieved bounds are important for the field and were previously conjectured. However, I find the analysis to be incremental relative to prior work, and the presentation raises multiple plagiarism concerns. Therefore, I consider the paper to be borderline.", "rebuttal": "Thank you for taking the time to review our paper. Regarding the presentations that the reviewer pointed out, we promise to carefully revise them to avoid potential plagiarism. Here, please note that the revision of these presentations does not affect our contributions and can be conducted with minor revisions. \nHowever, we strongly disagree with the following reviewer's opinion that the current contributions of our paper are insufficient. \n\n**However, I find the contribution, in its current form, insufficient for publication. While the refined analysis is valuable, it does not appear to be technically challenging and relies heavily on existing works. The scope of applications seems limited, and the difference from the prior work [Iwazaki and Takeno, 2025a] appears to be incremental.**\n\nWe clarify the reasons below.\n\n### The difference from the prior work [Iwazaki and Takeno, 2025a] and the technical challenge.\nThere are apparent differences between our work and [Iwazaki and Takeno, 2025a] in both the main results and the proof techniques. First, regarding the derived results: our main technical contribution, Lemma 3, is applicable to *any* algorithm, in contrast to the results in [Iwazaki and Takeno, 2025a], which are specific to the MVR algorithm. This algorithm-agnostic nature makes our contribution particularly important for the GP-bandits field, for several reasons:\n\n- As mentioned in Lines 152–159, our results address COLT open problems raised in [Vakili, 2022]. Specifically, [Vakili, 2022] conjectures that the input sequence of GP-UCB may satisfy the upper bounds provided in our Lemma 3 (See Chapter 4.4 in [Vakili, 2022]).  To the best of our knowledge, our work is the first to prove such a result.\n- In the setting under the squared exponential kernel and Matern with $d < \\nu$, we obtain a strictly optimal constant $O(1)$ regret bound. Prior works such as [Iwazaki and Takeno, 2025a] and [Salgia et al., 2024] necessarily rely on phased elimination strategies using sequential non-adaptive algorithms. However, such approaches can only achieve polylogarithmic regret even under highly smooth objective functions. In contrast, our algorithm-independent upper bound enables us to derive regret without relying on any phased elimination structure and attains a constant $O(1)$ regret. To our knowledge, no existing work in the GP-bandit literature provides constant or strictly optimal regret bounds, marking a significant and novel contribution beyond [Iwazaki and Takeno, 2025a].\n- Our result enables the extension of many existing analyses in the noisy setting, especially those based on[Srinivas et al., 2010], which plays a central role in GP-bandit literature, to stronger guarantees in the noiseless setting. This point is made explicit in Lines 160–169 and elaborated further in the latter section of this rebuttal (“Scope of Applications”).\n\nRegarding proof techniques, there is a distinct departure in methodology. The proof in [Iwazaki and Takeno, 2025a] relies on explicitly upper-bounding the sum of the posterior variance (not the standard deviations) using the information gain, extending the approach of [Srinivas et al., 2010], in combination with the elliptical potential count lemma (Lemma 6 in our paper). In contrast, as described in Lines 199–232, our proof avoids explicit reliance on the information gain-based upper bound of the sum of posterior variance. Instead, we combine the elliptical potential count lemma with the monotonicity of the posterior standard deviations with respect to the noise parameter and the training data, resulting in a fundamentally different and more direct application of the elliptical potential count lemma.\n\nWhile both our work and [Iwazaki and Takeno, 2025a] employ the elliptical potential count lemma, the way it is utilized differs significantly. Notably, the elliptical potential count lemma itself was initially applied in [Flynn & Reeb, 2025] to analyze GP-UCB. However, as stated in Chapter 3 of [Iwazaki and Takeno, 2025a] and shown in [Flynn & Reeb, 2025], combining this lemma with the standard information gain-based upper bound of the posterior variance by [Srinivas et al., 2010] leads to strictly suboptimal results unless applied to particular algorithms such as MVR. This makes it technically non-trivial to use the elliptical potential count lemma to achieve near-optimal results in noise-free GP-bandit fields. We overcome this challenge by developing a new proof strategy that bypasses the explicit information gain-based bound of the posterior variance in [Srinivas et al., 2010] entirely and instead relying on the repeated application of the elliptical potential count lemma with the monotonicity with respect to the noise parameter and training input. \n\n### The scope of applications\n\nAs detailed in Lines 160–169, our Lemma 3 enables a extension of regret analyses in noisy settings -often characterized by terms involving either $\\sum_{t=1}^T \\sigma(x_t; X_{t-1})$ or $\\min_{t \\in [T]} \\sigma(x_t; X_{t-1})$- to the noiseless setting, without requiring algorithm-specific structure. \nThis is possible because, in many existing results, the dominant terms in the regret or performance bounds are quantified by these quantities. Specifically, as described in \nBelow, we elaborate on the examples cited in the main text:\n\n- **Bayesian GP-UCB**: As in \\[Srinivas et al., 2010, Theorems 1 and 2], one obtains regret bounds of the form\n  $R_T \\leq O(\\sqrt{\\beta_T} \\sum_{t=1}^T \\sigma(x_t; X_{t-1}))$, with $\\sqrt{\\beta_T} = O(\\ln T)$.\n\n- **Bayesian GP-TS**: As shown in [Russo & Roy, 2014, Chapter 6.3 and Proposition 5],\n  $R_T \\leq O(\\sqrt{\\beta_T} \\sum_{t=1}^T \\sigma(x_t; X_{t-1}))$, where again $\\sqrt{\\beta_T} = O(\\ln T)$.\n\n- **Contextual GP bandits**: From \\[Krause & Ong, 2011, Lemma 4.1], CGP-UCB algorithm satisfies $R_T \\leq O(\\sqrt{\\beta_T} \\sum_{t=1}^T \\sigma(x_t; X_{t-1}))$. In frequentist settings, based on Lemma 7 of our paper, this assumes a fixed-width confidence bound $\\sqrt{\\beta_t} = B$. Furthermore, the input space $\\mathcal{X}$ is defined as the product of the context and decision spaces.\n\n- **Level-set estimation**: By combining Lemmas 5 and 6 of [Gotovos et al., 2013], the stopping time required to identify an $\\epsilon$-accurate solution using the straddle algorithm is bounded by the smallest $T$ satisfying $2 \\sqrt{\\beta_T} \\min_{t \\in [T]} \\sigma(x_t; X_{t-1}) \\leq \\epsilon$.\n\n- **Multi-objective optimization**: As in [Zuluaga et al., 2016, Section 4.2], the number of queries required to identify an $\\epsilon$-Pareto set using $\\epsilon$-PAL is upper bounded by the smallest $T$ satisfying\n  $2m \\sqrt{\\beta_T} \\max_{i \\in [m]} \\min_{t \\in [T]} \\sigma_i(x_t; X_{t-1}) \\leq \\epsilon$,\n  where $\\sqrt{\\beta_t} = B$ (by Lemma 7 of our paper), $m$ is the number of objective functions, and $\\sigma_i(\\cdot)$ is the posterior standard deviation of the $i$-th GP.\n\n- **Robust optimization**: From Eq.(42) in [Bogunovic et al., 2018], the robust regret of Stable-OPT is given by\n  $O(\\sqrt{\\beta_T} \\sum_{t=1}^T \\sigma(x_t; X_{t-1}) / T)$. Here, we assume $\\sqrt{\\beta_t} = B$ based on Lemma 7 of our paper.\n\nThese are merely examples, and we think that many other results based on the analysis by [Srinivas et al., 2010] for the noisy GP-bandit setting can also be extended to the noise-free setting by using our Lemma 3. \n\nFinally, we would like to add a note on the applications of the noise-free setting itself. Applications of the noise-free setting are not limited to Gaussian process bandits but have been extensively studied in related fields such as Efficient Global Optimization and Bayesian optimization. In particular, in engineering and scientific domains, dealing with noiseless black-box functions—such as in computer simulations and system tuning—is a critical problem. For example, relevant applications and studies are comprehensively referred to in Chapter 1 of [De Freitas et al., 2012] and in the tutorial paper by [Frazier,2018]. (Notably, the tutorial paper by [Frazier,2018] treats the noiseless setting as the \"standard\" problem.)\n\nBased on the above clarifications, we sincerely hope that the reviewer reconsider the current score or clarify the unresolved concerns in detail. We believe that the results presented in our paper are of significant importance to the field, and we strongly feel that the paper should not be rejected due to misunderstandings.\n\n- Srinivas, N., Krause, A., Kakade, S., & Seeger, M. (2010). Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design.\n\n- Krause, A., & Ong, C. (2011). Contextual Gaussian process bandit optimization.\n\n- De Freitas, N., Smola, A. J., & Zoghi, M. (2012). Exponential regret bounds for Gaussian process bandits with deterministic observations.\n\n- Gotovos, A., Casati, N., Hitz, G., & Krause, A. (2013). Active learning for level set estimation.\n\n- Russo, D., & Van Roy, B. (2014). Learning to optimize via posterior sampling.\n\n- Zuluaga, M., Krause, A., & Püschel, M. (2016). e-pal: An active learning approach to the multi-objective optimization problem.\n\n- Bogunovic, I., Scarlett, J., Jegelka, S., & Cevher, V. (2018). Adversarially robust optimization with Gaussian processes.\n\n- Frazier, P. I. (2018). A Tutorial on Bayesian Optimization.\n\n- Vakili, S. (2022). Open problem: Regret bounds for noise-free kernel-based bandits.\n\n- Li, Z., & Scarlett, J. (2024). Regret Bounds for Noise-Free Cascaded Kernelized Bandits.\n\n- Salgia, S., Vakili, S., & Zhao, Q. (2024). Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency.\n\n- Flynn, H., & Reeb, D. (2025). Tighter Confidence Bounds for Sequential Kernel Regression."}]

Author rebuttal:

Meta-review: This primarily theoretically oriented paper makes important contributions in the fundamental understanding of Gaussian process (GP) based bandit algorithms that rely on noiseless function value observations, as opposed to the classically studied noisy observation setting. Specifically, it develops refined bounds on the cumulative and minimum posterior variances across a sequence of actions, under commonly used kernels. These are then used to resolve open questions about the cumulative regret performance of the GP-Upper Confidence Bound (GP-UCB) algorithm in the noiseless setting, by showing that it achieves nearly optimal regret rates for commonly used kernels such as the Squared Exponential and Matérn kernels. As such, the results about bounding the posterior variance are of a plug-and-play form and hold promise for endowing any existing confidence-bound based regret analyses with improvements in regret rates. 

The referees all agree that the central contribution of the paper -- in developing improved bounds for posterior variances -- is of significant value in the black box GP optimization literature. Though one of the referees, with a borderline score, raised concerns about the overall quantum of novelty of the submission, the authors responded with detailed clarifications about the scope and importance of the contribution. As a result, I am of the view that the significance of the technical contribution is no longer a lingering concern. 

In view of the strengths of the paper as brought out in the reviews and ensuing discussions, I am happy to recommend that the paper be accepted. I urge the authors to consider the suggestions of the referees to improve the clarity of presentation in a revised version.
Decision: Accept (poster)