1

Lower Bounds on Regret for Noisy
Gaussian Process Bandit Optimization
Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher

arXiv:1706.00090v2 [stat.ML] 16 Jun 2017

Laboratory for Information and Inference Systems (LIONS), EPFL
{jonathan.scarlett, ilija.bogunovic, volkan.cevher}@epfl.ch

Abstract
In this paper, we consider the problem of sequentially optimizing a black-box function f based on
noisy samples and bandit feedback. We assume that f is smooth in the sense of having a bounded norm
in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian
form of Gaussian process bandit optimization. We provide algorithm-independent lower bounds on
the simple regret, measuring the suboptimality of a single point reported after T rounds, and on the
cumulative regret, measuring the sum of regrets over the T chosen points.
For the isotropic squared-exponential kernel in d dimensions, we find that an average simple regret
p


of  requires T = Ω 12 (log 1 )d/2 , and the average cumulative regret is at least Ω T (log T )d ,
thus matching existing upper bounds up to the replacement of d/2 by d + O(1) in both cases. For the

ν+d 
Matérn-ν kernel, we give analogous bounds of the form Ω ( 1 )2+d/ν and Ω T 2ν+d , and discuss
the resulting gaps to the existing upper bounds.

I. I NTRODUCTION
The problem of sequentially optimizing a black-box function based on noisy bandit feedback has
recently attracted a great deal of attention, and finds applications in robotics, environmental monitoring,
and hyperparameter optimization in machine learning, just to name a few. In order to make this problem
tractable, one must place smoothness assumptions on the function. Gaussian processes (GPs) provide
a versatile means for doing this, capturing the smoothness properties through a suitably-chosen kernel.
Within the GP framework, there are two distinct viewpoints: Bayesian and non-Bayesian. In the
Bayesian viewpoint, one assumes that the underlying function is random according to a GP distribution
with the specified kernel. On the other hand, in the non-Bayesian viewpoint, one treats the function
as fixed and unknown, and only assumes that it is has a low norm in the reproducing kernel Hilbert
space (RKHS) corresponding to the kernel.
Upper bounds on the regret, a widely-adopted performance measure (see Section I-A), have been
given for a variety of practical GP bandit optimization1 algorithms, including upper confidence bound
(GP-UCB) [21] and various alternatives [4; 19; 22]. However, to our knowledge, there are no existing
1
We use the terminology Gaussian process bandit optimization to refer collectively to the Bayesian and non-Bayesian
settings, whereas the former is typically referred to as Bayesian optimization.

2

algorithm-independent lower bounds on the regret in the noisy setting, thus making it unclear to what
extent the upper bounds can be improved.
In this paper, we provide such lower bounds in the non-Bayesian setting, focusing on two specific
widely-used kernels: squared exponential (SE) and Mátern. For the SE kernel, our lower bound nearly
matches existing upper bounds, whereas the gap is seen to be more significant in the case of the
Mátern kernel. As a result, the latter deserves further study both in terms of the lower bounds and
the existing algorithms; see Section II for further discussion.
A. Setup
We consider the optimization of a function f defined on a compact domain D = [0, 1]d . The
smoothness is dictated by a kernel function k(x, x0 ) [18]; specifically, we assume that the corresponding
RKHS norm is bounded as kf kk ≤ B . The set of all such functions is denoted by Fk (B), and for
a given f ∈ Fk (B), we let x∗ denote an arbitrary maximizer of f . In the t-th round, a point xt is
selected, and a noisy sample yt = f (xt ) + zt is observed, with zt ∼ N (0, σ 2 ) for some σ 2 > 0. We
assume independence among the noise terms at differing time instants.
We consider two widely considered performance metrics:
•

•

Simple regret: At the end of T rounds, an additional point x(T ) is reported, and the simple
regret incurred is r(T ) = f (x∗ ) − f (x(T ) ). We seek to characterize how large T must be to
permit E[r(T ) ] ≤ .
P
Cumulative regret: At the end of T rounds, the cumulative regret incurred is RT = Tt=1 rt ,
where rt = f (x∗ ) − f (xt ). We seek to provide lower bounds on E[RT ].

We focus on two commonly-considered kernels, namely, squared exponential (SE) and Matérn [18]:


kx − x0 k2
0
(1)
kSE (x, x ) = exp −
2l2
√
√

 

21−ν
2νkx − x0 k ν
2νkx − x0 k
0
Jν
,
(2)
kMatérn (x, x ) =
Γ(ν)
l
l
where l > 0 denotes the length-scale, ν > 0 is an additional parameter that dictates the smoothness,
and Jν denotes the modified Bessel function. Although we only consider these specific kernels, the
approach that we take can also potentially be applied to other stationary kernels.
B. Related Work
A recent review of Gaussian process bandit optimization is given in [20]. Upper bounds on the
regret for specific algorithms are given for the Bayesian and non-Bayesian settings with cumulative
regret in [19; 21; 23], and with simple regret in [4; 8]. Of these, [23] is the only one that did not
assume perfect knowledge of the kernel, but this distinction will not be important for our purposes,
since our lower bounds hold in either case. Bounded RKHS norm assumptions have also been used
in other problems, such as uniform function approximation [16; 17].
We are not aware of any existing lower bounds for the noisy setting. However, [7] is related to
our work, providing tight lower bounds on the simple regret for the Mátern kernel in the noiseless

3

