Abstract

We study a widely used Bayesian optimization method, Gaussian process Thompson sampling (GP-TS), under the assumption that the objective function is a sample path from a GP. Compared with the GP upper confidence bound (GP-UCB) with established high-probability and expected regret bounds, most analyses of GP-TS have been limited to expected regret. Moreover, whether the recent analyses of GP-UCB for the lenient regret and the improved cumulative regret upper bound can be applied to GP-TS remains unclear. To fill these gaps, this paper shows several regret bounds: (i) a regret lower bound for GP-TS, which implies that GP-TS suffers from a polynomial dependence on \(1/\delta\) with probability \(\delta\), (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on \(\delta\), (iii) expected lenient regret upper bounds, and (iv) an improved cumulative regret upper bound on the time horizon \(T\). Along the way, we provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on \(T\).

1 Introduction↩︎

Bayesian optimization (BO) [1], [2] is a powerful framework for black-box optimization problems. BO aims to optimize an expensive-to-evaluate black-box function using a small number of input-output pairs by adaptively querying input points based on a Bayesian model, typically a Gaussian process (GP) model. BO has been applied to a wide range of applications, such as materials informatics [3], AutoML [4], and drug discovery [5]. Alongside these applications and algorithmic developments, theoretical properties of BO have also been studied. This paper focuses on regret analysis under the assumption that the objective function is a sample path from a GP.

Gaussian process upper confidence bound (GP-UCB) [1], [6] is a BO algorithm with well-established theoretical guarantees. The theoretical performance of BO methods is often measured by cumulative regret [6], for which both high-probability and expected upper bounds of GP-UCB have been derived [6], [7]. High-probability upper bound of an alternative criterion called lenient regret [8], which counts a regret exceeding a given tolerance, has also been obtained by [9], [10]. Furthermore, [10] has shown a tighter high-probability upper bound for the cumulative regret. These results position GP-UCB as the most extensively analyzed algorithm in the BO literature.

GP Thompson sampling (GP-TS) [11] is another well-known BO algorithm with regret guarantees. GP-TS achieves a similar expected cumulative regret upper bound as GP-UCB [11]–[13]. However, its high-probability regret upper bound is limited to the direct consequence of the expected regret bound, leading to worse dependence on probability \(\delta\) than GP-UCB. In addition, neither high-probability lenient regret bounds nor tighter high-probability cumulative regret bounds have been established for GP-TS, which has been explicitly described as an open problem in [10]. Despite these limitations, GP-TS remains a promising alternative among BO methods with regret guarantees, since GP-UCB often relies on a carefully tuned confidence width parameter that lacks such guarantees in practice. Therefore, more refined regret analyses of GP-TS are needed to support its empirical effectiveness.

This paper aims to bridge the gap between the regret analyses of GP-UCB and GP-TS discussed above. First, we investigate the dependence on probability \(\delta\) in high-probability regret bounds. While GP-UCB enjoys logarithmic dependence on \(\delta\), existing analyses of GP-TS require polynomial dependence of \(1/\delta\), raising the question of whether logarithmic dependence is achievable by GP-TS. For this question, we construct a problem instance in which GP-TS incurs \(\Omega(1/\delta^{c})\) regret, which implies a purely theoretical limitation that GP-TS cannot obtain \(O(\log (1 / \delta))\) regret upper bounds in general. Second, we derive an upper bound on the second moment of the cumulative regret, which directly leads to an improved cumulative regret upper bound on \(\delta\). Third, we show that GP-TS achieves polylogarithmic expected upper bounds on lenient regrets, the first such bounds for any algorithm. Our proof for the lenient regret is different from [9], [10] and readily suggests polylogarithmic expected lenient regret upper bounds for GP-UCB by combining the known proof techniques [7], [11]. Finally, by adapting the recent analysis of GP-UCB by [10] and our lenient regret upper bounds, we obtain an improved cumulative regret bound on the time horizon \(T\) for GP-TS. Our refined analysis, applicable to both GP-UCB and GP-TS, relaxes the conditions on Matérn kernels.

Our contributions are summarized as follows:

Theorem 1 provides the problem instance in which GP-TS incurs \(\Omega(1/\delta^{c})\) regret with probability \(\delta\). This result implies a purely theoretical limitation of GP-TS that the regret upper bounds of GP-TS cannot be bounded from above by \(O\bigl(\log(1/\delta)\bigr)\).
In Theorem 2, we derive the upper bound on the second moment of the cumulative regret and the high-probability cumulative regret bound that improves dependence on probability \(\delta\) by a factor of \(1/\sqrt{\delta}\).
In Theorem 3, we obtain the expected lenient regret upper bound for GP-TS, which is polylogarithmic on the time horizon \(T\) as with the high-probability bound of GP-UCB.
Theorem 4 presents the \(\tilde{O}(\sqrt{T})\) high-probability cumulative regret upper bound, where \(\tilde{O}\) hides polylogarithmic factors on \(T\), improved with resect to \(T\) for squared exponential and Matérn kernels under a looser condition on Matérn kernels by the refined analysis shown in Lemma 3.

Along the way, we obtain useful lemmas, which are discussed alongside the most relevant theorems.

Common theoretical assumptions for BO are categorized into the frequentist setting [6], [14]–[17] and the Bayesian setting [6], [7], [10], [13], [18]. In the frequentist setting, the objective function is assumed to be an element of a reproducing kernel Hilbert space endowed by a predefined kernel function. In the Bayesian setting, the objective function is assumed to be a sample path from a GP with a predefined kernel function. Note that neither setting encompasses the other as discussed in Section 4 of [6]. As already discussed, this paper focuses on the Bayesian setting. In addition, we focus on the noisy setting, where observations are contaminated by noise, since a noise-free setting has been considered separately using different proof techniques [16], [19].

GP-TS has also been considered in the frequentist setting [14], [20]. Although we will not consider the frequentist setting, the proof technique in [14] could potentially be leveraged in the Bayesian setting, as discussed in Section 4. Furthermore, GP-TS has also been extended to various problem settings, such as parallel BO [12], [21], [22], constrained BO [23], multi-objective BO [24]–[26], preferential BO [27], and reinforcement learning [28], [29]. Thus, fundamental refinement of analysis for GP-TS is needed. Note that, for [28], [29], we will discuss their result that appears to contradict our Theorem 1 in Section 3.1.

Since the posterior sampling of GPs cannot be conducted analytically, we require an approximation, for example, proposed by [30], [31] based on random Fourier feature [32]. In our analysis, we ignore this approximation error, though it may be addressed by high-accuracy approximations as with [33].

In the BO literature, many other algorithms have been studied. For example, probability of improvement [1], expected improvement [2], knowledge gradient [34], entropy search [35], [36], predictive entropy search [37] have been extensively studied. However, regret guarantees for these algorithms remain an open problem.

Except for GP-UCB and GP-TS, several BO algorithms with regret guarantees have been proposed recently [7], [13], [38], [39]. These existing methods are randomized algorithms, as with GP-TS, and their regret analysis follows a similar approach to GP-TS. Therefore, our proof technique may be useful for analyzing those algorithms.

[18] has shown the algorithm-independent regret lower bound in the Bayesian setting. Specifically, [18] has shown the \(\Omega(\sqrt{T})\) regret lower bound for conditional expected regret with one-dimensional objective functions. Therefore, rigorous high-probability regret lower bounds have not been established. Thus, as discussed in Section 4, proving the optimality of BO algorithms rigorously remains an open problem.

TS [40] has been extensively studied in the bandit literature, and many regret bounds of TS have been provided, as reviewed in [41]. In particular, [42] have shown the expected regret lower bound for (independent) Gaussian multi-armed bandit. However, to our knowledge, regret lower bounds focusing on probability, particularly applicable to GP-TS, have not been established.

We analyze lenient regret, recently introduced by [8] in the bandit literature. [9] have derived the high-probability lenient regret upper bound of GP-UCB in the frequentist setting. [10] has extended this analysis to the Bayesian setting. We show the Bayesian expected lenient regret upper bound of GP-TS, in which we employ a different proof from [9], [10].

2 Preliminaries↩︎

This section provides problem setup, regularity assumptions, and background knowledge for GP-TS.

2.1 Problem Setup↩︎

We consider a sequential decision-making problem to optimize an unknown black-box function \(f\): \[\begin{align} \boldsymbol{x}^* = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in {\cal X}} f(\boldsymbol{x}), \end{align}\] where \({\cal X}\subset \mathbb{R}^d\) is an input domain and \(d\) is an input dimension. Here, “black-box” means that we can obtain only (contaminated) function values, and other information, such as derivatives, is unknown. Furthermore, we generally assume that \(f\) is expensive to evaluate. Therefore, our goal is to optimize \(f\) with fewer function evaluations.

In this problem, BO sequentially evaluates the maximizer of an acquisition function (AF), which is designed so that beneficial inputs are chosen based on a Bayesian model. That is, for all iterations \(t \geq 1\), BO algorithms sequentially evaluate \(f(\boldsymbol{x}_t)\), where \(\boldsymbol{x}_t = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in {\cal X}} \alpha_t(\boldsymbol{x})\) with some AF \(\alpha_t: {\cal X}\rightarrow \mathbb{R}\) based on the Bayesian model. By this procedure, BO aims to achieve a sample-efficient optimization.

In the BO literature, the performance of algorithms is often measured by cumulative regret [6]: \[\begin{align} R_T = \sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t). \end{align}\] In particular, if the cumulative regret is sublinear \(R_T = o(T)\), then we can see that the solution of the BO algorithm converges to the optimal solution. This is because we can choose the solution \(\hat{\boldsymbol{x}}_t\) so that \(f(\boldsymbol{x}^*) - f(\hat{\boldsymbol{x}}_t) \leq \frac{1}{T} R_T = o(1)\). Hence, we focus on sublinear cumulative regret bounds.

In addition, we consider the performance measure called lenient regret [8], [9]: \[\begin{align} LR_T = \sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t), \end{align}\] where \({\cal T}= \{ t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \}\) and \(\Delta > 0\) is a predefined constant. The lenient regret measures regret under a given tolerance \(\Delta\), where the input \(\boldsymbol{x}\) that satisfies \(f(\boldsymbol{x}^*) - f(\boldsymbol{x}) \leq \Delta\) is regarded as a sufficiently good action. We further analyze upper bounds of \(|{\cal T}|\) as with [8], [9].

2.2 Gaussian Process Regression↩︎

In this paper, we assume the following regularity condition on the objective function \(f\):

Assumption 1. The objective function \(f:{\cal X}\rightarrow \mathbb{R}\) follows \({\cal G}{\cal P}(0, k)\), where \({\cal X}\subset \mathbb{R}^d\), \(k: {\cal X}\times {\cal X}\rightarrow \mathbb{R}\) is a kernel function, and \({\cal G}{\cal P}(0, k)\) denotes a zero-mean GP with a covariance function \(k\). Furthermore, the kernel function satisfies \(k(\boldsymbol{x}, \boldsymbol{x}^\prime) \leq 1\) for all \(\boldsymbol{x}, \boldsymbol{x}^\prime \in {\cal X}\). Observation noise \(\{\epsilon_i\}_{i \in \mathbb{N}}\) are mutually independent and \(\epsilon_i \sim {\cal N}(0, \sigma^2)\) with \(\sigma^2 > 0\) for all \(i \in \mathbb{N}\). The noise contaminates observations as \(y_i = f(\boldsymbol{x}_i) + \epsilon_i\).

Let the training dataset \({\cal D}_t = \{ (\boldsymbol{x}_i, y_i) \}_{i=1}^t\). Under Assumption 1, the posterior distribution of \(f\) given \({\cal D}_t\) is also a GP, whose mean and variance are derived as follows: \[\begin{align} \mu_{t}(\boldsymbol{x}) &= \boldsymbol{k}_{t}(\boldsymbol{x})^\top \bigl(\boldsymbol{K}_t + \sigma^2 \boldsymbol{I}_{t} \bigr)^{-1} \boldsymbol{y}_{t}, \\ \sigma_{t}^2 (\boldsymbol{x}) &= k(\boldsymbol{x}, \boldsymbol{x}) - \boldsymbol{k}_{t}(\boldsymbol{x}) ^\top \bigl(\boldsymbol{K}_t + \sigma^2 \boldsymbol{I}_{t} \bigr)^{-1} \boldsymbol{k}_{t}(\boldsymbol{x}), \end{align} \label{eq:GP}\tag{1}\] where \(\boldsymbol{k}_{t}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \bigl( k(\boldsymbol{x}, \boldsymbol{x}_1), \dots, k(\boldsymbol{x}, \boldsymbol{x}_{t}) \bigr)^\top \in \mathbb{R}^{t}\), \(\boldsymbol{K}_t \in \mathbb{R}^{t \times t}\) is the kernel matrix whose \((i, j)\)-element is \(k(\boldsymbol{x}_i, \boldsymbol{x}_j)\), \(\boldsymbol{I}_{t} \in \mathbb{R}^{t \times t}\) is the identity matrix, and \(\boldsymbol{y}_{t} \mathrel{\vcenter{:}}= (y_1, \dots, y_t)^\top \in \mathbb{R}^{t}\) [43].

For continuous input domains, we consider the following additional assumption [6], [12], [13], [44]:

Assumption 2. Let \({\cal X}\subset [0, r]^d\) be a compact set with some \(r > 0\). There exist constants \(a, b > 0\) such that the kernel \(k\) satisfies the following condition on the derivatives of a sample path \(f\): \[\begin{align} \Pr \left( \sup_{\boldsymbol{x} \in {\cal X}} \left| \frac{\partial f}{\partial \boldsymbol{x}_j} \right| > L \right) \leq a \exp \left( - \left(\frac{L}{b}\right)^2 \right),\text{ for } j \in [d], \end{align}\] where \([d] = \{1, \dots, d\}\).

This condition is satisfied by the common kernel functions [6], such as linear kernels \(k_{\rm Lin} (\boldsymbol{x}, \boldsymbol{x}^\prime) = \boldsymbol{x}^\top \boldsymbol{x}^\prime\), squared exponential (SE) kernels \(k_{\rm SE} (\boldsymbol{x}, \boldsymbol{x}^\prime) = \exp\left( - \| \boldsymbol{x} - \boldsymbol{x}^\prime \|_2^2 / (2 \ell^2) \right)\), and Matérn kernels \(k_{\rm Mat}(\boldsymbol{x}, \boldsymbol{x}') = \frac{2^{1 - \nu}}{\Gamma(\nu)} \left( \frac{\sqrt{2\nu} \| \boldsymbol{x} - \boldsymbol{x}^\prime \|_2 }{\ell} \right)^{\nu} J_{\nu} \left( \frac{\sqrt{2\nu} \| \boldsymbol{x} - \boldsymbol{x}^\prime \|_2 }{\ell} \right)\) with \(\nu > 2\), where \(\ell, \nu > 0\) are the lengthscale and smoothness parameter, respectively, and \(\Gamma(\cdot)\) and \(J_{\nu}\) are Gamma and modified Bessel functions.

In addition, we leverage the following result [45] for continuous input domains:

Lemma 1 (Lipschitz constants for posterior standard deviation). Let \(k: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}\) be linear, SE, or Matérn kernel with \(\nu > 1\) and \(k(\boldsymbol{x}, \boldsymbol{x}) \leq 1\) for all \(\boldsymbol{x} \in \mathbb{R}^d\). Moreover, assume that a noise variance \(\sigma^2\) is positive. Then, for any \(t \geq 1\) and \({\cal D}_{t-1}\), the posterior standard deviation \(\sigma_{t-1} (\boldsymbol{x} )\) satisfies that \[\begin{align} \forall \boldsymbol{x},\boldsymbol{x}^\prime \in \mathbb{R}^d, \;| \sigma_{t-1} (\boldsymbol{x} ) - \sigma_{t-1} (\boldsymbol{x}^\prime ) | \leq L_{\sigma} \| \boldsymbol{x} - \boldsymbol{x}^\prime \| _1, \end{align}\] where \(L_{\sigma}\) is a positive constant given by \[\begin{align} L_{\sigma} = \left\{ \begin{array}{ll} 1 & \text{if k = k_{\rm Lin}}, \\ \frac{\sqrt{2}}{\ell} & \text{if k = k_{\rm SE}}, \\ \frac{\sqrt{2}}{\ell} \sqrt{\frac{\nu}{\nu-1} } & \text{if k = k_{\rm Mat} with \nu > 1}. \end{array}\right. \end{align}\]

We use this lemma to handle discretization error, as in the existing analysis of GP-TS [13].

Finally, to obtain a tighter regret upper bound on \(T\), we further leverage the following lemma [10], [18], [19]:

Lemma 2 (Conditions on the global maximizer of sample path). Let \({\cal X}= [0, r]^d\). Suppose \(k = k_{\rm SE}\) or \(k = k_{\rm Mat}\) with \(\nu > 2\) and Assumption 1 holds. Then, for any \(\delta_{\rm GP} \in (0, 1)\), there exist strictly positive constants \(c_{\rm gap}, c_{\rm sup}, c_{\rm quad}, \rho_{\rm quad} > 0\) such that the following statements hold simultaneously with probability at least \(1 - \delta_{\rm GP}\):

The function \(f\) has a unique maximizer \(\boldsymbol{x}^* \in {\cal X}\) such that \(f(\boldsymbol{x}^*) > f(\tilde{\boldsymbol{x}}^*) + c_{\rm gap}\) holds for any local maximizer \(\tilde{\boldsymbol{x}}^* \in {\cal X}\) of \(f\).
The sup-norm of the sample path is bounded as \(\| f \|_{\infty} \leq c_{\rm sup}\).
The function \(f\) satisfies \(\forall \boldsymbol{x} \in {\cal B}_2(\rho_{\rm quad}; \boldsymbol{x}^*), f(\boldsymbol{x}^*) - c_{\rm quad} \| \boldsymbol{x}^* - \boldsymbol{x}\|_2^2 \geq f(\boldsymbol{x})\), where \({\cal B}_2(\rho; \boldsymbol{x}^*) = \{ \boldsymbol{x} \in {\cal X}\mid \| \boldsymbol{x}^* - \boldsymbol{x}\|_2 \leq \rho \}\) is the L2-ball on \({\cal X}\), whose radius and center are \(\rho\) and \(\boldsymbol{x}^*\), respectively.

We use this lemma to derive a similar proof as that of [10]. For more details, see [10], [18], [19].

2.3 Maximum Information Gain (MIG)↩︎

The complexity of BO problems is commonly quantified by the MIG [6] defined below:

Definition 1 (Maximum information gain). Let \(f \sim {\cal G}{\cal P}(0, k)\) over \({\cal X}\subset [0, r]^d\). Let \(A = \{ \boldsymbol{a}_i \}_{i=1}^T\), where \(\boldsymbol{a}_i \in {\cal X}\) for all \(i \in [T]\). Let \(\boldsymbol{f}_A = \bigl(f(\boldsymbol{a}_i) \bigr)_{i=1}^T\), \(\boldsymbol{\epsilon}_A = \bigl(\epsilon_i \bigr)_{i=1}^T\), where \(\forall i, \epsilon_i \sim {\cal N}(0, \sigma^2)\), and \(\boldsymbol{y}_A = \boldsymbol{f}_A + \boldsymbol{\epsilon}_A \in \mathbb{R}^T\). Then, MIG \(\gamma_T\) is defined as follows: \[\begin{align} \gamma_T \mathrel{\vcenter{:}}= \max_{A} I(\boldsymbol{y}_A ; \boldsymbol{f}_A), \end{align}\] where \(I\) is the Shannon mutual information.

The MIGs of several commonly used kernel functions are known to be sublinear in terms of \(T\). For example, \(\gamma_T = O\bigl( d \log T \bigr)\) for linear kernels, \(\gamma_T = O\bigl( (\log T)^{d+1} \bigr)\) for SE kernels, and \(\gamma_T = O\bigl( T^{\frac{d}{2\nu + d}} (\log T)^{\frac{4\nu + d}{2\nu + d}} \bigr)\) for Matérn-\(\nu\) kernels, respectively [6], [10], [46], [47]¹. For convenience, we define the above known upper bound of MIG as \(\tilde{\gamma}_t: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}\), which is a concave function with respect to \(t \geq 1\) [6], [10], [46], [47]. We will use this concavity particularly to show Lemma 11.

2.4 Gaussian Process Thompson Sampling↩︎

GP-TS [11]–[13] is the BO method that sequentially evaluates the optimal point of a posterior sample path. Therefore, the AF of GP-TS is formalized as \[\begin{align} \boldsymbol{x}_t = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in {\cal X}} g_t(\boldsymbol{x}), \end{align}\] where \(g_t \sim p(f \mid {\cal D}_{t-1})\). Algorithm 1 provides a pseudocode of GP-TS.

The expected regret upper bounds under Assumption 1 have been shown as [11]–[13]: \[\begin{align} \mathbb{E}\left[ R_T \right] &= \tilde{O}(\sqrt{T \gamma_T}), \end{align}\] where \(\tilde{O}\) hides polylogarithmic factors in terms of \(T\). Therefore, for any \(\delta \in (0, 1)\), the following inequality holds with probability at least \(1 - \delta\): \[\begin{align} R_T = \tilde{O}\left( \frac{\sqrt{T \gamma_T}}{\delta} \right), \end{align}\] as a direct consequence of Markov’s inequality [11].

3 Regret Analysis↩︎

This section describes our regret analyses.

3.1 Regret Lower Bound↩︎

First, we show the simple two-armed problem instance where GP-TS must incur \((1 / \delta)^c\) cumulative regret, where \(c \in (0, 1)\), with probability at least \(\delta \in (0, 1)\).

