Regret Bounds for Gaussian-Process Optimization in Large Domains
Year: 2022

Abstract:
The goal of this paper is to characterize Gaussian-Process optimization in the setting where the function domain is large relative to the number of admissible function evaluations, i.e., where it is impossible to find the global optimum. We provide upper bounds on the suboptimality (Bayesian simple regret) of the solution found by optimization strategies that are closely related to the widely used expected improvement (EI) and upper confidence bound (UCB) algorithms. These regret bounds illuminate the relationship between the number of evaluations, the domain size (i.e. cardinality of finite domains / Lipschitz constant of the covariance function in continuous domains), and the optimality of the retrieved function value. In particular, we show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).

heading: 1 Introduction
text: In practice, nonconvex, gradient-free optimization problems arise frequently, for instance when tuning the parameters of an algorithm or optimizing the controller of a physical system (see e.g. Shahriari et al. [2016]) for more concrete examples). Different versions of this problem have been addressed e.g. in the multi-armed-bandit and the Bayesian-optimization literature (which we review below). However, the situation where the number of admissible function evaluations is too small to identify the global optimum has so far received little attention, despite arising frequently in practice. For instance, when optimizing the hyper-parameters of a machine-learning method or the controllerparameters of a physical system, it is typically impossible to explore the domain exhaustively. We take first steps towards a better understanding of this setting through a theoretical analysis based on the adaptive-submodularity framework by Golovin and Krause [2011]. It is not the purpose of the present paper to propose a novel algorithm with better performance (we modify the EI and UCB strategies merely to facilitate the proof), but rather to gain an understanding of how GP-optimization performs in the aforementioned setting, as a function of the number of evaluations and the domain size.
As is done typically, we model the uncertainty about the underlying function as a Gaussian Process (GP). The question is how close we can get to the global optimum with T function evaluations, where T is small relative to the domain of the function (i.e., it is impossible to identify the global optimum with high confidence with only T evaluations). As a performance measure, we use the Bayesian simple regret, i.e., the expected difference between the optimal function value and the value attained by the algorithm. For the discrete case with domain size N , we derive a problemindependent regret bound (i.e., it only depends on T,N and is worst-case in terms of the GP prior) for two optimization algorithms that are closely related to the well-known expected improvement (EI, Jones et al. [1998]) and the upper confidence bound (UCB, Auer et al. [2002], Srinivas et al.
∗manuel.wuthrich@pm.me
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
[2010]) methods. In contrast to related work, our bounds are non-vacuous even when we can only explore a small fraction of the function. We extend this result to continuous domains and show that the resulting bound scales better with the size of the function domain (equivalently, the Lipschitz constant of the covariance function) than related work (Grünewälder et al. [2010]).

heading: 1.1 Related Work
text: The multi-armed bandit literature is closest to the present paper. In the multi-armed bandit problem, the agent faces a row of N slot machines (also called one-armed bandits, hence the name). The agent can decide at each of T rounds which lever (arm) to pull, with the objective of maximizing the payoff. This problem was originally proposed in Robbins [1952] to study the trade-off between exploration and exploitation in a generic and principled way. Since then, this problem has been studied extensively and important theoretical results have been established.
Each of the N arms has an associated reward distribution, with a fixed but unknown mean Fn. When pulling arm n at round t, we obtain a payoff Yt := Fn + En,t where the noise is zero mean E[En,t] = 0, independent across time steps and arms, and identically distributed for a given arm across time steps. Let us denote the arm pulled at time t by At. Performance is typically analyzed in terms of the regret, which is defined as the difference between the mean payoff of the optimal arm and the one pulled at time t
Rt := max n∈[N ] Fn − FAt . (1)
Here, we are interested in the setting where En,t is small or even zero and we are allowed to pull only few arms T < N . We classify related work according to the information about the mean Fn and the noise En,t that is available to the agent.