setting. While our high-level approach is similar to [7] in the sense of considering a class of needlein-haystack type functions that are difficult to distinguish, there are a number of additional challenges
that we need to address:
1) Incorporating noise is non-trivial, and it is unclear a priori the extent to which it affects the
regret bounds. For instance, in the Bayesian setting, O(1) cumulative regret is possible for
noiseless observations [10; 12], whereas the best known bounds for the noisy case are between
√
O( T ) and o(T ) [21].
2) We consider not only the simple regret, but also the cumulative regret, which is not captured
by the framework of [7].
3) While [7, Thm. 1] gives a tight lower bound for the Mátern kernel, no analogous result is given
for the widely-adopted SE kernel. Moreover, an inspection of the analysis in [7] reveals that
the compactly supported functions used therein have an infinite RKHS norm for the SE kernel,
and thus cannot be used. To circumvent this issue, we consider a different class of functions
that are compactly supported in frequency domain, and hence have unbounded support in the
spatial domain Rd . This introduces additional challenges into the analysis, since we can no
longer directly state that most samples are uninformative as a result of the sampled function
value being exactly zero.
Another related work on the noiseless setting is [11], which provided upper and lower bounds for the
Bayesian case under a Hölder-continuity assumption on the kernel.
While multi-armed bandit problems [2; 3; 5] typically consist of finite action spaces, some
continuous variants have been proposed [13; 14]. However, these make significantly different
smoothness assumptions of the Lipschitz variety, and as a result, the results and analysis techniques
do not apply to our setting of bounded RKHS norm. In particular, Lipschitz properties do not imply
bounds on the RKHS norm, nor vice versa.
II. M AIN R ESULTS
In all of our results, we assume that the dimension d in the definition of D = [0, 1]d , as well as the
parameters l and ν in the kernels in (1)–(2), behave as Θ(1). In contrast, we allow the RKHS norm
upper bound B and the noise level σ to scale generally. We let O∗ (·) denote asymptotic expressions
√
√
up to dimension-independent logarithmic factors, e.g., 4 T (log T )d+3 = O∗ ( T (log T )d ).
Our main results are expressed in terms of the average regret. However, it is straightforward to
modify the proofs in order to show that the scaling laws are the same when considering regret bounds
that hold with constant (but arbitrarily close to one) probability. See Section V-D for details.
We first provide our main result for the simple regret.

Theorem 1. (Simple Regret) Fix  ∈ 0, 12 , B > 0, and T ∈ Z. Suppose there exists an algorithm
that, for any f ∈ Fk (B), achieves an average simple regret E[r(T ) ] ≤  after T rounds. Then, provided
that B is sufficiently small, we have the following:

4

1) For k = kSE , it is necessary that
 2

σ
B d/2
T = Ω 2 log
.



(3)

2) For k = kMatérn , it is necessary that
 2  
σ B d/ν
T =Ω 2
.



(4)

Our main result for the cumulative regret is as follows.
Theorem 2. (Cumulative Regret) Fix B > 0 and T ∈ Z. Suppose there exists an algorithm that, for
any f ∈ Fk (B), achieves an average cumulative regret of E[RT ] after T rounds. Then, we have the
following:
1) For k = kSE , it is necessary that
r
E[RT ] = Ω

T σ2



B 2 T d
log 2
σ

!

√ 
σ
provided that B
= O T with a sufficiently small implied constant.
2) For k = kMatérn , it is necessary that


ν+d
d
2ν
2ν+d
2ν+d
2ν+d
E[RT ] = Ω B
σ
T

(5)

(6)

√ 
T with a sufficiently small implied constant.
√ 
σ
= O T is assumed for technical reasons, and is quite mild. In
We note that the condition B
particular, below we will focus primarily on the case that σ and B are constants that do not scale
with T , in which case this condition is trivially satisfied.
Comparisons to Upper Bounds: The best known upper bounds on the cumulative regret were
given for the upper confidence bound (GP-UCB) algorithm [21], where bounded noise was assumed.
While Gaussian noise has unbounded support, it is bounded by O(log T ) for all t = 1, . . . , T with
high probability, and hence the bounded noise results transfer to the Gaussian setting at the expense
of additional dimension-independent logarithmic factors.
A summary of the comparisons is shown in Table I, and we proceed by discussing the entries in
more detail. We first compare our Theorem 2 (cumulative regret) to [21] in the case that σ 2 and B
behave as Θ(1); we will later discuss the dependence on these parameters. For fixed σ 2 , the upper
bound in [21] is of the form
q

T BγT + T γT2 ,
(7)
RT = O∗

provided that

σ
B

=O

where, letting I(X; Y ) denote the mutual information [9], we define
γT = max

max I(f ; yS ),

x1 ,...,xT S : |S|=T

f ∼ GP(0, k).

(8)

This represents the maximum amount of information that a set of T noisy observations yS =

5

Upper bound
([21])
SE kernel
Cumulative regret
Matérn kernel
Cumulative regret
SE kernel
Time to simple regret 
Matérn kernel
Time to simple regret 


T (log T )2d


1 2ν+3d(d+1)
· 2ν+d(d+1)
∗
2
O T
 
d 
1
1
∗
O 2 log 
  2(2ν+d(d+1)) 
2ν−d(d+1)
1
∗
O

O∗

p

(if 2ν − d(d + 1) > 0)

Conjectured upper
bound
(see Section II)

Lower bound
(Theorems 1–2)


T (log T )d


ν+d(d+1)
∗
2ν+d(d+1)
O T
 
d/2 
1
1
∗
O 2 log 


T (log T )d


ν+d
2ν+d
Ω T
 
d/2 
1
1
Ω 2 log 

O∗

O∗

p

 

2+d(d+1)/ν
1


Ω

p

Ω

 

2+d/ν
1


Table I: Summary of regret bounds for a fixed RKHS norm bound B > 0 and noise level σ 2 > 0.
(y1 , . . . , yT ) (corresponding to xS = (x1 , . . . , xT )) can reveal about a zero-mean Gaussian process

f with kernel k . We have γT = O (log T )d+1 for the squared-exponential kernel, and γT =
d(d+1)

O∗ T 2ν+d(d+1) for the Matérn kernel [21].
p

Hence, for kSE , the upper bound in (7) is O∗
T (log T )2d and the lower bound in (3) is
p

