arXiv CS open access

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

2026 · arxiv_cs

arXiv CS · Papers · 2026

deep-learning machine-learning neural-networks

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization Shion Takeno1 and Shogo Iwazaki2 1

Nagoya University 2

MI-6 Ltd.

takeno.s.mllab.nit@gmail.com

arXiv:2608.16492v1 [stat.ML] 17 Aug 2026

shogo.iwazaki@gmail.com

Abstract This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size Q. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for Q at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on Q can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.

Introduction

Gaussian process (GP) bandit optimization [Chowdhury and Gopalan, 2017, Srinivas et al., 2010] has emerged as a powerful framework for black-box optimization of expensive-to-evaluate functions, which is required in various scientific and engineering domains. For this purpose, GP bandit methods model the unknown objective function by a GP and sequentially select evaluation points. However, in many practical scenarios, such as high-throughput screening or asynchronous distributed computing, function evaluations can be performed in parallel or subject to delayed feedback [Hernández-Lobato et al., 2017, Kandasamy et al., 2018]. In such parallel and delayed settings, the algorithm must select new query points without waiting for the results of recent queries, while maintaining query point diversity. For this problem, batched and parallel variants of GP bandit algorithms have been proposed. A fundamental theoretical challenge in these settings is the degradation of the cumulative regret bound by a multiplicative factor of the batch size or delay parameter Q. For instance, the regret bounds of GP batched upper confidence bound (GP-BUCB) [Chowdhury and Gopalan, 2019, Desautels et al., 2014] and GP batched Thompson Sampling (GP-BTS) [Chowdhury and Gopalan, 2019, Vakili et al., 2021c] suffer from a multiplicative factor on Q. This can lead to substantial degradation, particularly with massive parallelization (Q > 100) [Hernández-Lobato et al., 2017, Vakili et al., 2021c]. To avoid this issue, the known analysis by Desautels et al. [2014] requires an initial phase of uncertainty sampling (US), which degrades the practical optimization performance. 1

Table 1: Summary of cumulative regret upper bounds for GP-BTS and GP-TS in the noisy setting e suppresses with respect to the number of function evaluations T and the batch size Q. Note that O polylogarithmic factors for Q and T . See Theorem 4.3 for the details and the simple regret bounds. SE p O Q lnd+1 Q+ T ln2d+3 T q T O QT lnd+1 Q lnd+2 T p T ln2d+3 T O

GP-BTS (Ours) GP-BTS (Based on [Vakili et al., 2021c]) sequential GP-TS [Chowdhury and Gopalan, 2017]

Matérn 2ν+3d e Q 2ν+d 2ν + T 4ν+2d O 2ν+3d ν e Q 2ν+d O T 4ν+2d e T 2ν+3d 4ν+2d O

Table 2: Summary of cumulative regret upper bounds of GP-BTS, GP-UCB-based batched method (GP-UCB-batch), and sequential GP-UCB in the noiseless setting with respect to the number of function e suppresses polylogarithmic factors for Q and T . See evaluations T and the batch size Q. Note that O Theorem 4.5 for the details. Matérn Method

d>ν

d=ν d<ν 1 5 e Q + Q νd T d GP-BTS (Ours) O(Q+ln T ) O O Q ln 2 T O Q ln 2 T q 2d+3 e Q 12 T 2ν+3d 4ν+2d GP-UCB-batch [Lyu et al., 2019] O QT ln T O e T d−ν d sequential GP-UCB [Iwazaki, 2025a] O(1) O O ln2 T O(1)

1 2

d−ν

In this paper, we resolve the above problem by an improved regret analysis technique and apply it to GP-BTS as an example. We summarize our main contributions as follows: • We develop Lemma 4.2, which plays a key role in decoupling the batch size Q as the additional term from the regret upper bound. • We prove that GP-BTS achieves a cumulative regret bound in the noisy setting with only an additive degradation of Q, eliminating the need for the practically inefficient initial US phase, as summarized in Table 1. • We provide the regret upper bounds for GP-BTS in the noiseless setting by leveraging the proof technique of [Iwazaki, 2025a], demonstrating that the regret upper bounds are much better than in the noisy case, as summarized in Table 2.

1.1

Related work

Sequential GP bandits. In the sequential setting, the theoretical properties of GP bandits have been extensively studied under the frequentist assumption that the objective function belongs to a reproducing kernel Hilbert space (RKHS). In particular, GP-UCB [Chowdhury and Gopalan, 2017, Srinivas et al., 2010] and GP-TS [Chowdhury and Gopalan, 2017] achieve the sublinear cumulative regret bounds. Several algorithms, such as phased elimination (PE) and SupKernelUCB, achieve near-optimal regret bounds but are often impractical or computationally complex [Calandriello et al., 2019, Iwazaki and Takeno, 2025, Janz et al., 2020, Li and Scarlett, 2022, Vakili et al., 2021a, Valko et al., 2013]. In particular, although PE 2

can readily yield a near-optimal regret bound in the parallel setting, we focus on the analysis of GP-BTS due to PE’s practical ineffectiveness. Parallel GP bandits. The regret bounds of parallel GP bandits have been explored through various approaches. GP-BUCB [Chowdhury and Gopalan, 2019, Desautels et al., 2014] and GP-BTS [Chowdhury and Gopalan, 2019, Vakili et al., 2021c] suffer from the multiplicative factor on Q in the regret upper bound. Although Contal et al. [2013] claimed that GP-UCB with pure exploration (GP-UCB-PE) achieves the cumulative regret upper bound without the multiplicative factor on Q, its proof leaves some technical ambiguities, 1 making the exact regret behavior unclear. Similarly, under Bayesian assumptions, several regret upper bounds, which also suffer from a multiplicative factor on Q, have been shown [Desautels et al., 2014, Kandasamy et al., 2018, Nava et al., 2022, Sugiura et al., 2026]. Our work resolves this fundamental bottleneck by achieving an additive factor on Q without any initial US phase. Stochastically delayed GP bandits. Recently, Verma et al. [2022] and Vakili et al. [2023] have studied GP bandits for the stochastic delayed-feedback setting, based on a tailor-made confidence interval for this setting. Although we focus on the deterministically delayed-feedback setting, an application of our analysis to this setting can be an important future direction. GP bandits with noiseless feedback. The regret analyses are also conducted on the noiseless setting [Bull, 2011, Flynn and Reeb, 2025, Iwazaki, 2025a, Iwazaki and Takeno, 2025, Kim and SanzAlonso, 2025, Lyu et al., 2019, Salgia et al., 2024, Vakili, 2022]. In particular, although Lyu et al. [2019] have studied the parallelization of GP bandit, their regret upper bounds have almost the same order as in the noisy case. Recently, near-optimal cumulative regret bounds for the sequential GP-UCB have been derived by Iwazaki [2025a]. We obtain much better regret bounds than [Lyu et al., 2019] by leveraging the proof of [Iwazaki, 2025a]. Regret lower bound. Several studies have provided algorithm-independent regret lower bounds for the GP bandit problem [Cai and Scarlett, 2021, Li and Scarlett, 2024, Ma et al., 2026, Scarlett et al., 2017]. For both noisy and noiseless settings, our regret analysis is not tight, since PE and US-based algorithms can achieve the near-optimal regret bound that matches the regret lower bound therein (see [Iwazaki, 2025a, Iwazaki and Takeno, 2025]). On the other hand, since PE and US-based algorithms are often practically ineffective, we tackle tightening the regret upper bounds of the GP-TS-based parallelization method, which is widely used [Chowdhury and Gopalan, 2019, Hernández-Lobato et al., 2017, Kandasamy et al., 2018, Nava et al., 2022, Vakili et al., 2021c].

Preliminaries

This section presents the problem statement, surrogate models, and assumptions.

2.1

Problem statement

We consider the d-dimensional maximization problem of f : X → R with an input domain X ⊂ Rd : x∗ ∈ arg max f (x), x∈X 1 In the proof of Lemma 6 in [Contal et al., 2013], the unjustified inequality σ̂ (x∗ ) ≤ σ̂ (xk ) seems to be used. t t t

where the evaluations of the most recent Q queries are not yet observed. Since evaluating the objective function f is assumed to be expensive, we sequentially choose xt for all iterations t and obtain a (possibly noisy) observation yt , by which we aim to optimize with a smaller number of observations. Hence, t−Q−1

the dataset that we have at the t-th iteration is Dt−Q−1 = {(xi , yi )}i=1

since we do not have the

observations at xt−Q , . . . , xt−1 . Thus, setting Q = 0 recovers the usual sequential optimization problem. This setting includes optimization problems with delayed or parallel feedback, a typical example of which is an asynchronous parallelization setup with Q + 1 workers. Note that although we consider this delayed setting for simplicity, our analysis can apply to other settings, such as the batch setting where Q + 1 queries are issued simultaneously. Regret. We evaluate the performance by the cumulative and simple regrets [Russo and Van Roy, 2014, Srinivas et al., 2010] defined below: RT =

T X

f (x∗ ) − f (xt ),

rT = f (x∗ ) − f (x̂T ),

t=1

where x̂T is some recommendation input by the algorithm at the end of the T -th iteration. As detailed in Section 4, we will analyze the expectation of the regret, where the expectation is taken with respect to all the randomness arising from the algorithm and the noise sequence (if it exists).

2.2

Gaussian process regression (GPR) model

We use a GPR model [Rasmussen and Williams, 2005] as the surrogate model, as with [Chowdhury and Gopalan, 2017, Janz et al., 2020, Srinivas et al., 2010]. Suppose that we have the training dataset Dt = {(xi , yi )}ti=1 , where yt = f (xt ) + ϵt with i.i.d. noise ϵt ∼ N (0, λ2 ). Under the assumption that f follows a GP denoted as GP(0, k), where k : X × X → R is a kernel function, the posterior distribution p(f | Dt ) is a GP again. That is, f | Dt ∼ GP(µt , kt ), whose posterior mean and covariance functions are given below: µt (x) = kt (x)⊤ K t + λ2 I t ′