heading: 1.1.1 No Prior Information
text: Traditionally, most authors considered the case where only very basic information about the payoff Fn + En,t is available to the agent, e.g. that its distribution is a member of a given family of distributions or that it takes values in an interval, typically [0, 1].
In a seminal paper, Lai and Robbins [1985] showed that the cumulative regret ∑ t∈[T ]Rt grows at least logarithmically in T and proposed a policy that achieves this rate asymptotically. Later, Auer et al. [2002] proposed an upper confidence bound (UCB) strategy and proved that it achieves logarithmic cumulative regret in T uniformly in time, not just asymptotically. Since then, many related results have been obtained for UCB and other strategies, such as Thompson sampling Agrawal and Goyal [2011], Kaufmann et al. [2012]. A number of similar results have also been obtained for the objective of best arm identification Madani et al. [2004], Bubeck et al. [2009], Audibert and Bubeck [2010], where we do not care about the cumulative regret, but only about the lowest regret attained.
However, all of these bounds are nontrivial only when the number of plays is larger than the number of arms T > N . This is not surprising, since no algorithm can be guaranteed to perform well with a low number of plays with such limited information. To see this, consider an example where Fi = 1 and Fn = 0 ∀n 6= i. Since the agent has no prior information about which is the right arm i, the best it can do is to randomly try out one after the other. Hence it is clear that to obtain meaningful bounds for T < N we need more prior knowledge about the reward distributions of the arms.

heading: 1.1.2 Structural Prior Information
text: In Dani et al. [2008] the authors consider the problem where the mean rewards at each bandit are a linear function of an unknown, K-dimensional vector. However, similarly to the work above, the difficulty addressed in this paper is mainly the noise, i.e. the fact that the same arm does not always yield the same reward. For En,t = 0, the O(K) cumulative regret bounds derived in this paper are trivial, since with O(K) evaluations we can simply identify the linear function.

heading: 1.1.3 Gaussian Prior
text: More closely related to our work, a number of authors have considered Gaussian priors. Bull [2011] for instance provides asymptotic convergence rates for the EI strategy with Gaussian-process priors on the unknown function.
Srinivas et al. [2010] propose a UCB algorithm for the Gaussian-process setting. The authors give finite-time bounds on the cumulative regret. However, these bounds are intended for a different setting than the one we consider here: 1) They allow for noisy observations and 2) they are only meaningful if we are allowed to make a sufficient number of evaluations to attain low uncertainty over the entire GP. Please see Appendix B for more details on the second point.
Russo and Van Roy [2014] use a similar analysis to derive bounds for Thompson sampling, which are therefore subject to similar limitations. In contrast, the bounds in Russo and Van Roy [2016] do not depend on the entropy of the entire GP, but rather on the entropy of the optimal action. However, our goal here is to derive bounds that are meaningful even when the optimal action cannot be found, i.e. its entropy remains large.
De Freitas et al. [2012] complement the work in [Srinivas et al., 2010] by providing regret bounds for the setting where the function can be observed without noise. However, these are asymptotic and therefore not applicable to the setting we have in mind.
Similarly to the present paper, Grünewälder et al. [2010] analyze the Bayesian simple regret of GP optimization. They provide a lower and an upper bound on the regret of the optimal policy for GPs on continuous domains with covariance functions that satisfy a continuity assumption. Here, we build on this work and derive a bound with an improved dependence on the Lipschitz constant of the covariance function, i.e., our bound scales better with decreasing length-scales (and, equivalently, larger domains). Unlike [Grünewälder et al., 2010], we also consider GPs on finite domains without any restrictions on the covariance.

heading: 1.1.4 Adaptive Submodularity
text: The adaptive-submodularity framework of Golovin and Krause [2011] is in principle well suited for the kind of analysis we are interested in. However, we will show that the problem at hand is not adaptively submodular, but our proof is inspired by that framework.

heading: 2 Problem Definition