Ω T (log T )d , so the two coincide up to the factor of two in the exponent, as well as the (few)
extra log T factors hidden in the O∗ (·) notation.
While [21] focused on the cumulative regret, one can obtain simple regret bounds by noting that it
it always possible to have a simple regret no higher than the normalized cumulative regret [6]; this
yields the condition BγTT+γ 2 ≥ C2 for -optimality, where C = O∗ (1) (see also [4; 8]). By substituting
T
d
0
γT and rearranging, we find that for the SE kernel this condition is of the form T ≥ C2 log 1 for
some C 0 = O∗ (1), again matching (3) up to the factor of two in the exponent.
d(d+1)

For the Matérn kernel, the gaps are more significant. In particular, substituting γT = O∗ T 2ν+d(d+1) ,
d(d+1)
< 21 . A similar
we find that the cumulative regret upper bound in (7) is only sublinear when 2ν+d(d+1)
statement holds for having a non-void condition on the simple regret. This suggests that these existing
upper bounds may be loose, since, at least in the authors’ judgment, sublinear regret should be possible
for all ν and d. This poses an interesting open problem for future work.

√
In contrast, if the right-hand side of (7) could be improved to O∗ T BγT , then the upper bound
would be sublinear for all d and ν . We conjecture that such a bound holds (as is the case in the
Bayesian setting [21]), but we do not currently have a proof. We proceed by discussing the bounds
that would arise if this conjecture were true, as summarized in the middle column of Table I.
For the squared exponential kernel, the conjecture would in fact close the above-mentioned gap on
the factor of 2 in the exponent to log T . For the Matérn kernel, we would obtain a cumulative regret
ν+d(d+1) 
of O∗ T 2ν+d(d+1) , hence matching our lower bound up to the replacement of d by d(d + 1). Thus,
both bounds would be of the same form, and behave as T c for some c that tends to one as d grows
large. Analogous observations hold for the simple regret, as summarized in Table I.
Finally, we discuss the dependence of the bounds on B and σ , focusing on the squared exponential

6

kernel with cumulative regret for brevity. Up to the logarithmic term, our boundq(5) depends linearly

1
on σ . In contrast, the upper bound in [21] contains a multiplicative term O
−2
log(1+σ ) , which
reduces to O(σ) when σ is large, but tends to zero much more slowly when σ is small. However, it is
shown in [4] that a linear dependence is attainable for the simple regret, and one should expect that
such a dependence is similarly attainable for the cumulative regret. As for the dependence on B , the
optimal scaling is unclear. For fixed T , d, and σ 2 , our lower bound has dependence (log B)d , whereas
√
the upper bound of in (7) has dependence B , which is stronger due to our assumption d = O(1).
The remainder of the paper is devoted to the proofs of Theorems 1 and 2.
III. C ONSTRUCTION OF A F INITE E NSEMBLE OF F UNCTIONS
We obtain lower bounds on the regret by considering the case that f is uniform on a finite set
= {f1 , · · · , fM }. If we can lower bound the regret (of an arbitrary algorithm) averaged over
m ∈ {1, . . . , M }, then it follows that there must exist a particular value of m such that the same
lower bound applies to fm .
More specifically, we let F 0 have the property that any single point x can only be -optimal for
at most one function in this set. By this property, the optimization problem with simple regret not
exceeding  is equivalent to the correct identification of the index m ∈ {1, · · · , M }.
Note that for the simple regret, the parameter  is part of the problem statement, whereas for
cumulative regret it is a parameter that we can choose to our liking. The starting point of the analysis
is the same for both regret notions, and throughout, we assume that B is sufficiently small. This is
true by assumption in Theorem 1, whereas when we prove Theorem 2, we will need to check that
our choice of  is consistent with this assumption.
F0

A. Function Class
The class that we consider corresponds to a “needle in haystack” problem, and is described as
follows: Let g(x) be a function on Rd with values in [−2, 2], an RKHS norm not exceeding B , a
peak value of 2 at x = 0, and a value strictly less than  when kxk∞ ≥ w, for some width w > 0 to
be chosen later. We let each fm (x) be given by g(x) shifted so that its peak is at a given point, and
then cropped to the domain [0, 1]d . By forming a d-dimensional grid of step size w in each dimension,
we can form
 d 
1
(9)
M=
w
of these while ensuring that any -optimal point for fm fails to be -optimal for any of the other fm0 .
See Figure 1 for an illustration.
It remains to choose g , and to determine small we can allow w to be without violating the RKHS
norm constraint. Intuitively, a smaller w gives a “less smooth” function and hence a higher RKHS
norm, but a smaller amplitude 2 also decreases the RKHS norm in a linear fashion. Hence, as  → 0,
we can afford to take w → 0.

7

2✏

f1

f2

f3

f4

f5

✏

0
w
Figure 1: Illustration of functions f1 , . . . , f5 such that any given point x ∈ [0, 1] can only be -optimal
for one function. See (10)–(11) for the specific function being plotted.

Instead of specifying g directly, we specify the Fourier transform H of another function h, and
then let g be a suitably scaled version of h. Specifically, H is defined to be the multi-dimensional
bump function:




exp − 1 2
kξk22 ≤ 1
1−kξk
H(ξ) =
(10)

2
0
kξk2 > 1,
which is compactly supported and infinitely differentiable. Let h(x) be the inverse Fourier transform
of H . Since H is a fixed function with finite energy, the amplitude of h(x) must vanish as kxk grows
large; hence, there exists a constant ζ such that h(x) < 21 h(0) for kxk∞ > ζ .
We choose
2  xζ 
h
,
(11)
g(x) =
h(0)
w
where the parameter w is the same as that in (9). Note that since H is real and symmetric, the
maximum of h occurs at zero, and thus the maximum of g is g(0) = 2, as desired. We consider w
as arbitrary for now, but this will be chosen to ensure that the RKHS norm of g is upper bounded
by B ; see Section IV. To get an idea of how g behaves, we note that it is precisely the function that
was used in producing Figure 1 (with d = 1).
IV. B OUNDING THE RKHS N ORM
Intuitively, in our function class in Section III-A, we would like M to be as large as possible, since
this means that there are more functions that need to be distinguished, and a higher lower bound can
be obtained. In this section, we determine how large M can be in our construction while still ensuring
that our assumptions are valid, namely, the RKHS norm of each function is upper bounded by B , and
any given point can only be -optimal for at most one function.