Theorem 1. Assume that \({\cal X}= \{ \boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)} \}\), \(\epsilon_t \sim {\cal N}(0, 1)\) for all \(t \in [T]\), and \[\begin{align} \left( \begin{array}{c} f(\boldsymbol{x}^{(1)}) \\ f(\boldsymbol{x}^{(2)}) \end{array} \right) \sim {\cal N}\left( \left( \begin{array}{c} 0 \\ 0 \end{array} \right), \left( \begin{array}{cc} 1 & 1 / 2 \\ 1 / 2 & 1 \end{array} \right) \right). \end{align}\] Then, if Algorithm 1 runs and \(T > e\), the following holds: \[\begin{align} \Pr\left( R_T \geq T / 2 \right) \geq \frac{c_1}{T^{c_2}}, \end{align}\] where \(c_1\) and \(c_2\) are strictly positive constants.

This theorem implies a purely theoretical limitation that we cannot obtain \(O(\log(1 / \delta))\) cumulative regret upper bounds for GP-TS in general. This is because we can show a contradiction from Theorem 1 if we set \(\delta = c_1 / T^{c_2}\). On the other hand, in practice, GP-TS often shows superior performance. Indeed, since the constant \(c_2 = 17\) in Theorem 1, shown in Appendix 5, is highly large, Theorem 1 does not necessarily suggest the practical instability of GP-TS. This result motivates us to improve the exponent of \(1 / \delta\) in the regret upper bound. See the following proof sketch and Appendix 5 for the proof.

3.1.0.1 Proof sketch.

We derive a lower bound on probability \[\begin{align} \Pr(E_f \land E_{\epsilon} \land E_{\rm TS}) \geq c_1 / T^{c_2}, \end{align}\] where the events are defined as follows: \[\begin{align} E_f &= \left\{ f(\boldsymbol{x}^{(1)}) \geq 4 \sqrt{ \log T} \text{ and } f(\boldsymbol{x}^{(2)}) \geq f(\boldsymbol{x}^{(1)}) + 1 \right\},\\ E_{\epsilon} &= \left\{ \forall t \in [\lceil T/2 \rceil], \frac{1}{t} \sum_{i=1}^t \epsilon_i \geq - 1 \right\}, \\ E_{\rm TS} &= \left\{ \forall t \in [\lceil T/2 \rceil], \boldsymbol{x}_t = \boldsymbol{x}^{(1)} \right\}, \end{align}\] for which we leverage Lemma 5.1 of [38] shown in Lemma 4. Obviously, under these events, GP-TS suffers from \(T / 2\) regret by querying the suboptimal arm \(\boldsymbol{x}^{(1)}\) for \(T / 2\) times.

3.1.0.2 Extendability of Theorem 1.

Extending Theorem 1 to arbitrary algorithms is difficult. On the other hand, we expect similar results to hold for algorithms without tuning parameters that promote exploration, such as the confidence width parameter in GP-UCB. Indeed, the proof of Theorem 1 is inspired by Theorem 4.6 in [38], which analyzes the regret lower bound of GP-UCB with a fixed (non-increasing) confidence width parameter. Therefore, we conjecture that, without some tuning parameter or modification of the algorithm to promote exploration, the BO algorithms cannot achieve \(O(\log (1 / \delta))\) cumulative regret upper bound in general, though solving it rigorously still remains open.

3.1.0.3 Contradictions from the existing study.

[28], [29] (for example, Remark 4 of [29]) have reported the \(O\bigl(\sqrt{T \gamma_T} \log(T / \delta)\bigr)\) regret upper bound that appears to contradict Theorem 1. Their analysis in the Bayesian setting closely follows the proof technique of [14], originally developed for the frequentist setting. We conjecture that this transfer may not be fully justified, as the randomness of \(f\) could affect the validity of the argument. In particular, Eq. (11) in [28] and Eq. (18) in [29] may fail to hold in general. This is because, following the definitions in [29], the realization \(\xi_{k-1}(\boldsymbol{s}_{h, k}, \boldsymbol{b}_{h, k})\) is not necessarily smaller than the conditional expectation \(\mathbb{E}\left[\xi_{k-1}(\boldsymbol{s}_{h, k}, \boldsymbol{a}_{h, k}) \mid \boldsymbol{a}_{h, k} \notin {\cal S}_{h, k}\right]\) since the saturated set \({\cal S}_{h, k}\) and \(\boldsymbol{b}_{h, k} = \mathop{\mathrm{arg\,min}}_{\boldsymbol{a} \in {\cal A}\backslash {\cal S}_{h, k}} \xi_{k-1}(\boldsymbol{s}_{h, k}, \boldsymbol{a})\) are random. On the other hand, we believe this issue can be addressed through suitable modifications to the analysis and the algorithm, such as variance inflation, as in [14], at least for our problem setup, though it remains necessary to verify whether the proof technique of [14] extends consistently for the problem setup in [28], [29].

3.2 Improved Regret Upper Bounds Regarding \(\delta\)↩︎

We confirmed that GP-TS cannot achieve \(O(\log(1 / \delta))\) upper bounds with respect to \(\delta\) in general by Theorem 1. The best known dependence on \(\delta\) in the sublinear cumulative regret upper bound for GP-TS is \(O(\sqrt{T \gamma_T \log T} / \delta)\) [11], [13]. The following theorem tightens the dependence on \(\delta\) by showing the upper bound of the second moment of cumulative regret:

Theorem 2 (Informal). Suppose that Assumption 1 and \(|{\cal X}| < \infty\) hold or Assumptions 1 and 2 hold. Then, if Algorithm 1 runs, the following holds: \[\begin{align} \mathbb{E}\left[ R_T^2 \right] = O(T \gamma_T \log T). \end{align}\] Thus, from Markov’s inequality, we have \[\begin{align} \Pr \left( R_T = O\left( \sqrt{\frac{T \gamma_T \log T}{\delta}} \right) \right) \geq 1 - \delta, \end{align}\] for any \(\delta \in (0, 1)\).

Theorem 2 tightens the term \(1 / \sqrt{\delta}\) from the existing result \(\tilde{O}(\sqrt{T \gamma_T} / \delta)\) [11], [13] though the additional \(\log T\) factor is required in the case of \(|{\cal X}| < \infty\) compared with [13]. Furthermore, the upper bound of the second moment itself implies the concentration property of the cumulative regret incurred by GP-TS. On the other hand, we have not revealed the tightness for \(\delta\). Showing the optimal bound for \(\delta\), which maintains the sublinearity in terms of \(T\), is an interesting future work. See the following proof sketch and Appendix 6 for the formal statement of Theorem 2 and the proof.

3.2.0.1 Proof sketch.

The high-probability result follows from the upper bound on the second moment and Markov’s inequality. The proof for the upper bound of the second moment mostly follows the existing analysis [11], [13]. For simplicity, we first focus on the case of \(|{\cal X}| < \infty\). From Cauchy–Schwarz inequality and the properties of GP-TS that \((\boldsymbol{x}^* \mid {\cal D}_{t-1})\) and \((\boldsymbol{x}_t \mid {\cal D}_{t-1})\) are identically distributed and \(\boldsymbol{x}^* \mathop{\perp\!\!\!\!\perp}\boldsymbol{x}_t \mid {\cal D}_{t-1}\), we can decompose the regret similarly to [11]: \[\begin{align} \mathbb{E}[R_T^2] \lesssim T \sum_{t = 1}^T \mathbb{E}\Biggl[ \bigl( f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) \bigr)_+^2 + \beta_t \sigma_{t-1}^2(\boldsymbol{x}_t) \Biggr], \end{align}\] where \(\lesssim\) hides \(O(1)\) factors, \((c)_+ = \max\{0, c \}\), and \(U_t(\boldsymbol{x}) = \mu_{t-1}(\boldsymbol{x}) + \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x})\) with \(\beta_t = O(\log t)\). The sum of posterior variances can be bounded from above by \(\gamma_T\) [6]. On the other hand, although the upper bound \(\sum_{t = 1}^T \mathbb{E}\bigl[ \bigl( f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) \bigr)_+ \bigr] = O(1)\) is known [11], we need an upper bound of \(\mathbb{E}\bigl[\bigl( f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) \bigr)_+^2 \bigr]\) to obtain the upper bound of \(R_T^2\). Thus, we provide its upper bound in Lemma 9. For continuous input domains, for a similar reason, we provide the upper bound of squared discretization error in Lemma 10.

3.3 Lenient Regret Upper Bounds↩︎

The following theorem provides the expected lenient regret upper bound for GP-TS:

Theorem 3. Fix \(\Delta > 0\) and \(\delta \in (0, 1)\) and let \({\cal T}= \{ t \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta\}\). Suppose that Assumption 1 and \(|{\cal X}| < \infty\) hold or Assumptions 1 and 2 hold. Then, if Algorithm 1 runs, the following inequalities hold: \[\begin{align} \mathbb{E}[|{\cal T}|] &\leq T_{\rm max}, \\ \mathbb{E}\left[LR_T \right] &= O\left( \sqrt{\beta_T T_{\rm max} \tilde{\gamma}_{T_{\rm max}}} \right). \end{align}\] Here, \(T_{\rm max}\) satisfies: \[\begin{align} T_{\rm max} = \begin{cases} O \left( \frac{\beta_T d \log T}{\Delta^2} \right) & \text{if k = k_{\rm Lin}}, \\ O \left( \frac{\beta_T \log^{d + 1} T}{\Delta^2} \right) & \text{if k = k_{\rm SE}}, \\ O \left( \left( \frac{\beta_T \log^{\frac{4\nu + d}{2\nu + d}} T}{\Delta^2} \right)^{1 + \frac{d}{2\nu}} \right) & \text{if k = k_{\rm Mat}}, \end{cases} \end{align}\] where \(\beta_T = O\bigl(\log(|{\cal X}| T)\bigr)\) and \(\nu > 1 / 2\) for the case of \(|{\cal X}| < \infty\) and \(\beta_T = O\bigl( d\log(d T) \bigr)\) and \(\nu > 1\) for the case of continuous \({\cal X}\).

Theorem 3 shows that GP-TS attains a polylogarithmic upper bound on the expected lenient regret, matching the order of the existing high-probability upper bounds for GP-UCB [9], [10] in terms of \(T\). In the next section, we leverage Theorem 3 to derive an improved upper bound on the cumulative regret with respect to \(T\). We employ a different proof technique than that of [9], [10] to obtain a bound on the expectation, as an analysis of expected lenient regret has not previously appeared in the BO literature. We expect that our proof technique can be extended to obtain the Bayesian expected lenient regret upper bound for GP-UCB. See the following proof sketch and Appendix 7 for the proof.

3.3.0.1 Proof sketch.

For simplicity, we here denote the case of \(|{\cal X}| < \infty\). We employ a proof inspired by that of the elliptical potential count lemma [15], [49]. That is, we leverage the inequality \[\begin{align} |{\cal T}| &= \sum_{t \in {\cal T}} \min \left\{1, \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} \right\} \\ &\leq \sum_{t \in {\cal T}} \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta^2}, \end{align}\] which holds because \(\frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} \geq 1\) for all \(t \in {\cal T}\). Then, by applying the properties of the expectation, GP-TS, and GPs, we can obtain \[\begin{align} \mathbb{E}[|{\cal T}|] \lesssim \frac{\beta_T}{\Delta^2} \left( \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] + \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] \right), \end{align}\] where \(\lesssim\) hides \(O(1)\) factors. Thus, we need to obtain an upper bound of \(\mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] + \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right]\), which is nontrivial, especially because \(\boldsymbol{x}_t\) and \(\boldsymbol{x}^*\) are not necessarily identically distributed given the condition \({\cal D}_{t-1}\) and \(t \in {\cal T}\). Hence, we show Lemma 11, which states \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] \lesssim \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]},\\ \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] \lesssim \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}, \end{align}\] from which we obtain the upper bound of \(\mathbb{E}[|{\cal T}|]\). Regarding the upper bound of \(\mathbb{E}\left[LR_T \right]\), we can obtain \(\mathbb{E}\left[LR_T \right] \lesssim \beta_T^{1/2} \bigl( \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}^*) \right] + \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}_t) \right] \bigr)\) by the similar proof as that of [11], [13]. Then, by adopting the following inequalities shown in Lemma 11, \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}^*) \right] \lesssim \sqrt{\mathbb{E}[|{\cal T}| \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}},\\ \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}_t) \right] \lesssim \sqrt{\mathbb{E}[|{\cal T}| \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}, \end{align}\] we see that \(\mathbb{E}\left[LR_T \right] \lesssim \sqrt{\beta_T \mathbb{E}[|{\cal T}| \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}\). Therefore, combining the upper bound of \(\mathbb{E}[|{\cal T}|]\) concludes the proof. See Appendix 9 for the details of Lemma 11.

3.4 Improved Regret Upper Bound Regarding \(T\)↩︎

We show the following generalized result before obtaining the regret upper bound specific to GP-TS:

Lemma 3. Let \({\cal X}= [0, r]^d\). Suppose Assumptions 1 and 2 hold. In addition, assume the three conditions in Lemma 2 and the following event \(E\) are true: \[\begin{align} E = \left\{\forall t \in \mathbb{N}, f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \leq 2 \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}_t) + \frac{1}{t^2} \right\}, \end{align}\] where \(\{ \beta_t \}_{t \in \mathbb{N}}\) is some monotonically increasing sequence with \(\beta_t = O(\log t)\). Then, the following holds: \[\begin{align} R_T = \begin{cases} O(\sqrt{T} \log T) & \text{if k = k_{\rm SE}}, \\ \tilde{O}(\sqrt{T}) & \text{if k = k_{\rm Mat} with \nu > 2}, \end{cases} \end{align}\] where the hidden constants may depend on \(d, \nu, \ell, r, \sigma^2\), and the constants \(c_{\rm sup}, c_{\rm gap}, \rho_{\rm quad}, c_{\rm quad}\) in Lemma 2.

Since the assumption in Lemma 3 holds for GP-UCB, Lemma 3 can be applied to the analysis for GP-UCB. Notably, our result relaxes the condition on Matérn kernels from \(2\nu + d \leq \nu^2\) [10] to \(\nu > 2\) by the refined analysis, which is discussed as an open question in [10]. Fortunately, although [10] conjecture that this relaxation of the condition requires stronger regularity conditions than those in Lemma 2, we did not require such conditions. See Appendix 8 for the detailed proof, though we provide a short description about the difference from the proof of [10] and the proof sketch hereafter.

3.4.0.1 Difference from the proof of [10].

[10] showed the proof that (i) derive \(\tilde{O}(1)\) regret upper bound over the input sets distant from \(\boldsymbol{x}^*\), that is, \({\cal X}\backslash {\cal B}(\rho_{\rm quad}; \boldsymbol{x}^*)\), by the lenient regret upper bound with fixed \(\Delta\) and (ii) obtain the upper bound of regret incurred in \({\cal B}(\rho_{\rm quad}; \boldsymbol{x}^*)\) by utilizing the fact that the inputs \(\{\boldsymbol{x}_t\}_{t \in \mathbb{N}}\) concentrate around \(\boldsymbol{x}^*\) and the MIG over \({\cal B}(\rho; \boldsymbol{x}^*)\) becomes small in proportion to \(\rho\). The first difference is that we control \(\Delta\) based on \(T\) so that the resulting sum of regret is \(\tilde{O}(\sqrt{T})\). The second difference, particularly for the case of Matérn kernels, is that we repeatedly apply the arguments like the lenient regret upper bound and the property that the MIG over \({\cal B}(\rho; \boldsymbol{x}^*)\) becomes small in proportion to \(\rho\). From these differences, we can tighten the regret upper bounds in the derivation, thereby simplifying the analysis for SE kernels and relaxing the required condition for Matérn kernels.

3.4.0.2 Proof sketch.

We here concentrate on the case of Matérn kernels, since SE kernels can be handled by a simpler analysis. We divide the index set \([T]\) as \[\begin{align} {\cal T}_0 &= \{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_1 \}, \\ {\cal T}_i &= \{t \in [T] \mid \Delta_i \geq f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_{i+1} \}, \forall i \in [\bar{i} - 1], \\ {\cal T}_{\bar{i}} &= \{t \in [T] \mid \Delta_{\bar{i}} \geq f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \}, \end{align}\] where we discuss the condition of \(\bar{i} \in \mathbb{N}\) and monotonically decreasing \(\Delta_2, \dots, \Delta_{\bar{i}} > 0\) later. Roughly speaking, we tune \(\Delta_i\) so that the cumulative regret over the index set \({\cal T}_i\) can be bounded from above by \(\tilde{O}(\sqrt{T})\) and confirm that \(\bar{i}\) can be set to a finite integer even for such \(\Delta_i\). If \(\sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) = \tilde{O}(\sqrt{T})\) for all \(i = 0, \dots, \bar{i}\) with \(\tilde{i} = O(1)\), then \(R_T = \tilde{O}(\bar{i} \sqrt{T}) = \tilde{O}(\sqrt{T})\). First, we obtain the regret bounds for \({\cal T}_0\) as \(\tilde{O}(\sqrt{T})\) with \(\Delta_1 = T^{- \tfrac{\nu}{2(\nu + d)}}\) by the similar argument as the lenient regret bound. Next, for the sufficiently small \(\Delta_1\), we can derive \(\boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right)\) for all \(t \in {\cal T}_i\) and \(i \in [\bar{i}]\) by the condition 3 of Lemma 2 and Lemmas 4 and 20 of [10]. This fact suggests that the MIG for \({\cal T}_i\) for all \(i \in [\bar{i}]\) can be bounded from above in proportion to \(\sqrt{c_{\rm quad}^{-1} \Delta_i }\) based on Corollary 8 of [10]. Therefore, we can tighten the upper bound of \(|{\cal T}_i|\) for all \(i \in [\bar{i} - 1]\). In addition, we can tighten the upper bound of \(\sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\) for all \(i \in [\bar{i}]\). From these tightened upper bounds, we can see that \(\sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) = \tilde{O}(\sqrt{T})\) for all \(i \in [\bar{i}]\) if \[\begin{align} \Delta_{\bar{i}} &= O\bigl(T^{- \tfrac{1}{\nu}}\bigr), \\ \Delta_{i + 1} &= \tilde{O}\left( T^{- \tfrac{\nu}{2 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{2(\nu + d)}} \right) && \text{for all i \in [\bar{i} - 1]}. \end{align}\] Finally, we show that the above condition can be satisfied with \(\tilde{i} = O(1)\) if \(\nu > 2\) by the arguments based on the formulas for the sum of a geometric series.

From Lemma 3, we obtain the following improved cumulative regret upper bound of GP-TS:

Theorem 4. Fix \(\delta \in (0, 1)\) and \(\delta_{\rm GP} \in (0, 1)\). Assume the same premise as in Lemma 2. Suppose Assumption 2 holds. Then, if Algorithm 1 runs, the following holds with probability at least \(1 - \delta - \delta_{\rm GP}\): \[\begin{align} R_T = \begin{cases} O(\sqrt{T} \log T) & \text{if k = k_{\rm SE}}, \\ \tilde{O}(\sqrt{T}) & \text{if k = k_{\rm Mat} with \nu > 2}, \end{cases} \end{align}\] where the hidden constants may depend on \(1 / \delta, d, \nu, \ell, r, \sigma^2\), and the constants \(c_{\rm sup}, c_{\rm gap}, \rho_{\rm quad}, c_{\rm quad}\) corresponding with \(\delta_{\rm GP}\).

Theorem 4 shows that GP-TS achieves \(\tilde{O}(\sqrt{T})\) cumulative regret upper bound as with GP-UCB, which is discussed as an open question in [10]. Thus, compared with the known-best high probability cumulative regret upper bound for GP-TS \(O(\sqrt{\gamma_T T \log T} / \delta)\) [11], [13] (or \(O(\sqrt{\gamma_T T \log T / \delta})\) in Theorem 2), Theorem 4 shows the improved result with respect to \(T\). Note that, although the dependence on \(\delta\) is worse than that of GP-UCB, the dependence on \(\delta_{\rm GP}\) is almost the same. Thus, the resulting dependence on probability of GP-TS and GP-UCB may be the same since the dependence on \(\delta_{\rm GP}\) in \(c_{\rm sup}, c_{\rm gap}, \rho_{\rm quad}\) and \(c_{\rm quad}\) have not been explicitly provided. Although Lemma 3 can be applied to GP-UCB directly, its application to GP-TS requires a careful derivation since we have only shown the expected regret bounds without conditioning on the conditions in Lemma 2. See the following proof sketch and Appendix 8 for the proof.

3.4.0.3 Proof sketch.

Under the three conditions in Lemma 2, from the similar arguments as that of Lemma 3, we can decompose the cumulative regret as \[\begin{align} R_T &\leq \sum_{i = 0}^{\bar{i}} \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t), \end{align}\] where the index sets \(\widetilde{{\cal T}}_i\) are defined as \[\begin{align} \widetilde{{\cal T}}_0 &= \left\{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_{1} \right\}, \\ \widetilde{{\cal T}}_i &= \left\{ \! \! \! \! \begin{array}{l} t \in [T] \biggm| \begin{array}{l} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \ge \Delta_{i+1} \\ \land \boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1}\Delta_i}; \boldsymbol{x}^*\right) \end{array} \end{array} \! \! \! \! \! \! \right\}, \forall i \in [\bar{i} - 1], \\ \widetilde{{\cal T}}_{\bar{i}} &= \left\{t \in [T] \mid \boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_{\bar{i}} }; \boldsymbol{x}^*\right) \right\}. \end{align}\] Therefore, if we can show the expected regret upper bound \(\mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] = \tilde{O}(\sqrt{T})\) for all \(i = 0, \dots, \bar{i}\) with \(\bar{i} = O(1)\), we can obtain \(R_T = \tilde{O}(\bar{i}^2 \sqrt{T}) = \tilde{O}(\sqrt{T})\) by the union bound and almost the same proof as that of Lemma 3. We can show \(\mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] = \tilde{O}(\sqrt{T})\) for all \(i = 0, \dots, \bar{i}\) by the similar proof as those of Theorems 2 and 3 and the same \(\{\Delta_i\}_{i=1}^{\bar{i}}\) and \(\bar{i}\) as in the proof of Lemma 3.