heading: 2.1 The Finite Case
text: In this section we specify the type of bandit problem we are interested in more formally. The goal is to learn about a function with domain A = [N ] (we will use [N ] to denote the set {1, ..., N}) and co-domain R. We represent the function as a sequence F = (Fn)n∈[N ]. Our prior belief about the function F is assumed to be Gaussian
F ∼N (µ,Σ). (2) At each of the T iterations, we pick an action (arm) At from [N ] at which we evaluate the function. After each action, an observation Yt ∈ R is returned to the agent
Yt := FAt . (3)
Note that here we restrict ourselves to the case where the function can be evaluated without noise.
For convenience, we introduce some additional random variables, based on which the optimization algorithm will pick where to evaluate the function next. We denote the posterior mean and covariance at time t by
Mt : = E[F |A:t, Y:t] (4) Ct : = COV[F |A:t, Y:t]. (5)
In addition, we will need the maximum and minimum observations up to time t
Ŷt : = max k∈[t]
Yk ∀t ∈ {1, .., T} (6)
Y̌t : = min k∈[t]
Yk ∀t ∈ {1, .., T}. (7)
Furthermore, we will make statements about the difference between the smallest and the largest observed value
ˆ̌Yt : = Ŷt − Y̌t ∀t ∈ {1, .., T}. (8)
Finally, for notational convenience we define
Ŷ , Y̌ , ˆ̌Y : = ŶT , Y̌T , ˆ̌YT . (9)
Analogously, let us define the function minimum F̌ := minn∈[N ] Fn, maximum F̂ := maxn∈[N ] Fn and difference ˆ̌F := F̂ − F̌ .

heading: 2.1.1 Problem Instances
text: A problem instance is defined by the tuple (N,T, µ,Σ), i.e. the domain size N ∈ N>0, the number of rounds T ∈ N>0 and the prior (2) with mean µ ∈ RN and covariance Σ ∈ Sn+, where we use Sn+ to denote the set of positive semidefinite matrices of size n.

heading: 2.2 The Continuous Case
text: The definitions in the continuous case are analogous. A problem instance here is defined by (A, T, µ, k), i.e. the function domain A, the number of rounds T ∈ N>0, a mean function µ : A → R and a positive semi-definite kernel k : A2 → R.

heading: 3 Results
text: In this section we provide bounds on the Bayesian simple regret that hold for the two different optimization algorithms we describe in the following.

heading: 3.1 Optimization Algorithms
text: Two of the most widely used GP-optimization algorithms are the expected improvement (EI) (Jones et al. [1998]) and the upper confidence bound (UCB) (Auer et al. [2002], Srinivas et al. [2010]) methods. In the following, we define two optimization policies that are closely related:
Definition 1. The expected improvement Bull [2011] is defined as
ei(τ) : = ∫ ∞ −∞ max{x− τ, 0}N (x)dx = N (τ)− τΦc(τ) (10)
where N is the standard normal density function and Φc is the complementary cumulative density function of a standard normal distribution. Furthermore, we use the notation
ei(τ |µ, σ) = σ ei ( τ − µ σ ) = ∫ ∞ −∞ max{x− τ, 0}N (x|µ, σ)dx. (11)
Definition 2 (EI2). An agent follows the EI2 strategy when it picks its actions according to
At+1 = argmax n∈[N ]
max { ei ( Ŷt|Mnt , √ Cnnt ) , ei ( −Y̌t| −Mnt , √ Cnnt )} (12)
with the expected improvement ei as defined in Definition 1.
Definition 3 (UCB2). An agent follows the UCB2 strategy when it picks its actions according to
At+1 = argmax n∈[N ]
max { −Ŷt +Mnt + √ Cnnt 2 logN, Y̌t −Mnt + √ Cnnt 2 logN } . (13)
The main difference to the standard versions of these methods (see Definition 6 and Definition 7) is that the algorithms here are symmetrical in the sense that they are invariant to flipping the sign of the GP. They maximize and minimize at the same time by picking the point which we expect to either increase the observed maximum or decrease the observed minimum the most. This symmetry is important for our proof, whether the same bound also holds for following the standard, one-sided EI or UCB strategies is an open question, we discuss this point in detail in Section 4.