′

kt (x, x ) = k(x, x ) − kt (x)

⊤

−1

yt ,

K t + λ2 I t

−1

kt (x′ ),

(1)

⊤ where kt (x) = k(x, x1 ), . . . , k(x, xt ) ∈ Rt , K t ∈ Rt×t is the kernel matrix whose (i, j)-element is k(xi , xj ), I t ∈ Rt×t is the identity matrix, and y t = (y1 , . . . , yt )⊤ ∈ Rt . For the sake of notational 2 simplicity, we define σt2 (x) = kt (x, x) and µ−i (x) = 0, σ−i (x) = k(x, x), and k−i (x, x′ ) = k(x, x′ ) for

all i = {0, . . . , Q} and x, x′ ∈ X . When λ = 0 and K t becomes not invertible though K t−1 is invertible, we do not add (xt , yt ) to the training dataset, that is, update Dt ← Dt−1 as in [Iwazaki, 2025a]. Maximum information gain (MIG). The complexity of GP bandits is commonly quantified by the MIG [Iwazaki, 2025b, 2026, Srinivas et al., 2010, Vakili et al., 2021b] defined below: Definition 2.1. Let f ∼ GP(0, k) over a compact input domain X ⊂ [0, r]d . Then, MIG γT is defined as follows: γT (λ2 ) =

1 sup ln det I T + λ−2 K T , 2 x1 ,...,xT ∈X

where K T ∈ RT ×T is the kernel matrix whose (i, j)-element is k(xi , xj ).

The MIG of several commonly used kernel functions is known to be sublinear regarding T . For d+1 example, γT (λ2 ) = O ln(T /λ2 ) for SE kernels kSE (x, x′ ) = exp −∥x − x′ ∥22 /(2ℓ2 ) , and γT (λ2 )= √ ν 2ν d d 1−ν 2ν∥x−x′ ∥2 e (T /λ2 ) 2ν+d for Matérn-ν kernels kMat (x, x′ ) = 2 O (T /λ2 ) 2ν+d ln 2ν+d (T /λ2 ) = O Γ(ν) ℓ √ 2ν∥x−x′ ∥2 Jν , where ℓ, ν > 0 are the lengthscale and smoothness parameter, respectively, and Γ(·) ℓ and Jν are Gamma and modified Bessel functions, respectively [Iwazaki, 2025b, 2026, Srinivas et al., 2010, e suppresses polylogarithmic factors. Vakili et al., 2021b]. Note that O Remark 2.2. We analyze regret via the widely used MIG bound from [Vakili et al., 2021b]. However, its flaw for Matérn kernels has been pointed out by Janz [2021] and Iwazaki [2025b]. Theorem 7 in Iwazaki 4ν+d d [2025b] provides the rectified MIG bound for the Matérn kernels γT = O (T /λ2 ) 2ν+d ln 2ν+d (T /λ2 ) , which requires the additional polylogarithmic factor on T . In addition, a slightly tighter MIG bound for the SE kernels is provided by Iwazaki [2026]. By adapting these analyses, our regret upper bounds may change slightly. Hereafter, when we focus on only the order except for λ2 , we denote γt (λ2 ) = γt for simplicity.

2.3

Regularity assumptions

Although we use the GPR model defined in Sec. 2.2, we assume a condition called the frequentist setting, which is different from the Bayesian assumption of the GPR model. We assume the following common regularity assumption on f [Chowdhury and Gopalan, 2017, Iwazaki and Takeno, 2025, Janz et al., 2020, Srinivas et al., 2010]: Assumption 2.3. Let f be an element of RKHS Hk specified by the predefined kernel k that satisfies ∀x ∈ X , k(x, x) ≤ 1, where X ⊂ [0, r]d is a compact input space. Furthermore, the RKHS norm of f is bounded as ∥f ∥Hk ≤ B < ∞ for some B > 0, where ∥ · ∥Hk denotes the RKHS norm of Hk . This assumption imposes desirable properties on f , such as smoothness and boundedness. We consider both the noisy case [Russo and Van Roy, 2014, Srinivas et al., 2010], where the observations are contaminated by noise, and the noiseless case [De Freitas et al., 2012, Iwazaki, 2025a], where we can obtain the function value as yt = f (xt ). For the noisy case, we assume the following condition on the noise sequence as in [Chowdhury and Gopalan, 2017, Janz et al., 2020]: Assumption 2.4. We can observe contaminated observations yt = f (xt ) + ϵt for all t ∈ N. The noise sequence (ϵt )t∈N is a sequence of conditionally R-sub-Gaussian random variables. That is, for some R > 0, 2 2 the moment generating function of ϵt satisfies E[exp(ηϵt ) | Ft−1 ] ≤ exp η 2R for all t ∈ N and η ∈ R, where Ft−1 is σ-algebra generated by the random variables {xi , yi }t−1 i=1 and xt . Furthermore, we assume the following conditions on smoothness and discretization as in [Chowdhury and Gopalan, 2017, 2019, Vakili et al., 2021a,c, 2022]: Assumption 2.5. The kernel function k satisfies the following condition on the derivatives. There 1/2

exists a constant Lk such that, supx∈X supj∈[d] ∂∂uk(u,v) j ∂vj

≤ Lk . Furthermore, there exists a u=v=x

(computable) finite subset Xt ⊂ X that satisfies maxx∈X minx′ ∈Xt ∥x−x′ ∥1 ≤ Lk1Nt and |Xt | ≤ (Lk drNt )d for all t ∈ [T ] and Nt ∈ N. This assumption is satisfied at least by the SE kernels and the Matérn kernels with ν > 1. The algorithm of GP-BTS depends on a predefined discretized input set Xt ⊂ X , as with [Chowdhury and Gopalan, 2017, 2019, Vakili et al., 2021c]. (For details, see Section 4.2 in [Chowdhury and Gopalan, 2017].) 5

Algorithm 1 GP-BTS Require: Domain X , kernel k, confidence width parameters {βt }t∈N , discretized inputs {Xt }t∈N 1: D0 ← ∅ 2: for t = 1, . . . , T do 3:

2 If t > Q + 1, update µt−Q−1 (·) and σt−Q−1 (·) by Eq. (1)

Compute xt = arg maxx∈Xt gt (x) where gt ∼ GP(µt−Q−1 , βt kt−Q−1 )

If t ≥ Q + 1, observe yt−Q = f (xt−Q ) + ϵt−Q

6: end for 7: return some recommendation x̂T

GP-BTS

This section describes the algorithm and the existing analyses of GP-BTS.

3.1

Algorithm

We define GP-BTS following [Chowdhury and Gopalan, 2019, Vakili et al., 2021c], whose pseudocode is shown in Algorithm 1. In our problem setup, since the recent Q observations are not yet available, we need to query xt that is diverse relative to the recent Q inputs. From the nature of GP-TS, which depends on the random posterior sampling, we can determine xt that is randomly distributed, by which we expect that the inputs have diversity. Thus, GP-BTS chooses the t-th input using the currently available dataset Dt−Q−1 as follows: xt = arg max gt (x), x∈Xt

where gt ∼ GP(µt−Q−1 , βt kt−Q−1 ) is the posterior sample path with the inflated posterior variance by the confidence width parameter βt to apply the proof technique by Chowdhury and Gopalan [2017]. Furthermore, we will theoretically specify βt as βt = Θ(γt ), as in [Vakili et al., 2021c], though GP-BTS in [Chowdhury and Gopalan, 2019] and GP-BUCB [Chowdhury and Gopalan, 2019, Desautels et al., 2014] set βt = Θ exp(γQ )γt .

3.2

Existing regret analysis

Although Vakili et al. [2021c] focused on the GP-BTS with sparse GP approximation, their analysis can apply to our problem setup, where we can compute an exact GP posterior and an exact posterior sample path. By adapting the analysis by Vakili et al. [2021c], GP-BTS attains the following cumulative regret bound (a detailed and modified version of this claim is shown in Lemma 4.1): " T # X p E [RT ] ≲ βT ln T E σt−Q−1 (xt ) ,

(2)

t=1

where ≲ ignores the constant factors except for T and Q, and the expectation is taken with respect to the randomness of the algorithm and the noise sequence. Since σt−Q−1 (xt ) ≥ σt−1 (xt ) holds, the above regret upper bound is larger than the regret bound for the sequential case, which depends on the quantity PT PT t=1 σt−1 (xt ). To obtain the upper bound for t=1 σt−Q−1 (xt ), Vakili et al. [2021c] apply the following lemma:2 2 Note that, due to the difference in the notation, BT in [Vakili et al., 2021c] is equivalent to T in this paper.

Lemma 3.1 (Adapted from Lemma 3 in [Vakili et al., 2021c]). For any input sequence x1 , . . . , xT ∈ X , the following inequality holds: T X

σt−Q−1 (xt ) ≤

C1 QT γT /Q ,

t=1

where C1 = 2/ ln(1 + λ−2 ). Finally, Vakili et al. [2021c] have derived the following cumulative regret upper bound of GP-BTS: q E [RT ] = O QγT /Q γT T ln T . (3) √ Compared with the O γT T ln T bound of the sequential GP-TS [Chowdhury and Gopalan, 2017], p √ γT is replaced with QγT /Q . Since we focus on the case where γT is sublinear, this replacement is a degradation with respect to Q. In the next section, we show that this degradation can be avoided without the impractical initial US phase.

Improved regret analysis