4 Conclusion and Discussion↩︎

In this paper, we showed several regret bounds of GP-TS in the Bayesian setting. First, we constructed the simple two-armed problem instance where GP-TS suffers from \(1 / \delta^c\) regret with probability \(\delta\), which implies that \(O\bigl(\log (1 / \delta)\bigr)\) regret upper bounds cannot be obtained by GP-TS in general. Second, we showed the \(\tilde{O}(\sqrt{T \gamma_T / \delta})\) cumulative regret upper bound tighter by a \(1 / \sqrt{\delta}\) factor than the existing result. Third, we proved the polylogarithmic expected lenient regret upper bounds by the different proof from [9], [10]. Lastly, we showed the \(\tilde{O}(\sqrt{T})\) high-probability cumulative regret upper bound by extending the analysis by [10], in which we relaxed the condition of \(\nu\) and \(d\) for Matérn kernels to only \(\nu > 2\), which matches the condition needed for Lemma 2. Note that this refined analysis can readily be adapted to that of GP-UCB. Hence, Lemma 3 and Theorem 4 partially address the limitations discussed as the “Smoothness condition” and the “Extension to other algorithms” in [10].

However, our analyses still have the limitations listed below:

Optimality for \(\delta\). Although we show the regret lower bound for GP-TS in Theorem 1, it does not imply the tightness of our Theorem 2 in terms of \(\delta\). In addition, whether a similar result can be obtained for continuous \({\cal X}\) is unclear. Therefore, showing the tightness on \(\delta\) and \(T\) or a sharper concentration property of \(R_T\) incurred by GP-TS for both finite and continuous input domains remains as future work.
Analysis of GP-TS with variance inflation. We conjecture that GP-TS with variance inflation [14] can attain an \(O(\sqrt{T \gamma_T \log(T / \delta)})\) cumulative regret upper bound by almost the same proof as that in the frequentist setting [14]. However, we expect that extending the analysis by [14] to the polylogarithmic lenient regret upper bound is not straightforward because of the use of the Azuma–Hoeffding inequality that causes \(\tilde{O}(\sqrt{T})\) dependence. This difficulty also hinders the application of the analysis of the improved regret upper bound on \(T\). An analysis of such a modified algorithm may be an important direction for achieving a regret upper bound with improved dependence on \(\delta\) of GP-TS.
Condition on \(\nu\) and \(d\) for Matérn kernels. We have relaxed the condition for Matérn kernels on \(\nu\) and \(d\) from \(2\nu + d \leq \nu^2\) [10] to \(\nu > 2\) in Lemma 3 and Theorem 4. This condition \(\nu > 2\) is also currently needed as the sufficient condition of Assumption 2 and Lemma 2, which is leveraged in most prior works [6], [10], [18]. However, this condition \(\nu > 2\) cannot be satisfied by the widely used value \(\nu = 1/2\) or \(3/2\). Therefore, it is crucial to determine whether the condition \(\nu > 2\) cannot be avoided or if this condition can be further relaxed.
Extension to other algorithms. As discussed in Section 1.1, there are several algorithms except for GP-UCB and GP-TS with the \(\tilde{O}(\sqrt{T \gamma_T})\) expected cumulative regret upper bounds [7], [13], [38], [39]. Therefore, extending our analyses to those algorithms would be an intriguing future direction.
Extension to other problem setup. Although we and [10] focused on the analysis of vanilla BO algorithms, BO has been extended to various problem settings, including multi-fidelity [50]–[53], multi-objective [25], [54], [55], constrained [23], and parallel BO [12], [22]. Thus, extending our analysis to these settings would be of interest to investigate the theoretical performance of BO algorithms.
Limitations discussed in prior work. The limitations named as “Optimality,” “Extension to the expected regret,” and “Instance dependence analysis in the frequentist setting” discussed in Section 4 of [10] still remain as interesting directions for future work.

Acknowledgements↩︎

This work was supported by JST PRESTO Grant Number JPMJPR24J6 and JSPS KAKENHI Grant Number JP24K20847.

5 Proof of Theorem 1 ↩︎

@title 1. Assume that \({\cal X}= \{ \boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)} \}\), \(\epsilon_t \sim {\cal N}(0, 1)\) for all \(t \in [T]\), and \[\begin{align} \left( \begin{array}{c} f(\boldsymbol{x}^{(1)}) \\ f(\boldsymbol{x}^{(2)}) \end{array} \right) \sim {\cal N}\left( \left( \begin{array}{c} 0 \\ 0 \end{array} \right), \left( \begin{array}{cc} 1 & 1 / 2 \\ 1 / 2 & 1 \end{array} \right) \right). \end{align}\] Then, if Algorithm 1 runs and \(T > e\), the following holds: \[\begin{align} \Pr\left( R_T \geq T / 2 \right) \geq \frac{c_1}{T^{c_2}}, \end{align}\] where \(c_1\) and \(c_2\) are strictly positive constants.

Proof. We show that the probability that the following events simultaneously hold can be bounded from below by \(\frac{c_1}{T^{17}}\): \[\begin{align} E_f &= \left\{ f(\boldsymbol{x}^{(1)}) \geq 4 \sqrt{ \log T} \text{ and } f(\boldsymbol{x}^{(2)}) \geq f(\boldsymbol{x}^{(1)}) + 1 \right\},\\ E_{\epsilon} &= \left\{ \forall t \in [\lceil T/2 \rceil], \frac{1}{t} \sum_{i=1}^t \epsilon_i \geq - 1 \right\}, \\ E_{\rm TS} &= \left\{ \forall t \in [\lceil T/2 \rceil], \boldsymbol{x}_t = \boldsymbol{x}^{(1)} \right\}. \end{align}\] If these events simultaneously hold, we can see that \(\sum_{t=1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq T / 2\), which concludes the proof.

5.0.0.1 Probability of \(E_f\):

From the assumption, we can see that \(\bigl(f(\boldsymbol{x}^{(1)}), f(\boldsymbol{x}^{(2)}) \bigr)\) and \((Z_0 + Z_1, Z_0 + Z_2)\) are identically distributed, where \(Z_0, Z_1\), and \(Z_2\) are independent and identically distributed as \({\cal N}(0, 1/2)\). Thus, we can rephrase the probability as \[\begin{align} \Pr\left( f(\boldsymbol{x}^{(1)}) \geq 4 \sqrt{ \log T} \text{ and } f(\boldsymbol{x}^{(2)}) \geq f(\boldsymbol{x}^{(1)}) + 1 \right) &= \Pr\left( Z_0 + Z_1 \geq 4 \sqrt{ \log T} \text{ and } Z_2 - Z_1 \geq 1 \right) \\ &\geq \Pr\left( Z_0 \geq 4 \sqrt{ \log T}\right) \Pr\left( Z_2 - Z_1 \geq 1 \text{ and } Z_1 \geq 0 \right). \end{align}\] Since \(\Pr\left( Z_2 - Z_1 \geq 1 \text{ and } Z_1 \geq 0 \right)\) does not depend on any variables, we treat it as a constant. Furthermore, using Gaussian anti-concentration inequality \(1 - \Phi(c) \geq \frac{1}{\sqrt{2\pi}} \frac{c}{c^2 + 1} \exp (- c^2 / 2)\), we can obtain the lower bound of \(\Pr\left( \sqrt{2} Z_0 \geq 4 \sqrt{2 \log T}\right)\): \[\begin{align} \Pr\left( Z_0 \geq 4 \sqrt{ \log ( T )}\right) &\geq \frac{1}{\sqrt{2\pi}} \frac{4 \sqrt{2 \log T}}{32 \log T + 1} \exp (- 16 \log T) \\ &\geq \frac{1}{\sqrt{2\pi}} \frac{4 \sqrt{2 \log T}}{32 \log T + 1} T^{-16}. \end{align}\] Hence, by choosing sufficiently small \(c_f > 0\), we can obtain \[\begin{align} \Pr\left( f(\boldsymbol{x}^{(1)}) \geq 4 \sqrt{ \log T} \text{ and } f(\boldsymbol{x}^{(2)}) \geq f(\boldsymbol{x}^{(1)}) + 1 \right) &\geq c_f T^{-17}. \end{align}\]

5.0.0.2 Probability of \(E_{\epsilon}\):

We apply Lemma D.1 of [38]:

Lemma 4 (Lemma D.1 of [38]). Let \(\{\epsilon_i\}_{i \geq 1}\) be a mutually independent sequence of standard normal random variables, that is, \(\epsilon_i \sim {\cal N}(0, 1)\) for all \(i \geq 1\). Then, there exists a positive constant \(C\) such that \[\begin{align} \Pr\left( \forall t \leq T, \frac{\sum_{i=1}^t \epsilon_i}{t} \geq -1 \right) \geq C. \end{align}\]

Therefore, \(\Pr(E_{\epsilon}) \geq c_{\epsilon}\) with some absolute constant \(c_{\epsilon} > 0\).

5.0.0.3 Probability of \(E_{\rm TS}\):

For the first iteration, \(\Pr(\boldsymbol{x}_1 = \boldsymbol{x}^{(1)} \mid E_f \land E_\epsilon) = \Pr(\boldsymbol{x}_1 = \boldsymbol{x}^{(1)}) = 1/2\) since \({\cal D}_0 = \emptyset\), the prior mean is zero, and the algorithm is independent of \(f\) and \(\epsilon\). We will show \[\begin{align} \Pr(\boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \mid E_f \land E_\epsilon \land E_t) &\geq 1 / 2 && \text{for all t \in [9]}, \\ \Pr(\boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \mid E_f \land E_\epsilon \land E_t) &\geq 1 - 1 / T && \text{for all t \in \{10, \dots, \lceil T / 2 \rceil \}}, \end{align}\] where the event \(E_t = \{ \forall i \in [t], \boldsymbol{x}_i = \boldsymbol{x}^{(1)} \}\) and \(10\) is chosen for simplicity. Then, we can show the probability that \(\boldsymbol{x}^{(1)}\) is chosen successively \(\lceil T / 2 \rceil\) times can be bounded from below by an absolute constant.

First, we show \(\Pr(\boldsymbol{x}_{t+1} = \boldsymbol{x}^{(1)} \mid E_f \land E_\epsilon \land E_t) \geq 1/2\) for \(t \in [9]\). If \(E_t\) is true, the posterior distribution of \(\bigl(f(\boldsymbol{x}^{(1)}), f(\boldsymbol{x}^{(2)}) \bigr)\) given \({\cal D}_t\) can be obtained as \[\begin{align} {\cal N}\left( \left( \begin{array}{c} \frac{t}{t+1} \bar{y}_t \\ \frac{t}{2(t+1)} \bar{y}_t \end{array} \right), \left( \begin{array}{cc} \frac{1}{t+1} & \frac{1}{2(t+1)} \\ \frac{1}{2(t+1)} & \frac{3t/4 + 1}{t+1} \end{array} \right) \right), \end{align}\] where \(\bar{y}_t = \frac{1}{t} \sum_{i=1}^{t} y_i = f(\boldsymbol{x}^{(1)}) + \frac{1}{t} \sum_{i=1}^{t} \epsilon_i\). Note that we use the Woodbury formula \((\boldsymbol{1} \boldsymbol{1}^\top + \boldsymbol{I}_t)^{-1} = \boldsymbol{I}_t - \frac{\boldsymbol{1} \boldsymbol{1}^\top}{t + 1}\) as with the proof of Theorem 4.6 in [38]. Therefore, we can obtain the posterior distribution of \(f(\boldsymbol{x}^{(2)}) - f(\boldsymbol{x}^{(1)})\) as \[\begin{align} {\cal N}\left( - \frac{t}{2(t+1)} \bar{y}_t, \frac{3t/4 + 1}{t+1} \right). \end{align}\] Hence, for any \({\cal D}_t\) that satisfies \(E_t\), we can obtain \[\begin{align} \Pr(\boldsymbol{x}_{t+1} = \boldsymbol{x}^{(1)} \mid {\cal D}_t) = \Phi\left( \frac{t \bar{y}_t}{2 \sqrt{t+1} \sqrt{3t/4 + 1}} \right). \end{align}\] If \(E_f\) and \(E_{\epsilon}\) are true, then \(\bar{y}_t \geq 0\) because \(f(\boldsymbol{x}^{(1)}) \geq 4 \sqrt{\log T}\), \(\frac{1}{t} \sum_{i=1}^T \epsilon_i \geq -1\) and \(T > e\). Hence, we see that \[\begin{align} &\Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| E_f \land E_\epsilon \land E_t \right) \\ &= \mathbb{E}_{{\cal D}_t \mid E_f \land E_\epsilon \land E_t} \left[ \Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| {\cal D}_t \land E_f \land E_\epsilon \land E_t \right) \right] \\ &\overset{(a)}{=} \mathbb{E}_{{\cal D}_t \mid E_f \land E_\epsilon \land E_t} \left[ \Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| {\cal D}_t \right) \right] \\ &\overset{(b)}{\geq} 1 / 2, \end{align}\] which holds because (a) \(\{\boldsymbol{x}_i\}_{i \leq t}\) is fixed given \({\cal D}_t\) and \(\boldsymbol{x}_{t + 1} \mathop{\perp\!\!\!\!\perp}f, \{\epsilon_t\}_{t \geq 1} \mid {\cal D}_t\) and (b) \(\bar{y}_t \geq 0\) under the conditions \(E_f, E_\epsilon\), and \(E_t\).

Next, we obtain the lower bound \(\Pr(\boldsymbol{x}_{t+1} = \boldsymbol{x}^{(1)} \mid E_f, E_{\epsilon}, E_t) \geq 1 - 1 / T\) for all \(t \geq 10\). If \(E_f, E_\epsilon\), and \(E_t\) are true, then we see that \[\begin{align} \frac{1}{t} \sum_{i = 1}^t \epsilon_i &\overset{(a)}{\geq} -1 \\ &\overset{(b)}{\geq} 2\sqrt{2 \log\left(\frac{T}{2}\right)} - 4 \sqrt{\log T} \\ &\overset{(c)}{\geq} 2\sqrt{2 \log\left(\frac{T}{2}\right)} - f(\boldsymbol{x}^{(1)}) \\ &\overset{(d)}{\geq} \frac{2\sqrt{t + 1}\sqrt{3t / 4 + 1}}{t} \sqrt{2 \log \left(\frac{T}{2}\right)} - f(\boldsymbol{x}^{(1)}), \end{align}\] where the inequalities hold because (a) \(E_\epsilon\) is true, (b) \(g(T) = 2\sqrt{2 \log\left(\frac{T}{2}\right)} - 4 \sqrt{\log T}\) has the maximum \(g(4) \approx - 2.354\) at \(T = 4\) since \(g^\prime (T) = \frac{2}{T} \left(\frac{1}{\sqrt{2 \log (T / 2)}} - \frac{1}{\sqrt{\log T}} \right)\), (c) \(E_f\) is true, and (d) \(g(t) = \frac{2\sqrt{t + 1}\sqrt{3t / 4 + 1}}{t} = \frac{\sqrt{t + 1}\sqrt{3t + 4}}{t}\) is monotonically decreasing for \(t > 0\) and \(g(t) \leq g(10) \approx 1.934 \leq 2\) for \(t \geq 10\) (note that \(\log(T / 2) > 0\) due to \(T > e\)). Therefore, we obtain \[\begin{align} &\bar{y}_t = f(\boldsymbol{x}^{(1)}) + \frac{1}{t} \sum_{i = 1}^t \epsilon_i \geq \frac{2\sqrt{t + 1}\sqrt{3t / 4 + 1}}{t} \sqrt{2 \log \left(\frac{T}{2}\right)} \\ &\Leftrightarrow \frac{t \bar{y}_t}{2 \sqrt{t+1} \sqrt{3t/4 + 1}} \geq \sqrt{2 \log \left(\frac{T}{2}\right)}. \end{align}\] Hence, as with the case of \(t \in [9]\), for any \({\cal D}_t\) that satisfies \(E_f, E_\epsilon\), and \(E_t\), we see that \[\begin{align} \Pr(\boldsymbol{x}_{t+1} = \boldsymbol{x}^{(1)} \mid {\cal D}_t) &= \Phi\left( \frac{t \bar{y}_t}{2 \sqrt{t+1} \sqrt{3t/4 + 1}} \right) \\ &\geq \Phi\left( \sqrt{2 \log \left(\frac{T}{2}\right)} \right) \\ &\geq 1 - \frac{1}{T}, \end{align}\] where we use the inequality \(\Phi(c) \geq 1 - \frac{1}{2} e^{- c^2 / 2}\) [6]. Thus, for any \(t \geq 10\), we derive \[\begin{align} &\Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| E_f \land E_\epsilon \land E_t \right) \\ &= \mathbb{E}_{{\cal D}_t \mid E_f \land E_\epsilon \land E_t} \left[ \Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| {\cal D}_t \land E_f \land E_\epsilon \land E_t \right) \right] \\ &\overset{(a)}{=} \mathbb{E}_{{\cal D}_t \mid E_f \land E_\epsilon \land E_t} \left[ \Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| {\cal D}_t \right) \right] \\ &\geq 1 - 1 / T, \end{align}\] where the inequality (a) holds because \(\{\boldsymbol{x}_i\}_{i \leq t}\) is fixed given \({\cal D}_t\) and \(\boldsymbol{x}_{t + 1} \mathop{\perp\!\!\!\!\perp}f, \{\epsilon_t\}_{t \geq 1} \mid {\cal D}_t\).

Consequently, we see that \[\begin{align} \Pr(E_{\rm TS} \mid E_f \land E_{\epsilon}) &= \Pr\left( \forall t \in [\lceil T / 2 \rceil] , \boldsymbol{x}_t = \boldsymbol{x}^{(1)} \mid E_f \land E_{\epsilon} \right) \\ &= \Pr(\boldsymbol{x}_1 = \boldsymbol{x}^{(1)} \mid E_f \land E_{\epsilon}) \prod_{t = 1}^{\lceil T / 2 \rceil} \Pr\left( \boldsymbol{x}_{t + 1} = \boldsymbol{x}^{(1)} \bigm| E_f \land E_\epsilon \land E_t \right) \\ &\geq \frac{1}{2^{10}} \left(1 - \frac{1}{T}\right)^{\max\{\lceil T / 2 \rceil - 10, 0 \}} \\ &\geq \frac{1}{2^{10}} \left(1 - \frac{1}{T}\right)^{T / 2} \\ &\geq \frac{1}{2^{11}} \eqqcolon c_{\rm TS}, \end{align}\] where the second equality follows by the repeated applications of Bayes-rule, and the last inequality follows from Bernoulli’s inequality \((1 + c)^r \geq 1 + rc\) for all integer \(r \geq 1\) and \(c \geq -1\).

5.0.0.4 Resulting lower bound:

Combining all the lower bounds for the probability, since \(E_f \land E_\epsilon \land E_{\rm TS} \Rightarrow \sum_{t=1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq T / 2\), we can see that \[\begin{align} \Pr\left( \sum_{t=1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq T / 2 \right) &\geq \Pr(E_f \land E_\epsilon \land E_{\rm TS}) \\ &= \Pr(E_{\rm TS} \mid E_f \land E_\epsilon) \Pr(E_f) \Pr(E_\epsilon) \\ &\geq \frac{c_f c_{\epsilon} c_{\rm TS}}{T^{17}}. \end{align}\] ◻

6 Proof of Theorem 2 ↩︎

Here, we show the proof of the formal version of Theorem 2:

Theorem 5. If Algorithm 1 runs, the following inequality holds:

If Assumption 1 holds and \(|{\cal X}| < \infty\), \[\begin{align} \mathbb{E}\left[ R_T^2 \right] &\leq 12 C_1 T (\beta_T + 1) \gamma_T + \beta_T^{1/2} = O(T \beta_T \gamma_T), \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\) and \(\beta_t = \max\{1, 2\log ( 24 |{\cal X}| T^2 / \sqrt{2 \pi} )\}\) for all \(t \in [T]\).
If Assumptions 1 and 2 hold and \(\nu > 1\) for Matérn kernels, \[\begin{align} \mathbb{E}[R_T^2] \leq 27 + \beta_T^{1/2} + 18T (\beta_T + 1) \left(2 + C_1 \gamma_T\right) = O(T \beta_T \gamma_T), \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\), \(\beta_t = \max\{1, 2\log \bigl( 36 \lceil drL T \rceil^d T^2 / \sqrt{2 \pi} ) \bigr)\}\) for all \(t \in [T]\), \(L = \max\{ L_{\sigma}, b\sqrt{\log (ad) + 1} \}\) and \(L_{\sigma}\) is defined as in Lemma 1.

Proof. Let \(U_t(\boldsymbol{x}) = \mu_{t-1}(\boldsymbol{x}) + \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x})\) and \((a)_+ = \max\{0, a \}\).