heading: 3.2 Upper Bound on the Bayesian Simple Regret for the Extremization Problem
text: Here, we provide a regret bound for function extremization (i.e. the goal is to find both the minimum and the maximum) from which the regret bound for function maximization will follow straightforwardly. Note that the bound is problem-independent in the sense that it does not depend on the prior (µ,Σ). Theorem 1. For any instance (N,T, µ,Σ) of the problem defined in Section 2.1 withN ≥ T ≥ 500, if we follow either the EI2 (Definition 2) or the UCB2 (Definition 3) strategy, we have
E [ ˆ̌F ] − E [ ˆ̌Y ]
E [ ˆ̌F ] ≤ 1− (1− T− 12√π ) √√√√ log(T )− log (3 log 32 (T )) log(N) . (14)
This guarantees that the expected difference between the maximum and minimum retrieved function value achieves a certain ratio with respect to the expected difference between the global maximum and the global minimum.
Proof. The full proof can be found in the supplementary material in Appendix G, here we only give an outline. The proof is inspired by the adaptive submodularity framework by Golovin and Krause [2011]. The problem at hand can be understood as finding the policy (optimization algorithm) which maximizes an expected utility. Finding this optimal policy would require solving a partially observable Markov decision process (POMDP), which is intractable in most relevant situations. Instead, a common approach is to use a greedy policy which maximizes the expected single-step increase in utility at each time step t, which is in our case
At+1 = argmax a
( E [ Ŷt+1 − Y̌t+1|At+1 = a,A:t, Y:t ] − E [ Ŷt − Y̌t|A:t, Y:t ]) . (15)
This corresponds to the EI2 (Definition 2) strategy. The task now is to show that the greedy policy will not perform much worse than the optimal policy. Golovin and Krause [2011] show that this holds for problems that are adaptively submodular (among some other conditions). In the present problem, we can roughly translate this condition to: The progress we make at a given time step has to be proportional to how far the current best value is from the global optimum. While our problem is not adaptively submodular (see Appendix A), we show that a similar condition holds (which leads to similar guarantees).

heading: 3.3 Upper and Lower Bound on the Bayesian Simple Regret for the Maximization Problem
text: For maximization, the goal is to minimize the Bayesian simple regret, i.e. the expected difference between the globally maximal function value and the best value found by the optimization algorithm
E[F̂ ]− E[Ŷ ]. (16) As is often done in the literature (see e.g. Srinivas et al. [2010]), we restrict ourselves here to centered GPs (i.e. zero prior mean; naturally, the mean will change during the optimization). To be invariant to scaling of the prior distribution, we normalize the regret with the expected global maximum:
normreg := E [ F̂ ] − E [ Ŷ ]
E [ F̂ ] . (17)