First, we derive Lemma 4.1, which shows the instantaneous regret upper bound of GP-BTS, modified slightly from [Vakili et al., 2021c] to apply Lemmas 4.2 and 4.4. Then, we show the regret upper bounds for GP-BTS in noisy and noiseless settings. We can obtain the following instantaneous regret bound for GP-BTS: Lemma 4.1 (Modified from Theorem 1 in [Vakili et al., 2021c]). Supposeq Assumptions 2.3 and 2.5 hold. (g) (f ) 1/2 R Set pt ∈ (0, 1), Nt ∈ N and (i) λ > 0, pt ∈ (0, 1) and βt (δ) = B + λ 2 γt + ln(1/δ) for the noisy (f )

setting where Assumption 2.4 holds or (ii) λ = pt

1/2

= 0 and βt

(δ) = B for the noiseless setting where

yt = f (xt ). Then, if Algorithm 1 runs, for all t ∈ [T ], the following inequality holds: 2+p B (f ) (g) E [min {2B, ct σt−Q−1 (xt )}] + + 2Bpt + 2Bpt p Nt √ 1/2 (f ) 1/2 (g) where p = 1/(4e π), ζt (δ) = 2 ln 2(Lk drNt )d / pδ , ct = βt pt 2ζt pt + 1 , and the expectaE[f (x∗ ) − f (xt )] ≤

tion is taken with respect to {ϵt }t∈[T ] and {gt }t∈[T ] for the noisy setting and {gt }t∈[T ] for the noiseless setting. See Appendix B.1 for the proof. Comparison from [Vakili et al., 2021c]. Our modification in Lemma 4.1 compared with [Vakili et al., 2021c] is useful to bound the regrets over some index set T . The difference is a replacement of min {2B, ct E [σt−Q−1 (xt )]} with E [min {2B, ct σt−Q−1 (xt )}]. If we use the upper bound min {2B, ct E [σt−Q−1 (xt )]} √ naively, the regret upper bound incurs the term cT |T | = O( γT ln T |T |), where T is the set of iterations P defined in Lemma 4.2. We can utilize Lemma 4.1 to obtain t∈T f (x∗ ) − f (xt ) = O(B|T |).

4.1

Regret analysis for noisy feedback

The degradation from the sequential setting arises mainly from Lemma 3.1. To avoid this, we obtain the following lemma similar to the elliptical potential count lemma (Lemma D.9 in [Flynn and Reeb, 2025], Lemma 3.3 in [Iwazaki and Takeno, 2025], Lemma 6 in [Iwazaki, 2025a]):

Lemma 4.2. For any T ∈ N, λ > 0, and any input sequence {xt }t∈[T ] , the following hold: |T | ≤ 8Qγ|T | (λ2 ) ≤ 8QγT (λ2 ), and ∀t ∈ T c , σt−Q−1 (xt ) ≤

√

2σt−1 (xt ),

2 where T = {t ∈ [T ] | σt−1 (xt ) ≥ λ2 /(2Q)} and T c is its complement set.

This lemma can be derived by combining a proof similar to the elliptical potential count lemma with the well-known posterior variance inequality shown in Lemma A.4. See Appendix B.2 for the detailed proof. This lemma implies that, in most iterations T c , where |T c | = T − |T | ≥ T − 8Qγ|T | (λ2 ), the increase from σt−1 (xt ) to σt−Q−1 (xt ) is at most a constant multiple. Thus, we can see that, for t ∈ T c , we can obtain a tighter upper bound compared with Lemma 3.1. By combining Lemmas 4.1 and 4.2, we can obtain the following regret upper bounds: (f )

(g)

Theorem 4.3. Suppose Assumptions 2.3, 2.4, and 2.5 hold. Set 1/Nt = pt = pt = 1/t2 , x̂T = (1/2) (g) arg maxx∈X µT (x) − βT (pT )σT (x) , and other variables as in Lemma 4.1. Then, the following inequality holds:

E[RT ] = O T

(Q)

√

+ γT T ln T ,

E[rT ] = O

(Q)

= max{t ∈ N | t ≤ 8Qγt }. In particular, T 2ν+d (Q) e 2ν for Matérn kernels. T =O Q

where T

(Q)

! √ + γT T ln T , T

= O Q lnd+1 Q for SE kernels and

P (Q) ∗ In the proof, roughly speaking, we show that E f (x ) − f (x ) = O(BE[|T |]) = O BT t t∈T √ P ∗ and E t∈T c f (x ) − f (xt ) = O γT T ln T . See Appendix B.3 for the detailed proof. Consequently, we obtain the following cumulative regret bound:  p  O Q lnd+1 Q + T (ln T )2d+3 for SE kernels, E [RT ] = 2ν+3d 2ν+d  e Q 2ν + T 4ν+2d O for Matérn kernels. Therefore, except for the additive factor on Q, our analysis achieves regret upper bounds similar to those for the sequential GP-TS [Chowdhury and Gopalan, 2017]. Compared with Eq. (3), our analysis replaces the multiplicative factor on Q with the additive factor on Q. This change is considered preferable in the √ literature [see Section 4 of Desautels et al., 2014] since the γT T ln T term is often dominant under the general assumption T ≫ Q.

4.2

Regret analysis for noiseless feedback

We obtain the following lemma combining the proof by Iwazaki [2025a] and Lemma 3.1: Lemma 4.4 (Informal). Based on the MIG bounds from [Vakili et al., 2021b], the following statements hold for any T ∈ N and any input sequence x1 , . . . , xT ∈ X : • For the SE kernels, 1 1e d+1 min σt−Q−1 (xt ) ≤ 2T /Q exp − CSE (T /Q) if T ≥ QT SE , 2 t∈[T ] !− 3d+3 2 T X eSE √ 3d + 3 C min {2B, ct σt−Q−1 (xt )} ≤ 2BQT SE + 2cT (d + 1) Γ . 2 2 t=1 p

• For the Matérn kernels with ν > 1/2, √

1/2

e (T /Q)− d (ln(T /Q)) d 2C if T ≥ QT Mat , Mat t∈[T ]  √ ν ν  e 1/2 d T d−ν d Q d (ln(T /Q)) d 2BQT Mat + 2cT C  Mat d−ν  T  X √ e 1/2 Q(ln(T /Q))2 /2 min {2B, ct σt−Q−1 (xt )} ≤ 2BQT Mat + 2cT C Mat   √ ν t=1  e 1/2 QΓ( d +1) 2BQT Mat + 2cT C ν +1  Mat ν ( d −1) d min σt−Q−1 (xt ) ≤

if d > ν, if d = ν, if d < ν.

eSE , C eMat , T SE , and T Mat are constants with respect to T and Q. where C See Appendix B.4 for the formal version and its proof. Hence, by combining Lemmas 4.1 and 4.4, we derive the following result: (g)

Theorem 4.5. Suppose Assumptions 2.3 and 2.5 hold. Set 1/Nt = pt Lemma 4.1. Then, the following inequality holds:  1  O Q + ln 2 T    ν d−ν   e Q + T d Qd O E [RT ] = 5   2 T  O Q ln     O Q ln 12 T

= 1/t2 and other variables as in

for SE kernels, for Matérn kernels with d > ν, for Matérn kernels with d = ν, for Matérn kernels with d < ν,

e suppresses the polylogarithmic factors for T and Q. where O As with the sequential case [Iwazaki, 2025a], we can obtain a much better regret upper bound compared with the noisy case. In particular, for SE kernels and Matérn kernels with ν ≥ d, we can obtain a polylogarithmic upper bound with respect to T . Our regret bounds are much tighter than the known results in [Lyu et al., 2019]. 1

Note that the ln 2 T factor comes from cT and does not stem from the parallelization. This greater dependence on T is a problem of the GP-TS-based method compared with GP-UCB-based methods, as discussed in [Chowdhury and Gopalan, 2017]. Furthermore, modifying the proof of Lemma 4.4, we obtain the following simple regret bounds: (g)

Corollary 4.6. Suppose Assumptions 2.3 and 2.5 hold. Set 1/Nt = pt

= 1/t2 and other variables as in

Lemma 4.1. In addition, define x̂t = arg maxt∈[T ] f (xt ). Then, the following inequality holds:  1   O QT −1 + T −1 ln 2 T for SE kernels,     ν ν  e QT −1 + T − d Q d O for Matérn kernels with d > ν, E [rT ] = 5  −1  for Matérn kernels with d = ν, O QT ln 2 T    1   O QT −1 ln 2 T for Matérn kernels with d < ν, e suppresses the polylogarithmic factors for T and Q. where O See Appendix B.4 for the proof. Remark 4.7 (Simple regret upper bound). Although we obtained polynomial convergence of the simple regret for both kernels, the dependence on T in these upper bounds is worse than in [Iwazaki, 2025a]. This degradation arises from the property of GP-TS, where we cannot obtain the upper bound like 1/2

f (x∗ ) − f (xt ) ≤ 2βt

σt−1 (xt ), which can be obtained by GP-UCB. Furthermore, even if we can obtain 9

300

125

250

Cumulative Regret

150

100 75

Q=0 Q=2 Q=4 Q=8 Q=16 Q=32

50 25 0

200

400 600 Iteration

800

Q=0 Q=2 Q=4 Q=8 Q=16 Q=32

100

1000

400 300 Q=0 Q=2 Q=4 Q=8 Q=16 Q=32

200 100 0

200

400 600 Iteration

800

1000

200

400 600 Iteration

800

1000

400 600 Iteration

800

1000

Q=0 Q=2 Q=4 Q=8 Q=16 Q=32

800 Cumulative Regret

Cumulative Regret

150

500

200

600 400 200 0

200

