Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit
Optimization

Hung Tran-The Sunil Gupta Santu Rana Svetha Venkatesh

Applied Artificial Intelligence Institute, Deakin University, Geelong,
Australia

###### Abstract

The expected improvement (EI) algorithm is one of the most popular strategies
for optimization under uncertainty due to its simplicity and efficiency.
Despite its popularity, the theoretical aspects of this algorithm have not
been properly analyzed. In particular, whether in the noisy setting, the EI
strategy with a standard incumbent converges is still an open question of the
Gaussian process bandit optimization problem. We aim to answer this question
by proposing a variant of EI with a standard incumbent defined via the GP
predictive mean. We prove that our algorithm converges, and achieves a
cumulative regret bound of $\mathcal{O}(\gamma_{T}\sqrt{T})$, where
$\gamma_{T}$ is the maximum information gain between $T$ observations and the
Gaussian process model. Based on this variant of EI, we further propose an
algorithm called Improved GP-EI that converges faster than previous
counterparts. In particular, our proposed variants of EI do not require the
knowledge of the RKHS norm and the noise’s sub-Gaussianity parameter as in
previous works. Empirical validation in our paper demonstrates the
effectiveness of our algorithms compared to several baselines.

##  1 Introduction

The problem of sequentially optimizing a black-box function based on bandit
feedback has recently attracted a great deal of attention and finds
application in robotics (Lizotte et al., 2007; Martinez-cantin et al., 2007),
environmental monitoring (Marchant and Ramos, 2012), automatic machine
learning (Bergstra et al., 2011; Snoek et al., 2012; Hoffman et al., 2014) and
reinforcement learning (Wilson et al., 2014; Balakrishnan et al., 2020). Under
this model, the goal is to design a sequential algorithm in a search space
$\mathcal{X}$, i.e., a sequence $x_{1},x_{2},..,x_{T}$ such that at iteration
$T$, the algorithm returns a state with the highest possible value. For this
problem, a widely used performance measure is the _cumulative regret_ $R_{T}$,
which is given by
$R_{T}=\sum_{t=1}^{T}\text{sup}_{x\in\mathcal{X}}f(x)-f(x^{+}_{t})$, where
$x^{+}_{t}$ is the point reported by the algorithm at iteration $t$.

In order to make this problem tractable, one must make smoothness assumptions
on the function. A versatile means for doing this is to model the function as
a Gaussian process (GP) which captures the smoothness properties through a
suitably chosen kernel. For GP-based algorithms, there are two settings:
_Bayesian_ (De Freitas et al., 2012; Tran-The et al., 2021) and _non-Bayesian_
(Scarlett et al., 2017). In Bayesian setting, the function is assumed to be
sampled from a GP while in the non-Bayesian setting, the function is treated
as fixed and unknown, and assumed to lie in a reproducing kernel Hilbert space
(RKHS). Under these assumptions, the optimization problem is usually called
the _Gaussian process bandit optimization_ whereas the optimization in
Bayesian setting is referred to as _Bayesian optimization_. In this paper, we
focus on the non-Bayesian setting, i.e. Gaussian process bandit optimization.

The Expected Improvement (EI) (Močkus, 1975) is one of the most widely used
strategy to optimize black-box functions due to its simplicity and ability to
handle uncertainty(e.g., works of Osborne (2010); Wilson et al. (2014); Qin et
al. (2017); Malkomes and Garnett (2018); Nguyen and Osborne (2020)). Unlike
other popular strategies, upper confidence bound (UCB) and Thompson sampling
(TS), EI is a greedy improvement-based strategy, which samples the next point
offering the greater expected improvement over the current incumbent.
Formally, $\alpha^{EI}(x)=\mathbb{E}[\text{max}\\{0,f(x)-\xi\\}]$, where $\xi$
is the incumbent to be defined. In the noiseless setting, $\xi$ is defined as
the current best observation so far, $f^{+}_{t}$. Given $\mathcal{D}_{t}$
which is the set of sampled points up to iteration $t$, $f^{+}_{t}$ at
iteration $t$ is computed as $f^{+}_{t}=\text{max}_{1\leq i\leq t}f(x_{i})$.
However, in the noisy setting, such a choice is not clear due to the noise. As
an alternative, $\xi$ is typically defined as either the current best value of
the GP predictive mean, formally $\xi=\mu^{+}_{t}$ which is computed as
$\mu^{+}_{t}=\text{max}_{1\leq i\leq t}\mu_{t}(x_{i})$, or the current best
observation value (containing the noise), formally $\xi=y^{+}_{t}$. Although
these incumbents can be easily computed, they make the theoretical analysis
harder.

A key challenge of analyzing EI-based algorithms comes from its improvement
function involving nonlinear, nonconvex term unlike UCB and TS. This causes
the difficulty of the analysis of EI. In the noisy setting, another challenge
comes from the fact that the incumbents such as $\xi=\mu^{+}_{t}$ or
$\xi=y^{+}_{t}$ do not have monotonicity property like the function
$f^{+}_{t}$ ($f^{+}_{t+1}\geq f^{+}_{t}$). This is one of crucial properties
to reach the convergence in the noise-free setting (Bull, 2011). These reasons
explain why convergence properties of GP-EI are not been well studied
especially in the noisy setting.

Wang and de Freitas (2014) studied GP-EI when the lower and upper bounds of
hyper-parameters of GP are known. However, to guarantee the convergence, their
non-peer reviewed work uses an alternative choice of the incumbent as the
maximum of the GP predictive mean
$\xi=\text{max}_{x\in\mathcal{X}}\mu_{t}(x)$. As a result, their GP-EI
algorithm requires an additional optimization step to approximate $\mu_{t}(x)$
_at each iteration_ which is computationally expensive compared to the use of
standard incumbents $\mu^{+}_{t}$ or $y^{+}_{t}$ especially when the search
space is large or unbounded (Tran-The et al., 2020).

Nguyen et al. (2017) proposed a “weak” version of GP-EI which uses $y^{+}$ as
the incumbent. This incumbent is easily computed, however their version of GP-
EI needs to use an assumption that values of the variance function at all
sampled points are not allowed to exceed a lower bound $\kappa$. Due to this,
their GP-EI regret upper bound depends on $\kappa$ and this bound quickly
explodes as $\kappa\rightarrow\infty$. As a result, their analysis does not
solve the traditional EI algorithm as we consider in this paper. Therefore,
_the natural question of whether GP-EI with a standard setting of incumbent
(e.g., $\xi=\mu^{+}$ or $\xi=y^{+}$) converges, and if true then what
convergence rate GP-EI can reach are open problems?._ In this paper, we
provide an affirmative answer to these questions. Our main contributions are
as follows:

  * •

We propose a variant of GP-EI for Gaussian process bandit optimization. This
algorithm uses a standard incumbent
$\xi=\text{max}\\{\mu_{t-1}(x_{i})\\}_{x_{i}\in\mathcal{D}_{t-1}}$ at
iteration $t$, where $\mathcal{D}_{t-1}$ is the set of sampled points up to
iteration $t$. Our algorithm enjoys a cumulative regret bound of
$\mathcal{O}(\gamma_{T}\sqrt{T})$, where $\gamma_{T}$ is the maximum
information gain between $T$ observations and the GP model. To our knowledge,
this is the first GP-EI algorithm using a standard incumbent with theoretical
guarantees.

  * •

Based on our above algorithm, we propose an efficient variant of GP-EI called
Improved-GP-EI of which $f$ lies in RKHS equipped by a Matérn-$\nu$ kernel.
Improved-GP-EI can achieve regret
$\tilde{\mathcal{O}}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$ for every $\nu>1$
and $d\geq 1$. By using a searching partitioning strategy, Improved-GP-EI
avoids the quick growth of the global scale of variance functions. In
particular, it does not require the knowledge of the RKHS norm and the
measurement noise’s sub-Gaussianity parameter. These parameters are required
by most previous algorithms for theoretical guarantees, but are usually
unknown in real applications.

  * •

We demonstrate the practical effectiveness of Improved-GP-EI against GP-EI and
$\pi$-GP-UCB on various synthetic functions.

##  2 Preliminaries

We consider a global optimisation problem whose goal is to maximise $f(x)$
subject to $x\in\mathcal{X}\subset\mathbb{R}^{d}$, where $d$ is the number of
dimensions and $f$ is an expensive blackbox function that can only be
evaluated point-wise. The performance of a global optimisation algorithm is
typically evaluated using the cumulative regret which we have defined in
section Introduction.

###  2.1 Regularity Assumptions

We assume that $f$ lives in a RKHS of functions
$\mathcal{X}\rightarrow\mathbb{R}$ with positive semi-definite kernel function
$k$. This $H_{k}$ space is defined as the Hilbert space of functions on
$\mathcal{X}$ equipped with an inner product $\langle.\rangle_{k}$ obeying the
reproducing property: $f(x)=\langle f,k(x,.)\rangle_{k}$ for all $f\in
H_{k}(\mathcal{X})$. The RKHS norm $||f||_{k}=\sqrt{\langle f,f\rangle_{k}}$
is a measure of smoothness of $f$, with respect to the kernel function $k$,
and satisfies: $f\in H_{k}(\mathcal{X})$ if and only if $||f||_{k}<\infty$. We
assume that the RKHS norm of the unknown target function is bounded by
$||f||_{k}\leq B$. Two common kernels that satisfy bounded variance property
are Squared Exponential (SE) and Matérn, defined as

$\displaystyle
k_{\text{SE}}(x,x^{\prime})=\text{exp}(\frac{-||x-x^{\prime}||^{2}}{2l^{2}}),$
(1) $\displaystyle
k_{\text{Mat}}(x,x^{\prime})=\frac{2^{1-\nu}}{\Gamma(\nu)}(\frac{||x-x^{\prime}||_{2}}{l})^{\nu}\mathcal{B}_{\nu}(\frac{||x-x^{\prime}||_{2}}{l}),$
(2)

where $\Gamma$ denotes the Gamma function, $\mathcal{B}_{\nu}$ denotes the
modified Bessel function of the second kind, $\nu$ is a parameter controlling
the smoothness of the function and $l$ is the lengthscale of the kernel.
Important special cases of $\nu$ include $\nu=\frac{1}{2}$ that corresponds to
the exponential kernel and $\nu\rightarrow\infty$ that corresponds to the
square exponential (SE) kernel. The Matérn kernel is of particular practical
significance, since it offers a more suitable set of assumptions for the
modeling and optimisation of physical quantities (Stein, 1999).

###  2.2 Gaussian process bandit optimization

Gaussian process bandit optimization proceeds sequentially in an iterative
fashion. At each iteration, a surrogate model is used to probabilistically
model $f(x)$. Gaussian process (GP) (Rasmussen and Williams, 2005) is a
popular choice for the surrogate model as it offers a prior over a large class
of functions and its posterior and predictive distributions are tractable.
Formally, we assume $f(x)\sim\mathcal{GP}(m(x),\omega^{2}k(x,x^{\prime}))$ a
prior distribution where $m(x)$ is the mean function and
$\omega^{2}k(x,x^{\prime})$ is the covariance function in which
$k(x,x^{\prime})$ is a kernel function associated with the RKHS $H_{k}$ in
which $f$ is assumed to have norm at most $B$, and $\omega>0$ is a parameter
to capture the global scale of variation of function $f$. Without loss of
generality, we assume that $m(x)=0$. Given a set of observations
$\mathcal{D}_{1:t}=\\{x_{i},y_{i}\\}_{i=1}^{t}$, the predictive distribution
can be derived as
$P(f_{t+1}|\mathcal{D}_{1:t},x)=\mathcal{N}(\mu_{t+1}(x),\omega^{2}\sigma_{t+1}^{2}(x))$,
where

$\mu_{t+1}(x)=k_{t}(x)^{T}[K_{t}+\lambda I]^{-1}y_{1:t},$
$\sigma_{t+1}^{2}(x)=k(x,x)-k_{t}(x)^{T}(K_{t}+\lambda I)^{-1}k_{t}(x),$

where we define $k_{t}(x)=[k(x,x_{1}),...,k(x,x_{t})]^{T}$,
$K_{t}=[k(x_{i},x_{j})]_{1\leq i,j\leq t}$, $y_{1:t}=[y_{1},\ldots,y_{t}]$ and
$\lambda$ as variance of the measurement noise.

We assume that kernel function $k$ is fixed and known and, without loss of
generation, the variance of $k$ is bounded as $k(x,x)\leq 1$. These
assumptions are similar as in (Srinivas et al., 2012; Chowdhury et al., 2017;
Janz et al., 2020). However, unlike these works, we do not require the
knowledge of the sub-Gaussianity parameter $R$ and upper bound $B$ on the RKHS
norm of $f$.

In our setting, we note that the parameters $\omega$ and $\lambda$ are
possibly time-dependent. They can be set specific to an algorithm as in many
previous works (e.g., (Bull, 2011), (Agrawal and Goyal, 2013), (Wang and de
Freitas, 2014), (Chowdhury et al., 2017)).

###  2.3 Expected Improvement

An acquisition function is used to suggest the point $x_{t+1}$ where the
function should be next evaluated. The acquisition step uses the predictive
mean and the predictive variance from the surrogate model to balance the
exploration of the search space and exploitation of current promising region.
Some examples of acquisition functions include GP-EI (Bull, 2011), GP-UCB
(Srinivas et al., 2012), GP-TS (Chowdhury et al., 2017), and entropy based
methods e.g., PES (Hernández-Lobato et al., 2014).