heading: 3.3.1 Upper Regret Bound for the EI2 and UCB2 Policies
text: We obtain the following upper bound on this normalized Bayesian simple regret: Corollary 1. For any instance (N,T, µ,Σ) of the problem defined in Section 2.1 with zero mean µn = 0 ∀n and N ≥ T ≥ 500, if we follow either the EI2 (Definition 2) or the UCB2 (Definition 3) strategy, we have
normreg ≤ 1− ( 1− T− 1 2 √ π )√√√√ log(T )− log (3 log 32 (T )) log(N) . (18)
This implies a bound on the ratio between the expected maximum found by the algorithm and the expected global maximum.
Proof. The Gaussian prior is symmetric about 0, as the mean is 0 everywhere (i.e. the probability density satisfies p(F = f) = p(F = −f) ∀f ). Since also both the EI2 and the UCB2 policies are symmetric, we have E [ F̂ ] = −E [ F̌ ] and hence
E [ ˆ̌F ] = E [ F̂ ] − E [ F̌ ] = 2E [ F̂ ]
(19) and similarly E [ ˆ̌Y ] = 2E [ Ŷ ] . Substituting this in Theorem 1, Corollary 1 follows.
In Figure 1, we plot this bound, and we observe that we obtain nontrivial regret bounds even when evaluating the function only at a small fraction of its domain. For instance, if we pick the curve that corresponds to N = 1020 (the rightmost curve), and we choose T = 106, we achieve a regret of about 0.6, as indicated in the figure. This means that we can expect to find a function value of about 40% of the expected global maximum by evaluating the function at only a fraction of 10−14 of its domain, and this holds for any prior covariance Σ.
In Figure 2, we plot the upper bound on the required number of evaluations T , implied by Corollary 1, as a function of the domain size N . We observe that T seems to scale polynomially with N (i.e. linearly in log space) with an order that depends on the regret we want to achieve. Indeed, it is easy to see from Corollary 1 that ∀ > 0 ∃K : ∀N ≥ T ≥ K :
normreg ≤ 1− √
log T√ logN + (20)
which implies that ∀ > 0 ∃K : ∀N ≥ T ≥ K : T ≤ N (1−normreg+ ) 2
. (21) This means for instance that, if we accept to achieve only 20% of the global maximum, the required number of evaluations grows very slowly with about T ≈ N1/25, but still polynomially.

heading: 3.3.2 Lower Regret Bound for the Optimal Policy
text: The upper bound from Corollary 1 is tight, as we can see by comparing (20) to the following result:
Lemma 1 (Lower Bound). For the instance of the problem defined in Section 2.1 with µ = 0 and Σ = I, the following lower bound on the regret holds for the optimal strategy: ∀ > 0 ∃K : ∀N ≥ T ≥ K :
normreg ≥ 1− √
log T√ logN − . (22)
Proof. Here, sampling without replacement is an optimal strategy, which yields the bound above, see Appendix I for the full proof.
It follows from Lemma 1 that ∀ > 0 ∃K : ∀N ≥ T ≥ K :
T ≥ N (1−normreg− ) 2 . (23)
Hence, for a given regret, the required number of evaluations T grows polynomially in the domain size N , even for the optimal policy, albeit with low degree. This means that if the domain size grows exponentially in the problem dimension, we will inherit this exponential growth also for the necessary number of evaluations. However, since our bounds are problem independent and hence worst-case in terms of the prior covariance Σ, this result does not exclude the possibility that for certain covariances we might be able to obtain polynomial scaling of the required number of evaluations in the dimension of the problem.

heading: 3.3.3 Lower Regret Bound for Prior-Independent Policies
text: It is important to note that a uniform random policy will not achieve the bound from Corollary 1 in general. In fact, despite the bound from Corollary 1 being independent of the prior (µ,Σ), it cannot be achieved by any policy that is independent of the prior:
Lemma 2. For any optimization policy which does not depend on the prior (µ,Σ), there exists an instance of the problem defined in Section 2.1 where
normreg ≥ 1− T N , (24)
which is clearly worse for T N than the bound in Corollary 1.
Proof. Suppose we construct a function that is zero everywhere except in one location. Since the policy has no knowledge of that location, it is possible to place it such that the policy will perform no better than random selection, which yields the regret above. See Appendix J for the full proof.

heading: 3.4 Extension to Continuous Domains
text: For finite domains, we looked at the setting where the cardinality of the domain N is much larger than the number of admissible evaluations T . The notion of domain size is less obvious in the continuous case, in the following we clarify this point before we discuss the results.