Figure 1: Synthetic function experiment results. The vertical axis shows the mean and standard error of cumulative regrets. The horizontal axis shows iterations. The left and right columns show the results in noiseless and noisy settings, respectively. The top and bottom rows show the results for the SE and Matérn kernels, respectively. In each plot, we show the result of GP-BTS with Q ∈ {0, 2, 4, 8, 16, 32} shown in Algorithm 1. the simple regret bound with the order of mint∈[T ] σt−Q−1 (xt ) in Lemma 4.4, the upper bounds result in the same rate as when T /Q times function evaluations can be performed sequentially. Thus, obtaining tighter simple regret bounds for GP-TS-based methods and determining whether we can further tighten the simple regret bound for parallel GP bandit methods are important directions for future work.

Numerical experiments

We conducted numerical experiments for synthetic functions that satisfy the theoretical settings using scikit-learn [Pedregosa et al., 2011]. We set X = {0, 0.1, . . . , 0.9}d with d = 3. As in [Chowdhury and Gopalan, 2017], we generate sample paths from a GP, and set the posterior mean learned from data at X as the objective function and B 2 = f K −1 f , where f = f (x) x∈X and K = k(xi , xj ) xi ,xj ∈X . We use the SE kernel with ℓ = 0.4 and the Matérn kernel with ℓ = 0.4 and ν = 5/2. In addition, we set δ = 0.1 and βt to its theoretical value based on the actual mutual information. We conducted the experiments for the noiseless setting and noisy setting with Gaussian noise εi ∼ N (0, λ2 ), where λ = 0.1, for all i ∈ [T ]. Figure 1 shows the mean and standard error of cumulative regrets for 16 random trials for GP sample paths generation and the randomness of the algorithm. Throughout the experiments, the dependence on Q seems to be mild, particularly for Q ≤ 4. These results align with our theoretical results, which imply

that the dependence on Q is not dominant when T is sufficiently large. Furthermore, in the noiseless setting, we can see that the cumulative regret for the SE kernel saturates around 100 iterations, which 1

matches our Theorem 4.5 that shows O(Q + ln 2 T ) cumulative regret upper bound. For the Matérn kernel, in the noiseless since d = 3 > ν = 5/2, the cumulative regret upper bound implied by 1 setting, 5 e 6 6 Theorem 4.5 is O T Q . Indeed, the cumulative regret exhibits sublinear growth, but its dependence on Q is more moderate than the theoretical upper bound would suggest.

Conclusion and future work

In this paper, we presented an improved regret analysis for GP-BTS in the simple delayed-feedback setting. By developing Lemma 4.2, we decoupled the delay parameter Q from the main regret term, converting the previously known multiplicative degradation into an additive one. Consequently, our analysis theoretically guarantees that GP-BTS achieves cumulative regret bounds comparable to those of the sequential case without relying on the practically inefficient initial US phase [Desautels et al., 2014]. Furthermore, we established regret upper bounds for the noiseless setting following [Iwazaki, 2025a]. Discussion and future work. While our results tighten the regret bounds for GP-BTS, several important avenues remain for future work: • Simple regret bound in noiseless setting. As discussed in Remark 4.7, determining the possibility of improving our simple regret bounds in the noiseless setting is crucial. • Adaptation to GP-BUCB. Our current proof technique cannot directly tighten the regret bounds of GP-BUCB, since it uses the confidence parameter βT = O(QγT ), which is already inflated by Q [Desautels et al., 2014]. Furthermore, unlike GP-BTS, GP-BUCB may not select diverse points in a batch if we use βt = Θ(γt ), which is not scaled by Q, although we conjecture that such an algorithm can achieve the same regret upper bound as ours. Thus, to develop a meaningful UCB-based batched method achieving the same regret upper bound as ours, we need to design a new UCB-based method that can select diverse points in a batch without scaling βt by Q. • High-probability bounds. Since we present expected regret bounds, Markov’s inequality readily indicates high-probability bounds with 1/δ dependence. For the noisy case, obtaining a ln(1/δ) dependence is relatively straightforward using the Azuma-Hoeffding inequality as with [Chowdhury and Gopalan, 2017]. However, deriving a ln(1/δ) dependence in the noiseless setting remains an √ open problem. This is because the standard concentration inequalities incur an O( T ) dependence, which is dominant in the noiseless case. • Bayesian setting adaptation. Tightening the regret bounds in the Bayesian setting [Kandasamy et al., 2018, Nava et al., 2022, Sugiura et al., 2026] is a promising direction. • Discretization error for GP-TS. Our analysis for GP-BTS incurs discretization error as with GP-TS [Chowdhury and Gopalan, 2017], which results in ln T degradation in the noisy setting and can be non-negligible in the noiseless setting. Carefully addressing the need for discretization to avoid this degradation is an important future direction. • Optimality with respect to Q. Although we have reduced the dependence on Q, the optimal dependence remains unknown. The additive Θ(Q) term is unavoidable, since the first Q evaluations can incur Θ(Q) regret in the worst case. On the other hand, it may be possible to eliminate the 11

additional factors, such as O(lnd+1 Q) and O(Qd/(2ν) ) for the SE and Matérn kernels, respectively, in the noisy setting, and the multiplicative Qν/d factor for the Matérn kernel with d > ν in the noiseless setting. We leave a characterization of the optimal dependence on Q for future work.

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

References Yasin Abbasi-Yadkori. Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, 2013. Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011. Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust Gaussian process bandit optimization. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 1216–1226. PMLR, 2021. Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Proceedings of the 32nd Conference on Learning Theory, volume 99, pages 533–557. PMLR, 2019. Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 844–853. PMLR, 2017. Sayak Ray Chowdhury and Aditya Gopalan. On batch Bayesian optimization. arXiv:1911.01032, 2019. Emile Contal, David Buffoni, Alexandre Robicquet, and Nicolas Vayatis. Parallel Gaussian process optimization with upper confidence bound and pure exploration. In Proceedings of the 2013th European Conference on Machine Learning and Knowledge Discovery in Databases, pages 225–240. Springer-Verlag, 2013. Nando De Freitas, Alex J. Smola, and Masrour Zoghi. Exponential regret bounds for Gaussian process bandits with deterministic observations. In Proceedings of the 29th International Conference on Machine Learning, page 955–962. Omnipress, 2012. Thomas Desautels, Andreas Krause, and Joel W. Burdick. Parallelizing exploration-exploitation tradeoffs in Gaussian process bandit optimization. Journal of Machine Learning Research, 15:4053–4103, 2014. Hamish Flynn and David Reeb. Tighter confidence bounds for sequential kernel regression. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258, pages 3844–3852. PMLR, 2025. José Miguel Hernández-Lobato, James Requeima, Edward O. Pyzer-Knapp, and Alán 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, volume 70, pages 1470–1479. PMLR, 2017. 12

Shogo Iwazaki. Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 38, pages 65863–65886. Curran Associates, Inc., 2025a. Shogo Iwazaki. Improved regret bounds for Gaussian process upper confidence bound in Bayesian optimization. In Advances in Neural Information Processing Systems, volume 38, pages 96922–96964. Curran Associates, Inc., 2025b. Shogo Iwazaki. Tighter regret lower bound for Gaussian process bandits with squared exponential kernel in hypersphere. In Proceedings of the 43rd International Conference on Machine Learning. PMLR, 2026. To appear. Shogo Iwazaki and Shion 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, volume 267, pages 26642–26672. PMLR, 2025. David Janz. Sequential decision making with feature-linear models. PhD thesis, University of Cambridge, 2021. David Janz, David Burt, and Javier Gonzalez. Bandit optimisation of functions in the Matérn kernel RKHS. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, volume 108, pages 2486–2495. PMLR, 2020. Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaussian processes and kernel methods: A review on connections and equivalences. arXiv:1807.02582, 2018. Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K. Sriperumbudur. Gaussian processes and reproducing kernels: Connections and equivalences. arXiv:2506.17366, 2025. Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabas Póczos. Parallelised Bayesian optimisation via Thompson sampling. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, volume 84, pages 133–142. PMLR, 2018. Hwanwoo Kim and Daniel Sanz-Alonso. Enhancing Gaussian process surrogates for optimization and posterior approximation via random exploration. SIAM/ASA Journal on Uncertainty Quantification, 13(3):1054–1084, 2025. Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151, pages 92–107. PMLR, 2022. Zihan Li and Jonathan Scarlett. Regret bounds for noise-free cascaded kernelized bandits. Transactions on Machine Learning Research, 2024. URL https://openreview.net/forum?id=oCfamUtecN. Yueming Lyu, Yuan Yuan, and Ivor W Tsang. Efficient batch black-box optimization with deterministic regret bounds. arXiv:1905.10041, 2019. Chenkai Ma, Keqin Chen, and Jonathan Scarlett. Batched kernelized bandits: Refinements and extensions. arXiv:2603.12627, 2026. Mojmir Mutny and Andreas Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. Advances in Neural Information Processing Systems 31, pages 9005–9016, 2018. 13

Elvis Nava, Mojmir Mutny, and Andreas Krause. Diversified sampling for batched Bayesian optimization with determinantal point processes. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151, pages 7031–7054, 2022. Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Andreas Müller, Joel Nothman, Gilles Louppe, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005. Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221–1243, 2014. Sudeep Salgia, Sattar Vakili, and Qing Zhao. Random exploration in Bayesian optimization: Orderoptimal regret and computational efficiency. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 43112–43141. PMLR, 2024. Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proceedings of the 30th Conference on Learning Theory, volume 65, pages 1723–1742. PMLR, 2017. Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, pages 1015–1022. Omnipress, 2010. Shuhei Sugiura, Ichiro Takeuchi, and Shion Takeno. Randomized kriging believer for parallel Bayesian optimization with regret bounds. arXiv:2603.01470, 2026. Shion Takeno, Yu Inatsu, Masayuki Karasuyama, and Ichiro Takeuchi. Posterior sampling-based Bayesian optimization with tighter Bayesian regret bounds. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 47510–47534. PMLR, 2024. Sattar Vakili. Open problem: Regret bounds for noise-free kernel-based bandits. In Proceedings of the 35th Conference on Learning Theory, volume 178, pages 5624–5629. PMLR, 2022. Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. Optimal order simple regret for Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 34, pages 21202–21215. Curran Associates, Inc., 2021a. Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 82–90. PMLR, 2021b. Sattar Vakili, Henry Moss, Artem Artemev, Vincent Dutordoir, and Victor Picheny. Scalable Thompson sampling using sparse Gaussian process models. In Advances in Neural Information Processing Systems, volume 34, pages 5631–5643. Curran Associates, Inc., 2021c.