In the noisy case, the function is evaluated as $y_{t}=f(x_{t})+\epsilon_{t}$,
which is a noisy version of the function value at $x_{t}$. We assume that the
noise sequence $\\{\epsilon_{t}\\}_{t=1}^{\infty}$ is conditionally $R$-sub-
Gaussian for a fixed constant $R\geq 0$, i.e., $\forall t\geq
0,\forall\lambda\in\mathbb{R},\mathbb{E}[e^{\lambda\epsilon_{t}}|\mathcal{F}_{t-1}]\leq\text{exp}(\frac{\lambda^{2}R^{2}}{2})$,
where $\mathcal{F}_{t-1}$ is the $\sigma$-algebra generated by the random
variables. This is a mild assumption on the noise and is standard in the BO
literature (Chowdhury et al., 2017) and also in bandit literature (Abbasi-
yadkori et al., 2011).

We let $\mathcal{D}_{t}=\\{x_{1},...,x_{t}\\}$ denote the set of chosen points
to be evaluated up to iteration $t$. The noise in the evaluation of the
incumbent causes it to be brittle. A standard choice of the incumbent in this
setting is the best value of the GP mean function so far
$\mu^{+}_{t}=\text{max}\\{\mu_{t-1}(x_{i})\\}_{x_{i}\in\mathcal{D}_{t}}$. We
note that the maximization is only over the observed points, not the complete
input space $\mathcal{X}$. For this choice, EI is written in closed form as:

$\displaystyle\alpha_{t}^{EI}(x)$ $\displaystyle=$
$\displaystyle\mathbb{E}[\text{max}\\{0,f(x)-\mu^{+}_{t}\\}|\mathcal{D}_{t}]$
(3) $\displaystyle=$
$\displaystyle\rho(\mu_{t-1}(x)-\mu^{+}_{t},\omega\sigma_{t}(x)),$ (4)

where $\rho(u,v)$ with two arguments $u$ and $v$ is defined as

$\rho(u,v)=\begin{cases}u\Phi(\frac{u}{v})+v\phi(\frac{u}{v}),&\text{if
$v>0$},\\\ \text{max}\\{0,u\\},&\text{if $v=0$},\end{cases}$ (5)

and $\Phi$ and $\phi$ are the standard normal distribution and density
functions respectively.

##  3 Gaussian Process Expected Improvement (GP-EI) Algorithm

Algorithm 1 GP-EI Algorithm

Input: Prior $\text{GP}(0,k)$

1: for $t=1$ to $T$ do

2: Set $\omega_{t}=\sqrt{\gamma_{t-1}+1+\text{ln}(\frac{1}{\delta})}$

3: Choose the next sampling point:
$x_{t}=\text{argmax}_{x\in\mathcal{X}}\rho(\mu_{t-1}(x)-\mu_{t}^{+},\omega_{t}\sigma_{t-1}(x))$

4: Observe $y_{t}=f(x_{t})+\epsilon_{t}$

5: Update Gaussian process

6: end for

Output: Report points $x^{+}_{t}=\text{argmax}_{1\leq i\leq
t}\mu_{t-1}(x_{i})$ for all $1\leq t\leq T$

Our GP-EI algorithm is represented in Algorithm 1. The time-varying scale
parameter $\omega_{t}=\sqrt{\gamma_{t-1}+1+\text{ln}(1/\delta))}$ is used to
control the exploration of the algorithm for guaranteeing the convergence.
Here $\delta$ is a free parameter in $(0,1)$ and $\gamma_{t}$ is the maximum
information gain at time $t$ which is defined as
$\gamma_{t}=\text{max}_{A\in\mathcal{X}:|A|=t}I(y_{A};f_{A})$, where
$I(y_{A};f_{A})$ denotes the mutual information between $f_{A}=[f(x)]_{x\in
A}$ and $y_{A}=f_{A}+\epsilon_{A}$ and
$\epsilon_{A}\in\mathcal{N}(0,\lambda\omega^{2}_{t}I)$. The algorithm choose a
point $x_{t}=\text{argmax}_{x\in\mathcal{X}}\alpha_{t}^{EI}(x)$ which is
computed by Eq (5) to sample. After $T$ iterations, the algorithm returns
points $x^{+}_{t}=\text{argmax}_{1\leq i\leq t}\mu_{t-1}(x_{i})$ for every
$1\leq t\leq T$.

We note that the time-varying scale of variation of function $f$ has been
usually utilized by many previous works e.g. (Chowdhury et al., 2017) which
analyzes the GP-TS algorithm, (Agrawal and Goyal, 2013) which analyzes a
Thompson Sampling algorithm but for the contextual bandit problem, and (Wang
and de Freitas, 2014) which analyzes the EI algorithm. For example, in the
setting of (Chowdhury et al., 2017), they used a Gaussian process with mean 0
and variance $v^{2}_{t}k(.,.)$, where $v_{t}$ is a global scale parameter of
the variance which is allowed to vary with time. For their GP-Thompson
sampling, the time-varying scale parameter is set as
$v_{t}=B+R\sqrt{2(\gamma_{t-1}+1+\text{ln}(2/\delta))}$ (See section 3.2
therein).

##### Comparison with related algorithms.

Most of previous algorithms for Gaussian process bandit optimization such as
GP-UCB Srinivas et al. (2012), Improved-GP-UCB (Chowdhury et al., 2017),
$\pi$-GP-UCB (Janz et al., 2020), and GP-TS (Chowdhury et al., 2017) require
to know exactly the sub-Gaussianity parameter $R$ and upper bound $B$ on the
RKHS norm of $f$ so that theoretical convergence guarantees hold. However,
these parameters are often unknown in real applications. To overcome this
issue, as an example, Berkenkamp et al. (2019) proposed to learn unknown $B$
by starting from an initial guess $B_{0}$ and then scale up the norm bound
over time. As a result, $B$ is replaced by a time-varying function
$B_{0}b(t)g(t)^{d}$ in their Theorem 1, where functions $b(t)$ and $g(t)$ are
designed heuristically. As a result, this causes an additional
$\mathcal{O}(b(t)g(t)^{3d/2})$ factor in the regret. Unlike these algorithms,
our GP-EI algorithm can avoid the need to specify or learn such parameters.
This is because our algorithm uses
$\omega_{t}=\sqrt{\gamma_{t}+1+ln(\frac{1}{\delta})}$ which is independent of
$B$ and $R$.

###  3.1 Theoretical Result

Importantly, we achieve a cumulative regret bound for the proposed GP-EI
algorithm, denoted by $R_{T}=\sum_{t=1}^{T}(f(x^{*})-f(x^{+}_{t}))$ as
follows:

######  Theorem 1.

Pick $\delta\in(0,1)$. Then with probability at least $1-\delta$, the
cumulative regret of Algorithm 1 is bounded as:

$R_{T}=\mathcal{O}(\gamma_{T}\sqrt{T}).$

The complete form of $R_{T}=\mathcal{O}(\beta_{T}\sqrt{T\gamma_{T}})$, where
$\beta_{T}=B+R\sqrt{2(\gamma_{t-1}+1+\text{ln}(1/\delta))}$ is provided in
Supplementary Material. Here we remove the influence of constants $B,R$ for
simplicity. The regret bound of our GP-EI algorithm is same as that of
Improved-GP-UCB (Chowdhury et al., 2017) but improve GP-TS (Chowdhury et al.,
2017) by a factor $\sqrt{d\text{ln}(dT)}$. For SE kernels, $R_{T}$ is
sublinear on $T$. However, for Matérn kernels, this proposed algorithm still
has some limitations. First, its regret bound is not always sublinear in $T$.
Vakili et al. (2021) currently provides a new bound for $\gamma_{T}$ as
$\gamma_{T}=\tilde{\mathcal{O}}(T^{\frac{d}{2\nu+d}})$. By this, $2\nu>d$ is
required so that our proposed GP-EI algorithm obtains a sublinear regret.
Second,$\gamma_{t}$ of the proposed GP-EI algorithm grows quickly with $t$. In
practice, it can cause unnecessary explorations. These motivate us to propose
a new variant of the GP-EI algorithm in the next section.

###  3.2 The Improved-GP-EI Algorithm

In this section, we propose a new variant of GP-EI, called Improved-GP-EI,
inspired from the $\pi$-GP-UCB algorithm (Janz et al., 2020). Improved-GP-EI
uses a global scale $\omega_{T}=\sqrt{\text{ln}(T)\text{ln}\text{ln}(T)}$
growing only poly-logarithmically with $T$. Here we assume that $T$ is known
as in (Janz et al., 2020) and we use the same $\omega_{T}$ at all iterations
from 1 to $T$. Improved-GP-EI is an adaptation of $\pi$-GP-UCB algorithm (Janz
et al., 2020) to GP-EI. The key difference is that (1) our Improved GP-EI uses
EI acquisition function instead of UCB, and (2) Improved GP-EI use a new time-
varying scale (in $T$) parameter $\omega_{T}$ instead of a constant like (Janz
et al., 2020). Now we start to describe the underlying idea of Improved GP-EI.

##### Improved-GP-EI algorithm

At each iteration $t$, the algorithm constructs a cover (a set of hypercubes)
of domain $\mathcal{X}$, $\mathcal{A}_{t}$, and selects a point $x_{t}$ to be
evaluated in the next iteration by taking a maximizer of the GP-EI constructed
independently on each cover element. The cover $\mathcal{A}_{t}$ is
constructed by induction starting from the initial cover $\mathcal{A}_{1}$.
Similar to $\pi$-GP-UCB, we set $b=\frac{d+1}{d+2\nu}$ and
$q=\frac{d(d+1)}{d(d+2)+2\nu}$. For a hypercube $A\in\mathcal{X}$, we will use
$\rho_{A}$ to denote its diameter.

Let $\mathcal{A}_{1}$ be any set of closed hypercubes of cardinality at most
$\mathcal{O}(T^{q})$ overlapping at edges only and covering the domain
$\mathcal{X}$. At each iteration $t$, we build a GP, select the next point
$x_{t}$ and then construct a new cover $\mathcal{A}_{t+1}$ as below:

  * •

Update GP: Fit an independent GP on each cover element $A\in\mathcal{A}_{t}$,
_using only the data within $A$_. We define the subset of $\mathcal{D}_{t}$ in
$A$ as $\mathcal{D}^{A}_{t}=\\{x^{A}_{i}\in\mathcal{D}_{t}|x_{i}^{A}\in A\\}$.
For $\mathcal{D}^{A}_{t}$ of cardinality $N$, we define the kernel $k$ as
$k^{A}_{t}=[k(x^{A}_{1},x),...,k(x^{A}_{N},x)]^{T}$ and the kernel matrix as
$K^{A}_{t}=[k(x,x^{\prime})]_{x,x^{\prime}\in\mathcal{D}^{A}_{t}}$. We use
$y^{A}_{1:t}$ to denote the observations corresponding to points in
$\mathcal{D}^{A}_{t}$. For a regularisation parameter $\lambda>0$, we define
the Gaussian process on $A\in\mathcal{X}$ by mean,

$\mu_{t}^{A}=k_{t}^{A}(x)(K^{A}_{t}+\lambda I)^{-1}y^{A}_{1:t},$

and predictive standard deviation,

$\sigma^{A}_{t}(x)=\sqrt{k(x,x)-k_{t}^{A}(x^{T}(K_{t}^{A}+\lambda
I)^{-1})k_{t}^{A}(x)}.$

  * •

Next point selection: We select the next point to evaluate as
$x_{t}=\text{argmax}_{A\in\mathcal{A}_{t}:x\in
A}\alpha_{t}^{EI}=\text{argmax}_{A\in\mathcal{A}_{t}:x\in
A}\rho(\mu_{t-1}(x)-\mu^{A+}_{t-1},\omega_{T}\sigma^{A}_{t-1}(x)),$ where
$\mu^{A+}_{t-1}$ is defined as $\mu^{A+}_{t-1}=\text{max}_{x_{i}\in
A\cap\mathcal{D}_{t-1}}\mu^{A}_{t-1}(x_{i})$, and function $\rho$ is defined
by Eq(5).

  * •

Build $\mathcal{A}_{t+1}$: Split any element $A\in\mathcal{A}_{t}$ for which
$\rho_{A}^{-1/b}<|\mathcal{D}^{A}_{t+1}|+1$ along the middle of each side,
resulting in $2^{d}$ new hypercubes. Let $\mathcal{A}_{t+1}$ be the set of the
newly created hypercubes and the elements of $\mathcal{A}_{t}$ that were not
split. (See (Janz et al., 2020) for details.)

We now present the regret bound for our Improved GP-EI algorithm.

######  Theorem 2.

Pick $\delta\in(0,1)$. Let $H_{k}(\mathcal{X})$ be the RKHS of a Matérn kernel
$k$ with parameter $\nu>1$. Then with probability at least $1-\delta$, the
cumulative regret of Improved GP-EI has the following rate:

$R_{T}=\tilde{\mathcal{O}}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}}).$

The regret bound of Improved GP-EI is sublinear in $T$ for every $\nu>1$, thus
improves over that of our above proposed GP-EI algorithm. Furthermore, we use
$\omega_{T}=\sqrt{\text{ln}(T)\text{ln}\text{ln}(T)}$ which grows only poly-
logarithmically with $T$. This property is useful in practice as it avoids
unnecessary explorations. Finally, we note that our Improved GP-EI achieves
the same regret rate as $\pi$-GP-UCB (Janz et al., 2020) on the regret,
however it does not require to know parameters $B,R$ like the work of Janz et
al. (2020).

###  3.3 Proof Sketch for Theorem 1

In this section, we provide the proof sketch for Theorem 1. A complete proof
of Theorem 1 is provided in Appendix B. To bound the cumulative regret
$R_{T}$, we proceed to bound instantaneous regrets
$r_{t}=f(x^{*})-f(x_{t}^{+})$. The proof involves two steps as follows.