heading: 3.4.1 Problem Setting
text: In the continuous setting, we characterize the GP by Lk and σ, which are properties of the kernel k:
|k(x, x)− k(x, y)| ≤ Lk ‖x− y‖∞ ∀x, y ∈ A (25) k(x, x) ≤ σ2 ∀x ∈ A (26)
where A is the D-dimensional unit cube (note that to use a domain other than the unit cube we can simply rescale). The setting we are interested in is
T ( Lk 2σ2 )D =: m(Lk, σ,D). (27)
As we discuss in more detail in Appendix C, m(Lk, σ,D) corresponds to the number of points we would require to cover the domain such that we could acquire nonzero information about any point in the domain. Naturally, to guarantee that we can find the global optimum we would require at least that number of evaluations T . Here, in contrast, we consider the setting where T is much smaller and only a small fraction of the GP can be explored.

heading: 3.4.2 Results
text: Here, we adapt Corollary 1 to continuous domains. The bound we propose in the following is based on a result from [Grünewälder et al., 2010], which states that for a centered Gaussian Process (Ga) a∈A with domain A being the D-dimensional unit cube and a Lipschitz-continuous kernel k |k(x, x)− k(x, y)| ≤ Lk ‖x− y‖∞ ∀x, y ∈ A, (28) the regret of the optimal policy is bounded by
E [
sup a∈A
G(a)− Ŷ ] ≤ √
2Lk⌊ T 1/D ⌋ (2√log (2T ) + 15√D) . (29) Note that Grünewälder et al. [2010] state the bound for the more general case of Hölder-continuous functions, for simplicity of exposition we limit ourselves here to the case of Lipschitz-continuous kernels. Grünewälder et al. [2010] complement this bound with a matching lower bound (up to log factors). However, as we shall see, we can improve substantially on this bound in terms of its dependence on the Lipschitz constant Lk if we assume that the variance is bounded, i.e., k(x, x) ≤ σ2. This is particularly relevant for GPs with short length scales (or, equivalently, large domains) and hence large Lk.
Interestingly, Grünewälder et al. [2010] obtain (29) using a policy that selects the actions a priori (by placing them on a grid), without any feedback from the observations made. Here, we will refine (29) by using this strategy for preselecting a large set of admissible actions offline and then selecting actions from this set using EI2 (Definition 2) or UCB2 (Definition 3) online. A reasoning along these lines yields the following bound: Theorem 2. For any centered Gaussian Process (Ga) a∈A, where A is the D-dimensional unit cube, with kernel k such that
|k(x, x)− k(x, y)| ≤ Lk ‖x− y‖∞ ∀x, y ∈ A (30)√ k(x, x) ≤ σ ∀x ∈ A (31)
we obtain the following bound on the regret, if we follow the EI2 (Definition 2) or the UCB2 (Definition 3) strategy:
E [
sup a∈A
G(a)− Ŷ ] ≤ √ 2 log(Lk)
T 1/D
2 √√√√log(2⌈ Lk
log(Lk) T 1/D
⌉D) + 15 √ D + √
2σ √D log(⌈ Lk log(Lk) T 1/D ⌉) − ( 1− T− 1 2 √ π )√√√√log( T 3 log 3 2 (T ) ) . (32) This bound also holds when restricting EI2 or UCB2 to a uniform grid on the domainA, where each side is divided into ⌈ Lk
log(Lk) T 1/D
⌉ segments. Finally, this bound converges to 0 as T →∞.
Proof. The idea here is to pre-select a set ofN points at locationsX1:N on a grid and then sub-select points from this set during runtime using EI2 (Definition 2) or UCB2 (Definition 3). We bound the regret of this strategy by combining Theorem 1 with the main result from [Grünewälder et al., 2010], the full proof can be found in Appendix K.
The important point to note here is that in Theorem 2 the bound grows logarithmically in Lk, as opposed to the bound (29) from Grünewälder et al. [2010], which grows with √ Lk. This means that for Gaussian Processes with high Lk, i.e. high variability, (32) is much lower than (29) (note that cuboid domainsA can be rescaled to the unit cube by adapting the Lipschitz constant Lk accordingly, hence a large domain is equivalent to a large Lipschitz constant). This allows for meaningful bounds even when the number of allowed evaluations is small relative to the domain-size of the function. We illustrate this in Figure 3. Consider for instance the case of Lk = 105, σ = 1, D = 2, T = 105, where the number of evaluations is far too low to explore the GP (T = 105 m(Lk, σ,D) = 2.5× 109). We see from Figure 3a that our regret bounds (second-darkest cyan) remain low while the ones from Grünewälder et al. [2010] (second-darkest magenta) explode. Theorem 2 also provides another insight: To allow for straightforward optimization of the acquisition function (e.g. EI, UCB), the domain is often discretized in practical Bayesian optimization. Theorem 2 tells us how fine this discretization should be to still achieve performance guarantees.

