Optimal Order Simple Regret for Gaussian Process Bandits
Authors: Sattar Vakili
Nacime Bouziani
Sepehr Jalali
Alberto Bernacchia
Da-shan Shiu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Gaussian Process Bandit
Confidence Intervals
RKHS
Optimal Order Simple Regret

Abstract: Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function $f$. The problem can be cast as a Gaussian Process (GP) bandit where $f$ lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. When $N$ is the number of exploration trials and $\gamma_N$ is the maximal information gain, we prove an $\tilde{\mathcal{O}}(\sqrt{\gamma_N/N})$ bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable to RKHS elements which may be of broader interest.

Optimal Order Simple Regret for Gaussian Process Bandits
Sattar Vakili", Nacime Bouziani
Sepehr Jalali", Alberto Bernacchia', Da-shan Shiu"
MediaTek Research
(sattar, vakili, sepehr. bopehr.jalle jalalii alberto. bernacchia, ds. www.sh/attrreeerrcccccoomm +mperial College London
n. bouzianii@@imperriiii ac.uk
Abstract
Consider the sequential optimization of continuous, possibly non-convex, and expensive to evaluate objective function f. The problem can be cast Gaussian Process (GP) bandit where f lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows significant gap between the lower and upper bounds on the simple regret performance. When is the number of exploration trials and "/ is the maximal information gain, we prove /N) bound the simple regret performance of pure exploration al algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up logarithmic factors for the cases where lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable RKHS elements which may be of broader interest.
Introduction
Sequential optimization has evolved into one of the fastest developing areas machine learning [1]. We consider sequential optimization of an unknown objective function from noisy and expensive to evaluate zeroth-order observations. That a ubiquitous problem in academic research and industrial production. Examples of applications include exploration in reinforcement learning, recommendation systems, medical analysis tools and speech recognizers [4]. A notable application the field of machine learning is automated hyper-parameter tuning. Prevalent methods such grid search can be prohibitively expensive [5, 6]. Sequential optimization methods, on the other hand, are shown to efficiently find good hyper-parametee by an adaptive exploration of the hyper-paramene parameter space [7].
Our sequential optimization setting is as follows. Consider an objective function f defined over domain X' C Rd, where d E N is the dimension of the input. A learning algorithm is allowed to perform an adaptive exploration to sequentially observe the potentially corrupted values of the objective function (Ix,) + ex J where are random noises. At the end of N exploration trials, the learning algorithm returns candidate maximizer 4 E X' of f. Let x* E argmaxze.a ((x) true optimal solution. We may measure the performance of the learning algorithm in terms of simple regret; that is, the difference between the performance under the true optimal solution, f(x"), and that under the learnt value, (+xx)
Our formulation falls under the general framework of continuum armed bandit that signifies receiving feedback only for the selected observation point at each time [8, 9, 10, 11]. Bandit problems have been extensively studied under numerous settings and various performance measures including simple
'Zeroth-order feedback signifies observations from f in contrast to first-order feedback which refers to observations from gradient of as e.g. in stochastic gradient descent [see, e.g., 2, 3].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

regret [see, e.g., 10, 12, 13), cumulative regret [see, e.g., 14, 15, 16], and best arm identification [see, e.g. 17, 18]. The choice of performance measure strongly depends on the application. Simple regret is suitable for situations with preliminary exploration phase (for instance hyper-paramett tuning) in which costs are not measured in terms of rewards but rather in terms of resources expended [10].
Due to infinite cardinality of the domain, approaching f(x") is feasible only when appropriate regularity assumptions on f and noise are satisfied. Following growing literature [19, 20, 21, 22], we focus on a variation of the problem where f is assumed to belong to a reproducing kernel Hilbert space (RKHS) that a very general assumption. Almost all continuous functions can be approximated with the RKHS elements of practically relevant kernels such as Matérn family of kernels [19]. We and light-tailed.
consider two classes of noise:
Our regularity assumption on f allows us to utilize Gaussian processes (GPs) which provide powerful Bayesian (surrogate) models for [23]. Sequential optimization based GP models is often referred to as Bayesian optimization in the literature [4, 24, 25). We build on prediction and uncertainty estimates provided by GP models to study an efficient adaptive exploration algorithm referred as Maximum Variance Reduction (MVR). Under simple regret measure, MVR embodies the simple principle of exploring the points with the highest variance first. Intuitively, the variance in the GP model is considered as a measure of uncertainty about the unknown objective function and the exploration steps are designed to maximally reduce the uncertainty. At the end of exploration trials, MVR returns a candidate maximizer based on the prediction provided by the learnt GP model. With its simple structure, MVR is amenable to a tight analysis that significantly improves the best known bounds on simple regret. To this end, we derive novel and sharp confidence intervals for GP models applicable to RKHS elements. In addition, we provide numerical experiments on the simple regret performance of MVR comparing it to GP-UCB [19, 20], GP-PI [26] and GP-EI [26).
1.1 Main Results
We first derive novel confidence intervals for GP models applicable to RKHS elements (Thcorems I and 2). As part of our analysis, we formulate the posterior variance of a GP model as the sum of two terms: the maximum prediction error from noise-free observations, and the effect of noise (Proposition 1). This interpretation elicits new connections between GP regression and kernel ridge regression [27]. These results are of interest on their own.
We then build the confidence intervals for GP models provide a tight analysis of the simple regret of the MVR algorithm (Theorem 3). In particular, we prove high probability Ö V simple regret, where "N is the maximal information gain (see $ 2.4). In comparison to O IN bounds on simple regret [see, e.g., 19, 20, 28], we show ((VTx) improvement. It is noteworthy that our bound guarantees convergence to the optimum value of f. while previous Ó TN bounds do not, since although "N grows sublinearly with N, it can grow faster than VN.
VN
We then specialize our results for the particular cases of practically relevant Matérn and Squared Exponential (SE) kernels. We show that our regret bounds match the lower bounds and close the gap reported in [28, 29], who showed that an average simple regret of requires N = Ω ( ()) exploration trials in the case of SE kernel. For the Matérn-v kernel (where v is the smoothness parameter, see $ 2.1) they gave the analogous bound of N 2 (1))+)). They also reported a significant gap between these lower bounds and the upper bounds achieved by GP-UCB algorithm. In Corollary 1, we show that our analysis of MVR closes this gap in the performance and establishes upper bounds matching the lower bounds up to logarithmic factors.
In contrast to the existing results which mainly focus on Gaussian and sub-Gaussian distributions for noise, we extend our analysis to the more general class of light-tailed distributions, thus broadening the applicability of the results. This extension increases both the confidence interval width and the simple regret by only multiplicative logarithmic factor. These results apply to e.g. the privacy preserving setting where often a light-tailed noise is employed [30, 31, 32].
'The notations O and Ô are used to denote the mathematical order and the mathematical order up to logarithmic factors, respectively.
2

---

1.2 Literature Review
The celebrated work of Srinivas et al. [19] pioneered the analysis of GP bandits by proving an ÓGN vN) upper bound on the cumulative regret of GP-UCB, an optimistic optimization algorithm sequentially selecting In which maximize an upper confidence bound index over the search space. That implies O 2x simple regret [28]. Their analysis relied on deriving confidence intervals for GP models applicable to RKHS elements. They also considered fully Bayesian setting where is assumed to be a sample from GP and noise is assumed to be Gaussian. [20] built on feature space representation of GP models and self-normalized martingale inequalities, first developed in [33] for linear bandits, to improve the confidence intervals of [19] by multiplicative log(N) factor. That led to an improvement in the regret bounds by the same multiplicative log(N) factor. A discussion on the comparison between these results and the confidence intervals derived in this paper is provided in 3.3. technical comparison with some recent advances in regret bounds requires introducing new notations and is deferred to $ 4.4.
The performance of Bayesian optimization algorithms has been extensively studied under numer- ous settings including contextual information [34], high dimensional spaces [35, 36), safety con- straints [37, 38], parallelization [39], meta-learning [40], multi-fidelity evaluations [41], ordinal models [42], corruption tolerance [43, 29], and neural tangent kernels [44, 45]. [46] introduced an adaptive discretization of the search space improving the computational complexity of a GP-UCB based algorithm. Sparse approximation of GP posteriors are shown to preserve the regret orders while improving the computational complexity of Bayesian optimization algorithms [36, 47, 48]. Under the RKHS setting with noisy observations, GP-TS [20] and GP-EI [49, 50J are also shown to achieve the same regret guarantees as GP-UCB (up to logarithmic factors). All these works report Ö regret bounds.
The regret bounds are also reported under other often simpler settings such as noise-free ob- servations [51, 52, en = 0, Vn] or Bayesian regret that is averaged over known prior on f [39,, 53, 54, 55, 56, 57, 58, 59], rather than for a fixed and unknown f as in our setting.
Other lines of work on continuum armed bandit exist, relying on other regularity assumptions such as Lipschitz continuity [9. 11, 12, 60], convexity [61] and unimodality [62], name a few. A notable example is [1 I] who showed that hierarchical algorithms based on tree search yield O(N कम) cumulative regret. We do not compare with these results due to the inherent difference in the regularity assumptions.
d+1
1.3 Organization
In $ 2, the problem formulation, the regularity assumptions, and the preliminaries on RKHS and GP models are presented. The novel confidence intervals for GP models are proven in MVR algorithm and its analysis are given in $ 4. The experiments are presented in 5. We conclude with discussion in $
2 Problem Formulation and Preliminaries
Consider an objective function f X' R, where X C IR is a convex and compact domain. Consider an optimal point xx argmax
A learning algorithm A sequentially selects observation points { E neN and observes the corresponding noise disturbed objective values {yn (*x, + en nnN,, where 6n is the observation noise. We use the notations H.. {X,, Y, X, = [x1, (2,,,2, x,, ",,]". Y.Y,Y
[y1, Vi..,,...., Vn] In, E X, yn E R. for all n 2 1. In simple regret setting, the learning algorithm determines a sequence of mappings {Sn)n21 where each mapping Sn Hr + X predicts a candidate maximizer 2,, For algorithm A, the simple regret under a budget
of N tries is defined as
N f(x S(xx)
The budget N may be unknown a priori. Notationwise, we use F, = [f(z), f(x))) and F., [e1, [e1,62, .2,..., en]" T to denote the noise free part of the observations and the noise history, respectively, similar to Xn, and Y..
3

---

2.1 Gaussian Processes
The Bayesian optimization algorithms build on GP (surrogate) models. GP a random process {f(x)))Exx where each of its finite subsets follow multivariate Gaussian distribution. The distribu- tion of GP is fully specified by its mean function (xx)) = E[f(x)] and a positive definite kernel (or -
covariance function) k(x,, x²) - E (())))((()))(() uxx))) Without loss generality, is lypically assumed that, for prior GP distributions, μ(x) O, Vo X.
Conditioning GPs on available observations provides us with powerful con-parametric Bayesian (surrogate) models over the space of functions. In particular, using the conjugate property, conditioned on Hu. the posterior of is GP with mean function J4n (x) [[f HHn] and kernel function kn (z. x²) [[(((x) pm (z))))
(x()))) specified follows:
(n(x) = h Xn) (k(X Xn,) 12 Yn:
kn(x,x') k(x,x') k (z, Xn) (k(Xn, Xn) + >² k(r'. Xn). oz(x)) & kn, x2,
where with some abuse of notation k(z, Xn) [k(z, 21), k(x, x2).............. ................................ k(x, =n,]",, k(X, Xn) [k(2,, 2y)li is the covariance matrix, Ln is the identity matrix of dimension n, and À > 0 a real number.
In practice Matérn and squared exponential (SE) are the most commonly used kernels for Bayesian optimization [see, e.g., 4, 24],
v 22p
"
V2vp 1
p² 212
MMatém (I, x0)
k x') exp
[(u)2K-1
where > 0 referred to as lengthscale, م || - x'I1t, is the Euclidean distance between x and x', > 0 is referred to as the smoothness parameter, I' and B, are, respectively, the Gamma function and the modified Bessel function of the second kind. Variation over parameter y creates a rich family of kernels. The SE kernel can also be interpreted special case of Matérn family when
2.2 RKHSs and Regularity Assumptions on
X' - E with respect finite Borel measure (e.g.. the Lebesgue measure) supported on X. A Hilbert space H₃ of functions on X' equipped with an inner product (.,))., He is called an RKHS with reproducing kernel k if the following is satisfied. For all x E X. k(., z) E Hy, and for all x E X' and f E Hμ. (f, k(., x)) H. = f(x) (reproducing property). constructive definition of RKHS requires introducing Mercer theorem, which provides an alternative representation of kernels as an inner product of infinite dimensional feature maps [see, e.g., 27, Theorem 4. 1] and is deferred to Appendix We have the following regularity assumption on the objective function
Consider a positive definite kernel k
Assumption The objective function ff is assumed to live in the RKHS corresponding to a positive definite kernel k. In particular, [f]]l, S. B. for some B >> O, where [| (f. f)
For common kernels, such as Matérn family of kernels, members of H₃ can uniformly approximate any continuous function any compact subset of the domain X' [19]. This is very general class of functions; more general than, e.g., the class of convex functions. has thus gained increasing interest in recent years.
2.3 Regularity Assumptions on Noise
We consider two different cases regarding the regularity assumption on noise. Let us first revisit the definition of sub-Gaussian distributions.
Definition A random variable X is called sub- Gaussian if its moment generating function M (()) e B[exp(hXX) is upper bounded by that of a Gaussian random variable.
The Sab-Gaussian assumption implies that [E[X] = 0. also allows us to use Chernoff- Dedemoff--Hoffding concentration inequality [63] in our analysis.

---

We next recall the definition of light-tailed distributions.
Definition 2 A random variable X called light-tailed if itss moment-generating function exists, i.e.
there exists ho > O such that for all [b] S ho, (h) < co.
For zero mean light-tailed random variable X, we have [64]
(h) S
exp(<nh2 (2),,nl/2),, 144 S ho, sup (M (b), |4| S ho):
where (.) denotes the second derivative of (.) and ho the parameter specified in Definition 2. We observe that the upper bound in (3) is the moment generating function of a zero mean Gaussian random variable with variance fo- Thus, light-tailed distributions are also called locally sub-Gaussian distributions [65].
We provide confidence intervals for GP models and regret bounds for MVR under each of the following assumptions on the noise terms.
Assumption (Sub-Gaussian Noise) The noise terms en are independent over n. In addition, vh E IR, Vn N, Biehs[]] & exp( R² for some 0.
Assumption (Light-Tailed Noise) The noise terms 6n zero mean independent random vari- ables over n.. In addition, vh < fo, Vn E N,Eje"=]] I exp( (050 (0 for some &o >
Bayesian optimization uses GP priors for the objective function, and assumes Gaussian distribution for noise (for its conjugate property). is noteworthy that the use of GP models is merely for the purpose of algorithm design and does not affect regularity assumptions on f and noise. We use the notation distinguish the GP model from the fixed f.
2.4 Maximal Information Gain
The regret bounds derived in this work are given in terms of the maximal information gain, defined as YN = su I[YN; f), where I(YN; f) denotes the mutual information between Y, and [see, e.g., 66, Chapter 2]. In the case of GP model, the mutual information can be given as I(Y,: f) 2/2 log det (In + x (X,,, (x)) where the notation (log) det denotes the (logarithm of) determinant of a square matrix. Note that the maximal information gain is kernel-specffic and Xx- independent. Upper bounds on 7N are derived in [19, 21, 22] which are commonly used to provide explicit regret bounds. In the of Matérn and SE kernels, 7N O (N (log(N)) ařfa| and IN O (log())))++1), respectively [22].
3 Confidence Intervals for Gaussian Process Models
The analysis of bandit problems classically builds on confidence intervals applicable to the values of the objective function [see, e.g., 67, 68). The GP modelling allows to create confidence intervals for complex functions over continuous domains. In particular, we utilize the prediction (f²)) and the uncertainty estimate (ax,) provided by GP models in building the confidence intervals which become an important building block of our analysis in the next section. To this end, we first prove the following proposition which formulates the posterior variance GP model as the sum of two terms: the maximum prediction error for an RKHS element from noise free observations and the effect of noise.
Proposition 1 Let 0 be the posterior variance of the surrogate GP model as defined in (2). Let 7 (x) TT (x, X,) (k:Xa, X,)) + x²Tx) have
(x)))= = sup (f(x) - 2, (x) 1Z)
filll1 $1
Notice that the first term f(x) 2,_ Fn captures the maximum prediction enror from noise free observations F,. The second term captures the effect noise in the surrogate GP model (and independent of F,). A detailed proof for Proposition I is provided in Appendix B.
5

---

Proposition elicits new connections between GP models and kernel ridge regression. While the equivalence of the posterior mean in GP models and the regressor in kernel ridge regression is well known, the interpretation of posterior variance of GP models as the maximum prediction enror for an RKHS element less studied [see 27, Section 3, for a detailed discussion on the connections between GP models and kernel ridge regression].
3.1 Confidence Intervals under Sub- Sub-Gaussian Noise
The following theorem provides confidence interval for GP models applicable RKHS elements under the assumption that the noise terms are sub-Gaussian.
Theorem Assume Assumptions and 2 hold. Provided noisy observations H, {Xns Y, from J. let pa and on be as defined in (2). Assume Xn are independent of F.n For fixed ar E X, define the upper and lower confidence bounds, respectively,
(x) A p2(x)) (B B(6)) (x). and (x) & p (B ((8)
(4)
with B(5) X / where å E (0,1), and B and R are the parameters specified in Assump-
tions and We have
f(x) & (x) w.p. at least 6, and f(x) 2 (x) wip. at least 5.
We can write the difference in the objective function and the posterior mean as follows.
fz) Mn (z) f(x) Z,, (
(x)
Z (z)
Prediction error from noise free observations
The effect noise
The first term be bounded directly following Proposition 1. The second term is bounded result of Proposition and Chernoff- soeooof--oeffiiggggg inequality. A detailed proof of Theorem is provided in Appendix C.
3.2 Confidence Intervals under Light-Tailes Noise
We now extend the confidence intervals the case of light-tailed noise. The main difference with uub-Gaussian noise is that Chernoff-Hoefdding inequality is no more applicable. We derive new bounds accounting for light-tailed noise in the analysis of Theorem 2.
Theorem Assume Assumptions I and 3 hold. For fixed X, define the upper and lower confi-
dence bounds (x)) and (x)) similar to Theorem with 3(5) à //22 (Eo V 2ogg()) where E (0,1), and B, he and Eo are specified in Assumptions and Assume Xn are independens of E,, We have
log( (f) 3,
f(x) S (x( w.p. at least 1 - 8, and f(x) 2 (x) w.p. at least 1 -
In comparison to Theorem 1, under the light-tailed assumption, the confidence interval width increases with multiplicative O( o(ylog(()) log( factor. A detailed proof of Theorem 2 is provided in Appendix C.
Remark Theorems and rely on the assumption that Xn, are independent of E,, As we shall see in 4, this assumption is satisfied when the confidence intervals are applied to the analysis of MVR.
3.3 Comparison with the Existing Confidence Intervals
The most relevant work to our Theorems and 2 is [20, Theorem 2] which itself was improvement over [19, Theorem 6]. [20] built on feature space representation of GP kernels and self-normalized
ô confidence interval in the same form in Theorem under Assumptions and 2, with confidence interval width B R 2(Th + 1 log(
martingale inequalities [33, 69] to establish
Thee notation V is used to denote the maximum of two real numbers, Ya, E IR, (a V b) é ma)
NNte that the effect of À is absorbed in "n.

---

(instead of B + B())). There is a stark contrast between this confidence interval and the one given in Theorem in its dependence on Yn. which has relatively large and possibly polynomial value. That contributes extra (VTTN) multiplicative factor to regret.
Neither of these two results (our Theorem and [20, Theorem 2)) imply the other. Although our confidence interval is much tighter, there are two important differences in the settings of these theorems. One difference is in the probabilistic dependencies between the observation points 2,, and the noise terms { While Theorem assumes that Xn are independent of E., [20, Theorem 2] allows for the dependence of 2n on the previous noise terms {G)]ien This is a reflection of the difference in the analytical requirements of MVR and GP-UCB. The other difference is that [20, Theorem holds for all z E X. While, Theorem holds for single E X. As we will see in 4.2, probability union bound can be used to obtain confidence intervals applicable to all x in (a discretization of) X, which contributes only logarithmic terms to regret, in contrast to ((v)n). Roughly speaking, we are trading off the extra O (n))) term for restricting the confidence interval to hold for single æ. It remains an open problem whether the same can be done when Ii are allowed to depend on {ej)iso
4 Maximum Variance Reduction and Simple Regret
In this section, we first formally present an exploration policy based on GP models referred to as Maximum Variance Reduction (MVR). We then utilize the confidence intervals for GP models derived in 3 to prove bounds on the simple regret of MVR.
4.1 Maximum Variance Reduction Algorithm
MVR relies on the principle of maximally reducing the uncertainty, where the uncertainty measured by the posterior variance of the GP model. After N exploration trials, MVR returns a candidate maximizer according to the prediction provided by the learnt GP model. A pseudo-code is given in Algorithm 1.
Algorithm Maximum Variance Reduction (MVR)
1: Initialization: k, X, (x) k(x, w).
2: for = 1,2,.... N do
3: Ix argmax (z), where a tie is broken arbitrarily.
4: Update (.) according (2).
5: end for
6: Update (.) according (2).
7:
return iyy- = argmax............ xE (z), where a tie is broken arbitrarily.
We note that MVR, similar other standard GP bandit algorithms, requires optimizing an internal index created based on previous observations (here, o (-) and (.)( Examples of other typical indices are UCB and EI, which often referred to as acquisition functions. The index itself may be multi modal in general. It is however standard to assume a perfect optimization of the index, since the cost of evaluating f considered dominate the cost of maximizing the index [19].
4.2 Regret Analysis
For the analysis of MVR, we assume there exists a fine discretization of the domain for RKHS elements, which is a standard assumption in the literature [see, e.g., 19, 20, 48].
Assumption For each given N and f Hy with fl I B, there exists discretization DD, of X such that f f(x f((z]n) S V where [x), argmin,''pp. || - ælle is the closest point in Dn to x, and [D.] < 4/2, where C' is a consiant independent of n and B.
Assumption 4 is mild assumption that holds for typical kernels such as SE and Matérn [19, 20]. The following theorem provides a high probability bound on the regret performance of MVR, when the noise terms satisfy either Assumption or 3.
7

---

Theorem 3 Consider the GP bandit problem, with fixed N. Under Assumptions 1, 4, and (2 or 3), for 5 (0, 1), with probability at least MVR satisfies
NyN V log(1 + )
2B + BC +
3C B (NN322/333) d mure
2
VN
where under Assumption 2. 3(0)
3. V log(t)) and under Assumption 3, B(6)
x 1/2 (5o 2log(#) #
log(t), and B, R. ho. Eo and C are the constants specified in Assump-
tions 1, 2, 3 and 4.
A detailed proof of the theorem is provided in Appendix D.
Remark Under Assumptions and 3, respectively, the regret bounds can be simplified as
MVR YN log(Nd/0) and IN =o
( IN log(N4 (2g(N4/8) (8)
= O(V
TN
N
For instance, in the case of Matérn-v kernel, under Assumption and 3, respectively,
MVV TN
-
OON (NazAa (log(N)) avi4 av4a (log(N488) and V'N = O (N zu (log(N)) =4 log (og(NN//)) 18)).
which always converge zero N grows.
Remark 3 In the analysis of Theorem 3, apply Assumption 4 PN well For this purpose, derive high probability B + 3N3(26 /3N) upper bound on || Hr (see Lemma 4 in Appendix D), which appears in the regret bound expression.
Remark Theorem 3 holds for a fixed N. The result however easily extends to an anytime regret bound, using standard probability union bound over N. Specifically, we replace 8 in the bound with 6g
68 N2N2, the theorem holds, with probability 6, for all N N. Note that ΣN=1 xaNa
65
4.3 Optimal Order Simple Regret with SE and Matérn Kernels
To enable direct comparison with the lower bounds simple regret proven in [28, 29]. in the following corollary, we state a dual form of Theorem 3 for the Matérn and SE kernels. Specifically formalize the number of exploration trials required achieve average regret.
Corollary Consider the GP bandit problem with SE Matérn kernel. For E (0, 1), define N. min(N E N E[ on N, are reported in Table 1.
MVR I c, vn 2 N). Under Assumptions 1, 4, and (2 or 3), upper bounds
Table 1: The upper bounds on N. defined in Corollary with SE or Matérn kernl.
Kernel
Under Assumption
Under Assumption 3
SE
N. O ((t)² log( () dd2)
N. O ((t)² log( ( t)a+3)
Matérn-v
N. = 0 (2)2 (log(
10td 20
N. =0=0 (2)2+ (log( (2)) 60424
A proof is provided in Appendix E. [28, 29] showed that for the SE kernel, average simple regret of e requires N. = S2 - (log( (1))( For the Matérn-ı kernel they gave the analogous bound of
N. = Ω 2+) They also reported significant gaps between these lower bounds and the existing results [see, e.g., 28, Table I]. Comparing with Corollary 1, our bounds are tight all cases up to log(1/e) factors.

---

4.4 Comparing the Regret Bounds with Other Related Work
There are several Bayesian optimization algorithms namely GP-UCB [19], IGP-UCB, GP-TS [20],
TruVar [70], GP-EI [50, 49] and KerneUUCB [71] which enjoy theoretical upper bounds on regret
under Assumptions 1, 2 and 4. The regret bounds of these algorithms grow at least as fast as O 2x ).
That does not necessarily converge to zero, since "NN can grow faster than vN, resulting in trivial regret bounds. For example, in the case of a Matérnyy kernel, inserting "/N Ö(N حमح [22] gives 222
an ON
4- ) regret, which does not converge to zero for > 2v, meaning the algorithm does not
necessarily approach f(x").
More recently, [21] developed GP-UCB based algorithm, specific to Matérn family of kernels, that constructs cover for the search space, many hypercubes, and fits independent GP to each cover element. This algorithm, referred to as π T-GP-UCB, was proven to achieve diminishing regret for all 1 and d 2 1. In particular, [21, Theorem 3] provided an upper bound on the regret of I-GPUUCB which in our notation implies rN
). In contrast, our bound for the case of ON 20 is uniformly tighter that the bound on T' r.-G-UCB for all > 1 and d 2 1. [72] introduced LP-GP-UCB where the GP model is augmented with local polynomial estimators to construct a multi-scale upper confidence bound guiding the sequential optimization. They further improved the regret bounds of [21] and showed that the performance of L.P-GP-UCD matches the lower bound for some configuration of parameters V and d in the case of a Matérn kernel.
-.--U-UCBB = Ö(N 4u (ataaii
2xr
Matérn kernel r
Defining Lo- = (0, 1]. 1 (1, ddd+1) 1 = d(d+1) d' +5d 12 and I3 = o0) To I U Iz,
2
4
their bounds on simple regret are as follows. For v E To U I LP.GP-UBB = Ö(N a+4 ). For v E Iz, IN
(ddddd)))) ..P..PP.UBB = Ō(N For E Is. "N r.P.GP.UCC = Ó(N S042d)(45)
[see, 72, Sec. 3.2, for a detailed discussion on bounds on the simple regret of LP-GP-UCBB. In comparison, our bounds on simple regret match the 2 Ierd) ) lower bound [28], up logarithmic factors, with all parameters and d. In addition, LP-GP-UCB is impractical due to large constant factors, though practical heuristic was also given.
Of important theoretical value, SupKerneUUCB [71], which builds on episodic independent batches of observations, was proven to achieve ( (X regret on finite set ((X1) oo). SupKernelUCB is reported to perform poorly in practice [21, 47, 29]. While the proof of the regret bound for SupKernlUUCB is given on finite set, relying on the remarks from [21] and [29, Appendix A.4], we note that the bounds can be extended to a continuous domain using a discretization argument. That SupKemelUCB leads to 'N bound on r is tighter with a factor of (log(N)) #
Ollog((N) (N) ) under similar assumptions as ours. In comparison, our
is noteworthy that our techniques do not directly apply to the analysis of cumulative regret of algorithms such as GP-UCB, The key difference is that in MVR the observation points 2,, are independent of the noise terms en (although Vn are allowed to depend on {zy}y<m, and ã is allowed to depend on {Z 6n (n)),)) while in GP-UCB xn, are allowed depend on {ez jej (see also Sec. 3.3). It remains an interesting open question whether the existing analysis of the regret performance of GP-UCB [20] is tight or the gap with the lower bound [28] an artifact of its proof. For more details on this open question, see [73].
Experiments
In this section, we provide numerical experiments on the simple regret performance of MVR, Improved GP-UCB (IGP-UCB) presented in [20], and GP-PI and GP-EI as presented in [26].
We follow the experiment set up in [20] generate test functions from the RKHS. First, 100 points are uniformly sampled from interval [0, 1]. A GP sample with kernel k is drawn over these points. Given this sample, the mean of posterior distribution used as the test function f. Parameter X2 is set to 1% of the function range. For IGP-UCB we set the parameters exactly as described in [20]. The GP model is equipped with SE or Matérn-2. 2.5 kernel with / = 0.2. We use different models for the noise: zero mean Gaussian with variance equal to X² (a sub-Gaussian distribution) and zero mean I Laplace with scale parameter equal to X (a light-tailed distribution). We run each experiment over 25 independent trials and plot the average simple regret in Figure 1. More experiments on

---

two commonly used benchmark functions for Bayesian optimization (Rosenbrock and Hartman3) are reported in Appendix Further details on the experiments are provided in the supplementary material.
ISPNUCC DRUPI
3.-
ION-UCA
Aectag- Sirple Regeo
OPLI
1.0
Nuerogs Simble
00
100
120
205
20.0
400
120
25gg
250
(a) SE, Gaussian Noise
(b) Matémn Gaussian Noise
OP-N
Smpp
Nocrations
(c) SE, Laplace Noise
(d) Matérn, Laplace Noise
Figure 1: Comparison of the simple regret performance of Bayesian optimization algorithms on samples from RKHS.
6 Discussion
In this paper, we proved novel and sharp confidence intervals for GP models applicable to RKHS elements. We then built on these results to prove Ö( ((V /N) bounds for the simple regret of an adaptive exploration algorithm under the framework of GP bandits. In addition, for the practically relevant SE and Matérn kernels, where a lower bound on regret is known [28, 291, we showed the order optimality of our results up logarithmic factors. That closes a significant gap in the literature of analysis of Bayesian optimization algorithms under the performance measure of simple regret.
The limitation of work adhering simple regret that neither theoretical nor experimental re- sults proves that MVR is necessarily the right algorithm in practice. Overall, ppploration-exploitaaei oriented algorithms such as GP-UCB may perform worse than MVR in terms of simple regret due two reasons. One is over-exploitation of local maxima when f is multimodal, and the other is depen- balancing hyper-parameet
dence on an ppploration-explotattte to guarantee low regret bounds. Furthermore, their existing analytical regret bounds are suboptimal and possibly trivial (non-diminishing: when 7N grows faster than VN, as discussed). On the other hand, when compared in terms of cumulative regret ( [xx) (xx))) MVR suffers from linear regret.
that is often set too conservatively,
The main value of our work is in proving tight bounds on the simple regret of a GP based exploration algorithm, when other Bayesian optimization algorithms such as GP-UCB lack a proof for an always diminishing regret under the same setting as ours. It remains an open question whether the possibly trivial regret bounds of GP-UCB (as well as GP-TS and GP-EI. whose analysis is inspired by that of GP-UCB) is fundamental limitation or an artifact of the proof [73].
Funding Disclosure
This work was funded by MediaTek Research.
10

---

References
[1] Eric Mazumdar, Aldo Pacchiano, Yi-an Ma, Peter L Bartlett, and Michael Jordan. On thompson sampling with langevin algorithms. Proceedings of ICML, 2020.
[2] Alekh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. arXiv preprint arXiv: 107. /744, 2011.
[3] Sattar Vakili and Qing Zhao. A random walk approach to first-order stochastic convex optimiza- tion. In IEEE International Symposium on Information Theory (ISIT), 2019.
[4] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148-175, 2016.
[5] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In 25th annual conference on neural information processing systems (NIPS 20/1), volume 24. Neural Information Processing Systems Foundation, 2011.
[6] Robert T McGibbon, Carlos X Hernández, Matthew P Harrigan, Steven Kearnes, Mohammad M Sultan, Stanislaw Jastrzebski, Brooke Husic, and Vijay S Pande. Osprey: Hyperparameter optimization for machine learning. Journal of Open Source Software, 155)34, 2016.
[7] Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter optimization at scale. arXiv preprint arXiv:1807.01770 2018.
[8] Rajeev Agrawal. The continuum continuum-armed bandit problem. SIAM journal on control and optimiza- tion, 33(6):1226-195 1995.
[9] Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 17:697-704, 2004.
[10] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in finitely-armed and continuous-armed bandits. Theoretical Computer Science, 412(19):1832-1185) 2011.
[11] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5). 2011.
[12] Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. In International Conference on Machine Learning, pages 1133-13 1 111.. PMLR, 2015.
[13] Aniket Anand Deshmukh, Srinagesh Sharma, James Cutler, Mark Moldwin, and Clayton Scott. Simple regret minimization for contextual bandits. arXiv preprint /rXiv:/8I1l 181007337, 2018.
[14] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235-22 2-635555,,,,6 May 2002.
[15] Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint 1r4.v:190..07272. 2019.
[16] Qing Zhao Multi-armed bandits: Theory and applications to online learning in networks. Synthesis Lectures Communication Networks, 12(1):1-165, 2019
[17] Jean-Yves Audihert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53, 2010.
[18] Aditya Grover, Todor Markov, Peter Attia, Norman Jin, Nicolas Perkins, Bryan Cheong, Michael Chen, Zi Yang. Stephen Harris, William Chuch, et al. Best arm identification in multi-armed bandits with delayed feedback. In International Conference on Artificial Intelligence and Statistics, pages 833-842. PMLR, 2018.
[19] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 1015-1022. Omnipress, 2010.
11

---

[20] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi- bandits. In International Conference on Machine Learning, pages 844-853, 2017.
[21] David Janz, David Burt, and Javier Gonzalez. Bandit optimisation of functions in the matern kernel rkhs. In Proceedings of Machine Learning Research, volume 108, pages 2495. PMLR, 26 28 Aug 2020.
[22] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. arXiv preprint arXiv:2009.6696) 2020.
[23] Carl E Rasmussen and Christopher KI Williams. Caussian Processes for Machine Learning. MIT Press, 2006.
[24] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems 25, pages 2951- - 2959. Curran Associates, Inc., 2012.
[25] Peter Frazier. Bayesian optimization. Recent Advances in Optimization and Modeling of Contemporary Problems, pages 255-278 INFORMS, 2018.
[26] Matthew D Hoffman, Eric Brochu, and Nando de Freitas. Portfolio allocation for bayesian optimization. In UAI, pages 327-336. Citeseer, 2011.
[27] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. Available at Arxiv, 2018
[28] Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proceedings of the 2017 Conference on Learning The- ory, volume 65 of Proceedings of Machine Learning Reseurch, pages 1723-1742, Amsterdam, Netherlands, 07-10 Jul 2017. PMLR.
[29] Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust gaussian process bandit optimization. arXiv preprint (rXXi:20008.8757 2020.
[30] Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privacy for multi- armed bandits: What is it and what is its cost? arXiv preprint arXiv: /2298, 2019.
[31] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint NXXx:2007.00121,, 2020.
[32] Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning, arXiv preprint arXiv:2006.00701, 2020.
[33] Y. Abbasi-Yadkor,, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits.
In Advances Neural Information Processing Systems, pages 2312-2320, 2011.
[34] Andreas Krause and Cheng S. Ong. Contextual gaussian process bandit optimization. In Advances in Neural Information Processing Systems 24, pages 2447-2455. Curran Associates, Inc., 2011.
[35] Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional gaussian process bandits. In Advances in Neural Information Processing Systems 26, pages 1025-1033. Curran Associates, Inc., 2013.
[36] Mojmir Mutny and Andreas Krause. Efficient high dimensional bayesian optimization with additivity and quadrature fourier features. In Advances in Neural Information Processing Systems 31, pages 9005-9016. Curran Associates, Inc., 2018
[37] Felix Berkenkamp, Andreas Krause, and Angela Schoellig. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. arXiv preprint 1602.0600 2016.
[38] Yanan Sui, Vincent Zhuang, Joel W Burdick, and Yisong Yue. Stagewise safe bayesian optimization with gaussian processes. arXiv preprint 17X7511806.07555,2000 2018.
12

---

[39] Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Paral- lelised bayesian optimisation via thompson sampling. In International Conference on Artificial Intelligence and Statistics, pages 133-142, 2018.
[40] Zi Wang, Beomjoon Kim, and Leslie Pack Kaelbling. Regret bounds for meta bayesian optimization with an unknown gaussian process prior. In Advances in Neural Information Processing Systems, pages 10477-10488, 2018.
[41] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabas Poczos. Multi- fidelitfidlityy&& gaussian process bandit optimisation. Journal of A'rtificial Intelligence Research, 66:151-196, 2019.
[42] Victor Picheny, Sattar Vakili, and Artem Artemev. Ordinal bayesian optimisation. arXiv preprint 1/X1n:19/. 2019.
[43] Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-toleran gaussian process bandit optimization. arXiv preprint arXiv:2003.01971, 2020.
[44] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
[45] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010.00827, 2020.
[46] T. Javidi and S. Shekhar. Gaussian process bandits with adaptive discretization. Electron. J. Statist., 12(2):3829-3877 2018.
[47] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Proceedings of the Chirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, Phoenix, USA, 25-28 Jun 2019. PMLR.
[48] Sattar Vakili, Victor Picheny, and Artem Artemev. Scalable thompson sampling using sparse gussian process mdels. Available at Arxiv, 2020.
[49] Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. In Asian Conference Machine Learning, pages 279-294, PMLR, 2017.
[50] Ziyu Wang and Nando de Freitas. Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters. arXiv preprint arXiv: 2014.
[51] Adam D. Bull. Convergence rates of efficient global optimization algorithms. The Journal of Machine Learning Research, 2011.
[52] Sattar Vakili, Victor Picheny, and Nicolas Durrande. Regret bounds for noise-free bayesian optimization. arXiv preprint arXiv:2002.0509% 2020.
[53] Zi Wang, Beomjoon Kim, and Leslie Pack Kaelbling. Regret bounds for meta bayesian optimization with an unknown gaussian process prior. arXiv preprint arXiv:1811.09558 2018.
[54] Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In 34th International Conference on Machine Learning, ICML 2017, volume 7, pages 5530-5543, 2017.
[55] Jonathan Scarlett, Tight regret bounds for bayesian optimization in one dimension. arXiv preprint arXiv: 1805. / 1792, 2018
[56] Shubhanshu Shekhar and Tara Javidi. Significance of gradient information in bayesian opti- mization. International Conference on Artificial Intelligence and Statistics, pages 2836-2844. PMLR, 2021.
13

---

[57] Steffen Grünewälder, Jean-Yve Audibert, Manfred Opper, and John Shawe-Taylor Regret bounds for gaussian process bandit problems. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pages 273-280, 2010.
[58] Nando de Freitas, Alex J Smola, and Masrour Zoghi. Exponential regret bounds for gaussian process bandits with eterministic observations. In Proceedings of the 29th International Conference Machine Learning, pages 955-962, 2012.
[59] Kenji Kawaguchi, Leslie Pack Kaelbling, and Tomás Lozano-Pére Pérez.. Bayesian optimization with exponential convergence. In Advances in Neural Information Processing Systems, volume 2015-Janua, pages 2809-2817, 2015.
[60] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681-690, 2008.
[61] Alekh Agarwal, Dean Foster, Daniel Hsu, Sham M. Kakade, and Alexander Rakhlin and. Stochastic convex optimization with bandit feedback. In Advances in Neural Information Processing Systems, 2011.
[62] Richard Combes, Alexandre Proutière, and Alexandre Fauquette. Unimodal bandits with continuous arms: Order-optimal regret without smoothness. Proceedings of the ACM Measurement and Analysis of Computing Systems, 4(1):1-28, 2020.
[63] Rita Giuliano Antonini, Yuriy Kozachenko, and Andrei Volodin. Convergence of series of dependent --subgaussian random variables. Journal of mathematical analysis and applications. (8662):118-12000 2008.
[64] Patrick Chareka, Ottilia Chareka, and Sarah Kennendy. Locally sub-gaussian random variable and the strong law large numbers. Atlantic Electronic Journal of Mathematics, 1(1):75-81, 2006.
[65] Sattar Vakili, Keqin Liu, and Qing Zhao. Deterministic sequencing of exploration and exploita- tion for aulti-armed bandit problems. IEEE Journal of Selected Topics in Signal Processing. 7(5):759-767, 2013.
[66] Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
[67] Peter Auer. Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[68] S Bubeck, N Cesa-Bianchi, and G Lugosi. Bandits with heavy tail. arxiv. arXiv preprint arXiv: 1209. 1727, 2012.
[69] Victor H Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer Science & Business Media, 2008
[70] Ilija Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher. Truncated variance reduction: A unified approach to bayesian optimization and level-set estimation. arXiv preprint 1rXiv:1610.07379. 2016.
[71] Michal Valko, Nathan Korda, Rémi Munos, Iaas Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, 13 page 653,663, Arlington, Virginia, USA, 2013.
AUAI Press.
[72] Shubhanshu Shekhar and Tara Javidi. Multi-scale zero-order optimization of smooth functions in an rkhs. arXiv preprint arXiv:2005.0483. 2020.
[73] Sattar Vakili, Jonathan Scarlett, and Tara Javidi. Open problem: Tight online confidence intervals for rkhs elements. In Conference on Learning T'heory pages 4647-4652, PMLR, 2021.
14


Reviews:
[{"review_id": "lt8bRpT0ejq", "reviewer": "Reviewer_yRtV", "summary": "The paper derives improved upper bounds for the best-arm identification problem in GP bandits. Specifically, they improve the previously best-known upper bound on simple regret from O(\\gamma_N/\\sqrt{N}) to O(\\sqrt{\\gamma_N/N}), where \\gamma_N is the maximal information gain and N is the number of function evaluations. \n\nRemoving the extra \\sqrt{\\gamma_N} factor is important as \\gamma_N can grow faster than \\sqrt{N}. In particular, for the special cases of Matern and SE kernels, the authors show that the new bound (unlike old ones) goes to 0 as N-->\\infty and is only logarithmically far from previously established lower bounds. \n\nThe improvement in regret analysis boils down to a new confidence ellipsoid bound that is available for both subgaussian and light-tailed noise distributions. Unlike previous works, that focused on cumulative regret, the new confidence ellipsoid bound requires that query points x_1,...,x_n are independent of noise terms e_1,...,e_n for each n. This additional restriction gives improved bounds and is not restrictive for best-arm identification using a maximum variance reduction algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "To the best of my knowledge, the author's result is new and shows clear improvement to state-of-the-art for important problem of best-arm identification in GP bandits. Comparison to related literature is transparent and nicely presented. Also, the paper is very well-written and I believe is accessible and will be of interest to broad audience. Thus, I recommend acceptance.\n\nOne remark:\nYou mention a few times that \"simple regret is favorable in situations with a preliminary exploration phase\". It might be worth elaborating a bit on this point. A concrete example would benefit the reader distinguish between the relevance of simple vs cumulative regret. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work. Limitations of the analysis is clearly presented.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "iae3Ei4H6JE", "reviewer": "Reviewer_kShU", "summary": "The paper introduces a new approach for simple regret minimization in Bayesian optimization. This is a useful testbed as an intermediate setting harder than pure black-box optimization due to the presence of noise, but avoiding some of the worst case pitfalls of a cumulative regret analysis.\n\nNote that a GP with noisy observation will use regularization in its posterior, and that standard analysis is to split the prediction error in a part depending on the regularized posterior as if it was trained on the noiseless feedback and an error term as if it was trained only on the noise. From this template the paper derives its two main novel approaches:\n- Prop. 1, a new equality that connects the maximum (worst-case) prediction error of a regularized posterior trained on (unavailable) noiseless observation to the posterior variance of the regularized GP plus a regularization term depending on the regularization (and therefore on the noise level) \n- Thm. 1, where the main difference is that using Prop. 1 the authors construct a point-by-point concentration inequality rather than the more commonly martingale concentrations used in the literature that apply to the whole input space. The upside is that this allows for confidence intervals whose radius does not depend on the information gain $\\gamma_N$, unlike most methods. The downside is that it requires the noise to be uncorrelated with the observations, which in optimization means that the candidates for evaluation are chosen without looking at the feedback at all. The authors also provide a variant (Thm. 2) for light-tailed noise.\n\nWith these two tools the regret analysis is pretty straightforward, relying on an ideal discretization of the input space to extend the for-any concentration to a for-all bound, and then union bound the success probability. The final tool required is a unsupervised strategy to select candidates, and the authors resort to greedy information gain maximization, playing a sort of optimism role in the inner optimization loop. Finally all the candidates are evaluated and the best candidate found is returned.\n\nCompared to other simple regret minimization approaches, this shaves a $\\sqrt{\\gamma_N}$ factor off, taking it closer to its min-max lower bound. \n\nExperimentally, the proposed approach does not seem to outperform existing methods, slightly weakening the argument that the tighter confidence interval improves exploration/exploitation trade-offs in practice. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Overall I feel that the paper is an interesting contribution, but is held back by placing several crucial comparisons in the appendix, painting a picture in the main paper that is not fully satisfactory. For this reason I would like the paper to more clearly state what is a true improvement and what is not.\n\nThe phrase L66:\"It is noteworthy that our bound guarantees convergence to the optimum value off, while previous ̃$O(\\gamma_N/\\sqrt{N})$ bounds do not\" is quite misleading. There are at least two other algorithms that match MVR's regret rate. SupKernelUCB already achieves the improved $O(\\sqrt{\\gamma_N/N})$ rate, and is only mentioned in the appendix, while it should be the most obvious baseline. pi-GP-UCB is also guaranteed to achieve at least sub-linear regret, but is only cited and not discussed in the main paper.\nElements brought in favour of MVR in the appendix are 1) generality, 2) simpler implementation  and 3) working efficiently in practice (L28)\n1) Regarding generality, SupKernelUCB holds for any kernel just like MVR. pi-GP-UCB is specific to the Matern kernel, but note that also MVR's analysis require a good discretization that is not easy to find for kernel that are not translation invariant. Regarding the restriction\nof SupKernelUCB's analysis only to finite sets, both Janz et al. [21] and Cai et al [29, Appendix A.4] argue that it can be easily extended to continuous settings with a discretization argument similar to the one used for MVR. Moreover in practice running MVR with guarantees might also requires a discrete set (more of this later) and not being so easy to apply to continuous set.\n2) Regarding simplicity of implementation, even a single iteration of the MVR optimization problem (which is known in the literature as greedy information gain maximization) is a well known NP-HARD problem on continuous sets, since it requires optimizing a non-convex function. In practice, this essentially voids the regret guarantees for MVR, unless the domain is finite where we can find the optimum by enumeration. Comparing the complexity of MVR and pi-GP-UCB, MVR is indeed simpler but pi-GP-UCB is not much harder to implement than IGP-UCB (it is essentially IGP-UCB + a tree partitioning of the space), and IGP-UCB is included in the experimental comparison.\n3) Regarding working efficiently in practice, the plots are quite inconclusive. If all the algorithms converge quickly before 100 iterations, it makes little sense to plot up to 400 iterations with markers every 50. It would rather be more useful to zoom in the first 100 iterations, and increase the number of repetitions to observe convergence speed.\n\nOverall I find the paper quite interesting, and a nice bridge between online simple regret optimization and active learning. However the lack of comparison with its most obvious baselines, no statistically significant improvement even on toy data, and several minor exposition problems (more in detail later) push it slightly under the bar. I am open to reconsider my score if a more rigorous comparison is included where appropriate in the main paper rather than the appendix, showing clearly where MVR outperforms existing state of the art methods.\n\nMINOR:\n-The probability delta for a single sample and delta for the overall algorithm should be probably indicated with different symbols. It took me a long time to understand why large discretizations would negatively impact the regret, until i noticed that the denominator of the beta function becomes the numerator of the logarithm.\n-It might be good to include a remark highlighting that the algorithm needs to know both a bound on the function norm and on the noise level, which are usually hard to estimate. This is ok and common in the frequentist literature, but under bayesian assumptions the norm of the function can be unknown.\n- It would be good to include in the appendix one or two examples of how to generate covering grids that satisfy the assumptions (and if the method used in the experiments do so).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As a theory paper the direct societal impact is not a direct concern.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "b1AJ7dLm29D", "reviewer": "Reviewer_wjVJ", "summary": "This paper considers the Gaussian process optimization problem where the objective function f lives in a reproducing kernel Hilbert space (RKHS). So far there is a significant gap between the lower and upper bound on the simple regret performance. The authors propose a full exploration algorithm, called Maximum Variance Reduction (MVR) which achieves a simple regret bound $\\mathcal O^*(\\frac{\\sqrt{\\gamma_T}}{T})$, where {\\gamma_T} is the maximum information gain. This bound significantly improves the existing simple regret bounds. Further, on specific Square Exponential and Mat\\’ern kernels, their bound matches the lower bound up to logarithmic factors. Further, the authors extend their results to the more general class of light-tail distributions, thus broadening the applicability of the results. Finally, they validate their theoretical results on several synthetic functions and show that their algorithm is better than other algorithms such as GP-PI, GP-EI, IGP-UCB. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The paper is well written and easy to follow. A central result of their theoretical analysis is to provide the novel and sharp confidence intervals for GP model in the RKHS space. This key result is obtained via a novel connection between Gaussian processes regression and Kernel ridge regression.  Under the theoretical view, this is a good paper. The results are significant especially these novel confidence intervals. While simulations are a bit limited given that we are looking at a new algorithm, I do not see it as much limitation as the key focus here is theory. \n\nQuestion: In all experimental results, why the graphs of MVR always decrease while the graphs of other baselines are not stable? \n\nSome minor mistakes: \n1.\tThe formula of EI acquisition at line 212 seems incorrect (the argument of function \\Phi should be \\sigma/\\kappa instead of \\kappa/\\sigma). If so, please fix it!\n2.\tAt the second equation in the proof of Lemma 1, t should be n. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "FUHP8VOvIuO", "reviewer": "Reviewer_HA1h", "summary": "This paper studies the problem of pure exploration in Gaussian processes. In particular, given a function sampled from a GP, the paper gives bounds on the simple regret of the classifier: the gap between the predicted optimum at time n and the true optimum. The authors assume an additive noise model where the noise is either assumed to be subgaussian or more generally “light tailed” according to a definition provided therein. In these settings, the authors develop novel confidence widths for GPs with additive noise. These are not the first bounds for GPs. Chowdhury and Gopalan for instance give tight confidence widths. What is novel is that in contrast to past works, the authors do not assume that the additive noise is Gaussian- a fact that makes computing past posterior distributions easier. These bounds allow the authors to derive simple regret bounds that scale like O(\\sqrt(\\gamma_N / N)) matching known lower bounds up to logarithmic factors and shaving a factor of \\sqrt(\\gamma_N) off of prior art. As the authors note, without this improvement, there are settings where past algorithms are not guaranteed to converge while theirs is. It is worth noting however, that the lower bounds given in 28 and 29 appear to be minimax in nature which would imply that the algorithms presented in this paper are minimax optimal, but that an instance dependent algorithm may be possible. For instance, a very recent work (recent enough that is does not impact my score since that would be unfair) https://arxiv.org/abs/2105.05806 studies pure exploration in RKHSs and gives a instance dependent result. They specialize their result to the GP case, and it may be worth comparing against them?", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strengths: The paper is very clearly written and easy to understand which I appreciate as a reviewer. The theoretical results seem strong too. In particular, the confidence widths may be of more practical relevance than the rest of the paper given the growing popularity of GP and RKHS models. The algorithm also improves over prior art in terms of simple regret. I would be curious to know if using these confidence widths with past algorithms could lead to improvements on the order of \\sqrt(\\gamma_N) as well or if the improvements that this paper shows in its simple regret guarantee are algorithmic as well as due to the confidence bound. The latter is a stronger contribution than the former, especially since MVR sampling exists in previous work. \n\nWeaknesses: There is little improvement empirically. Furthermore, it is unclear if the gains in this paper are due solely to the confidence widths or if the design of the algorithm is important too. For the empirical study, it is unclear how the other experiments would perform if they had access to the same confidence widths presented in this work. This may make the algorithmic comparison fairer since the differences in performance would be solely due to the sampling procedures. Also, (and I am torn on this since the setup is nice and clear) it is worth noting that the authors are most of the way through page 5 before any results are presented. \n\nOther comments and questions:\n-\tDoes theorem 1 hold for an adaptive sequence of x_n’s or a fixed sequence? The theorem just seems to specify a set of (x,y)’s that have been collected. Ie, is this a truly anytime result or for a fixed sequence? In the case of a linear kernel, the gap in the confidence widths between an anytime and fixed confidence bound is O(\\sqrt(d)) which behaves like O(sqrt(\\gamma_n)) in that setting. I guess that the algorithm is using these as an adaptive sequence which is maybe okay from a Bayesian perspective. \n-\tSame question for Thm 2\n-\tFor the result in remark 2, do other works get the same factor of d since log(N^d) = dlog(N)? This work is tighter in terms of \\sqrt(\\gamma) but is the d dependence the same?\n-\tWhy is MVR the right sampling objective?\n-\tRegarding the statement in Section 6 about simple and cumulative regret bounds, it is somewhat expected that the cumulative regret is linear if you do this well on simple regret as your objective is largely one of exploration. Take for example the SE kernel as the variance \\sigma -> 0. In this setting, we recover standard multiarmed bandits where http://sbubeck.com/ALT09_BMS.pdf for instance show that there cannot be an algorithm that is simultaneously optimal in both simple and cumulative regret. \n\nMinor comments: \n-\tMake sure that the colors chosen for the plots are colorblind friendly. There are a variety of palettes in python for this. \n-\tSome of the axes in the plots in the main body and especially Appendix G are hard to read. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do a good job discussing the limitations of their work, though more consideration should be given to potential negative societal impacts than simply saying “our work is theoretical, therefore we can do no wrong.”", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the reviews and discussion, the consensus is that the contributions of the paper are valuable and worth publication in NeurIPS, particularly the new confidence bounds leading to a simple proof of order-optimal simple regret.  The initial concerns were largely resolved following the author response.   One reviewer score remains below the threshold, but unfortunately that reviewer did not respond to the rebuttal nor take part in any of the discussions, so I will not put as much weight on their score, even with the highest-confidence rating.  The reviewing team did, however, discuss that reviewer's concerns, and came to the consensus that they serve as points that should be addressed in the final version, but not serve as a reason for rejection.  Specifically:
- Please carefully move the comparisons to the most related earlier works (e.g., pi-GP-UCB, SupKernelUCB) to the main body and expand them.
- Ideally provide at least a brief mention of the issue of being able to optimize the acquisition function exactly.
- Comparing experimentally to pi-GP-UCB would have been ideal, but was not judged to be essential.  Nevertheless, the experiment section could be revised, adding more data points in the plots for t in [0,50], and discussing the results more (e.g., yours vs. IGP-UCB).

Beyond these points, please incorporate the other reviewer comments carefully, and additionally be careful of typos, e.g., (i) the arguments to k(.,.) in Appendix C and (ii) several missing E[.] operations after Line 87 of the supplementary material. These are both central to the analysis, so additional careful proof-reading is strongly encouraged.
Decision: Accept (Poster)