##### Upper bounding the instantaneous regret $r_{t}=f(x^{*})-f(x_{t}^{+})$:

We break down $r_{t}$ into two terms as follows:

$\displaystyle
r_{t}=f(x^{*})-f(x_{t}^{+})=\underbrace{f(x^{*})-\mu^{+}_{t}}_{\text{Term
1}}+\underbrace{\mu_{t}^{+}-f(x_{t}^{+})}_{\text{Term 2}}$

Set $I_{t}=\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}$. We upper bound Term 1
through the following lemma:

######  Lemma 1.

Pick $\delta\in(0,1)$. Then with probability at least $1-\delta$ we have

$f(x^{*})-\mu_{t}^{+}\leq\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}(I_{t}+(\beta_{t}+\omega_{t})\sigma_{t}(x_{t+1})),$

where given any $z\in\mathbb{R}$, the function $\tau(z)$ is defined as
$\tau(z)=z\Phi(z)+\phi(z)$, where $\Phi$ and $\phi$ are the standard normal
distribution and density functions respectively.

We upper bound Term 2 through the following lemma:

######  Lemma 2.

Pick a $\delta\in(0,1)$. Then with probability $1-\delta$ we have

$\mu_{t}^{+}-f(x^{+}_{t})\leq\frac{\beta_{t}}{\omega_{t}}(\sqrt{2\pi}(\beta_{t}+\omega_{t})\sigma_{t}(x_{t+1})+\sqrt{2\pi}I_{t}).$

By using $\omega_{t}=\sqrt{\gamma_{t-1}+1+ln(\frac{1}{\delta})}$, we obtain
$\frac{\beta_{t}}{\omega_{t}}\leq B+\sqrt{2}$ and there exists a constant
$C>0$ such that
$\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}\leq
C$ for every $t$. Combining these results, we obtain an upper bound for the
regret $r_{t}$ as $r_{t}\leq(B+C+2)(I_{t}+2\beta_{t}\sigma_{t}(x_{t+1}))$,
where $C>0$ is constant.

To achieve Lemma 1, we adapt several results of (Bull, 2011) in noise-free
setting to our the noisy setting, and to achieve Lemma 2, we exploit
additionally properties of the function $\tau(z)$ and the points
$x^{+}_{t}=\text{argmax}_{1\leq i\leq t}\mu_{t-1}(x_{i})$. We note that in the
noise-free setting, we can use $\xi=f^{+}$ as the incumbent in the form of the
expected improvement $\alpha^{EI}(x)=\mathbb{E}[\text{max}\\{0,f(x)-\xi\\}]$,
where $f^{+}_{t}$ is the current best observed function value so far. In the
noisy setting, the function values can not observed due to noises. Using
$\xi=\mu^{+}_{t}$ as a replacement allows to compute easily the incumbent but
also causes the difficulty in the theoretical analysis. While Bull (2011)
leverages the _monotonicity_ of $f^{+}_{t}=\text{max}_{1\leq i\leq t}f(x_{i})$
to derive directly an upper bound for the regret $r_{t}$, this is very
challenging in our setting because the values $\mu^{+}_{i}$ with $1\leq i\leq
t$ have no monotonicity property. To overcome this, we seek to upper bound the
sum of $\sum_{t=1}^{T}r_{t}$. We obtain
$\sum_{t=1}^{T}r_{t}\leq(C+B+2)(\sum_{t=1}^{T}I_{t}+\sum_{t=0}^{T-1}\beta_{t}\sigma_{t}(x_{t+1}))$.

While upper bounding $\sum_{t=0}^{T-1}\sigma_{t}(x_{t+1})$ can be achieved via
the maximum information gain like previous works in the noisy setting
(Srinivas et al., 2012; Chowdhury et al., 2017), upper bounding the sum
$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}$ is the _key
challenge_ in our regret analysis. We overcome this difficulty by exploiting
the _monotonicity of variance functions_ (Vivarelli, 1998) which shows that
$\sigma_{t}(x)\geq\sigma_{t^{\prime}}(x)$ if $t\leq t^{\prime}$. To our
knowledge, we exploit for the first time this property for Gaussian process
bandit optimization problem.

We achieve an upper bound for
$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}$ as in the following
important lemma.

######  Lemma 3.

Pick a $\delta\in(0,1)$. Then with probability at least $1-\delta$ we have
that

$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}\leq\mathcal{O}(\beta_{T}\sqrt{T\gamma_{T}}),$

where $\beta_{T}=B+R\sqrt{2(\gamma_{T-1}+1+ln(1/\delta))}$.

To prove this lemma, we need two auxiliary lemmas from the literature.

######  Lemma 4 (Theorem 2 of Chowdhury et al. (2017)).

Pick $\delta\in(0,1)$. We define
$\beta_{t}=B+R\sqrt{2(\gamma_{t-1}+1+ln(1/\delta))}$ for every $1\leq t\leq
T$. Then $\mathbb{P}(\forall 1\leq t\leq T,\forall
x\in\mathcal{X},|f(x)-\mu_{t-1}(x)|\leq\beta_{t}\sigma_{t-1}(x))\geq
1-\delta$.

######  Lemma 5 (Lemma 5 of De Freitas et al. (2012)).

When $f\in H_{k}(\mathcal{X})$, then for every $x,y\in\mathcal{X}$, we have
$|f(x)-f(y)|\leq BL||x-y||_{1}$, where $L$ is the Lipschitz constant in
$H_{k}(\mathcal{X})$.

##### Proof of Lemma 3

Set $S_{T}=\sum_{t=0}^{T-1}I_{t}$. There are three cases to be considered:

##### Case 1

$S_{T}=0$. This happens when for every $t$: $f(x_{t+1})-\mu_{t}^{+}\leq 0$.

##### Case 2

There exists an unique index $1\leq t^{\prime}\leq T$ such that
$f(x_{t^{\prime}+1})-\mu_{t}^{\prime+}>0$. It follows that
$S_{T}=f(x_{t^{\prime}+1})-\mu_{t}^{\prime+}$. In this case, we have that

$\displaystyle S_{T}$ $\displaystyle=$ $\displaystyle
f(x_{t^{\prime}+1})-\mu_{t}^{\prime+}$ $\displaystyle\leq$ $\displaystyle
f(x_{t^{\prime}+1})-(f(x^{\prime})-\beta_{t^{\prime}+1}\sigma_{t^{\prime}}(x^{\prime}))$
$\displaystyle\leq$ $\displaystyle
f(x_{t^{\prime}+1})-f(x^{\prime})+\beta_{t^{\prime}+1}\sigma_{t^{\prime}}(x^{\prime})$
$\displaystyle\leq$ $\displaystyle
BL||x_{t^{\prime}+1}-x^{\prime}||_{1}+\beta_{t^{\prime}+1}$ $\displaystyle=$
$\displaystyle\mathcal{O}(\beta_{T}),$

where in the last inequality, we use Lemma 5, the inequality
$\beta_{t^{\prime}+1}\leq\beta_{T}$, and the fact that
$\sigma_{t}^{\prime}(x)\leq 1$. Finally, because the domain $\mathcal{X}$ is
bounded, $||x_{t^{\prime}+1}-x^{\prime}||_{1}$ is bounded.

##### Case 3

There are $0\leq t_{1}<t_{2},...,<t_{l}\leq T-1$ where $l\geq 2$ such that
$f(x_{t_{i}+1})\geq\mu_{t_{i}}^{+}$. Thus, we have

$\displaystyle\sum_{t=0}^{T-1}I_{t}$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{l}(f(x_{t_{i}+1})-\mu_{t_{i}}^{+})$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{l}(\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i}+1})+\mu_{t_{i}}(x_{t_{i}+1})-\mu_{t_{i}}^{+})$
$\displaystyle\leq$
$\displaystyle\underbrace{\sum_{i=1}^{l}\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i}+1})}_{\text{Term
5}}+\underbrace{\sum_{i=1}^{l}(\mu_{t_{i}}(x_{t_{i}+1})-\mu_{t_{i}}^{+})}_{\text{Term
6}}$

##### Bound Term 5

$\displaystyle\sum_{i=1}^{l}\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i}+1})$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{T-1}\beta_{t+1}\sigma_{t}(x_{t+1})$
$\displaystyle\leq$
$\displaystyle\beta_{T}\sum_{t=0}^{T-1}\sigma_{t}(x_{t+1})$

##### Bound Term 6

Set $M_{1}=\sum_{i=1}^{l}(\mu_{t_{i}}(x_{t_{i}+1})-\mu_{t_{i}}^{+})$.

$\displaystyle M_{1}$
$\displaystyle=\mu_{t_{l}}(x_{t_{l}+1})-\mu_{t_{1}}^{+}+\sum_{i=1}^{l-1}(\mu_{t_{i-1}}(x_{t_{i-1}+1})-\mu_{t_{i}}^{+}))$
$\displaystyle\leq$
$\displaystyle\underbrace{\mu_{t_{l}}(x_{t_{l}})-\mu_{t_{1}}^{+}}_{\text{Term
7}}+\underbrace{\sum_{i=1}^{l-1}(\mu_{t_{i-1}}(x_{t_{i-1}+1})-\mu_{t_{i}}(x_{t_{i-1}+1})))}_{\text{Term
8}}$

##### Bound Term 7

Set $M_{2}=\mu_{t_{l}}(x_{t_{l}+1})-\mu_{t_{1}}^{+}$. We have

$\displaystyle M_{2}$ $\displaystyle\leq$ $\displaystyle
f(x_{t_{l}+1})+\beta_{t_{l}+1}\sigma_{t_{l}}(x_{t_{l}+1})-(f(x_{t_{1}}-\beta_{t_{1}}\sigma_{t_{1}}(x_{t_{1}})))$
$\displaystyle\leq$ $\displaystyle
f(x_{t_{l}+1})-f(x_{t_{1}})+\beta_{t_{l}+1}\sigma_{t_{l}}(x_{t_{l}+1})+\beta_{t_{1}+1}\sigma_{t_{1}}(x_{t_{1}}))$
$\displaystyle\leq$ $\displaystyle
f(x_{t_{l}+1})-f(x_{t_{1}})+\beta_{t_{l}+1}+\beta_{t_{1}}$ $\displaystyle\leq$
$\displaystyle BL||x_{t_{l}+1}-x_{t_{1}}||_{1}+2\beta_{T}$ $\displaystyle\leq$
$\displaystyle\mathcal{O}(\beta_{T})$

The argument to achieve the bound for Term 7 is similar to Case 2.

##### Bound Term 8

Set
$M_{3}=\sum_{i=1}^{l-1}(\mu_{t_{i-1}}(x_{t_{i-1}+1})-\mu_{t_{i}}(x_{t_{i-1}+1})))$
for simplicity. We go to bound $M$.

$\displaystyle M_{3}$
$\displaystyle\leq\sum_{i=1}^{l-1}(f(x_{t_{i-1}+1})+\beta_{t_{i-1}+1}\sigma_{t_{i-1}}(x_{t_{i-1}+1}))$
$\displaystyle-(f(x_{t_{i-1}+1})-\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i-1}+1}))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{l-1}\beta_{t_{i-1}+1}\sigma_{t_{i-1}}(x_{t_{i-1}+1})+\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i-1}+1})$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{l-1}(\beta_{t_{i-1}+1}+\beta_{t_{i}+1})\sigma_{t_{i-1}}(x_{t_{i-1}+1})$
$\displaystyle\leq$ $\displaystyle
2\beta_{T}\sum_{i=1}^{l-1}\sigma_{t_{i-1}}(x_{t_{i-1}+1})$ $\displaystyle\leq$
$\displaystyle 2\beta_{T}\sum_{i=0}^{T-1}\sigma_{i}(x_{i+1}),$

where in the first inequality, we use Lemma 4:
$\mu_{t_{i-1}}(x_{t_{i-1}+1})\leq
f(x_{t_{i-1}+1})+\beta_{t_{i-1}}\sigma_{t_{i-1}}(x_{t_{i-1}+1})$;
$\mu_{t_{i}}(x_{t_{i-1}+1})\geq
f(x_{t_{i}+1})-\beta_{t_{i}}\sigma_{t_{i}}(x_{t_{i-1}+1})$. In the second
inequality, we use the fact that $f(x_{t_{i-1}+1})\leq f(x_{t_{i}+1})$. In the
third inequality, we use the _decreasing monotonicity of variance functions_
((Vivarelli, 1998) and (Chowdhury et al., 2017), see Section F). Here, we use

$\sigma_{t_{i}}(x_{t_{i-1}+1})\leq\sigma_{t_{i-1}}(x_{t_{i-1}+1}),$

because $T-1\geq t_{i}>t_{i-1}\geq 0$ due to the definition of $t_{i}$ and
$t_{i-1}$. This step is crucial to bound $M_{3}$. Without this step, $M_{3}$
may be bounded by two sums: $\sum^{l-1}_{i=1}\sigma_{t_{i-1}}(x_{t_{i-1}+1}))$
and $\sum^{l-1}_{i=1}\sigma_{t_{i}}(x_{t_{i-1}+1}))$. While the first term can
be bounded in terms of the information gain, bounding the second is
challenging, and was what led to an error in Lemma 7 of Nguyen et al. (2017).

For every $x_{i}$, where $1\leq i\leq T-1$, Lemma 4 holds with probability
$1-\delta$. Therefore, Lemma 4 holds with probability at least $1-\delta$ for
all $x_{i}$, where $1\leq i\leq T-1$. Combining Term 5, Term 7, Term 8, with
probability $1-T\delta$ we have

$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}\leq\mathcal{O}(\beta_{T}\sum_{i=1}^{T-1}\sigma_{i}(x_{i+1})).$