Sattar Vakili, Jonathan Scarlett, Da-Shan Shiu, and Alberto Bernacchia. Improved convergence rates for sparse approximation methods in kernel-based learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 21960–21983. PMLR, 2022. Sattar Vakili, Danyal Ahmed, Alberto Bernacchia, and Ciara Pike-Burke. Delayed feedback in kernel bandits. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 34779–34792. PMLR, 2023. Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, UAI’13, page 654–663. AUAI Press, 2013. Arun Verma, Zhongxiang Dai, and Bryan Kian Hsiang Low. Bayesian optimization under stochastic delayed feedback. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 22145–22167. PMLR, 2022.

Auxiliary lemmas

This section lists the auxiliary lemmas for the proof. We use the following lemma to obtain the upper bound of the discretization error. Lemma A.1 (Lemma 5.1 in [De Freitas et al., 2012]). Suppose that Assumption 2.5 holds. Then, any g ∈ Hk is Lipschitz continuous with respect to ∥g∥Hk Lk . The following lemmas provide the confidence intervals for both noisy and noiseless settings: Lemma A.2 (Proposition 1 in [Vakili et al., 2021a], Corollary 3.11 in [Kanagawa et al., 2018], Corollary 5.6 in [Kanagawa et al., 2025], or Lemma 6 in [De Freitas et al., 2012]). Suppose that Assumption 2.3 holds and f (xt ) can be obtained for all t ∈ N. Then, by setting λ2 ≥ 0, the following holds: ∀t ∈ N, ∀x ∈ X , |f (x) − µt−1 (xt )| ≤ Bσt−1 (xt ),

(4)

for any input sequence (xt )t∈N . Lemma A.3 (Adapted from Theorem 3.11 in [Abbasi-Yadkori, 2013]). Suppose that Assumptions 2.3 and 2.4 hold. Fix δ ∈ (0, 1). Then, by setting λ2 > 0, the following holds: 1/2 Pr ∀t ∈ N, ∀x ∈ X , |f (x) − µt−1 (xt )| ≤ βt σt−1 (xt ) ≥ 1 − δ, p 1/2 where βt = B + R 2γt + 2 ln(1/δ). λ

(5)

We use the following useful lemmas for both noisy and noiseless settings: Lemma A.4 (Lemma 13 in [Mutny and Krause, 2018], Lemma 4.2 in [Takeno et al., 2024]). For all t ≥ Q + 1, the following inequality holds: s λ2 σt−Q−1 (x) ≤ σt−1 (x) ≤ σt−Q−1 (x). 2 Qσt−Q−1 (x) + λ2

(6)

Proof. First, σt−1 (x) ≤ σt−Q−1 (x) is trivial since the posterior variance decreases monotonically with respect to the addition of training data. Second, σt−1 (x) becomes the smallest value when xt−Q , . . . , xt−1 are the same input x. In such case, we can compute σt−1 (x) analytically: s λ2 σt−1 (x) = σt−Q−1 (x), 2 Qσt−Q−1 (x) + λ2 which concludes the proof. 15

(7)

Proof

B.1

Proof for Lemma 4.1

First, we show the following lemma, modified from Lemma 10 in [Chowdhury and Gopalan, 2017]: (f )

Lemma B.1. Assume the same premise as in Theorem 4.3. Furthermore, define the event Et

follows: (f )

1/2

= {∀x ∈ Xt , |f (x) − µt−Q−1 (x)| ≤ βt

(f )

(8)

σt−Q−1 (x)}

(f )

where Xt ⊂ X is a finite subset of an input domain. Then, for all t ∈ [T ] and Dt−Q−1 such that Et

true, the following inequality holds: 2+p (g) E [min {2B, ct σt−Q−1 (xt )} | Dt−Q−1 ] + 2Bpt , p √ 1/2 (g) 1/2 (f ) 2ζt pt + 1 . where [x]t = arg minx′ ∈Xt ∥x − x′ ∥1 , p = 1/(4e π), and ct = βt pt E [f ([x∗ ]t ) − f (xt ) | Dt−Q−1 ] ≤

(f )

Proof. First, we show that, for any Dt−Q−1 such that Et

(9)

is true,

Pr (xt ∈ Xt \St | Dt−Q−1 ) ≥

2 , p

(10)

where St is called saturation set [Chowdhury and Gopalan, 2017] and is defined as follows: 1/2 (f ) 1/2 (g) St = x ∈ Xt f ([x∗ ]t ) − f (x) > βt pt ζt pt + 1 σt−Q−1 (x) .

(11)

(f )

To show the above inequality, we use the following facts. For any Dt−Q−1 such that Et

is true and

σt−Q−1 ([x ]t ) = 0, the probability Pr (gt ([x ]t ) = f ([x ]t ) = µt−Q−1 ([x ]t ) | Dt−Q−1 ) = 1. Furthermore, ∗

∗

(f )

the following inequality holds for any Dt−Q−1 such that Et

is true and σt−Q−1 ([x∗ ]t ) > 0: (12)

Pr (gt ([x∗ ]t ) ≥ f ([x∗ ]t ) | Dt−Q−1 ) 1/2 (f ) ≥ Pr gt ([x∗ ]t ) ≥ µt−Q−1 ([x∗ ]t ) + βt pt σt−Q−1 ([x∗ ]t ) | Dt−Q−1 ! gt ([x∗ ]t ) − µt−Q−1 ([x∗ ]t ) = Pr ≥ 1 Dt−Q−1 1/2 (f ) βt pt σt−Q−1 ([x∗ ]t )

(13) (14) (15)

≥ p, (f )

where the first inequality holds since Et

is true and the second inequality holds due to

gt ([x∗ ]t )−µt−Q−1 ([x∗ ]t ) 1/2

(f )

βt

σt−Q−1 ([x∗ ]t )

Dt−Q−1 ∼ N (0, 1) and Gaussian anti-concentration inequality (e.g., Lemma 7 in [Chowdhury and Gopalan, 2017] and and Lemma 5.1 in [Srinivas et al., 2010]). Hence, Pr (gt ([x∗ ]t ) ≥ f ([x∗ ]t ) | Dt−Q−1 ) ≥ p for (f )

any Dt−Q−1 such that Et (g)

(g)

is true. Furthermore, define the event Et 1/2

= {∀x ∈ Xt , |gt (x) − µt−Q−1 (x)| ≤ βt

(f ) 1/2 ζt

as follows: (g)

(16)

σt−Q−1 (x)}.

From Gaussian concentration inequality (e.g., Lemma 5 in [Chowdhury and Gopalan, 2017] and and Lemma 5.1 in [Srinivas et al., 2010]) and the definition of ζt (δ) = 2 ln 2(Lk drNt )d / pδ , we have (g)

Pr(Et

(g)

| Dt−Q−1 ) ≥ 1 − p2 pt

(f )

for any Dt−Q−1 . Therefore, for any Dt−Q−1 such that Et

is true,

Pr (∃x ∈ St , f ([x∗ ]t ) < gt (x) | Dt−Q−1 ) 1/2 (f ) 1/2 (g) ζt pt + 1 σt−Q−1 (x) < gt (x) | Dt−Q−1 ≤ Pr ∃x ∈ St , f (x) + βt pt p (g) ≤ pt , 2 16

(17) (18) (19)

(g)

which holds due to the definition of St and the probability bound for Et . Obviously, Xt \St is not empty since [x∗ ]t belongs to Xt \St . If gt ([x∗ ]t ) ≥ gt (x) for all x ∈ St , then (f )

xt ∈ Xt \St . Thus, for any Dt−Q−1 such that Et

is true, we can obtain the lower bound as follows: (20)

Pr (xt ∈ Xt \St | Dt−Q−1 ) ≥ Pr (∀x ∈ St , gt ([x ]t ) ≥ gt (x) | Dt−Q−1 )

(21)

≥ Pr (∀x ∈ St , gt ([x∗ ]t ) ≥ f ([x∗ ]t ) ≥ gt (x) | Dt−Q−1 )

(22)

≥ Pr (gt ([x∗ ]t ) ≥ f ([x∗ ]t ) | Dt−Q−1 ) − Pr (∃x ∈ St , f ([x∗ ]t ) < gt (x) | Dt−Q−1 ) p (g) p ≥ p − pt ≥ . 2 2

(23)

∗

(24)

Define x̄t = arg minx∈Xt \St σt−Q−1 (x). Then, since x̄t is deterministic given Dt−Q−1 , we can see that, (f )

for any Dt−Q−1 such that Et

is true,

E [min {2B, ct σt−Q−1 (xt )} | Dt−Q−1 ]

(25)

≥ E [min {2B, ct σt−Q−1 (xt )} | Dt−Q−1 , xt ∈ Xt \St ] Pr (xt ∈ Xt \St | Dt−Q−1 )

(26)

p min {2B, ct σt−Q−1 (x̄t )} , 2 1/2 (f ) 1/2 (g) where ct = βt pt 2ζt pt + 1 .

(27)

≥

(f )

If Et

(g)

and Et

are true, then