8

A. Properties of RKHS Norms
The following properties of RKHS norms are well-known; see for example [1, Sec. 1.5] and [7,
Sec. 3]. The first property explicitly expresses the RKHS norm on Rd in terms of the Fourier transform.
Lemma 1. [1, Sec. 1.5] Consider an RKHS H for functions on Rd , corresponding to a kernel of the
form k(x, x0 ) = k(τ ) with τ = x − x0 , and let K(ξ) be the d-dimensional Fourier transform of k(τ ).
Then for any f˜ ∈ H with Fourier transform F̃ (ξ), we have
Z
|F̃ (ξ)|2
2
˜
kf kH =
dξ.
(12)
K(ξ)
The next result relates the RKHS norm on Rd to that on a compact subset D ⊆ Rd , and reveals
that the cropping operation described at the start of Section III-A cannot increase the RKHS norm.
Lemma 2. [1, Sec. 1.5] Consider two RKHS H(D) and H(Rd ) for functions on a compact set D ⊆ Rd
and Rd respectively, corresponding to a kernel of the form k(x, x0 ) = k(τ ) with τ = x − x0 . Then for
any f˜ ∈ H(D), we have
kf˜kH(D) = inf kg̃kH(Rd ) ,
(13)
g̃

where the infimum is over all functions g̃ ∈ H(Rd ) that agree with f˜ when restricted to D.
B. Squared Exponential Kernel
We first consider the isotropic squared exponential kernel with lengthscale l, defined in (1). Writing
k(x, x0 ) = k(τ ) with τ = x − x0 , the Fourier transform is given by [18, Sec. 4.2]
K(ξ) = (2πl2 )d/2 e−2π

2 2

l kξk22

.

(14)

2
and w0 = wζ (cf., (11)) for brevity, the RKHS norm
Using Lemma 1 and (14), and denoting a0 = h(0)
of g in Rd is given by
Z
1
2 2
2
kgk2k =
|G(ξ)|2 e2π l kξk2 dξ
(15)
(2πl2 )d/2


Z
a20 w02d
2
2 2
2
exp 2π l kξk2 −
dξ
(16)
=
1 − kw0 ξk2
(2πl2 )d/2 kw0 ξk2 ≤1
Z

a20 w02d
≤
exp 2π 2 l2 kξk22 dξ
(17)
d/2
2
(2πl )
kξk2 ≤ w1
0
 2π 2 l2 
a20 w02d
−1
V
(w
)
exp
(18)
≤
0
w02
(2πl2 )d/2
 2π 2 l2 
a20
≤
exp
,
(19)
w02
(2πl2 )d/2

where:
•

(16) follows from (10)–(11) and the fact that the d-dimensional Fourier transform of ah(x/b) is
abd H(xb);

9

•

(18) follows by upper bounding kξk22 ≤ w12 according to the constraint, and defining V (w0−1 ) to
0
be the volume of a ball of radius w0−1 in d dimensions:
V (w0−1 ) =

•

π d/2
(w0−1 )d ,
Γ( d2 − 1)

(20)

where Γ(·) denotes the gamma function;
(19) holds when w0 is chosen such that w02d V (w0−1 ) ≤ 1, as will be done shortly.

Equating (19) with B 2 (so that kgkk ≤ B ), and recalling the definition a0 =
 π 2 l2 