On the other hand, following Lemma 4 of Chowdhury et al. (2017), we have
$\sum_{i=1}^{T-1}\sigma_{i}(x_{i+1})\leq\sqrt{4(T+2)\gamma_{T}}$. Thus,

$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}=\mathcal{O}(\beta_{T}\sqrt{T\gamma_{T}}).$

Thus, for all cases, Lemma 3 holds.

###  3.4 Proof Sketch for Theorem 2

Theorem 2 holds using a non-trivial combination of the proof techniques as
above and the technical results for $\pi$-GP-UCB Janz et al. (2020). A
complete proof of Theorem 2 is provided in Appendix C of the Supplementary
Material.

##  4 Related works

Figure 1: Comparison of methods for Hartmann3, Shekel, Hartmann6 and Ackley
functions.

A recent review of GP-EI can be found in (Zhan and Xing, 2020).

In the noise-free setting, the most notable work in this sub-line is the one
of Bull (2011) which showed that GP-EI can obtain an $\mathcal{O}(T^{-1/d})$
upper bound on the simple regret.

In noisy setting, Srinivas et al. (2012) first introduced GP-UCB for both
Bayesian and non-Bayesian settings. Valko et al. (2013) introduced KernelUCB
for the case of a finite-armed bandit which can be extended to a continuum-
armed bandit via a discretization argument. Another notable work for GP-UCB is
Improved GP-UCB (Chowdhury et al., 2017), which offers a slightly faster
convergence rate. A limitation of these algorithms is that the proposed
regrets are sublinear only if $2\nu>d(d+1)$. To address this limitation, (Janz
et al., 2020) recently introduced $\pi$-GP-UCB which is built upon Improved
GP-UCB with guarantees that $\pi$ GP-UCB has a sublinear regret for every
$\nu>1$ and $d\geq 1$. GP-TS is another approach for Gaussian process bandit
optimization. This was introduced by Chowdhury et al. (2017) by extending the
Thompson sampling algorithm in finite-armed bandits to continuum-armed
bandits. Scarlett et al. (2017) provided lower bounds for Gaussian process
bandit optimization for both simple and cumulative regret. Recently Vivarelli
(1998) provided new upper bounds for GP-UCB and GP-TS as well as the new
bounds for the maximum information gain $\gamma_{t}$.

A limitation of GP-UCB and GP-TS algorithms is that the explorations are
maintained via an upper confidence bound which requires to know several
parameters e.g. the bound on the function RKHS norm, sub-Gaussianity level of
the measurement noise. These parameters are usually unknown in practice.
Consequently, these parameters are often set in a heuristic manner (Berkenkamp
et al., 2017; Bogunovic et al., 2018; Janz et al., 2020; Wachi and Sui, 2020).
Our GP-EI based algorithms avoid this limitation.

EI has also been studied in finite-armed bandit setting. Ryz (2016) studied EI
for the problem of best-arm identification. Later, Qin et al. (2017) proposed
an improvement of this algorithm on computational efficiency. However, these
results and analysis techniques do not apply to our settings of Gaussian
processes and the RKHS norm.

##  5 Experiments

While the main focus of this paper is performing theoretical analysis for GP-
EI in noiseless and noisy settings, we have also proposed a new algorithm
termed as “Improved-GP-EI” and also provided a variant of GP-EI which we will
call Modified-GP-EI in noisy setting. In this section we have performed a
comparison of our Improved-GP-EI as well as Modified-GP-EI against GP-EI with
fixed $\omega$ and $\pi$-GP-UCB proposed by Janz et al. (2020), which has the
tightest regret so far in the noisy setting. To compare the sample-efficiency
of all the algorithms, we used four functions in noisy setting: Hartmann3
($d=3$), Shekel ($d=4$), Hartmann6 ($d=6$) and Ackley ($d=10$). The evaluation
metric is the log distance to the true optimum:
$\text{log}_{10}(f(x^{*})-f(x^{+}_{t}))$.

All implementations are in Python 3.6. For each test function, we repeat the
experiments 15 times. We plot the mean and a confidence bound of one standard
deviation across all the runs. We used Matérn kernel with $\nu=2.5$ and the
length scale $l=0.2$. Set $T=100$, and $\delta=0.05$. $\omega_{T}$ of
Modified-GP-EI and Improved-GP-EI is set following Theorem 1 and Theorem 2.
For GP-EI, we use $\omega=1$ by default.

As seen from Figure 1, the Modified-GP-EI performs similar to GP-EI. This is
expected as both methods only differ by $\omega_{T}$ , which is used for
theoretical guarantee. $\pi$-GP-UCB is the most inefficient (except Shekel),
probably because it requires to know the RKHS norm and sub-Gaussianity
parameters which are unknown in practice. Following (Janz et al., 2020), we
used $B=1$, $R=1$. In contrast, Improved-GP-EI does not need to know such
hyper-parameters and clearly outperforms $\pi$-GP-UCB.

We note that our Improved-GP-EI results in a significantly more scalable
algorithm. The cover construction (i.e. partitioning the space) of Improved-
GP-EI permits it to perform the inverse of the kernel $K_{t}$ on a subset of
the data to reduce the computations from $O(t^{3})$ to
$O(\sum_{i=1}^{p}t^{3}_{i})$ where $t=\sum_{i=1}^{p}t_{i}$ and $p$ is the
number of hypercubes in the partition. E.g. for Hartmann3, the average runtime
per iteration of Improved-GP-EI is 1.21 mins compared to GP-EI’s 1.37 min.
This difference gets larger for larger horizons.

###  5.1 Synthetic Test Functions

In this part, we benchmark on synthetic functions in RKHS spaces. The first
function is built in the RKHS space equipped with a Matérn kernel with
$\nu=2.5$ and $l=0.2$. The second function is built in the RKHS space equipped
with a SE kernel with $l=1$. We construct each function $f$ in a five-
dimensional space by sampling 500 points $\hat{x}_{1},..,\hat{x}_{m}$,
uniformly on $[0,1]^{5}$, and $\hat{a}_{1},..,\hat{a}_{m}$ each independent
uniform on $[-1,1]$ and defining
$f(x)=\sum_{i=1}^{m}\hat{a}_{i}k(\hat{x}_{i},x)$ for all $x\in\mathcal{X}$ and
$k$ is a kernel. The RKHS norm of this function is computed as
$||f||^{2}_{k}=\sum_{i,j=1}^{\infty}\hat{a}_{i}\hat{a}_{j}k(\hat{x}_{j},\hat{x}_{i})$.
This norm is unknown for all the algorithms. Since the baseline $\pi$-GP-UCB
requires to know this norm and the sub-Gaussianity parameter $R$, we set $B=1$
and $R=1$ (in a heuristic manner) for $\pi$-GP-UCB. Otherwise, our proposed
Improved-GP-EI algorithm as well as Modified-GP-EI and GP-EI do not require to
know these parameters. We used $\lambda=0.01$ for the noise setting.

Figure 2: Comparison of methods for the functions generated from the RKHS
space. The left corresponds to the Matérn kernel ($\nu=2.5$, $l=0.2$). The
right corresponds to the Squared Exponential (SE) kernel ($l=1.0$). The SE
kernel is considered as a special case of the Matérn kernel. We estimate the
algorithms based on the function values at each iteration.

As seen from Figure 2, for both the Matérn kernel and the SE kernel, Improved-
GP-EI outperforms all the other algorithms while Modified-GP-EI and GP-EI show
competitive performance. Improved-GP-EI performs better than Modified-GP-EI
because it avoids using a large global scale variance parameter $\omega_{T}$.
Improved-GP-EI uses $\omega_{T}$ growing only poly-logarithmically with $T$.
$\pi$-GP-UCB is outperformed by the EI based algorithms which are parameter-
free. This is also observed in (Chowdhury et al., 2017). We agree with
Chowdhury et al. (2017) that the UCB-based algorithms are somewhat less robust
on the choice of kernel than EI-based algorithms.

##  6 Conclusion

We have demonstrated that GP-EI can converge with standard incumbent defined
as the current best value of the GP predictive mean. Further we have proposed
a variant of GP-EI, called Improved GP-EI which converges for every $\nu>1$
and every $d\geq 1$. The empirical results have demonstrated the effectiveness
of our proposed Improved GP-EI.

#### Acknowledgements

This research was partially funded by the Australian Government through the
Australian Research Council (ARC). Prof Venkatesh is the recipient of an ARC
Australian Laureate Fellowship (FL170100006).

## References

  * Ryz (2016) On the convergence rates of expected improvement methods.  _Operations Research_ , 64(6):1515–1528, 2016\.  Winner, INFORMS Simulation Society Outstanding Publication Award, 2017\.
  * Abbasi-yadkori et al. (2011) Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24, pages 2312–2320. Curran Associates, Inc., 2011.  URL https://proceedings.neurips.cc/paper/2011/file/e1d5be1c7f2f456670de3d53c7b54f4a-Paper.pdf.
  * Agrawal and Goyal (2013) Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In Sanjoy Dasgupta and David McAllester, editors, _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pages 127–135, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * Balakrishnan et al. (2020) Sreejith Balakrishnan, Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Harold Soh.  Efficient exploration of reward functions in inverse reinforcement learning via bayesian optimization, 2020.
  * Bergstra et al. (2011) James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl.  Algorithms for hyper-parameter optimization.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24, pages 2546–2554. Curran Associates, Inc., 2011.  URL https://proceedings.neurips.cc/paper/2011/file/86e8f7ab32cfd12577bc2619bc635690-Paper.pdf.
  * Berkenkamp et al. (2017) Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause.  Safe model-based reinforcement learning with stability guarantees.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30, pages 908–918. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/file/766ebcd59621e305170616ba3d3dac32-Paper.pdf.
  * Berkenkamp et al. (2019) Felix Berkenkamp, Angela P. Schoellig, and Andreas Krause.  No-regret bayesian optimization with unknown hyperparameters.  _Journal of Machine Learning Research_ , 20(50):1–24, 2019.
  * Bogunovic et al. (2018) Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher.  Adversarially robust optimization with gaussian processes.  NIPS’18, page 5765–5775, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Bull (2011) Adam D. Bull.  Convergence rates of efficient global optimization algorithms.  _J. Mach. Learn. Res._ , 12:2879–2904, November 2011.  ISSN 1532-4435.
  * Chowdhury et al. (2017) Sayak Ray Chowdhury, Aditya Gopalan, and abc.  On kernelized multi-armed bandits.  ICML’17, page 844–853. JMLR.org, 2017.
  * De Freitas et al. (2012) Nando De Freitas, Alex J. Smola, and Masrour Zoghi.  Exponential regret bounds for gaussian process bandits with deterministic observations.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , ICML’12, page 955–962, Madison, WI, USA, 2012. Omnipress.  ISBN 9781450312851.
  * Hernández-Lobato et al. (2014) José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani.  Predictive entropy search for efficient global optimization of black-box functions.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.
  * Hoffman et al. (2014) Matthew Hoffman, Bobak Shahriari, and Nando Freitas.  On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning.  In Samuel Kaski and Jukka Corander, editors, _Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics_ , volume 33 of _Proceedings of Machine Learning Research_ , pages 365–374, Reykjavik, Iceland, 22–25 Apr 2014. PMLR.  URL http://proceedings.mlr.press/v33/hoffman14.html.
  * Janz et al. (2020) David Janz, David Burt, and Javier Gonzalez.  Bandit optimisation of functions in the matérn kernel rkhs.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 2486–2495. PMLR, 26–28 Aug 2020.
  * Lizotte et al. (2007) Daniel Lizotte, Tao Wang, Michael Bowling, and Dale Schuurmans.  Automatic gait optimization with gaussian process regression.  IJCAI’07, page 944–949, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
  * Malkomes and Garnett (2018) Gustavo Malkomes and Roman Garnett.  Automating bayesian optimization with bayesian optimization.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/2b64c2f19d868305aa8bbc2d72902cc5-Paper.pdf.
  * Marchant and Ramos (2012) R. Marchant and F. Ramos.  Bayesian optimisation for intelligent environmental monitoring.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 2242–2249, 2012.  doi: 10.1109/IROS.2012.6385653.
  * Martinez-cantin et al. (2007) Ruben Martinez-cantin, Nando de Freitas, Arnaud Doucet, and José A. Castellanos.  Active policy learning for robot planning and exploration under uncertainty.  In _IN PROCEEDINGS OF ROBOTICS: SCIENCE AND SYSTEMS_ , 2007.
  * Močkus (1975) J. Močkus.  On bayesian methods for seeking the extremum.  In G. I. Marchuk, editor, _Optimization Techniques IFIP Technical Conference Novosibirsk, July 1–7, 1974_ , pages 400–404, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.  ISBN 978-3-540-37497-8.
  * Nguyen and Osborne (2020) Vu Nguyen and Michael A. Osborne.  Knowing the what but not the where in Bayesian optimization.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7317–7326. PMLR, 13–18 Jul 2020.
  * Nguyen et al. (2017) Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh.  Regret for expected improvement over the best-observed value and stopping condition.  In Min-Ling Zhang and Yung-Kyun Noh, editors, _Proceedings of the Ninth Asian Conference on Machine Learning_ , volume 77 of _Proceedings of Machine Learning Research_ , pages 279–294. PMLR, 15–17 Nov 2017.
  * Osborne (2010) Michael A. Osborne.  Bayesian gaussian processes for sequential prediction, optimisation and quadrature.  2010\.
  * Qin et al. (2017) Chao Qin, Diego Klabjan, and Daniel Russo.  Improving the expected improvement algorithm.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 5387–5397, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Rasmussen and Williams (2005) Carl Edward Rasmussen and Christopher K. I. Williams.  _Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning)_.  The MIT Press, 2005.  ISBN 026218253X.
  * Scarlett et al. (2017) Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher.  Lower bounds on regret for noisy Gaussian process bandit optimization.  In Satyen Kale and Ohad Shamir, editors, _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pages 1723–1742, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR.
  * Snoek et al. (2012) Jasper Snoek, Hugo Larochelle, and Ryan P. Adams.  Practical bayesian optimization of machine learning algorithms.  In _Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’12, page 2951–2959, Red Hook, NY, USA, 2012. Curran Associates Inc.
  * Srinivas et al. (2012) Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger.  Information-theoretic regret bounds for gaussian process optimization in the bandit setting.  _IEEE Trans. Inf. Theor._ , 58(5):3250–3265, May 2012.  ISSN 0018-9448.  doi: 10.1109/TIT.2011.2182033.  URL http://dx.doi.org/10.1109/TIT.2011.2182033.
  * Stein (1999) Michael L. Stein.  _Interpolation of spatial data_.  Springer Series in Statistics. Springer-Verlag, New York, 1999.  ISBN 0-387-98629-4.  doi: 10.1007/978-1-4612-1494-6.  URL http://dx.doi.org/10.1007/978-1-4612-1494-6.  Some theory for Kriging.
  * Tran-The et al. (2020) Hung Tran-The, Sunil Gupta, Santu Rana, Huong Ha, and Svetha Venkatesh.  Sub-linear regret bounds for bayesian optimisation in unknown search spaces.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 16271–16281. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/bb073f2855d769be5bf191f6378f7150-Paper.pdf.
  * Tran-The et al. (2021) Hung Tran-The, Sunil Gupta, Santu Rana, and Svetha Venkatesh.  Bayesian optimistic optimisation with exponentially decaying regret.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 10390–10400. PMLR, 18–24 Jul 2021.
  * Vakili et al. (2021) Sattar Vakili, Kia Khezeli, and Victor Picheny.  On information gain and regret bounds in gaussian process bandits.  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 82–90. PMLR, 13–15 Apr 2021.
  * Valko et al. (2013) Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini.  Finite-time analysis of kernelised contextual bandits.  In _Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence_ , UAI’13, page 654–663, Arlington, Virginia, USA, 2013\. AUAI Press.
  * Vivarelli (1998) Francesco Vivarelli.  Studies on the generalisation of gaussian processes and bayesian neural networks.  In _PhD thesis_. Aston University, 1998.
  * Wachi and Sui (2020) Akifumi Wachi and Yanan Sui.  Safe reinforcement learning in constrained Markov decision processes.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 9797–9806, Virtual, 13–18 Jul 2020. PMLR.
  * Wang and de Freitas (2014) Ziyu Wang and Nando de Freitas.  Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters, 2014.
  * Wilson et al. (2014) Aaron Wilson, Alan Fern, and Prasad Tadepalli.  Using trajectory data to improve bayesian optimization for reinforcement learning.  _Journal of Machine Learning Research_ , 15(8):253–282, 2014.  URL http://jmlr.org/papers/v15/wilson14a.html.
  * Zhan and Xing (2020) Dawei Zhan and Huanlai Xing.  Expected improvement for expensive optimization: a review.  _J. Glob. Optim._ , 78(3):507–544, 2020.  doi: 10.1007/s10898-020-00923-x.  URL https://doi.org/10.1007/s10898-020-00923-x.