f ([x∗ ]t ) − f (xt ) = f ([x∗ ]t ) − f (x̄t ) + f (x̄t ) − gt (x̄t ) + gt (x̄t ) − gt (xt ) + gt (xt ) − f (xt ) 1/2 (f ) 1/2 (g) ≤ βt pt ζt pt σt−Q−1 (x̄t ) + f (x̄t ) − gt (x̄t ) + gt (xt ) − f (xt ) 1/2 (f ) 1/2 (g) ≤ ct σt−Q−1 (x̄t ) + βt pt ζt pt + 1 σt−Q−1 (xt )

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

≤ ct (σt−Q−1 (x̄t ) + σt−Q−1 (xt )) ,

where the first inequality follows from x̄t ∈ Xt \St and gt (x̄t ) − gt (xt ) ≤ 0, and the second inequality (f )

holds since Et

(g)

and Et

are true. Furthermore, since f ([x∗ ]t ) − f (xt ) ≤ 2B from Assumption 2.3, we

can see that (32)

f ([x∗ ]t ) − f (xt ) ≤ min{2B, ct (σt−Q−1 (x̄t ) + σt−Q−1 (xt ))} ≤ min {2B, ct σt−Q−1 (x̄t )} + min {2B, ct σt−Q−1 (xt )} , (f )

if Et

(g)

and Et

(33)

are true. This is because, the last upper bound min {2B, ct σt−Q−1 (x̄t )}+min {2B, ct σt−Q−1 (xt )}

is 4B, 2B + ct σt−Q−1 (x̄t ), 2B + ct σt−Q−1 (xt ), or ct (σt−Q−1 (x̄t ) + σt−Q−1 (xt )).

Hence, if 2B ≤

ct (σt−Q−1 (x̄t ) + σt−Q−1 (xt )), then 2B is less than the above four quantities, and vice versa. Thus, (f )

for any Dt−Q−1 such that Et

is true, we can obtain the following bound:

E [f ([x∗ ]t ) − f (xt ) | Dt−Q−1 ] h i (g) (g) ≤ E min {2B, ct σt−Q−1 (x̄t )} | Et , Dt−Q−1 Pr(Et | Dt−Q−1 ) h i (g) (g) + E min {2B, ct σt−Q−1 (xt )} | Et , Dt−Q−1 Pr(Et | Dt−Q−1 ) h i (g) (g) + E f ([x∗ ]t ) − f (xt ) | Et , Dt−Q−1 Pr(Et | Dt−Q−1 ) ≤ E [min {2B, ct σt−Q−1 (x̄t )} | Dt−Q−1 ]

≤

(34) (35) (36) (37) (38)

(g) + E [min {2B, ct σt−Q−1 (xt )} | Dt−Q−1 ] + 2Bpt

(39)

2+p (g) E [min {2B, ct σt−Q−1 (xt )} | Dt−Q−1 ] + 2Bpt , p

(40)

(g)

where Et

(g)

is a complementary event of Et

and we use Eqs. (27) and (33), maxx∈X |f (x)| ≤ B from

Assumption 2.3. Lemma 4.1 (Modified from Theorem 1 in [Vakili et al., 2021c]). Supposeq Assumptions 2.3 and 2.5 hold. (g) (f ) 1/2 R Set pt ∈ (0, 1), Nt ∈ N and (i) λ > 0, pt ∈ (0, 1) and βt (δ) = B + λ 2 γt + ln(1/δ) for the noisy (f )

setting where Assumption 2.4 holds or (ii) λ = pt

1/2

= 0 and βt

(δ) = B for the noiseless setting where

yt = f (xt ). Then, if Algorithm 1 runs, for all t ∈ [T ], the following inequality holds: B 2+p (f ) (g) E [min {2B, ct σt−Q−1 (xt )}] + + 2Bpt + 2Bpt p Nt √ 1/2 (f ) 1/2 (g) where p = 1/(4e π), ζt (δ) = 2 ln 2(Lk drNt )d / pδ , ct = βt pt 2ζt pt + 1 , and the expectaE[f (x∗ ) − f (xt )] ≤

tion is taken with respect to {ϵt }t∈[T ] and {gt }t∈[T ] for the noisy setting and {gt }t∈[T ] for the noiseless setting. Proof. First, from Assumption 2.5, Lemma A.1 and ∥f ∥Hk ≤ B (Assumption 2.3), we can see that max |f (x) − f ([x]t )| ≤ BLk max ∥x − [x]t ∥1 ≤ x∈X

x∈X

(f )

where [x]t = arg minx′ ∈Xt ∥x − x′ ∥1 . Furthermore, define the event Et (f )

1/2

= {∀x ∈ X , |f (x) − µt−1 (x)| ≤ βt (f )

(f )

For the noisy setting, from Lemma A.3, Pr(Et ) ≥ 1 − pt

(f )

B , Nt

(41)

as follows: (42)

σt−1 (x)}. (f )

and Pr Et

(f )

≤ pt , where Et

is a

(f ) (f ) (f ) complementary event of Et . For the noiseless setting, from Lemma A.2, Pr(Et ) = 1 and Pr Et = 0.

Therefore, we can arrange the instantaneous regret as follows: (43)

E [f (x∗ ) − f (xt )] ∗

∗

≤ |f (x ) − f ([x ]t )| + E [f ([x ]t ) − f (xt )] h i h i B (f ) (f ) (f ) (f ) ≤ + E (f ([x∗ ]t ) − f (xt ))1 Et Pr(Et ) + E (f ([x∗ ]t ) − f (xt ))1 Et Pr(Et ) Nt h i B (f ) (f ) (f ) ≤ + E (f ([x∗ ]t ) − f (xt ))1 Et Pr(Et ) + 2Bpt Nt h i B (f ) (f ) (f ) = + EDt−Q−1 E f ([x∗ ]t ) − f (xt )1 Et | Dt−Q−1 Pr(Et ) + 2Bpt . Nt

(44) (45) (46) (47)

where we use (i) f and Xt do not depend on the random quantities for the first line, (ii) the property of the discretization and the decomposition of the expectation for the second line, (iii) maxx∈X |f (x)| ≤ B (f )

(f )

from Assumption 2.3 and Pr(Et ) ≤ pt

for the third line, and (iv) tower property of expectation for

the fourth line. Thus, by combining Lemma B.1, we can see that E [f (x∗ ) − f (xt )] i 2+p h B (f ) (f ) (f ) (g) ≤ E min {2B, ct σt−Q−1 (xt )} 1 Et Pr(Et ) + + 2Bpt + 2Bpt p Nt 2+p B (f ) (g) ≤ E [min {2B, ct σt−Q−1 (xt )}] + + 2Bpt + 2Bpt , p Nt 1/2 (f ) 1/2 (g) 2ζt pt + 1 . where ct = βt pt

(48) (49) (50)

B.2

Proof for Lemma 4.2

Lemma 4.2. For any T ∈ N, λ > 0, and any input sequence {xt }t∈[T ] , the following hold: |T | ≤ 8Qγ|T | (λ2 ) ≤ 8QγT (λ2 ), and ∀t ∈ T c , σt−Q−1 (xt ) ≤

√

2σt−1 (xt ),

2 where T = {t ∈ [T ] | σt−1 (xt ) ≥ λ2 /(2Q)} and T c is its complement set.

Proof. As with the proof for the elliptical potential count lemma (Lemma D.9 in [Flynn and Reeb, 2025], Lemma 3.3 in [Iwazaki and Takeno, 2025], Lemma 6 in [Iwazaki, 2025a]), we can see that |T | =

2 min{1, 2Qλ−2 σt−1 (xt )}

(51)

(52)

t∈T

≤ 2Q

2 min{1, λ−2 σt−1 (xt )}

t∈T

≤ 8Q

X1 t∈T

(53)

2 ln 1 + λ−2 σt−1 (xt )

(54)

≤ 8Qγ|T | (λ2 ) ≤ 8QγT (λ2 ), where the second inequality holds because min{1, a} ≤ 2 ln(1 + a) for all a ≥ 0.

2 For the second inequality, we utilize Lemma A.4. First, if Q = 0, it is trivial that σt−Q−1 (xt ) = 2 σt−1 (xt ). For all t ∈ T c and Q ≥ 1, from Lemma A.4, we can see that 2 λ2 σt−Q−1 (xt ) λ2 2 2 ≤ ⇔ 2Qσt−Q−1 (xt ) ≤ Qσt−Q−1 (xt ) + λ2 2 Qσt−Q−1 (xt ) + λ2 2Q

(55) (56)

2 ⇔ Qσt−Q−1 (xt ) ≤ λ2 2 ⇔ σt−Q−1 (xt ) ≤

λ2 Q

(57)

Therefore, we can obtain 2 σt−Q−1 (xt ) ≤

2 Qσt−Q−1 (xt ) + λ2 2 2 σt−1 (xt ) ≤ 2σt−1 (xt ), λ2

(58)

for all t ∈ T c and Q ∈ N.

B.3

Proof for noisy setting (f )

(g)

E[RT ] = O T

(Q)

√

+ γT T ln T ,

E[rT ] = O

(Q)

= max{t ∈ N | t ≤ 8Qγt }. In particular, T 2ν+d (Q) e T = O Q 2ν for Matérn kernels.

where T

(Q)

! √ + γT T ln T , T

= O Q lnd+1 Q for SE kernels and

Proof. From Lemma 4.2, we can derive T X

min {2B, ct σt−Q−1 (xt )} ≤ 2B|T | + 2cT

σt−1 (xt )

(59)

σt−1 (xt )

(60)

t∈T c

t=1

≤ 2B|T | + 2cT

T X t=1

v u T u X 2 (x ), λ−2 σt−1 ≤ 2B|T | + 2cT tλ2 T t

(61)

t=1

where the second inequality holds due to T c ⊂ [T ] and the third inequality holds from the Cauchy– 2 Schwartz inequality. Since λ−2 σt−1 (xt ) ≤ 1/(2Q) ≤ 1 for all t ∈ T c from the definition of T c , we can

