Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance
Authors: Shogo Iwazaki
Shion Takeno
Venue: ICML 2025 oral (2025)
Keywords: Gaussian process bandits
kernel bandits
noiseless setting
Primary area: theory->online_learning_and_bandits

Abstract: We study the Gaussian process (GP) bandit problem, whose goal is to minimize regret under an unknown reward function lying in some reproducing kernel Hilbert space (RKHS). 
The maximum posterior variance analysis is vital in analyzing near-optimal GP bandit algorithms such as maximum variance reduction (MVR) and phased elimination (PE).
Therefore, we first show the new upper bound of the maximum posterior variance, which improves the dependence of the noise variance parameters of the GP. By leveraging this result, we refine the MVR and PE to obtain (i) a nearly optimal regret upper bound in the noiseless setting and (ii) regret upper bounds that are optimal with respect to the RKHS norm of the reward function. Furthermore, as another application of our proposed bound, we analyze the GP bandit under the time-varying noise variance setting, which is the kernelized extension of the linear bandit with heteroscedastic noise. For this problem, we show that MVR and PE-based algorithms achieve noise variance-dependent regret upper bounds, which matches our regret lower bound.

Improved Regret Analysis in Gaussian Process Bandits:
Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance
Shogo Iwazaki
Shion Takeno
Abstract
theoretical guarantee for the regret. Established work by Srinivas et al. (2010) has shown the upper bounds of the cumulative regret for the GP upper confidence bound (GP- UCB) algorithm. Furthermore, Valko et al. (2013) have shown a tighter regret upper bound for the SupKemneUCCB algorithm. Scarlett al. (2017) have shown the lower bound of the regret, which implies that the regret upper bound from (Valko et al., 2013) is near-optimal; that is, the re- gret upper bound matches the lower bound except for the poly-logarithmic factor. Then, several studies further tack- led obtaining a near-optimal GP-bandit algorithm. Vakili et al. (2021a) have proposed maximum variance reduction (MVR), which is shown to be near-optimal for the simple re- gret incurred by the last recommended action. Furthermore. Li & Scarlett (2022) have shown that phased elimination (PE) is near-optimal for the cumulative regret. The regret analysis of MVR and PE heavily depends on the upper bound for the maximum posterior variance.
We study the Gaussian process (GP) bandit prob- lem, whose goal is to minimize regret under an un- known reward function lying in some reproducing kernel Hilbert space (RKHS). The maximum pos- terior variance analysis vital in analyzing near- optimal GP bandit algorithms such maximum variance reduction (MVR) and phased climina- tion (PE). Therefore, we first show the new upper bound of the maximum posterior variance, which improves the dependence of the noise variance parameters of the GP. By leveraging this result, we refine the MVR and PE to obtain (i) a nearly optimal regret upper bound in the noiseless setting and (ii) regret upper bounds that are optimal with respect to the RKHS norm of the reward func- tion. Furthermore, as another application of our proposed bound, we analyze the GP bandit under the time-varying noise variance setting, which the kernelized extension of the linear bandit with heteroscedastic noise. For this problem, show that MVR and PE-based algorithms achieve noise variance-dependen regret upper bounds, which match our regret lower bound.
We derive the upper bound of the maximum posterior vari- ance in Section by which we tackle tightening the regret upper bound in the settings where room for improvement remains. Our contributions summarized as follows:
1. In Section 3, we obtain the upper bound of the maxi- mum posterior variance (Lemma 3.1 and Corollary 3.2). Our proposed bound is tighter than the existing bound when the noise variances approach zero
1. Introduction
The Gaussian process (GP) bandits (Srinivas al., 2010) is powerful framework for sequential decision-making tasks to minimize regret defined by a black-box reward function, which belongs to known reproducing kernel Hilbert space (RKHS). The applications include many fields such as robotics (Berkenkamp et al., 2021), experimen- tal design (Lei al., 2021), and hyperparameter tuning task (Snoek al., 2012).
Section 4, we analyze the GP bandit under the noise- less setting. We show novel result that PE achieves the cumulative regret upper bound that matches the conjectured lower bound shown by Vakili (2022) un- der common assumptions in the GP bandit literature. Furthermore, we prove that MVR achieves the expo- nentially converging and near-optimal simple regret upper bounds for squared exponential (SE) and Matérn kernels, respectively. These results are summarized in Tables 1-2.
Many existing studies have been conducted to obtain the
'MI-6 Ltd. Tokyo, Japan DDpaartment of Mechanical Engineer- ing, Nagoya University, Aichi, Japan. Correspondence to: Shogo Iwazaki <shogo iwazaki gmail.com>.
3.
In Section 5, we show that the modified PE- and MVR- style algorithms achieve the near-optimal cumulative and simple regret upper bounds with respect to the RKHS norm upper bound of the reward function under
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
several conditions. These results are summarized in Tables 3-5.
comparison.
Compared with the regret upper bound, the analysis for the regret lower bound is limited (Bull, 2011; Scarlett et al., 2017; Cai & Scarlett, 2021; Vakili, 2022). From these results, we will confirm the optimality of the GP bandit algorithms in Sections 4 and 5. In Section 6, our regret lower bound for the non-stationary noise variance setting is directly obtained from the proof's of (Bull, 2011; Scarlett et al., 2017).
4. In Section 6, we analyze the GP-bandit problem with the non- stationtt noise variance, which is the kernel- ized extension of the linear bandit with heteroscedastic noise (Zhou et al., 2021). We first study the regret lower bound. Then, we show that the modified PE- and MVR-style algorithms achieve the near-optimal cumu- lative and simple regret upper bounds, respectively. To our knowledge, our analyses are the first for this set- ting, though the non-stationary noise is a frequently faced problem.
The linear bandit with heteroscedastic noise, where the noise variance is non-stationary with respect to the time horizons, has been studied (Zhou et al., 2021; Zhang et al., 2021; Kim et al., 2022: Zhou & Gu, 2022; Zhao et al., 2023). These studies aim to obtain the noise variance-dependent regret upper bound, characterized by the sum of noise variances. To our knowledge, the kernelized extension of this setting has not been investigated. Furthermore, as discussed in Sec- tion 6, the direct extension from the linear bandit methods is not near-optimal.
1.1. Related Works
The theoretical assumption of the GP bandit is twofold:
Bayesian setting (Srinivas et al., 2010; De Freitas et al., 2012: Russo & Van Roy. 2014; Scarlett, 2018; Takeno et al., 2023; 2024) where the reward function follows GPs, and the frequentist setting, where the reward function lies in known RKHS (Srinivas et al., 2010; Chowdhury & Gopalan, 2017; Vakili et al., 2021a; Li & Scarlett, 2022). Although this paper concentrates on deriving the regret upper bound for the frequentist setting. our Lemma 3.1 and Corollary 3.2 are versatile and can be applied to the Bayesian setting.
2. Preliminaries
Problem Setting. f - RR be an unknown reward function with compact input domain X C gd. At each step t, learner chooses the query point 2; E XX; after that, the learner observes the corresponding reward yı == f(x;, where & is a mean-zero random variable. Under this setup, the learner's goal is to minimize the following cumulative regret Rr or the simple regret rr:
Many GP bandit algorithms have been proposed in the fre- quentist setting (for example, Srinivas et al., 2010; Valko et al., 2013; Chowdhury& & Gopalan, 2017: Janz et al., 2020; Vakili et al., 2021a; Li & Scarlett, 2022). Although sev- eral existing methods (Valko et al., 2013; Janz et al., 2020; Camilleri et al., 2021; Salgia et al., 2021; Li & Scarlett, 2022) achieve near-optimal regret upper bounds for the or- dinary GP bandit setting as summarized in (Li & Scarlett, 2022), we develop PE- and MVR-style algorithms due to their simplicity. On the other hand, although these existing methods are near- ooar-optimal regarding the time horizons, the optimality regarding the RKHS norm of the reward function has not been shown as summarized in Tables 3-5.
[ + te.,
RT Σ f(x") - f(xx); rE[T]
(1)
TT f(x" f(TT),
(2)
where [T] = (1..... 7} and x² E arg max x (ar) Fur- thermore, क7 E X' is the estimated maximizer, which is returned by the algorithm at the end of step T.
Regularity Assumptions. To construct an algorithm, we leverage the following assumptions.
The regret analyses are also conducted on the noiseless set- ting (Bull, 2011; Lyu et al., 2019; Vakili, 2022; Salgia et al., 2024; Kim & Sanz-Alonso 2024; Flynn& & Reeb, 2025). Re- garding the cumulative regret, we obtained a tighter upper bound for both SE and Matérn kernels than existing results without the additional assumption for the reward function like Assumption 4.2 in (Salgia et al., 2021). Regarding the simple regret, Kim & Sanz-Alonss (2024) have shown that the random sampling-based algorithm achieves the known- best regret upper bound in terms of the expectation regarding the algorithm's 's randomness. Compared with this result, we show the regret upper bounds that always hold with the de- terministic MVR-style algorithm. In particular, the regret upper bound is tighter for the Matérn kernel than that from (Kim & SlnzoA 2024). Tables 1-2 summarize the
Assumption 2.1 (Smoothness of f). Assume that f be an element of RKHS H4 with bounded RKHS norm llfllm. s B < co. Here, Hr and ||] respectively denote RKHS and its norm endowed with a known positive definite kernel k X x X + R. Furthermore, we assume k(2x, x)) < 1 holds for all x E X.
Assumption 2.2 (Assumption for noise). The noise se- quence (<) is mutually independent. Furthermore, assume that e, is sub-Gaussian random variable with vari- ance proxy P: 2 0; namely, Ejexp(Ae:)] N exp(X²p2/2) holds for all X E IR.
In existing works (c.g., Srinivas et al., 2010), Assump- tion 2.1 is the standard assumption for encoding the smooth-
2

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Table Comparison between existing noiseless algorithms' guarantees for cumulative regret and our result. In all algorithms, the smoothness parameter of the Matérn kernel is assumed to be v > 1/2. Furthermore, d, f, v. and B are supposed to be ((1) here. "Type" column shows that the regret guarantee is (D)eterministic or (P (P)robabllistic. Throughout this paper, the notation (()) represents the order notation whose poly-logarithii dependence ignored.
Regret (Matérn)
Algorithm
Regret (SE)
Type
Remark
V u<d d
V U> d
GP-UCB
(Lyu et al., 2019)
o T
T'2+4 2044
D
(Kim & Sanz-Alonso, 2024)
Explore-thes then-Coomit
N/A
δ T v42
P
(Vakili, 2022)
Kernel-AMM-UCH
0 [n r)
Ō T 2. 12nd 12
D
(Flynn& & Reeb, 2025)
REDS
N/A
Ō x
o (In & r)
O IIn in T
P
Assumption for level-set is required.
(Salgia et al., 2024)
PE (our analysis)
(In T)
δ (
O (In2tap T)
O (In
D
a >> is an arbitrarily fixed constant.
Conjectured Lower Bound (Vakili, 2022)
N/A
Ω T
P(InT)
22(1)
N/A
ness of the underlying reward function depending on the kernel. We focus on the following SE kernel ksg and Matérn kernel Matérn that commonly used in the GP bandit:
whose mean ( X, y) and variance o (x; X) are ps(a; x, = k(x, X) T (K(X, X) + "
oB X) = k(
- kk(x, X) (K(X, X) + 1 X),
(
| 1e--apo 212
KSE(I, xt) exp
20
Rtxt and K(x, X) = [k(z, T)a E Re' respectively represent the kernel matrix and vector defined by x and X. Furthermore, E E Rx is the positive definite variance parameter ma- trix that defines the noise structure of the observation of GP. Namely, given the input data X, the corresponding outputs y is assumed be given as y f (X) + under the GP mod- eling, where e ~ (O, Σ) and f(X) _N(O, ((O,K(X,, KXX, We would like emphasize that the above modeling as- sumptions (ʃ ~ GP, k) and e ~ N((0, Σ)) are "fictional" assumptions that are used only for GP modeling, and are distinct from Assumptions 2.1 and 2.2.
where X(X,X)
(k(2,, (. 1
MMaatrn (2. (x)
-1-V
22 x
Ø112 </2Vlee x
Ju
[(v)
where E and v/ > are the lengthscale and smoothness parameter, respectively. Furthermore, (()) and Ju denote Gamma and modified Bessel function, respectively. As- sumption 2.2 is also common in existing work (e.g.. Vakili al., 202 la; Li & Scarlett, 2022). In Sections 4-5, we con- sider the stationary noise variance setting whose variance proxy or is fixed over time, while the non-stationary noise variance setting that allows the time-dependent variance proxies Dr in Section 6.
Maximum Information Gain. The maximum informa- tion gain (MIG) is the kernel-depender complexity param- eter used to characterize the regret and confidence bounds in the GP bandits. Given the variance parameter matrix Σr = ( ................................ AZ.), ...,...,....... the MIG (EE))) is defined as
Gaussian Process. GP is a fundamental kernel-based model that gives both the prediction and its uncertainty quantification of the underlying function. Let GP (0, k) be mean-zero GP whose covariance is characterized by the kernel function k. In addition, let X == (æ),.... ax.) and = (yI...., yt) be training input and output data of GP, respectively. Then, under the Bayesian assumption that f follows the GP prior GP(O, k). the posterior distribution of f() given X and y is defined as Gaussian distribution,
TT (ET) = max (f()),))))) XCX
(3)
where I3, (f()))) = In det(Ex+K(XxX)) denote the det(S.r)
mutual information between y and S(X), under the GP modeling assumpsions f(X) y = f(X) + e, and e ~ NO,, E7). When E, = 2 with some fixed > 0 and the identity ma- trix IT E RIXT, the upper bound of MIG (T,
NO K(,,
3

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
is known in several commonly used kernels. For ex- ample, (r)22rr) I (T) O(In* 4+1 (T/22) and 20 mrr (r) I (2) = O((T/>²)=))) . (In(TAA)) )ां in SE and Matérn kernels with v > 1/2, respectively (Vak- ili et al., 2021b). Furthermore, for general Σr, we can see ( S IT) with > mi Xi from the data processing inequality (Theorem 2.8.1 of Cover & Thomas, 2006). We show the proof in Appendix B for completeness.
diag(A} ................................ . Then, for any T E (T N T/2 2 47r (Er))
T
max TE (0; XT) S =E
4
Σ
X
7T
(Ez), (5)
T
1=1
where Σ diag (X1 X2).
To make the above statements explicit, we give the following corollary for k = kse and k Matéén with the stationary variance parameter as special case of Lemma 3.1. The proof is in Appendix C.
Maximum Variance Reduction and Phased Elimination. MVR is the algorithm that sequentially chooses the most uncertain action 2; = argmaxxex* (z; X) as shown in Algorithm 2 in Appendix G. PE is the algorithm that com- bines MVR and candidate elimination as shown Algo- rithm in Appendix G. PE divides the time horizons into batches with appropriately designed lengths and performs MVR in each batch. In PE, after each batch, the inputs whose UCB is lower than the maximum of the lower CB are eliminated from the candidates. MVR and PE achieve near-optimal simple and cumulative regret upper bounds, respectively. Due to their simplicity, we analyze MVR- and PE-style algorithms.
Corollary 3.2. Suppose the assumptions in statement of Lemma 3.1. Then, the following four statements hold:
1. Suppose k kSF and fix any o > O. xf
1(exp( TiI In nnn(1 + T))), Eq. (4) holds with for all T 2 T. where T < oc is the constant that depends on X, a, d, and f.
X2= for
2. Suppose h: = Mattrr with v > 1/2 and fix any a > O.
If xr = Q(T a (In(1 + +T) 2u(1+o)
3. Uniform Upper Bound of Posterior Variance for Maximum Variance Reduction
), Eq. (4) holds with X2- X for all T 2 T, where T co is the constant that depends on X. a, d, E, and v.
In this section, we describe the theoretical core result that gives a new upper bound of the posterior variance for the MVR algorithm. Specifically, our result improves the ex- isting upper bound of posterior variance when decreasing noise variance parameters.
3. Suppose h kSE and fix any > 0 and C > O. If vT E N+, -2 < Cexp (-Tatz In 1nnnn(111111111 (1+T) (in-
cluding NT = 0), the following inequality holds for all T T:
Lemma 3.1 (General posterior variance upper bound for MVR). Fix any compact subset X C X. Then, the follow- ing two statements hold:
/oop(-Tattmm In )))
max d " (x; (T.T)
=
1. Stationary var.: Let (AT)TEN, be a non-negative sequence, and (XT)TEN, be a strictly positive se- quence such that XT S AT. Furthermore, for any
where T oo and the implied constant of the above inequality depend on X, a, d, C, and f.
T N4, t E [T], define aT. X as ØT, E arg max maxx=xX0x
4. Suppose k kMater with v > 1/2 and fix any -2 and C > O. Vf E N4, < CT % (In(1 + T)) 20(1+a2
0
(x; (T; where XT.-1 (IT.I...., 1T) Then, for any T E (T E N+ Ir),, the following inequality holds:
(including XT = 0), the following inequal- ity holds for all T 22'? T:
T/2 2 35t (1+1))
4 max 022 1, (x; XT.) S T X4 (4) xEX
(x: XT.T) S O ( (T~x(m (In ((1+a
max T IT =
(6)
2. Non-stationary var.: Let (Ne)teN, be non-negative sequence, and (Ne) be a strictly positive sequence such that X₂ < Nx Furthermore, for any E N4, de- fine Di E X as xs E arg T (x: Xt-1,, where X,- = (æi,..., (1-1)).,;;-1)) and E1-1 =
where T < oo and the implied constant of the above inequality depend on X, a, d, C, f, and
In all of the above statements, T increases as decreasing of a, and T - OC as a +

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Comparison with Existing Upper Bound. Here, we com- pare statement 1 in Lemma 3.1 with the existing upper bound. By considering the case X7- = >xy, 2 O T ( dard deviation under the sublinear increasing condition of MIG so that T/2 2 (x+ holds. On the other hand,
algorithm in noiseless feedback (see Assumption 4.2 in (Salgia al., 2024)). Furthermore, as described in the proof sketch below, our proof mainly relies the simple extension of the well-known information gain arguments from (Srinivas et al., 2010), not on the technique of (Salgia et al., 2024) that involves the theoretical tools from function approximation literature.
our result shows
X (T (T) upper bound of posterior stan-
the existing analysis of MVR! implies
Proof sketch of Lemma 3.1. Here, since statement 2 is derived as the extension of the proof of statement 1, only describe the proof sketch of statement for simplicity. We leave the full proof, including statement 2, in Appendix C. Our proof is based on the following two observations:
max xx2 X7 IT =E
(z; XT.r)
0 TV VV 2
if X (IL),
(7)
0
T
Tyx (XpT In 1n(1+
if X (1).
1.
For any index set T C [7], max Xz,1, (2;; Xr.)) can be bounded from above by the average observed posterior standard deviation on T from the defini- tion of MVR. Namely, max a X2,11 (æ; XT,T) S
Since Xy S 1/Im(1 + x,7). our analysis improves the noise parameter dependence on the decreasing regime of X2. Furthermore, several recent noiseless GP bandit works also derive the related result to Lemma 3.1 or Corollary 3.2. Flynn & Reeb (2025) consider the noiseless setting by rely- ing on elliptical potential count lemma (Lemma 3.3 below), and the naive adaptation of their analysis leads?
MT EIET
R.n. (DT, XT,t-1) holds.
2. If we set T = {t E
(T)
X x (TTT (T,zi)x,.1100 11}
2 s2 (IT, XT,(-1)
max #Ex Xy
Ir
(x: XT.))
X min 1, x o 1,
( (T.-1)
(8)
iT Ir IT)
2 ((r
S 227% In (1 + X7 0z
( Xr.-1))
00
T
T
for all t E T. We use Va 2 0, min (1, a} < 2 2l)(++a) in the last line. By relying on the standard MIG-based analysis (e.g., Theorem 5.3, 5.4 in (Srinivas et al., 2010)) and the assumption X I Xr, the above in- equality implies
2 In the above equation, the decreasing speed of Xy- is more restricted than that of Corollary 3.2 to obtain the same order upper bound as Eq. (4). For example, if & = kiaatrnn and as with the condition of statement 4 in Corollary 3.2, the first term (x, dominates the second term since the existing upper bound of MIG implies (x, Ir) Ö(1). Furthermore, Salgia et al. (2024) derives similar result to our statement 4 with random sampling algorithm instead of MVR. The main theoretical advantage of our result is that the constant T depends on the entire input space X' instead of the subset X. while that of (Salgia et al., 2024) has the dependence on X. This dependence on X' raises the requirement of the additional level-set assumption to apply the PE-style
X² = Q(T 2x (In(1 + T)) 2011
Σ N (TT,;; S 2 TT LET
T
From the above two observations, the remaining interest is the increasing speed of (T). We use the following lemma, which we call elliptical potential count lemma in (Flynn& & Reeb, 2025), as the analogy of elliptical potential arguments in linear bandits.
Lemma 3.3 (Elliitical potential count lemma, Lemma D.9 in (Flynn & Reeb, 2025)). Fix any T E No, any se- quence 21,...,37 FT
X, and any X > O. Set T as To = {t E [T] X x' "x (I1;; X.-1) > 13, where X, (21, 21)). Then, the number of elements of To satisfies |T S min 337 (3 (X IT),X*) ,37 (X IT) } Furthermore, 7l,-)) is any monotonic upper bound of MIG defined on R, x R,, which satisfies VT E N., >
'Eq. (7) also holds for any algorithm by replacing max.e. "xj,, (æ; Xr,7) with 1 "T Ex=1,, (æT,;; For example, GP-UCB (Srinivas al., 2010; Chowdhury & Gopalan, 2017) and GP-TS (Chowdhury& & Gopalan, 2017) use the upper bound of ΣLn Xx (ØT.6; Xr..-)).
In some settings of X². the first term of r...s. yr IT)TT can be small by putting min {7 (mm(() pT (Xn
0. (x2rr) I 7(T, and AA > 0,T 2 1,6 2 0,7 S (T +c,
the first term, instead of yr Ir). See Lemma 3.3.
5

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
From the above lemma, we obtain the lower bound of T as [T] 2 T 3- Ir). Finally, we obtain the desired result by noting [T] 2 T/2 holds for any T E (T' E N+
with k kSE. whose polynomial factor in exponential
gets worse from (a + 1/d) into -1 11/(d + 1), compared to the algorithm of (Kim & Sanz-Alonso, 2024). Roughly speaking, the numerator of the factor -1/(d + 1) in our analysis comes from the exponent of the upper bound of MIG O (Ind+1(I/XX) (T/X²)). We expect our simple regret has room of improvement from O(exp(-Ta- In T)) into Ö(exp(-Tà In -a T)) in future work, since the conjectured best upper bound of MIG is O(n 4/2 (T/x²) from the regret lower bound (Scarlett et al., 2017).
T/2 2 3 (T)
4. Noiseless Setting
As a first application of our result, we study a noiseless setting; namely, we focus on the setting where P: = 0 for all I E N+ in Assumption 2.2. The following results show our cumulative and simple regret guarantees for PE and MVR.
Theorem 4.1 (Cumulative Regret Bound for PE.). Suppose Assumptions 2.1 and 2.2 hold with pt. 0 for all E N4. Furthermore, assume B, d, f. and v are (1). Then, when running Algorithm I with / = B, X = 0, and any fixed N1 E N+, the following statements hold:
5. Optimal Dependence of RKHS Norm Upper Bound
As the second application of our result, we consider improv- ing the existing dependence of RKHS norm upper bound B in the regret upper bounds.
Ifk -KE, RT = (.n
5.1. Simple Regret
If Maatéra with v > 1/2.
The following theorem shows our results for simple regret.
)
if V < d,
Theorem 5.1 (Simple Regret Bound for MVR.). Suppose
RT
O((1n))2ta) TlIT))
if V d. if V > d.
(10)
Assumptions 2.1 and 2.2 hold with Pt = p > 0 for all N+. Furthermore, assume p. d, f, and are O and X is finite. Then, when running Algorithm 2 with X2 = O(B-²), the following statements hold for any fixed a > 0 with probability at least 1 -8:
Here, a > 0 is an arbitrarily fixed constant.
Theorem 4.2 (Simple Regret Bound for MVR.). Suppose the same conditions as those of Theorem 1. Then, when running Algorithm 2 with X = O, the following statements hold:
If k -KSE B O (exp (Tair In 71 (1+T)) and
T 2 T, then, rT O In+ti
Here, T is the constant, defined in statement I of Corollary 3.2.
kf = : TT =0 0 (exp (11Ta In (n==T))
kf = -MMatérn with v > 1/2, PT = Ō (T
If k kMaatru with > 1/2, -u(l+a)
0 T In (1+T)). and T 2 T, then, TT BBAST-I' In'r Herre, T is the constant defined in statement 2 of Corollary 3.2.
Remark 4.3. The above theorems assume that the learner can exactly choose x, in the algorithms, which is unrea- sonable for a continuous domain X. However, a similar guarantee, which is worse by an additional vIn T multi- plicative factor than the above results, can be obtained by the existing analysis (Li & Scarlett, 2022) under the addi- tional Lipschitz assumption for f. Note that such Lipschitz assumption for f automatically holds under fixed B when we set k- kSF or k kMatém with v 1 (Lee et al., 2022).
The important point is that the setting of the noise parameter X ((1B²) depends on B. We describe the full proof of the above theorem in Appendix E.
Remark 5.2. If we allow an additional logarithmic factor, we can eliminate the finiteness assumption of X' in Theorem 5.1 by relying on the discretization with 1 1/T-net as with Re- mark 4.3. The notable point we have to care about is that the Lipschitz constant given as B in the existing result (Lee et al., 2022). Therefore, the extension of Theorem 5.1 for continuous domain requires //BBT)-eet to maintain the or- der of B, and the resulting regret upper bound suffers from additional /In(TB) factor, instead of vin T factor derived from the standard discretizing argument that does not care the dependence of (Li Scarlett, 2022).
The proofs of Theorems 4.1 and 4.2 are respectively derived by directly following the standard analysis of PE and MVR with statements 3 and 4 of Corollary 3.2. We describe full proofs in Appendix D for completeness.
Discussion. As summarized in Tables 1-2, our results are the same as or superior to the best-known upper bounds in almost all cases. The only exception the simple regret
6

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Discussion. In both kernels, the polynomial dependence of B matches the lower bound in (Scarlett al., 2017), while there exists room for improvement in the logarith- mic factor. On the other hand, there exist some exceptional cases that Theorem 5.1 does not cover, even though its lower bound of the simple regret is guaranteed to converge to O. For example, when B = ( a In à T), the lower bound of (Scarlett et al., 2017) suggest that some algorithm find any c-optimal point for sufficiently large T (namely, simple regret converges to 0), while violating our assumption. As with the discussion in Section 4, this limitation can be elim- inated in the future if the upper bound of MIG matches the conjectured best upper bound.
6. Non-Stationary Variance
As the third application of our result, we consider the non- stationary variance setting, which falls between noiseless and a noisy regime. In this setting, our goal is to quantify the regret by the cumulative variance proxy Vi Everry Pi- That is, we aim to construct algorithm that achieves better performance than the one for the stationary noise setting if VT increases sublinearly. While the non-stationary variance setting has already been studied and motivated in the linear bandits (Zhou et al., 2021), to our knowledge, no existing GP-bandits literature exists for this problem. Therefore, in Appendix J, we describe some potential applications to motivate non-stationary variance setting in GP-bandits.
5.2. Cumulative Regret
By following the existing works (Zhou et al., 2021; Zhang et al., 2021: Zhou & Gu, 2022), we suppose that the learner can access true variance proxy pf at the end of step t. We leave the unknown pf setting for future research. Note that, as described later, the direct extension of the existing linear bandit algorithm with non-stationary variance does not lead to the near-optimal guarantee.
The following theorem also shows that the PE algorithm can achieve optimal dependence of B up to a poly-logarithmic factor.
Theorem 5.3 (Cumulative Regret Bound for PE.). Suppose Assumptions 2.1 and 2.2 hold with Pt = p > 0 for all t E N.. Furthermore, assume p. d, f, and v are (11), and X is finite. Then, when running Algorithm 1 with 31/2 = (B + T) X²= = ((B=2), and any fixed N1 N+, the following statements hold with probability at least] 1- - -8:
Lower bound. Since the stationary noise problem with p² = V//TT is subsumed in the non-stationary problem with the cumulative variance proxy Vr, the following lower bounds are obtained as the corollary of the existing station- ary variance lower bound (Scarlett et al., 2017) and noiseless lower bound (Bull, 2011).
pa-1) V/ 21 2 0
1f k = KSE and B- = O(VT), then, Rr
o 0 (I / T In In (TB2)) In ! )
Corollary 6.1 (Lower bound for cumulative regret). Let X' be X = [0, 1/5. Furthermore, assume Vr = (2(1) and VT = O(T2) with sufficiently small implied constant. Then, for any algorithm, there exists a GP bandit problem instance that satisfies Assumptions 2.1 and 2.2 with EiE(T Pt = -T and the following two statements:
If k
kMatrrn with v > 1/2 and B 2.2 3and
o
T add +aul Fand ) then, RT =m=
Ō (T utd zv4d
See Appendix E for the proof. In contrast to the analysis of the MVR, the analysis of PE cannot leverage Corollary 3.2 by setting X² = O(B Intuitively, this is because the existence of the common constant 7' over each batch is not guaranteed since X² depends only on T, not the total step size of each batch. Due to this limitation, the above result proved by leveraging Lemma 3.3 with the analysis of (Flymn& & Reeb, 2025), instead of using Corollary 3.2. As result, the conditions about B are more restricted than those of Theorem 5.1, due to the fundamental limitation of the analysis of (Flynn& & Reeb, 2025) as previously discussed in Section 3. For example, if k- = kyaatrnn the increasing 20 2and in Theorem 5.3 is more
T2 . Ifk = kig, E[RT] = S (V
Vp
. -fk= =
kMarérn E[RT] = S (Vizeira T
Here, we assume B, d, E, and v are O(1).
Corollary 6.2 (Lower bound for simple regret). Let X be
X' = [0, 1]a. Furthermore, assume Vr 2(1). If there exists an algorithm such that B[rr] I hold for all prob- lem instances that satisfy Assumptions 2.1 and 2.2 with Exeryy pi = VT, then:
speed of B O (11004
For k KSE, the total step size T needs to satisfy
restricted than B= = Ô (T') in Theorem 5.1, regardless the fact that lower bound (Scarlett et al., 2017) suggest the sublinear cumulative regret is achievable when B = TT").. We leave future research to break this limitation.
T 2 Ω (
Vzz In
For l kaattrns the total step size T needs to satisfy
7

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Vr (1) $ Ω Ω
d < o VT - Q(TT" )
o
d+1
T2 Vr
In
if k. = -SR- Further-
T2
$
if avd VT = O(T
more, if = kaattrn
Here, we assume B, d, f, and are ((1). Furthermore, >> 0 is a sufficiently small constant.
20 T
V T 2044
204d
if S 2V,
2v δ Vi
if 2v, V1 = 52 -
TT
2043
δ (T=%)
if 20, Vr = 0 T 2-20
The lower bound 2 ((1/e)=)
: for KMatér if d > 2z and VT= = in Corollary 6.2 come from (Bull, 2011), and others come from (Scarlett et al., 2017).
In both results, the regret upper bound matches the lower bound up to the logarithmic factor, except for the cumu- lative regret guarantee for d > 2v, Vr = O (T in = AMatérn- However, note that the resulting regret Ô T (T in this exceptional case matches the conjectured lower bound (Vakili, 2022); Therefore, as with our simple regret lower bound, δ TT upper bound in our analy- sis has no room for improvement if the conjectured lower bound in (Vakili, 2022) is true.
Note that the noiseless lower bound for expected regret also holds for noisy settings since an expected regret in the noisy setting can always be reduced to one in the noiseless setting, whose algorithm randomness is induced by obser- vation noise. Interestingly, the above simple regret lower bound indicates that if d > 2v and Vir = non-stationary variance setting may have the same level of difficulty as that of the noiseless problem. Our VA-MVR algorithm proposed below justifies this fact by providing simple regret upper bound matching the above lower bound.
20 ). the
Comparison with the stationary setting. When Vy ( our result matches the existing Ö(T ued ) upper bound for the stationary setting. If we consider the set- ting that V increases sublinearly, our algorithm achieves smaller regret than the existing stationary lower bounds. For example, if V (1) in k ksg, the resulting re- gret becomes logarithmeally increasing regret Rr = Ō(), while the regret lower bound for stationary variance setting is ((
Algorithm. Algorithms& 3 and 4 in Appendix H show PE and MVR-based algorithms for non-stationary variance problems, which we call variance-aware PE (VA-PE) and MVR (VA-MVR), respectively. The algorithms themselves are the variant of the standard PE or MVR algorithms that directly set the true variance proxy of to the noise variance parameter Xe for the heteroscedastic GP model.
Thcoretical analysis. The following theorems give the cumulative and simple regret guarantees for VA-PE and VA-MVR, respectively.
Comparison with the algorithm in heteroscedastic linear bandits. In heteroscedastic linear bandits, the weighted OFUL+ algorithm, which is known to achieve nearly opti- mal regret with UCB-based algorithm construction, is pro- posed in the known of setting. We can also consider the ex- tension of weighted OFUL+ to the GP bandits by construct- ing a UCB-based score with a heteroscedastic GP model. We call this extension variance-aware GP-UCB (VA-GP- UCB), and give the details in Appendix I. However, the re- gret of VA-GP-UCB becomes strictly worse than VA-PE and VA-MVR due to the following two reasons: Firstly, as with the stationary adaptive confidence bound (e.g., Lemma 3.11 in (Abbasi-Yadkori, 2013)), the existing adaptive confidence bound for heteroscedastic GP-model (Kirschner & Krause, 2018) contains O( 7h (E.) factor in the confidence width parameter, which leads to the sub-optimal order of the regret. Secondly, our analysis of VA-GP-UCB relies on the exten- sion of the elliptical potential count lemma (Lemma C.1) to a heteroscedastic GP model, which could result in worse dependence of the noise variance parameters than that of Lemma 3.1 (See the discussion in Section 3). To our knowl- edge, the existing technical tools provide no direct way to avoid the above two issues.
Theorem 6.3 (Cumulative regret upper bound for VA-PE). Suppose Assumptions 2.1 and 2.2, and |X| < 00 holds. Furthermore, assume Vr = Eveny P
(11). Then, when running Algorithmm 3 with g1/2
[ + / 2)
with probability at least 1-5, 5,
Rr 00 -(II V Furthermore, if k- kMatérn
VT (In+11 T2) Vi
(In (m1)))
ifk KSR.
if < 2v,
RT-
Ô T
V
ifd 2v, VT = 12 T
d-
if 2v, VT = O ( d=
Theorem 6.4 (Simple regret upper bound for VA-MVR). Suppose Assumptions 2./ and 2.2 and | < 20 holds. Furthermore, assume Vr = 211). Then, when run- ning Algorithm 4, with probability at least - 6, rt =
8

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Finally, give the summary of our results for the non- stationary variance setting in Tables 6-8 in Appendix A.
Chowdhury, S. R. and Gopalan, A. On kernelized multi- armed bandits. In Proc. International Conference on Machine Learning (ICML), 2017.
7. Conclusion
Cover, T. M. and Thomas, J. A. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley--nterscience, 2006.
We study the GP-bandit problem with the following three settings: (i) noiseless observation, (ii) varying RKHS norm, and (iii) non-stationary variance setting. We first propose new uniform upper bound of the posterior standard de- viation of GP in the MVR algorithm. By leveraging this upper bound, we refine the regret guarantee of the exist- ing PE and MVR algorithms. Our derived upper bound matches the lower bound up to the logarithmic factor in the aforementioned three settings.
De Freitas, N., Smola, A. J., and Zoghi, M. Exponential regret bounds for Gaussian process bandits with deter- ministic observations. In Proceedings of the 29th In- ternational Conference on International Conference on Machine Learning, pp. 955-962. Omnipress, 2012.
Flynn, H. and Reeb, D. Tighter confidence bounds for se- quential kernel regression. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learn- ing Research, pp. 3844-3852. PMLR, 2025.
Acknowledgements
This work was supported by JST ACT-X Grant Num- ber JPMJAX23CD, JST PRESTO Grant Number JP- MJPR24J6, JSPS KAKENHI Grant Number (JP23K192) 199677 and JP24K20847), and RIKEN Center for Advanced Intelli- gence Project.
Hickstein, D. D., Goldfarbmuren, R., Darrah, J., Erickson, L., and Johnson, A. Rapid, accurate, and precise con- centration measurements of methanol- mixture using Raman spectroscopy. OSA Continuum, 1(3):1097- 1110, 2018.
Impact Statement
Janz, D., Burt, D.,, and Gonzalez, J. 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, pp. 2486-2495. PMLR. 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
References
Kim, H. and Sanz-Alonso, D. Enhancing Gaussian process surrogates for optimization and posterior approximation via random exploration. arXiv preprint a7X0022401.17037. 2024.
Abbasi-Yadkond Y.
Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, 2013.
Berkenkamp, F., Krause, A., and Schoellig, A. P. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Mach. Learn., 112(10): 3713-3747, 2021.
Kim, Y., Yang, I., and Jun, K.-S. Improved regret analysis for variance-adaptive linear bandits and horizon-free lin- ear mixture MDPs. In Advances in Neural Information Processing Systems, volume 35, pp. 1060-1072. Curran Associates, Inc., 2022.
Bull, A. D. Convergence rates of efficient global optimiza- tion algorithms. Journal of Machine Learning Research, 2011.
Kirschner, J. and Krause, A. Information directed sam- pling and bandits with heteroscedastic noise. In Proc. Conference on Learning Theory (COLT), 2018.
Cai, X. and Scarlett, J. On lower bounds for standard and robust Gaussian process bandit optimization. In Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learn- ing Research, pp. 1226. PMLR, 2021.
Lee, M., Shekhar, S., and Javidi, T. Multi-scale zero-order optimization of smooth functions in an RKHS. In 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022.
Camilleri, R., Jamieson, K., and Katz-Samuels, J. High- dimensional experimental design and kernel bandits. In Proceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1227-1237. PMLR, 2021.
Lei, B., Kirk, T. Q., Bhattacharya, A., Pati, D.,, Qian, X., Arroyave, R., and Mallick, B. K. Bayesian optimization with adaptive surrogate models for automated experimen- tal design. upj Computational Materials, 7(1):194, 2021.

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Li, Z. and Scarlett, J. Gaussian process bandit optimization with few batches. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
41st International Conference on Machine Learning, vol- ume 235 of Proceedings of Machine Learning Research, pp. 47510-47534, PMLR, 2024.
Lyu, Y., Yuan, Y., and Tsang, I. W. Efficient batch black- box optimization with deterministic regret bounds. arXiv preprint arXiv: /905. /905./0051, 10041, 2019.
Vakili, S. Open problem: Regret bounds for noise-free kernel-based bandits. In Proc. Conference on Learning Theory (COLT), 2022.
Makarova, A., Usmanova, I., Bogumovic, I., and Krause, A.
Vakili, S., Bouziani, N., Jalali, S., Bernacchia, A., and shan Shiu, D. Optimal order simple regret for Gaussian process bandits. In Proc. Neural Information Processing Systems (NeurIPS), 2021a.
Risk-averse heteroscedastic Bayesian optimization. In Proc. Neural Information Processing Systems (NeurIPS), 2021.
Russo, D. and Van Roy, B. Learning to optimize via poste- rior sampling. Mathematics of Operations Research, 39 (4):1221-1243, 2014.
Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds Gaussian process bandits. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2021b.
Salgia, S., Vakili, S., and Zhao, Q. A Homain--hrinkinn based Bayesian optimization algorithm with order- optimal regret performance. In Advances in Neural Infor- mation Processing Systems, volume 34, pp. 28836-28847. Curran Associates, Inc., 2021.
Valko, M., Korda, N., Munos, R., Flaounas, I., and Cris- tianini, N. Finite-time analysis kernelised contextual bandits. In Proceedings of the Twenty-Ninth Confer- ence on Uncertainty Artificial Intelligence, 13I'13, pp. 654 663, AUAI Press, 2013.
Salgia, S., Vakili, S., and Zhao, Q. Random exploration in Bayesian optimization: Order-optimal regret and compu- tational efficiency. In Proc. International Conference on Machine Learning (ICML), 2024.
Zhang, Z., Yang. J., Ji, X., and Du, S. S. Improved variance- aware confidence sets for linear bandits and linear mixture MDP. In Advances in Neural Information Processing Systems, volume 34, pp. 4342 4355. Curran Associates, Inc., 2021.
Scarlett, J. Tight regret bounds for Bayesian optimization in one dimension. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pp. 4500-4508, PMLR, 2018
Zhao, H., He, J., Zhou, D.,, Zhang, T., and Gu, Q. Variance- dependent regret bounds for linear bandits and reinforce- ment learning: Adaptivity and computational efficiency. In Proc. Conference on Learning Theory (COLT). PMLR, 2023.
Scarlett, J., Bogunovic, I., and Cevher, V. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proc. Conference on Learning Theory (COLT), 2017.
Zhou, D. and Gu, Q. Computationally efficient horizon- free reinforcement learning for linear mixture MDPs. In Advances in Neural Information Processing Systems, vol- ume 35, pp. (6337-36349) Curran Associates, Inc., 2022.
Snoek, J., Larochelle, H., and Adams, R. P. Practical Bayesian optimization of machine learning algorithms. In Proc. Neural Information Processing Systems (NeurIPS), 2012.
Zhou, D., Gu, Q., and Szepesvari, C. Nearly minimax op- timal reinforcement learning for linear mixture Markov decision processes. In Proceedings of Thirty Fourth Con- ference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4532-4576. PMLR, 2021.
Srinivas, N., Krause, A., Kakade, S., and Seeger, M. Gaus- sian process optimization in the bandit setting: No regret and experimental design. In Proc. International Confer- ence on Machine Learning (ICMI., 2010.
Takeno, S., Inatsu, Y., and Karasuyama, M. Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds. In Proceedings of the 40th In- ternational Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp- 33490-33515. PMLR, 2023.
Takeno, S., Inatsu, Y., Karasuyama, M., and Takeuchi, I. Posterior sampling-baseee Bayesian optimization with tighter Bayesian regret bounds. In Proceedings of the
10

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Table Comparison between existing noiseless algorithms' guarantees for simple regret and result. In all algorithms except for
GP-UCB+ and EXPLOIT+, the smoothness parameter of the Matérn kernel is assumed to be > 1/2.
Algorithm
Regret (SE)
Regret (Matérn)
Type
Remark
GP-EI
N/A
0
T min
D
(Bull, 2011)
GP-EI with e-Grredy
N/A
(T
P
(Bull, 2011)
GP-UCB
(Lyu et al., 2019)
T T
δ (T
D
(Kim & Sanz-Alonse Alonso, 2024)
Kernel-AMM--CC
0 In In T
δ T
ud+224
D
(Flynn & Reeb, 2025)
GP-UCB+,
a >> 0 an arbitrarily
EXPLOIT+
0 0exx (-CT+-a)
0 OT-
P
fixed constant.
(Kim & Sanz-Alonse 2024)
C >>> 0 is some constant.
MVR (our analysis)
O exp
(- - In - TT)
2
δ Ö
D
>> 0 is an arbitrarily fixed constant.
Lower Bound
N/A
Ω (T
N/A
(Bull, 2011)
Table Comparison of expected cumulative regret upper bound between existing noisy algorithms' guarantees and our result in the
regime where the RKHS norm upper bound B may change along with T. Here, d, l, v. and the noise level p² are supposed to be @(1). Note that the table below describes the expected regret by setting confidence level ā = 1/T and = 1/(TB) existing PE and our PE, respectively. The resulting regrets for existing PE and our PE respectively suffer from additional O T) and O(vIn T TB)) factors in the high- high-probability regret upper bound of PE. Algorithm
Cumulative Regret (SE)
Cumulative Regret (Matérn)
GP-UCB
(BVTI d+ d+1 T+ vT VInn I)
BT u+d
3o++a 4u+2d
+ T
(Srinivas et al., 2010)
Existing PE
o max (B, V TIn
δ max {B, 1) T
(Li & Scarlett, 2022)
PE (our analysis)
utd
Lower bound (Scarlett et al., 2017)
(VTmm (TB2)
Ω B T 3042
A. A Additional Table Summary
We describe the additional table to summarize the results the existing analysis and ours. Table 2 summarizes the results of the simple regret upper bounds. Furthermore, Tables 3-5 and Tables 6-8 show the results for the setting of Section 5 and Section 6, respectively.
B. Monotone Property of MIG
Fix X C XT, Let yı and y/ be yı f(X) + 6 and y2 = f(X) + +1 + E2, where 61 ~ (1,,S)) 62 ~ NO S2), and S and S₂ are some positive semidefinite matrices. Then, from the definition, f(X) and ya are conditionally independent given y1. Therefore, we can see that,
Iff()::1) = I(f(X) + ((f([):(())))) y2 11)) =I(f(X); v2) ((f y1 132)
2 =(f(X);

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Table Comparison between existing noisy algorithms' guarantees and result in the regime where the RKHS norm upper bound B may change along with Z' Here, d, f, v, and the noise level p² are supposed to be ((1). As with Table 3, note that the resulting regret upper bounds for existing MVR and ours suffer from additional logarithmic factors high- seeh--rbbbilltyy regret upper bound. Simple regret (Matérn)
Algorithm
Simple regret (SE) I VT
GP-UCB
By
1 T
+
δ 8( कun
(Srinivas et al., 2010)
Existing MVR
o max {B, 13 v In0+2r
(max {B, I ToTo)
(Vakili al., 202
MVR (our analysis)
(ndt ( B2)
Ō B zorz B Triaa xira
T
Table Comparison the total time step condition to find the expected e-optimal solution the regime where the RKHS norm upper bound B may change along with T. Here, d, f. v, and the noise level p² are supposed to be @()). Time to simple regret e (SE)
Algorithm
Time to simple regret e (Matérn)
GP-UCB
0
Ba cx
In
d+1 B + 1 ((22)) !f
2+ #
(if 2v > d)
(Srinivas et al., 2010)
Existing MVR
o
max
B² 1 In d+2 (B.l
max (B.1)
2
(Vakili et al., 2021a)
MVR (our analysis)
0
22 In e)
1
B
27
Lower bound
Ω ( ln E)
Ω
1
B 4
(Scarlett et al., 2017)
22
where T(::)) and T(:: I)) are mutual information and conditional mutual information. The above inequality called the data processing inequality (Theorem 2 of Cover & Thomas, 2006). Note that the first and second equalities and last inequality are obtained by (X); y2 Bi) = 0 from the conditional independent property, the chain rule, and the non-negativity of the mutual information, respectively. Since this inequality holds for any X C XT. by setting S = IT and S.- = Ex X² I we can obtain maxxcxT TA42, (f(X): y) 2 maxxex" Iz, (f():
C. Proof of Section 3
C.1. Proof of Lemma 3.1
Proof. Below, we give the proofs for stationary and non-stationary variance parameters separately.
12

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Table 6. Summary of the cumulative regret upper bounds of the naive applications of existing results and our results in the non-stationary variance setting. Here, d, L, and are supposed to be (1). In the table below, p == mā p denotes the maximum variance proxy up to step I' Note that the table below describes the expected regret by setting the confidence level ò = 1/T in PE and VA-PE, respectively. The resulting regrets suffer from additional O(vhn /nn T) factors in the high-probability regret upper bound of these algorithms. Cumulative Regret (Matérn)
Algorithm
Cumulative Regret (SE)
d S 2 or VT = 2t
T
d < 2v and VT = 0
T 2u
GP-UCB
T
In T PT)
d-1
Ō
20 T
(Srinivas et al., 2010)
in(1+777
2)
In(1 +7 2) PT
PE
O ((nnT)38p2 In(1+ap
In
d+l I
In(1+77 2) PT 5ッ T
(Li & Scarlett, 2022)
P/.
VA-GP-UCB
o
(VVrin ald 1)
2d δ
T
d VVT
(ours)
VA-PE
o (InTT)332 /vr (In
12 Vr
Ö V Ioaa T Twidd
Ö (T
(ours)
Lower bound (Corollary 6.1)
Ω
v Vr Vr
T2 Vi
s ( V
d
Table 7. Summary of the simple regret upper bounds of the naive applications of existing results and our results in non-stationary variance setting. Here, d, and are supposed to be (11) In the table below, PJ- max P denotes the maximum variance proxy up to step T. As with Table 6, note that the resulting regrets for MVR and VA-MVR suffer from additional logarithmic factors in high-probability regret upper bound.
Simple Regret (Matérn)
Algorithm
Simple Regret (SE)
d S 2v or VT = 8
T
4
d >>> 2v and VT = 0 (T
(Srinivas et al., 2010)
GP-UCB
0
T'n(++p7 3)
In
d+1 T
V In(1+7,, 27 PT
2044 T au+2d
2d
MVR
0 (l In T
In 1+1 I
V In(1+7, 2, PT
Tリーa T To
(Vakili et al., 2021a)
TIn(I+P7 3
VA-GP-UCB
o (
[VVV
1 In (edtr))
δ [ 201d VVT
(ours)
VA-MVR (ours)
o (V t (In d+1 12
(InT)
20 Ō 1
zuA2 T
aued
VT
Stationary variance case. Fix any T E (T E N+
1
T/2 2 37r((2 }r and define T
{I [T] X7 mghn n- (OT,;;XT,--10 ) S $1).
Then, we have the following if T + 0:
max X; Ir (x;; XT.T
S T
Σ
X
(TT, XT.
(11)
#EX
LE
<
I- (IT,ti 1T,1-1)
(12)
IET
Σ
Xr min
1 2zt (DT,3) XT.=1)}
(13)
ET
min 1, 1, 02 2
(DT (T.11))
(14)
EE
X
Σ
1 2
In
(1+
X 02
(ET,1) Xx:tx)
(15)
|T
--
KE|T9
2
<
(16)
T
13

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Table Summary of the total time step condition to find e-optimal solution in non-stationary variance setting. We only focus algorithms and a lower bound here for simplicity.
Time to Simple Regret c (Matérn)
Algorithm
Time to Simple Regret e (SE)
d S 2v Vr ? T
d 2v and Vr =0
T
VA-GP-UCB
(
V 2 In d 2
(if 2v > d)
(ours)
VA-MVR
V
#
(Inat1 d+1 1) (In k
((22 (1) )))*)
δ (1)
(ours)
Lower bound (Corollary 6.2)
Ω
V 5 In
(1) (2)
? (!)
where:
Eq. (11) follows from the fact that X2211 (z; XT,T) S 0x (TT, XT.-1) holds for all [T], x X from the
MVR selection rule.
Eq. (12) follows from the monotonicity of the posterior variance on the noise parameter. Note that 'r S Ay holds from the assumption.
Eq. (13) follows from the definition of T.
Eq. (14) follows from Schwartz's 's inequality.
Eq. (15) follows from [T| < and the inequality Va 2 0, min(1,a) s 21n(1 + a
Eq. (16) follows from Every 1 In (I + Xx 22 _g.1_ (IT,Ii XT,c-)) 1xp,, (f(XT.T),)) 8) S (X) See, e.g.,
Theorem 5.3 in (Srinivas et al., 2010).
Furthermore, from the condition of T, we have
T T IT
(17)
2 T 3 31-33r((2) (2.1T)
(18)
2 T/2,
(19)
where the first inequality follows from Lemma 3.3. Combining Eq. (19) with Eq. (16), we obtain the desired result.
Non-stationary variance setting. We start by extending the elliptical potential count lemma to the non-stationary setting,
Lemma C.1 (Elliptical potential count lemma for non-stationary variance setting). Fix any T E N+, any sequence
FI...., ET E X, and A1...., Ar > 0. Define T as T = {t E [T] X "',,,, X4-1) > 1}. where X.-1 (aI....., 12-1) and E,-1 diag(A?,.... x;__) Then, the number of elements of T satisfies [T S min (47 (Ayr(ET), >7) (yr(E))), where d2 = min,e X2. Furthermore, T(,,)) is any monotonic upper bound of MIG defined on R4 x R4, which satisfies VT E N4, > 0,71 (X?I)) $ 7(T,??) and VX > 0.T 2 1, 2.220, 0, (TT(T. < 7(T + +e, X2).
Proof of Lemma C.I. T 0. the claimed inequality trivial, so we focus on the case where T of hereafter. From
14

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
the definition of Tc, we have
179
Σ
σI.-1 (zy; X(-1)) min
(20)
1,,,,00 Σ min 1 ,
00 Et (o/; X -1)
(21)
1
4 Σ
In [1 2 2
(z) X X(-1))
(22)
2
1ET.
4 4 Σ
In
1 + X 23 30, X(1))
(23)
(E[T]
x (Er(
(24)
In the above inequalities:
Eqs. (20) and (21) follows from 1 min {1, oz._, (z, X(-11 I min 11,2703,. (x) ((-))
which holds
for all t To from the definition of T
Eq. (22) follows from the inequality Va 2 0, mi, s 21nn(1 + a).
Eq. (24) follows from Every 1 In (1+ X2 o5 (ori X 13, (f(XT).)) S (T(2T). This is a direct
extension of Theorem 5.3 in (Srinivas et al., 2010) and is proved explicitly in the proof of Proposition in (Makarova et al., 2021).
Here, we set 41,...,479 E [T] as the elements of Ts, which are indexed the increasing order. Furthermore, for all [[T let respectively define H. X, X, and Σ, ã; Dt. X, (Zi,...., I.,), d dee, and Σ, diag() ..., ). Then, from Eq. (22), we also have the following inequality:
T 4 4 Σ
In
(1+
( X.-1)
(25)
2
1E7
17
< 4
In 1
X oz E._1
(z.:8111)
(26)
47po (DiTM)
(27)
< 47 |T
min X²
(28)
< 47
(29)
The second inequality follows from the fact that the posterior variance has the monotonicity on data; namely, of L S o0 X,-1) holds since the input data X;-1 is included in X,,-1-
The remaining proof is given by following the proof strategy under the stationary variance setting using Lemma C.I. Here, fix any T E (T E N4 T/2 2 47r (Er)) and define T [T] X o.__, (mx; X,-I) 1)) $1) Then, as with the proof
15

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
in the stationary variance setting, we have:
max OET (z; =EX
XT)
-
1
Σ
(ot; X1-1)
(30)
[T|
TET
1
I (Tt; X(-1)
(31)
TET
1
A min 1,, 1
(2 X(-1)}
(32)
[7|
TET
1
Σ MET
X
Σ
min 1, 2,2
2022222 Ex-1
(z Xc-1
(33)
171
TET
2
Σ
x2
Σ
In (1+ 22 -._!
(ari x
(34)
[E(T)
LET
2
Σ X
In (1+ x (1+
0z L.
(0 (11x)
(35)
[
2
(E(T)
(E(T]
2
Σ
X
(ET).
(36)
|T|
(E(TT)
Furthermore, from Lemma C.I and the condition of T, we have
IT| = T - 179
(37)
2 T 4YT (Er)
(38)
2 T/2.
(39)
Combining the above inequality with Eq. (36), we obtain the desired result.
C.2. Proof of Corollary 3.2
Proof. We describe the proof for each statement separately.
Statement 1. From the assumption, VT N4 2 Cexp (-ratr In - a(1 (T) holds for some constant C > 0.
Furthermore, since k = ksg, there exist constant C 0 such that yr (Xrlr) I Cl (T/X))) Here, C depends on and
d. Then,
(T(A)()) < Cln d+1 (TC- exp (raiz In " + ++)))
(40)
< TI d+1 exp (ČT In (1+
(41)
= (In(1 + T)) +T)) -a(d+1)
(42)
where δ > 0 is constant that satisfies TC-1 exp T aTas In (1 + T)) I exp ČT dh In In 11- +T) for all T e N4.
Here, note that Ò may depend on d, a, and C. Since coa+1 (In(1 (1 + T)) ald+1) + 0 as T + O, there exists a constant 7 such that T/2 2 3T (In(1 + -a)d111) holds for all T T. Furthermore, such constant 7 satisfies 2 VT 2 TTT22 2 3rr (x, Ir) from Eq (42). Therefore, for any T 2 T. Eq. (7) holds from Lemma 3.1 with X X
Statement 2.
From the assumption, VT E N > CT In
(1 + T') holds for some constant C > 0. > such that 7r (Z) S ((T/Xx)) In (1 +
pu(1+o)
Furthermore, since k kMatérn with v > 1/2, there exist constant
16

---

and calculating the explicit value of Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
T/ (y))) Here, depends on l, v, and d. Then,
7T (T) & C0
d 20t4 T [In-2i 2v (1+a) (1 + T)) In 2--d
2044
20
(1 1+0
In
2013
(1+1))
(43)
00 xجकक T In t (I+a) (1 + T)
In 20
TT -4
(44)
wa - CC veaa ČT
(1 + T),
(45)
where C 0 is constant that satisfies 1 1 CT In 20(1
2n14 for all T E Furthermooor C' > 0 is a constant that satisfies In Tr (Ō(1 T) شدا S CC अग (1 + T) for all T E N4. Here, note that C and Ć' may
T) - Č(1 T) -
depend on d, a, and v, but are the constants under the condition that d, a, and are fixed. Since CC" Ün In 20t4 (1 + T) + 0 as T + O, there exists constant T such that T/2 2 30C 2 CTIn 2 (1 + T) holds for all T > T.
Furthermore, such constant T satisfies VT 2 T/2 2 (7p from Eq. (45). Therefore, for any T 2 T. Eq. (7) holds from Lemma 3.1 with X7 Xx-
Statements and 4. For statement 3, we set X²- = Cex (-7 In 01 (1 Then, following the same argument as the proof statement I in Corollary 3.2, we confirm that "T (T) = oTT), and the quantity min E N+ Vt 2 T, T.2/2 2 3 ( (X) is bounded from above by some finite constant T that depends on d, and C. Furthermore, from 1T (T(> (T) and the definition of '', we can evaluate the order of the r.h.s. in Eq. (4)
4 T ( so $0
(VeS (-Tut In T
(46)
We also obtain the result for statement by setting X as X3. = CT - (In 2oll+o1 rh.s. in Eq. (4).
D. Proof in Section
D.I. Proof of Theorem 4.1
Lemma D.1 (Deterministic confidence bound for noiseless setting, Lemma 11 in (Lyu et al., 2019) or Proposition 1 in (Vakili et al., 2021a)). Suppose Assumptions 2.1, 2.2 with Vt E N4, Pt = hold. Then, for any sequence? (æx) on X, the following event holds:
AI E N Va E EX [xx)) - pxP,, (2; X,, fi)l (x;
(47)
where x = 0, X, (æ),..., x.), and f. (f( T
The proof of Theorem 4.1 follows by using Lemma D.I and Lemma 3.2 in the standard PE analysis.
Proof of Theorem 4.1. Fix any a > 0 and set T as the constant defined in statements 3 or 4 of Corollary 3.2. Furthermore, let i E N4 be the first batch index such that N₂ 2 T holds. In both kernels, the cumulative regret before the start of batch
7 is bounded from above by max(8B7 2BN1} } due to || S |l S N, < 2T, and E N₂ < N, N1 < T.
SStrictyy speaking, the input (æz))en, is required to have no duplication to guarantee the existence of the inverse gram matrix. In all of algorithms, such events only occur when the algorithm finds the maximizer x²" which leads to subsequent instantancous regrets of our upper bounds trivially hold. Therefore, we suppose that such events not occur our proof.
17

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Next, for any i-th batch with 2 i
have
Σ fxx) f(x))) - 1cb;-1(x=)) - 120)
(48)
leb;-1 (xx" - ucb, + 2/ -
(z) 2
(z))xx((-1) Ni.1 + 2/31/2 x22
(x X
(1-1)
Ni-1
]=1
(49)
N;
lcb:-1 1a="
max leb; 1cb;-1(ar) + 4B max -AAIN (æ;; X (1-11) mEX,
(50)
mE
1=1
(z: X 11 !
I 4BN, max ANINN wEA:-1
(51)
where Eq. (48) follows from the definition of /1/2 and Lemma D.1. Furthermore, Eq. (50) follows from (0) xx E X=-11
For SE kernel.
From statement 3 in Corollary 3.2², we have
(-N In No-1
4BN, max OXPIN,-1 (x; 8BN-11 =EX,
C1 expp
(52)
8BC2.
(53)
In the above inequalities, C1, C2 E 00) are the constant that may depend on d, L, and a. The existence of C2 is
guaranteed by V exp (-t=tr In 11) + O. Since the total number of batches is bounded from above by + log, T, we
have
Rr S max 8BC log2 0(I
(54)
For Matérn kernel.
From statement 4 in Corollary 3.2, we have
4BN, max OA (o;; X N S 8BCIN ((+4)) Ni-1,
(55)
with some constant C E oc) that depends on d, l, and a. When d > v, we have 8BC,N d- Inā(1+a) N 5 "²" In (1+a) T; therefore,
Rr S max 2BN1) + SBC (In(())))T) (log, 7) = - -
(56)
When d = v, we have 8BC,N 1-1 In g(1+a) N S 8BC, In 1+a T; hence,
Rr ma 2BN:) + SBC, (In (In'+a)) T) (log2 T)) 0 (In (12+0a))
(57)
Finally, when d < v, we have N In 5l)+a) N S 8BC, for some constant C2 E (0, oo); therefore,
Rr < max BT, 2BN; } + 8BC, (log, T) O (ln
(58)
"The application of Lemma 3.1 requires the compactness of the potential maximizers, which verified by the continuity of ucb;(.) under ksp and kxtttrnn
18

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
D.2. Proof of Theorem 4.2
Proof. If T, from Lemma D.I, have
f(x²) f(0r)= MA2T, (x" XT, fr) + Bo (x"; Mlar, (3x (xr;Xr, fr) + Box,, (0r; (0r; Xx))
(59)
s 2B max Ox (z; X
(60)
where the last line follows from the definition of TT.
For SE kernel.
From statement 3 in Corollary 3.2 and || S B, we have
2B TT
if I T T2T,
(61)
2BC exp (-17att In
Here, C1 E (0,1) is the implied constant in Corollary 3.2. From the above inequality, vT N+ (1), PT
BC2 exp (- a In r) holds for sufficiently large constant C2 oo), which depends on C1 T, a, and d.
Note that T and C the constant that only depends a, d, l, and This implies rT O (exp (-1 (-1Tat In - T T))
For Matérn kernel.
From statement 4 in Corollary 3.2, we have
2B
T if T2T,
TT S
T In ((+t)
(62)
Here, C E (0,1) is the implied constant in Corollary 3.2. From the above inequality, vT N+ (1), rT s BC, à 3n holds for sufficiently large constant C2 E (0, 00), which depends on C₁, T, a, d, and v. This implies Ô (T- 8).
E. Proof in Section 5
E.1. Proof of Theorem 5.3
Lemma E.1 (Non-adaptive confidence bound for noisy setting, Theorem 1 in (Vakili al., 2021a)). Fix any T N+. 8 E (0, 1), X2 > and suppose Assumptions 2, 2.2 with Vt N+. 0. Furthermore, assume X is finite. Then, if the input sequence (#4))E(T)) is independent of the noise sequence (ee)εεfry, the following event holds with probability at least 1 8:
B+ P \
2|X1| 5
Væ E X, (f(z) - 1AIII, (x: Xx, yr) S
21n
O (x;; Xx),
(63)
where Xx (#1,..., TT) and yr (y1,...,TT) VT)
Proof of Theorem 5.3. From Lemma E.1 and the union bound, the following event holds with probability at least - 8:
Vi E [Qr), Vo E X, lcb,(x) - f(x) < ucb;(w))
(64)
where Qr E N denotes the total batch size PE. Note that Qr < 1 + log, holds. Hereafter, we assume the above event holds.
19

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
First, the cumulative regret at the first batch is bounded from above by 2BN Next, for any i-th batch with i 2, we have
No
Σ f(x") - [(ae)
Σ ucb (x=") lcb)-((re)))
(65)
5
Σ lob; (a=") - ucb, u + 2/ x
(al) 10
xxxx) +23g1/2
(0'; X Ni-1
I
(66)
$ lcb;-1(x")) max lcb;-1(xx) + 4B max O xEA--1
(z; Xx: No-1
(67)
#ER
$ 4N,31/2 =E
max
- (x; X !
(68)
From the definition of 82/2 and X² = C/B²2 for some constant C > 0, the above inequality implies
N: Σ -a=)) ((z))) < 4N 1+0-1/2 p/ 21n X (1 + logg 1)
OX (0); X (1-1))
max
N;-1
(69)
6
Here, let us define T and T as T {j E [N,-1] 1 (2 x 1) To [Ni-11] T, respectively, From elliptical potential count lemma (Lemma 3.3), have
[T9 min 337 (3%.__, (1 IN. X2) 3 (AP (A2IN,1))-
(70)
Furthermore, from the definition of T, we have the following inequality as with the Eqs. (12)-16)::
Σ (,; - S
(71)
JET
Then, regarding the maximum of the posterior standard deviation, we have the following from the above inequalities:
max -EX--1
(x;; 02
(
(72)
0231 ( x(-
(73)
JE(N.-1]
T + Σ 02 (z:;; (x);:((11)) )
(74)
N
JET
min 3 (3YM.-, (X (A2I IN. . 3YN.,,
+ 2 (P (
(75)
N
min (37 (3 (, + +
(76)
N111
where the first inequality follows from the definition of the MVR-selection rule, and the second inequality follows from OX2T, 1 x ("1) s k(z,, < 1. Combining the above inequality with Eq. (68) and Qr S (1 + log, T), we have
Rr S 2BN 8(1 + log, g)/ min {3r ()3T((A2T),)))) 3 3 (121T) 2 (
,3T
(77)
For SE kernel. Note that 2
O(1/B²), B O(VT), and {(t,}?) O (t Since
3rr (I2 = O(In d+1 01 (TB²), we obtain min {37 ()2r((22r), 3 Ir)} = 0
(TB²)). Furthermore,
from (1TTT((2TT) o
T
V In in (TB2)) min (37 (3 (X2 22) 3,r(( + 2 (x
B
20

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
B In ++ (TB2) when B = O(V)) Hence, by noting B²/² - BB o and B = O(VT), we have
B, (1nT) T (n / (Innnn((((B))))) (in | )}}
R 0 max
(78)
=0 (
( In |2[|
(79)
Note that X = O(1/B²), = ( ( 2u2
and ((, = -(((/))) zrte
For Matérn kernel.
Furthermore,
we can see that
2v² + +vd
V S d
#2 + 3vd < 4nd + 4v² + 6v²d
4d + 4v² + 6vd
+0 S vd + 4v² + 4v2d
+ v v + 20)².
2udd
we can obtain B 0 (T²). Then, 3yT(>²IT) o aitt )
)
Thus, from B- O
T "'ad44uu4ord
Y (X Ö
Twu+ B
vtd
2044 and 37 (3)) Ō ((11 (rlntte) (B²)
diar 12d) (artd)
Therefore, for the
second term of Eq. (77), we see that
8(1 + log, 1)/1/2
min 37 (37T (A IT) X2) (} + (x-+7)
(80)
= - (B/2 82/2 min ((tta)) (
422)
(2
(T B²)
+ To B
2v
(81)
di2u+24) (2r4ay
Note that, if (T#), then (svrra)
(2))
(T) and (T v
(
Therefore,
if B (T*), T( x (B²)
222))22)
(2x 12)
O (T
20td
since
2ota
d
a(2u-2d)
(2v+d)=
Thus, Eq. (81) is
δ 81/2 T(arta)² 2
420) (20
))
+ T B Tolu
Then, we can see that
T(x )² (B2)
2(2++2)) (20+4)
Adu 1eft +u22
T
(2v44)²
B
(2v+4)²
(82)
T 20 B
2042
2u2 Bud
2n2 +4.24oud B
T
(204d)2
(av+
(83)
Therefore, if B O
2u² T add + fuod
then ((xiaa) 2
(B2)
(T ( B 2012 ). Thus, from the assumption
B =00 0
202 aodd T
T Tuutts) ) (B2)
a12n 12d) (au+d))
2u T B=
Hence, Eq. (81) Ō (B1/eT aed
B B= wits
δ ( vid (Tat Brita)
because of 31/2= (9BBV In 12' Therefore, we have
Rr = δ max B, m
mu B m }).
(84)
Furthermore, noting that B- θ (T=*
(T
B θ T 2otu B BIAid) since
utd
1 + d
2 2= +3vd
20
2 2v
4d + 1
B O (I (Tavee B ( Consequently, we have
Ry Ō (Ittte B B
utt
(85)
21

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
E.2. Proof of Theorem 5.1
Proof. From Lemma E.I, have the following with probability least 1- 6:
(ŌT; f(x') f(Ør) S Mx2z, (x"; XT, + 3 0x21, (x:; XT) - ( 0x XT) (86)
s 2/3 max Iy (m;; X ΦEX
(87)
2|X8 2ln
1 + PV 22
max 1 (x; XT). mEx
(88)
Here, when ksE, note that the condition B (exxp( In "1-"11 + T))) implies X² = ((exp(-xx)))) T In "(1 +
(1
T))). Therefore, in the SE kernel, from statement in Corollary 3.2, we have the following inequality for any 2
S 8 1 p1 2
2|x||
Voll
Cinn CIndtip (TB²)
(119) =0
(v In d+1 (TB2)
(89)
T
T
where C the implied constant of the upper bound of MIG, As for the Matérn kernel, leveraging statement 2 in Corollary 3.2 by noting the condition of B, have
rr T
8 1
1+
2| 21
pV
2
V
VCB
D(rid) ar Iold In 20 (TB*) Ō (BaraT 2+ं2
(90)
8
for any T.
F. Proof in Section 6
F.1. Proof of Theorem 6.3
Lemma F. (Non-adaptive confidence bound for non-stationary variance setting, extension of Theorem 1 in (Vakili et al., 2021a)). Fix any T N+. 8 E (0, 1), any non-negative sequence (De)EeN, and suppose Assumptions 2.1 and 2.2 with P: S X Furthermore, assume X is finite. Then, if the input sequence (ax))e(T) is independent of the noise sequence (ex)ettT, the following event holds with probability at least 1 8:
B + 2 2| ox. (x; XT),
Va X, If(x) - pri. (z; Xr.
(91)
where XT = (#I....., IT). yr = yr)) and En (), ).))
Proof. The proof almost directly follows by replacing the original Proposition 1 in (Vakili et al., 2021a). Let Zr(xx) be Zr(x) = (ax Xr) (K((T, XT) + -t) Then, following the proof of Proposition in (Vakili et al., 2021a), we
obtain its extension as
XT) = sup o
- (f(x)-Zr(z1) fr)² (IZT()))
(92)
fl <1
where fr- =
ET ZT Next, we consider replacing Proposition I with Eq. (92) in the original proof of Theorem 1 in (Vakili et al., 2021a). As with the original proof, we decompose
and (T(()) ||, Zr(x)) Σx
[f(x) - Psz (x; Xr, yr) into two terms:
If(x) Py,, (z: Xr. yT)l & [f(x)
(z) frl Zr(x) crll
(93)
where er = (f1....,,,r) T. The first term of r.h.s. is bounded from above as
f(x)
fr
[(xx) T frl B
Zr(z)T
S
(x: XT).
(94)
B
B
22

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
The last inequality follows from Eq. (92) since |I]())/Bl
n4. s 1 holds by Assumption 2.1. Regarding the second term, Tee Er is the sub-Gaussian random variable from the independence assumption between (ZI))E(T) and (T)) and
(r(x)²
its concentration inequality is obtained by evaluating the upper bound of the moment generating function. By following the proof of Theorem I in (Vakili al., 2021a), we have
1 [T((2)
E [xp((Z((x) (T)TT())(r)) cT) S exp
diigg(p......ff
(95)
ZZ 1
< exp
(96)
2
T (2;; XT)
S exp
(97)
where the second inequality follows from the assumption Pt X and the third inequality follows from Eq. (92). The above upper bound for the moment-generating function implies the following concentration inequality for any x E X' from Chernoft-Hoeffding inequality:
P (Zr(2)) erl S V 2 josy (æ: Xr) 2 1 ó.
(98)
Finally, we obtain the desired result by combining Eq. (93) with Eqs. (94), (98), and the union bound.
Proof of Theorem 6.3. From Lemma F.1 and the union bound, the confidence bound is valid with probability at least 1 8. Hereafter, From the assumption Vr I2(1), we have the constant C 0 such that Vr 2 C. Below, we prove each statement of the theorem separately based on the setting of the kernel.
For k = ksg. Let us set 7 as T = min E N+ VE 2 T,t/2 (ct( Note that the constant 7 is well-defined, since (C( = 0In (2) o(t). Furthermore, let i N4 be the first batch index such that N, > T holds. Then, the cumulative regret before the start of (i + 1)-th batch is bounded from above by max max(8B7) (8BT, 2BN; }. Next, we consider the cumulative regret after the start of (7 + 1)-th batch. We apply statement 2 of Lemma 3.1 with the following arguments:
1. Set X
(x50)²
max (159) (8)
Vr N.
Then, have (x50) 2
Vr/N, 2 C/N, Furthermore, set
(0 diag
[
2
(1)
2. From the above lower bound of X we have YN.
S TN. (CN, which implies N,/2 2 4YN, (E()) if
N₂ 2 T. Therefore, applying statement 2 of Lemma 3.1, we have
N; Σ
(11))2 YN.
max SOO
(%%)
for all 2 F.
(99)
E
N₂
\
The equation inside the square root in r.h.s. of Eq. (99) can be bounded from above further as
Σ (20) (29)))
V
7N:
[N:)
N
7N:
E-N.
(100)
VI I IN Ni
$ 2VTYN.
(101)
VT IT
2VTT
(102)
In 7
0
(103)
Vr
23

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Since 0100 = 2 the total cumulative regret bounded from above with probability at least 1 as
R f(x' f((x)) +
f(x²) f(a)5)
(104)
isi
S max(88BT,BNN] + 4/31/2
NJ max y: (2;; X ( wedi-1 -
(105)
N:
< max(88T, + 32
( (((-111 2
((i-1) 7N:-1
(106)
1
S Lmax(8BT,2BN) +0 31/2 + loge TV V1 In T2
(107)
VT
5o (In 50(10))
(inT)y Vr
d- T2 Vi
|
In
(108)
where the first inequality follows from the standard analysis of the PE (c.g.. Eqs. (65)-(68) with Lemma F.1. Furthermore, the second inequality uses the fact that the total number of batches is at most + logg T.
For l: = Matérn- The proof is almost the same as that of the SE kernel, while we need to introduce the additional lower
2 bound set X Let us set T as T min N 11 TT,12 2 47, Ax Ie], where set X = - In
20(1=0)
(1 +
here, where a > 0 is any fixed constant. Next, set X as (
max (2)0)
2
Vr 2 No AN. }. Then, as with the proof for
the case k= ksE, the following statement holds from statement 2 of Lemma 3.1:
max O SIO (z;
4
Σ j=1
N:
(x5))²
2
Y.N. (E%) for all i i,
(109)
W N;
N₂
where 7 E N4, is the first batch index such that N₂ 2 T holds. Furthermore,
N: Σ
(2)))
N
YN. (IN.) v
Σ
N
IN.
(40) NN.)
(110)
1=1
j=l
S 2V + N₂
YN..
(4) (NN.
(111)
In the above inequality, we can see that 7N;
50(0) S TM: (
S nr 44 Ir). Furthermore, if V+/N, N, then,
2Vr + N.T < 3Vr, which implies
Σ
N
2
YN: (50)) S y /Vrr
V1 T
IT
=0 (v Tzire)
(112)
On the other hand, YN. ($() I YN. (Xr, Iv.) also holds. If Vr S R then, 2V + NoYo I 3N, which implies
Σ (x)))) YN. (5()) S 3NN.A. (Rr, =
- (N, 1-"
(0(1)
if d
5 0 (T))
(113)
if d>
24

---

Improved Regret Analysis in GP Bandits:
Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Therefore, since 7 Trrid 2 T if S and VT (11), we have
Ō
VT Vire+a Twiitd
if d S 2n,
5(0) N
IN.
1
max Vi
uppitaatnn T TT })
(114)
if d > 2v.
Hence, as with Eq. (104) of the proof for h = kSE, with probability at least we have
N:
R - 8BT + 163 log2 T),
Σ
(x)))
YN. E
(115)
δ Vi
if s 2v,
(116)
δ max
V/
T
T -"2 })
if 2v.
"" Here, VT = O(T" " implies V
mita T 2u = O and Vr = 22TTTTT "M" implies vise versa; therefore, by combining
the condition Vi = 211,, we have
V To T 20
if d 2v,
Rr
①
V Irld I04a
if d> 2v and VT = S2 (T-
(117)
0
> 2v and VT 0 -
F.2. Proof of Theorem 6.4
Proof. Set 31/2 = B + V 21 2|
From Lemma F.1, with probability at least 1 - ō, we have
- f((r) S PΣ, (x": XT, yr) + 3113 oz, XT)) - HEz (ør; XT, yr) + 8 oz, 12, (TT;
(118)
I 1/ oxr (x; Xr).
(119)
We first consider the case where k KSE. Let us respectively define T, Xe, Ey as T = min(T E 2 2 4nx(Ctt-1 X2 = max (A?, Vr/T), and Σy = diagg .,,,)))) Here, C > 0 is the constant such that Vy 2 C. Note that the existence of is guaranteed by the assumption Vrr = 2(1). Then, as with the arguments of the proof of Theorem 6.3,
max #EX
(x: XT) S T
Σ X
YT (ET) for all T T.
(120)
From the definition of Xe, the above inequality implies, for all T > T,
8
T
- S
X2
YT
[ST)
(121)
8
T
T
Vir
p
+
rT
Σr
(122)
1/2
Vi
2V
IT
(123)
T
=0
(1
VT
In d+1 d+
T22
In
|28
)
(124)
T2
Vr
25

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Next, when & = Marérr we set T, Xr En as T = m | and Σn di ..... ) with the arguments of the proof of Theorem 6.3, statement (120) also holds for Maatrru- Therefore,
1)) X = max / X Xy.. ا (1 + 1), where a > 0 any fixed constant. Then, as
respectively. Here, X L _
In
8/1/2
T
f(a")- - f(ēT) v
X
PT
(ΣT)
(125)
T
1=1
8/3/22
/
(2V TXx) rT (Kir):
< T
(126)
Vr/T2 Xy or not, we obtain
As with the proof of Theorem 6.3, considering the two cases:
Vi Vi
if Vr > Xy
2
V 2V (2V + TXT) rr ErT) =
(127)
Ö T (T""""
d=y
if if Xy.
Therefore, we have
f(x)) f(āT) = Ō mmax - Viziiag
T 207J O(T 5), and V/ 1((1, have
20-4
(128)
Finally, since Vr O implies V1"" V -
Virld T zona
if < 2v,
fwx)) - [(TT)
0 Viuind 7 zター2
if d > 2v and VT S2 (
(129)
(T
if d > 2v and Vr 0 T d=20
G. Pseudo Code of PE and MVR
Algorithms and show the pseudo-code of PE and MVR, respectively. In the PE algorithm, we denote 2; yj and " as the selected query point, observed output, and the observation noise at step j on i-th batch, respectively.
(1)
H. Pseudo Code of VA-PE and VA-MVR
Algorithms 3 and show the pseudo-code of VA-PE and VA-MVR described in Section 6, respectively.
I. VA-GP-UCB Algorithm
We consider the (P-UCB-based algorithm as the extension of the variance-aware UCB-style algorithms (Zhou et al., 2021; Zhang al., 2021; Zhou & Gu, 2022) in linear bandits.
Algorithm. Algorithm 5 shows the pseudo-code of VA-GP-UCB algorithm. Overall, the algorithm construction is almost the same as the GP-UCB algorithm with a heteroscedastic GP model. The only difference is the application of the lower threshold > 0 for the variance parameter (Line 7 in Algorithm 5). Intuitively, such lower threshold has a role in preventing an explosion of the MIG in the first term of the elliptical potential count lemma (Lemma C.1) in the analysis. Note that such lower threshold is also leveraged in the existing variance-aware UCB-style algorithms (Zhou et al., 2021; ;; Zhang et al., 2021; Zhou & Gu, 2022). We believe this algorithm construction the most natural kernelized extension of the methods proposed in (Zhou et al., 2021: Zhang et al., 2021: Zhou & Gu, 2022).
Theoretical analysis for VA-GP-UCB.
Lemma I.1 (Adaptive confidence bound in non-stationary variance, e.g., Lemma 7 in (Kirschner & Krause, 2018)). Fix any strictly positive sequence (Ne)sets, and define E, as E, = diag({?,.... X?). Suppose Assumptions 2.1 and 2.2 holds with
26

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Algorithm 1 Phased Elimination (PE)
Require: Confidence width parameter B1/2 0, initial batch size N1. noise variance parameter X? 2 0. 1: Initialize the potential maximizer X1 < X.
2: for = 1,2,...de do
3: x 0.
4: for ,..... N₂ do
(8)
t arg max -2 (x; x
5:
zj
6: Observe vj" = 12) (0) + {
(1)
7:
X
[a mebi)-
8:
end for
9:
(0))
(1) y)
kE|NG]
10: Calculate lcb;(-) and (.) as
lcb;(ar) = MARIN;
(a; x (0)) - O (a;; x
ucb,(a)) = MARIN,
(x; x ()) 2 (x; x.)
11:
X441 x ucb;(x:) 2 max lob, (z) j. zeA:
12: Update the batch size N441 < 2N.
13: end for
Algorithm 2 Maximum Variance Reduction (MVR)
Require: Noise variance parameter X² 2
Xo
2: for = 1, ... T do
3: #t f- arg max (æ;; X,-1).
4: Observe y, and construct data X, = [az]]ee[t)
5: end for
6: Return the estimated solution क7 == arg max (2; XT:yT), where yr [Wnlee(T)-
Pr. )x. Then, for any algorithm, the following event holds with probability least 1 5:
1 [(x)) B + (xx) + 21n or, (2;; X,-1).
VL E N+, Vo E X, 1157, (2; 1,,,x-1,,9111
(130)
Lemma I.2 (General regret bound of VA-GP-UCB). Fix any <> and 8 E (0, 1). Suppose Assumptions 2.1 and 2.2 hold. + / (Tx) + 2 3, the following two statements hold with probability
Then, when running Algorithm with 8//2 at least - 8:
The cumulative regret Rr of VA-GP-UCB satisfies
Rr S 2B min (47 (4TT(ET), (4M(()) + 43//2 V(T + (T(T).
(nT(ET))
(131)
The simple regret rT of VA-GP-UCB satisfies
2B min (47 (ATT((E)) (Er) + T V(T + (2 yr (ET)
43
< T
(132)
In the above upper bound, the estimated solution Tr is defined as कr o7 with T. E arg mob Here, (ab)( is defined as leb,(xx) uE,-((m: X,-1, 91-1) - 83 σx (Rt; X,-1).
27

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Algorithm 3 Variance-aware phased elimination (VA-PE)
Require: Confidence width parameter B1/2 O, finite input set X, initial batch size N1 N4. 1: Initialize the potential maximizer X1 < X.
2: for = 1,2.... do
3: x 0, (5) 0.
4: for ,........ N₂ do
zy (6)
(x; (x:
5:
+ arg max y00
6: Observe /3 - / 2
+
(6)
7:
Obtain the variance proxy
(A 10)
8:
diag (210)² ..... (1/)))
9:
10:
end for
11:
(())
(8) y)
kE|NEl
Calculate lcb;(-) and (.) as
lcb,(x) My)(1)
x; x (1)
N, 211)
-31/20 2011)
x; X
ucb;(æ:) = My:(1)
x:: (
(o y01))
+ 3/12 0
x: X
13:
X441 + = X5 ucb;(x)) 2 max lcb:(T))
N.
Update the batch size N4+1 t 2N, 15: end for
Algorithm 4 Variance-aware maximum variance reduction (VA-MVR)
Require: Finite input set X.
1: Xo 0. F. 0.
2: for t 1,2. ......III. do
3: I, f arg max m (z; 1).
4: Observe yt, and obtain the variance proxy pi.
5: Construct data X, = (x a.leet
6: X₂ p7, E, + diag(Af....,,
7: end for
8: Return the estimated solution कe arg max (æ;; XT; where yr (Vll.e(T)-
Proof. From the construction of X Algorithm and the definition of /1/2, the event (130) holds with probability least
1 - 8. Hereafter, suppose the event (130) holds. Furthermore, T {t [T] X, o (z, X,-1) 1) and T (t e [T] \- -xx_, (m;; x,-)) 1}.
28

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Cumulative regret upper bound. We decompose Ry as Ri = EIET f(x²) [(x,) + EIET f(x") -(())) and consider the upper bound of each term separately. First, the first term satisfies
f(a")) f(x))) 2
Σ
By
0x (x; X,-1)
(133)
1ET
IET
I 2//9
1hnil (2;X,-)) X1-1)
(134)
TET
S 4
Σ X (E(T]
7T TT(TT
(135)
S 4
4
V(T + (2T) (ET).
(136)
where the first inequality follows from the event (130) and the UCB-selection rule of Ht, and the third inequality follows from the same arguments as Eqs. (32)-(36). Regarding the second term, from the extension of the elliptical potential count lemma (Lemma C.1), we have
Σ f(x)) f(x)) S 2B|T9| T
(137)
< 2B min (47 (1rr(Err) (77
(yr((E))
(138)
From Eqs. (135) and (138), we obtain the desired result.
Simple regret upper bound.
From the definition of Tr, for any t E T, we have
f(x²) - f(ăr) I (x.) leb;(ar))
(139)
S ucb)(xx)) lcb, S 20 ox. (2;; X,-1).
(140)
(141)
Furthermore, for any & E To, we have f(x') - f(ār) S 2B. By taking the average of the above inequalities, we have
f(0")- - ((ēr) < 7
Σ
2/21/2 os, (2; (1=; +
Σ
2B
(142)
LITT
LET
43 T
2B
( (2T)
7T (ET) + min ( (47 (4TT(ET), 4TT (Er)).
(143)
T
T
Theorem L.3 (Regret bound of VA-GP-UCB for k = KSE and k Ma Let us assume the same setting that of Lemma 1.2. Furthermore, suppose V1- = (2)).. Then, the following statements hold with probability at least 1 8,
k = ksg, by setting 2 as (== = 1/T, we have
Vr R₁ R = (Vyy and rr =0 (
In indttT)
(144)
T2
Ifk kaattrn by selting ạ as (² 1/T, we have
Rr = δ ( ( VTr and rT = Ō (T- 20 / VT
(
(145)
Proof. When b KSE, 7T (Tr) o In r 22
o (1n and 4///2 V(Vr (2T) 7r (2r)
0 (vT(Er) - (VT By noting Vr = 2(1), we obtain
RT = 0 (v T)
(146)
29

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
Algorithm 5 Variance-aware Gaussian process upper confidence bound (VA-GP-UCB)
Require: Confidence width parameter ///2 > 0, lower threshod Ç >> 0 of variance parameters.
1: Xo 3/ = 20
2: for t- 1..... T do
3: Compute ucb (a:) = 11 1 (o; 1, 32 0z, Po.0o,11000 X1-1).
4: 3t f- arg max
5: Observe y/+ - - (at) + Ex.
6:
Obtain the variance proxy p 2 0.
7:
AP c max {pi,
8:
X, f [mm]me((), Σt t- diag (A):...,
9: end for
from Lemma I.2.
When = Materr (r(ET) $ IT) = ō o ((E)) 20+4
/(V + 7447
= o Ō(T
24
δ @(Taatte (((tta)((()))
(52) auto (arta)) =0 ( (
and 43
0 (xT((V))VV))
24 δ Taris VVr). By noting Vi = (1)), we can conclude the following from Lemma 1.2:
RT = Ō (T20-44 20-4d
VT
(147)
Finally, by comparing the upper bound of rr and Ry in Lemma 1.2, we can also confirm that the simple regret bounds are followed by multiplying 1/T to the above cumulative regret upper bounds.
Remark 1.4. In Theorem I.3, we suppose that the learner does not have prior knowledge about Vr before running the algorithm. On the other hand, if we assume the learner knows Vr, the regret upper bound in Theorem I.3 can be smaller by setting the lower threshold Ç² depending on Vr. Specifically, when A kMaatrn the setting Ç² VT/T improves the polynomial dependence of Vy.
J. Potential Applications for Non-Stationary Variance Setting in GP-Bandits
In this section, we discuss potential applications for the non-stationary variance setting in GP-bandits.
Reinforcement Learning: The existing variance dependent algorithms in linear bandits (Zhou et al., 2021; Zhang et al., 2021; Zhou & Gu, 2022; Zhao et al., 2023) motivates the non-stationary variance setting as one of the online reinforcement learning problems. Specifically, Zhou al. (2021) consider the regret minimization problem under specific Markov decision process (MDP), which is called linear mixture MDP, and subsumes the linear bandit problem when the length of the horizon is 1. In the decision- decision-making under linear mixture MDP, Zhao et al. (2023) show the algorithm with variance-dependent regret guarantees. If we assume the linear mixture MDP whose feature map of the transition probability setting of the existing works (Zhou et al., 2021; Zhang al., 2021; Zhao et al., 2023) is naturally derived. Extensions in such reinforcement learning setting are an interesting direction for our future research.
and induced by some kernel function, the kernelized extension the
Experimental Design: scientific experiments, the observation noise level of the result of the experiment may vary over time. Specifically, the observation noise level can increase over extended periods due to factors such as environmental fluctuations, material degradation, or systematic drifts in measurement instruments. For example, such factors measurement accuracy have been observed in studies of chemical analysis (Hickstein al., 2018).
Stationary Setting with Heteroscedastic Variance: Kirschner Krause (2018) consider the heteroscedastic variance setting where the variance proxy (²xx)) may depend on the selected input Iy. If we apply our algorithm to a heteroscedastic setting, the resulting regret of our non-stationary variance algorithm quantified by the cumulative
30

---

Improved Regret Analysis in GP Bandits: Optimality for Noiscless Reward, RKHS norm, and Non-Stationary Variance
variance proxy Vi E (xx)) of the selected inputs'. The further precise quantification of the increasing speed of VT in this setting requires additional structural assumption about p²(.). For example, expect Vr is increasing sublinearly with our algorithm design of æ; if there exists unique maximizer x", and p² (x) - p² (x*) (as z + x²) and p²(x") 0 holds. We believe this research direction is an interesting application of our analysis to the heteroscedastic setting.
'Our VA-GP-UCB algorithm can be applied in the same conditionally sub-Gaussian assumption used in (Kirschner & Krause, 2018) (Eq. (1) in (Kirschner& & Krause, 2018)). On the other hand, VA-PE and VA-MVR algorithms require restricted independence assumption the noise sequence (Et) is conditionally independent given MVR input sequence.
31


Reviews:
[{"review_id": "aACEClSOcN", "reviewer": "Reviewer_7Bi6", "summary": "This paper presents improved theoretical guarantees for Gaussian Process (GP) bandit algorithms, with a particular focus on reducing regret under three key scenarios: the noiseless setting, dependence on the RKHS norm of the underlying reward function, and non-stationary noise variance. The main contribution is a new, tighter upper bound on the posterior variance of GP models used in MVR and PE algorithms. This result refines existing analyses by considering a subset of time indices in which the variance reduction is well-controlled, rather than uniformly averaging over all steps. As a result, the paper shows nearly optimal cumulative and simple regret bounds for standard kernels in various settings. The paper also provides regret bounds under time-varying noise, filling a gap in existing literature. Overall, the analysis is clean, and the technical results are novel and broadly applicable.\n\n## update after rebuttal\nThe authors have provided clear and satisfactory responses to most of the questions raised in the initial review. As a result, I will maintain my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for the overall positive feedback. We will carefully incorporate your comments into the revision. Below are the answers to your questions.\n\n**1. Have you considered evaluating your bounds under the polynomial kernel? Given its finite-dimensional nature, the information gain is logarithmic, and your results should match linear bandit regret bounds (I guess). This would be a valuable consistency check.**\n\nThank you for your suggestion. \nAs for the non-stationary variance setting, in Lines 402-424, we discuss the connection between the existing linear bandit method and \nour work. However, so far, we are not aware of the existing linear bandit literature that focuses on the noiseless setting, or the RKHS norm upper bound (L2-norm upper bound of linear parameter). Therefore, we will add the discussions in the revision after carefully investigating the related works in linear bandits.\n\n\n**2. Is it possible to extend your special time-index argument to randomized selection methods such as GP-TS? Could this lead to improved analyses for such algorithms?**\n\nAt least, maximum posterior variance upper bounds (e.g., Eq. (4)) are only applicable for the MVR algorithm. \nWe believe that the extension to other well-known algorithms is important for future work.\nOn the other hand, we can also obtain a more limited result: an algorithm-independent \"minimum\" posterior variance upper bound as Eq. (4). \nThis can be easily confirmed by replacing the L.H.S. of the inequality in Lines 229-231 with the minimum posterior variance. \nThis upper bound is meaningless for the analysis of the cumulative regret; however, it is useful for analyzing the simple regret of other algorithms or stopping time analysis for other problem settings (e.g., level-set estimation (Gotovos et al., 2013)).\n\n- Gotovos, Alkis, et al. \"Active learning for level set estimation.\" Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. 2013.\n\n**3. To ensure I understood the key technical improvement correctly: Is the main reason for the improved regret bound in Lemma 3.1 the fact that the authors consider a carefully chosen subset of time indices. This selective averaging strategy appears crucial, could the authors clarify how general this idea is, and whether it can be extended to other types of GP bandit algorithms beyond MVR?**\n\nSince the subset selection $\\mathcal{T}$ itself is conducted by the elliptical potential count lemma (Lemma 3.3), which is an algorithm-independent lemma, at least Eq. (9) always holds for any algorithm. On the other hand, dealing with the regret incurred from the remaining index set $\\mathcal{T}^c = [T] \\setminus \\mathcal{T}$ is difficult for algorithms other than MVR. So far, the only possible claim in algorithms other than MVR is the upper bound given on Lines 237-242 in the left column. As discussed in Lines 234-250 in the left column, although this gives a certain extent of improved dependence on the noise variance parameter for any algorithm, the decreasing speed of the noise variance is more restricted and is not sufficient to claim near-optimality in our analysis.", "claims_and_evidence": "The theoretical claims in the paper are generally well-supported. The main claim regarding the improved posterior variance upper bound (Lemma 3.1) is carefully proven, with clear intuition and appropriate use of mutual information and elliptical potential arguments. The paper also provides detailed corollaries (Corollary 3.2) that concretely instantiate the regret implications under SE and Matérn kernels. The claims about achieving optimal dependence on the RKHS norm are also backed by theorems with well-structured proofs and appropriate comparison to prior bounds. However, the paper does not discuss the polynomial kernel case, which was treated in prior work (e.g., Srinivas et al., 2010). Including this would help verify consistency with linear bandit results and strengthen the generality of the framework.", "methods_and_evaluation_criteria": "The methods are theoretically grounded and appropriate for the goal of tightening regret bounds under the GP bandit setting.", "theoretical_claims": "I checked the derivation of Lemma 3.1 and its application to the noiseless setting and RKHS-norm-dependent regret bounds. The idea of using a selected index subset $\\mathcal{T}$ for tighter bounding is novel and clean. The use of the elliptical potential count lemma and its adaptation are sound. The regret bounds in Theorems 4.1, 4.2, and 5.1 seem correct under the stated assumptions. I did not identify any obvious mistakes.", "experimental_designs_or_analyses": "There are no experiments in this paper, which is acceptable given its theoretical nature.", "relation_to_broader_scientific_literature": "The work builds upon classical results in GP bandits and recent advances in MVR and PE. It contributes to tightening regret bounds with respect to noise and RKHS norm, which is important in both theoretical and practical settings.", "essential_references_not_discussed": "References are sufficient enough.", "other_strengths_and_weaknesses": "- Theoretical novelty in posterior variance bounding technique.\n- Clear improvement over existing results in noiseless and RKHS-dependent settings.\n- Addresses an underexplored but practically relevant scenario of heteroscedastic noise.", "other_comments_or_suggestions": "- Consider adding a \"Notation Table\" near the end of Section 2 for ease of reference.\n- Discuss the behavior under polynomial kernels, as it connects to linear bandits and prior results.", "questions_for_authors": "1. Have you considered evaluating your bounds under the polynomial kernel? Given its finite-dimensional nature, the information gain is logarithmic, and your results should match linear bandit regret bounds (I guess). This would be a valuable consistency check.\n\n2. Is it possible to extend your special time-index argument to randomized selection methods such as GP-TS? Could this lead to improved analyses for such algorithms?\n- Chowdhury, Sayak Ray, and Aditya Gopalan. \"On kernelized multi-armed bandits.\" International Conference on Machine Learning. PMLR, 2017.\n\n3. To ensure I understood the key technical improvement correctly: Is the main reason for the improved regret bound in Lemma 3.1 the fact that the authors consider a carefully chosen subset of time indices $\\mathcal{T}=\\\\{\\frac{T}{2} \\geq 3 \\gamma_T(\\tilde{\\lambda}_T^2 I_T)\\\\}$, instead of averaging over all $[T]$? If so, this selective averaging strategy appears crucial, could the authors clarify how general this idea is, and whether it can be extended to other types of GP bandit algorithms beyond MVR?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CVFtd8bZdi", "reviewer": "Reviewer_ATja", "summary": "The paper develops a novel bound for the posterior variance of the Gaussian process. Such bounds are used to obtain a tighter regret bound of noise-free simple/cumulative regret bounds of Bayesian optimization algorithms. Furthermore, these bounds facilitates establishing novel regret bounds for MVR/PE algorithms in both stationary/nonstationary noise setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for the overall positive feedback. We will carefully incorporate your suggestions about the clarity into the revision.  Below is our answer to the reviewer's question.\n\n**Is the condition $\\mathcal{X} = [0, 1]^d$ necessary for corollary 6.1 and 6.2? If I recall correctly, Bull's result only assumes to be a compact subset (perhaps satisfying the interior cone condition) of the Euclidean space.**\n\nAlthough Bull's lower bound for the noiseless setting is applicable to any sufficiently regularized compact subset, the lower bound for the noisy setting in Scarlett et al. (2017) explicitly assumes $\\mathcal{X} = [0, 1]^d$.\nWe added this condition to be consistent with the setting in Scarlett et al. (2017). We also believe that the result of Scarlett et al. (2017) can be generalized to any compact subset whose packing number behaves as that of $[0, 1]^d$; however, since we are not aware of any formal proof in existing work, we decided to add the condition $\\mathcal{X} = [0, 1]^d$ explicitly.\n\n- Scarlett, Jonathan, Ilija Bogunovic, and Volkan Cevher. \"Lower bounds on regret for noisy Gaussian process bandit optimization.\" Conference on Learning Theory. PMLR, 2017.", "claims_and_evidence": "The claims made in this paper seem to be valid and convincing.", "methods_and_evaluation_criteria": "No numerical experiments.", "theoretical_claims": "I went through most of the appendix to check the validity of the manuscript. It seems to be a solid work.", "experimental_designs_or_analyses": "No numerical experiments.", "relation_to_broader_scientific_literature": "This paper provides a novel bound on posterior variance of Gaussian process, which can be utilized many downstreaming tasks involving Gaussian process.", "essential_references_not_discussed": "The manuscript contains a broad range of relevant literature, including the most up-to-date ones.", "other_strengths_and_weaknesses": "No significant weakness.\n\nThe manuscript contains several contributions in advancing the theory of Bayesian optimization. 1) By establishing the upper bound of the posterior variance, 2) it establishes competitive regret bounds for noise-free Bayesian optimization, 3) tightened PE/MVR regret bound under both stationary/nonstationary noise. I believe these contributions are non-trivial and, accordingly, the manuscript deserves to be accepted.", "other_comments_or_suggestions": "1. While I was able to follow the manuscript after spending quite a bit of time, I initially had a hard time following their notations to distinguish stationary/non-stationary bound. in Lemma 3.1, it would help readers if authors add a remark in clarifying the notations and the time index $t$ and $T$.\n\n2. The paper briefly describes the two metrics, simple regret and cumulative regret, in Section 2. It is worthwhile to distinguish the role/relationship of these regrets. For instance, simple regret represents the convergence rate, while the cumulative regret serves as a metric to assess the holistic performance of the algorithm, not just the final output.", "questions_for_authors": "Is the condition $\\mathcal{X} = [0,1]^d$ necessary for corollary 6.1 and 6.2? If I recall correctly, Bull's result only assumes $\\mathcal{X}$ to be a compact subset (perhaps satisfying the interior cone condition) of the Euclidean space.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "faHBoATwzH", "reviewer": "Reviewer_wREb", "summary": "The paper studies the classic problem of Bayesian optimization under the frequentist setting (where the target function lies in the RKHS of a known kernel). It derives a novel bound on the maximum variance after $T$ observations (Lemma 3.1). This bound has several consequences and applies to various Bayesian optimization problems. In the noiseless setting, it establishes near-optimal cumulative regret guarantees, addressing a COLT open problem. In the noisy setting, it improves regret bounds with respect to the RKHS norm of the target function. The results are also extended to the heteroscedastic noise setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for the overall positive feedback. Below are our answers to the reviewer's questions.\n\n**1. Are there additional technical challenges that should be emphasized, or ...**\n\nWe clarify the technical challenges and novelty of the results in Sections 4-6 below.\n- The results in Section 4 directly follow Lemma 3.1 with the existing analysis; therefore, once we obtain Lemma 3.1, there is no technical challenge.\n- The novelty of the results in Section 5 is the observation that the combination of the proper setting of $\\lambda^2 = \\Theta(B^{-2})$ and Lemma 3.1 results in the optimal dependence of RKHS norm $B$ in regret. However, the proof itself is straightforward and simple once we find the proper scaling of noise variance setting $\\lambda^2 = \\Theta(B^{-2})$.\n- The analysis in Section 6 contains non-trivial technical challenges in the proof, while we omit the discussion in the paper due to space limitations. Specifically, the time-varying variance proxies make the naive application of statement 2 in Lemma 3.1 difficult. One naive way is to set $\\tilde{\\lambda}_t^2$ as the true variance proxy $\\rho_t^2$; however, this strategy breaks the condition related to maximum information gain in Lemma 3.1 when $\\rho_t^2$ becomes too small. Another idea is to introduce the lower threshold against \nvariance proxy so that the condition lemma 3.1 always holds, but this strategy does not lead to the nearly-optimal dependence in the regret since the upper bound of the information gain is quantified only by the minimum of the elements in the noise variance parameter matrix. Roughly speaking, the difficult problem is that the existing theory of the information gain cannot capture the total noise level. For example, if the cumulative variance proxy is low, the information gain upper bound becomes very high if one of the variance proxies is very low. To overcome the above issues, we set $\\tilde{\\lambda}_t^2$ based on carefully chosen thresholds depending on the cumulative variance $V_T$ (Line 1221 for SE kernel, Line 1268 for Matern kernel). We believe that our paper's solution to the above-described issues is highly novel.\n\n\n**2. Can the authors specifically state the bounds on information gain that they use?**\n\nWe use the result of Vakili et al. (2021) (Corollary 1). As the reviewer kindly pointed out, we will add the citation in the revision.\n\n**3. Can similar bounds to those in Lemma 3.1 be established for the sum of variances rather than the maximum variance?**\n\nTo our current understanding, we cannot generalize our result to the sum of the posterior variance or the maximum variance in the algorithms other than MVR, because the effect of $\\mathcal{T}^c$ seems not negligible (See also next question's answer in detail). \nThe only thing we can obtain is an algorithm-independent \"minimum\" posterior variance upper bound as Eq. (4). Please see our related rebuttal of the #2 answer for Reviewer 7Bi6.\n\n\n**4. Can the authors provide more technical details on the comparison with Flynn and Reeb (2024)?**\n\nThe reason why we can obtain a stronger result than that in Flynn and Reeb (2024) is that the MVR algorithm does not have to care about the regret incurred from the time subset $\\mathcal{T}^c$, which is defined in Lemma 3.3. \nFlynn and Reeb (2024) uses elliptical potential count lemma for the analysis of GP-UCB; however, the resulting cumulative regret upper bound suffers from approximately $O(\\min\\\\{\\gamma_{\\gamma_T(\\lambda^2)}(\\lambda^2), \\gamma_T(\\lambda^2)\\\\} + \\sqrt{\\lambda^2 T \\gamma_T(\\lambda^2)})$ regret. While the second term is the favorable dependence against noise variance parameter (as with our upper bound in Eq.(4)), the existence of the first term, which comes from $\\mathcal{T}^c$ and the elliptical potential count lemma (Lemma 3.3), becomes problematic. \nSpecifically, if we desire optimal regret in our paper's settings (such as the noiseless setting), we have to decrease the noise variance parameter rapidly so that the second term $\\sqrt{\\lambda^2 T \\gamma_T(\\lambda^2)}$ matches the lower bound.\nThis can be done by setting the decreasing noise variance parameter $\\lambda^2$ such that the maximum information gain $\\gamma_T(\\lambda^2)$ increases almost linearly with $T$; however, in this case, the resulting regret becomes far away from the desired result due to the effect of the first term $O(\\min\\\\{\\gamma_{\\gamma_T(\\lambda^2)}(\\lambda^2), \\gamma_T(\\lambda^2)\\\\})$.\nOn the other hand, as described in the proof sketch of Lemma 3.1, we can obtain the maximum posterior variance bound of MVR without the effect $|\\mathcal{T}^c|$ by bounding the maximum variance with the average only on the favorable subset $\\mathcal{T} = [T]\\setminus \\mathcal{T}^c$ (Line 226-230 in the right column). Therefore, we can obtain stronger results than those in Flynn and Reeb (2024) by bypassing the above-described problematic behavior of their analysis with MVR.", "claims_and_evidence": "The proofs are provided and seem correct to me.", "methods_and_evaluation_criteria": "The paper is of theoretical nature.", "theoretical_claims": "I checked the proof of Lemma 3.1 in detail. Other results are sound.", "experimental_designs_or_analyses": "Not applicable!", "relation_to_broader_scientific_literature": "The paper improves regret bounds in a well-studied problem and addresses a COLT open problem.", "essential_references_not_discussed": "The bounds on information gain given in Section 2 seem from the following paper but the reference is not provided.\n \nOn information gain and regret bounds in gaussian process bandits, Vakili, S. and Khezeli, K. and Picheny, V., AISTATS 2021.", "other_strengths_and_weaknesses": "The paper is clearly written, with rigorous mathematics, and addresses regret bounds in BO under the frequentist setting, improving upon existing results.\n\nThe literature on BO with heteroscedastic noise, such as Makarova et al. (2021), does not seem to be well discussed.", "other_comments_or_suggestions": "Typos in the introduction: \"fileds\", \"Establised\". Check for more typos!", "questions_for_authors": "1. Are there additional technical challenges that should be emphasized, or do the results follow directly from combining Lemma 3.1 with the existing analysis for BO algorithms MVR and PE?\n\n2. Can the authors specifically state the bounds on information gain that they use?\n\n3. Is Footnote 1 on page 5 directly related to the results of this paper? Does Lemma 3.1 have implications for other algorithms such as GP-UCB? Can similar bounds to those in Lemma 3.1 be established for the sum of variances rather than the maximum variance?\n\n4. Can the authors provide more technical details on the comparison with Flynn and Reeb (2024)? While Lemma 3.3 appears to be a crucial step in both papers, what makes the results of this paper stronger? Is the improvement related to bounding maximum variance instead of the sum of variances?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "Not applicable!"}}, {"review_id": "1EbHtPdVCC", "reviewer": "Reviewer_MinQ", "summary": "This paper provides refined regret analyses of maximum variance reduction (MVR) type of algorithms in Gaussian Process (GP) bandits. It first establishes a general upper bound on the maximum posterior variance for MVR algorithm (Lemma 3.1), and applies it to obtain upper bounds on the cumulative regret and the simple regret in the noiseless setting (Section 4), the bounded RKHS norm setting (Section 5), and the time-varying noise variance setting (Section 6). Across all three settings, the resulting regret bounds improve the existing upper bounds previously established in the literature.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for the overall positive feedback. We will carefully incorporate the reviewer's feedback in the revision. Below is our answer to the reviewer's question.\n\n**In Section 5, the paper analyzes the algorithms with $\\lambda$ chosen to be different from the actual noise variance, unlike the other sections. Is this something necessary?**\n\nThe setting $\\lambda = \\Theta(B^{-2})$ is necessary to obtain improved dependence against the RKHS norm upper bound $B$. \nRoughly speaking, our result suggests that we should set smaller (larger) noise variance parameters if the underlying function could be complex (simple). This is intuitively reasonable from the frequentist point of view since the noise variance parameter of GP corresponds to the regularization parameter of the kernel ridge estimate. Namely, it is reasonable to set a suitable regularization parameter depending on the underlying function's complexity to obtain a good kernel ridge estimator and corresponding GP.", "claims_and_evidence": "All claims are made through theoretical analysis with solid proofs.\n\nAlthough I am not doubting the results, I believe the statements Corollary 3.2 should be made more explicit regarding the hidden constants. It was stated that those hidden constants have dependence on $\\mathcal{X}$, but it is unclear what the dependence is, even in their proofs in Appendix C.2. For example, is the constant finite even if $\\mathcal{X}$ is continuous or unbounded? I understand the authors' main goal is to analyze the dependence of regret on $T$, $B$, or $V_T$, but the hidden constants should be stated explicitly somewhere in the paper.", "methods_and_evaluation_criteria": "This paper suggests a novel analysis, not a novel algorithm. The MVR algorithm and its variant called PE algorithm are investigated in this paper, which would be fairly straightforward and sensible algorithms for GP bandits. As performance metrics, this paper investigated the cumulative regret and the simple regret, which are also standard in the literature.", "theoretical_claims": "I had a look into the proof of Lemma 3.1, Corollary 3.2, Theorem 4.1 and Theorem 4.2. I couldn’t find a critical error, although the proof of Corollary 3.2 lacks details.", "experimental_designs_or_analyses": "This paper does not include numerical experiments.", "relation_to_broader_scientific_literature": "The main contribution of this paper is that the improved regret upper bounds were established for GP bandits. At the core of their analysis, Lemma 3.1 plays an important role, suggesting improved posterior variance upper bounds for MVR. Although these results only apply to MVR algorithms, it is notable that the resulting regret bounds improve or match the state-of-the-art results including the other algorithms. I believe that this work will become one of key papers in the GP bandit area.\n\nI am not so sure about this paper’s contribution beyond GP bandits. As mentioned in the paper, this work is partly related to heteroscedastic linear bandits, but I do not see a clear implication.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Although the main contribution of this paper is theoretical analysis, I believe that it also has practical implications on the implementation of MVR algorithms -- the analysis provides a guideline on how to choose the algorithm parameters $\\beta$ or $\\lambda$ given the target time horizon $T$ or RKHS norm $B$. However, the analysis ends up revealing the optimal asymptotic dependence of those algorithm parameters on the problem constants. It will be great if explicit suggestions are given.", "other_comments_or_suggestions": "- It will also be great if the paper includes numerical experiments showing that MVR algorithms with suggested parameter choice actually perform very well.\n\n- I am not so sure whether \"heteroscedastic\" is the right term to describe the non-stationary noise variance setting. I would believe \"heteroscedastic\" describes the situation where the noise variance depends on the query point. If the algorithm adaptively chooses the query points utilizing the heteroscedastic noise variance, it may violate Assumption 2.2 saying that the noise sequence should be mutually independent. I believe the best description would be just \"time-varying noise variance\".", "questions_for_authors": "In Section 5, the paper analyzes the algorithms with $\\lambda$ chosen to be different from the actual noise variance $\\rho$, unlike the other sections. Is this something necessary?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the Gaussian Process bandits problem in noiseless, varying RKHS norm, and non-stationary variance settings. Due to the refined maximum posterior variance analysis, this paper provides improved bounds in these three settings. All reviewers like the technical novelties and contributions of this paper, therefore, I'm happy to recommend this paper for outstanding paper award and oral presentation.
Decision: Accept (oral)