Supplementary Material:
Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit
Optimization

Before providing the theoretical results and the additional experiments, we
summarize some important notations used in our proofs in Table 2 and in
section A we first explain the derivation of the EI acquisition function in
Section 2.3. Next, in Section B and C we provide the proof for Theorem 1 and
Theorem 2 in the main paper, respectively.

Table 1: A summary of the notations used in the paper.

Common | Definition
---|---
$d$ | the number of dimensions of the search space $\mathcal{X}$
$x^{*}$ |  $\text{argmax}_{x\in\mathcal{X}}f(x)$, an optimal
$B$ | the upper bound of the RKHS norm
$R$ | the sub-Gaussianity parameter of the noise
$\nu$ | the parameter controlling the smoothness of the function
$l$ | the lengthscale of the kernel
$\alpha_{t}^{EI}(x)$ | the EI acquisition function at iteration $t$
$\xi$ | the incumbent of EI
$\Phi(z)$ | the standard normal distribution function
$\phi(z)$ | the density function
$\tau(z)$ |  $z\Phi(z)+\phi(z)$ which is a increasing function
Section B |
$\omega_{t}$ | the replacement of $\omega$ in the noisy setting
$x_{t}^{+}$ | $x^{+}_{t}=\text{argmax}\\{\mu_{t-1}(x_{i})\\}_{x_{i}\in\mathcal{D}_{t-1}}$
$\mu_{t}^{+}$ | the best GP predictive mean, $\mu^{+}_{t}=\text{max}\\{\mu_{t-1}(x_{i})\\}_{x_{i}\in\mathcal{D}_{t}}$
$\gamma_{t}$ | the maximum information gain up to $t$ iterations
Section C |
$b$ | the constant defined as $b=\frac{d+1}{d+2\nu}$
$q$ | the constant defined as $q=\frac{d(d+1)}{d(d+2)+2\nu}$
$\rho_{A}$ | the diameter of the hypercube $A$
$\mathcal{D}_{t}^{A}$ | the subset of $\mathcal{D}_{t}$ in $A$
$K_{t}^{A}$ | the kernel matrix, defined as $K_{t}^{A}=[k(x,x^{\prime})]_{x,x^{\prime}\in\mathcal{D}_{t}^{A}}$
$\gamma_{t}^{A}$ | the information gain for $A$, defined as $\gamma_{t}^{A}=\frac{1}{2}\text{log}|I+\lambda^{-1}K_{t}^{A}|$ (See (Janz et al., 2020))
$\mathcal{A}_{t}$ | the set of the newly created hypercubes at iteration $t$ and the hypercubes of $\mathcal{A}_{t-1}$ that were not split

##  Appendix A Derivation of the Expected Improvement in Section 2.3.

Set $I_{t}(x)=\text{max}\\{0,f(x)-\mu^{+}_{t}\\}$. $I_{t}(x)$ is positive when
the prediction is higher than the best value known thus far. Otherwise,
$I_{t}(x)$ is set to zero. The new query point is found by maximizing the
expected improvement:

$x=\text{argmax}_{x}\mathbb{E}(I_{t}(x)).$

As defined in Section 3.2, for every $x\in\mathcal{X}$, the posterior
distribution of $f(x)$, at iteration $t$, is
$\mathcal{N}(\mu_{t-1}(x),\omega^{2}\sigma^{2}_{t-1}(x))$. Therefore, the
likelihood of improvement $I_{t}$ on a normal posterior distribution
characterized by $\mu_{t-1}(x),\omega\sigma_{t-1}(x)$ can be computed from the
normal density function:

$\frac{1}{\sqrt{2\pi}\omega\sigma_{t}(x)}\text{exp}(-\frac{(\mu_{t}(x)-f(x)-I_{t}(x))^{2}}{2\omega^{2}\sigma^{2}_{t}(x)}).$

The expected improvement is the integral over this function:

$\displaystyle\mathbb{E}(I_{t})$ $\displaystyle=$
$\displaystyle\int_{I_{t}=0}^{I_{t}=\infty}I_{t}\frac{1}{\sqrt{2\pi}\omega\sigma_{t}(x)}\text{exp}(-\frac{(\mu_{t-1}(x)-f(x)-I_{t}(x))^{2}}{2\omega^{2}\sigma^{2}_{t}(x)})\;\mathrm{d}t$
$\displaystyle=$
$\displaystyle\omega\sigma_{t}(x)[\frac{\mu_{t-1}(x)-\mu^{+}_{t}}{\omega\sigma_{t-1}(x)}\Phi(\frac{\mu_{t-1}(x)-\mu^{+}_{t}}{\omega\sigma_{t-1}(x)})+\phi(\frac{\mu_{t-1}(x)-\mu^{+}_{t}}{\omega\sigma_{t-1}(x)})]$
$\displaystyle=$
$\displaystyle(\mu_{t-1}(x)-\mu^{+}_{t})\Phi(\frac{\mu_{t-1}(x)-\mu^{+}_{t}}{\omega\sigma_{t-1}(x)})+\omega\sigma_{t-1}(x)\phi(\frac{\mu_{t-1}(x)-\mu^{+}_{t}}{\omega\sigma_{t-1}(x)})$

Setting $u=\mu_{t-1}(x)-\mu^{+}_{t}$ and $v=\omega\sigma_{t-1}(x)$, and
$\rho(u,v)=u\Phi(\frac{u}{v})+v\phi(\frac{u}{v})$, we obtain the formula of EI
as :

$\alpha_{t}^{EI}(x)=\rho(u,v)=\rho(\mu_{t-1}(x)-\mu^{+}_{t},\omega\sigma_{t-1}(x)).$

##  Appendix B Proof of Theorem 1

Instead of upper bounding directly the simple regret, we will seek to upper
bound the sum $\sum_{t=1}^{T}r_{t}$ to exploit the results from the maximum
information gain ($\gamma_{T}$) in the noisy setting. The proof for Theorem 1
involves two steps.

  * •

Upper bounding the instantaneous regret $r_{t}=f(x^{*})-f(x_{t}^{+})$.

  * •

Upper bounding the sum $\sum_{t=1}^{T}r_{t}$

###  B.1 Upper bounding the instantaneous regret
$r_{t}=f(x^{*})-f(x_{t}^{+})$:

To obtain a bound on $r_{t}$, we break down $r_{t}$ into two terms as follows:

$\displaystyle r_{t}$ $\displaystyle=$ $\displaystyle f(x^{*})-f(x_{t}^{+})$
$\displaystyle=$ $\displaystyle\underbrace{f(x^{*})-\mu^{+}_{t}}_{\text{Term
1}}+\underbrace{\mu_{t}^{+}-f(x_{t}^{+})}_{\text{Term 2}}$

##### Upper Bounding Term 1.

First, we provide the lower bound and upper bound for the acquisition function
$\alpha^{EI}_{t}(x$ in the noisy setting. These bounds are similar to those in
the noiseless setting (See Lemma 4).

######  Lemma 6 (Based on Lemma 9 of (Wang and de Freitas, 2014)).

Pick $\delta\in(0,1)$. For $x\in\mathcal{X}$, $t\in\mathbb{N}$, set
$I_{t}(x)=\text{max}\\{0,f(x)-\mu^{+}_{t}\\}$. Then with probability at least
$1-\delta$ we have

$I_{t}(x)-\beta_{t}\sigma_{t-1}(x)\leq\alpha^{EI}_{t}(x)\leq
I_{t}(x)+(\beta_{t}+\omega_{t})\sigma_{t-1}(x).$

###### Proof.

If $\sigma_{t-1}(x)=0$ then $\alpha_{t}^{EI}(x)=I_{t}(x)$, which makes the
result trivial. We now assume that $\sigma_{t-1}(x)>0$. Set
$q=\frac{f(x)-\mu^{+}_{t}}{\sigma_{t-1}(x)}$ and
$u=\frac{\mu_{t-1}(x)-\mu^{+}_{t}}{\sigma_{t-1}(x)}$. Then we have that

$\alpha_{t}^{EI}(x)=\omega_{t}\sigma_{t-1}(x)\tau(\frac{u}{\omega_{t}}).$

By Lemma 11, we have that $|u-q|\leq\beta_{t}$ with probability $1-\delta$.
Set $\tau(z)=z\Phi(z)+\phi(z)$. As $\tau^{\prime}(z)=\Phi(z)\in[0,1]$, $\tau$
is non-decreasing and $\tau(z)\leq 1+z$ for $z>0$. Hence,

$\displaystyle\alpha_{t}^{EI}(x)$ $\displaystyle\leq$
$\displaystyle\omega_{t}\sigma_{t-1}(x)\tau(\frac{\text{max}\\{0,q\\}+\beta_{t}}{\omega_{t}})$
$\displaystyle\leq$
$\displaystyle\omega_{t}\sigma_{t-1}(x)(\frac{\text{max}\\{0,q\\}+\beta_{t}}{\omega_{t}}+1)$
$\displaystyle=$ $\displaystyle
I_{t}(x)+(\beta_{t}+\omega_{t})\sigma_{t-1}(x)$

If $I_{t}(x)=0$ then the lower bound is trivial as $\alpha_{t}^{EI}(x)$ is
non-negative. Thus suppose $I_{t}(x)>0$. Since $\alpha_{t}^{EI}(x)\geq 0$ and
$\tau(z)\geq 0$ for all $z$, and $\tau(z)=z+\tau(-z)\geq z$. Therefore,

$\displaystyle\alpha_{t}^{EI}(x)$ $\displaystyle\geq$
$\displaystyle\omega_{t}\sigma_{t-1}(x)\tau(\frac{q-\beta_{t}}{\omega_{t}})$
$\displaystyle\geq$
$\displaystyle\omega_{t}\sigma_{t-1}(x)(\frac{q-\beta_{t}}{\omega_{t}})$
$\displaystyle=$ $\displaystyle I_{t}(x)-\beta_{t}\sigma_{t-1}(x)$

∎

Now we will use the results from Lemma 6 to upper bound Term 1 as in the
follow lemma.

######  Lemma 7.

Pick $\delta\in(0,0.5)$. Then with probability at least $1-2\delta$ we have

$f(x^{*})-\mu_{t}^{+}\leq\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}(\text{max}\\{0,f(x_{t})-\mu_{t-1}^{+}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})).$

###### Proof.

