Optimal Order Simple Regret for Gaussian Process Bandits
Year: 2021

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 γN is the maximal information gain, we prove an Õ( √ γ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.

text: √ γ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.

heading: 1 Introduction
text: Sequential optimization has evolved into one of the fastest developing areas of machine learning [1]. We consider sequential optimization of an unknown objective function from noisy and expensive to evaluate zeroth-order1 observations. That is 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 in the field of machine learning is automated hyper-parameter tuning. Prevalent methods such as grid search can be prohibitively expensive [5, 6]. Sequential optimization methods, on the other hand, are shown to efficiently find good hyper-parameters by an adaptive exploration of the hyper-parameter space [7].
Our sequential optimization setting is as follows. Consider an objective function f defined over a domain X ⊂ Rd, where d ∈ 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 {f(xn) + n}Nn=1, where n are random noises. At the end of N exploration trials, the learning algorithm returns a candidate maximizer x̂∗N ∈ X of f . Let x∗ ∈ argmaxx∈X f(x) be a 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, f(x̂∗N ).
Our formulation falls under the general framework of continuum armed bandit that signifies receiving feedback only for the selected observation point xn at each time n [8, 9, 10, 11]. Bandit problems have been extensively studied under numerous settings and various performance measures including simple
1Zeroth-order feedback signifies observations from f in contrast to first-order feedback which refers to observations from gradient of f as e.g. in stochastic gradient descent [see, e.g., 2, 3].
35th Conference on Neural Information Processing Systems (NeurIPS 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 a preliminary exploration phase (for instance hyper-parameter 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 a 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 is 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 consider two classes of noise: sub-Gaussian and light-tailed.
Our regularity assumption on f allows us to utilize Gaussian processes (GPs) which provide powerful Bayesian (surrogate) models for f [23]. Sequential optimization based on 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 to 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].

heading: 1.1 Main Results
text: We first derive novel confidence intervals for GP models applicable to RKHS elements (Theorems 1 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 on the confidence intervals for GP models to provide a tight analysis of the simple regret of the MVR algorithm (Theorem 3). In particular, we prove a high probability Õ( √ γN N ) 2 simple regret, where γN is the maximal information gain (see § 2.4). In comparison to Õ( γN√N ) bounds on simple regret [see, e.g., 19, 20, 28], we show an O(√γN ) improvement. It is noteworthy that our bound guarantees convergence to the optimum value of f , while previous Õ( γN√
N ) bounds do
not, since although γN grows sublinearly with N , it can grow faster than √ N .
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 = Ω ( 1 2 (log( 1 )) d 2 ) exploration trials in the case of SE kernel. For the Matérn-ν kernel (where ν is the smoothness parameter, see § 2.1) they gave the analogous bound of N = Ω ( ( 1 ) 2+ dν ) . 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 a multiplicative logarithmic factor. These results apply to e.g. the privacy preserving setting where often a light-tailed noise is employed [30, 31, 32].
2The notations O and Õ are used to denote the mathematical order and the mathematical order up to logarithmic factors, respectively.

heading: 1.2 Literature Review
text: The celebrated work of Srinivas et al. [19] pioneered the analysis of GP bandits by proving an Õ(γN √ N) upper bound on the cumulative regret of GP-UCB, an optimistic optimization algorithm sequentially selecting xn which maximize an upper confidence bound index over the search space. That implies an Õ( γN√
N ) simple regret [28]. Their analysis relied on deriving confidence intervals for
GP models applicable to RKHS elements. They also considered a fully Bayesian setting where f is assumed to be a sample from a 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 a 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. A 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 numerous settings including contextual information [34], high dimensional spaces [35, 36], safety constraints [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, 50] are also shown to achieve the same regret guarantees as GP-UCB (up to logarithmic factors). All these works report Õ( γN√
N )
regret bounds.
The regret bounds are also reported under other often simpler settings such as noise-free observations [51, 52, n = 0,∀n] or a Bayesian regret that is averaged over a 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], to name a few. A notable example is [11] who showed that hierarchical algorithms based on tree search yieldO(N d+1 d+2 ) cumulative regret. We do not compare with these results due to the inherent difference in the regularity assumptions.

heading: 1.3 Organization
text: 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 § 3. MVR algorithm and its analysis are given in § 4. The experiments are presented in § 5. We conclude with a discussion in § 6.

heading: 2 Problem Formulation and Preliminaries
text: Consider an objective function f : X → R, where X ⊆ Rd is a convex and compact domain. Consider an optimal point x∗ ∈ argmaxx∈X f(x). A learning algorithm A sequentially selects observation points {xn ∈ X}n∈N and observes the corresponding noise disturbed objective values {yn = f(xn) + n}n∈N, where n is the observation noise. We use the notationsHn = {Xn, Yn}, Xn = [x1, x2, ..., xn]
>, Yn = [y1, y2, ..., yn]>, xn ∈ X , yn ∈ R, for all n ≥ 1. In a simple regret setting, the learning algorithm determines a sequence of mappings {Sn}n≥1 where each mapping Sn : Hn → X predicts a candidate maximizer x̂∗n. For algorithm A, the simple regret under a budget of N tries is defined as
rAN = f(x ∗)− f(x̂∗N ). (1)
The budget N may be unknown a priori. Notationwise, we use Fn = [f(x1), f(x2), . . . , f(xn)]> and En = [ 1, 2, . . . , n]> to denote the noise free part of the observations and the noise history, respectively, similar to Xn and Yn.

heading: 2.1 Gaussian Processes
text: The Bayesian optimization algorithms build on GP (surrogate) models. A GP is a random process {f̂(x)}x∈X , where each of its finite subsets follow a multivariate Gaussian distribution. The distribution of a GP is fully specified by its mean function µ(x) = E[f̂(x)] and a positive definite kernel (or covariance function) k(x, x′) = E [ (f̂(x)− µ(x))(f̂(x′)− µ(x′)) ] . Without loss of generality, it is
typically assumed that, for prior GP distributions, µ(x) = 0,∀x ∈ X . Conditioning GPs on available observations provides us with powerful non-parametric Bayesian (surrogate) models over the space of functions. In particular, using the conjugate property, conditioned on Hn, the posterior of f̂ is a GP with mean function µn(x) = E[f̂(x)|Hn] and kernel function kn(x, x ′) = E[(f̂(x)− µn(x))(f̂(x′)− µn(x′))|Hn] specified as follows:
µn(x) = k >(x,Xn) ( k(Xn, Xn) + λ 2In )−1 Yn,
kn(x, x ′) = k(x, x′)− k>(x,Xn) ( k(Xn, Xn) + λ 2In )−1 k(x′, Xn), σ 2 n(x) , kn(x, x), (2)
where with some abuse of notation k(x,Xn) = [k(x, x1), k(x, x2), . . . , k(x, xn)]>, k(Xn, Xn) = [k(xi, xj)] n i,j=1 is the covariance matrix, In is the identity matrix of dimension n, and λ > 0 is 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],
kMatérn(x, x ′) =
1
Γ(ν)2ν−1
(√ 2νρ
l
)ν Bν (√ 2νρ
l
) , kSE(x, x ′) = exp ( − ρ 2
2l2
) ,
where l > 0 is referred to as lengthscale, ρ = ||x− x′||l2 is the Euclidean distance between x and x′, ν > 0 is referred to as the smoothness parameter, Γ and Bν are, respectively, the Gamma function and the modified Bessel function of the second kind. Variation over parameter ν creates a rich family of kernels. The SE kernel can also be interpreted as a special case of Matérn family when ν →∞.

heading: 2.2 RKHSs and Regularity Assumptions on f
text: Consider a positive definite kernel k : X × X → R with respect to a finite Borel measure (e.g., the Lebesgue measure) supported on X . A Hilbert space Hk of functions on X equipped with an inner product 〈·, ·〉Hk is called an RKHS with reproducing kernel k if the following is satisfied. For all x ∈ X , k(·, x) ∈ Hk, and for all x ∈ X and f ∈ Hk, 〈f, k(·, x)〉Hk = f(x) (reproducing property). A 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 A. We have the following regularity assumption on the objective function f .
Assumption 1 The objective function f is assumed to live in the RKHS corresponding to a positive definite kernel k. In particular, ||f ||Hk ≤ B, for some B > 0, where ‖f‖2Hk = 〈f, f〉Hk .
For common kernels, such as Matérn family of kernels, members of Hk can uniformly approximate any continuous function on any compact subset of the domain X [19]. This is a very general class of functions; more general than, e.g., the class of convex functions. It has thus gained increasing interest in recent years.

heading: 2.3 Regularity Assumptions on Noise
text: We consider two different cases regarding the regularity assumption on noise. Let us first revisit the definition of sub-Gaussian distributions.
Definition 1 A random variableX is called sub-Gaussian if its moment generating functionM(h) , E[exp(hX)] is upper bounded by that of a Gaussian random variable.
The sub-Gaussian assumption implies that E[X] = 0. It also allows us to use Chernoff-Hoeffding concentration inequality [63] in our analysis.
We next recall the definition of light-tailed distributions.
Definition 2 A random variable X is called light-tailed if its moment-generating function exists, i.e., there exists h0 > 0 such that for all |h| ≤ h0, M(h) <∞.
For a zero mean light-tailed random variable X , we have [64]
M(h) ≤ exp(ξ0h2/2), ∀|h| ≤ h0, ξ0 = sup{M (2)(h), |h| ≤ h0}, (3)
whereM (2)(.) denotes the second derivative ofM(.) and h0 is 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 ξ0. 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 2 (Sub-Gaussian Noise) The noise terms n are independent over n. In addition, ∀h ∈ R,∀n ∈ N,E[eh n ] ≤ exp(h 2R2
2 ), for some R > 0.
Assumption 3 (Light-Tailed Noise) The noise terms n are zero mean independent random variables over n. In addition, ∀h ≤ h0,∀n ∈ N,E[eh n ] ≤ exp(h 2ξ0 2 ), for some ξ0 > 0.
Bayesian optimization uses GP priors for the objective function f and assumes a Gaussian distribution for noise (for its conjugate property). It is noteworthy that the use of GP models is merely for the purpose of algorithm design and does not affect our regularity assumptions on f and noise. We use the notation f̂ to distinguish the GP model from the fixed f .

heading: 2.4 Maximal Information Gain
text: The regret bounds derived in this work are given in terms of the maximal information gain, defined as γN = supXN⊆X I(YN ; f̂), where I(YN ; f̂) denotes the mutual information between Yn and f̂ [see, e.g., 66, Chapter 2]. In the case of a GP model, the mutual information can be given as I(Yn; f̂) = 12 log det ( In + 1 λ2 k(Xn, Xn) ) , where the notation (log) det denotes the (logarithm of) determinant of a square matrix. Note that the maximal information gain is kernel-specific and XN - independent. Upper bounds on γN are derived in [19, 21, 22] which are commonly used to provide explicit regret bounds. In the case of Matérn and SE kernels, γN = O ( N d 2ν+d (log(N)) 2ν 2ν+d ) and
γN = O ( (log(N))d+1 ) , respectively [22].

heading: 3 Confidence Intervals for Gaussian Process Models
text: 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 us to create confidence intervals for complex functions over continuous domains. In particular, we utilize the prediction (µn) and the uncertainty estimate (σn) 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 of a 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 σ2n be the posterior variance of the surrogate GP model as defined in (2). Let Z>n (x) = k >(x,Xn) ( k(Xn, Xn) + λ 2In )−1 . We have
σ2n(x) = sup f :||f ||Hk≤1 (f(x)− Z>n (x)Fn)2 + λ2‖Zn(x)‖2l2 .
Notice that the first term f(x)− Z>n (x)Fn captures the maximum prediction error from noise free observations Fn. The second term captures the effect of noise in the surrogate GP model (and is independent of Fn). A detailed proof for Proposition 1 is provided in Appendix B.
Proposition 1 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 error for an RKHS element is less studied [see 27, Section 3, for a detailed discussion on the connections between GP models and kernel ridge regression].

heading: 3.1 Confidence Intervals under Sub-Gaussian Noise
text: The following theorem provides a confidence interval for GP models applicable to RKHS elements under the assumption that the noise terms are sub-Gaussian.
Theorem 1 Assume Assumptions 1 and 2 hold. Provided n noisy observations Hn = {Xn, Yn} from f , let µn and σn be as defined in (2). Assume Xn are independent of En. For a fixed x ∈ X , define the upper and lower confidence bounds, respectively,
Uδn(x) , µn(x) + (B + β(δ))σn(x), and L δ n(x) , µn(x)− (B + β(δ))σn(x), (4)
with β(δ) = Rλ √ 2 log(1δ ), where δ ∈ (0, 1), and B and R are the parameters specified in Assumptions 1 and 2. We have
f(x) ≤ Uδn(x) w.p. at least 1− δ, and f(x) ≥ Lδn(x) w.p. at least 1− δ.
We can write the difference in the objective function and the posterior mean as follows.
f(x)− µn(x) = f(x)− Z>n (x)Yn = f(x)− Z>n (x)Fn︸ ︷︷ ︸ Prediction error from noise free observations − Z>n (x)En︸ ︷︷ ︸ The effect of noise .
The first term can be bounded directly following Proposition 1. The second term is bounded as a result of Proposition 1 and Chernoff-Hoeffding inequality. A detailed proof of Theorem 1 is provided in Appendix C.

heading: 3.2 Confidence Intervals under Light-Tailed Noise
text: We now extend the confidence intervals to the case of light-tailed noise. The main difference with sub-Gaussian noise is that Chernoff-Hoeffding inequality is no more applicable. We derive new bounds accounting for light-tailed noise in the analysis of Theorem 2.
Theorem 2 Assume Assumptions 1 and 3 hold. For a fixed x ∈ X , define the upper and lower confi-
dence bounds U δn(x) and L δ n(x) similar to Theorem 1 with β(δ) = 1 λ √ 2 ( ξ0 ∨ 2 log( 1δ )
h20
) log( 1δ ) 3,
where δ ∈ (0, 1), andB, h0 and ξ0 are specified in Assumptions 1 and 3. AssumeXn are independent of En. We have
f(x) ≤ Uδn(x) w.p. at least 1− δ, and f(x) ≥ Lδn(x) w.p. at least 1− δ.
In comparison to Theorem 1, under the light-tailed assumption, the confidence interval width increases with a multiplicative O( √
log( 1δ )) factor. A detailed proof of Theorem 2 is provided in Appendix C.
Remark 1 Theorems 1 and 2 rely on the assumption that Xn are independent of En. As we shall see in § 4, this assumption is satisfied when the confidence intervals are applied to the analysis of MVR.

heading: 3.3 Comparison with the Existing Confidence Intervals
text: The most relevant work to our Theorems 1 and 2 is [20, Theorem 2] which itself was an improvement over [19, Theorem 6]. [20] built on feature space representation of GP kernels and self-normalized martingale inequalities [33, 69] to establish a 1 − δ confidence interval in the same form as in Theorem 1, under Assumptions 1 and 2, with confidence interval widthB+R √ 2(γn + 1 + log( 1 δ )) 4
3The notation ∨ is used to denote the maximum of two real numbers, ∀a, b ∈ R, (a ∨ b) , max(a, b). 4Note that the effect of λ is absorbed in γn.
(instead of B + β(δ)). There is a stark contrast between this confidence interval and the one given in Theorem 1 in its dependence on γn, which has a relatively large and possibly polynomial in n value. That contributes an extra O(√γN ) multiplicative factor to regret. Neither of these two results (our Theorem 1 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 xn and the noise terms { j}j<n. While Theorem 1 assumes that Xn are independent of En, [20, Theorem 2] allows for the dependence of xn on the previous noise terms { j}j<n. This is a reflection of the difference in the analytical requirements of MVR and GP-UCB. The other difference is that [20, Theorem 2] holds for all x ∈ X . While, Theorem 1 holds for a single x ∈ X . As we will see in § 4.2, a 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 O(√γn). Roughly speaking, we are trading off the extra O(√γn) term for restricting the confidence interval to hold for a single x. It remains an open problem whether the same can be done when xn are allowed to depend on { j}j<n.

heading: 4 Maximum Variance Reduction and Simple Regret
text: 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.

heading: 4.1 Maximum Variance Reduction Algorithm
text: MVR relies on the principle of maximally reducing the uncertainty, where the uncertainty is 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 1 Maximum Variance Reduction (MVR)
1: Initialization: k, X , f , σ20(x) , k(x, x). 2: for n = 1, 2, . . . , N do 3: xn = argmaxx∈Xσ 2 n−1(x), where a tie is broken arbitrarily. 4: Update σ2n(.) according to (2). 5: end for 6: Update µN (.) according to (2). 7: return x̂∗N = argmaxx∈XµN (x), where a tie is broken arbitrarily.
We note that MVR, similar to other standard GP bandit algorithms, requires optimizing an internal index created based on previous observations (here, σ2n−1(.) and µN (.)). Examples of other typical indices are UCB and EI, which are 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 is considered to dominate the cost of maximizing the index [19].

heading: 4.2 Regret Analysis
text: 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 4 For each given n ∈ N and f ∈ Hk with ‖f‖Hk ≤ B, there exists a discretization Dn of X such that f(x)− f([x]n) ≤ 1√n , where [x]n = argminx′∈Dn ||x
′ − x||l2 is the closest point in Dn to x, and |Dn| ≤ CBdnd/2, where C is a constant independent of n and B.
Assumption 4 is a 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 2 or 3.
Theorem 3 Consider the GP bandit problem, with a fixed N . Under Assumptions 1, 4, and (2 or 3), for δ ∈ (0, 1), with probability at least 1− δ, MVR satisfies
rMVRN ≤ √
2γN
log(1 + 1λ2 )N
2B + β(δ 3 ) + β ( δ 3C ( B + √ Nβ(2δ/3N) )d Nd/2 )+ 2√ N ,
where under Assumption 2, β(δ) = Rλ √ 2 log(1δ ), and under Assumption 3, β(δ) =
1 λ √ 2 ( ξ0 ∨ 2 log( 1δ )
h20
) log( 1δ ), and B, R, h0, ξ0 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 2 Under Assumptions 2 and 3, respectively, the regret bounds can be simplified as rMVRN = O( √ γN log(Nd/δ)
N ), and rMVRN = O (√ γN N log(Nd/δ) ) .
For instance, in the case of Matérn-ν kernel, under Assumption 2 and 3, respectively, rMVRN = O ( N −ν 2ν+d (log(N)) ν 2ν+d √ log(Nd/δ) ) , and rMVRN = O ( N −ν 2ν+d (log(N)) ν 2ν+d log(Nd/δ) ) ,
which always converge to zero as N grows.
Remark 3 In the analysis of Theorem 3, we apply Assumption 4 to µN as well as f . For this purpose, we derive a high probability B + √ Nβ(2δ/3N) upper bound on ‖µN‖Hk (see Lemma 4 in Appendix D), which appears in the regret bound expression.
Remark 4 Theorem 3 holds for a fixed N . The result however easily extends to an anytime regret bound, using a standard probability union bound over N . Specifically, if we replace δ in the bound with δ0 = 6δπ2N2 , the theorem holds, with probability 1−δ, for allN ∈ N. Note that ∑∞ N=1 6δ π2N2 = δ.

heading: 4.3 Optimal Order Simple Regret with SE and Matérn Kernels
text: To enable a direct comparison with the lower bounds on 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 we formalize the number of exploration trials required to achieve an average regret.
Corollary 1 Consider the GP bandit problem with an SE or a Matérn kernel. For ∈ (0, 1), define N = min{N ∈ N : E[rMVRn ] ≤ ,∀n ≥ N}. Under Assumptions 1, 4, and (2 or 3), upper bounds on N are reported in Table 1.
A proof is provided in Appendix E. [28, 29] showed that for the SE kernel, an average simple regret of requires N = Ω ( 1 2 (log( 1 )) d 2 ) . For the Matérn-ν kernel they gave the analogous bound of
N = Ω ( ( 1 ) 2+ dν ) . 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 in all cases up to log(1/ ) factors.

heading: 4.4 Comparing the Regret Bounds with Other Related Work
text: There are several Bayesian optimization algorithms namely GP-UCB [19], IGP-UCB, GP-TS [20], TruVar [70], GP-EI [50, 49] and KernelUCB [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( γN√
N ).
That does not necessarily converge to zero, since γN can grow faster than √ N , resulting in trivial regret bounds. For example, in the case of a Matérn-ν kernel, inserting γN = Õ(N d
2ν+d ) [22] gives an Õ(N d−2ν 4ν+2d ) regret, which does not converge to zero for d > 2ν, meaning the algorithm does not necessarily approach f(x∗).
More recently, [21] developed a GP-UCB based algorithm, specific to Matérn family of kernels, that constructs a cover for the search space, as many hypercubes, and fits an independent GP to each cover element. This algorithm, referred to as π-GP-UCB, was proven to achieve diminishing regret for all ν > 1 and d ≥ 1. In particular, [21, Theorem 3] provided an upper bound on the regret of π-GP-UCB, which in our notation implies rπ-GP-UCBN = Õ(N −2ν−d 4ν+d(2d+4) ). In contrast, our bound for the case of Matérn kernel rMVRN = Õ(N −ν
2ν+d ) is uniformly tighter that the bound on rπ-GP-UCBN , for all ν > 1 and d ≥ 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 LP-GP-UCB matches the lower bound for some configuration of parameters ν and d in the case of a Matérn kernel. Defining I0 = (0, 1], I1 = (1, d(d+1) 2 ], I2 = ( d(d+1) 2 , d2+5d+12 4 ] and I3 = (0,∞) \ I0 ∪ I1 ∪ I2, their bounds on simple regret are as follows. For ν ∈ I0 ∪ I1, rLP-GP-UCBN = Õ(N −ν
2ν+d ). For ν ∈ I2, rLP-GP-UCBN = Õ(N −1 2+d ). For ν ∈ I3, rLP-GP-UCBN = Õ(N −4ν+d(d+1) 8ν+2d(d+5) ) [see, 72, Sec. 3.2, for a detailed discussion on bounds on the simple regret of LP-GP-UCB]. In comparison, our bounds on simple regret match the Ω(N −ν 2ν+d ) lower bound [28], up to logarithmic factors, with all parameters ν and d. In addition, LP-GP-UCB is impractical due to large constant factors, though a practical heuristic was also given.
Of important theoretical value, SupKernelUCB [71], which builds on episodic independent batches of observations, was proven to achieve Õ( √ γN N ) regret on a finite set (|X | <∞). SupKernelUCB is reported to perform poorly in practice [21, 47, 29]. While the proof of the regret bound for SupKernelUCB is given on a 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 leads to rSupKernelUCBN = O(log 2(N) √ γN N ), under similar assumptions as ours. In comparison, our bound on rMVRN is tighter with a factor of (log(N)) 3 2 .
It 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 xn are independent of the noise terms n (although xn are allowed to depend on {xj}j<n, and x̂∗N is allowed to depend on {xn, n}n≤N ), while in GP-UCB xn are allowed to depend on { j}j<n (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] is an artifact of its proof. For more details on this open question, see [73].

heading: 5 Experiments
text: In this section, we provide numerical experiments on the simple regret performance of MVR, Improved GP-UCB (IGP-UCB) as presented in [20], and GP-PI and GP-EI as presented in [26].
We follow the experiment set up in [20] to 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 is used as the test function f . Parameter λ2 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.5 kernel with l = 0.2. We use 2 different models for the noise: a zero mean Gaussian with variance equal to λ2 (a sub-Gaussian distribution) and a zero mean Laplace with scale parameter equal to λ (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 F. Further details on the experiments are provided in the supplementary material.

heading: 6 Discussion
text: 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 Õ( √ γN/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, 29], we showed the order optimality of our results up to 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 our work adhering to simple regret is that neither our theoretical nor experimental results proves that MVR is necessarily the right algorithm in practice. Overall, exploration-exploitation oriented algorithms such as GP-UCB may perform worse than MVR in terms of simple regret due to two reasons. One is over-exploitation of local maxima when f is multimodal, and the other is dependence on an exploration-exploitation balancing hyper-parameter that is often set too conservatively, to guarantee low regret bounds. Furthermore, their existing analytical regret bounds are suboptimal and possibly trivial (non-diminishing; when γN grows faster than √ N , as discussed). On the other
hand, when compared in terms of cumulative regret ( ∑N n=1 f(x
∗)− f(xn)), MVR suffers from a linear regret.
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 a fundamental limitation or an artifact of the proof [73].
Funding Disclosure
This work was funded by MediaTek Research.

Review summaries:
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?

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.  Note 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: - 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)  - 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.  With 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.  Compared to other simple regret minimization approaches, this shaves a $\sqrt{\gamma_N}$ factor off, taking it closer to its min-max lower bound.   Experimentally, 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. 

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.   Removing 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.   The 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.

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.