B(2πl2 )d/4 exp − 2 h(0) = 2
w0
πl
=⇒ w0 = q
.
2 )d/4 h(0)
log B(2πl 2

2
h(0) ,

we find that
(21)
(22)

From this choice, we see that w0 → 0 as B → 0. Hence, and since w02d V (w0−1 ) = O(w0d ), we find
that the above assumption w02d V (w0−1 ) ≤ 1 is indeed true as long as B is sufficiently small. The latter
is assumed in Theorem 1, and will be ensured when we choose  to prove Theorem 2.
Recalling that h(x) < 12 h(0) for kxk∞ > ζ , we have from (11) that g(x) < 21 g(0) =  for
kxk∞ > ζw0 = w, as was assumed in the construction of the functions in Section III-A. Hence, from
ζπl
in (9), yielding
(22), we can choose w = ζw0 = q B(2πl
2 )d/4 h(0)
log

2

$ q
M=

2 d/4

)
log B(2πl 2

ζπl

h(0) !d %

.

(23)

In summary, we have shown that with this choice of M , we can construct M functions whose RKHS
norm is upper bounded by B , whose peak values are 2, and such that any -optimal point for one
function cannot be -optimal for any of the other M − 1 functions.
C. Matérn Kernel
We now consider the Matérn kernel with parameters l and ν , defined in (2). The Fourier transform
of k (treated as a function of τ = x − x0 ) is [18, Sec. 4.2]

−(ν+d/2)
2ν
2
2
K(ξ) = c1 2 + 4π kξk2
,
(24)
l
d

d/2

ν

where c1 = 2 π Γ(ν+d/2)(2ν)
is a constant (recall that d, l, and ν are assumed to be fixed). Hence,
Γ(ν)l2ν
2
using Lemma 1 and again denoting a0 = h(0)
and w0 = wζ (cf., (11)), we have the following,
analogously to (15):

(ν+d/2)
Z
−1
2
2
2
2 2ν
kgkk = c1
|G(ξ)|
+ 4π kξk2
dξ
(25)
l2


(ν+d/2)
Z
2
2ν
2
2
2 2d
= c−1
a
w
exp
−
+
4π
kξk
dξ
(26)
0 0
1
l2
1 − kw0 ξk22
kw0 ξk2 ≤1

10

(ν+d/2)
2ν
2
2
≤
+ 4π kξk2
dξ
l2
kξk2 ≤ w1
0


4π 2 (ν+d/2)
2ν
−1 2 2d
−1
≤ c1 a0 w0 V (w0 ) 2 + 2
l
w0
(ν+d/2)

2νw02
−1 2 d−2ν
−1
2
= c1 a0 w0
+ 4π
V (w0 )
l2
(ν+d/2)

2νw02
2
+
4π
≤ c2 a20 w0−2ν
l2
(ν+d/2)
≤ c2 a20 w0−2ν 8π 2
,
2 2d
c−1
1 a 0 w0



Z

(27)
(28)
(29)
(30)
(31)

where:
•

•
•

•
•

(26) follows from (10)–(11) and the fact that the d-dimensional Fourier transform of ah(x/b) is
abd H(xb);
(27) follows by upper bounding the exponential term by one;
(28) follows by upper bounding kξk22 ≤ w12 according to the constraint, and using the definition
0
of the volume in (20);
(30) holds for some c2 > 0 since V (w0−1 ) = O(w0−d ) by (20);
2
2
0
(31) holds when w0 is chosen such that 2νw
l2 ≤ 4π , as will be done shortly.

Equating (31) with B 2 (thus ensuring kgkk ≤ B ), and recalling that a0 =
−1/2

Bc2

8π 2

2
h(0) ,

we obtain

h(0)w0ν

(ν+d/2)/2 = 2.

(32)

We again observe that in the limit as B → 0 we have w0 → 0; hence, to satisfy the above condition
2νw02

2
l2 ≤ 4π , it suffices that B is sufficiently small.
Rearranging (32), we obtain
!1/ν
(8π 2 )(ν+d/2)/2
w0 = 2
.
(33)
−1/2
Bc2 h(0)
Recalling that w = ζw0 in (9) and (11), we find that (33) gives the following analog of (23):
j Bc d/ν k
3
,
M=

where
c3 :=

 1 ν
ζ

·

!
−1/2
c2 h(0)
.
2(8π 2 )(ν+d/2)/2

(34)

(35)

V. B OUNDING THE R EGRET
In this section, we combine the tools from Sections III and IV to deduce the regret bounds given
in Theorems 1 and 2. Throughout the section, we use the fact that for P1 and P2 representing the

11

density functions of Gaussian random variables with means (µ1 , µ2 ) and variance σ 2 , we have
D(P1 kP2 ) =

Here, D(P1 kP2 ) =
functions [9].

R
R

(µ1 − µ2 )2
.
2σ 2

(36)

P1 (z) log PP12 (z)
(z) dz denotes the Kullback-Leibler divergence between two density

A. Auxiliary Lemmas and Definitions
Fix an arbitrary (e.g, optimal) bandit optimization algorithm. Let y = (y1 , . . . , yT ) be the
observations up to time T , and for m = 1, . . . , M , let Pm (y) be the probability density function
of y upon running the algorithm on a given function fm indexed by m. Moreover, let P0 (y) be the
probability density of y when the algorithm is run with f being zero everywhere. Let Em and Pm
denote expectations and probabilities when the underlying function is f = fm , and similarly for E0
1 PM
and P0 . Finally, let E[·] = M
m=1 Em [·] be the expectation averaged over a uniformly random
function index, and similarly for P[·].
The following lemma from [3] relates two expectations Em and E0 in terms of the corresponding
divergence D(P0 kPm ).
Lemma 3. [3, p. 27] For any function a(y) taking values in a bounded range [0, A], we have
p
(37)
Em [a(y)] ≤ E0 [a(y)] + A D(P0 kPm ).
To make the paper self-contained, the proof is given in the appendix.
Before proceeding, we introduce some additional notation:
•

•

•

•

•

Let {Rm }M
m=1 be the partition of the domain into M regions according to (9), i.e., done according
to a uniform grid with fm taking the maximum in the centre of Rm ;
Let jt be the index at time t such that xt falls into Rjt – this can be thought of as a quantization
of xt ;
P
Let Nj = Tt=1 1{jt = j} denote the number of points from Rj that are selected throughout
the T rounds;
Let Pm (yt |yt−1 ) denote the distribution of yt given all the observations up to time t − 1, denoted
by yt−1 = (y1 , . . . , yt−1 ) (and y0 = ∅), in the case that f = fm ;
Define the maximum function value within a single region Rj as
v jm := max fm (x),
x∈Rj

(38)

and the maximum divergence within the region as
j

Dm := max D(P0 (·|x)kPm (·|x)),
x∈Rj

(39)

where Pm (y|x) is the distribution of an observation y for a given selected point x under the
function fm , and similarly for P0 (y|x).

12

The following lemma provides a simple upper bound on the divergence in (37).
Lemma 4. Under the preceding definitions, we have
D(P0 kPm ) ≤

M
X

j

E0 [Nj ]Dm

(40)

j=1

Proof. We use the chain rule for divergence [9, Sec. 2.5] to write
D(P0 kPm ) =
≤

T
X

h
i
E0 D P0 (·|yt−1 )kPm (·|yt−1 )

t=1
T X
M
X

j

P0 [jt = j]Dm

(41)

(42)

t=1 j=1

=

M X
T
X
j=1

=

M
X


j
P0 [jt = j] Dm

(43)

t=1
j

E0 [Nj ]Dm ,

(44)

j=1

where (42) follows by noting that the argument to the expectation in (41) depends on yt−1 only
through the resulting selected point xt , which is chosen based on yt−1 . When xt falls into Rj (i.e.,
j
jt = j ), the divergence is upper bounded by Dm due to (39).
Finally, the following technical lemma will also be key to the analysis. It roughly states that if we
sum the function values fm (x) over x lying on the grid defined by {Rj }, then the total is dominated
by the largest value, i.e., it behaves as O().
Lemma 5. The functions {fm } constructed in Section III-A are such that v jm satisfy the following:
PM j
1)
v m = O() for all m;
Pj=1
j
M
2)
m=1 v m = O() for all j ;
PM
j 2
2
3)
m=1 (v m ) = O( ) for all j .
Proof. The three claims in the lemma statement are proved in a nearly identical manner, so we focus