First, we consider the case of \(|{\cal X}| < \infty\). We can obtain \[\begin{align} \mathbb{E}\left[ R_T^2 \right] &\leq \mathbb{E}\left[ \left( \sum_{t=1}^T f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) + U_t(\boldsymbol{x}^*) - g_t(\boldsymbol{x}^*) + g_t(\boldsymbol{x}_t) - U_t(\boldsymbol{x}_t) + U_t(\boldsymbol{x}_t) - f(\boldsymbol{x}_t) \right)^2 \right] \\ &\leq \mathbb{E}\left[ \left( \sum_{t=1}^T \bigl(f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*)\bigr)_+ + U_t(\boldsymbol{x}^*) - g_t(\boldsymbol{x}^*) + \bigl(g_t(\boldsymbol{x}_t) - U_t(\boldsymbol{x}_t)\bigr)_+ + U_t(\boldsymbol{x}_t) - f(\boldsymbol{x}_t) \right)^2 \right], \end{align}\] which holds because \(g_t(\boldsymbol{x}_t) \geq g_t(\boldsymbol{x}^*)\) from the nature of GP-TS and \(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq 0\) for all \(t \in [T]\). Furthermore, by the Cauchy-Schwarz inequality, we obtain \[\begin{align} \mathbb{E}\left[ R_T^2 \right] \leq 6T \sum_{t = 1}^T \mathbb{E}& \biggl[ \bigl( f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) \bigr)_+^2 + \beta_t \sigma_{t-1}^2(\boldsymbol{x}^*) + \bigl( \mu_{t-1} (\boldsymbol{x}^*) - g_t(\boldsymbol{x}^*) \bigr)^2 \\ &+ \bigl( g_t(\boldsymbol{x}_t) - U_t(\boldsymbol{x}_t) \bigr)_+^2 + \beta_t \sigma_{t-1}^2(\boldsymbol{x}_t) + \bigl( \mu_{t-1} (\boldsymbol{x}_t) - f(\boldsymbol{x}_t) \bigr)^2 \biggr]. \end{align}\] From the independence \(\boldsymbol{x}_t \mathop{\perp\!\!\!\!\perp}f \mid {\cal D}_{t-1}\) and \(\boldsymbol{x}^* \mathop{\perp\!\!\!\!\perp}g_t \mid {\cal D}_{t-1}\) for all \(t \in [T]\), we see that \[\begin{align} \mathbb{E}\left[\bigl( \mu_{t-1} (\boldsymbol{x}^*) - g_t(\boldsymbol{x}^*) \bigr)^2 \right] &= \mathbb{E}\left[ \mathbb{E}\left[\bigl( \mu_{t-1} (\boldsymbol{x}^*) - g_t(\boldsymbol{x}^*) \bigr)^2 \mid \boldsymbol{x}^*, {\cal D}_{t-1} \right] \right] =\mathbb{E}\left[\sigma_{t-1}^2 (\boldsymbol{x}^*)\right], \\ \mathbb{E}\left[\bigl( \mu_{t-1} (\boldsymbol{x}_t) - f(\boldsymbol{x}_t) \bigr)^2 \right] &= \mathbb{E}\left[ \mathbb{E}\left[ \bigl(\mu_{t-1} (\boldsymbol{x}_t) - f(\boldsymbol{x}_t) \bigr)^2 \mid \boldsymbol{x}_t, {\cal D}_{t-1} \right] \right] = \mathbb{E}\left[ \sigma_{t-1}^2(\boldsymbol{x}_t) \right]. \end{align}\] In addition, since \(\boldsymbol{x}_t \mid {\cal D}_{t-1}\) and \(\boldsymbol{x}^* \mid {\cal D}_{t-1}\) are identically distributed from the nature of GP-TS, we obtain \(\mathbb{E}\left[\sigma_{t-1}^2 (\boldsymbol{x}^*)\right] = \mathbb{E}\left[ \sigma_{t-1}^2(\boldsymbol{x}_t) \right]\). Hence, we derive \[\begin{align} \mathbb{E}\left[ R_T^2 \right] \leq 6T \sum_{t = 1}^T \mathbb{E}\left[ \underbrace{\bigl( f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) \bigr)_+^2 + \bigl( g_t(\boldsymbol{x}_t) - U_t(\boldsymbol{x}_t) \bigr)_+^2}_{A_1} + \underbrace{2(\beta_t + 1) \sigma_{t-1}^2(\boldsymbol{x}_t)}_{A_2} \right]. \end{align}\]

Regarding the term \(A_1\), from Lemma 9, we see that \[\begin{align} 6T \sum_{t = 1}^T \mathbb{E}\biggl[ \bigl( f(\boldsymbol{x}^*) - U_t(\boldsymbol{x}^*) \bigr)_+^2 + \bigl( g_t(\boldsymbol{x}_t) - U_t(\boldsymbol{x}_t) \bigr)_+^2 \biggr] &\leq 12T \sum_{t=1}^T \frac{2\beta_t^{1/2}}{24T^2} = \beta_T^{1/2}. \end{align}\] Regarding the term \(A_2\), since \(\sum_{t=1}^T \sigma_{t-1}^2 (\boldsymbol{x}_t) \leq C_1 \gamma_T\) [6], we obtain \[\begin{align} 6T \sum_{t = 1}^T \mathbb{E}\left[ 2(\beta_t + 1) \sigma_{t-1}^2(\boldsymbol{x}_t) \right] &\leq 12 C_1 T (\beta_T + 1) \gamma_T. \end{align}\] Consequently, we derive the following desired result: \[\begin{align} \mathbb{E}\left[ R_T^2 \right] &\leq 12 C_1 T (\beta_T + 1) \gamma_T + \beta_T^{1/2} = O(T \beta_T \gamma_T). \end{align}\]

Second, we consider the case of \({\cal X}\subset [0, r]^d\). Purely for the sake of analysis, we consider equally divided grid points \({\cal X}_t\), where the grid size for each dimension is \(\tau_t = \lceil d r L T \rceil\), \(|{\cal X}_t| = \tau_t^d\), and \(L = \max\{ b (\sqrt{\log (ad) + 1}), L_\sigma \}\) with \(L_\sigma\) defined in Lemma 1. We denote \([\boldsymbol{x}]_t = \mathop{\mathrm{arg\,min}}_{\boldsymbol{x}^\prime \in {\cal X}_t} \| \boldsymbol{x} - \boldsymbol{x}^\prime \|_1\). Therefore, \(\sup_{\boldsymbol{x} \in {\cal X}} \| \boldsymbol{x} - [\boldsymbol{x}]_t \|_1 \leq \frac{1}{LT}\).

Since \(g_t(\boldsymbol{x}_t) \geq g_t([\boldsymbol{x}^*]_t)\), we can obtain \[\begin{align} \mathbb{E}\left[ R_T^2 \right] \leq \mathbb{E}\biggl[& \biggl( \sum_{t=1}^T f(\boldsymbol{x}^*) - f([\boldsymbol{x}^*]_t) + f([\boldsymbol{x}^*]_t) - U_t([\boldsymbol{x}^*]_t) + U_t([\boldsymbol{x}^*]_t) - g_t([\boldsymbol{x}^*]_t) + g_t(\boldsymbol{x}_t) - g_t([\boldsymbol{x}_t]_t) \\& + g_t([\boldsymbol{x}_t]_t) - U_t([\boldsymbol{x}_t]_t) + U_t([\boldsymbol{x}_t]_t) - f([\boldsymbol{x}_t]_t) + f([\boldsymbol{x}_t]_t) - f(\boldsymbol{x}_t) \biggr)^2 \biggr] \\ \leq 9T \sum_{t=1}^T \mathbb{E}\biggl[& \underset{A_1}{\underline{\bigl( f(\boldsymbol{x}^*) - f([\boldsymbol{x}^*]_t) \bigr)^2 + \bigl( g_t(\boldsymbol{x}_t) - g_t([\boldsymbol{x}_t]_t) \bigr)^2 + \bigl( f([\boldsymbol{x}_t]_t) - f(\boldsymbol{x}_t) \bigr)^2}} \\ &+ \underset{A_2}{\underline{\bigl( f([\boldsymbol{x}^*]_t) - U_t([\boldsymbol{x}^*]_t) \bigr)_+^2 + \bigl( g_t([\boldsymbol{x}_t]_t) - U_t([\boldsymbol{x}_t]_t) \bigr)_+^2}} \\ &+ \underset{A_3}{\underline{\bigl( \mu_{t-1}([\boldsymbol{x}^*]_t) - g_t([\boldsymbol{x}^*]_t) \bigr)^2 + \bigl( \mu_{t-1}([\boldsymbol{x}_t]_t) - f([\boldsymbol{x}_t]_t) \bigr)^2 + \beta_t \sigma_{t-1}^2([\boldsymbol{x}^*]_t) + \beta_t \sigma_{t-1}^2([\boldsymbol{x}_t]_t) }} \biggr]. \end{align}\] For the term \(A_1\), from Lemma 10, \[\begin{align} 9T \sum_{t=1}^T \mathbb{E}\biggl[ \bigl( f(\boldsymbol{x}^*) - f([\boldsymbol{x}^*]_t) \bigr)^2 + \bigl( g_t(\boldsymbol{x}_t) - g_t([\boldsymbol{x}_t]_t) \bigr)^2 + \bigl( f([\boldsymbol{x}_t]_t) - f(\boldsymbol{x}_t) \bigr)^2 \biggr] &\leq 27T \sum_{t=1}^T \frac{1}{T^2} = 27. \end{align}\] Note that, since \(g_t\) and \(f\) are identically distributed, we can apply Lemma 10 to \(g_t\). For the term \(A_2\), as with the case of \(|{\cal X}| < \infty\), from Lemma 9 \[\begin{align} 9T \sum_{t=1}^T \mathbb{E}\biggl[ \bigl( f([\boldsymbol{x}^*]_t) - U_t([\boldsymbol{x}^*]_t) \bigr)_+^2 + \bigl( g_t([\boldsymbol{x}_t]_t) - U_t([\boldsymbol{x}_t]_t) \bigr)_+^2 \biggr] &\leq 18T \sum_{t=1}^T \frac{2 \beta_t^{1/2}}{36T^2} = \beta_T^{1/2}. \end{align}\] For the term \(A_3\), as with the case of \(|{\cal X}| < \infty\) \[\begin{align} &9T \sum_{t=1}^T \mathbb{E}\biggl[ \bigl( \mu_{t-1}([\boldsymbol{x}^*]_t) - g_t([\boldsymbol{x}^*]_t) \bigr)^2 + \bigl( \mu_{t-1}([\boldsymbol{x}_t]_t) - f([\boldsymbol{x}_t]_t) \bigr)^2 + \beta_t \sigma_{t-1}^2([\boldsymbol{x}^*]_t) + \beta_t \sigma_{t-1}^2([\boldsymbol{x}_t]_t) \biggr] \\ &\leq 18T (\beta_T + 1) \sum_{t=1}^T \mathbb{E}\biggl[ \sigma_{t-1}^2([\boldsymbol{x}_t]_t) \biggr]. \end{align}\] From Lemma 1 and \(\sigma_{t-1}(\boldsymbol{x}) \leq 1\) for all \(\boldsymbol{x} \in {\cal X}\), we see that for any \(t \geq 1\) and \({\cal D}_{t-1}\), \[\begin{align} \forall \boldsymbol{x}, \boldsymbol{x}^\prime \in {\cal X}, |\sigma_{t-1}^2(\boldsymbol{x}) - \sigma_{t-1}^2(\boldsymbol{x}^\prime)| \leq |\sigma_{t-1}(\boldsymbol{x}) + \sigma_{t-1}(\boldsymbol{x}^\prime)| |\sigma_{t-1}(\boldsymbol{x}) - \sigma_{t-1}(\boldsymbol{x}^\prime)| \leq 2 L _{\sigma} \| \boldsymbol{x} - \boldsymbol{x}^\prime \|_1. \end{align}\] Thus, from \(\sum_{t=1}^T \sigma_{t-1}^2 (\boldsymbol{x}_t) \leq C_1 \gamma_T\) [6] and the definition of \({\cal X}_t\), we obtain \[\begin{align} \sum_{t=1}^T \mathbb{E}\biggl[ \sigma_{t-1}^2([\boldsymbol{x}_t]_t) \biggr] &\leq \sum_{t=1}^T \mathbb{E}\biggl[ |\sigma_{t-1}^2([\boldsymbol{x}_t]_t) - \sigma_{t-1}^2(\boldsymbol{x}_t)| + \sigma_{t-1}^2(\boldsymbol{x}_t) \biggr] \\ &\leq \sum_{t=1}^T \frac{2}{T} + \sum_{t=1}^T \mathbb{E}\biggl[ \sigma_{t-1}^2(\boldsymbol{x}_t) \biggr] \\ &\leq 2 + C_1 \gamma_T. \end{align}\] Combining all the results, we see that \[\begin{align} \mathbb{E}[R_T^2] \leq 27 + \beta_T^{1/2} + 18T (\beta_T + 1) \left(2 + C_1 \gamma_T\right) = O(T \beta_T \gamma_T). \end{align}\] ◻

7 Proof of Theorem 3 ↩︎

First, we show the following general theorem to show the kernel-specific results in Theorem 3.

Theorem 6. Fix \(\Delta > 0\) and let \({\cal T}= \{ t \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta\}\). Then, if Algorithm 1 runs, the following inequality holds for any \(T \geq 2\):

If Assumption 1 holds and \(|{\cal X}| < \infty\), \[\begin{align} \mathbb{E}[|{\cal T}|] \leq T_{\rm max} \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{T_{\rm max}}}{\Delta^2} + \frac{1}{T}, \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\), \(T_{\rm max} = \max\{ t \in \mathbb{R}_{\geq 0} \mid t \leq \frac{32 C_1 \beta_T \tilde{\gamma}_t}{\Delta^2} + \frac{1}{T}\}\), and \(\beta_t = 2\log (2|{\cal X}| T^2 t (t+1))\)
If Assumptions 1 and 2 hold, \[\begin{align} \mathbb{E}[|{\cal T}|] \leq T_{\rm max} \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{T_{\rm max}}}{\Delta^2} + \frac{8 \pi^2 (\beta_T^{1/2} + 1)^2}{\Delta^2} + \frac{1}{T}, \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\), \(T_{\rm max} = \max\{ t \in \mathbb{R}_{\geq 0} \mid t \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{t}}{\Delta^2} + \frac{8 \pi^2 (\beta_T^{1/2} + 1)^2}{\Delta^2} + \frac{1}{T}\}\), and \(\beta_t = 2\log (2 \lceil dr L t \rceil^d T^2 t (t+1))\), and \(L = \max\{ b \sqrt{\log (2ad T^2)}, L_\sigma \}\) with \(L_\sigma\) defined in Lemma 1.

Proof. First, we consider the case of \(|{\cal X}| < \infty\). We define the event for the credible intervals of \(f\) and \(g_t\): \[\begin{align} E = \left\{ \forall t \geq 1, \forall \boldsymbol{x} \in {\cal X}, |f(\boldsymbol{x}) - \mu_{t-1}(\boldsymbol{x})| \leq \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}), |g_t(\boldsymbol{x}) - \mu_{t-1}(\boldsymbol{x})| \leq \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}) \right\}, \end{align}\] where \(\beta_t = 2\log (2|{\cal X}| T^2 t (t+1) )\). We denote a complementary event of \(E\) as \(E^c\). Then, using Lemma 5 (Lemma 5.1 of [6]) and the union bound, \(\Pr(E^c) \leq 1 / T^2\). Therefore, we can see that \[\begin{align} \mathbb{E}[|{\cal T}|] &= \mathbb{E}[|{\cal T}| \mid E] \Pr(E) + \mathbb{E}[|{\cal T}| \mid E^c] \Pr(E^c) \\ &\leq \mathbb{E}[|{\cal T}| \mid E] + \frac{1}{T}, \end{align}\] where the inequality holds because \(\Pr(E) \leq 1\), \(\mathbb{E}[|{\cal T}| \mid E^c] \leq T\), and \(\Pr(E^c) \leq 1 / T^2\).

Regarding \(\mathbb{E}[|{\cal T}| \mid E]\), as with the proof of the elliptical potential count lemma [15], [49], we can obtain the upper bound as follows: \[\begin{align} \mathbb{E}[|{\cal T}| \mid E] &= \mathbb{E}\left[ \sum_{t \in {\cal T}} \min \left\{1, \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} \right\} \biggm| E \right] \\ &\overset{(a)}{\leq} \mathbb{E}\left[ \sum_{t \in {\cal T}} \min \left\{1, \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta^2} \right\} \biggm| E \right] \\ &\leq \mathbb{E}\left[ \sum_{t \in {\cal T}} \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta^2} \biggm| E \right] \\ &\overset{(b)}{\leq} \frac{1}{\Delta^2} \mathbb{E}\left[ \sum_{t \in {\cal T}} 4 \beta_t \bigl( \sigma_{t-1}(\boldsymbol{x}^*) + \sigma_{t-1}(\boldsymbol{x}_t)\bigr)^2 \biggm| E \right] \\ &\overset{(c)}{\leq} \frac{8 \beta_T}{\Delta^2} \left( \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \biggm| E \right] + \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t)\bigr) \biggm| E \right] \right) \\ &\overset{(d)}{\leq} \frac{16 \beta_T}{\Delta^2} \left( \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] + \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] \right), \end{align}\] where the inequalities hold because of (a) \(\frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} \geq 1\) for \(t \in {\cal T}\), (b) \(f(\boldsymbol{x}_t) + 2 \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}_t) \geq g_t(\boldsymbol{x}_t) \geq g_t(\boldsymbol{x}^*) \geq f(\boldsymbol{x}^*) - 2 \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}^*)\) due to the conditioning by \(E\) and the nature of GP-TS, (c) \((a + b)^2 \leq 2(a^2 + b^2)\) for any \(a, b \in \mathbb{R}\), and (d) the definition of the conditional expectation \(\mathbb{E}[X | E] = \mathbb{E}[X \mathbb{1}_E] / \Pr(E)\) (Example 34.1 of [56]), \(\Pr(E) \geq 1 - 1 / T^2 \geq 1/2\) due to \(T \geq 2\), and \(\sigma_{t-1}^2(\boldsymbol{x}_t) \geq 0\).

Therefore, combining Lemma 11, we obtain \[\begin{align} \mathbb{E}[|{\cal T}| \mid E] &\leq \frac{32 C_1 \beta_T \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}{\Delta^2}. \end{align}\] Thus, we see that \[\begin{align} \mathbb{E}[|{\cal T}|] \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}{\Delta^2} + \frac{1}{T} \end{align}\] Hence, \(\mathbb{E}[|{\cal T}|] \in \{ t \in \mathbb{R}_{\geq 0} \mid t \leq \frac{32 C_1 \beta_T \tilde{\gamma}_t}{\Delta^2} + \frac{1}{T}\}\) and \(\mathbb{E}[|{\cal T}| \leq T_{\rm max}\) from the definition of \(T_{\rm max}\).

Next, we consider the case of \({\cal X}\subset [0, r]^d\). Purely for the sake of analysis, we consider equally divided grid points \({\cal X}_t\), where the grid size for each dimension is \(\tau_t = \lceil d r L t \rceil\) and \(|{\cal X}_t| = \tau_t^d\), where \(L = \max\{ b \sqrt{\log (2ad T^2)}, L_\sigma \}\) with \(L_\sigma\) defined in Lemma 1. We denote \([\boldsymbol{x}]_t = \mathop{\mathrm{arg\,min}}_{\boldsymbol{x}^\prime \in {\cal X}_t} \|\boldsymbol{x} - \boldsymbol{x}^\prime \|_1\). Therefore, \(\sup_{\boldsymbol{x} \in {\cal X}} \| \boldsymbol{x} - [\boldsymbol{x}]_t \|_1 \leq 1 / (Lt)\).

We define \[\begin{align} E_{\rm Lip} = \left\{ \| f \|_{\rm Lip} \leq b \sqrt{\log (2ad T^2)} \right\}, \end{align}\] where \(\| f \|_{\rm Lip}\) is the Lipschitz constant of \(f\). From Assumption 2, \(\Pr(E_{\rm Lip}^c) \leq 1 / (2 T^2)\). In addition, we define the event for the credible intervals of \(f\) and \(g_t\): \[\begin{align} E = \left\{ \forall t \geq 1, \forall \boldsymbol{x} \in {\cal X}_t, |f(\boldsymbol{x}) - \mu_{t-1}(\boldsymbol{x})| \leq \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}), |g_t(\boldsymbol{x}) - \mu_{t-1}(\boldsymbol{x})| \leq \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}) \right\}, \end{align}\] where \(\beta_t = 2\log (2|{\cal X}_t| T^2 t (t+1)) = 2\log (2 \tau_t^d T^2 t (t+1))\). From Lemma 5 and the union bound, \(\Pr(E^c) \leq 1 / (2 T^2)\). Hence, we see \(\Pr( E^c \lor E_{\rm Lip}^c ) \leq 1 / T^2\).

Therefore, we can see that \[\begin{align} \mathbb{E}[|{\cal T}|] &= \mathbb{E}[|{\cal T}| \mid E \land E_{\rm Lip}] \Pr(E \land E_{\rm Lip}) + \mathbb{E}[|{\cal T}| \mid E^c \lor E_{\rm Lip}^c] \Pr(E^c \lor E_{\rm Lip}^c) \\ &\leq \mathbb{E}[|{\cal T}| \mid E \land E_{\rm Lip}] + \frac{1}{T}, \end{align}\] where the inequality holds because \(\Pr(E \land E_{\rm Lip}) \leq 1\), \(|{\cal T}| \leq T\) a.s., and \(\Pr(E^c \lor E_{\rm Lip}^c) \leq 1 / T^2\). Then, as with the case of discrete \({\cal X}\), we obtain \[\begin{align} \mathbb{E}[|{\cal T}| \mid E \land E_{\rm Lip}] &= \mathbb{E}\left[ \sum_{t \in {\cal T}} \min \left\{1, \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} \right\} \biggm| E \land E_{\rm Lip} \right] \\ &\leq \mathbb{E}\left[ \sum_{t \in {\cal T}} \min \left\{1, \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta^2} \right\} \biggm| E \land E_{\rm Lip} \right] \\ &\leq \mathbb{E}\left[ \sum_{t \in {\cal T}} \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta^2} \biggm| E \land E_{\rm Lip} \right] \end{align}\] where the first inequalities hold because \(1 \leq \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta}\) due to the definition of \({\cal T}\).