further obtain T X

v u T u X t 2 (x )} 2 min {2B, ct σt−Q−1 (xt )} ≤ 2B|T | + 2cT λ T min{1, λ−2 σt−1 t

t=1

(62)

t=1

v u T u X 1 t 2 (x ) 2 ln 1 + λ−2 σt−1 ≤ 2B|T | + 4cT λ T t 2 t=1 p ≤ 2B|T | + 4cT λ2 T γT ,

(63) (64)

where the second inequality holds because min{1, a} ≤ 2 ln(1 + a) for all a ≥ 0. Furthermore, we (Q)

see that |T | ≤ T since |T | ≤ 8Qγ|T | from Lemma 4.2. By substituting the above equation and P∞ 2 2 t=1 1/t = π /6 into the sum of upper bounds derived in Lemma 4.1, we can obtain the desired result. (f )

1/2

1/t2 σt−1 (x)}.

Next, we show the simple regret upper bound. Let the event Et (f )

= {∀t ∈ [T ], ∀x ∈ X , |f (x) − µt−1 (x)| ≤ βt 1/2

In addition, define LCBt (x) := µt−1 (x) − βt

(65)

1/t2 σt−1 (x). Then, since x̂T = arg maxx∈X LCBT (x),

we can obtain the upper bound as follows: (66)

E[rT ] = E [min {2B, f (x∗ ) − f (x̂T )}] h i (f ) (f ) (f ) c ≤ E min {2B, f (x∗ ) − f (x̂T )} | ET Pr ET + 2B Pr ET h i 2B (f ) (f ) ≤ E min {2B, f (x∗ ) − LCBT (x̂T )} | ET Pr ET + 2 T T h i 2B X 1 (f ) (f ) ≤ E min {2B, f (x∗ ) − LCBT (xt )} | ET Pr ET + 2 T t=1 T

(67) (68) (69)

T i 2B 1X h (f ) (f ) ≤ E min {2B, f (x∗ ) − f (xt ) + f (xt ) − LCBT (xt )} | ET Pr ET + 2 T t=1 T

≤

T n i 2B o 1X h (f ) (f ) 1/2 E f (x∗ ) − f (xt ) + min 2B, 2βT 1/T 2 σt−1 (xt ) | ET Pr ET + 2, T t=1 T

(70) (71)

where (i) the first inequality holds due to maxx∈X |f (x)| ≤ B, (ii) the second inequality holds due to the (f )

definition of ET

(f ) c

and Pr ET

≤ 1/T 2 from Lemma A.3, (iii) the third inequality holds since for all (f )

t ∈ [T ], LCBt (x̂T ) ≥ LCBt (xt ), and (iv) the fourth inequality holds since ET

is true and σt (x) ≥ σT (x)

for all t ≤ T and x ∈ X . Hence, we can finally obtain hP n oi 1/2 T E[RT ] + 2E 1/T 2 σt−1 (xt ) t=1 min 2B, βT 2B E[rT ] ≤ + 2. T T 20

(72)

Then, by the same proof as that of cumulative regret, we can obtain the desired order of the simple regret. Finally, we show the order of T

(Q)

. For the case of SE kernels, it suffices to show Q lnd+1 Q = Ω 8Q lnd+1 Q lnd+1 Q

(73)

d+1

(74)

⇔ C lnd+1 Q > lnd+1 (Q) + ((d + 1) ln ln Q)

where C is some absolute constant. Since we can choose an absolute constant c such that c lnd+1 > (Q) 2ν+d (Q) d+1 e ((d + 1) ln ln Q) , we can choose C = 1+c. For the case of Matérn kernels, by setting T = O Q 2ν (Q) e Q 2ν+d 2ν and we see that QγT (Q) = O . Therefore, we can see that T and QγT (Q) have the same order with respect to Q, which is the desired result.

B.4

Proof for noiseless setting

Lemma B.2 (Formal version of Lemma 4.4, Posterior standard deviation upper bound for SE and Matérn kernel in the noiseless and batched setting). Fix any compact input domain X ⊂ Rd , and kernel function k : X × X → R that satisfies k(x, x) ≤ 1 for all x ∈ X . Furthermore, let CSE , CMat , λSE , λMat > 0, T SE , T Mat ≥ 2 be the constants that satisfies ∀λ ∈ (0, λSE ], ∀t ≥ T SE , γt (λ2 ) ≤ CSE (ln(t/λ2 ))d+1 and d

2ν

∀λ ∈ (0, λMat ], ∀t ≥ T Mat , γt (λ2 ) ≤ CMat (t/λ2 ) 2ν+d (ln(t/λ2 )) 2ν+d for SE kernels and Matérn kernels, respectively. Let B, Q ≥ 0 and {ct }t∈N be monotonically non-decreasing sequence. Then, the following statements hold for any T ∈ N and any input sequence x1 , . . . , xT ∈ X : • For the SE kernels,  1 min σt−Q−1 (xt ) ≤ p 

t∈[T ] T X

if T < QT SE ,

eSE (T /Q) 2T /Q exp − 21 C

min {2B, ct σt−Q−1 (xt )} ≤ 2BQT SE +

t=1

√

2cT (d + 1)

1 d+1

eSE C 2

if T ≥ QT SE ,

− 3d+3 2

3d + 3 2

1 (λ) e d+1 ⌉ + 1} with T (λ) = min{T ∈ eSE = (8CSE )− d+1 where C and T SE = max{T SE , T SE , ⌈(d + 1)d+1 /C SE SE 1 eSE t d+1 ) ≤ λ2 }. N | ∀t ≥ T, t exp(−C

• For the Matérn kernels with ν > 1/2,  1 if T < QT Mat , min σt−Q−1 (xt ) ≤ √ ν ν 1/2  t∈[T ] e (T /Q)− d (ln(T /Q)) d 2C if T ≥ QT Mat , Mat  √ d−ν  e 1/2 d T d Q νd (ln(T /Q)) νd  if d > ν, 2BQT Mat + 2cT C Mat d−ν  T  X √ e 1/2 Q(ln(T /Q))2 /2 if d = ν, min {2B, ct σt−Q−1 (xt )} ≤ 2BQT Mat + 2cT C Mat   √ ν t=1 QΓ( +1)  1/2 d e  if d < ν, ν +1 2BQT Mat + 2cT C Mat ν ( d −1) d n o 2ν (λ) (λ) eMat = max 1, 2 + 2ν d (6CMat )1+ 2ν d where C and T Mat = max{4, T Mat , T Mat } with T Mat = d 2ν

2 eMat t− 2ν d (ln t) d ≤ λ min{T ∈ N | ∀t ≥ T, C Mat }.

Proof. In this proof, we describe the noise to calculate the posterior standard deviation explicitly as in σt−Q−1 (xt ; λ2 ). Therefore, the posterior standard deviation written in this lemma is σt−1 (xt ) = σt−1 (xt ; 0). Note that if λ ≤ λ̃, then σt−Q−1 (xt ; λ2 ) ≤ σt−Q−1 (xt ; λ̃2 ). Thus, to obtain the upper bound of posterior standard deviation in the noiseless setting, we can consider bounding as σt−Q−1 (xt ; 0) ≤ σt−Q−1 (xt ; λ2T ) with some λ2T > 0. 21

First, we show the variant of Lemma 4.2 adapted from Lemma 3.1. Let λ > 0, T = {t ∈ [T ] | σt−Q−1 (xt ) > λ} and Tq = {t ∈ [T ] | t mod Q = q}. Then, as with the proof of Lemma 4.2, for any λ > 0, we can obtain |T | ≤

(75)

2 min{1, λ−2 σt−Q−1 (xt ; λ2 )}

t∈T

≤

Q X X

(76)

2 min{1, λ−2 σt−Q−1 (xt ; λ2 )}

q=1 t∈Tq

≤4

Q X X 1 q=1 t∈Tq

≤4

Q X

2 ln 1 + λ−2 σt−Q−1 (xt ; λ2 )

(77)

(78)

γ⌈T /Q⌉ (λ2 )

q=1

(79)

≤ 4Qγ⌈T /Q⌉ (λ2 ),

where the second inequality holds because min{1, a} ≤ 2 ln(1 + a) for all a ≥ 0. Then, we will control λT to guarantee |T c | ≥ 1, that is, there are at least one index t′ ∈ [T ] such that σt′ −Q−1 (xt′ ) ≤ λT . 1 (λ) eSE (t/Q) d+1 For the SE kernels, we set λ2t = (2t/Q) exp(−C ) and T SE := max{T , T , ⌈(d + SE

(λ)

e d+1 ⌉ + 1}. From the definition of λ2 , T , and T , we have, for any t ≥ QT SE , λ2 ≤ λ2 and 1)d+1 /C t t SE SE SE SE d+1 t −2 λ ln Q t h id+1 1 eSE (t/Q) d+1 ≤ CSE ln exp C

γ⌈t/Q⌉ (λ2t ) ≤ CSE

e d+1 t CSE C SE , Q

(80) (81) (82)

where we use ⌈t/Q⌉ ≤ 2t/Q for all t ≥ QT SE ≥ Q for the second inequality. Furthermore, e d+1 t CSE C t−1 SE e d+1 ≤ t − 1 ≤ ⇔C SE Q 4Q 4CSE t e d+1 ≤ 1 ⇐C SE 8CSE 1 d+1 1 eSE ≤ ⇔C , 8CSE

(83) (84) (85)

where the second line follows from the inequality t − 1 ≥ t/2 for all t ≥ QT SE ≥ 2. From the definition of eSE , we conclude that ∀t ≥ T SE , γ⌈t/Q⌉ (λ2 ) ≤ CSE C e d+1 t/Q ≤ t−1 from the above inequalities. C t

Since |T | ≤ 4Qγ⌈T /Q⌉ (λ2T ) ≤ T − 1 from Eq. (79), we can see that there exists t′ ∈ [T ] such that σt−Q−1 (xt ; λ2T ) ≤ λT . Therefore, we can further obtain mint∈[T ] σt−Q−1 (xt ; 0) ≤ mint∈[T ] σt−Q−1 (xt ; λ2T ) ≤ p p 1 1 eSE (T /Q) d+1 eSE (T /Q) d+1 λT ≤ ⌈T /Q⌉ exp(− 12 C ) ≤ 2T /Q exp(− 12 C ) for T ≥ QT SE . For T < QT SE , it is obvious that σt−Q−1 (xt ; 0) ≤ k(xt , xt ) ≤ 1 from Assumption 2.3. Regarding the sum of the posterior standard deviations, by repeatedly picking the index t′ that

satisfies σt′ −Q−1 (xt′ ; λ2t ) ≤ λt for all t ≥ QT SE as with [Iwazaki, 2025a], we can see that T X

min {2B, ct σt−Q−1 (xt )} =

t=1

T X

(86)

min {2B, ct σt−Q−1 (xt ; 0)}

t=1 T X

≤ 2BQT SE + cT

(87)

λt

t=QT SE

√

Z T

p 1 1e d+1 ≤ 2BQT SE + 2cT t/Q exp − CSE (t/Q) dt 2 QT SE −1 Z Tp √ 1 1e d+1 ≤ 2BQT SE + 2cT t/Q exp − C (t/Q) dt, SE 2 0

(88) (89)

eSE (t/Q)1/(d+1) ) where the second inequality follows from the fact that the function g(t) := (t/Q) exp(−C is non-increasing for t ≥ QT SE − 1. In fact, we have eSE 1 1 1 C eSE (t/Q) d+1 g (t) = exp −C 1− (t/Q) d+1 Q d+1 ′

! ,

(90)

1 e d+1 . Let u be u = C eSE t d+1 which implies g ′ (t) ≤ 0 for t ≥ QT SE − 1 ≥ Q(d + 1)d+1 /C /2. Then, we can d+1 SE d e e e obtain t = 2u/CSE and dt/du = 2(d + 1)/CSE 2u/CSE . Therefore, we can obtain

Z Tp 0

Z ∞√ 1 1 1e 1 e d+1 d+1 t/Q exp − C t exp − (t/Q) dt ≤ C t dt SE SE 2 2 0 3d+3 Z T 2 3d+1 2 u 2 exp(−u)du = (d + 1) e CSE 0 3d+3 2 2 3d + 2 = (d + 1) Γ , eSE 2 C

(91) (92) (93)

where the last equality uses the definition of the Gamma function. 2ν 2ν (λ) eMat Q 2ν d t− d (ln(t/Q)) d and T Next, for Matérn kernels, we set λ2t = 2C Mat = max{4, T Mat , T Mat } 2ν eMat = 2 + 2ν d (16CMat )1+ 2ν d . Then since ⌈t/Q⌉ ≤ 2t/Q for all t ≥ QT with C Mat ≥ Q, we can obtain, d for any t ≥ QT Mat , d 2ν 2ν+d 2ν+d 2t ln Qλ2t 2ν " !# 2ν+d 2ν − 2ν+d − 2ν d d 2ν+d 2ν+d t t t − 2ν+d e −1 Q− d t d e ln ln C ln = CMat C Mat Mat Q Q Q 2ν 2ν − 2ν+d 2ν+d d e −1 + d + 2ν ln t − 2ν (ln ln(t/Q)) e − 2ν+d t ln t ln C = CMat C Mat Mat Q Q d Q d 2ν 2ν − 2ν+d 2ν+d d 2d + 2ν t e − 2ν+d t ln t ≤ CMat C ln Mat Q Q d Q 2ν 2ν+d d e − 2ν+d t 2d + 2ν = CMat C , Mat Q d

γ⌈t/Q⌉ (λ2t ) ≤ CMat

2t Qλ2t

(94) (95) (96) (97) (98)

eMat ≥ 1 ⇒ C eMat ≥ Q/t ⇔ ln(C e −1 ) ≤ ln(t/Q) for t ≥ Q. where the fourth line holds because C Mat

Furthermore, e − 2ν+d t CMat C Mat Q d

2d + 2ν d

2ν 2ν+d

2ν d t−1 t 2d + 2ν 2ν+d e 2ν+d ≤ ⇔ 4CMat ≤C Mat 4Q t−1 d 2ν 1+ 2ν d 2ν d 4CMat t eMat 2+ ≤C ⇔ t−1 d 2ν 2ν d 1+ 2ν eMat . ≤C ⇐ (8CMat ) d 2 + d

(99) (100) (101)

Combining the above inequalities, we can confirm 4Qγ⌈t/Q⌉ (λ2t ) ≤ t − 1 for all t ≥ QT Mat . Therefore, as with the case of SE kernels, from Eq. (79), we can obtain mint∈[T ] σt−Q−1 (xt ; 0) ≤ mint∈[T ] σt−Q−1 (xt ; λ2T ) ≤ √ 1/2 e (T /Q)− νd (ln(T /Q)) νd for T ≥ QT Mat . λT ≤ 2C Mat

Regarding the sum of posterior deviations, by repeatedly picking the index t′ that satisfies σt′ −Q−1 (xt′ ; λ2t ) ≤ λt for all t ≥ QT Mat as with [Iwazaki, 2025a], we can see that T X

min {2B, ct σt−Q−1 (xt )} =

t=1

T X

(102)

min {2B, ct σt−Q−1 (xt ; 0)}

t=1 T X

≤ 2BQT Mat + cT

(103)

λt

t=QT Mat

− νd ν t t d ln dt Q Q QT Mat −1 ν Z T − νd √ t d t 1/2 e ln dt, ≤ 2BQT Mat + 2cT CMat Q Q Q ≤ 2BQT Mat +

√

1/2

Z T

e 2cT C Mat

2ν

(104) (105) 2ν

where the second inequality follows from the fact that the function g(t) := (t/Q)− d (ln(t/Q)) d is non-increasing for t ≥ QT Mat − 1 ≥ 3Q > eQ. Indeed, we have g ′ (t) =

2ν 2ν 1 2ν (t/Q)− d −1 (ln(t/Q)) d (ln(t/Q))−1 − 1 , Q d

(106)

which implies g ′ (t) ≤ 0 for t ≥ eQ. The desired results are obtained by bounding the quantity RT R T /Q − ν ν ν ν (t/Q)− d (ln(t/Q)) d dt = Q 1 t d (ln t) d dt from above. When d > ν, we have Q Z T /Q Q

t− d (ln t) d dt ≤ Q(ln(T /Q)) d

Z T /Q

(107)

t− d dt

= Q(ln(T /Q)) ≤ Z T /Q

t−1 (ln t) dt = Q

d d−ν t d d−ν

T /Q

(108)

d−ν ν ν d T d Q d (ln(T /Q)) d . d−ν

When d = ν, Q

ν d

T /Q 1 Q (ln t)2 = (ln(T /Q))2 2 2 1

(109)

(110)

When d < ν, we have Z T /Q Q

t− d (ln t) d dt = Q

Z ln(T /Q) Z0 ∞

≤Q

e−( d −1)u u d du ν

(∵ u = ln t)

e−( d −1)u u d du ν

(111) (112)

QΓ( νd + 1) νd +1 , ν d −1

where the last equality follows from the standard property of the Gamma function: Γ(b + 1)/λb+1 for any λ > 0 and b > −1. 24

(113) R ∞ −λu b e u du = 0

Note. We can obtain a result similar to Lemma 4.4 also by using Lemma 4.2 instead of Eq. (79), but in such a case, the order of the cumulative regret upper bound with respect to Q becomes worse from Θ(Q) to ω(Q). Here, we consider the case of SE kernels, but a similar discussion holds for Matérn kernels. If we use Lemma 4.2 instead of Eq. (79), the necessary condition with respect to T ≥ QT SE is changed. Specifically, if we naively use Lemma 4.2, then the necessary condition with respect to T ≥ QT SE can be tightened as T ≥ T SE . This is because, to apply the MIG upper bound based on Eq. (79), T /Q ≥ T SE is required, although only T ≥ T SE is required for the case of Lemma 4.2. On the other hand, the (λ)

necessary condition with respect to T ≥ QT SE ⇔ λ2T ≤ λSE is degraded. This is because, if we naively 1 eSE (t/Q) d+1 use Lemma 4.2, then λ2t is set as λ2t = 2t exp(−C ), where the 1/Q factor is removed. Thus, the necessary condition with respect to λ2T ≤ λSE becomes worse from T = Ω(Q) to T = ω(Q). Thus, we employ the proof using Eq. (79) to obtain the O(Q) upper bound. (g)

Corollary 4.6. Suppose Assumptions 2.3 and 2.5 hold. Set 1/Nt = pt

= 1/t2 and other variables as in

Lemma 4.1. In addition, define x̂t = arg maxt∈[T ] f (xt ). Then, the following inequality holds:  1   O QT −1 + T −1 ln 2 T     ν ν  e QT −1 + T − d Q d O E [rT ] = 5  −1 2 T  O QT ln      O QT −1 ln 12 T

for SE kernels, for Matérn kernels with d > ν, for Matérn kernels with d = ν, for Matérn kernels with d < ν,

e suppresses the polylogarithmic factors for T and Q. where O (g)

Proof. From the settings of 1/Nt and pt , the dominant term of the simple regret can be written as ∗ E[rT ] ≤ E min f (x ) − f (xt ) (114) t∈[T ]

1 ≤ E [RT ] . T Thus, from Theorem 4.5, we can obtain the desired result.

(115)

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

Analyze & explore related research in Conceptio

Related documents