If $\sigma_{t-1}(x^{*})=0$ then by definition of $\alpha_{t}^{EI}(x)$, we have
$\alpha_{t}^{EI}(x^{*})=I_{t}(x^{*})$. We have

$\displaystyle I_{t}(x^{*})$ $\displaystyle=$
$\displaystyle\alpha^{EI}_{t}(x^{*})$ $\displaystyle\leq$
$\displaystyle\alpha^{EI}_{t}(x_{t})$ $\displaystyle\leq$
$\displaystyle\text{max}\\{0,f(x_{t})-\mu^{+}_{t}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})$
$\displaystyle\leq$
$\displaystyle\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}(\text{max}\\{0,f(x_{t})-\mu_{t-1}^{+}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})),$

where in the first inequality, we use the definition
$\alpha^{EI}_{t}(x_{t})=\text{max}_{x\in\mathcal{X}}\alpha^{EI}_{t}(x)$. In
the second inequality, we use Lemma 6. The third inequality holds since
$\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}\geq\frac{\tau(0)}{\tau(0)}=1$
due to the fact that function $\tau(z)$ is an increasing function. Thus, the
lemma holds with probability $1-\delta$.

We now consider $\sigma_{t-1}(x^{*})>0$. If $f(x^{*})<\mu_{t}^{+}$ then the
lemma will be trivial. We now consider $f(x^{*})\geq\mu_{t}^{+}$. By Lemma 11,
$\mu_{t-1}(x^{*})-f(x^{*})\geq-\beta_{t}\sigma_{t-1}(x^{*})$ with probability
$1-\delta$. Combining with the fact that $f(x^{*})\geq\mu_{t}^{+}$, we have
that
$\frac{\mu_{t-1}(x^{*})-\mu^{+}_{t}}{\omega_{t}\sigma_{t-1}(x^{*})}\geq\frac{-\beta_{t}}{\omega_{t}}$
with probability $1-\delta$. On the other hand, following the derivation of
the acquisition function $EI$, we have
$\alpha_{t}^{EI}(x^{*})=\omega_{t}\sigma_{t-1}(x^{*})\tau(\frac{\mu_{t-1}(x^{*})-\mu^{+}_{t}}{\omega_{t}\sigma_{t-1}(x^{*})})$.
Therefore,
$\alpha_{t}^{EI}(x^{*})\geq\omega_{t}\sigma_{t-1}(x^{*})\tau(-\beta_{t}/\omega_{t})$
with probability $1-\delta$ due to the fact that $\tau(z)$ is an increasing
function.

By combining inequalities
$\alpha_{t}^{EI}(x^{*})\geq\omega_{t}\sigma_{t-1}(x^{*})\tau(-\frac{\beta_{t}}{\omega_{t}})$,
$\alpha_{t}^{EI}(x^{*})\geq I_{t}(x^{*})-\beta_{t}\sigma_{t-1}(x^{*})$ which
is proven in Lemma 6, we obtain
$\frac{\beta_{t}}{(\omega_{t}\tau(-\frac{\beta_{t}}{\omega_{t}}))}\alpha_{t}^{EI}(x^{*})+\alpha_{t}^{EI}(x^{*})\geq
I_{t}(x^{*})$. Now,using the fact that $\tau(z)=z+\tau(-z)$ for
$z=\frac{\beta_{t}}{\omega_{t}}$, we obtain

$\displaystyle
I_{t}(x^{*})\leq\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}EI_{t}(x^{*})$
(6)

This inequality (6) holds with probability $1-\delta$. Finally, we achieve

$\displaystyle f(x^{*})-\mu_{t}^{+}$ $\displaystyle\leq$ $\displaystyle
I_{t}(x^{*})$ $\displaystyle\leq$
$\displaystyle\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}EI_{t}(x^{*})$
$\displaystyle\leq$
$\displaystyle\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}EI_{t}(x_{t})$
$\displaystyle\leq$
$\displaystyle\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}(\text{max}\\{0,f(x_{t})-\mu_{t}^{+}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})),$

where the first inequality holds by the definition of the function $I_{t}$.
The second one comes from (6). The third one holds by the property of the
chosen point $x_{t}=\text{argmax}_{x}\alpha_{t}^{EI}(x)$. The final inequality
hold due to Lemma 6. ∎

##### Upper bounding Term 2.

Bounding Term 2 is our important result. This is represented in the following
lemma.

######  Lemma 8.

Pick a $\delta\in(0,1)$. Then with probability $1-\delta$ we have

$\mu_{t}^{+}-f(x^{+}_{t})\leq\frac{\beta_{t}}{\omega_{t}}(\sqrt{2\pi}(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})+\sqrt{2\pi}\text{max}\\{0,(f(x_{t})-\mu_{t}^{+})\\}).$

###### Proof.

By the definition of our GP-EI algorithm,
$x^{+}_{t}=\text{argmax}_{x\in\mathcal{D}_{t}}\mu_{t-1}(x)$. It implies that
$\mu_{t}(x^{+}_{t})=\mu_{t}^{+}$. Hence,

$\displaystyle\alpha_{t}^{EI}(x^{+}_{t})$ $\displaystyle=$
$\displaystyle\omega_{t}\sigma_{t-1}(x^{+}_{t})\tau(\frac{\mu_{t}(x^{+}_{t})-\mu_{t}^{+}}{\omega_{t}\sigma_{t-1}(x^{+}_{t})})$
$\displaystyle=$ $\displaystyle\omega_{t}\sigma_{t-1}(x^{+}_{t})\tau(0)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi}}\omega_{t}\sigma_{t-1}(x^{+}_{t})$

Combining this with the fact that
$\alpha_{t}^{EI}(x_{t})=\text{max}_{x\in\mathcal{X}}\alpha_{t}^{EI}(x)$, we
have

$\displaystyle\frac{1}{\sqrt{2\pi}}\omega_{t}\sigma_{t}(x^{+}_{t})$
$\displaystyle=$ $\displaystyle\alpha_{t}^{EI}(x^{+}_{t})$ $\displaystyle\leq$
$\displaystyle\alpha_{t}^{EI}(x_{t})$ $\displaystyle\leq$
$\displaystyle\text{max}\\{0,f(x_{t})-\mu_{t}^{+}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})$

where the inequality holds due to Lemma 6.

Thus,

$\displaystyle\omega_{t}\sigma_{t-1}(x^{+}_{t})\leq(\sqrt{2\pi}(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t+1})+\sqrt{2\pi}\text{max}\\{0,(f(x_{t})-\mu_{t}^{+})\\})$
(7)

Finally, we can upper bound $\mu_{t}^{+}-f(x^{+}_{t})$ with probability
$1-\delta$ based on (7) as follows:

$\displaystyle\mu_{t}^{+}-f(x^{+}_{t})$ $\displaystyle\leq$
$\displaystyle\beta_{t}\sigma_{t-1}(x^{+}_{t})$ $\displaystyle\leq$
$\displaystyle\frac{\beta_{t}}{\omega_{t}}(\sqrt{2\pi}(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})+\sqrt{2\pi}\text{max}\\{0,(f(x_{t})-\mu_{t}^{+})\\})$

where in the first inequality,
$\mu_{t}^{+}-f(x^{\prime}_{t})\leq\beta_{t}\sigma_{t-1}(x^{\prime}_{t})$ with
probability $1-\delta$ due to Lemma 11. $f(x^{\prime}_{t})-f(x^{+}_{t})\leq 0$
because by definition $x^{\prime}_{t}\in\mathcal{D}_{t}$ and
$x^{+}_{t}=\text{argmax}_{x_{i}\in\mathcal{D}_{t}}f(x_{i})$. The second
inequality holds with probability $1-\delta$ due to Eq(7). Thus, the lemma
holds with probability $1-\delta$. ∎

##### Upper bounding the instantaneous regret $r_{t}=f(x^{*})-f(x_{t}^{+})$.

Combining Term 1 (in Lemma 7) and Term 2 (in Lemma 8), with high probability
we have

$r_{t}\leq(\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}+\sqrt{2\pi}\frac{\beta_{t}}{\omega_{t}})[\text{max}\\{0,f(x_{t})-\mu_{t}^{+}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})]$

.

Now we make this bound simple. By using the assumption of Theorem 2,
$\omega_{t}=\sqrt{\gamma_{t-1}+1+ln(\frac{1}{\delta})}$, we can bound the
ratio
$\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}$
as follows:

######  Lemma 9.

There exists $C>0$ and
$\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}\leq
C$ for every $T\geq 1$ and $1\leq t\leq T$.

###### Proof.

By definition, $\beta_{t}=B+\sqrt{2(\gamma_{t-1}+1+ln(1/\delta))}$. Hence,
$\frac{\beta_{t}}{\omega_{t}}\leq B+\sqrt{2}$. Since the function $\tau(z)$ is
non-decreasing, we have that
$\tau(\frac{\beta_{t}}{\omega_{t}})\leq\tau(B+\sqrt{2})$, and
$\tau(-\frac{\beta_{t}}{\omega_{t}})\geq\tau(-B-\sqrt{2})$. Thus,

$\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}\leq\frac{\tau(B+\sqrt{2})}{\tau(-(B+\sqrt{2}))}.$

Setting $C=\frac{\tau(B+\sqrt{2})}{\tau(-(B+\sqrt{2}))}$ which is a constant,
we have that
$\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}\leq
C$ for every $T\geq 1$ and $1\leq t\leq T$. The lemma holds. ∎

Thus, we obtain an upper bound on $r_{t}$ as follows:

######  Lemma 10.

There exist constant $C>0$ such that

$r_{t}\leq(C+\sqrt{2\pi}(B+\sqrt{2}))(I_{t}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})),$

where $I_{t}=\text{max}\\{0,f(x_{t})-\mu_{t}^{+}\\}$.

###### Proof.

$\displaystyle r_{t}$ $\displaystyle\leq$
$\displaystyle(\frac{\tau(\frac{\beta_{t}}{\omega_{t}})}{\tau(-\frac{\beta_{t}}{\omega_{t}})}+\sqrt{2\pi}\frac{\beta_{t}}{\omega_{t}})[\text{max}\\{0,f(x_{t})-\mu_{t}^{+}\\}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})]$
$\displaystyle\leq$
$\displaystyle(C+\sqrt{2\pi}(B+\sqrt{2}))(I_{t}+(\beta_{t}+\omega_{t})\sigma_{t-1}(x_{t})),$

∎

###  B.2 Upper bounding the sum $\sum_{t=1}^{T}r_{t}$

Using Lemma 10, we obtain an upper bound for $\sum_{t=1}^{T}r_{t}$ as follows:

$\sum_{t=1}^{T}r_{t}\leq(C+\sqrt{2\pi}B+2\sqrt{\pi})\underbrace{\sum_{t=1}^{T-1}I_{t}}_{\text{Term
3}}+(C+\sqrt{2\pi}B+2\sqrt{\pi})\underbrace{\sum_{t=0}^{T-1}(\beta_{t}+\omega_{t})\sigma_{t}(x_{t+1})}_{\text{Term
4}}.$

To upper bound the sum, we will go to upper bound Term 3 and Term 4. While
Term 4 can be bounded via the maximum information gain similar as in the
existing works of GP-UCB and GP-TS (Srinivas et al., 2012; Chowdhury et al.,
2017), bounding Term 3 is the key step in our proof for the acquisition
function GP-EI.

Before providing upper bounds for Term 3 and Term 4, we restate some important
results from existing works in the following section.

####  B.2.1 Auxiliary Lemmas

######  Lemma 11 (Theorem 2 of (Chowdhury et al., 2017)).

Pick $\delta\in(0,1)$. Fix a horizon $T>1$. We define
$\beta_{t}=B+R\sqrt{2(\gamma_{t-1}+1+ln(1/\delta))}$ for every $1\leq t\leq
T$. Then

$\mathbb{P}(\forall 1\leq t\leq T,\forall
x\in\mathcal{X},|f(x)-\mu_{t-1}(x)|\leq\beta_{t}\sigma_{t-1}(x))\geq
1-\delta.$

######  Lemma 12 (Lemma 3 of (Chowdhury et al., 2017)).

The information gain for the points selected can be expressed in terms of the
predictive variances as follows:

$I(y_{T};f_{T})=\frac{1}{2}\sum_{t=1}^{T}ln(1+\lambda^{-1}\sigma_{t-1}(x_{t})).$

######  Lemma 13 (Lemma 5 of (De Freitas et al., 2012)).

When $f\in H_{k}(\mathcal{X})$, then for every $x,y\in\mathcal{X}$, we have

$|f(x)-f(y)|\leq BL||x-y||_{1},$

where $L$ is a Lipschitz constant in $H_{k}(\mathcal{X})$.

###### Proof.

Lemma 5 of (De Freitas et al., 2012) holds for functions in an RKHS equipped
by a kernel $k$. The Lipschitz constant is defined as

$\text{sup}{x\in\mathcal{X}}\partial_{x}\partial{x’}k(x-x’)|_{x’=x}$

, so the second derivative on $k$ is needed. For SE kernel, it alsways holds.
For Matérn kernel , to our best understanding, if we have $\nu\geq 1/2$, we
can ensure the differentiability. ∎

We now are ready to bound Term 3 and Term 4.

####  B.2.2 Upper Bounding Term 3

######  Lemma 14.

Pick $\delta\in(0,1)$. Then with probability at least $1-\delta$ we have that

$\sum_{t=1}^{T}I_{t}=\mathcal{O}(\beta_{T}\sqrt{T\gamma_{T}}).$

###### Proof.

Set $S_{T}=\sum_{t=0}^{T-1}I_{t}$. There are three cases to be considered:

##### Case 1

$S_{T}=0$. This happens when for every $t$: $f(x_{t+1})-\mu_{t}^{+}\leq 0$.