heading: 4 Relation to Standard EI and UCB
text: An empirical comparison (Appendix F) indicates EI2/UCB2 require more evaluations than EI/UCB to attain a given regret, but not more than twice as many. This matches our intuition: We would expect standard EI/UCB to perform better because i) any given step, evaluating at a potential maximizer instead of a minimizer will clearly lead to a larger immediate reduction in expected regret and ii) we would not expect an evaluation at a potential minimizer to provide any more useful information than an evaluation at a potential maximizer. Further, we would not expect EI2/UCB2 to perform much worse because a substantial fraction of its evaluations (in expectation half, for a centered GP) will be maximizations.
If we could prove that EI/UCB performs better than EI2/UCB2 for maximization, this would imply that the regret bounds presented above apply to EI/UCB. Unfortunately, proving this formally appears to be nontrivial. Nevertheless, we are able to give weaker regret bounds for standard EI/UCB which we discuss in the following.

heading: 4.1 Upper Bound on the Bayesian Simple Regret for Standard EI and UCB
text: Let us now consider the standard, one-sided versions of EI (Definition 6) and UCB (Definition 7), which are identical to EI2 (Definition 2) and UCB2 (Definition 3) except that we drop the second term in the max. We obtain the following version of Theorem 1: Theorem 3. For any instance (N,T, µ,Σ) of the problem defined in Section 2.1 withN ≥ T ≥ 500, if we follow either the EI (Definition 6) or the UCB strategy (Definition 7) we have
E [ ˆ̌F ] − E [ Ŷ − F̌ ] E [ ˆ̌F ] ≤ 1− (1− T− 12√π ) √√√√ log(T )− log (3 log 32 (T )) log(N) . (33)
Proof. The proof is very similar to the one of Theorem 1 and can be found in Appendix H.
Note that we marked the changes in bold. Now, instead of a guarantee on ˆ̌Y , we provide a guarantee on Ŷ − F̌ , i.e. the difference between the best obtained value and the function minimum. We can then derive from that a version of Corollary 1: Corollary 2. For any instance (N,T, µ,Σ) of the problem defined in Section 2.1 with zero mean µn = 0 ∀n and N ≥ T ≥ 500, if we follow either standard EI (Definition 6) or UCB strategy (Definition 7), we have
normreg ≤ 2 1− (1− T− 12√π ) √√√√ log(T )− log (3 log 32 (T ))
log(N)
 . (34)
Proof. The proof is analogous to the one of Corollary 1.
The important thing to note here is the appearance of the factor 2 in the bound. This means that asymptotically we have normreg ≤ 2 ( 1− √
log T√ logN
) + (35)
and T ≤ N (1−normreg/2+ ) (36)
which is weaker compared to (20) and (21). We believe that this gap is not due to EI/UCB actually performing worse than EI2/UCB2, but rather an artifact of the proof.