Since the event \(E\) and \(E_{\rm Lip}\) holds and discretization error can be bounded from above by \(1 / t\) from Lemma 8, for all \(t \geq 1\), \[\begin{align} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq |f(\boldsymbol{x}^*) - f([\boldsymbol{x}^*]_t)| + |f([\boldsymbol{x}^*]_t) - \mu_{t-1}([\boldsymbol{x}^*]_t)| + \mu_{t-1}([\boldsymbol{x}^*]_t) - \mu_{t-1}([\boldsymbol{x}_t]_t) \\ &\qquad + |f([\boldsymbol{x}_t]_t) - \mu_{t-1}([\boldsymbol{x}_t]_t)| + |f(\boldsymbol{x}_t) - f([\boldsymbol{x}_t]_t)| \\ &\leq \mu_{t-1}([\boldsymbol{x}^*]_t) - \mu_{t-1}([\boldsymbol{x}_t]_t) + \beta_t^{1/2} \bigl( \sigma_{t-1}( [\boldsymbol{x}^*]_t) + \sigma_{t-1}( [\boldsymbol{x}_t]_t) \bigr) + \frac{2}{t}. \end{align}\] Furthermore, we can obtain \[\begin{align} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq 2 \beta_t^{1/2} \bigl(\sigma_{t-1}([\boldsymbol{x}^*]_t) + \sigma_{t-1}([\boldsymbol{x}_t]_t) \bigr) + \frac{4}{t}, \end{align}\] because \[\begin{align} &g_t(\boldsymbol{x}_t) \geq g_t(\boldsymbol{x}^*) \quad \text{(from the nature of GP-TS)}\\ &\Rightarrow \mu_{t-1}([\boldsymbol{x}_t]_t) + \beta_t^{1/2} \sigma_{t-1}([\boldsymbol{x}_t]_t) + \frac{1}{t} \geq \mu_{t-1}([\boldsymbol{x}^*]_t) - \beta_t^{1/2} \sigma_{t-1}([\boldsymbol{x}^*]_t) - \frac{1}{t} \\ &\Rightarrow \mu_{t-1}([\boldsymbol{x}^*]_t) - \mu_{t-1}([\boldsymbol{x}_t]_t) \leq \beta_t^{1/2} \bigl(\sigma_{t-1}([\boldsymbol{x}^*]_t) + \sigma_{t-1}([\boldsymbol{x}_t]_t) \bigr) + \frac{2}{t}. \end{align}\] Finally, we see that \[\begin{align} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq 2 \beta_t^{1/2} \bigl(\sigma_{t-1}(\boldsymbol{x}^*) + \sigma_{t-1}(\boldsymbol{x}_t) \bigr) + \frac{4 (\beta_t^{1/2} + 1)}{t}, \end{align}\] because \[\begin{align} \sup_{\boldsymbol{x} \in {\cal X}} | \sigma_{t-1}(\boldsymbol{x}) - \sigma_{t-1}([\boldsymbol{x}]_t) | \leq L_\sigma \| \boldsymbol{x} - [\boldsymbol{x}]_t \|_1 \leq \frac{1}{t}, \end{align}\] due to Lemma 1.

Hence, noting \(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq 0\) for all \(t \geq 1\), we obtain \[\begin{align} \mathbb{E}[|{\cal T}| \mid E \land E_{\rm Lip}] &\leq \frac{1}{\Delta^2} \mathbb{E}\left[ \sum_{t \in {\cal T}}\left( 2 \beta_t^{1/2} \bigl( \sigma_{t-1}(\boldsymbol{x}^*) + \sigma_{t-1}(\boldsymbol{x}_t) \bigr) + \frac{4(\beta_t^{1/2} + 1)}{t} \right)^2 \biggm| E \land E_{\rm Lip} \right] \\ &\overset{(a)}{\leq} \frac{12 \beta_T}{\Delta^2} \mathbb{E}\left[ \sum_{t \in {\cal T}} \left\{ \sigma_{t-1}^2(\boldsymbol{x}^*) + \sigma_{t-1}^2(\boldsymbol{x}_t) \right\} \biggm| E \land E_{\rm Lip} \right] + \frac{48}{\Delta^2} \mathbb{E}\left[ \sum_{t \in {\cal T}} \frac{(\beta_t^{1/2} + 1)^2}{t^2} \biggm| E \land E_{\rm Lip} \right] \\ &\overset{(b)}{\leq} \frac{12 \beta_T}{\Delta^2} \mathbb{E}\left[ \sum_{t \in {\cal T}} \left\{ \sigma_{t-1}^2(\boldsymbol{x}^*) + \sigma_{t-1}^2(\boldsymbol{x}_t) \right\} \biggm| E \land E_{\rm Lip} \right] + \frac{8 \pi^2 (\beta_T^{1/2} + 1)^2}{\Delta^2}, \end{align}\] where the inequalities hold because of the monotonicity of \(\beta_t\), (a) the Cauchy–Schwarz inequality, and (b) \(\sum_{t = 1}^T 1 / t^2 \leq \pi^2 / 6\).

Finally, for the term \(\mathbb{E}\left[ \sum_{t \in {\cal T}} \left\{ \sigma_{t-1}^2(\boldsymbol{x}^*) + \sigma_{t-1}^2(\boldsymbol{x}_t) \right\} \biggm| E \land E_{\rm Lip} \right]\), since we can apply the same proof as the case of \(|{\cal X}| < \infty\) (with \(\Pr(E \land E_{\rm Lip}) \geq 1 - 1 / T^2 \geq 3 / 4\) due to \(T \geq 2\)), we obtain \[\begin{align} \mathbb{E}[|{\cal T}| \mid E \land E_{\rm Lip}] \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}{\Delta^2} + \frac{8 \pi^2 (\beta_T^{1/2} + 1)^2}{\Delta^2}, \end{align}\] and \[\begin{align} \mathbb{E}[|{\cal T}|] \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}{\Delta^2} + \frac{8 \pi^2 (\beta_T^{1/2} + 1)^2}{\Delta^2} + \frac{1}{T}. \end{align}\] Hence, \(\mathbb{E}[|{\cal T}|] \in \{ t \in \mathbb{R}_{\geq 0} \mid t \leq \frac{32 C_1 \beta_T \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}{\Delta^2} + \frac{8 \pi^2 (\beta_T^{1/2} + 1)^2}{\Delta^2} + \frac{1}{T}\}\) and \(\mathbb{E}[|{\cal T}| \leq T_{\rm max}\) from the definition of \(T_{\rm max}\). ◻

Next, we show the general lenient regret upper bounds for \(\sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\).

Theorem 7. Fix \(\Delta > 0\) and \(\delta \in (0, 1)\) and let \({\cal T}= \{ t \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta\}\). Then, if Algorithm 1 runs, the following inequality holds for any \(T \geq 2\):

If Assumption 1 holds and \(|{\cal X}| < \infty\), \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] \leq 4 \sqrt{ C_1 \beta_T \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} } + 1 \leq 4 \sqrt{ C_1 \beta_T T_{\rm max} \tilde{\gamma}_{T_{\rm max}} } + 1. \end{align}\] where \(\beta_t = \max\bigl\{1, 2\log (4|{\cal X}| T / \sqrt{2 \pi})\bigr\}\) for all \(t \in [T]\) and \(T_{\rm max}\) is defined as in Theorem 6.
If Assumptions 1 and 2 hold, \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] &\leq 4 + 4 \beta_T^{1/2} + 4 \sqrt{C_1 \beta_T \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}} \leq 4 + 4 \beta_T^{1/2} + 4 \sqrt{C_1 \beta_T T_{\rm max} \tilde{\gamma}_{T_{\rm max}}}. \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\), \(\beta_t = \max\bigl\{1, 2\log \bigl(4\lceil drL T \rceil^d T / \sqrt{2 \pi} \bigr) \bigr\}\) for all \(t \in [T]\), \(L = \max\{ L_{\sigma}, b \bigl(\sqrt{\log (ad)} + \sqrt{\pi}/2 \bigr)\}\), \(T_{\rm max}\) is defined as in Theorem 6, and \(L_{\sigma}\) is defined as in Lemma 1.

Proof. Let \(U_t (\boldsymbol{x}) = \mu_{t-1}(\boldsymbol{x}) + \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x})\) and \(L_t (\boldsymbol{x}) = \mu_{t-1}(\boldsymbol{x}) - \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x})\). Moreover, we define \((c)_+ = \max \{0, c\}\).

For the terms \(A_1\) and \(A_2\), by applying Lemma 9 and Lemma 11 respectively, we have \[\begin{align} A_1 &\leq \sum_{t=1}^T \frac{4}{4T} = 1, \\ A_2 &\leq 4 \sqrt{ C_1 \beta_T \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} }, \end{align}\] which is the desired result. Note that, for the terms \(\bigl( L_t(\boldsymbol{x}^*) - g_t(\boldsymbol{x}^*) \bigr)_+\) and \(\bigl( L_t(\boldsymbol{x}_t) - f(\boldsymbol{x}_t) \bigr)_+\), we apply Lemma 9 to \(- g_t\) and \(-f\).

Next, we consider the case of \({\cal X}\subset [0, r]^d\). Purely for the sake of analysis, we consider equally divided grid points \({\cal X}_t\), where the grid size for each dimension is \(\tau_t = \lceil d r L T \rceil\) and \(|{\cal X}_t| = \tau_t^d\), where \(L = \max\{ b \bigl(\sqrt{\log (ad)} + \sqrt{\pi} / 2\bigr), L_\sigma \}\) with \(L_\sigma\) defined in Lemma 1. We denote \([\boldsymbol{x}]_t = \mathop{\mathrm{arg\,min}}_{\boldsymbol{x}^\prime \in {\cal X}_t} \| \boldsymbol{x} - \boldsymbol{x}^\prime \|_1\). Therefore, \(\sup_{\boldsymbol{x} \in {\cal X}} \| \boldsymbol{x} - [\boldsymbol{x}]_t \|_1 \leq \frac{1}{LT}\).

Since \(g_t(\boldsymbol{x}_t) \geq g_t(\boldsymbol{x}^*)\) and \(\beta_t\) is monotonically increasing, we can derive \[\begin{align} &\mathbb{E}\left[ \sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] \\ &\leq \mathbb{E}\biggl[ \sum_{t \in {\cal T}} \biggl( f(\boldsymbol{x}^*) - f([\boldsymbol{x}^*]_t) + f([\boldsymbol{x}^*]_t) - U_t([\boldsymbol{x}^*]_t) + 2 \beta_t^{1/2} \sigma_{t-1}([\boldsymbol{x}^*]_t) + L_t([\boldsymbol{x}^*]_t) - g_t([\boldsymbol{x}^*]_t) \\ & \qquad \qquad + g_t(\boldsymbol{x}_t) - g_t([\boldsymbol{x}_t]_t) + g_t([\boldsymbol{x}_t]_t) - U_t([\boldsymbol{x}_t]_t) + 2 \beta_t^{1/2} \sigma_{t-1}([\boldsymbol{x}_t]_t) + L_t([\boldsymbol{x}_t]_t) - f([\boldsymbol{x}_t]_t) + f([\boldsymbol{x}_t]_t) - f(\boldsymbol{x}_t) \biggr) \biggr] \\ &\leq \underbrace{\mathbb{E}\biggl[ \sum_{t = 1}^T \biggl( |f(\boldsymbol{x}^*) - f([\boldsymbol{x}^*]_t)| + |g_t(\boldsymbol{x}_t) - g_t([\boldsymbol{x}_t]_t)| + |f([\boldsymbol{x}_t]_t) - f(\boldsymbol{x}_t)| \biggr) \biggr]}_{A_1} \\ &\quad + \underbrace{\mathbb{E}\biggl[ \sum_{t = 1}^T \biggl( \bigl( f([\boldsymbol{x}^*]_t) - U_t([\boldsymbol{x}^*]_t) \bigr)_+ + \bigl( L_t([\boldsymbol{x}^*]_t) - g_t([\boldsymbol{x}^*]_t) \bigr)_+ + \bigl( g_t([\boldsymbol{x}_t]_t) - U_t([\boldsymbol{x}_t]_t) \bigr)_+ + \bigl( L_t([\boldsymbol{x}_t]_t) - f([\boldsymbol{x}_t]_t) \bigr)_+ \biggr) \biggr]}_{A_2} \\ &\quad + \underbrace{2 \beta_T^{1/2} \mathbb{E}\biggl[ \sum_{t = 1}^T \biggl( |\sigma_{t-1}(\boldsymbol{x}^*) - \sigma_{t-1}([\boldsymbol{x}^*]_t)| + |\sigma_{t-1}(\boldsymbol{x}_t) - \sigma_{t-1}([\boldsymbol{x}_t]_t)| \biggr) \biggr]}_{A_3} + \underbrace{2 \beta_T^{1/2} \mathbb{E}\biggl[ \sum_{t \in {\cal T}} \biggl( \sigma_{t-1}(\boldsymbol{x}^*) + \sigma_{t-1}(\boldsymbol{x}_t) \biggr) \biggr]}_{A_4}. \end{align}\]

Regarding the term \(A_1\), from Lemma 8, we obtain \[\begin{align} A_1 \leq 3 \sum_{t=1}^T \frac{1}{T} = 3. \end{align}\] Regarding the term \(A_2\), from Lemma 9, we derive \[\begin{align} A_2 \leq 4 \sum_{t=1}^T \frac{1}{4T} = 1. \end{align}\] Regarding the term \(A_3\), from Lemma 1 and the construction of \({\cal X}_t\), we have \[\begin{align} A_3 \leq 4 \beta_T^{1/2} \sum_{t=1}^T \frac{1}{T} = 4 \beta_T^{1/2}. \end{align}\] Finally, regarding the term \(A_4\), from Lemma 11, we see that \[\begin{align} A_4 \leq 4 \sqrt{C_1 \beta_T \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}. \end{align}\]

Consequently, we obtain the desired result: \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] &\leq 4 + 4 \beta_T^{1/2} + 4 \sqrt{C_1 \beta_T \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}. \end{align}\] ◻

Finally, we show the kernel-specific results shown below.

@title 2. Fix \(\Delta > 0\) and \(\delta \in (0, 1)\) and let \({\cal T}= \{ t \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta\}\). Suppose that Assumption 1 and \(|{\cal X}| < \infty\) hold or Assumptions 1 and 2 hold. Then, if Algorithm 1 runs, the following inequalities hold: \[\begin{align} \mathbb{E}[|{\cal T}|] &\leq T_{\rm max}, \\ \mathbb{E}\left[\sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] &= O\left( \sqrt{\beta_T T_{\rm max} \tilde{\gamma}_{T_{\rm max}}} \right). \end{align}\] Here, \(T_{\rm max}\) satisfies: \[\begin{align} T_{\rm max} = \begin{cases} O \left( \frac{\beta_T d \log T}{\Delta^2} \right) & \text{if k = k_{\rm Lin}}, \\ O \left( \frac{\beta_T \log^{d + 1} T}{\Delta^2} \right) & \text{if k = k_{\rm SE}}, \\ O \left( \left( \frac{\beta_T \log^{\frac{4\nu + d}{2\nu + d}} T}{\Delta^2} \right)^{1 + \frac{d}{2\nu}} \right) & \text{if k = k_{\rm Mat}}, \end{cases} \end{align}\] where \(\beta_T = O\bigl(\log(|{\cal X}| T)\bigr)\) and \(\nu > 1 / 2\) for the case of \(|{\cal X}| < \infty\) and \(\beta_T = O\bigl( d\log(d T) \bigr)\) and \(\nu > 1\) for the case of continuous \({\cal X}\).

Proof. From Theorems 6 and 7, it suffices to show the upper bound of \(T_{\rm max}\). For both cases of discrete and continuous input domains, we see that \[\begin{align} T_{\rm max} = O \left( \frac{\beta_T \tilde{\gamma}_{T_{\rm max}}}{\Delta^2} \right). \end{align}\] For the linear and SE kernels, we obtain a crude upper bound by substituting \(\gamma_T\) with \(\tilde{\gamma}_{T_{\rm max}}\) as follows: \[\begin{align} T_{\rm max} = O \left( \frac{\beta_T \gamma_T}{\Delta^2} \right). \end{align}\] Since \(\gamma_T = O(d \log T)\) for the linear kernel and \(\gamma_T = O(\log^{d + 1} T)\) [6], [46], we obtain the desired result. For the Matérn kernel, by substituting \(\gamma_T = O(T^{\frac{d}{2\nu + d}} \log^{\frac{4\nu + d}{2\nu + d}} T)\) [10], we see that \[\begin{align} &T_{\rm max} = O \left( \frac{\beta_T T_{\rm max}^{\frac{d}{2\nu + d}} \log^{\frac{4\nu + d}{2\nu + d}} T}{\Delta^2} \right) \\ &\Leftrightarrow T_{\rm max}^{\frac{2\nu}{2\nu + d}} = O \left( \frac{\beta_T \log^{\frac{4\nu + d}{2\nu + d}} T}{\Delta^2} \right) \\ &\Leftrightarrow T_{\rm max} = O \left( \left(\frac{\beta_T \log^{\frac{4\nu + d}{2\nu + d}} T}{\Delta^2} \right)^{1 + \frac{d}{2\nu}} \right), \end{align}\] which concludes the proof. ◻

8 Proof of Theorem 4 ↩︎

First, we show the following general result regarding the improved regret analysis, refined from [10]:

@title 3. Let \({\cal X}= [0, r]^d\). Suppose Assumptions 1 and 2 hold. In addition, assume the three conditions in Lemma 2 and the following event \(E\) are true: \[\begin{align} E = \left\{\forall t \in \mathbb{N}, f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \leq 2 \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}_t) + \frac{1}{t^2} \right\}, \end{align}\] where \(\{ \beta_t \}_{t \in \mathbb{N}}\) is some monotonically increasing sequence with \(\beta_t = O(\log t)\). Then, the following holds: \[\begin{align} \sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) = \begin{cases} O(\sqrt{T} \log T) & \text{if k = k_{\rm SE}}, \\ \tilde{O}(\sqrt{T}) & \text{if k = k_{\rm Mat} with \nu > 2}, \end{cases} \end{align}\] where the hidden constants may depend on \(d, \nu, \ell, r, \sigma^2\), and the constants \(c_{\rm sup}, c_{\rm gap}, \rho_{\rm quad}, c_{\rm quad}\) in Lemma 2.

Proof. We consider the cases of SE and Matérn kernels separately.

Case of SE kernels.

We set \(\Delta = \frac{\beta_T \gamma_T}{\sqrt{T}}\). If \(\Delta > \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\), we can see that \(T < \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}^{-2} \beta_T^2 \gamma_T^2\). Therefore, \(\sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \leq c_{\rm sup} \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}^{-2} \beta_T^2 \gamma_T^2 = O(\log^{2d + 4} T)\). Hence, we consider the case of \(\Delta \leq \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\) below.

We divide the index set \([T]\) as follows: \[\begin{align} {\cal T}&= \{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \}, \\ {\cal T}^c &= \{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) < \Delta \}. \end{align}\] We will obtain the regret incurred regarding \({\cal T}\) and \({\cal T}^c\), respectively.

For the set \({\cal T}\), we can obtain the upper bound of \(|{\cal T}|\) as follows: \[\begin{align} |{\cal T}| &= \sum_{t \in {\cal T}} \min\left\{1, \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} \right\} \\ &= \sum_{t \in {\cal T}} \min\left\{1, \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta^2} \right\} \\ &\overset{(a)}{\leq} \sum_{t \in {\cal T}} \frac{(2\beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}_t) + 1 / t^2)^2}{\Delta^2} \\ &\overset{(b)}{\leq} \frac{8 \beta_T }{\Delta^2} \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) + \frac{\pi^2}{3 \Delta^2} \\ &\overset{(c)}{\leq} \frac{8 C_1 \beta_T \gamma_T}{\Delta^2} + \frac{\pi^2}{3 \Delta^2} \\ &= O\left(\frac{T}{\beta_T \gamma_T} \right), \end{align}\] where the inequalities hold because (a) the event \(E\) holds and \(\frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta} > 1\), (b) \((a + b)^2 \leq 2a^2 + 2b^2\) for all \(a, b \in \mathbb{R}\) and \(2 \sum_{t=1}^T 1 / t^4 \leq 2 \sum_{t=1}^T 1 / t^2 \leq \pi^2 / 3\), and (c) \(\sum_{t=1}^T \sigma_{t-1}^2 (\boldsymbol{x}_t) \leq C_1 \gamma_T\) with \(C_1 = 2 / \log(1 + \sigma^{-2})\) [6], respectively. Therefore, from Lemma 7, we can obtain \[\begin{align} \sum_{t \in {\cal T}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T |{\cal T}| \gamma_T} + \pi^2 / 6 = O(\sqrt{T}). \end{align}\]