##### Case 2

There exists an unique index $1\leq t^{\prime}\leq T$ such that
$f(x_{t^{\prime}+1})-\mu_{t}^{\prime+}>0$. It follows that
$S_{T}=f(x_{t^{\prime}+1})-\mu_{t}^{\prime+}$. In this case, we have that

$\displaystyle S_{T}$ $\displaystyle=$ $\displaystyle
f(x_{t^{\prime}+1})-\mu_{t}^{\prime+}$ $\displaystyle\leq$ $\displaystyle
f(x_{t^{\prime}+1})-(f(x^{\prime})-\beta_{t^{\prime}+1}\sigma_{t^{\prime}}(x^{\prime}))$
$\displaystyle\leq$ $\displaystyle
f(x_{t^{\prime}+1})-f(x^{\prime})+\beta_{t^{\prime}+1}\sigma_{t^{\prime}}(x^{\prime})$
$\displaystyle\leq$ $\displaystyle
BL||x_{t^{\prime}+1}-x^{\prime}||_{1}+\beta_{t^{\prime}+1}$ $\displaystyle=$
$\displaystyle\mathcal{O}(\beta_{T}),$

where in the last inequality, we use Lemma 5, the inequality
$\beta_{t^{\prime}+1}\leq\beta_{T}$, and the fact that
$\sigma_{t}^{\prime}(x)\leq 1$. Finally, because the domain $\mathcal{X}$ is
bounded, $||x_{t^{\prime}+1}-x^{\prime}||_{1}$ is bounded.

##### Case 3

There are $0\leq t_{1}<t_{2},...,<t_{l}\leq T-1$ where $l\geq 2$ such that
$f(x_{t_{i}+1})\geq\mu_{t_{i}}^{+}$. Thus, we have

$\displaystyle\sum_{t=0}^{T-1}I_{t}$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{l}(f(x_{t_{i}+1})-\mu_{t_{i}}^{+})$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{l}(\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i}+1})+\mu_{t_{i}}(x_{t_{i}+1})-\mu_{t_{i}}^{+})$
$\displaystyle\leq$
$\displaystyle\underbrace{\sum_{i=1}^{l}\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i}+1})}_{\text{Term
5}}+\underbrace{\sum_{i=1}^{l}(\mu_{t_{i}}(x_{t_{i}+1})-\mu_{t_{i}}^{+})}_{\text{Term
6}}$

##### Bound Term 5

$\displaystyle\sum_{i=1}^{l}\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i}+1})$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{T-1}\beta_{t+1}\sigma_{t}(x_{t+1})$
$\displaystyle\leq$
$\displaystyle\beta_{T}\sum_{t=0}^{T-1}\sigma_{t}(x_{t+1})$

##### Bound Term 6

Set $M_{1}=\sum_{i=1}^{l}(\mu_{t_{i}}(x_{t_{i}+1})-\mu_{t_{i}}^{+})$.

$\displaystyle M_{1}$
$\displaystyle=\mu_{t_{l}}(x_{t_{l}+1})-\mu_{t_{1}}^{+}+\sum_{i=1}^{l-1}(\mu_{t_{i-1}}(x_{t_{i-1}+1})-\mu_{t_{i}}^{+}))$
$\displaystyle\leq$
$\displaystyle\underbrace{\mu_{t_{l}}(x_{t_{l}})-\mu_{t_{1}}^{+}}_{\text{Term
7}}+\underbrace{\sum_{i=1}^{l-1}(\mu_{t_{i-1}}(x_{t_{i-1}+1})-\mu_{t_{i}}(x_{t_{i-1}+1})))}_{\text{Term
8}}$

##### Bound Term 7

Set $M_{2}=\mu_{t_{l}}(x_{t_{l}+1})-\mu_{t_{1}}^{+}$. We have

$\displaystyle M_{2}$ $\displaystyle\leq$ $\displaystyle
f(x_{t_{l}+1})+\beta_{t_{l}+1}\sigma_{t_{l}}(x_{t_{l}+1})-(f(x_{t_{1}}-\beta_{t_{1}}\sigma_{t_{1}}(x_{t_{1}})))$
$\displaystyle\leq$ $\displaystyle
f(x_{t_{l}+1})-f(x_{t_{1}})+\beta_{t_{l}+1}\sigma_{t_{l}}(x_{t_{l}+1})+\beta_{t_{1}+1}\sigma_{t_{1}}(x_{t_{1}}))$
$\displaystyle\leq$ $\displaystyle
f(x_{t_{l}+1})-f(x_{t_{1}})+\beta_{t_{l}+1}+\beta_{t_{1}}$ $\displaystyle\leq$
$\displaystyle BL||x_{t_{l}+1}-x_{t_{1}}||_{1}+2\beta_{T}$ $\displaystyle\leq$
$\displaystyle\mathcal{O}(\beta_{T})$

The argument to achieve the bound for Term 7 is similar to Case 2.

##### Bound Term 8

Set
$M_{3}=\sum_{i=1}^{l-1}(\mu_{t_{i-1}}(x_{t_{i-1}+1})-\mu_{t_{i}}(x_{t_{i-1}+1})))$
for simplicity. We go to bound $M$.

$\displaystyle M_{3}$
$\displaystyle\leq\sum_{i=1}^{l-1}(f(x_{t_{i-1}+1})+\beta_{t_{i-1}+1}\sigma_{t_{i-1}}(x_{t_{i-1}+1}))$
$\displaystyle-(f(x_{t_{i-1}+1})-\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i-1}+1}))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{l-1}\beta_{t_{i-1}+1}\sigma_{t_{i-1}}(x_{t_{i-1}+1})+\beta_{t_{i}+1}\sigma_{t_{i}}(x_{t_{i-1}+1})$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{l-1}(\beta_{t_{i-1}+1}+\beta_{t_{i}+1})\sigma_{t_{i-1}}(x_{t_{i-1}+1})$
$\displaystyle\leq$ $\displaystyle
2\beta_{T}\sum_{i=1}^{l-1}\sigma_{t_{i-1}}(x_{t_{i-1}+1})$ $\displaystyle\leq$
$\displaystyle 2\beta_{T}\sum_{i=0}^{T-1}\sigma_{i}(x_{i+1}),$

where in the first inequality, we use Lemma 4:
$\mu_{t_{i-1}}(x_{t_{i-1}+1})\leq
f(x_{t_{i-1}+1})+\beta_{t_{i-1}}\sigma_{t_{i-1}}(x_{t_{i-1}+1})$;
$\mu_{t_{i}}(x_{t_{i-1}+1})\geq
f(x_{t_{i}+1})-\beta_{t_{i}}\sigma_{t_{i}}(x_{t_{i-1}+1})$. In the second
inequality, we use the fact that $f(x_{t_{i-1}+1})\leq f(x_{t_{i}+1})$. In the
third inequality, we use the _decreasing monotonicity of variance functions_
((Vivarelli, 1998) and (Chowdhury et al., 2017), see Section F). Here, we use

$\sigma_{t_{i}}(x_{t_{i-1}+1})\leq\sigma_{t_{i-1}}(x_{t_{i-1}+1}),$

because $t_{i}>t_{i-1}$. This step is crucial to bound $M_{3}$. Without this
step, $M_{3}$ may be bounded by two sums:
$\sum^{l-1}_{i=1}\sigma_{t_{i-1}}(x_{t_{i-1}+1}))$ and
$\sum^{l-1}_{i=1}\sigma_{t_{i}}(x_{t_{i-1}+1}))$. While the first term can be
bounded in terms of the information gain, bounding the second term is very
challenging.

For every $x_{i}$, where $1\leq i\leq T-1$, Lemma 4 holds with probability
$1-\delta$. Therefore, Lemma 4 holds with probability at least $1-\delta$ for
all $x_{i}$, where $1\leq i\leq T-1$. Combining Term 5, Term 7, Term 8, with
probability $1-T\delta$ we have

$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}\leq\mathcal{O}(\beta_{T}\sum_{i=1}^{T-1}\sigma_{i}(x_{i+1})).$

On the other hand, following Lemma 4 of Chowdhury et al. (2017), we have
$\sum_{i=1}^{T-1}\sigma_{i}(x_{i+1})\leq\sqrt{4(T+2)\gamma_{T}}$. Thus,

$\sum_{t=0}^{T-1}\text{max}\\{0,f(x_{t+1})-\mu_{t}^{+}\\}=\mathcal{O}(\beta_{T}\sqrt{T\gamma_{T}}).$

∎

####  B.2.3 Upper Bounding Term 4

######  Lemma 15.

Let $x_{1},...,x_{t}$ be the points selected by Algorithm 2. The sum of
predictive standard deviation at those points can be expressed in terms of the
maximum information gain. More precisely,

$\sum_{t=0}^{T-1}\sigma_{t}(x_{t+1})\leq\sqrt{4(T+1)\gamma_{T}}.$

###### Proof.

By Cauchy-Schwartz inequality,
$\sum_{t=0}^{T-1}\sigma_{t}(x_{t+1})\leq\sqrt{T\sum_{t=1}^{T-1}\sigma^{2}_{t}(x_{t+1})}$.
By assumption, $0\leq k(x,x)\leq 1$. It implies that
$0\leq\sigma_{t-1}^{2}(x)\leq 1$ for all $x\in\mathcal{X}$. Following Lemma 4
of (Chowdhury et al., 2017), we get
$\sum_{t=1}^{T}\sigma_{t-1}(x_{t})\leq\sqrt{4T(1+2/T)\gamma_{T}}\leq\sqrt{4(T+2)\gamma_{T}}$.
Note that we here use $\lambda=1+2/T$ as the setting of (Chowdhury et al.,
2017).

Thus, we have that
$\sum_{t=0}^{T-1}\sigma_{t}(x_{t+1})\leq\sqrt{4(T+2)\gamma_{T}}$ ∎

Combining Lemma 14 and Lemma 15, we obtain an upper bound for the cumularive
regret $\sum_{t=1}^{T}r_{t}$ as follows:

######  Theorem 3.

Pick $\delta\in(0,1)$. Then with probability at least $1-\delta$, the
cumulative regret of Algorithm 1 is bounded as:

$R_{T}=\mathcal{O}(\gamma_{T}\sqrt{T}).$

##  Appendix C Proof of Theorem 2

In this section, we provide a complete proof for Theorem 2 in the main paper.
Here we use a non-trivial combination of the proof techniques as above and the
technical results for $\pi$-GP-UCB (Janz et al., 2020). A key difference from
(Janz et al., 2020) lies in steps from equation 16 to 21 to obtain an upper
bound for $R_{T}^{+}$ which is easy in (Janz et al., 2020).

To obtain an upper bound the sum of $R_{T}=\sum_{t=1}^{T}r_{t}$, where
$r_{t}=f(x^{*})-f(x^{+}_{t})$, we denote $\tilde{\mathcal{A}}_{T}=\cup_{t\leq
T}\mathcal{A}_{t}$, the set of all cover elements created until time $T$, and
define the initial time for an element $A\in\tilde{\mathcal{A}}_{T}$, as
$\phi(A)=\text{min}\\{t:A\in\mathcal{A}_{t}\\}$, and the terminal time as
$\phi^{\prime}(A)=\text{max}\\{t:A\in\mathcal{A}_{t}\\}$.

Unlike the analysis of the sum $R_{T}=\sum_{t=1}^{T}r_{t}$ in the proof of
Theorem 1, we here analyze $R_{T}=\sum_{t=1}^{T}r_{t}$ into groups based on
the partitioning of the searching space.

$\displaystyle R^{+}_{T}$ $\displaystyle=$ $\displaystyle\sum_{t=1}^{T}r_{t}$
(8) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\sum_{A\in\mathcal{A}_{t}}\textbf{1}\\{x_{t}\in
A\\}r_{t}$ (9) $\displaystyle=$
$\displaystyle\sum_{A\in\tilde{\mathcal{A}}_{T}}\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t}$ (10)

The next step is to estimate each component
$\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in A\\}r_{t}$. Given a
set $A\in\mathcal{A}_{T}$, we consider the set $\mathcal{D}_{T}\cap A$.
Without loss of generality, assume that $\mathcal{D}_{T}\cap
A=\\{x^{A}_{1},...,x^{A}_{n(A)}\\}$ with $n(A)=|\mathcal{D}_{T}\cap A|$. We
assume that this order is the real order of time that $x^{A}_{i}$ is selected
by the algorithm. It means that $x^{A}_{1}$ corresponds to time $t_{1}$, …,
and $x^{A}_{n(A)}$ corresponds to time $t_{n(A)}$ where $1\leq
t_{1}<t_{2},<...<t_{n(A)}\leq T$. In addition, for every $1\leq i\leq n(A)$,
$i\leq t_{i}$. Let $x^{A+}_{i}=\text{argmax}_{x^{A}_{j}\in\mathcal{D}_{T}\cap
A,1\leq j\leq i}f(x^{A}_{j})$ and let $r^{A}_{i}=f(x^{*})-f(x^{A+}_{i})$ as
the instantaneous regret at iteration $i$ for the sampled points in $A$. We
have that

$\displaystyle\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t}$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n(A)}r_{t_{i}}$ (11)
$\displaystyle=$ $\displaystyle\sum_{i=1}^{n(A)}(f(x^{*})-f(x^{+}_{t_{i}}))$
(12) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n(A)}(f(x^{*})-f(x^{A+}_{i}))$ (13) $\displaystyle=$
$\displaystyle\sum_{i=1}^{n(A)}r^{A}_{i},$ (14)