heading: 5 Limitations
text: While we believe that the results above are insightful, there are a number of limitations one should be aware of:
As discussed in Section 4, the regret bounds we derive for standard EI and UCB are weaker than the ones for EI2 and UCB2, despite the intuition and empirical evidence that EI/UCB most likely perform no worse for maximization than EI2/UCB2. It would be interesting to close this gap.
Another limitation is that the bounds only hold for the noise-free setting. We believe that this limitation is acceptable because the problem of noisy observations is mostly orthogonal to the problem studied herein. Furthermore, the naive solution of reducing the noise by evaluating multiple times at each point leads to qualitatively similar regret bounds, see Appendix D for a more detailed discussion.
Further, the bounds from Corollary 1, Theorem 2, and Corollary 2 only hold for zero prior mean (equivalently, constant prior mean). This assumption is not uncommon in the GP optimization literature (see e.g. Srinivas et al. [2010]) but it may be limiting if one has prior knowledge about where good function values lie. It is likely possible to extend the results in this article to arbitrary prior means.
Finally, there are limitations that hold generally for the GP optimization literature: 1) In a naive implementation, the computational cost is cubic in the number of evaluations T and 2) the assumption that the true function is drawn from a Gaussian Process is typically not realistic and only made for analytical convenience. It is hence not clear whether the relations we uncovered herein apply to realistic optimization settings or if they are mostly an artifact of the GP assumption.
Summarizing, it is clear that the results in the present paper have little direct practical relevance. Instead, the intention is to develop a theoretical understanding of the problem setting.

heading: 6 Conclusion
text: We have characterized GP optimization in the setting where finding the global optimum is impossible because the number of evaluations is too small with respect to the domain size. We derived regret-bounds for the finite-arm setting which are independent of the prior covariance, and we showed that they are tight. Further, we derived regret-bounds for GP optimization in continuous domains that depend on the Lipschitz constant of the covariance function and the maximum variance. In contrast to previous work, our bounds are non-vacuous even when the domain size is very large relative to the number of evaluations. Therefore, they provide novel insights into the performance of GP optimization in this challenging setting. In particular, they show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).

Review summaries:
This paper considers Gaussian process optimization and provides bounds for the (normalized) Bayesian simple regret of two policies. Each of these policies can be seen as a symmetrization of either the classical expected improvement (EI) or upper confidence bound (UCB) policies. The symmetrized version of EI, which is denoted by EI2,  picks the point expected to either increase the current observed maximum or decrease the current observed minimum the most. UCB2 is defined analogously with respect to UCB. The bounds obtained are shown to be tight and suggest that it is possible to find points with high (normalized) objective value even when the number of evaluations is small relative to the number of points in the domain, $N$,  (in the finite case, or relative to the smoothness of the prior covariance function in the continuous case), although it still grows polynomially with respect to $N$. Such guarantee contrasts with previously obtained results, which require the number of evaluations to be large with respect to the number of points in the domain.

The paper derives bounds for the Bayesian simple regret of two GP optimization policies that are variants of the popular expected improvement and UCB, specifically under the assumption that the querying budget is very low compared to the size of the search space. The authors first do this in the discrete setting where there are a finite number of actions to be taken and then extend their results to the continuous setting. The bounds are derived using a procedure inspired by the adaptive submodularity framework. Results show that these new bounds are lower than those from a previous work.

The paper studies regret bounds for Bayesian Optimization (with UCB & EI as acquisition functions) in the setting where the function domain is large relative to the number of admissible function evaluations, and the function evaluation is noiseless. The paper proposes two modified version of EI and UCB for this purpose and characterize the Bayesian simple regret of these methods, for both discrete and continuous domains. The work shows that the methods can find nontrivial function values even when the number of evaluations is far too small to find the global optimum.

This paper studies the problem of Gaussian process optimization when the number of arms (the domain) is larger than the horizon of the problem. In the finite arm case, it is assumed that the function is drawn from a zero-mean Gaussian prior and the learner is allowed to make T noiseless queries. Two algorithms based on expected improvement and UCB are proposed to solve this by achieving a simple regret that is some fraction of the optimal value. These are shown to be tight. It is shown that similar results can be extended to the continuous domain, but instead depending on a large Lipschitz constant.