x
on the first. Recall from (9) that each fm is a shifted version of g(x) = a0 h ζw
, where the shifts
among the m values differ by integer multiples of w in one or more of the d dimensions. That is, the
amount by which g is shifted to produce fm is given by wim for some im = (im,1 , . . . , im,d ) ∈ Zd ,
and the vectors im and im0 differ in at least one coordinate when m 6= m0 .
In the following, we let 1 denote the vector of ones, and we write i  i0 for element-wise inequalities.

13

Recalling the definitions of Rj and v jm following Lemma 3, we have
M
X

v jm

=

M
X
j=1

j=1

≤

X
i∈

=

max fm (x)

(45)

x∈Rj

Zm

max

iwx(i+1)w

g(x)

2 X
max
h(ζx0 ),
0 i+1
ix
h(0)
m

(46)
(47)

i∈Z

where (46) follows by expanding the sum over i ∈ {im : m = 1, . . . , M } to all i ∈ Zd and recalling
that each fm is a shifted version of g , and (47) follows by substituting (11) and applying the change
of variable x0 = wx .
2
Since h(0)
= O(), it only remains to show that the summation in (47) is O(1). To do this, we note
that since the bump function H(ξ) in (10) is infinitely differentiable, its inverse Fourier transform
1
h(x) decays to zero as kxk2 → ∞, at a rate faster than any finite power of kxk
[15]. The 2d-th
2
C1
0
power suffices for our purposes: There exist constants C1 , C2 such that h(ζx ) ≤ ζ 2 kx
0 k2d whenever
2
0
2
kx k2 ≥ C2 . Hence, we bound the sum in (47) by considering two separate cases:
If the vector i is such that kx0 k22 < C2 for some i  x0  (i + 1), we upper bound h(ζx0 ) by
its maximum value h(0). This case can only occur for a finite number of i, and hence the total
contribution from such i is O(1) (recall that we assume d = O(1)).
0
• For the vectors i is such that kx0 k2
2 ≥ C2 for all i  x  (i + 1), we apply the upper bound
C1
1
h(ζx0 ) ≤ ζ 2 kx
0 k2d . The total contribution is again finite, since the sum of kik2d over all i 6= 0
2
2
Q
is finite. For instance, this can be seen by upper bounding kik12d ≤ dl=1 i12 (since kik22 ≥ i2l ),
2
l
P
P∞ 1 d
which implies that i1 kik12d ≤
<
∞
.
2
i=1
i
2
P
j
Combining the above, we conclude that M
j=1 v m = O().
•

B. Completion of the Proof of Theorem 1
Applying Lemma 3: Letting v (T ) = f (x(T ) ) be the reward of the recommended point, we have
Em [v (T ) ] = Em [f (x(T ) )]
≤

M
X

(48)

Pm [x(T ) ∈ Rj ]v jm

(49)

j=1

≤

M
X
j=1

v jm P0 [x(T )

v
!
uM
uX
0
j
E0 [Nj 0 ]Dm
∈ Rj ] + t

(50)

j 0 =1

where (49) follows by the same argument as (42), and (50) follows from Lemma 3 and (40), with the
former setting a(y) = 1{x(T ) ∈ Rj } and using the fact that 1{·} ∈ [0, 1] (note that x(T ) is a function

14

of y). Averaging over m gives the following bound on the average reward:
v
!
uM
M X
M
X
uX
0
1
j
(T )
j
(T )
E[v ] ≤
v m P0 [x ∈ Rj ] + t
E0 [Nj 0 ]Dm .
M
0
m=1 j=1

(51)

j =1

Bounding the two terms in (51): Using the second part of Lemma 5, we can bound the first term
in (51) as follows:

M M
M  M
1 XX j
1 X X j
v m P0 [x(T ) ∈ Rj ] =
v m P0 [x(T ) ∈ Rj ]
(52)
M
M
m=1 j=1
m=1
j=1
 X
M

=O
P0 [x(T ) ∈ Rj ]
(53)
M
j=1
 