where in Eq (12), we use the fact the $f(x^{+}_{t_{i}})\geq f(x^{A+}_{i})$.
Indeed, we have that
$x^{A+}_{i})=\text{argmax}_{x^{A}_{j}\in\mathcal{D}_{T}\cap A,1\leq j\leq
i}f(x^{A}_{j})$ which is defined as above. $x_{t_{i}}$ corresponds to
$x^{A}_{i}$ in set $A$. Therefore, $\\{x^{A}_{1},...,x^{A}_{i}\\}$ is the
subset of $\\{x_{1},x_{2},...,x_{t_{i}}\\}$. It implies that
$f(x^{+}_{t_{i}})\geq f(x^{A+}_{i})$.

By Lemma 21 which we will provide in section C.1, we have that

$\displaystyle\sum_{i=1}^{n(A)}r^{A}_{i}\leq\tilde{\mathcal{O}}(\sqrt{n(A)\gamma^{A}_{\phi^{\prime}(A)}}),$
(15)

where $\gamma^{A}_{\phi^{\prime}(A)}$ is the information gain of $A$ at
iteration $\phi^{\prime}(A)=\text{max}\\{t:A\in\mathcal{A}_{t}\\}$ (See Lemma
17 in Section C.1).

Thus, $\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t}\leq\tilde{\mathcal{O}}(\sqrt{n(A)\gamma^{A}_{\phi^{\prime}(A)}})$.
It is equivalent that

$\displaystyle\frac{(\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t})^{2}}{n(A)}\leq\tilde{\mathcal{O}}(\gamma^{A}_{\phi^{\prime}(A)})$
(16)

Since the inequality at Eq(16) holds for every $A\in\tilde{\mathcal{A}}_{T}$,
we get

$\displaystyle\sum_{A\in\tilde{\mathcal{A}}_{T}}\frac{(\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t})^{2}}{n(A)}\leq\sum_{A\in\tilde{\mathcal{A}}_{T}}\tilde{\mathcal{O}}(\gamma^{A}_{\phi^{\prime}(A)})$
(17)

On the other hand, applying the Cauchy–Schwarz inequality, we have that

$\displaystyle(\sum_{A\in\tilde{\mathcal{A}}_{T}}n(A)(\sum_{A\in\tilde{\mathcal{A}}_{T}}\frac{(\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t})^{2}}{n(A)})\geq(\sum_{A\in\tilde{\mathcal{A}}_{T}}\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t})^{2}$ (18)

As the sets $A$ in $\tilde{\mathcal{A}}_{T}$ are not overlapping,
$\sum_{A\in\tilde{\mathcal{A}}_{T}}n(A)=T$. Replacing this to Eq(18), we get

$\displaystyle\sqrt{T(\frac{(\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t})^{2}}{n(A)})}\geq\sum_{A\in\tilde{\mathcal{A}}_{T}}\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t}$ (19)

Combining Eq(10), Eq(17) and Eq(19), we get that

$\displaystyle R^{+}_{T}$ $\displaystyle=$
$\displaystyle\sum_{A\in\tilde{\mathcal{A}}_{T}}\sum_{t=\phi(A)}^{\phi^{\prime}(A)}\textbf{1}\\{x_{t}\in
A\\}r_{t}$ (20) $\displaystyle\leq$
$\displaystyle\sqrt{T(\sum_{A\in\tilde{\mathcal{A}}_{T}}\tilde{\mathcal{O}}(\gamma^{A}_{\phi^{\prime}(A)}))}$
(21)

By Lemma 18 which is proven in Section C.1, the number of the sets
$A\in\tilde{\mathcal{A}}_{T}$ is $\mathcal{O}(T^{q})$, where
$q=\frac{d(d+1)}{d(d+2)+2\nu}$ (See Section 5.1). By Lemma 17 in Section C.1,
$\gamma^{A}_{\phi^{\prime}(A)}$ is bounded by a logarithmic function in $T$
for all $A\in\tilde{\mathcal{A}}_{T}$. Thus, we have
$R_{T}\leq\mathcal{O}(T^{\frac{q+1}{2}})$. Using the definition of
$q=\frac{d(d+1)}{d(d+2)+2\nu}$, we get that
$R_{T}=\tilde{\mathcal{O}}(T^{\frac{-2\nu-d}{d(2d+4)+4\nu}})$.

###  C.1 Auxiliary Lemmas

######  Lemma 16.

For every $1\leq i\leq T$, we have that $\gamma_{i}\leq\gamma_{T}$.

###### Proof.

By Lemma 12, for a set of point $A_{i}={x_{1},x_{2},...,x_{i}}$, we have that
$I(y_{i};f_{i})=\frac{1}{2}\sum_{t=1}^{i}ln(1+\lambda^{-1}\sigma_{t-1}(x_{t}))$.
Consider a set $A_{T}=A_{i}\cup\\{x_{i+1,...,x_{T}}\\}$ containing $T$
elements. We also have that
$I(y_{A_{T}};f_{A_{T}})=\frac{1}{2}\sum_{t=1}^{T}ln(1+\lambda^{-1}\sigma_{t-1}(x_{t}))$.
Thus, for each $A_{i}$ which contains $i$ elements, we always can construct a
set $A_{T}$ containing $T$ elements such that $I(y_{i};f_{i})\leq
I(y_{T};f_{T})$. Thus,

$\gamma_{i}=\text{max}_{A\in\mathcal{X}:|A|=i}I(y_{A}:f_{A})\leq\text{max}_{A\in\mathcal{X}:|A|=T}I(y_{A}:f_{A})=\gamma_{T}.$

∎

######  Lemma 17 (Lemma 1 of (Janz et al., 2020)).

Let $A$ be a subset of $\mathcal{X}$ and assume that there exists a
$1\leq\phi\leq T$ such that $A\in\mathcal{A}_{\tau}$. Let
$\phi^{\prime}(A)=\text{max}\\{1\leq t\leq T:A\in\mathcal{A}_{t}\\}$. Then for
some $C>0$, $\gamma_{\phi^{\prime}(A)}^{A}\leq Cln(T)lnln(T)$.

######  Lemma 18 (Lemma 2 of (Janz et al., 2020)).

Let A be the covering set at time $t$. Assume that
$\mathcal{A}_{2}=\mathcal{O}(T^{q})$. Then for $T$ sufficiently large,
$|\cup_{t\leq T}\mathcal{A}_{t}|\leq C_{d,v}T^{q}$, where $C_{d,v}>0$ depends
on $d$ and $\nu$ only.

######  Lemma 19 (Lemma 5 of (Janz et al., 2020)).

Given $\delta\in(0,1)$. for all $t\leq T$, for all $A\in\cup_{t\leq
T}\mathcal{A}_{t}$, we have

$\mathbb{P}(\forall t,\forall x\in
A,|f(x)-\mu^{A}_{t-1}(x)|\leq\hat{\beta}^{A}_{t}\sigma_{t-1}(x))\geq
1-\delta,$

where $\hat{\beta}^{A}_{t}=B+R\sqrt{2(\gamma^{A}_{t-1}+1+ln(1/\delta))}$, and
$\gamma^{A}_{t-1}=\frac{1}{2}ln|I+\lambda^{-1}K^{A}_{t-1}|$.

Before proving the important Lemma , we need the following lemma to upper
bound
$\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}$
for $1\leq i\leq n(A)$.

######  Lemma 20.

Given $\omega_{T}=\sqrt{\text{ln}(T)\text{ln}\text{ln}(T)}$. Let $A$ be a
subset of $\mathcal{X}$ and assume that there exists a $1\leq\phi\leq T$ such
that $A\in\mathcal{A}_{\tau}$. Let $\phi^{\prime}(A)=\text{max}\\{1\leq t\leq
T:A\in\mathcal{A}_{t}\\}$. There exists a constant $C>0$ such that for every
$T>0$ and for every $1\leq i\leq n(A)$ we have

$\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}\leq
C.$

###### Proof.

By definition,
$\beta^{A}_{t_{i}}=B+\sqrt{\gamma^{A}_{t_{i}-1}+1+ln(1/\delta)}$. Using the
increasing monotonicity of function $\gamma^{A}$, we have that
$\gamma^{A}_{t_{i}-1}\leq\gamma_{\phi^{\prime}(A)}^{A}$ (because
$t_{i}-1\leq\phi^{\prime}(A)$). By Lemma 17,
$\gamma_{\phi^{\prime}(A)}^{A}\leq Cln(T)lnln(T)$. Therefore,
$\beta^{A}_{t_{i}}=B+\sqrt{\gamma^{A}_{t_{i}-1}+1+ln(1/\delta)}\leq
B+\sqrt{\gamma_{\phi^{\prime}(A)}^{A}+1+ln(1/\delta)}\leq
B+\sqrt{Cln(T)lnln(T)+1+ln(1/\delta)}$.

On the other hand, there exists a $C_{1}$ large enough such that
$B+\sqrt{Cln(T)lnln(T)+1+ln(1/\delta)}\leq C_{1}\sqrt{ln(T)lnln(T)}$.
Combining this with the above result, we imply that $\beta^{A}_{t_{i}}\leq
C_{1}\sqrt{ln(T)lnln(T)}=C_{1}\omega_{T}$. It is equivalent that
$\frac{\beta^{A}_{t_{i}}}{\omega_{T}}\leq C_{1}$.

Since the function $\tau(z)$ is non-decreasing, we have that
$\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})\leq\tau(C_{1})$, and
$\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})\geq\tau(-C_{1})$. Thus,

$\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}\leq\frac{\tau(C_{1})}{\tau(-C_{1})}.$

Set $C=\frac{\tau(C_{1})}{\tau(-C_{1})}$. We now can bound the ratio
$\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}$
by a constant.

$\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}\leq
C.$

∎

Finally, we provide an upper bound for the sum $\sum_{i=1}^{n(A)}r^{A}_{i}$.

######  Lemma 21.

Let $\omega_{T}=\sqrt{\text{ln}(T)\text{ln}\text{ln}(T)}$. Given a set
$A\in\mathcal{A}_{t}$ and assume that there exists a $1\leq\phi\leq T$ such
that $A\in\mathcal{A}_{\tau}$. Let $\phi^{\prime}(A)=\text{max}\\{1\leq t\leq
T:A\in\mathcal{A}_{t}\\}$. Then with probability at least $1-\delta$, we have

$\sum_{i=1}^{n(A)}r^{A}_{i}\leq\tilde{\mathcal{O}}(\sqrt{n(A)\gamma^{A}_{\phi^{\prime}(A)}}),$

where $n(A)=|\mathcal{D}_{T}\cap A|$ which is defined as above. The notation
$\tilde{\mathcal{O}}$ is a variant of $\mathcal{O}$, where log factors are
suppressed.

###### Proof.

Following the Improved-GP-EI algorithm, each $A\in\mathcal{A}_{t}$ is fitted
by an independent Gaussian process with $N(A)$ observations and the sampled
points in $\mathcal{D}_{t}^{A}$:
$(x_{1}^{A},y_{1}^{A}),...,(x_{N(A)}^{A},y_{N(A)}^{A})$. Therefore, we can
apply the results in Section B to the set $A$.

Similar to the proofs of Lemma 6, Lemma 7, and Lemma 8, we obtain an upper
bound on $r^{A}_{i}=f(x^{*})-f(x^{A+}_{i})$ as follows.

$r^{A}_{i}\leq(\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}+\sqrt{2\pi})\text{max}\\{0,f(x^{A}_{i+1})-\mu^{A+}_{t_{i}}\\}+(\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}(\beta^{A}_{t_{i}}+\omega_{T})+\sqrt{2\pi}(3\beta^{A}_{t_{i}}+\omega_{T}))\sigma^{A}_{t_{i}}(x^{A}_{i+1})),$

where $\mu^{A+}_{i}=\text{max}_{x^{A}_{j}\in\mathcal{D}_{T}\cap A,1\leq j\leq
i}\mu_{t_{i}}(x^{A}_{j})$. Recall that
$x^{A+}_{i}=\text{argmax}_{x^{A}_{j}\in\mathcal{D}_{T}\cap A,1\leq j\leq
i}f(x^{A}_{j})$.

Using Lemma 21, we can bound the ratio
$\frac{\tau(\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}{\tau(-\frac{\beta^{A}_{t_{i}}}{\omega_{T}})}$
by a constant which is independent of $1\leq t\leq T$ and $T$. Thus, by the
proofs similar to those of Lemma 14 and Lemma 15, we obtain an upper bound on
the sum $\sum_{i=1}^{n(A)}r^{A}_{i}$ as

$\sum_{i=1}^{n(A)}r^{A}_{i}\leq\mathcal{O}(\beta^{A}_{t_{N(A)}}\sqrt{n(A)\gamma^{A}_{\phi^{\prime}(A)}}).$

Using the proof similar to Lemma 21 as above, there exists constant $C_{1}$
such that $\beta^{A}_{t_{N(A)}}\leq
C_{1}\omega_{T}=\Theta(\sqrt{\text{ln}(T)\text{ln}\text{ln}(T)})$. We can
remove this log component from the upper bound. Finally, we have that

$\sum_{i=1}^{n(A)}r^{A}_{i}\leq\tilde{\mathcal{O}}(\sqrt{n(A)\gamma^{A}_{\phi^{\prime}(A)}}).$

∎

##  Appendix D Additional Experiments for Real-World Benchmarks

We now take a 2-layer perceptron network (MLP) with 512 neurons/layer and
optimize three hypeparameters: the learning rate $l$ and the norm
regularization hyperparameters $l_{r1}$ and $l_{r2}$ of the two layers. We
train the algorithms using the MNIST train dataset (55000 patterns) and then
test the model on the MNIST test dataset (10000 patterns). We plot the
optimization results using prediction accuracy in Figure 3.

Figure 3: Comparison of methods on MLP.