For the set \({\cal T}^c\), due to \(\Delta \leq \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\) and the condition 3 in Lemma 2, we can obtain Lemma 6, which is modified from the proof of Lemmas 4 and 20 of [10]. Therefore, we see that \(\boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta }; \boldsymbol{x}^*\right)\), where \({\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta }; \boldsymbol{x}^*\right)\) is the L2 ball whose center and radius are \(\boldsymbol{x}^*\) and \(\sqrt{c_{\rm quad}^{-1} \Delta }\), respectively. Thus, by denoting the MIG over the domain \({\cal X}\) as \(\gamma_T({\cal X})\), we can obtain \[\begin{align} \sum_{t \in {\cal T}^c} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T T \gamma_T\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta }; \boldsymbol{x}^*\right) \right)} + \pi^2 / 6. \end{align}\] From Corollary 8 of [10], we can choose sufficiently large \(C_{\rm SE}\) so that \[\begin{align} \forall t \geq 2, \forall \eta \in \left(0, \sqrt{\frac{2\ell^2}{e^2 c_d}}\right), \gamma_t\left( {\cal B}\left(\eta; 0\right) \right) \leq C_{\rm SE} \left(\frac{\log^{d+1} t}{\log^d \left( \frac{2 \ell^2}{\eta^2 e c_d} \right)} + \log t\right), \end{align}\] where \(c_d = \max \left\{1, \exp\left( \frac{1}{e} \left(\frac{d}{2} - 1 \right) \right) \right\}\). If \(\sqrt{c_{\rm quad}^{-1} \Delta } \geq \sqrt{\frac{2\ell^2}{e^2 c_d}} \Leftrightarrow T \leq \left( \frac{e^2 c_d \beta_T \gamma_T}{2 c_{\rm quad} \ell^2} \right)^2\), we can see that \(\sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \leq c_{\rm sup} \left( \frac{e^2 c_d \beta_T \gamma_T}{2 c_{\rm quad} \ell^2} \right)^2 = O(\log^{2d + 4} T)\). Thus, we consider the case of \(\sqrt{c_{\rm quad}^{-1} \Delta } < \sqrt{\frac{2\ell^2}{e^2 c_d}}\) hereafter. Then, we see that \[\begin{align} \gamma_T\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta }; \boldsymbol{x}^*\right) \right) &\leq C_{\rm SE} \left(\frac{\log^{d+1} T}{\log^d \left( \frac{2 \ell^2}{c_{\rm quad}^{-1} e c_d \Delta} \right)} + \log T \right) \\ &= C_{\rm SE} \left(\frac{\log^{d+1} T}{ \left((1 / 2) \log T + \log\left( \frac{2 c_{\rm quad} \ell^2}{\beta_T \gamma_T e c_d} \right) \right)^d} + \log T \right). \end{align}\] Since \((1 / 2) \log T\) is dominant (in terms of \(T\)) compared with \(\log\left( \frac{2 c_{\rm quad} \ell^2}{\beta_T \gamma_T e c_d}\right) = \Omega\left( - (d+2)\log \log T \right)\), we have \(\left((1 / 2) \log T + \log\left( \frac{2 c_{\rm quad} \ell^2}{\beta_T \gamma_T e c_d} \right) \right)^d = \Omega(\log^d T)\), and thus, \[\begin{align} \gamma_T\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta }; \boldsymbol{x}^*\right) \right) &= O(\log T). \end{align}\] Consequently, we obtain \[\begin{align} \sum_{t \in {\cal T}^c} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T T \gamma_T\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta }; \boldsymbol{x}^*\right) \right)} + \pi^2 / 6 \\ &= O( \sqrt{T} \log T). \end{align}\]

Case of Matérn kernels.

We set \(\Delta_1 = T^{- \tfrac{\nu}{2(\nu + d)}}\). If \(\Delta_1 > \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\), we can see that \(T < \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}^{- \tfrac{2(\nu + d)}{\nu}}\). Therefore, \(\sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \leq c_{\rm sup} \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}^{- \tfrac{2(\nu + d)}{\nu}} = O(1)\). Hence, we consider the case of \(\Delta_1 \leq \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\) below.

We divide the index set \([T]\) as follows: \[\begin{align} {\cal T}_0 &= \{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_1 \}, \\ {\cal T}_i &= \{t \in [T] \mid \Delta_i \geq f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_{i+1} \}, \forall i \in [\bar{i} - 1], \\ {\cal T}_{\bar{i}} &= \{t \in [T] \mid \Delta_{\bar{i}} \geq f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \}, \end{align}\] where \(\bar{i} \in \mathbb{N}\) and monotonically decreasing \(\Delta_2, \dots, \Delta_{\bar{i}} > 0\) will be chosen hereafter so that the desired result can be obtained.

First, we show the regret incurred for \({\cal T}_0\). As with the case of SE kernels, we have \[\begin{align} |{\cal T}_0| &= \sum_{t \in {\cal T}_0} \min\left\{1, \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta_1} \right\} \\ &= \sum_{t \in {\cal T}_0} \min\left\{1, \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta_1^2} \right\} \\ &\leq \frac{8 \beta_T }{\Delta_1^2} \sum_{t \in {\cal T}_0} \sigma_{t-1}^2(\boldsymbol{x}_t) + \frac{\pi^2}{3 \Delta_1^2} \\ &\leq \frac{8 C_1 \beta_T \gamma_{|{\cal T}_0|}}{\Delta_1^2} + \frac{\pi^2}{3 \Delta_1^2} \\ &= \tilde{O}\left( |{\cal T}_0|^{\tfrac{d}{2\nu + d}} T^{\tfrac{\nu}{(\nu + d)}} \right). \end{align}\] Therefore, we see that \[\begin{align} |{\cal T}_0| = \tilde{O} \left( T^{\tfrac{2\nu + d}{2(\nu + d)}} \right). \end{align}\] Note that, if \(\frac{\pi^2}{3 \Delta_1^2}\) is dominant compared with \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_0|}}{\Delta_1^2}\), then \(|{\cal T}_0| = \tilde{O} \left( T^{\tfrac{\nu}{(\nu + d)}} \right) = \tilde{O} \left( T^{\tfrac{2\nu + d}{2(\nu + d)}} \right)\). Hence, from Lemma 7, we obtain \[\begin{align} \sum_{t \in {\cal T}_0} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T |{\cal T}_0| \gamma_{|{\cal T}_0|}} \\ &= \tilde{O}\left( T^{\tfrac{2\nu + d}{4(\nu + d)}} \left( T^{\tfrac{2\nu + d}{4(\nu + d)}} \right)^{\tfrac{d}{2\nu + d}}\right) \\ &= \tilde{O}\left( \sqrt{T} \right). \end{align}\]

Next, we consider \({\cal T}_i\) for all \(i \in [\bar{i}]\). Due to \(\Delta_1 \leq \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\) and the condition 3 in Lemma 2, we can obtain Lemma 6, which is modified from the proof of Lemmas 4 and 20 of [10]. Therefore, we see that \(\boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right)\) for all \(t \in {\cal T}_i\) and \(i \in [\bar{i}]\). Thus, from Lemma 7, we can obtain \[\begin{align} \forall i \in [\bar{i}], \sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T |{\cal T}_i| \gamma_{|{\cal T}_i|} \left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)} + \pi^2 / 6. \end{align}\] From Corollary 8 of [10], we can choose sufficiently large \(C_{\rm Mat}\) so that \[\begin{align} \forall t \geq 2, \forall \eta > 0, \gamma_{t} \left( {\cal B}\left(\eta; 0\right) \right) \leq C_{\rm Mat}\left( \eta^{\tfrac{2\nu d}{2\nu + d}} t^{\tfrac{d}{2\nu + d}} \log^{\tfrac{4\nu + d}{2\nu + d}} t + \log^2 t \right). \end{align}\] Therefore, we have \[\begin{align} \gamma_{|{\cal T}_i|} \left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right) = O \left( \Delta_i^{\tfrac{\nu d}{2\nu + d}} |{\cal T}_i|^{\tfrac{d}{2\nu + d}} \log^{\tfrac{4\nu + d}{2\nu + d}} |{\cal T}_i| + \log^2 |{\cal T}_i| \right). \end{align}\] If the term \(\log^2 |{\cal T}_i| = O(\log^2 T)\) is dominant compared with \(\Delta_i^{\tfrac{\nu d}{2\nu + d}} |{\cal T}_i|^{\tfrac{d}{2\nu + d}} \log^{\tfrac{4\nu + d}{2\nu + d}} |{\cal T}_i|\), then the corresponding regret for \({\cal T}_i\) can be readily bounded from above by \(\tilde{O}(\sqrt{T})\). Thus, hereafter, we focus on the set \({\cal I}\subset [\bar{i}]\), for which \(\Delta_i^{\tfrac{\nu d}{2\nu + d}} |{\cal T}_i|^{\tfrac{d}{2\nu + d}} \log^{\tfrac{4\nu + d}{2\nu + d}} |{\cal T}_i|\) is dominant compared with \(\log^2 T\). Therefore, we have \[\begin{align} \forall i \in {\cal I}, \sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \tilde{O} \left( \sqrt{|{\cal T}_i|^{\tfrac{2\nu + 2d}{2\nu + d}} \Delta_i^{\tfrac{\nu d}{2\nu + d}}} \right). \end{align}\] Hence, if we can set \(\Delta_{\bar{i}} = \tilde{O}\bigl(T^{- \tfrac{1}{\nu}}\bigr)\) when \(\bar{i} \in {\cal I}\), by the upper bound \(|{\cal T}_{\bar{i}}| \leq T\), we can obtain \[\begin{align} \sum_{t \in {\cal T}_{\bar{i}}} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \tilde{O} \left( \sqrt{T} \right). \end{align}\] Hereafter, we will confirm the condition that we can choose \(\Delta_2, \dots, \Delta_{\bar{i} - 1}\) so that the resulting regret over \({\cal T}_1, \dots, {\cal T}_{\bar{i} - 1}\) is \(\tilde{O}(\sqrt{T})\) and \(\Delta_{\bar{i}} = \tilde{O}\bigl(T^{- \tfrac{1}{\nu}}\bigr)\).

As with the previous derivations, for all \(i \in {\cal I}\backslash \{ \bar{i} \}\), we have \[\begin{align} |{\cal T}_i| &= \sum_{t \in {\cal T}_i} \min\left\{1, \frac{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)}{\Delta_{i+1}} \right\} \\ &= \sum_{t \in {\cal T}_i} \min\left\{1, \frac{\bigl(f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)\bigr)^2}{\Delta_{i+1}^2} \right\} \\ &\leq \frac{8 \beta_T }{\Delta_{i+1}^2} \sum_{t \in {\cal T}_i} \sigma_{t-1}^2(\boldsymbol{x}_t) + \frac{\pi^2}{3 \Delta_{i+1}^2} \\ &\leq \frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} + \frac{\pi^2}{3 \Delta_{i+1}^2}. \end{align}\] Then, we consider the following two cases, depending on which term is dominant.

8.0.0.1 Case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} \geq \frac{\pi^2}{3 \Delta_{i+1}^2}\).

In this case, we see that \[\begin{align} |{\cal T}_i| &= \tilde{O} \left( \Delta_i^{\tfrac{\nu d}{2\nu + d}} \Delta_{i+1}^{-2} |{\cal T}_i|^{\tfrac{d}{2\nu + d}} \right), \end{align}\] which immediately suggests that \[\begin{align} |{\cal T}_i| = \tilde{O} \left( \left(\Delta_i^{\tfrac{\nu d}{2\nu + d}} \Delta_{i+1}^{-2}\right)^{\tfrac{2\nu + d}{2\nu}} \right). \end{align}\] Therefore, for all \(i \in {\cal I}\backslash \{ \bar{i} \}\), we can see that \[\begin{align} \sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T |{\cal T}_i| \gamma_{|{\cal T}_i|} \left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)} + \pi^2 / 6 \\ &= \tilde{O} \left( \sqrt{\left( \left(\Delta_i^{\tfrac{\nu d}{2\nu + d}} \Delta_{i+1}^{-2} \right)^{\tfrac{2\nu + d}{2\nu}} \right)^{\tfrac{2\nu + 2d}{2\nu + d}} \Delta_i^{\tfrac{\nu d}{2\nu + d}}} \right) \\ &=\tilde{O} \left( \Delta_i^{\tfrac{d}{2}} \Delta_{i+1}^{- \tfrac{\nu + d}{\nu}} \right). \end{align}\] To obtain \(\Delta_i^{\tfrac{d}{2}} \Delta_{i+1}^{- \tfrac{\nu + d}{\nu}} = \tilde{O}(\sqrt{T})\), we require the following condition: \[\begin{align} \Delta_{i + 1} = \tilde{\Omega}\left( T^{- \tfrac{\nu}{2 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{2(\nu + d)}} \right), \end{align}\] where \(\tilde{\Omega}\) hides polylogarithmic factors.

8.0.0.2 Case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} < \frac{\pi^2}{3 \Delta_{i+1}^2}\).

In this case, we see that \[\begin{align} |{\cal T}_i| &= \tilde{O} \left( \Delta_{i+1}^{-2} \right). \end{align}\] Therefore, for all \(i \in {\cal I}\backslash \{ \bar{i} \}\), we can see that \[\begin{align} \sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sqrt{C_1 \beta_T |{\cal T}_i| \gamma_{|{\cal T}_i|} \left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)} + \pi^2 / 6 \\ &= \tilde{O} \left( \sqrt{\left( \Delta_{i+1}^{-2} \right)^{\tfrac{2(\nu + d)}{2\nu + d}} \Delta_i^{\tfrac{\nu d}{2\nu + d}}} \right) \\ &=\tilde{O} \left( \Delta_i^{\tfrac{\nu d}{2(2 \nu + d)}} \Delta_{i+1}^{- \tfrac{2(\nu + d)}{2\nu + d}} \right). \end{align}\] To obtain \(\Delta_i^{\tfrac{\nu d}{2(2 \nu + d)}} \Delta_{i+1}^{- \tfrac{2(\nu + d)}{2\nu + d}} = \tilde{O}(\sqrt{T})\), we require the following condition: \[\begin{align} \Delta_{i + 1} = \tilde{\Omega}\left( T^{- \tfrac{2\nu + d}{4 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{4(\nu + d)}} \right). \end{align}\]

It suffices to consider the case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} \geq \frac{\pi^2}{3 \Delta_{i+1}^2}\) due to the following reason. Since we currently focus on \(i < \bar{i}\) such that \(\Delta_{i} = \tilde{\Omega}\bigl(T^{- \tfrac{1}{\nu}}\bigr)\), we have \[\begin{align} T^{- \tfrac{2\nu + d}{4 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{4(\nu + d)}} &= T^{- \tfrac{\nu}{2 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{2(\nu + d)}} T^{- \tfrac{d}{4 (\nu + d)}} \Delta_i^{- \tfrac{\nu d}{4(\nu + d)}} = \tilde{O} \left( T^{- \tfrac{\nu}{2 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{2(\nu + d)}} \right). \end{align}\] Therefore, the required condition \(\Delta_{i + 1} = \tilde{\Omega}\left( T^{- \tfrac{\nu}{2 (\nu + d)}} \Delta_i^{\tfrac{\nu d}{2(\nu + d)}} \right)\) is a strong condition. Hence, it is sufficient that we can prove for the case that \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} \geq \frac{\pi^2}{3 \Delta_{i+1}^2}\) holds for all \(i \in {\cal I}\backslash \{ \bar{i} \}\).

Thus, since \(\Delta_1 = T^{- \tfrac{\nu}{2(\nu + d)}}\), we choose \(\Delta_i\) as \[\begin{align} \Delta_i = \tilde{\Theta}\left( T^{ - \tfrac{\nu}{2(\nu + d)} \sum_{j=1}^i \left( \tfrac{\nu d}{2(\nu + d)} \right)^{j - 1}} \right). \end{align}\] Under this setting of \(\Delta_i\), the regret \(\sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) = \tilde{O}(\sqrt{T})\) for all \(i \in [\bar{i}]\). Finally, we will confirm the condition that above \(\Delta_i\) can reach to \(\Delta_{\bar{i}} = \tilde{O}\bigl(T^{- \tfrac{1}{\nu}}\bigr)\) with finite \(\bar{i}\).

8.0.0.3 Case of \(\frac{\nu d}{2(\nu + d)} \geq 1\).

Due to the condition, we can obtain \[\begin{align} \Delta_i = \tilde{O}\left( T^{ - \tfrac{i \nu}{2(\nu + d)}} \right). \end{align}\] Thus, we can choose \(\bar{i} = \left\lceil \frac{2(\nu + d)}{\nu^2} \right\rceil = O(1)\), by which \(\Delta_{\bar{i}} = \tilde{O}\left( T^{- \tfrac{1}{\nu}} \right)\). The condition \(\frac{\nu d}{2(\nu + d)} \geq 1\) can be transofrmed as \((\nu - 2)d - 2\nu \geq 0\). Therefore, this condition holds if and only if \(\nu > 2\) and \(d \geq \frac{2\nu}{v-2}\) simultaneously hold.

8.0.0.4 Case of \(\frac{\nu d}{2(\nu + d)} < 1\).

From the above discussion, this condition holds if (i) \(\nu \leq 2\) or (ii) \(\nu > 2\) and \(d < \frac{2\nu}{v-2}\) simultaneously hold. If \(\sum_{j=1}^{\bar{i}} \left( \frac{\nu d}{2(\nu + d)} \right)^{j - 1}\) with finite \(\bar{i}\) can be \(\frac{2(\nu + d)}{\nu^2}\), we can get \(\Delta_{\bar{i}} = \tilde{O}\bigl(T^{- \tfrac{1}{\nu}}\bigr)\). From the formula for the sum of a geometric series, we obtain \[\begin{align} \sum_{j=1}^i \left( \frac{\nu d}{2(\nu + d)} \right)^{j - 1} &= \frac{1 - \left( \frac{\nu d}{2(\nu + d)} \right)^i}{1 - \left( \frac{\nu d}{2(\nu + d)} \right)} \rightarrow \frac{2(\nu + d)}{2(\nu + d) - \nu d} && \text{as i \rightarrow \infty,} \end{align}\] since \(\left( \frac{\nu d}{2(\nu + d)} \right)^i \rightarrow 0\) due to the condition. Therefore, to get finite \(\bar{i}\), we require the condition \[\begin{align} \frac{2(\nu + d)}{2(\nu + d) - \nu d} > \frac{2(\nu + d)}{\nu^2}, \end{align}\] which can be rephrased as \((\nu + d) (\nu - 2) > 0\). Hence, if \(\nu > 2\), we can set \(\bar{i}\) as the smallest integer such that \[\begin{align} \frac{1 - \left( \frac{\nu d}{2(\nu + d)} \right)^{\bar{i}}}{1 - \left( \frac{\nu d}{2(\nu + d)} \right)} \geq \frac{2(\nu + d)}{\nu^2} &\Leftrightarrow 1 - \left( \frac{\nu d}{2(\nu + d)} \right)^{\bar{i}} \geq \frac{2(\nu + d) - \nu d}{\nu^2} \\ &\Leftrightarrow 1 - \frac{2(\nu + d) - \nu d}{\nu^2} \geq \left( \frac{\nu d}{2(\nu + d)} \right)^{\bar{i}} \\ &\Leftrightarrow \log\left( 1 - \frac{2(\nu + d) - \nu d}{\nu^2} \right) / \log\left( \frac{\nu d}{2(\nu + d)} \right) \leq \bar{i}. \end{align}\] Regarding the last transformation, note that \(\left( \frac{\nu d}{2(\nu + d)} \right) < 1 \Leftrightarrow \log \left( \frac{\nu d}{2(\nu + d)} \right) < 0\) from the condition. Thus, we can set \[\begin{align} \bar{i} = \left\lceil \log\left( 1 - \frac{2(\nu + d) - \nu d}{\nu^2} \right) / \log\left( \frac{\nu d}{2(\nu + d)} \right) \right\rceil = O(1). \end{align}\]

Summarizing the both cases, we can set \(\bar{i} = O(1)\) if \(\nu > 2\). Consequently, since the all regret incurred over \({\cal T}_0, \dots, {\cal T}_{\bar{i}}\) are \(\tilde{O}(\sqrt{T})\), the cumulative regret is bounded from above as \[\begin{align} \sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) = \sum_{i = 0}^{\bar{i}} \tilde{O}(\sqrt{T}) = \tilde{O}(\sqrt{T}), \end{align}\] which is the desired result. ◻

@title 4. Fix \(\delta \in (0, 1)\) and \(\delta_{\rm GP} \in (0, 1)\). Assume the same premise as in Lemma 2. Suppose Assumptions 1 and 2 hold. Then, if Algorithm 1 runs, the following holds with probability at least \(1 - \delta - \delta_{\rm GP}\): \[\begin{align} R_T = \begin{cases} O(\sqrt{T} \log T) & \text{if k = k_{\rm SE}}, \\ \tilde{O}(\sqrt{T}) & \text{if k = k_{\rm Mat} with \nu > 2}, \end{cases} \end{align}\] where the hidden constants may depend on \(1 / \delta, d, \nu, \ell, r, \sigma^2\), and the constants \(c_{\rm sup}, c_{\rm gap}, \rho_{\rm quad}, c_{\rm quad}\) corresponding with \(\delta_{\rm GP}\).

Proof. The overview of proof of this theorem is similar to that of Lemma 3. However, since the cumulative regret upper bound of GP-TS is shown via the expected regret bounds, we will transform the cumulative regret so that the proof of Lemma 3 can be applied. Let the index set \({\cal T}_i \subset [T]\) for all \(i = 0, \dots, \bar{i}\) be \[\begin{align} {\cal T}_i &= \{t \in [T] \mid \Delta_i \geq f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_{i+1} \}, \end{align}\] with convenient definition of \(\Delta_0 = 2 c_{\rm sup}\) and \(\Delta_{\bar{i} + 2} = 0\). For the both cases of SE and Matérn kernels, we choose \(\{\Delta_i\}_{i=1}^{\bar{i}}\) and \(\bar{i}\) as with the proof of Lemma 3. Hereafter, we define \(\beta_t = O(\log T)\) as the maximum of those defined in Lemmas 6 and 7 to apply both cases’ proofs.

Assume the three conditions in Lemma 2 hold. Then, we can decompose the cumulative regret as follows: \[\begin{align} \sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &= \sum_{i = 0}^{\bar{i}} \sum_{t \in {\cal T}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t). \end{align}\] Under the condition \(\Delta_1 \leq \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\) and the condition 3 in Lemma 2, we can obtain Lemma 6, which is modified from the proof of Lemmas 4 and 20 of [10]. (Note that, if \(\Delta_1 > \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\), we can get \(R_T = \tilde{O}(1)\) as with the proof of Lemma 3.) Therefore, we see that \(\Delta_i \geq f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \Rightarrow \boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right)\) for all \(i \in [\bar{i}]\). Hence, we have the upper bound below: \[\begin{align} \sum_{t = 1}^T f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) &\leq \sum_{i = 0}^{\bar{i}} \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t), \end{align}\] with \(\widetilde{{\cal T}}_i = \left\{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta_{i+1} \land \boldsymbol{x}_t \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right\}\). We will show upper bounds of \(\mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right]\).