,
(54)
=O
M
P
(T ) ∈ R ] = 1.
since M
j
j=1 P0 [x
The second term in (51) is bounded as follows:
v
uM
M X
M
X
uX
1
j0
j t
vm
E0 [Nj 0 ]Dm
M
m=1 j=1
j 0 =1
v
u X
M X
M
X
uM
0
1
1
j
=√
·
vm t
E0 [Nj 0 ](v jm )2
(55)
2 · σ M m=1 j=1
j 0 =1
v
 
M
M u
X
uX
0

1
t
E0 [Nj 0 ](v jm )2
=O
·
(56)
σ
M
m=1
j 0 =1
v
  u
M X
M
u1 X
0

t
≤O
·
E0 [Nj 0 ](v jm )2
(57)
σ
M
m=1 j 0 =1
v
  u
X

M
M
u1 X
0

j
=O
·t
E0 [Nj 0 ]
(v m )2
(58)
σ
M 0
m=1
j =1
v
 2  uX
uM

=O √
·t
E0 [Nj 0 ]
(59)
Mσ
j 0 =1
√ 2
T
=O √
,
(60)
Mσ
2

where (55) follows since the divergence associated with a point x having value v(x) is v(x)
2σ 2 (cf.,
(36)), (56) follows from the first part of Lemma 5, (57) follows from Jensen’s inequality, (59) follows
P
from the third part of Lemma 5, and (60) follows from j 0 Nj 0 = T .

15

Combining and Simplifying: Substituting (54) and (60) into (51) gives
r 

1
T

(T )
E[v ] ≤ C · 
+
M
σ M

(61)

for some constant C . Since the maximum function value is f (x∗ ) = 2 by the construction in Section
III-A, this implies that the simple regret is lower bounded by
r 

1
T

(T )
E[r ] ≥ 2 − C · 
+
(62)
M
σ M
r 

C T
C
−
.
(63)
= 2−
M
σ
M
Noting that M → ∞ as
and hence


B

→ 0 in both (23) and (34), we have for sufficiently small

E[r

(T )

r 

3 C T
]≥
−
.
2
σ
M


B

that

C
M

≤ 12 ,

(64)

By equating the bracketed term with one, it follows that if the time horizon satisfies
T ≤

M σ2
,
4C 2 2

(65)

then the average simple regret at time T is at least .
d/2 
Theorem 1 now follows by substituting M = Θ log B
into (65) for the squared exponential
 
B d/ν
kernel (cf., (23)), and M = Θ 
for the Matérn kernel (cf., (34)).
C. Completion of the Proof of Theorem 2
We initially follow similar steps to those used above for the simple regret, but the later steps become
slightly more involved.
P
Applying Lemma 3: Letting VT = Tt=1 f (xt ) be the total cumulative reward, we have
Em [VT ] =
≤

T
X

Em [f (xt )]
t=1
T X
M
X

(66)

Pm [jt = j]v jm

(67)

t=1 j=1

=

M
X

v jm Em [Nj ]

(68)

j=1

≤

M
X
j=1

v jm

v
!
uM
uX
0
j
E0 [Nj 0 ]Dm ,
E0 [Nj ] + T t

(69)

j 0 =1

where (67) follows by the same argument as (42), and (69) follows from Lemma 3 and (40), with the
former setting a(y) = Nj and using the fact that Nj ∈ [0, T ] (note that {xt }Tt=1 is a function of y).

16

Averaging over m gives the following bound on the average total reward:
v
!
uM
M M
uX
0
1 XX j
j
E[VT ] ≤
v m E0 [Nj ] + T t
E0 [Nj 0 ]Dm .
M
0
m=1 j=1

(70)

j =1

Bounding the two terms in (70): Using the second part of Lemma 5, we can bound the first
in (70) as follows:

M M
M  M
1 XX j
1 X X j
v m E0 [Nj ] =
v m E0 [Nj ]
M
M
m=1 j=1
m=1
j=1
 X
M

=O
E0 [Nj ]
M
j=1
 
T
,
=O
M
P
since M
j=1 Nj = T . Moreover, the second term in (70) was already bounded in (55)–(60):
v
uM
 √ 2
M X
M
X
uX
1
T T
j0
j t
,
T·
vm
E0 [Nj 0 ]Dm = O √
M
Mσ
m=1 j=1
j 0 =1
Combining and simplifying: Substituting (73) and (74) into (70) gives
r 

1

T
0
E[VT ] ≤ C · T 
+
M
σ M

term

(71)

(72)
(73)

(74)

(75)

for some constant C 0 . Since the maximum function value is f (x∗ ) = 2 by the construction in Section
III-A, this implies that the cumulative regret is lower bounded by
r 

T
1

E[RT ] ≥ 2T  − C 0 · T 
+
(76)
M
σ M
r


C0
C 0 T
= T 2 −
−
.
(77)
M
σ
M
Noting that M → ∞ as
and hence


B

→ 0 in both (23) and (34), we have for sufficiently small

r 

3 C 0 T
E[RT ] ≥ T 
−
.
2
σ
M


B

that

C0
M

≤ 12 ,

(78)

By equating the bracketed term with one, it follows that if the time horizon satisfies
T ≤

M σ2
,
4(C 0 )2 2

(79)

then the average cumulative regret at time T is at least T . For convenience, we also note the following
equivalent form of (79):
s
M σ2
≤
,
(80)
4(C 0 )2 T

17

While  represented the target simple regret in Section V-B, for cumulative regret it can be treated
as a parameter that we can set to our liking, subject to the fact that we assumed in the analysis that

B is sufficiently small. Hence, we simply need to choose  to ensure that (79) (or equivalently, (80))
holds, and substitute this value into the lower bound T .
To do this, we choose  such that (80) nearly holds with equality:
s
M σ2
≥
.
(81)
8(C 0 )2 T
Note that the right-hand side depends on M , while M itself is expressed in terms of  in (23) and
(34). Hence, it remains to show that these choices are consistent, and in particular, to lower bound 
(and hence the cumulative regret bound T ) in terms of T alone.
d 
Application to the SE kernel: For the SE kernel, we have from the choice M = Θ log B
in
(23), along with the upper and lower bounds on  in (80) and (81), that

r 2 
σ
B d
log
.
(82)
=Θ
T

We therefore deduce that
B
log = log


r




T B2
B d/2
−
log
Θ(1)
log
σ2


(83)

by a direct substitution of (82). Now, since we have assumed that d = O(1), we find that the second

term behaves as O log log B , which is at most 12 log B when B is sufficiently small. By moving

B2T
B
=
Θ
log
, and substitution into (82)
this term to the
left-hand
side
of
(83),
we
find
that
log
2

σ
q


2
2
σ
B T d
yields  = Θ
, meaning that the lower bound T  yields (5).
T log σ 2
q
 
σ2
B2T d
Note that the behavior  = Θ
reveals that B is indeed arbitrary small when the
T log σ 2
√
d
σ
implied constant in the theorem assumption B
= O( T ) is sufficiently small (note that z log z1 → 0
as z → 0). This justifies the assumption of B being sufficiently small throughout our analysis.
d/ν 
Application to the Matérn kernel: For the Matérn kernel, we have from (34) that M = Θ B
,
2 d/ν 
2 d/ν 
σ
B
σ
B
and substitution into (81) gives 2 = Θ T d/ν , or equivalently T = Θ 2+d/ν . This, in turn, implies
d/ν
−1 
2
that  = Θ σ 2+d/ν B 2+d/ν T 2+d/ν , and hence the lower bound T  yields (6). Once again, we find that
√

σ
the assumption B
= O T (with a sufficiently small implied constant) in the theorem statement
ensures that B is sufficiently small.
D. High-Probability Regret Bounds
Here we discuss how to adapt the above proofs to provide lower bounds on the regret that hold
with a given probability 1 − δ .
For the simple regret, recall that we considered functions where all points are at most 4-suboptimal
(implying r(T ) ≤ 4), and showed that E[r(T ) ] ≥  for all T < T and suitably-defined T . For such

18

T , it follows from the reverse Markov inequality (i.e., Markov’s inequality applied to the random
variable 4 − r(T ) ) that
 − η
1−η
P[r(T ) ≥ η] ≥
=
(84)
4 − η
4−η

for any η ∈ (0, 1). By choosing η sufficiently small, and renaming η as 0 , it follows that in order
to achieve some target simple regret 0 with any constant probability above 43 , a lower bound of the
same form as the average regret bound holds.
An analogous argument applies for the cumulative regret upon recalling that we chose  such that
the average cumulative regret was lower bounded by T , while also considering functions such that
the cumulative regret can never exceed 4T .
VI. C ONCLUSION
We have given, to our knowledge, the first lower bounds on regret for (non-Bayesian) Gaussian
process bandit optimization in the presence of noise, considering both the simple regret and the
cumulative regret. These bounds nearly match existing upper bounds for the squared exponential
kernel, with the gaps being more significant for the Matérn kernel.
An immediate direction for future research is to settle our conjecture in Section II regarding the
presence of γT vs. γT2 in the existing upper bounds, which would close the gaps present for the squared
exponential kernel, and bring the bounds for the Matérn kernel closer together. Another interesting
direction is to provide lower bounds and improved upper bounds for the Bayesian setting. In this
setting, the “needle in haystack” type functions considered in the present paper are extremely unlikely
to be observed, and it is thus reasonable to expect that the optimal scaling laws may be significantly
milder than those for the RKHS setting.
A PPENDIX
We repeat the short proof from [3] here for completeness:
Z

Em [a(y)] − E0 [a(y)] = a(y) Pm (y) − P0 (y) dy
Z

≤
a(y) Pm (y) − P0 (y) dy
Pm (y)≥P0 (y)
Z

≤A
Pm (y) − P0 (y) dy

(85)
(86)
(87)

Pm (y)≥P0 (y)

A
kP0 − Pm k1
2p
≤ A D(P0 kPm ),
=

(88)
(89)

where (86)–(87) follow from the assumption that a(y) ∈ [0, A], (88) is a standard property of the
`1 -norm, and (89) follows from Pinsker’s inequality.

19

ACKNOWLEDGMENT
This work was supported in part by the European Commission under Grant ERC Future Proof, SNF
200021-146750 and SNF CRSII2-147633, and the ‘EPFL Fellows’ program (Horizon2020 665667).
R EFERENCES
[1] N. Aronszajn. Theory of reproducing kernels. Trans. Amer. Math. Soc, 68(3):337–404, 1950.
[2] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In Conf. Learning
Theory (COLT), 2010.
[3] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire.
Gambling in a
rigged casino: The adversarial multi-armed bandit problem.
Technical report,
http://www.dklevine.com/archive/refs4462.pdf, 1998.
[4] I. Bogunovic, J. Scarlett, A. Krause, and V. Cevher. Truncated variance reduction: A unified
approach to Bayesian optimization and level-set estimation. In Conf. Neur. Inf. Proc. Sys. (NIPS),
2016.
[5] S. Bubeck and N. Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-Armed
Bandit Problems. Found. Trend. Mach. Learn. Now Publishers, 2012.
[6] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In Conf.
Alg. Learn. Theory (ALT), 2009.
[7] A. D. Bull. Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Res.,
12(Oct.):2879–2904, 2011.
[8] E. Contal, D. Buffoni, A. Robicquet, and N. Vayatis. Machine Learning and Knowledge
Discovery in Databases, chapter Parallel Gaussian Process Optimization with Upper Confidence
Bound and Pure Exploration, pages 225–240. Springer Berlin Heidelberg, 2013.
[9] T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 2006.
[10] N. de Freitas, M. Zoghi, and A. J. Smola. Exponential regret bounds for Gaussian process
bandits with deterministic observations. In Proc. Int. Conf. Mach. Learn. (ICML), 2012.
[11] S. Grünewälder, J.-Y. Audibert, M. Opper, and J. Shawe-Taylor. Regret bounds for Gaussian
process bandit problems. In Int. Conf. Art. Intel. Stats. (AISTATS), pages 273–280, 2010.
[12] K. Kawaguchi, L. P. Kaelbling, and T. Lozano-Pérez. Bayesian optimization with exponential
convergence. In Adv. Neur. Inf. Proc. Sys. (NIPS), 2015.
[13] R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proc. ACM
Symp. Theory Comp. (STOC), pages 681–690, 2008.
[14] R. D. Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In Adv. Neur.
Inf. Proc. Sys. (NIPS), pages 697–704, 2004.
[15] K. O. Mead and L. M. Delves. On the convergence rate of generalized Fourier expansions. IMA
J. Appl. Math., 12:247–259, 1973.
[16] G. Raskutti, M. J. Wainwright, and B. Yu. Minimax-optimal rates for sparse additive models
over kernel classes via convex programming. J. Mach. Learn. Res., 13(Feb):389–427, 2012.

20

[17] G. Raskutti, M. J. Wainwright, and B. Yu. Early stopping and non-parametric regression: An
optimal data-dependent stopping rule. J. Mach. Learn. Res., 15(1):335–366, 2014.
[18] C. E. Rasmussen. Gaussian processes for machine learning. MIT Press, 2006.
[19] D. Russo and B. Van Roy. An information-theoretic analysis of Thompson sampling. J. Mach.
Learn. Res., 17(1):2442–2471, Jan. 2016.
[20] 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. Proc. IEEE, 104(1):148–175, 2016.
[21] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the
bandit setting: No regret and experimental design. In Int. Conf. Mach. Learn. (ICML), 2010.
[22] Z. Wang, B. Zhou, and S. Jegelka. Optimization as estimation with Gaussian processes in bandit
settings. In Int. Conf. Art. Intel. Stats. (AISTATS), 2016.
[23] Z. Wang and N. de Freitas. Theoretical analysis of Bayesian optimisation with unknown Gaussian
process hyper-parameters. http://arxiv.org/abs/1406.7758, 2014.