At first, for any \(\widetilde{{\cal T}}_i\), the proof of Theorem 6 derives \[\begin{align} \mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right] = O\left( \frac{\beta_T \mathbb{E}\left[\sum_{t \in \widetilde{{\cal T}}_i} \bigl\{ \sigma_{t-1}^2(\boldsymbol{x}^*) + \sigma_{t-1}^2(\boldsymbol{x}_t) \bigr\} \right]}{\Delta_{i+1}^2} \right) + O\left( \frac{\beta_T}{\Delta_{i+1}^2} \right). \end{align}\] Furthermore, the proof of Theorem 7 derives \[\begin{align} \mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] &\leq O(\log T) + 2 \beta_T^{1/2} \left( \mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} \sigma_{t-1}(\boldsymbol{x}^*) \right] + \mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} \sigma_{t-1}(\boldsymbol{x}_t) \right] \right). \end{align}\] By applying Lemma 12, we obtain² \[\begin{align} \mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right] = O\left( \max \left\{ \frac{\beta_T \gamma_{\mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right]} \left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; 0\right) \right) }{\Delta_{i+1}^2}, \frac{\beta_T}{\Delta_{i+1}^2} \right\} \right), \end{align}\] and \[\begin{align} \mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right] = O\left( \sqrt{\beta_T \mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right] \tilde{\gamma}_{\mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right]}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; 0\right) \right) } \right). \end{align}\]

By taking the union bound regarding the conditions in Lemma 2 and the Markov’s inequality for \(\mathbb{E}\left[ \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \right]\) for all \(i = 0, \dots, \bar{i}\), the three conditions in Lemma 2 and the following inequalities hold simultaneously with probability at least \(1 - \delta - \delta_{\rm GP}\): \[\begin{align} \sum_{t \in \widetilde{{\cal T}}_i} f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) = O\left( \frac{\bar{i}+1}{\delta} \sqrt{\beta_T \mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right] \tilde{\gamma}_{\mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right]}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; 0\right) \right) } \right). \end{align}\] The remainder of the proof is the same as that of Lemma 3, although the dependence on \(1 / \delta\) and \(\bar{i}\) is worse. ◻

9 Supporting Lemmas↩︎

Lemma 5 (Lemma 5.1 of [6]). Suppose that Assumption 1 holds. Fix \(\delta \in (0, 1)\). Then, for any \({\cal X}\) such that \(|{\cal X}| < \infty\), the following inequality holds with probability at least \(1 - \delta\): \[\begin{align} \Pr\left( \forall t \geq 1, \forall \boldsymbol{x} \in {\cal X}, |f(\boldsymbol{x}) - \mu_{t-1}(\boldsymbol{x})| \leq \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}) \right) \geq 1 - \delta, \end{align}\] where \(\beta_t = 2\log (|{\cal X}| t (t+1) / \delta)\).

Lemma 6 (Modified from the proof of Lemmas 4 and 20 of [10]). Suppose \(f\) is continuous. Then, under conditions 1 and 3 in Lemma 2, \(\boldsymbol{x} \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \epsilon}; \boldsymbol{x}^*\right) \subset {\cal B}(\rho_{\rm quad}; \boldsymbol{x}^*)\) holds for any \(\boldsymbol{x} \in {\cal X}\) such that \(f(\boldsymbol{x}^*) - f(\boldsymbol{x}) \leq \epsilon\) with \(\epsilon \leq \min\{c_{\rm gap}, c_{\rm quad} \rho_{\rm quad}^2 \}\).

Proof. From Lemma 20 of [10], we see that \[\begin{align} \boldsymbol{x} \in {\cal B}(\rho_{\rm quad}; \boldsymbol{x}^*). \end{align}\] Hereafter, we follow the proof of Lemma 4 in [10]. From the condition 3 in Lemma 2 and \(\boldsymbol{x} \in {\cal B}(\rho_{\rm quad}; \boldsymbol{x}^*)\), we obtain \[\begin{align} \forall \boldsymbol{x} \in \{\boldsymbol{x} \in {\cal X}\mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}) \leq \epsilon \}, f(\boldsymbol{x}^*) - f(\boldsymbol{x}) \geq c_{\rm quad} \| \boldsymbol{x}^* - \boldsymbol{x} \|_2^2. \end{align}\] Since \(f(\boldsymbol{x}^*) - f(\boldsymbol{x}) \leq \epsilon\), we have \[\begin{align} c_{\rm quad} \| \boldsymbol{x}^* - \boldsymbol{x} \|_2^2 \leq \epsilon \Leftrightarrow \| \boldsymbol{x}^* - \boldsymbol{x} \|_2 \leq \sqrt{c_{\rm quad}^{-1} \epsilon}, \end{align}\] which shows the desired result \(\boldsymbol{x} \in {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \epsilon}; \boldsymbol{x}^*\right)\). ◻

Lemma 7 (Modified from Lemma 21 of [10]). Fix any index set \({\cal T}\subset [T]\). Then, we have the following inequality: \[\begin{align} \sum_{t \in {\cal T}} 2 \beta_t^{1/2} \sigma_{t-1} (\boldsymbol{x}_t) \leq 2 \sqrt{C_1 \beta_T |{\cal T}| \gamma_{|{\cal T}|}({\cal X}_{{\cal T}}) }, \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\), \({\cal X}_{{\cal T}} = \{ \boldsymbol{x}_t \}_{t \in {\cal T}}\), and \(\gamma_{|{\cal T}|}({\cal X}_{{\cal T}})\) is the MIG defined over \({\cal X}_{{\cal T}}\).

Proof. See the proof of Lemma 21 of [10]. ◻

Lemma 8 (Discretized error, Lemma H.2 of [7]). Suppose Assumptions 1 and 2 hold. Let \({\cal X}_t \subset {\cal X}\) be a finite set with each dimension equally divided into \(\tau_t = bdr u_t \bigl( \sqrt{\log (ad)} + \sqrt{\pi} / 2 \bigr)\) for any \(t \geq 1\). Then, for all \(t \geq 1\), the following inequality holds: \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}} | f(\boldsymbol{x}) - f( [\boldsymbol{x}]_t ) | \right] \leq \frac{1}{u_t}, \end{align}\] where \([\boldsymbol{x}]_t\) is the nearest point in \({\cal X}_t\) of \(\boldsymbol{x} \in {\cal X}\).

Lemma 9. Suppose Assumption 1 holds. Let \({\cal X}_t \subseteq {\cal X}\) be a finite set. Then, the following inequality holds: \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}_t} \left\{ \bigl( f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \bigr)_+ \right\} \right] &\leq \frac{1}{u_t}, \\ \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}_t} \left\{ \bigl(f(\boldsymbol{x}) - U_t ( \boldsymbol{x} )\bigr)_+^2 \right\} \right] &\leq \frac{2\beta_t^{1/2}}{u_t}, \end{align}\] where \((c)_+ = \max\{c, 0\}\) and \(U_t (\boldsymbol{x}) = \mu_{t-1}(\boldsymbol{x}) + \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x})\) with \(\beta_t = \max\{1, 2 \log (|{\cal X}_t| u_t / \sqrt{2 \pi})\}\).

Proof. As with [11], we use the following fact: \[\begin{align} \mathbb{E}[Z_+] &\leq \frac{s}{\sqrt{2\pi}} \exp \left\{ - \frac{\alpha^2}{2} \right\}, \\ \mathbb{E}[Z_+^2] &= (m^2 + s^2) \Phi(\alpha) + ms \phi(\alpha) \leq \frac{s^2 (\alpha^2 + 1)}{\sqrt{2\pi} |\alpha|} \exp \left\{ - \frac{\alpha^2}{2} \right\}, \end{align}\] where \(Z \sim {\cal N}(m, s^2)\) with \(m \leq 0\) and \(\alpha = m / s\). The former inequality is used, e.g., in [7], [11]. Both inequalities can be obtained, e.g., by the moments of the truncated normal distribution.

For the first inequality, following the proof from [11], we can see that \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}_t} \left( f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \right)_+ \right] &\leq \mathbb{E}\left[ \sum_{\boldsymbol{x} \in {\cal X}_t} \left( f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \right)_+ \right] \\ &\leq \sum_{\boldsymbol{x} \in {\cal X}_t} \mathbb{E}_{{\cal D}_{t-1}} \left[ \mathbb{E}\left[ \left( f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \right)_+ \mid {\cal D}_{t-1} \right] \right], \end{align}\] where \(f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \mid {\cal D}_{t-1}\) follows \({\cal N}(- \beta_t^{1/2} \sigma_{t-1}(\boldsymbol{x}), \sigma_{t-1}(\boldsymbol{x}))\). Therefore, we can obtain \[\begin{align} \mathbb{E}_{{\cal D}_{t-1}} \left[ \sup_{\boldsymbol{x} \in {\cal X}_t} \left\{ f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \right\} \right] &\leq \mathbb{E}\left[ \sum_{\boldsymbol{x} \in {\cal X}_t} \frac{\sigma_{t-1}(\boldsymbol{x})}{\sqrt{2\pi}} \exp \left\{ - \frac{\beta_t}{2} \right\} \right] \\ &\leq \frac{|{\cal X}_t|}{\sqrt{2\pi}} \exp \left\{ - \frac{\beta_t}{2} \right\} \\ &\leq \frac{1}{u_t}, \end{align}\] where the second and third inequalities holds because of \(\sigma_{t-1}(\boldsymbol{x}) \leq 1\) and the definition of \(\beta_t\), respectively.

For the second inequality, as with the above derivation, we see that \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}_t} \left\{ (f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ))_+^2 \right\} \right] &\leq \sum_{\boldsymbol{x} \in {\cal X}_t} \mathbb{E}_{{\cal D}_{t-1}} \left[ \mathbb{E}\left[ \left( f(\boldsymbol{x}) - U_t ( \boldsymbol{x} ) \right)_+^2 \mid {\cal D}_{t-1} \right] \right] \\ &\leq \sum_{\boldsymbol{x} \in {\cal X}_t} \mathbb{E}_{{\cal D}_{t-1}} \left[ \frac{\sigma_{t-1}^2 (\boldsymbol{x}) (\beta_t + 1)}{\sqrt{2\pi} \beta_t^{1/2}} \exp \left\{ - \frac{\beta_t}{2} \right\} \right] \\ &\leq \frac{2\beta_t^{1/2} |{\cal X}_t|}{\sqrt{2\pi}} \exp \left\{ - \frac{\beta_t}{2} \right\} \\ &\leq \frac{2\beta_t^{1/2}}{u_t}, \end{align}\] where the second and third inequalities hold because of \(\sigma_{t-1}^2(\boldsymbol{x}) \leq 1\) and the definition of \(\beta_t (\geq 1)\), respectively. ◻

Lemma 10 (Squared discretized error). Suppose Assumptions 1 and 2 hold. Let \({\cal X}_t \subset {\cal X}\) be a finite set with each dimension equally divided into \(\tau_t = \bigl\lceil b dr \sqrt{u_t \bigl(\log (ad) + 1 \bigr)} \bigr \rceil\) for any \(t \geq 1\). Then, for all \(t \geq 1\), the following inequality holds: \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}} \bigl( f(\boldsymbol{x}) - f( [\boldsymbol{x}]_t ) \bigr)^2 \right] \leq \frac{1}{u_t}, \end{align}\] where \([\boldsymbol{x}]_t\) is the nearest point in \({\cal X}_t\) of \(\boldsymbol{x} \in {\cal X}\).

Proof. Let \(L_f\) be the Lipschitz constant of \(f\). From Assumption 2, we see that \[\begin{align} \Pr(L_f^2 > c) \leq ad \exp \left( - \frac{c}{b^2} \right). \end{align}\] Therefore, we can obtain \[\begin{align} \mathbb{E}\bigl[L_f^2\bigr] &= \int_{0}^\infty \Pr(L_f^2 > c) {\rm d} c \\ &\leq \int_{0}^\infty \min\{1, ad e^{- c / b^2} \} {\rm d} c \\ &= b^2 \log(ad) + \int_{b^2 \log(ad)}^\infty ad e^{- c / b^2} {\rm d} c \\ &= b^2 \log(ad) + b^2 \int_{\log(ad)}^\infty ad e^{- c} {\rm d} c \\ &= b^2 \bigl(\log(ad) + 1 \bigr). \end{align}\] Then, we see that \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}} \bigl( f(\boldsymbol{x}) - f( [\boldsymbol{x}]_t ) \bigr)^2 \right] \leq \mathbb{E}\left[ L_f^2 \sup_{\boldsymbol{x} \in {\cal X}} \|\boldsymbol{x} - [\boldsymbol{x}]_t \|_1^2 \right]. \end{align}\] From the construction of \({\cal X}_t\), we see that \[\begin{align} \sup_{\boldsymbol{x} \in {\cal X}} \|\boldsymbol{x} - [\boldsymbol{x}]_t \|_1^2 \leq \frac{1}{b^2 u_t \bigl(\log(ad) + 1 \bigr)}. \end{align}\] Therefore, we derive \[\begin{align} \mathbb{E}\left[ \sup_{\boldsymbol{x} \in {\cal X}} \bigl( f(\boldsymbol{x}) - f( [\boldsymbol{x}]_t ) \bigr)^2 \right] &\leq \frac{\mathbb{E}\bigl[ L_f^2 \bigr]}{b^2 u_t \bigl(\log(ad) + 1 \bigr)} \\ &\leq \frac{1}{u_t}. \end{align}\] ◻

Lemma 11. Suppose Assumption 1 holds. Fix \(\Delta > 0\) and let \({\cal T}= \{ t \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta\}\). Then, if Algorithm 1 runs, the following inequality holds: \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] &\leq C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}, \\ \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}_t) \right] &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}, \end{align}\] and \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] &\leq C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}, \\ \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}^*) \right] &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}}, \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\).

Proof. First, we can see that \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] &\overset{(a)}{\leq} C_1 \mathbb{E}[\gamma_{|{\cal T}|}] \\ &\overset{(b)}{=} C_1 \mathbb{E}[\tilde{\gamma}_{|{\cal T}|}] \\ &\overset{(c)}{\leq} C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}. \end{align}\] The inequalities hold because of (a) \(\sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \leq C_1 \gamma_{|{\cal T}|}\) from Lemma 7, (b) \(\gamma_T = \tilde{\gamma}_T\) for any \(T \in \mathbb{N}\), and (c) Jensen’s inequality and the concavity of \(\tilde{\gamma}_T\).

For the proof with respect to \(\sigma_{t-1}^2(\boldsymbol{x}^*)\), we use the property of \({\cal T}_g = \{ t \mid g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta\}\). Let \(\mathbb{1}_E\) be the indicator function that is 1 if \(E\) is true, and 0 otherwise. Since \(\bigl(\mathbb{1}_{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta} \mid {\cal D}_{t-1} \bigr)\) and \(\bigl(\mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \mid {\cal D}_{t-1} \bigr)\) follow the identical distribution, we can see that \[\begin{align} \mathbb{E}[ |{\cal T}| ] &= \mathbb{E}_{{\cal D}_{t-1}} \left[ \sum_{t=1}^T \mathbb{E}\left[ \mathbb{1}_{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta} \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}_{{\cal D}_{t-1}} \left[ \sum_{t=1}^T \mathbb{E}\left[ \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}\left[ \sum_{t=1}^T \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \right] \\ &= \mathbb{E}[|{\cal T}_g|]. \end{align}\]

Then, we can show the results regarding \(\sigma_{t-1}^2(\boldsymbol{x}^*)\) as follows: \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] &= \mathbb{E}_{{\cal D}_{t-1}} \left[ \sum_{t \in [T]} \mathbb{E}\left[ \sigma_{t-1}^2(\boldsymbol{x}^*) \mathbb{1}_{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta} \mid {\cal D}_{t-1} \right] \right] \\ &\overset{(a)}{=} \mathbb{E}_{{\cal D}_{t-1}} \left[ \sum_{t \in [T]} \mathbb{E}\left[ \sigma_{t-1}^2(\boldsymbol{x}_t) \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}\left[ \sum_{t \in [T]} \sigma_{t-1}^2(\boldsymbol{x}_t) \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \right] \\ &\overset{(b)}{\leq} C_1 \mathbb{E}[\gamma_{|{\cal T}_g|}] \\ &\overset{(c)}{\leq} C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}_g|]} \\ &= C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}. \end{align}\] The equalities and inequalities hold because (a) \(\bigl(\sigma_{t-1}^2(\boldsymbol{x}^*) \mathbb{1}_{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta} \mid {\cal D}_{t-1} \bigr)\) and \(\bigl(\sigma_{t-1}^2(\boldsymbol{x}_t) \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \mid {\cal D}_{t-1} \bigr)\) follow the identical distribution, (b) \(\sum_{t \in {\cal T}_g} \sigma_{t-1}^2(\boldsymbol{x}_t) \leq C_1 \gamma_{|{\cal T}_g|}\) from Lemma 7, and (c) \(\gamma_T = \tilde{\gamma}_T\) for any \(T \in \mathbb{N}\) and \(\tilde{\gamma}_T\) is a concave function.

Furthermore, by the same reasons shown above, we can see that \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}^*) \right] &= \mathbb{E}_{{\cal D}_{t-1}} \left[ \sum_{t \in [T]} \mathbb{E}\left[ \sigma_{t-1}(\boldsymbol{x}^*) \mathbb{1}_{f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta} \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}_{{\cal D}_{t-1}} \left[ \sum_{t \in [T]} \mathbb{E}\left[ \sigma_{t-1}(\boldsymbol{x}_t) \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}\left[ \sum_{t \in [T]} \sigma_{t-1}(\boldsymbol{x}_t) \mathbb{1}_{g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta} \right] \\ &\leq \mathbb{E}\left[ \sqrt{C_1 |{\cal T}_g| \gamma_{|{\cal T}_g|}} \right] \\ &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}_g|] \gamma_{\mathbb{E}[|{\cal T}_g|]}} \\ &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}|] \gamma_{\mathbb{E}[|{\cal T}|]}}. \end{align}\] ◻

Lemma 12. Suppose Assumption 1 holds and \(k = k_{\rm SE}\) or \(k = k_{\rm Mat}\) with \(\nu > 1/2\). Fix \(\Delta, \rho > 0\) and let \({\cal T}= \left\{t \in [T] \mid f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \land \boldsymbol{x}_t \in {\cal B}\left(\rho; \boldsymbol{x}^*\right) \right\}\). Then, if Algorithm 1 runs, the following inequality holds: \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] &\leq C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}\left({\cal B}\left(\rho; 0\right)\right), \\ \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}_t) \right] &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} \left({\cal B}\left(\rho; 0\right)\right) }, \end{align}\] and \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] &\leq C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]}\left({\cal B}\left(\rho; 0\right)\right), \\ \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}^*) \right] &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} \left({\cal B}\left(\rho; 0\right)\right)}, \end{align}\] where \(C_1 = 2 / \log(1 + \sigma^{-2})\) and \(\tilde{\gamma}_T ({\cal X})\) is the MIG over the domain \({\cal X}\).

Proof. First, we can see that \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] &\overset{(a)}{\leq} C_1 \mathbb{E}[\gamma_{|{\cal T}|} \left({\cal B}\left(\rho; \boldsymbol{x}^*\right)\right)] \\ &\overset{(b)}{=} C_1 \mathbb{E}[\tilde{\gamma}_{|{\cal T}|} \left({\cal B}\left(\rho; 0\right)\right)] \\ &\overset{(c)}{\leq} C_1 \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} \left({\cal B}\left(\rho; 0\right)\right). \end{align}\] The inequalities hold because of (a) \(\sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \leq C_1 \gamma_{|{\cal T}|} \left({\cal B}\left(\rho; \boldsymbol{x}^*\right)\right)\) from Lemma 7 and \(\boldsymbol{x}_t \in {\cal B}\left(\rho; \boldsymbol{x}^*\right)\), (b) \(\gamma_T \left({\cal B}\left(\rho; \boldsymbol{x}^*\right) \right) = \tilde{\gamma}_T \left({\cal B}\left(\rho; 0\right)\right)\) for any \(T \in \mathbb{N}\) due to the definition of \(\tilde{\gamma}\) and the shift-invariant property of the SE and Matérn kernels, and (c) Jensen’s inequality and the concavity of \(\tilde{\gamma}_T\).

Second, we can obtain \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}_t) \right] &\overset{(a)}{\leq} \mathbb{E}\left[ \sqrt{|{\cal T}| \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t)} \right] \\ &\overset{(b)}{\leq} \mathbb{E}\left[ \sqrt{C_1 |{\cal T}| \gamma_{|{\cal T}|} \left({\cal B}\left(\rho; \boldsymbol{x}^*\right)\right) } \right] \\ &\overset{(c)}{\leq} \mathbb{E}\left[ \sqrt{C_1 |{\cal T}| \tilde{\gamma}_{|{\cal T}|} \left({\cal B}\left(\rho; 0\right)\right) } \right] \\ &\overset{(d)}{\leq} \sqrt{C_1 \mathbb{E}[|{\cal T}|] \mathbb{E}\left[ \tilde{\gamma}_{|{\cal T}|} \left({\cal B}\left(\rho; 0\right)\right) \right]} \\ &\overset{(e)}{\leq} \sqrt{C_1 \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} \left({\cal B}\left(\rho; 0\right)\right) }. \end{align}\] The inequalities hold because of (a) Cauchy–Schwarz inequality (b) \(\sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \leq C_1 \gamma_{|{\cal T}|} \left({\cal B}\left(\rho; \boldsymbol{x}^*\right)\right)\) from Lemma 7 and \(\boldsymbol{x}_t \in {\cal B}\left(\rho; \boldsymbol{x}^*\right)\), (c) \(\gamma_T \left({\cal B}\left(\rho; \boldsymbol{x}^*\right) \right) = \tilde{\gamma}_T \left({\cal B}\left(\rho; 0\right)\right)\) for any \(T \in \mathbb{N}\) due to the definition of \(\tilde{\gamma}\) and the shift-invariant property of the SE and Matérn kernels, (d) Cauchy–Schwarz inequality (\(|\mathbb{E}[XY]| \leq \sqrt{\mathbb{E}[X^2] \mathbb{E}[Y^2]}\) for any random variables \(X\) and \(Y\)), and (e) Jensen’s inequality and the concavity of \(\tilde{\gamma}_t\).

For the proof with respect to \(\sigma_{t-1}^2(\boldsymbol{x}^*)\), we use the property of \({\cal T}_g = \left\{ t \in [T] \bigm| g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho \right\}\). Let \(\mathbb{1}_E\) be the indicator function that is 1 if \(E\) is true, and 0 otherwise. We can see that \[\begin{align} \mathbb{E}\left[\left| {\cal T}\right|\right] &= \mathbb{E}\left[ \sum_{t = 1}^T \mathbb{E}\left[ \mathbb{1}_{ f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho } \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}\left[ \sum_{t = 1}^T \mathbb{E}\left[ \mathbb{1}_{ g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho } \mid {\cal D}_{t-1} \right] \right] \\ &= \mathbb{E}\left[\left| {\cal T}_g \right|\right], \end{align}\] where the second equality holds since \(\bigl( \mathbb{1}_{ f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho } \mid {\cal D}_{t-1} \bigr)\) and \(\bigl(\mathbb{1}_{ g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho } \mid {\cal D}_{t-1}\bigr)\) are identically distributed.

Then, we have \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}^*) \right] &= \mathbb{E}\left[ \sum_{t \in [T]} \mathbb{E}\left[ \sigma_{t-1}^2(\boldsymbol{x}^*) \mathbb{1}_{ f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \land \boldsymbol{x}_t \in {\cal B}\left(\rho; \boldsymbol{x}^*\right) } \biggm| {\cal D}_{t-1} \right]\right] \\ &\overset{(a)}{=} \mathbb{E}\left[ \sum_{t \in [T]} \mathbb{E}\left[ \sigma_{t-1}^2(\boldsymbol{x}_t) \mathbb{1}_{ g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho } \biggm| {\cal D}_{t-1} \right] \right]\\ &= \mathbb{E}\left[ \sum_{t \in {\cal T}_g} \sigma_{t-1}^2(\boldsymbol{x}_t) \right] \\ &\overset{(b)}{\leq} C_1\mathbb{E}\left[ \gamma_{|{\cal T}_g|} \left({\cal B}\left(\rho; \boldsymbol{x}^*\right)\right) \right] \\ &\overset{(c)}{\leq} C_1\mathbb{E}\left[ \tilde{\gamma}_{|{\cal T}_g|} \left({\cal B}\left(\rho; 0\right)\right) \right] \\ &\overset{(d)}{\leq} C_1 \tilde{\gamma}_{\mathbb{E}\left[|{\cal T}_g|\right]} \left({\cal B}\left(\rho; 0\right)\right) \\ &= C_1 \tilde{\gamma}_{\mathbb{E}\left[|{\cal T}|\right]} \left({\cal B}\left(\rho; 0\right)\right) \end{align}\] where the equality and inequality hold because (a) \(\bigl( \sigma_{t-1}^2(\boldsymbol{x}^*) \mathbb{1}_{ f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t) \geq \Delta \land \boldsymbol{x}_t \in {\cal B}\left(\rho; \boldsymbol{x}^*\right) } \mid {\cal D}_{t-1} \bigr)\) and \(\bigl( \sigma_{t-1}^2(\boldsymbol{x}_t) \mathbb{1}_{ g_t(\boldsymbol{x}_t) - g_t(\boldsymbol{x}^*) \geq \Delta \land \|\boldsymbol{x}_t - \boldsymbol{x}^*\|_2 \leq \rho } \mid {\cal D}_{t-1} \bigr)\) are identically distributed, (b) \(\sum_{t \in {\cal T}} \sigma_{t-1}^2(\boldsymbol{x}_t) \leq C_1 \gamma_{|{\cal T}|} \left({\cal B}\left(\rho; \boldsymbol{x}^*\right)\right)\) from Lemma 7 and \(\boldsymbol{x}_t \in {\cal B}\left(\rho; \boldsymbol{x}^*\right)\), (c) \(\gamma_T \left({\cal B}\left(\rho; \boldsymbol{x}^*\right) \right) = \tilde{\gamma}_T \left({\cal B}\left(\rho; 0\right)\right)\) for any \(T \in \mathbb{N}\) due to the definition of \(\tilde{\gamma}\) and the shift-invariant property of the SE and Matérn kernels, and (d) Jensen’s inequality and the concavity of \(\tilde{\gamma}_T\). By almost the same arguments shown above and Lemma 11, we further obtain \[\begin{align} \mathbb{E}\left[ \sum_{t \in {\cal T}} \sigma_{t-1}(\boldsymbol{x}^*) \right] &\leq \sqrt{C_1 \mathbb{E}[|{\cal T}|] \tilde{\gamma}_{\mathbb{E}[|{\cal T}|]} \left({\cal B}\left(\rho; 0\right)\right)}, \end{align}\] which concludes the proof. ◻

References↩︎

[1]

H. J. Kushner, “A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise,” Journal of Basic Engineering, vol. 86, no. 1, pp. 97–106, 1964.

[2]

J. Mockus, V. Tiesis, and A. Zilinskas, “The application of Bayesian methods for seeking the extremum,” Towards Global Optimization, vol. 2, no. 117–129, p. 2, 1978.

[3]

T. Ueno, T. D. Rhone, Z. Hou, T. Mizoguchi, and K. Tsuda, “COMBO: An efficient Bayesian optimization library for materials science,” Materials discovery, vol. 4, pp. 18–21, 2016.

[4]

J. Snoek, H. Larochelle, and R. P. Adams, “Practical Bayesian optimization of machine learning algorithms,” in Advances in neural information processing systems 25, 2012, pp. 2951–2959.

[5]

K. Korovina et al., “ChemBO: Bayesian optimization of small organic molecules with synthesizable recommendations,” in Proceedings of the 23rd international conference on artificial intelligence and statistics, 2020, vol. 108, pp. 3393–3403.

[6]

N. Srinivas, A. Krause, S. Kakade, and M. Seeger, “Gaussian process optimization in the bandit setting: No regret and experimental design,” in Proceedings of the 27th international conference on machine learning, 2010, pp. 1015–1022.

[7]

S. Takeno, Y. Inatsu, and M. Karasuyama, “Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds,” in Proceedings of the 40th international conference on machine learning, 2023, vol. 202, pp. 33490–33515.

[8]

N. Merlis and S. Mannor, “Lenient regret for multi-armed bandits,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 10, pp. 8950–8957, 2021.

[9]

X. Cai, S. Gomes, and J. Scarlett, “Lenient regret and good-action identification in Gaussian process bandits,” in Proceedings of the 38th international conference on machine learning, 2021, vol. 139, pp. 1183–1192.

[10]

S. Iwazaki, “Improved regret bounds for Gaussian process upper confidence bound in Bayesian optimization,” in Advances in neural information processing systems, 2025, vol. 38, pp. 96922–96964.

[11]

D. Russo and B. Van Roy, “Learning to optimize via posterior sampling,” Mathematics of Operations Research, vol. 39, no. 4, pp. 1221–1243, 2014.

[12]

K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Póczos, “Parallelised Bayesian optimisation via Thompson sampling,” in Proceedings of the 21st international conference on artificial intelligence and statistics, 2018, vol. 84, pp. 133–142.

[13]

S. Takeno, Y. Inatsu, M. Karasuyama, and I. Takeuchi, “Posterior sampling-based Bayesian optimization with tighter Bayesian regret bounds,” in Proceedings of the 41st international conference on machine learning, 2024, vol. 235, pp. 47510–47534.

[14]

S. R. Chowdhury and A. Gopalan, “On kernelized multi-armed bandits,” in Proceedings of the 34th international conference on machine learning, 2017, vol. 70, pp. 844–853.

[15]

S. Iwazaki and S. Takeno, “Improved regret analysis in Gaussian process bandits: Optimality for noiseless reward, RKHS norm, and non-stationary variance,” in Proceedings of the 42nd international conference on machine learning, 2025, vol. 267, pp. 26642–26672.

[16]

S. Iwazaki, “Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free Gaussian process bandits,” in Advances in neural information processing systems, 2025, vol. 38, pp. 65863–65886.

[17]

D. Janz, D. Burt, and J. Gonzalez, “Bandit optimisation of functions in the Matérn kernel RKHS,” in Proceedings of the 23rd international conference on artificial intelligence and statistics, 2020, vol. 108, pp. 2486–2495.

[18]

J. Scarlett, “Tight regret bounds for Bayesian optimization in one dimension,” in Proceedings of the 35th international conference on machine learning, 2018, vol. 80, pp. 4500–4508.

[19]

N. De Freitas, A. J. Smola, and M. Zoghi, “Exponential regret bounds for Gaussian process bandits with deterministic observations,” in Proceedings of the 29th international conference on machine learning, 2012, pp. 955–962.

[20]

S. Vakili, H. Moss, A. Artemev, V. Dutordoir, and V. Picheny, “Scalable Thompson sampling using sparse Gaussian process models,” in Advances in neural information processing systems, 2021, vol. 34, pp. 5631–5643.

[21]

J. M. Hernández-Lobato, J. Requeima, E. O. Pyzer-Knapp, and A. Aspuru-Guzik, “Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space,” in Proceedings of the 34th international conference on machine learning, 2017, vol. 70, pp. 1470–1479.

[22]

E. Nava, M. Mutny, and A. Krause, “Diversified sampling for batched Bayesian optimization with determinantal point processes,” in Proceedings of the 25th international conference on artificial intelligence and statistics, 2022, vol. 151, pp. 7031–7054.

[23]

D. Eriksson and M. Poloczek, “Scalable constrained Bayesian optimization,” in Proceedings of the 24th international conference on artificial intelligence and statistics, 2021, vol. 130, pp. 730–738.

[24]

E. Bradford, A. M. Schweidtmann, and A. Lapkin, “Efficient multiobjective optimization employing Gaussian processes, spectral sampling and a genetic algorithm,” Journal of global optimization, vol. 71, no. 2, pp. 407–438, 2018.

[25]

B. Paria, K. Kandasamy, and B. Póczos, “A flexible framework for multi-objective Bayesian optimization using random scalarizations,” in Proceedings of the 35th uncertainty in artificial intelligence conference, 2020, vol. 115, pp. 766–776.

[26]

A. Renganathan and K. Carlson, “qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling,” in Proceedings of the 28th international conference on artificial intelligence and statistics, 2025, vol. 258, pp. 4051–4059.

[27]

Y. Sui, V. Zhuang, J. W. Burdick, and Y. Yue, “Multi-dueling bandits with dependent arms,” in Proceedings of uncertainty in artificial intelligence, 2017.

[28]

J. Bayrooti, S. Vakili, A. Prorok, and C. H. Ek, “Reinforcement learning with Thompson sampling: No-regret performance over finite horizons,” in The exploration in AI today workshop at ICML 2025, 2025.

[29]

J. Bayrooti, S. Vakili, A. Prorok, and C. H. Ek, “No-regret Thompson sampling for finite-horizon Markov decision processes with Gaussian processes,” in Advances in neural information processing systems, 2025, vol. 38, pp. 72894–72922.

[30]

J. Wilson, V. Borovitskiy, A. Terenin, P. Mostowsky, and M. Deisenroth, “Efficiently sampling functions from Gaussian process posteriors,” in Proceedings of the 37th international conference on machine learning, 2020, vol. 119, pp. 10292–10302.

[31]

J. T. Wilson, V. Borovitskiy, A. Terenin, P. Mostowsky, and M. P. Deisenroth, “Pathwise conditioning of Gaussian processes,” Journal of Machine Learning Research, vol. 22, no. 105, pp. 1–47, 2021.

[32]

A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Advances in neural information processing systems 20, 2008, pp. 1177–1184.

[33]

M. Mutny and A. Krause, “Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features,” Advances in Neural Information Processing Systems 31, pp. 9005–9016, 2018.

[34]

P. Frazier, W. Powell, and S. Dayanik, “The knowledge-gradient policy for correlated normal beliefs,” INFORMS journal on Computing, vol. 21, no. 4, pp. 599–613, 2009.

[35]

P. Hennig and C. J. Schuler, “Entropy search for information-efficient global optimization,” Journal of Machine Learning Research, vol. 13, no. 57, pp. 1809–1837, 2012.

[36]

J. Villemonteix, E. Vazquez, and E. Walter, “An informational approach to the global optimization of expensive-to-evaluate functions,” Journal of Global Optimization, vol. 44, no. 4, pp. 509–534, 2009.

[37]

J. M. Hernández-Lobato, M. W. Hoffman, and Z. Ghahramani, “Predictive entropy search for efficient global optimization of black-box functions,” in Advances in neural information processing systems 27, 2014, pp. 918–926.

[38]

S. Takeno, Y. Inatsu, and M. Karasuyama, “Regret analysis for randomized Gaussian process upper confidence bound,” Journal of Artificial Intelligence Research, vol. 84, no. 18, 2025.

[39]

S. Takeno, Y. Inatsu, M. Karasuyama, and I. Takeuchi, “Regret analysis of posterior sampling-based expected improvement for Bayesian optimization,” Transactions on Machine Learning Research, 2025, [Online]. Available: https://openreview.net/forum?id=v0s9knY99c.

[40]

W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” Biometrika, vol. 25, no. 3–4, pp. 285–294, 1933.

[41]

D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen, “A tutorial on Thompson sampling,” Found. Trends Mach. Learn., vol. 11, no. 1, pp. 1–96, 2018.

[42]

S. Agrawal and N. Goyal, “Near-optimal regret bounds for Thompson sampling,” Journal of the ACM, vol. 64, no. 5, 2017.

[43]

C. E. Rasmussen and C. K. I. Williams, Gaussian processes for machine learning (adaptive computation and machine learning). The MIT Press, 2005.

[44]

S. Takeno et al., “Distributionally robust active learning for Gaussian process regression,” in Proceedings of the 42nd international conference on machine learning, 2025, vol. 267, pp. 58339–58358.

[45]

S. Kusakawa et al., “Bayesian optimization for cascade-type multistage processes,” Neural Computation, vol. 34, no. 12, pp. 2408–2431, 2022.

[46]

S. Vakili, K. Khezeli, and V. Picheny, “On information gain and regret bounds in Gaussian process bandits,” in Proceedings of the 24th international conference on artificial intelligence and statistics, 2021, vol. 130, pp. 82–90.

[47]

S. Iwazaki, To appear“Tighter regret lower bound for Gaussian process bandits with squared exponential kernel in hypersphere,” in Proceedings of the 43rd international conference on machine learning, 2026.

[48]

D. Janz, “Sequential decision making with feature-linear models,” PhD thesis, University of Cambridge, 2021.

[49]

H. Flynn and D. Reeb, “Tighter confidence bounds for sequential kernel regression,” in Proceedings of the 28th international conference on artificial intelligence and statistics, 2025, vol. 258, pp. 3844–3852.

[50]

K. Kandasamy, G. Dasarathy, J. Oliva, J. Schneider, and B. Póczos, “Gaussian process bandit optimisation with multi-fidelity evaluations,” in Advances in neural information processing systems 29, 2016, pp. 1000–1008.

[51]

K. Kandasamy, G. Dasarathy, J. Schneider, and B. Póczos, “Multi-fidelity Bayesian optimisation with continuous approximations,” in Proceedings of the 34th international conference on machine learning, 2017, vol. 70, pp. 1799–1808.

[52]

S. Takeno et al., “Multi-fidelity Bayesian optimization with max-value entropy search and its parallelization,” in Proceedings of the 37th international conference on machine learning, 2020, vol. 119, pp. 9334–9345.

[53]

S. Takeno et al., “A Generalized Framework of Multifidelity Max-Value Entropy Search Through Joint Entropy,” Neural Computation, vol. 34, no. 10, pp. 2145–2203, 2022.

[54]

Y. Inatsu, S. Takeno, H. Hanada, K. Iwata, and I. Takeuchi, “Bounding box-based multi-objective Bayesian optimization of risk measures under input uncertainty,” in Proceedings of the 27th international conference on artificial intelligence and statistics, 2024, vol. 238, pp. 4564–4572.

[55]

M. Zuluaga, A. Krause, and M. Püschel, “\(\epsilon\)-PAL: An active learning approach to the multi-objective optimization problem,” Journal of Machine Learning Research, vol. 17, no. 104, pp. 1–32, 2016.

[56]

P. Billingsley, Convergence of probability measures. John Wiley & Sons, 2013.

Although [46] claimed the tighter MIG upper bound for Matérn kernels, we use the bound from [10] due to the issue pointed out by [10], [48].↩︎
For the case of Matérn kernels, although the upper bound \(\mathbb{E}\left[\left| \widetilde{{\cal T}}_i \right|\right] = O(\beta_T / \Delta_{i+1}^2)\) is worse by \(\log T\) factor than that in Lemma 3, we can apply the same proof since the logarithmic factor does not change the result. Alternatively, we can remove \(\beta_T\) by a finer discretization.↩︎

On Regret Bounds of Thompson Sampling
for Bayesian Optimization
On Regret Bounds of Thompson Sampling
for Bayesian Optimization

Abstract

1 Introduction↩︎

2 Preliminaries↩︎

2.1 Problem Setup↩︎

2.2 Gaussian Process Regression↩︎

2.3 Maximum Information Gain (MIG)↩︎

2.4 Gaussian Process Thompson Sampling↩︎

3 Regret Analysis↩︎

3.1 Regret Lower Bound↩︎

3.1.0.1 Proof sketch.

3.1.0.2 Extendability of Theorem 1.

3.1.0.3 Contradictions from the existing study.

3.2 Improved Regret Upper Bounds Regarding \(\delta\)↩︎

3.2.0.1 Proof sketch.

3.3 Lenient Regret Upper Bounds↩︎

3.3.0.1 Proof sketch.

3.4 Improved Regret Upper Bound Regarding \(T\)↩︎

3.4.0.1 Difference from the proof of [10].

3.4.0.2 Proof sketch.

3.4.0.3 Proof sketch.

4 Conclusion and Discussion↩︎

Acknowledgements↩︎

5 Proof of Theorem 1 ↩︎

5.0.0.1 Probability of \(E_f\):

5.0.0.2 Probability of \(E_{\epsilon}\):

5.0.0.3 Probability of \(E_{\rm TS}\):

5.0.0.4 Resulting lower bound:

6 Proof of Theorem 2 ↩︎

7 Proof of Theorem 3 ↩︎

8 Proof of Theorem 4 ↩︎

8.0.0.1 Case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} \geq \frac{\pi^2}{3 \Delta_{i+1}^2}\).

8.0.0.2 Case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} < \frac{\pi^2}{3 \Delta_{i+1}^2}\).

8.0.0.3 Case of \(\frac{\nu d}{2(\nu + d)} \geq 1\).

8.0.0.4 Case of \(\frac{\nu d}{2(\nu + d)} < 1\).

9 Supporting Lemmas↩︎

References↩︎

Subjects

Updated on Academus

On Regret Bounds of Thompson Sampling for Bayesian OptimizationOn Regret Bounds of Thompson Sampling for Bayesian Optimization

Abstract

1 Introduction↩︎

1.1 Related Work↩︎

2 Preliminaries↩︎

2.1 Problem Setup↩︎

2.2 Gaussian Process Regression↩︎

2.3 Maximum Information Gain (MIG)↩︎

2.4 Gaussian Process Thompson Sampling↩︎

3 Regret Analysis↩︎

3.1 Regret Lower Bound↩︎

3.1.0.1 Proof sketch.

3.1.0.2 Extendability of Theorem 1.

3.1.0.3 Contradictions from the existing study.

3.2 Improved Regret Upper Bounds Regarding \(\delta\)↩︎

3.2.0.1 Proof sketch.

3.3 Lenient Regret Upper Bounds↩︎

3.3.0.1 Proof sketch.

3.4 Improved Regret Upper Bound Regarding \(T\)↩︎

3.4.0.1 Difference from the proof of [10].

3.4.0.2 Proof sketch.

3.4.0.3 Proof sketch.

4 Conclusion and Discussion↩︎

Acknowledgements↩︎

5 Proof of Theorem 1↩︎

5.0.0.1 Probability of \(E_f\):

5.0.0.2 Probability of \(E_{\epsilon}\):

5.0.0.3 Probability of \(E_{\rm TS}\):

5.0.0.4 Resulting lower bound:

6 Proof of Theorem 2↩︎

7 Proof of Theorem 3↩︎

8 Proof of Theorem 4↩︎

8.0.0.1 Case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} \geq \frac{\pi^2}{3 \Delta_{i+1}^2}\).

8.0.0.2 Case of \(\frac{8 C_1 \beta_T \gamma_{|{\cal T}_i|}\left( {\cal B}\left(\sqrt{c_{\rm quad}^{-1} \Delta_i }; \boldsymbol{x}^*\right) \right)}{\Delta_{i+1}^2} < \frac{\pi^2}{3 \Delta_{i+1}^2}\).

8.0.0.3 Case of \(\frac{\nu d}{2(\nu + d)} \geq 1\).

8.0.0.4 Case of \(\frac{\nu d}{2(\nu + d)} < 1\).

9 Supporting Lemmas↩︎

References↩︎

Subjects

Updated on Academus

On Regret Bounds of Thompson Sampling
for Bayesian Optimization
On Regret Bounds of Thompson Sampling
for Bayesian Optimization

5 Proof of Theorem 1 ↩︎

6 Proof of Theorem 2 ↩︎

7 Proof of Theorem 3 ↩︎

8 Proof of Theorem 4 ↩︎