Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization
Authors: Shion Takeno
Yu Inatsu
Masayuki Karasuyama
Ichiro Takeuchi
Venue: Accepted by TMLR ()

Abstract: Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demonstrated in a wide range of applications. However, theoretical analyses of EI are limited compared with other theoretically established algorithms. This paper analyzes a randomized variant of EI, which evaluates the EI from the maximum of the posterior sample path. We show that this posterior sampling-based random EI achieves the sublinear Bayesian cumulative regret bounds under the assumption that the black-box function follows a Gaussian process. Finally, we demonstrate the effectiveness of the proposed method through numerical experiments.

Published in Transactions on Machine Learning Research (09/2025)
Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization
Shion Takeno
takeno. mllab. nit
Deportment of Mechanical Systems Engineering, Nagoya University RIKEN Center for Advanced Intelligence Project
Yu Inatsu
thatsu..ju@nitecc.cccm
Department of Computer Science, Nagoya Institute of Technology
Masayuki Karasuyama
kerosuyomoo@hittch.c...
Department of Computer Science, Nagoya Institute of Technology
Ichiro Takeuchi
takeuchi, ichiro. mb mail www.aaaaaa.......e...
Department of Mechanical Systems Engineering, Nagoya Universily
RIKEN Center for Advanced Intelligence Project
Reviewed on OpenReview: https: // openreview net/ for id= u0s99kn99c
Abstract
Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demon- strated in wide range of applications. However, theoretical analyses of El are limited compared with other theoretically established algorithms. This paper analyzes random- ized variant of EI, which evaluates the EI from the maximun of the posterior sample path. We show that this posterior sampling-basee random El achieves the sublinear Bayesian cumulative regret bounds under the assumption that the black-box function follows a Gaus- sian process. Finally, we demonstrate the effectiveness of the proposed method through mumerical experiments.
1 Introduction
Bayesian optimization (BO) (Shahriari et al.) 2016) a powerful tool for optimizing expensive-to-evaluaae black-box functions. BÒ aims for optimization with fewer observations due to the expensive evaluation cost of the objective function. For this purpose, BO sequentially queries candidate input determined by maximizing acquisition function (AF) based on some Bayesian model. That is, the queried candidate arg max a(x)) where a(x) is an AF computed based on the Bayesian model. A Gaussian process (GP) model (Rasmussen & Williams 2005) is typically employed in BO. BO has been applied to various fields, such as materials informatics (Ueno et al. 2016), robotics (Berkenkamp
1-th iteration Dt is chosen
et al. 2023); and hyperparameter tuning (Snoek al. 2012
Several widely used BО algorithms are based on an improvement from a reference value, which is often set the current best observation. The GP-based probability of improvement (GP-PI) algorithm (Kushner) 1964) evaluates the AF defined the probability that However, it is known that GP-PI is too exploitative depending on the reference value (Jones) 2001 Shahriari
observation exceeds the current best observation.
et al. 2016). Therefore, GP-based expected improvement. (GP-EI) (Mockus et al. 1978 Jones el al. 1998
which evaluates the expectation of improvement from the current best observation, has been frequently used.
The effectiveness of GP-FI has been repeatedly demonstrated not only in the usual BO (Snock et al. 2012
Ament al. 2023) but also in several extended BO settings, such as multi-fidee multi-fidelity BO (Huang et al.
2006
constrained BO (Gardner et al. 2014 Gelbart al. 2014). multi-objective BO (Emmerich et. al.
201 and

---

Published in Transactions on Machine Learning Research (09/2025)
BO with large noises (Letham et al. 2019) best observation, which can include noise, its heuristic hyperparameter tuning approach has been discussed; for example, see Section 2.3.2 in (Brochu et al. 2010) and (Lizotte 2008). Hence, GP-EI is often regarded as a heuristic method with strong empirical performance.
However, since the usual GP-EI still depends on the current
Other lines of study have tackled obtaining theoretical regret bounds (for example, SSinivas et al., 2010 Russo & Van Roy 2014). Seminal work (Srinivas et al., 2010) showed the cumulative regret upper bound for the GP upper confidence bound (GP-UCB) algorithm. Russo & Van Roy (2014); Chowdhhry & Gopalan (2017)
derived the cumulative regret upper bounds for the GP-based Thompson sampling algorithm (GP-TS).
Furthermore, [carlett (2018) showed the algorithninndependent regret lower bound and tighter regret upper bound under several conditions. Recently, Taakno et al. (2024) showed that the variant of GP- PI called GP-PI from the maximum of sample path (GP-PIMS) achieves a sublinear Bayesian cumulative regret (BCR) upper bound. GP-PIMS avoids the problem of selecting the reference value by replacing it with the maximum of the posterior sample path, inspired by GP-TS. Furthermore, a recent study (Iwazaki, 2025) showed lighter high-probability regret upper bound for the usual GP-UCB.
Several studies (Bull 2011 Wang & de Freitas 2014 Nguyen et al. 2017 Berk et al. 2019 have attempted to obtain regret guarantees of GP-EI-based algorithms, in which the reference value is often changed from the current. best observation to, for example, the maximum of the posterior mean (Wang & de Freitas 2014), and the maximum of the posterior sample path (Berk et al., 2019). However, as reported in existing
studies (Tran-Thee et al.] 2022 Bedi et al. 2022 Hu et al. 2025), several analyses appear incorrect (See
Section 3 and Appendix A for more details). ) Other theoretical analyses in (Wang & de Freitas 2014 Tran-
The et al. 2022 require rescaling the posterior variance, which can deteriorate the practical optimization performance. Hence, theoretical analysis for GP-El-based algorithms without posterior variance rescaling has not been established except for the noiseless case Bull 2011
This paper analyzes the posterior sampling-based GP-EI algorithm inspired by GP-PIMS Takeno et al. 2024), which is GP-EI with the reference value set by the maximum of the posterior sample path. We refer to this algorithm as GP-FT from the maximum of the sample path (GP-FIMS). We show that GP-EIMS achieves the sublinear BCR under the Bayesian setting, where the objective function follows GPs. Moreover, GP-EIMS does not require rescaling of the posterior variance. Finally, we demonstrate the effectivencss of GP-EIMS, which stems from avoiding posterior variance rescaling, compared with other theoretically guaranteed El-based methods through numerical experiments.
2 Preliminary
Bayesian Optimization:
We consider the black-box optimization for f X + IR formulated as
x arg max f(x),
#ex
where X Rdd is an imput domain and d is dimension. We assume that only observations y= f(x) + c. where is noise, can be obtained, but are costly. Thus, our goal is to optimize ʃ with the fewest observations possible, For this goal, BO sequentially performs queries on an imput point æ, and observes y1 = =z + where t is an iteration. The queried input x; is chosen as o; = arg max a(x), where axx) is an AF computed based on the Bayesian model updated by the collected dataset.
Gaussian Process Model: In this paper, we assume that f follows a GP with a predefined kernel k X x X + R, denoted as ʃ CP(O,k). We further assume that the observation is contaminated by Gaussian noise; that is, Vi = f(x)) + Es, where e ~ (N(0, o2) with a positive variance o² 0. Let D = [ be the training data obtained until the beginning of 1-th iteration. Then, the posterior distribution p(f D,-1) is a GP again (Rasmussen & Williams 2005 whose mean and variance can be
obtained as follows:
[ k. (x= (K + -²Ir_1)~ V1-1 of k(Ø, (2)) (K + I² (-)((x),
(1)
(2)
2

---

0f and [d] fl....... Published in Transactions on Machine Learning Research (09/2025)
where (1-1(x))== (1(x, ((,,, E R is the kernel vector, K E ([((=))x(-1)) is the kernel ma- trix whose (i. (clementt is k( 2z), I E (((-))x((-1) is the identity matrix, and yz-1 == (U1..... 1e-1) R Hereafter, we denote that a probability density function (PDF) p(-12-1) = -p+(), a probability Pr(-ID--1) (r, and an expectation [[-[ [.[:] for brevity.
Furthermore, for the case of continuous X, assume the following smoothness condition for GPs: Assumption 2.1. Let X C 10, be compact and convex set, where > 0. Assume that the kernel k satisfies the following condition on the derivatives of a sample path f. There exists the constants a 2 1 and > such that,
(-(9)), for j E [d]
Pr > c) S a exp
(3)
where L, = supzex dm;
This assumption is commonly used (Srinivas et al. and holds at least for the squared exponential (SE) and Matérn-w kernels with v > 2 (Thcorem 5 in Ghosal
2010 Kandasamy et al. 2018 Takeno et al. 2023 2024
& Roy
2006 Srinivas et al. 2010).
Maximum Information Gain: For regret analysis, we will use the quantity called maximum information gain (MIG) (Srinivas al.) 2010: Vakili al. 2021bb:
Definition 2.2 (Maximum information gain). Let f GP((,) k) over X [0, Let A {a:) where X' for all i E [T]. Let fA = (f(a.)) i CA (4) where ~ NNO, o²) for all E [T]. and
yA E E Then, MIG Pr is defined follows:
TT = max fA) such that |A] = T and a, E E for all i (7),
(4)
A
where I is the Shannon mutual information.
For frequently used kernels, MIG is known to be sublinear (Srinivas et al. 2010 Vakili et al. 2021b), for example, ?r ((lg T))+1) for the SE kernels and "r 0 (T (log 7) lerd for the Matérn-v kernels.
Performance Mcasure: We evaluate the theoretical performance of BO methods by the BCR Russo &
Van Roy 2014 Takeno et al. 2023
2024 defined as
BCR E(I((') ((x)),
where the expectation is taken with all the randomness, that is, J, (e))eet)) and the randomness of the algorithm. For example, in GP-TS, GP-PIMS, and GP-EIMS, the randomness of the algorithm implics the posterior sampling. Our goal is to show the sublinearity of the BCR since it implies that the simple regret E [ff(=)) - f(tr) < BCRT/T + as T + co (Proposition 8 in Russo & Van Roy 2018 where dr = arg m (xx is recommendation point at T-th itcration. The Bayesian regret has been
analyzed in many existing studies (Russo & Van Roy 2014 2018 Kandasamy et al. 2018 Paria et al. 2020 Takeno et al. 2023 2024]. Although the Bayesian regret quantifies the average performance of the algorithm, the Bayesian regret upper bound immediately implies high probability upper bound due to Markov's incquality. For more details, refer (Sec. 3.1 in Russo & Van Roy 2014).
GP-based EI algorithm: GP-EI is the widely used AF for BO MMockus al. 1978 Jones et al.
1998
As the name suggests, the AF of GP-EI given D.-1 at 1-th iteration is defined as follows:
El(p-1(()) Te- (z) ) E, Imax{((a - max 03
(6)
(a=-((r)) (Mr)T
oz (a:1 (x) > 0,
)(-)(=))
(7)
max (axx(p=11800 - 0}
if (0-1(x) = 0,
3

---

Published in Transactions on Machine Learning Research (09/2025)
where - max Me is the current best observation, T:R R+ is
= - + d(c).
(8)
and @ and o are the cumulative distribution function and the PDF of the standard Gaussian distribution. Mainly due the noise included vi-1, regret analysis for the original GP-FT is difficult.
3 Literature Review for Regret Analysis of GP-EI
The two most commonly used assumptions for the regret analysis in the BO literature are the Bayesian setting that f follows GPs (Srinivas et al. 2010 Russo & Van Roy] 2014; Takeno al. 2023 2024) and the frequentist setting that f belongs to the known reproducing kernel Hilbert space (RKHS) (Srnniaas et al. 2010 Chowdhury & Gopalan 2017 Janz et al. 2020 Twazaki & Takeno 2025). Furthermore, the analyzed regret can be categorized as cunulative regret recommended imput at t-th iteration, for example, 2, arg max (z(x). In addition, we discussed above, refer to its expected variants as BCR and Bayesian simple regret in the Bayesian setting. Although our main analysis concentrates on the BCR analysis in the Bayesian setting, we review the analyses of GP-EI for both regret, definitions in both settings.
fxx) and simple regret f(x=*) f((=)) with some
3.1 Regret Analysis for Noise Setting
Seminal works for the regret analysis of GP-EI concentrated on a noise-free setting where observation noise does not exist. Therefore, there is no need to care about the noise. Vazquez & Bect (2010) show that GP-EI asymptotically converges on the optimum for both Bayesian and frequentist settings regarding the stationary and non-degeneraey kernels, such as the Matérn kernel family. Grüüewälder et. al.. (2010) proves that the computationally intractable T-step look-ahead variant of GP-EI is near-optimal in the noise-free Bayesian setting under assumption that the prior mcan function and the kernel function are Hölder-comtinuous. Here, near-optimal means that regret upper bound matches regret lower bound except for logarithmic factors. Bull (2011) further shows simple regret upper bounds of GP-EI and modified GP-EI algorithms for the Matérn kernel family in the frequentist setting. In particular, the modified GP-EI is shown to be near-optimal.
3.2 Regret Analysis with Rescaling Posterior Variance
Wang & de Freitas (2014) 4h show the high-probability cumulative regret upper bound in the frequentist. setting
for case where additional noise contaminates observations, as with our setting. For this analysis, [Wan & de Freitas 2014) propose to use p = maX (x) instead of yi and to scale σ;-1(x) by v 1/2 > 0
in the AF of GP-EI as follows:
(t-1(z) p v 1/2 (
1/2 01-1(2)7 1/2 o0- (2)1 max) = v/ E
(9)
where = 0 (n)). Their analysis shows O V cumulative regret upper bound, which is sublinear, for example, for the SE kernel. However, since > in most cases, the above rescaling strengt hens the exploration behavior, and the practical effectiveness can deteriorate. As a result, in the practical scenarios, we must tune Vi as a hyperparamcter. Note that although Wang & de Freitas (2014) further consider a case where hyperparameters of GPs are unknown, focus on case where the hyperparameters of GPs are specified beforehand.
Tran- The al. 2002 analyze EI(pe-1()).. v.. o (x), (x), which avoids an optimization over (contin- uous) X by replacing p in (Wang & de Freitas 2014 Çitea (( /4-1(m)), in the frequentist setting. However, Tran-The et al. (2022) only analyze the simple regret. f(x²) f(,,) = O(Tr/VT). There- fore, even in the frequentist setting, the cumulative regret upper bound of the GP-EI algorithm with pr
1 Although Theorem in Wang & de Freitas 2014 states
3/2 3/2
helieve that their proof suggests O(Tr VT).
4

---

Published in Transactions on Machine Learning Research (09/2025)
has not been shown to our knowledge. Furthermore, their algorithm suffers from the same problem WWag
& de Freitas 2014), that is, the rescaling of posterior variance.
Although Wang & de Freitas (0014) Tran-Thh et al. (0022) discuss only the frequentist setting, their deriva- tion can be extended to the Bayesian setting by carefully applying well-known proof techniques mainly
from (Russo Van Roy, 2014] Kandasamy et al. 2018 Takeno et al.] (023). For completeness, we
show high probability curuulative regret upper bounds and BCR upper bounds in the Bayesian setting of El(ue1((z), 0)-1(()), 1) and EI(H)_((z), w/! 0,-1(x), AT"T)) in Appendices B.2 and B.3 respec- tively. Since our analysis for finite input domains can apply almost similarly to the frequentist setting, the o
cumulative regret incurred by EI())1((x))) 1/2 01-1(z), P is O(TrVT) in the frequentist setting (see
Appendix B.4 for details).
Hu et al. (025)) recently analyze the GP-EI-based algorithm combining (1()-11()),)))))))1)))))())) v.! v/ ( ((m)) and candidate elimination based on quantity ( (1,"1, 1/2 1/2 0,-1(z)), (t- (T t) called evaluation cost. However, although Remark 1 in (Hu et al. 2025) claim that their V(TvVT) cumulative regret upper bound is Vighter than the existing result, O( T) cumulative regrel upper bound has already been shown in (Wang& & de Freitas 2014) with the reference value po described above. Furthermore, even in the case that the reference value is p the cumulative regret upper bound O(TrVT) can be obtained without any modification to the GP-EI algorithm (see Appendix B Hence, the importance of the candidate elimination based the evaluation cost is ambignous in the theorem.
3.3 Other Related Works
Several other studies analyze GP-EI without rescaling of the posterior variance based on (Nguyen et al. 2017). Nguyen et al. (2017) claims that the cumulative regret upper bound for the usual GP-FI with y maa
is sublinear in the frequentist setting. However, as shortly discussed in Section 3 of (Tran- et al. 2022).
Remark of (Hu et al.
2025 ; and Section of (Wang et al. 2025), Lemma 7 in (Nguyen et al.) 2017]. which
claims ΣT 0f Σi=1 as E (z;) = O(Tr) (Srinivas et al. 2010). The incorrect derivation in (Nguyen et al. 2017 is the last equality in the proof of Lemma 7. The counter-examples are shown in Appendix A
= O(T) for all x E X, incorrect. Note that the usual upper bound by MTG given
At least to our knowledge, Eq (8) in Berk et al., 2019), page 37 in (Grosnit et al. 2021 ), Eq. (9.26) in (Bedi et al. 2022), Lemma B.3 in (Marisu & Pun 2023), and Lemma in (Zhou et al.) 2024) in the regret analyses of GP-FI-based algorithms are also incorrect by using similar result from Lemma in (Nguyen) et al. 2017). In addition, this mistake has been used for regret analyses for other AFs, such as Lemma 6 of (Nguyen et al. 2019), Lemma 12 in (Husain el al. 2023).
Exploration enhanced El (E*1) (Berk et al. 2019 is the following GP-EI variants:
E²I(x) = E (Bg-ni(((rr))) (2))((2)7
[it-i(x) - gt )
01-1 (x) o6
(10)
where Jt ~ pf( is the sample path from the posterior and of maX (xx) The expectation regarding of ~ (f((xx))) is approximated by Monte Carlo (MC) estimation. However, as we alrcady discussed, their analysis appears incorrect. We will consider GP-EIMS, a similar posterior sampling based GP-EI algorithm that uses only one posterior sample. In the BCR analyses of GP-EIMS, the probability matching property between of and f(x",, that is, the randomness caused by the algorithm relying on only one sample, plays a key role, as with the analyses of GP-TS (Russo & Van Roy 2014 Kandasamy et al., 2018 Takeno et al., 2024)-
Fu et al. (024 analyze the GP-EI algorithm without the posterior variance scaling for the bilevel opti- mization problem. However, the derivation from Eq. (D.8) to Eq. (D.9) in (Fu et al.) 2024) is not ob- vious. In Eq. (D.8) in dFu et al. 2024), the regret upper bound has the multiplicative term -(.))サr
with BT = O(logT), Then, T(3)) - BT = 3TØ(37) (++ 1-4(8r) o(0r)
= ((37((3T) since the mills ra-
1-b(c) 0 tio 1-#(c) 1 as + oo (for example, see Eq. (7) in Gasull & Utzet, 2014 and c ((c)
d(c)
5

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm GP-EIMS
Require: Input space X, GP prior μ 0 and and initial dataset Do
for t = do Fit GP to D
Generate sample path 9: ~ p(f(D--1)
4: gi f maxxex (t(x))
5: It f- arg max (2) 10-001100 (
Observe y1 f())) + e and D. t- D U (t)
end for
for all 0. Therefore, we can see -( 2(1/(3r((3r)) Recalling BT Gllo T), the term - 1(TlooTT log 7), which is not sublinear.
Wang et al. 2025 tackle theoretical analysis of the usual El with y without the posterior variance scaling. However, Wang et al. (2025) analyze a quantity f(x") - yT which is not the established regret definition, and can be negative. Paritularly when the noise variance o² is large compared with f(x"), then fx=) - yTax can diverge to -co rapidly by noise. Therefore, analyzing f(x") ) - yfax is not advisable in general.
4 GP-EIMS
This section provides the algorithm and the BCR upper bounds of GP-EIMS.
4.1 Algorithm
As with GP-PIMS
(Takeno al. 2024), we use the sampled maximum defined as follows:
9.' max (x()),
(11)
where gi p(f(Dr-1) is the sample path from the posterior. Then, the AF of GP-EIMS is
(() (2)) )i) = E (())))(((()) [max{f(x) -i, 0Hgrl
(12)
= =
(4-1((x) σ--1(x)
9t
(13)
Note that the posterior variance (x)) is not rescaled. Finally, an algorithm of GP-EIMS is shown in Algorithm The difference from the usual AF of GP-EI is only changing the reference value as g from Vi-1
4.2
Regret Analysis
First, we can obtain general BCR uppor bound for arbitrary BO algorithms, as shown in Takeno et al. 2024):
Lemma 4.1. Let
9e - 14 114111220 (2:e)
(14)
0x-1(x1))
Then, the BCR can be bounded from aboue follows:
BCRT <
E
2 2 0} Varr,
(15)
where C1 == 2//log( 2) and the indicator function 1 (n 0) = if n 2 0, and 0 otherwise.

---

Published in Transactions on Machine Learning Research (09/2025)
For completeness, Σ E [of {n 2 0)] ((T2//r) based on the property of GP-EIMS so that the resulting BCR upper bounds are sublinear.
show the proof in Appendix C41
Hence, can concentrate deriving
For this purpose, the following lemma plays a key role in our analysis. For more detailed proof, see Ap- pendix C.2
Lemma 4.2. Fiz B 0 and U S max (4-1(1)) 3 01-1 (z)). Suppose that k(z, x) S 1 for all x X. Then, the following inequality holds:
U - 14
0 +² -
log
+ B + V
(16)
0 (2))
where H2 = arg max El( (z)
Short proof. As with (Wang & de Freitas 2014), by using the properties of r(-) and the posterior variance and the definition of ær, we can obtain
( UI (Vioe) 0² ( 1 1) 0²
2 log (F(-31/2)) - -log(22) o
(17)
However, since the AF is defined by instead of max (x) in (Wang & de Freitas 2014). we must further obtain an upper bound of -2 (T(-3)/2)) To obtain the upper bound, we leverage the following useful result:
Lemma 4.3 (Lemma in Jang 2011
Q-function 1 ((c) can be bounded from above as follows:
1- (c) <
1 1-exp exp
π
exp
c²
(18)
2TCC
2
exp
π (-V
2
((c).
(19)
c
for all > 0.
By using Lemma 4.3 and properties of 4 and o, we can obtain the following inequality:
T(-3112) = - ( 1/11/ + x(-
(20)
(1 1 -21/2
(18(2))))) (181122
(21)
2-(1-exp) (-V 3322) )) )(311)) 132122
(
(22)
π 1 6(81/2)
= exp
(23)
Hence, we see that log (T(-31/2) < 3 log log()(31/2)) V2T - 3 + log(2r). Consequently, by combining the results, we obtain the desired result.
By leveraging Lemmas 4.1 and
4.2 we show BCR upper bounds for discrete and continuous input domains.
4.2.1 BCR Upper Bound for Finite Input Domain
We combine the following lemma from (Srinivas et al. 2010 Takeno et al. 2023 with Lemma 4.2
Lemma 4.4 (Lemma 4.1 in Takeno et al. 2023)). Suppose that f a sample path from GP with zero mean and predefined kernel k and X' finite. Pick 8 E (0, 1) and 2 1. Then, for any given Dz-1,
Pr. (I(m) S (=)( (12(()) (2)), Who E EX) 21-6
(24)
where B(6) 2 log((X{)/(2)))

---

Published in Transactions on Machine Learning Research (09/2025)
Since f(x*) Di-1 and D are identically distributed, this lemma implics that
Pr gi
max(m1-1(2) + 3 (0)o wEAt
8.
(25)
Thus, applying Lemma 4.2 by substituting of to U, we can derive the following result:
Corollary 4.5. Assume the same condition as in Lemma 4-4 Suppose that k(æ, x) S for all a E X. Then, by running GP-EIMS, the following inequality holds with probability at least 1 - 6:
0² + 1 + 3(0) + V2T((0),
1 log
(26)
σ²
where B(6) = =(6)=2log((( 1ogg(1x1((26)). Furthermore, we oblain
/² - + C2 + V2TC2.
11 1m 2 0}] < log
(27)
02
where C2 = 2 2
See Appendix C.3 for the proof. The first inequality is direct consoquence Lemmas 4.2 and 4.4 The
second inequality be derived similarly to the proof of Lemma 3.2 in (Takeno al. 2024
Consequently, from Lemma 4.1 and Corollary 4.5 we obtain the following BCR upper bound:
Theorem 4.6. Let f ~ (P k), where the kernel function l is normalized as k(æ, x) S 1, and X be finite. Then, by running GP-EIMS, the BCR can be bounded from above as follows:
BCRT S VCBBTT.
(28)
where By log (2"tT-1) + C2 V C1 = 2/ log(1 + o o) and C2 = 2 loo (log(
See Appendix C.3 for the proof. The BCR upper bound of GP-EIMS for finite input domains is (TT log(T x)), which sublinear at least for the SE, linear, and Matérn kernels.
4.2.2
BCR Upper Bound for Continuous Input Domain
For continuous input domains, as with the prior works (for example, Srinivas et al. 2010 Kandasamy et al. 2018 Takeno et al. 2023 2024), we consider a discretized input set X, C X, which is a finite set with each dimension equally divided into my 2 1. Thus, [&l m.. Furthermore, we define the nearest point of æ in X as (æ>. arg mi || x ||
If we consider the AF, El(pt-1(z) (x), 0.-1(()), 9r), where 9i maXxeX, (z(w), a sublinear BCR upper bound can be derived in similar way to the proof of Theorem 4.6 However, for Xr must depend on several unknown parameters such as a and b in Assumption 2.1 T Thus, my must be tuned by users if the computation of Øf is required in practico. Hence, using øf means that a new tuning parameter my is involved, which is not preferable. Therefore, we consider BCR upper bound for EI( (x)), at- (x),, which does not require the discretization the actual algorithm, as with the analyses of GP-PIMS [Takeno al. 2024).
From Lemma 4.4 and Assumption
2.1
we obtain the following lemma by appropriatcly controlling me:
Lemma 4.7. Suppose Assumption
2.1 holds. Pick 8 E (0, 1) and t 2 1. Then, the following holds:
Pr, (Vz E f(x) S (t=1((x)e) + 23 1/2 (6/2)
2 - 5,
(29)
where (6)8) = log (28) and m, = max bdr / 10² + t- log((dd) 02
See Appendix C.4 for the proof. As with the case of finite input domains, since f(x*) D.-1 and gi De-1
are identically distributed, Lemmas 4.2 and 4.7 derive
0²
+1 + V
E m 1 (n. 0}} < log
(30)
02
8

---

Published in Transactions on Machine Learning Research (09/2025)
where Cr- 8(d + 1).
Consequently, the BCR upper bound can be derived:
Theorem 4.8. Suppose Assumption 2.1 holds and f ~ GP(O, k), where the kernel function k is normalized
as k(z, - 1. Then, by running GP-EIMS, the BCR can be bounded from above as follows:
BCRT S VCBBTTT
(31)
where C1 = 2/log( + 2) Br = log max [bdr / + +T 1) log( (2dd)// [
(
+ Or + V2TOT, CT = 8(dlog(mT) + 1), and mr
See Appendix C.4 for the proof. As with Theorem 4.6 BCRT = OlVTTI log T), which sublinear for widely used kernels, such as the SE, linear, and Matérn kernels.
5 Experiments
We performed numerical experiments using synthetic functions generated from GPs, which match the as- sumptions for our analysis. We set = {0.0, o..,...,0.91 and d = 4. Therefore, = 10 We employed exp (-1 x' 2212 Furthermore, we actually added observation noise NN(00, ) We report results changing & (0.1, and (0.01,0.1,1) We fixed the hyperparameters of the GP model, that is l and a, to the parameters used to generate the synthetic functions and observation noise. We set an initial dataset to data that is closest to 2d data generated randomly
the SE kernel kgg(2,
Sobol sequence.
As baselines, we employed GP-UCB (Srinivas et al. 2010 improved randomized GP-UCB (IRGP- UCB) Takeno et al. 2023), which uses the random variable Çe instead of Be in GP-UCB, GP-TS Russo & Van Roy| (2014), value entropy search (MES) (Wang & Jegelka| 2017), joint entropy search
(JES) [Hvarfner et al.)
2022
Tu et al. 2022). GP-PIMS (Takeno et al. 2024), GP-EI (Mockus et al.
2019 and GP-EI using the maximum of the posterior mean (Wang & de Freitas, 1978 E (Berk et al.
2014 We denote the method of (Wang & de Freitas 2014) GP-EL-p"ma, We set the hyperparameters of GP-UCB, IRGP-UCB, and GP-EI-p to the theoretically derived parameters for the BCR analyses.
Therefore, we set 3, = 2 log( (/ 22 for GP-UCB and 4 = 2 log( (og()//// (2122)++ Ze with Z, ~ Exp(A = 1/2) for RRGP-UCB Takeno et al. 2023 Furthermore, we set 14 = 2 lo / + 1) for GP-EI-u mmx (see Theorem B.4. The number of MC samples in MES, JES, and E was set to 10. We employed random Fourier feature approximations (Rahimi & Rocht 2008) for the postcrior sampling in GP-EIMS, GP-TS, MES, JES, E and GP-PIMS.
Figures D and 2 show the simple regret and cumulative regret for the SE kernels. We measured optimization performance by the simple regret f(x") - f(t),, where &; = arg max (xx),, and the cumulative regret We report the mean and standard error over 16 random trials for the generation of the initial dataset, the synthetic functions, the observation noise, and the algorithm's 's randomness.
f
GP-UCB and GP-FI-nuax are consistently inferior to other methods. This is because the theoretical values of 3, and 74 are too large in practice. Indeed, IRGP-UCB, which uses Ç = O(log (1) instead of B, = @(log((x(()), shows better performance than GP-UCB and GP-EI-pmax, However, IRGP-UCB slightly deteriorates when f = 0.2, particularly for the cumulative regret, since So is still large for the objective function with 0.2 whose local optima are not so many. Note that if & becomes small, then the objective function has large variability and more local optima.
GP-TS and JES show superior performance when é 0.2. However, when é 0.1, GP-TS and JES often deteriorate for both simple and cumulative regret. This tendency has been reported to be caused by over- exploration Takeno et al.) 2023
2024 Shahriari et al. 2016
MES and 1 show superior performance in terms of cumulative regret, although their regret upper bounds have not been shown, as discussed Takeno et al. 2022) and See. 3. However, their simple regrets stagnate in the case of 0.2 and o 0.01, 0.1. Therefore, we can interpret that MES and E are slightly too exploitative in these experiments since showing the relatively low cumulative regret and large simple regret
9

---

Published in Transactions on Machine Learning Research (09/2025)
EIMS
E1-H maxt
IRGPUCB GPUCB
PIMS
MES
EI
-
TS
JES
GP (SE, 1=0.1, 0=0.01)
GP (SE, 0=0.01)
1.50
1.50
1.25
1.25
Simple Regret
1.00
1.00
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
0
50
100
150
200
0
50
100
150
200
Iteration
Iteration
GP (SE, 2= 0.1, 0=0.1)
GP (SE, == 0=0.1)
1.50
1.50
1.25
1.25
Simple Regret
1.00
1.00
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
0
50
100
150
200
50
100
150
200
Iteration
Iteration
GP (SE, 2 1. 0=1.0)
GP (SE. 8= 0.2, 0=1.0)
1.50
2.0
1.25
Simple Regret
1.5
1.00
0.75
1.0
0.50
0.5
0.25
0.0
0.00
0
100
200
300
400
0
100
200
300
400
Iteration
Iteration
Results of simple regret for synthetic functions generated from GP defined by the SE kernel. The top, middle, and bottom rows show the result for noise standard deviations The left and right columns show the result for length scales of the kernel É = 0.1 and f = 0.2, respectively, Daggers the legend indicate that the BO method was performed with theoretical settings, for example, regarding the hyperparameters.
Figure 1:
0.01, 0. and 1, respectively.
implies that the corresponding BO method repeatedly evaluates non-optimal points whose instantaneous regret. is low but not zero. On the other hand, it is known that GP-PIMS can be viewed MES using
10

---

Published in Transactions on Machine Learning Research (09/2025)
EIMS EI
E1-44 maxt
IRGPUCB GPUCB
PIMS
MES
-3- E31
TST
JES
x10
GP (SE, /=0.1, 0=0.01)
x102
GP (SE, / 0=0.01)
6.0
Cumulative Regret
6.0
4.0
4.0
2.0
2.0
0.0
0.0
50
100
150
200
0
50
100
150
200
Iteration
Iteration
x102
GP (SE, =00.1 0=0.1)
x102
GP (SE, =02., 0=0.1)
6.0
Cumulative Regret
6.0
4.0
4.0
2.0
2.0
0.0
0.0
50
100
150
200
50
100
150
200
Iteration
Iteration
x103
GP (SE, == 0=1.0)
x10
GP (SE, f= 0.2, 0=1.0)
1.5
1.2
Cumulative Regret
1.0
1.0
0.8
0.5
0.5
0.2
0.0
0.0
100
200
300
400
100
200
300
400
Iteration
Iteration
Figure Results of cumulative regret for synthetic functions generated from GP defined by the SE kernel. The top, middle, and bottom rows show the result for noise standard deviations 0.01, 0.1, and 1, respectively. The left and right columns show the result for length scales of the kernel f 0.1 and / 0.2, respectively. Daggers in the legend indicate that the BO method was performed with theoretical settings, for example, regarding the hyperparameters.
MC sample Takeno et al. 2024). Furthermore, GP-EIMS the same as E using one MC sample. Showing whether MES and FS1 have regret guarantees is important future work.
11

---

Published in Transactions on Machine Learning Research (09/2025)
GP-EI shows superior performance for the simple regret, although its regret analysis for 0 has not been shown. However, in the experiments for the cumulative regret, GP-FI clearly deteriorates compared with E MES, JES, GP-PIMS, and GP-EIMS, particularly for the case of é = 0.2. Since the noisy best observation yrn** tends to be large with larger noise e, we can expect that GP-EI tends to lean more towards exploration. Since uncertainty sampling that maximizes a(-1(a)) achieves the simple regret upper bound that converges to zero (Vakili et al. 2021a], is understandable that GP-EI shows superior performance for the simple regre D On the other hand, we conjecture that the deterioration of GP-EI for the cumulative regret is due to expr-exploration. Furthermore, we consider that since the objective function with L 0.1 has many local optima, the aggressive exploration by larger y!ax results in relatively better performance compared with that of (= 0.2.
GP-EIMS and GP-PIMS show superior performance consistently for both simple and cumulative regret, particularly compared with other theoretically guaranteed methods. Both GP-EIMS and GP-PIMS are based on the postcrior sample of gi and show similar results in these experiments, although GP-EIMS chooses a larger a (2x) compared with GP-PIMS, due to the formulation of the AF.
We performed the experiments for the Matérn kernels kaa (2r, (2r, = 2'-" (V2vll K2 (v 1/221l==21
T(p]
where r(.) and (.).) are the gamma function and the modified Bessel function, and several benchmark These experiments are shown in
functions from https: https://www.sff sfu. Appendix E In the experiments for the Matérn kernels, we observed a similar tendency to the experiments for the SE kernel. In the experiments for the benchmark functions, we confirmed that all BO methods perform well in most cases since we employed heuristic parameter settings for GP-UCB, IRGP-UCB, and GP-EI-pmax On the other hand, GP-TS, GP-PIMS, and GP-EIMS show good performance without heuristic tuning, and GP-PIMS and GP-EIMS exhibit superior or comparable performance to GP-TS.
6 Conclusion
The regret analyses of GP-El-based algorithms are fewer than those of theorelically established algorithms, such as GP-UCB and GP-TS, despite the fact that GP-El-based algorithms have been utilized in various applications. Existing analysis by Wang & de Frcitas (2014) requires incrcasing the postcrior variance in the actual algorithm, which can deteriorate the optimization performance. Therefore, we analyzed the posterior sampling-based based GP-FI algorithm called GP-EIMS, which does not require rescaling the posterior variance. We derived the sublinear BCR upper bounds of the GP-EIMS algorithm in the Bayesian setting, We demonstrated that GP-EIMS achieves at least comparable performance compared with other baseline methods, especially theoretically guaranteed Fl-based hothods, without sacrificing the theoretical guarantee.
Several future directions for this study exist. First, the posterior sampling for continuous X' or discrete X' with huge | requires some approximation, such as random Fourier features, in practice. Theoretical analysis incorporating such approximations (Mutny & Krausel 2018) is interesting. Second, since show only the BCR upper bounds, whether GP-EIMS (and GP-PIMS) achieves sublinear high-probability cumulative regret bounds is of interest. Third, recent studies (Scarlett 2018 Iwazaki 2025) imply that the standard GP-UCB achieves a near-optimal regret upper bound with high probability. Showing whether other BO methods, including GP-EIMS, achieve a near-optimal regret upper bound is vital, as discussed in Section 4 (Iwazaki 2025). Lastly, our analysis for GP-EIMS concentrates on the Bayesian setting. As with the analysis of GP-TS the frequentist setting (Chowdhury & Gopalan 2017 theoretical analysis in the frequentist setting is also intriguing.
Limitation and Future Work:
Broader Impact Statement
Our work focuses on theoretical aspects of machine learning methods, and we do not anticipate any negative societal impact.
2 Although Vakili et all 2021b: analyze the frequentist setting, their analysis immediately suggests simple regret upper bound in the Bayesian setting.
12

---

Published in Transactions on Machine Learning Research (09/2025)
Acknowledgments
This work was supported by JST ACT-X Grant Number (JPMJAX23CD and JPMJAX24C3), JST PRESTO Grant. Number (JPMJPR24J6), JST CREST (JPMJCR21D3 and JPMJCR22N2), JST Moonshot R&D (JPMJMS2033-05), MEXT Program: Data Creation and Utilization Type Material Research and Develop- ment Project (Grant No. JPMXPP122712807), JSPS KAKENHI Grant Number (JP21H03498, JP23K19967, JP23K16943, JP24K20847, and JP25K03182), and RIKEN Center for Advanced Intelligence Project.
References
Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Newral Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Sebastian Ament, Samuel Daulton, David Eriksson, Maximilian Balandat, and Fytan Bakshy. Unexpected improvements expected improvement for Baycsian optimization. In Advances in Neural Information Processing Systems, volune 36, pp. 20577 20612. Curran Associates, Inc., 2023.
Amrit Singh Bedi, Dhecraj Peddireddy, Vancet Aggarwal, Brian M. Sadler, and Alec Koppel. Regret and belief complexity trade-off in Gaussian process bandits via information thresholding. orXiv:2003.1055: 2022.
Julian Berk, Vu Nguyen, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Exploration enhanced expected improvement for Bayesian optimization. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD, pp. 621-637. Springer, 2019.
Felix Berkenkamp, Andreas Krause, and Angela P Schoellig, Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Machine Learning, 112(10):3713 3747, 2023.
Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on Bayesian optimization of expensive cost func- tions, with application to active user modeling and hierarchical reinforcement learning. arXiv. 1012. 2010.
Adam Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 844 853, 2017.
Michael T. M. Emmerich, André H. Deutz, and Jan Willem Klinkenberg. Hypervolume-based expected improvement: Monotonicity properties and exact computation. In 2011 IEEE Congress of Evolutionary Computation (CEC), pp. 2147-2154, 2011.
Shi Fu, Fengxiang He, Xinmei Tian, and Dacheng Tao. Convergence of Bayesian bilevel optimization. In The Twelfth International Conference Learning Representations, 2024.
Jacob Gardnor, Matt Kusner, Zhixiang, Kilian Weinberger, and John Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pp. 937 945. PMLR, 2014.
Armengol Gasull and Frederic Utzet. Approximating mills ratio. Journal of Mathematical Analysis and Applications, 420()):1832-1185))) 1853, 2014.
Michael A. Gelbart, Jasper Snoek, and Ryan P. Adams. Bayesian optimization with unknown constraints. In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, pp. 250 259. AUAI Press, 2014.
Subhashis Ghosal and Anindya Roy. Posterior consistency of Gaussian process prior for nonparametric binary regression. The Annals of Statisties, 34(5):2413 2429, 2006.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Antoine Grosnit, Rasul Tutunov, Alexandre Max Maraval, Ryan-Rhys Griffiths, Alexander I. Cowen- Rivers, Lin Yang, Lin Zhu, Wenlong Lyu, Zhitang Chen, Jun Wang, Jan Peters, and Haitham Bou- Ammar. High-dimensional Bayesian optimisation with variational autoencoders and deep metric learning. arXiv:2106. 03609, 2021.
Steffen Grünewälder, Jean Yves Audibert, Manfred Opper, and John Shawe Taylor. Regret bounds for Gaussian process bandit problems. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 273-280. PMLR, 2010.
Shouri Hu, Haowei Wang, Zhongxiang Dai, Bryan Kian Hsiang Low, and Szu Hui Ng. Adjusted expected improvement for cumulative regret minimization in noisy Bayesian optimization. Journal of Machine Learning Research, 26(46):1 1:36):)33:33000 2025.
Deng Huang, Theodore T. Allen, William I. Notz, and Richard A. Miler. Sequential kriging optimization using multiple-fidelity evaluations. Struclural and Mullidisciplinary Oplimizalion, 32(5):369-333)) 2006.
Hisham Husain, Vu Nguyen, and Anton van den Hengel. Distributionally robust Bayesian optimization with y-divergences. In Advances in Neural Information Processing Systems, volume 36, pp. 20133-20 20145. Curran Associates, Inc., 2023.
Carl Hvarfner, Frank Hutter, and Luigi Nardi. Joint entropy search for maximally-inforeed Bayesian opti- mization. In Advances in Neural Information Processing Systems 35, pp. 11494 11506. Curran Associates, Inc., 2022.
Shogo Iwazaki. Improved regret bounds for Gaussian process upper confidence bound in Bayesian optimiza- tion. In Advonces in Neural Information Processing Systems 38, 2025. 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 41st International Conference on Machine Learning, Proccedings of Machine Learning Research. PMLR, 2025. To appear.
Won Mee Jang. A simple upper bound of the Gaussian Q-function with closed-form error bound. IEEE Communications Letters, 15(2):157-159, 2011.
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 of Proceedings of Machine Learning Research, pp. 2486 2495, 2020.
Donald R. Jones. A taxonomy of global optimization methods based on response surfaces. Journal of global oplimization, 21:345-388 383, 2001.
Donald R. Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimizalion, 13:455-499 492, 1998.
Kirthevasan Kandasamy, Gautam Dasarathy, Junier B. Oliva, Jeff Schneider, and Barnabas Póczos. Gaussian process bandit optimisation with multi-fidelity evaluations. In Advances in Neural Information Processing Systems 29, pp. 1000 1008. Curran Associates, Inc., 2016.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schncider, and Barnabas Póczos. Parallelised Bayesian optimisation via Thompson sampling. Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Reseorch, pp. 133-142, 2018
Harold J. Kushner. A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering, 86(1):97-106, 1964.
Benjamin Letham, Brian Karrer, Guilherme Otioni, and Eytan Bakshy. Constrained Bayesian optimization with noisy experiments. Bayesian Anal., 14(2):495-50) 519, 2019.
Daniel James Lizotte. Practical Bayesian optimization. PhD thesis, University of Alberta, 2008
14

---

Published in Transactions on Machine Learning Research (09/2025)
Godeliva. Petrina Marisu and Chi Seng Pun. Bayesian estimation and optimization for learning sequential regularized portfolios. STAM Journal on Financial Mathemalics, 14(1):127-15) 2023.
Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of Bayesian methods for seeking the extremum. Towards Global Optimization, 2(117-129):2, 1978.
Mojmir Mutny and Andreas Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. Advances in Neural Information Processing Systems 31, pp. 9005-900 9016, 2018.
Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. In Asian conference on machine learning, pp. 279- 294. PMLR, 2017.
Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Filtering Bayesian optimization approach in weakly specified search space. Knowledge and Information Systems, 60:385 413, 2019.
Biswajit Paria, Kirthevasan Kandasamy, and Barnabés Póczos. A flexible framework for multi-objective Bayesian optimization using random scalarivations. In Proceedings of The 35th Uncertainly in Arlificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp.
2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Newral Information Processing Systems 20, pp. 1177 1184. Curran Associates, Inc., 2008.
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( ():1121 1243, 2014.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Operations Research, 66(1):230 252, 2018.
Jonathan Scarlett. Tight regret bounds for Bayesian optimization in one dimension. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp.
PMLR, 2018.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando De Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148 175, 2016.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems 25, pp. 2951 2959. Curran Associates,
Inc., 2012.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, pp. 1015-10222 Omnipress, 2010.
Shion Takeno, Tomoyuki Tamura, Kazuki Shitara, and Masayuki Karasuyama. Sequential and parallel constrained max-value entropy search via information lower bound. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 20960 20986, 2022.
Shion Takeno, Yu Inatsu, and Masayuki Karasuyama. Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 33490 33515. PMLR, 2023.
Shion Takeno, Yu Inatsu, Masayuki Karasuyama, and Ichiro Takeuchi. Posterior sampling-bass based Bayesian optimization with tighter Bayesian regret bounds. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 47510-47534. PMLR, 2024.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Hung The, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Regret bounds for expected improvement algorithms in Gaussian process bandit optimization. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 7715-8737. PMLR, 2022.
Ben Tu, Axel Gandy, Nikolas Kantas, and Behrang Shafei. Joint entropy search for multi-objective bayesian optimization. In Advances in Neural Information Processing Systems 35, pp. 9922-9938. Curran Asso- ciates, Inc., 2022.
Tsuyoshi Ueno, Trevor David Rhone, Zhufeng Hou, Teruyasu Mizoguchi, and Koji Tsuda. COMBO: An efficient Bayesian optimization library for materials science. Materials discovery, 4:18-21, 2016.
Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shin. Optimal order simple regret for Gaussian process bandits. In Adeances Newral Information Processing Systems, volume 34, pp. 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 of Proceedings of Machine Learning Rescarch, pp. 82-90, 2021b.
Emmanuel Vazquez and Julien Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. Journal of Statistical Planning and Inference, 140(11):3088 3095, 2010.
Jingyi Wang, Haowei Wang, Nai- Yuan Chiang, and Cosmin G. Petra. On the convergence rate of noisy Bayesian optimization with expected improvement. arXiv:2501.000 00262, 2025.
Zi Wang and Stefanie Jegelka. Max-value entropy search for elficient Bayesian oplimization. In Proceedings of the 94th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3627 3635, 2017.
Ziyu Wang and Nando de Freitas. Theoretical analysis of Bayesian optimisation with unknown Gaussian process hyper-parameters. arXiv:1406. 7758, 2014.
Han Zhou, Xingchen Ma, and Matthew B Blaschko. A corrected expected improvement acquisition function under noisy observations. Proceedings of the 15th Asian Conference on Machine Learning, volume 222 Proceedings of Machine Learning Research, pp. 1747 1762, PMLR, 2024.
A Technical Issue in (Nguyen et al., 2017)
A counter-example against Lemina in (Nguyen et al. 2017) can be made easily. Let us consider the BO algorithm that always evaluates the same point; that is, l X, E [T], = æ. Then, choosing an input z such that k( k( /kx,, m) 2 C with some strictly positive constant C, (m) 2 k(@, x) - k(x, / x) 2 C for / E (T). Therefore, Σi (f( CT = ((T), which contradicts Lemma in Nguyen al. 2017).
confirm
Note that if Lemma 7 in Nguyen et al.) 2017) is true, any BO algorithm achieves the converged simple regret upper bound in some settings. Suppose that I _ (a) O(vr) for all X holds. Assume is finite and Br is set that for all X, [p)(#) f()) < 83 or (a:) with high probability (for example,
16

---

Published in Transactions on Machine Learning Research (09/2025)
in Srinivas et al. 2010 Then, the following holds with high probability:
f(x') - f(OT) $ pr (x") + B7 "r((x")) - (T((T) + / (dr)
(32)
$ 2 or (
(33)
T
< 7 2BT Σ (क+)
(because Vo E X, Vi E [T], 2 σT
(34)
(V BT
False
o
o
(35)
T
where Ør = arg max (C)), är == max This result suggests that (if the equality shown
a8
is true) the simple regret upper bound converges to 0 when 3r o(T) regardless of the BO algorithm. For example, Br = o()) holds for SE and Matérn kernels. This result is obviously strange.
False
B Regret Upper Bounds for GP-EI with Rescaling of Posterior Variance
This section shows the regret upper bounds for GP-EI with rescaling of the posterior variance in the Bayesian setting. The derivation of the regret upper bounds comes mainly from (Wang & de Freitas 2014) and can be applied to the freguentist setting almost the same way. For more details on the frequentist setting, we discuss in Appendix B.4 We denote the cumulative regret Rr Etz f(x") f(x)).
B.1 Auxiliary Lemmas
First, to generalize the analysis of (Wang & de Freitas 2014 we provide the two lemmas modified slightly from (Wang & de Freitas 2014).
Lemma B.1 (Modified from Lemma 9 of (Wang & de Freitas
2014)).
Pick X and t [T]. Suppose
that a E I satisfies the following inequality holds with some 3 > 0:
1--1-1(a))) S 82 0z (2x)
(36)
Then, the following holds with b E I and 0:
max ((c
7( 7(-81/2/ /v212)
(a (a- -1//2 8//20/0 (x))
(a (a-b)+ b)+
(37)
T/8,12//1 /v2/2)
< v 11/20-1120)) (2-1((x)= bb)
= El(Mu- (1(lu-1(20 (2t), 11/2 (1120=-((2).b
(38)
01/20,11(0)
$ (a - b)+ + (B/ 12 (0.1((1))
(39)
where (.)+ max (..)).
Proof. If ( = O, then a == (-)(w) and FT( 1 (a-b)) Therefore, the inequal- ities are trivial (Note that 7(-) is monotonically increasing function). Thus, we assume that r--1( > 0 hereafter. Furthermore, define the variables 9 and follows:
a
Pt- (x) b
(40)
1
1 (x:
First,, derive the upper bound. From the definition,
EI (x)), 1/2 02 (x)). b) = 11122
( u
(41)
w1/2
17

---

Published in Transactions on Machine Learning Research (09/2025)
From the assumption, | ol B. Since 7(-) is monotonically increasing and 7(c) e for 0, we obtain
(g)+ + 8//2
El (
(z), v2/2 02)1), < 0,-12111)
(42)
u1/2
(4)+ + 8/12
12/2 (
+1)
(43)
v112
- (a b)+ + (0)/ 12 + 1012))00-1(24
(44)
Next, we derive the lower bound. If (a - b)+ = 0, then the lower bound is trivial since the GP-EI acquisition function non-negative. Therefore, assume (a - b)+ > 0. Since r(.) is monotonically increasing, we can see that
9- 4-3/// 31/2
Bl( 01/201
2 u 1/2 120)7
(because - S u)
(45)
v2/2
9- /--1//2
2 1/2 01120:=11(2))
(because =c 2 2c)
(46)
w2/2
(a-b)) 8///2 0(-)((x).
(47)
Furthermore, since T(-) monotonically increasing,
EI( u 01- o( 01220-1((0)) Me-1 (2x) a +
(48)
v1120,,11 (x)
Ne_ (1-1(x)) a
2 1/2 (0))
(because a > 0 from assumption)
11/20
(49)
-3/122
2 1/120 12))
(because (t-1(z) - a -3,/2 0,
1112
(50)
[l(m)-10))ut122 (2 (1m).b)
Hence,
we obtain
(
By substuting this inequality to
w1/27 (-8. -/112/1113)
EI( v 12) 2 (a b)+ 3/ 11)011(x)) we can that
1/2 -331/3 //112)
(1(H41122),11 (z)) (
(a (c-b). b)+
(51)
07 + 11/27 (-1//2/ /w1/2///)))
12/27
///12/1///
(a= b)+
(52)
w1/27 ////2 /v212)
Lemma B.2 (Modified from Lemma 10 of (aag & de Freitas 2014 ). Assume the kernel function
k(x, x²) & 1 for all xx x' E X. Let at = arg w El( w 0 (x)) b) with min (t-1(x) S b S
max Pe-1(a)) (x) and some v > 0. Then, the following inequality holds:
b - 1x-1( S Vlog(t 1 o2) log(o?)v>/12 (2
(53)
18

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. If b S (x-1(x)),, then the inequality is trivial. Thus, assume b (e-1(x)) hereafter. From the assumption of b, there exists 2 E X such that (4-12z) b. Therefore, we obtain
w² 01-1 (0) - 1/2 01-1(2)) (1-1
(54)
111200(1(2))
El( (2), 1 1/2 0,- (2), b) E1 (2t), v 1//2 o (2zz); b) [4-1 (a++)
(55)
(56)
w² 0 (2))T
(57)
v1/20,-1(xz))
Then, since we assume > 1 and r(0) = v= we can arrange the incquality as follows:
(-)
(x=) -
2t
Oc-
(2:)6
(11201-1(00)) (x1)
(because 7(c) <c() for << 0)
(58)
14_
(2x) (1t)
2
exp
(59)
2
12122 011221111220 (x:)
Hence, by applying the logarithm, we can see that
(x)))
(10) - 11 s V 22log log
v 1/2 (2:1
(60)
(z)
( o2-1(z)
flog
y 1/2 101))
(61)
We know that, for all E X, the posterior variance is bounded as 0²/(0² +t S (2) S from Lemma D.1 and monotone decreasing property of the posterior variance. By substituting ( S 1 and
o² 0²/(02 +1 1) S of-1(2), we obtain the desired result.
B.2 Regret Bounds for GP-EI with Maximum Posterior Mean
In this section, although (Wang de Freitas 2014) use the parameters {1e121 scale the posterior variance, use (8)) instead of (re for simplicity. We believe that this modification does not affect the essential order of the resulting regret upper bound.
Theorem B.3. Let f GP(O, k), where the kernel function k is normalized k(æ, x) S 1. Pick 8 E (0, 1).
Assume X is finile set or Assumplion 2.1
holds.
(i) When X is finite set, set Br( (0:0)==logg))) 22lo((1
(it When Assumption 2.1 holds, set (6(6) (:00)=2100)) 2022 + 2d 2d (lodrt² /log(Aad//0)) + +1).
If a, arg max EI ( // ( (z), ) where p max Mt- (2:), then the curullatvve regret is bounded from above with probability at least 8 as follows:
RT = 0 (
(62)
Proof. First, we provide the proof regarding case (i). In this case, from Lemma 5.1 of Srinivas et al. 2010 the following holds:
Pr Vv X [T] 81 21 2188
(63)
19

---

Published in Transactions on Machine Learning Research (09/2025)
Therefore, we assume [f(x) (x)1 S Be (/ (0) (a) holds for all æ E X and I [T] hereafter. We can see that the instantaneous regret r, be bounded follows:
r f(x") f(x))
(64)
f(x') ) -Pi-1 pi- f(x)))
(65)
Ix(x") + m 14-1 + ( (6)0t_1()))
(66)
where [x)x)) = (f(z) 11
Regarding the term (x(),, using Lemma B.1 with f(x"), b p1-1
and Bc),, we see that
1((x') S (2
(2))) C) /2 (-) (
(67)
(because æ, is the maximizer)
(68)
r(1) where C3 7[-1)- Moreover, by applying Lemma B.1 again with (4-1( b = 14-11 and 3e(8).
we can obtain
4(x0)) C3 (1))) + + 20)
(69)
< 20 // (0))
(because 11-1 > (4-1(2)))
(70)
Furthermore, the term Pi-1 Pr- (a:) is bounded from above by Lemma B.2
max ( s Vlog(t - + o²) - log log(o>))) (1)=,.aa))
(71)
Hence, aggregating the results, we can obtain
rs (2Cs + Vlog(1 1 log +1) 87 (1)
(72)
Then, the cumulative regret can be bounded from above as follows:
Ry =
(73)
Σ 2C's Vlo((t 1+
- 1) -og(o))
(8))(()))_)(z))
(74)
$ (20s + o +1)
Σ
1/2 2 (5)0)-1(Z11)
(75)
T
T
200 + Vlgg(T -1 10g +1)
Σ
(,(5) Σ of (x,,)
(76)
x 20's + Iog(TT - 1+ -logo)) + 1) v CTT33
(77)
In the second last and last. inequalities, we use Cauchy Schwarz inequality and the inequality ET (x)) & Cirr (Srinivas et al. 2010).
For the case (ii), we consider a finite set X, with each dimension evenly divided by Te = bdrrt / (og(()d/))
such that X ने. In addition, we denote [x]e arg min || - æ'I11- For this X, using the union bound and Lemmas 5.5, 5.6, and 5.7 of (Srinivas et al. 2010), the following events simultancously hold with probability least. 1-8.
W E [T], sup If(x) f((x).) F =Et
(78)
Vt E Va E X X
s // -M-
(8))(()))_)()))
(79)
20

---

Published in Transactions on Machine Learning Research (09/2025)
[1X1+)))²2) Note that +1 in |&g] + required to guarantee the confidence bound on 36
since 3((6) 2 2 log
dt.- Therefore, we assume the above two events hold hereafler.
Since the above two events hold, the instantaneous regret can be bounded as
[(x") [(xx)
(80)
= fxx") - [[xx'())) + 1((x0)))) - Mi-1 + 16-1 - ((x))
(81)
- + (f([x*))) - -1-1) + + 14-1 14-1((1)) + 2 (6)
(82)
As with the case (i); using Lemma B.1 at [a=) with a = [((xx')) b b= 11-11 and v = B,(d), we see that
(f((z")) + I C3El (M I.), (6) (6)0 ((x")))), (1)
(83)
S < (1 (z.). 0/ ( (0)0, (x+4), 11-1).
(because æ, is the maximizer)
(84)
Morcover, using Lemma. B.1 again at with 14-11 (x))) 11-11 and (,(6), we can obtain
f(x01)) max S C3 (14-1(11)) - 11 + 22 (1)
(85)
s 20 12 (8)0)-1(21).
(86)
Futhermore, using Lemma B.2
max Pt- 1 (ax)) & Vlg(l - 1 + o²) ())((2)))) (0)
(87)
In addition, Σt= 1/12 S 7 Therefore, repeating the same proof as case (i), we obtain
Rr S n² + (2Cs + Vlog(T - 1+ 0²) - log(o?) +1) VCTT3r(0m. 6
(88)
Thcorem B.4. Let GP(O, k), where the kernel function k is normalized as k(x,x) S 1. Assume X is a finite set or Assumption 2.1 holds.
(i) When X' is a finite set, set Br = log (1x)12/ 11.
(it) When Assumption 2.1 holds, set 3r 2d ((bdrt (vllt(a//ogaad)) + vT/2)]] + 2log(t /V2T + 1).
If Dz = arg x (1)-) 2//2 (x), (())) where p bounded from above as follows:
maX&ex Pt-1 then the BCR is
BCR = (V
(89)
Proof. First, consider the case (i).
BCR B[f(x") f(x;))
(90)
T
[[((z*) )- Uz(x") + ++(x** - pma + - [x-1(
(91)
<
E f(xx)) U+(x*) + (Ui(x") - ) + + yumax - ph- (20)
(92)
1=1
[ff(x") - Ux(2')) +
E (U.(x") p
E 1 1
(93)
21

---

Published in Transactions on Machine Learning Research (09/2025)
where U,(xt) (z) + 3.5² (a)) Then, from the same proof Theorem B.1 of (Takeno et al. 2023
Ei= - - 7²/6. Note that B > 0 due to the ceil function.
Regarding the term (U,( m we can apply Lemma B.1 x² with Uz(x"), b 14-11 and B. Therefore,
(Uz(x*)) -2=1( 2 C3El |h- (x"), 81/2 r 0 1
(94)
I C3El (x-1( B3. 3,.2 ( 11
(95)
r(1) where C3 = -[-1] Moreover, using Lemma B.1 at i with a = ( b = p-111 and v = Be, we obtain
(U+(=") ( C3 (1L)1( ( 021102001(1x1)) 2C0 0
(96)
Furthermore, regarding " p4 (1:4); using Lemma. B.2
p (x:) S Vlog(t 1+ o2) log(o²))3 ///2 1
(97)
Hence, the sum of these terms can be bounded from above as with the proofs of Theorem
B.3
E (U.(x0)) - ( + Σ p (=-1(xx)] (2C3 + Vlog(T' 1 0²) 1og(o2)++
+ 1) VCTBTT..
(98)
Consequently, we obtain the following upper bound:
BCRT S n² + (2C's Vlog(T 1 o²) log(o>)++ + VCIT8mT.
(99)
6
Next, for the case (ii),
T
BCRT
E [[f(x') - f(x1))
(100)
E [f(x)) f((x'))) + f((x')) Ue((="1)) + Ux((x))) - 1. + + ---1(x))),
(101)
1=1
$
Σ
E [[f(x') [((x=1]))) + Σ E [f([x*)) U.('))))))
(102)
1=1
E (U.((="))) p +
E max (x-1(x))]
(103)
where =1(x)= (z) + 33/22 1
We consider a finite set X₁ with each dimension evenly divided by [odrt? (Viog(ad) + v such that [x]] Tf. In addition, denote [æ]e arg min || æ'1l. [|I Then, with the proof of Theorem B.1 of Taaeeno et al. 2023) we can obtain
T E [f(x")) -[([<=)))]
(104)
6'
2
E [ff([="))) - U.(((x")e))
(105)
22

---

Published in Transactions on Machine Learning Research (09/2025)
As with the case (i); using Lemma B.1 at (x"), with Ui([x")),, b p and St, we see that
(U+((==))) - 11 x C3 (Me- ((x))),, 11, 3/1/ oz
[1,"))),,
(106)
CgEI(M) B, o 1 1
(æ, is the maximizer)
(107)
Moreover, using Lemma
B.1 again at 24 with 14-1 (2)), b pi-1 and Be, can obtain
(Ui([>*)) max + S <C3 (1)) - 11-1) + 23. o, )
(108)
20 21/2 0
(109)
Futhermore, using Lemma. B.2
max [4
Pt- (x4)
v log(1 - 1 + o²) log( oz (zt)
(110)
Therefore, repeating the same proof as Theorem B.3
we obtain
1+ 12) BCRT S 3 + (20s - 1og((=)+
x²
VCTTBTT.
(111)
B.3 Regret Bounds for GP-EI with Maximum Posterior Mean among Evaluated Points
First, show variant of Theorem B.3 where the reference value is changed to اا maxxatt11 Mr-1 (m:):
Theorem B.5. Let f GP(O, k), where the kernel function normalized k( x) s Pick 8 e (0, 1).
Assume X is a finite set or Assumption 2. holds.
(i) When X is a finite set, set (,(5) (()]))=2og((()1111 (112((((1177
(ti) When Assumption 2.1 holds, set B(( = 2 (( (35)) + 2d
([bdrt² Vlog(Add// + +t)
If æt arg max xxX Bl (I( (0) 1 where أ maxte[111 ( for 1 2 and
pmax = 0 for i = 1, then the cumulattove regret is bounded from above with probability at least 1 8 as follows
RT = (v
(112)
Proof. As with the proof of Theorem
B.3 we can guarantee the following events with probability at least
Ve E (f(x))))) - p1 --1((=)1 S // ())
(113)
for the case (i), and
14 E [T], sup [fx)) f((x){] S Tz
(114)
Vt E [T). Ve E X (z. [(x) - s 8. (0)))-1())
(115)
(116)
for the case (ii). Note that, in the case (ii), we additionally consider the bounds on {=; not only øe. (1 +
compared with the proof Theorem B.3 In the remainder the proof, we assume the above events hold in each case.
using (e(6) = log
34
23

---

Published in Transactions on Machine Learning Research (09/2025)
By almost the same proof as Theorem B.3. in which set f(x;) for second application of Lemma B.1 we can obtain
r2 S Car)(an)) + (2Cs + Vlog(1 - 1 o2) -ogg)) + 1) 31 (6)
for the case (i); (117)
- 1
12 Cali(zi)+ + (20s + vlog(t 1 02) 1og( 1) (0)o for the case (ii);
(118)
where [((x,) = (f(x1) p=0+ and C3 x(1)
+(-1)- Thus, the cumulative regret is bounded from above as
follows:
T
Rr S C3 Σ
[((x))) + (20'+ Vlog(T + + 1og((2)) +1) VCTT3r(0m. for the case (i),
1=1
(119)
T
n² Rr S + +ss Σ
[((x)) + (2Css +
VCTTBr(0hx, for the case (ii).
(120)
Next, obtain the upper bound of Σi= (ax))) by the proof modified slightly from Tran- The et al.
2022
Hu et al. 2025 First, we can see that
(a))) < (J(x1) - 0)+ S 2/. (6),
(121)
where we use the inequality [f(x))] S // ( [k(11,11) S (5) for both cases (1) and (ii). Then, define an
indices M = {ma()) Imis) (zm(s)) ) > 0, m()) > 1} with ascending order m(1) < <... < m mMM), where M = [MM.
In addition, let m(0) m1) 1 2 1. If M we can easily show Σ Ie(x,) (2x) 2// On
the other hand, for the case of M > 1, we can obtain
M
Σ (x.)) = Σ ((m(()) - A muax 1=2
(m(()-11
(122)
1=1
(arm(()) - Mm(())) (1
(because Definition of pT)))) (123)
1=1
Σ ((Fm(()) ((0m((111 + 2212 (0)m))0000mmmmmmmmmm))
(124)
M
< ((mm(r))) - -((
Σ
8 81/2 ( (0)
(125)
m(t)
1=1
T
223312200 +2+
31 (0)))
(126)
1=1
< <23 + +2+ (CTTBr
(127)
where we use
in the second incquality it is guaranteed that Vt E Va Va E X. xf1)((x) ---1(x)) < (2) for the
case (i), and VL [T], Va X, (a.)) (m=) s / (8)0 (a:) for the case (ii) from the assumption;
the third inequality, a (1 S 1
in the fourth inequality, for all x E X, [f(x) & // for the case (i), and [f(x)) $ [[(
s())))) < 8122 for the case (ii) from the assumption.
24

---

Published in Transactions on Machine Learning Research (09/2025)
0l which concludes the proof. 0 Theorem B.6. Let GP k), where the kernel function k is normalized k(xxx) S 1. Assume X' is finite set Assumption 2.1 holds.
Consequently, Ei= [ax) 2 -
(i) When X' is a finâte set, set Be 2lo (121)////2)) 1).
(8) When Assumption 2.1 holds, set Br - 2d bedrl (log(ad)) + v + 2 log(( /v22 + 1).
If arg x El ( (m), 8./2 - "T where p max for 1 1 and joxx
0 for t = 1, then the BCR is bounded from above as follows:
BCRT = 00 (VBrnTlogT)
(128)
Proof. By the same proof Theorem B.4 for both cases (i) and (ii), can see that
T
E [e(()))) + (v BrrrTllogT
BCRT = C3
(129)
t=1
where [xx)) = (f(z) 1-1) and C3 7(1)/(--1). Therefore, we here consider the upper bound of Σtm B[)((=))]
First, we can obtain
= =B[([(=)) ,] = 20(0)) k( x1) S <VT
(130)
f(x;) ~ (0, k(xz) .)). Then, define indices M {m(i) Imm()) (z)(()) ()) > m(1) > 1} with ascending
order m(1) < m(M), where M = [M]. In addition, let m(0) m(1) - 12 If M = 0, easily
show Et [xx))) (x1) S V 3.3 Thus, we consider the case of M 2 For any M under M 1, we can
obtain
T
M
Σ ((x))) = Σ
max [ (x mm(())-1
(131)
2
M
< (xm((() (mm()) (20m())1)))
(132)
+ (( -
Σ
(2()(( +/2/2 (ntti--))) B -
(133)
M
M
$ f(#m)())) - (I +
Σ f( - U Um(s) (2m((-)))
+
m(j) σ mm(i m 1)) (134)
M
T
< max f(x) min f(x) + mex
Σ (f( - Umii) (m)))(2m((-)))
+
8
1/2
)
(135)
xex
1=1
< max f(x)
min f(x) + Σ> - +
Σ
s (
(136)
xex
(=2
1=1
where U.(x:) /4-
(m- (z) 12 (x)) In the above transformation;
in the first inequality, we the definition of max
25

---

Published in Transactions on Machine Learning Research (09/2025)
in the second inequality, mm())) 1 (#m(i-1)) S 0m(i- (
From Lemma D.2
E
max (ax)
min (x) =EX
< 2 2 2og( + 2,
for the case (i); (137)
æEA
E
max
[(:)
min ((x)
5 22 lo (Ibdr(log(ad) + vT/22]] 2 2 log + 2,
for the case (ii). (138)
.EA
In addition, as with the proof of Theorem B.1 of "Takeno et al. 2023
can obtain
E
Σ Σ -0,))-U(0)))))
(139)
1=
(140)
$ 1 1+ +oggT
(141)
Furthermore, we know that Ets ((1(()) 1
VC Consequently,
we can observe
ΣT [[(((x)) O(VC
B.4 Discussion on Modification to Frequentist Setting
We focus on the analysis the Bayesian selting. However, our proof approach for finile input domains can apply to the frequentist. setting since, in general, (i) supwex [xx) S B with some constant B from the assumption and (ii) the confidence bounds for f hold for all E X even if X an infinite input domain (for example, Srinivas et al.) 2010 Chowdhury & Gopalan 2017). Therefore, since 3r is set
(((r)) to make confidnce bounds in the frequntist setting, our suggosts that GP-EI with ju 1/2 achieves MVBBTTT T) = O(TryTlog" cumulative regrel upper bound with high probability without any other modification to the GP-El algorithm like (Hu et al. 2025). To our knowledge, this has not been revealed by the existing studies.
suggests
Note that, in the frequentist setting, extension to the expected regrel upper bound from the high- probability regret bound is trivial under some conditions, such as sup f(x <. B and inf f(x) > -B, which is assumed in most existing studies (for example, Srinivas et al. 2010 Chowdhury & Gopalan 2017). If we obtain the high probability regret upper bound as Ry Olg(T log( (gg1/)) 1/))) with some increasing sublinear function g(T) = (TT/log(T)) by setting 8 = 1/T, we see that
E Rr] S g(T) log(1 + 8
Σ f(x') f(xx) S
+ 2B,
(142)
1=1
which is sublincar. Similar derivation is often performed in the literature of the bandit algorithms, for example, discussed in Abbasi-yadkori et al. 2011
C Proofs for GP-EIMS
Here, show the proofs of the main paper's theorems, lemmas, and corollaries. Our proof flow is summarized follows. First, from Lemma 4.1
see that
T E 1n 2
BCR S
Σ
26

---

Published in Transactions on Machine Learning Research (09/2025)
Then, for the case of ||| which is shown by Lemmas 4.2 and 4.4
show the upper bound of E [m] 2 0} Ollog in Corollary 4.5
Therefore, combining Lemma 4. and Corollary 4.5 can obtain
the sublinear BCR upper bound of (vTTTr log I") as in Theorem 4.6 For the case that Assumption 2.1
holds, by adapting the credible interval obtained in Lemma 4.7 a similar proof derives the BCR upper bound of V log T) as in Theorem 4.8
C.1 Proof of Lemma
Lemma 4.1
Let
(xtt)
T)
(143)
0
0
Then, the BCR incurred by GP-EIMS can be bounded from above as follows:
T iine 2 0} VGr.
BCR S
E
(144)
where C1 = 2/ log(1 2) and the indicator function 1(m 0) = 1 if ne 2 0, and 0 otherwise.
Proof. From the tower property and linearity of expectation, we obtain
T Bif(x*) f(x))
BCR
(145)
T
Σ E [ff(x") )) gt + tt fxx))
(146)
T
Ep,,, E, [f(x*) 9.1 + E. lot - f(xx))
(147)
ED,,.
E, [gt f(x)
(148)
(8)
[g]
(x,1(
(149)
For the equality (a), the fact [.f((=*]] E.ggi] since f(x") Di-1 and of D,-1 are identically distributed. For the equality (b), use the tower property of expectation and [x]f(x;)] Ee|ue- (x:)). which holds since æ defined via Si and f are independent. Then, we define the random variable as follows:
Oi 14- (2)))
7)
(150)
0
Therefore, since (x)) > 0 due to o² 0, obtain
BCR, Σ E (m
(151)
27

---

Published in Transactions on Machine Learning Research (09/2025)
Furthermore, from the lincarity of expectation, we that
BCRT = E
Σ ((0))
(152)
E
Th nT 2 -00))1((01)
(because (x=) > 0)
(153)
T
E
fm 2 0}
Σ t=1
o7 (20))
(because of Cauchy Schwarz inequality
(154)
1=1
T
E
Σ
TE {m 20
VinT,
(155)
E
ne Lm 0}
VOnT..
(because of Jensen's inequality)
(156)
where C1 == 2/ log(1 + 2) and the indicator function 1/ - if n > 0, and 0 otherwise. For the third inequality, use Ein (xt) S CI77 (Lemma 5.2 in Srinivas et al. 2010
C.2
Proof of Lemma 4.2
Lemma 4.2
Fix B 0 and U < maxxex ( + (12 Then, the following inequality holds:
Suppose that k(x S 1 for all x E X.
- (x0) S
0² 022
log
+ B + 3
(157)
(
02
where xe arg m El(p)-1(x) 01-1 (1))
Proof. Let z E be the input that satisfies U < (z-((z) + 0//22,1-11 12)); that )-p(-1()) S B1/2. Tf
U S (t)) it is obvious due to (- d.-1(#,) < O. Thus, assume U > (x; hereafter. Then, from the assumption and the monotonic increasing property of T(c) = c$(c) + ((c),
E((u-1(2),0 o())) (M-1(2)) - U
(158)
02-1(2)
(z
(159)
In addition, due to the definition of æı, we see that
(E) < El(u-1 (2:). o.- (2x).
(160)
Therefore, we obtain that
(=(2)7(-3113) < EI( or (2x)) U)
(161)
(1-1(2))
U
= =
(162)
01-1 (x:)
From the assumption U (=-1(x:), can that (()))-t < 0. Then, since 7(c) S d(c) if 0, we further obtain
0(-1
((-1(x)) - U 01-1 (x+)
(=33)(-))113 < (
(163)
(x-1(x))
(M-1 U)2 20 207_1(01)
exp
(164)
2
28

---

Published in Transactions on Machine Learning Research (09/2025)
Hence, by transforming and applying the logarithm and the square root, we obtain that
1
(x-)((x)) - Ul - 2 (2 (
(165)
Due to the monotonicity of o, (x) 2 0x(2)) and the assumption of k(xxx) & 1, we see that oc-1(x:)) S 1. In addition, from Lemma D.1 1 2 -41-11 Therefore,
(v log
0 + 2og (T(-B1/2) - l2g( oz 1
( - Ul
(166)
0²
Then, for T(-3//2), we can bound as follows:
T(-B1/2) = --1122 + ((-B112)
(167)
= -B1/2 (1 (1- (131(1))2) ((B1122
(168)
2 2-(1-o8p) (-12 (322) 0(B1/3) $(31/2)
(169)
T 2/311 6(B112) (-V
= exp
(170)
where we use Lemma 4.3 Thus, obtain
2log (T(-3112)) S S-2
π g//2 - log /2T 8
(171)
2
=V + log(2x) + 3.
(172)
By combining the results, we obtain the desired result.
C.3 Proofs for Sec. 4.2.1
First, we show the proof of the following corollary:
Corollary 4.5. Assume the same condition as Lemma 4-4 Suppose that k(æ, a)) S for all x E X.
Then, by running GP-EIMS, the following inequality holds with probability least 1 8:
T) S log (02+ ( + (()) + 2m3((),
(173)
g²
where B(8) = log( Furthermore, we obtain
02 ( + C2 + 2
1n 2 03] < log
(174)
0²
where C2 2 22+llo((()1122)
Proof. From Lemma
4.4
defining 2: = arg max 9e (x), we see that
Pr (0t (-1((2)) + B (2 (8)
2 5,
(175)
since oi - (2(). Therefore, a direct consequence of Lemma 4.2 we obtain that
02 +2+1-1
S log
+ 3(0) + 2m,(3),
(176)
g2
29

---

Published in Transactions on Machine Learning Research (09/2025)
which holds with probability least - 6. Furthermore, since the right-hand side is positive, the following also holds:
- + 3(6) + v2T 2
0² 1-+1-1
Pr
t1 1
[tt 2 0} I log
(177)
0²
o² - F
log
+ 3(0) + 227 2 21-6,
(178)
o²
where F(.) is the cumulative distribution function of nz (1 0}. By applying F-1, which is the generalized inverse function of F and monotonically incrcasing, we obtain that
0² ( + ((6) + 2xx 2 F1 8). 0²
log
(179)
By substituting Z Uni(0, 1) to and taking the expectation with respect to Z,
t 0² +
Ez
log
(()) (2m
2 Ezz (1- 2)] = Ez [F- [Z)] = [ (m 2 0)] (180)
In the last equality, we use the fact that n/ 1m 2 0} and F- (Z) are identically distributed. Furthermore, the left-hand side can be transformed as
( + ((2) + 2T
0² 0²
0 +t 1
Ez log
log
+ +
(181)
0²
0² +2 0²
S log
[2]
2: (Z))),
(182)
where the last inequality is obtained by Jensen's inequality. addition, we can derive
[2)3 = =
- Ey/2oog(11///// = 2log((X)122 + 2,
(183)
since log(1/2) follows the exponential distribution. Consequently, obtain that
o ( 0²
m 1m 2 03] < log
+ C2 + V
(184)
where C2 = Ez|B(Z)) 2 logg( (22) 2
Then, we provide the detailed proof of Theorem 4.6
Theorem 4.6 Let f GP(O, k), where the kernel function is normalized as k(x, S 1, and X' be finite. Then, by runming GP-EIMS, the BCR can be bounded from above as follows:
BCRT S CTBTTT
(185)
where By log ( + C2 + V C1 = =2 log(1 + o), and C2 = 2 + 2 2log((((122)
Proof. From Lemma 4.1 and Corollary
we see that
BCR <
Σ E Ime /in
(186)
v C BrThT
(187)
30

---

Published in Transactions on Machine Learning Research (09/2025)
C.4 Proofs for Sec. 4.2.2
First we show the proof of Lemma 4.7
Lemma 4.7
Suppose Assumplion
2.1 holds. Pick â E (0, 1) and 12 1. Then, the sollowing holds:
((z).)) 2 11-0 where Bc(6) = 2dllog(m) (2g( and my max bdr (02 (02 + t 1) log log((ad) (2ad)/ o
Pr.
VVx E X, f(x) s - +
(188)
Proof. Under Assumption 2.1 using the union bound with respect to E [d],
Pr
max L3 > I(8) 2 jEId
(189)
where L(ö) bvlog(ad/O) Therefore, the following inequality holds with probability least 1- 6:
Pr (Vo E X, f(x) f([x])) L(6) [æ]+|lı) 2 1 8.
(190)
Hence, by using the union bound, the following upper bound holds with probability at least 1 - 8:
f(x) 100----1(aan ((-1((=)))) = f(x) f((=),) + f(())))) - ((=))
(191)
S L//2||æ - [=]] + ((x))
(192)
In addition, from the construction of Xz,
Va E X. 1111 - -(x]1111 S dr
(193)
m2
Therefore, we see that
Ls/2dr m bdr /log(2ad/0)
L8/2||æ
|0lella
(194)
(195)
22
(6)
(because my 2 bdr (0² + t 1) log 2od)
(196)
02 +
log (2ad)
02
2log()).
(bocause log(2ad) 2 log > 0.69)
(197)
0² t
On the other hand,
8. (6/2) / 2d log(m)) log(o)
(198)
2 22dlog(2) 2 log.
(because m, 2 2)
(199)
Moreover, from Lemma D.1 (x) 2 02/(0² + - for all x e X. Therefore, we obtain that
L,/2|1 |æ]e||] < (6/2
(200)
Finally, we derive the desired result:
f(x) - - < (6)
(201)
Next, show the BCR upper bound for continuous input domains:
31

---

Published in Transactions on Machine Learning Research (09/2025)
Theorem 4.8
Suppose Assumption 2.1 holds and f GP) where the kernel function k is normalized Then, by running GP-EIMS the BCR con be bounded from above follows:
k( x)) <
BCRT S VCBBTTT.
(202)
where C = 2/ log(11 + 2), BT = log ( + CT + VTOT, CT 8(dlog(mr) + 1), and mr
max (2. ( T - 1) log (ad) ]
Proof. As with the proof of Corollary 4.5 using Lemmas 4.2 and 4.7 we can derive that
(
o²
1h
(m 2 0}} <
log
+ C. V
(203)
where C. = ((dlog(m;) + 1). Then, as with the proof Theorem 4.6 we can obtain that
BCRr S
Σ E Ln Im
0flv Cir
(204)
C1 Br
(205)
D Auxiliary Lemmas
Lemma D.1 (Lemma 4.2 in (Taeeno et al.
2024 Let l be kernel s.t. k(x,x) S 1. Then, the posterior
variance is lower bounded as,
di(x) 2 0² +
(206)
for all x E X and for all 2 0.
Lemma D.2. Let f ~ GP(O, k), where & is a kernel 8.l. k(x, x) < 1. If X is finile, Elmax [(x)] - Elmingex / [ar) I /2g (1x) 2. If Assumption holds, E|maxzexx f(x)] = - E[mingex [x)) S
/2dlog (Ibdr(log(at + / 2 + 22 2
Proof. First, since f follows centered GP, E E[max [()) - -Emin [æ)].. For a finite input domain can obtain
X, from Lemma 4.2 of (Takeno et. al. 2023
E
max xEX
f(x) < 12 V = 22 +
(207)
where Ç - 2 2l)(((X112 + 2Z and Z Exp(A- 1).
For an infinite input domain, we consider a finite set X, with each dimension evenly divided by T. [bdr(log(ad)) + v such that |&/]= - Td. In addition, we denote [z], arg ming'ex, || 1 x'|l1- Then, by
Lemma H.2 of (Takeno et al.) 2023 we see that
E Eff(=') f([x"]+) 1.
(208)
Furthermore, as with the case of finite input domain,
max (xx s 2og (22) + 2 = / 22dlog ([bdr(log(ad) + vx/2)]) + 2 - 2 log 2, (209)
which concludes the proof.
32

---

Published in Transactions on Machine Learning Research (09/2025)
EIMS
El-4 maxt
IRGPUCB GPUCB
PIMS
MES
-
TS
JES
GP (Matern52, 1=0.1, 0=0.01)
GP (Matern52, == 0=0.01)
1.50
1.50
1.25
1.25
Simple Regret
1.00
1.00
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
0
50
100
150
200
0
50
100
150
200
Iteration
Iteration
GP (Matern52, 0.1, 0=0.1)
GP (Matern52, -02 0=0.1)
1.50
1.50
1.25
1.25
Simple Regret
1.00
1.00
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
50
100
150
200
0
50
100
150
200
Iteration
Iteration
GP (Matern52,
0.1, 0=1.0)
GP (Matern52, f= 0=1.0)
1.50
2.0
1.25
Simple Regret
1.5
1.00
0.75
1.0
0.50
0.5
0.25
0.0
0.00
0
100
200
300
400
100
200
300
400
Iteration
Iteration
Figure 3: Results of simple regret for synthetic functions generated from GP defined by the Matérn kernel
with = 5/2. The top, middle, and bottom rows show the result for noise standard deviations 0.01, 0.1, and 1, respectively. The left and right columns show the result for length scales of the kernel é = 0.1 and = 0.2, respectively. Daggers in the legend indicate that the BO method was performed with theoretical settings, for example, regarding the hyperparameters.
33

---

Published in Transactions on Machine Learning Research (09/2025)
E
Additional Experiments
E.1
Synthetic Function Experiments with Matérn Kernel
and show the simple regret and cumulative regret for the Matérn kernel with = 5/2. The experimental settings are the same as those in the main paper, excepl for the kernel function. Also in these experiments, we can observe a similar tendency to the results of the SE kernel function.
Figures
3
E.2
Benchmark Function Experiments
Figure 5 shows the results of the simple regret for several benchmark functions. We employed the SE kernel function with automatic relevance determination (Rasmusson & Williams 2005). We performed hyperparameter selection for the GP model every five iterations. In these experiments, we did not add actual noise. Since arg =ax (xx) is unstable due the hyperparameter selection, we define the simple regret using é arg m (x) 20,(z)). We employed the heuristic hyperparamcters for the AFs of GP- UCB, IRGP-UCB, and GP-EI-p
Bt 0.2d log(2t) with (Kandasamy et al. 2016 and & = max log(d) 0) Zu, where Ze ~ Exp(A 1/2). Therefore, GP-UCB, IRGP-UCB, and GP-EI-yemas are no longer theoretically guaranteed. Other settings are the same as those of the synthetic function experiments.
0.2ddog((2)
Except for the Ackley and Shekel functions, almost all BO methods perform well. For the Ackley function, GP-UCB, IRGP-UCB, and GP-EI show superior performance. This is because these BO methods are more exploitative than other BO methods in this experiment, and exploitative AFs work well for the Ackley func- tion. However, for the Shekel function, more explorative GP-PIMS, GP-EIMS, and E show superior perfor- mance. Therefore, we believe that these differences in performance come from the exploitation-cxpllratio tradeofT. On the other hand, regarding the BO methods with the theorelical guaranlee without heuristic tunings, we consider that GP-PIMS and GP-EIMS are superior or comparable to GP-TS.
34

---

Published in Transactions on Machine Learning Research (09/2025)
EIMS
_ El-4 maxt
IRGPUCB GPUCB
PIMS
MES
EI
-4--E31
TS
JES
x10
GP (Matern52, /=0.1, 0=0.01)
x102 GP (Matern52, == 0=0.01)
6.0
Cumulative Regret
6.0
4.0
4.0
2.0
2.0
0.0
0.0
50
100
150
200
0
50
100
150
200
Iteration
Iteration
x10
GP (Matern52, ==0.1, 0=0.1)
x102
GP (Matern52, t= 0.2, 0=0.1)
6.0
Cumulattve Regret
6.0
4.0
4.0
2.0
2.0
0.0
0.0
50
100
150
200
0
50
100
150
200
Iteration
Iteration
x103
GP (Matern52, ==0.1, 0=1.0)
x 3
GP (Matern52, = 0=1.0)
1.5
1.2
Cumulative Regret
1.0
1.0
0.8
0.5
0.5
0.2
0.0
0.0
100
200
300
400
100
200
300
400
Iteration
Iteration
Figure 4: Results of cumulative regret for synthetic functions generated from GP defined by the Matérn kernel with 5/2. The top, middle, and bottom rows show the result for noise standard deviations = 0.01, 0.1, and 1, respectively. The left and right columns show the result for length scales of the kernel = 0.1 and f = 0.2, respectively. Daggers in the legend indicate that the BO method was performed with theoretical settings, for example, regarding the hyperparameters.
35

---

Published in Transactions on Machine Learning Research (09/2025)
Ackley (SE, d=4)
Hartmann3 (SE, d=3)
EIMS
GPUCB
EI
PIMS
El-ymmax
TST
Simple Regret
10
E31
MES
10-1
IRGPUCB
JES
10-3
10-5
50
100
150
200
50
100
150
200
Iteration
Iteration
Hartmann4 (SE, 4=
Hartmann6 (SE, d=6)
100
100
Simple Regret
10
10
10-2
10-3
10-2
50
100
150
200
50
100
150
200
Iteration
Iteration
Shekel (SE, d=4)
Styblinski tang (SE, d=2)
10
102
100
Simple Regret
100
10-2
10-1
10
1
50
100 Iteration
150
200
0
50
100
150
200
Iteration
Figure 5: Results of simple regret for the benchmark functions. Daggors in the legend indicate that the BO method was performed with theoretical settings, for example, regarding the hyperparameters.
36


Reviews:
[{"review_id": "LG7Ak0C5pg", "reviewer": "Reviewer_5GpT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new algorithm for a Bayesian optimization setting where the objective function is drawn randomly from a centered Gaussian Process, and the observation noise is assumed to be Gaussian with a known variance. The new algorithm is a variant of the expected improvement framework, in which the reference value is chosen by maximizing a posterior sample path. Two sub-linear regret bounds for finite and continuous domain are provided. The analysis and proof techniques are mostly leveraged from existing works.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper's main contributions are Algorithm 1 and its regret bounds in two theorems 4.6 and 4.8. I carefully verified the proofs of these theorems in Appendix C and found all proofs to be correct. I also verified the claim made in Appendix A on the mistake of an existing paper.", "audience_yn": "Yes", "audience_explanation": "The new algorithm and its sublinear BCR bound are novel, and likely of interest to the Bayesian optimization community.", "requested_changes": "Main:\n- It would be better to explicitly point out exactly what the novelty in Algorithm 1 is in comparison to previously known algorithms in existing works. In particular, is using $g_t^*$ in the EI function the main novelty of Algorithm 1?\n- In Lemma D.2: Is $E[\\max_x f(x)] = E[\\min_x f(x)]$ a typo and it should be $E[\\max_x f(x)] = -E[\\min_x f(x)]$?\n\nMinor:\n- In the Introduction, it would be helpful to be more explicit about the role of the Acquisition Function in this framework. For example, writing $x_t \\in \\argmax AF(x)$ would be good.\n- In the first sentence after Equation 165: why does the monotonicity of $\\sigma_t$ implies $\\sigma_{t-1}(x) \\leq 1$? I thought this came from the normalized kernel $k(x,x) \\leq 1$.\n- Right before Equation 175: it is helpful to remind the reader that $g_t^* = g_t(z_t)$ here.\n- The sentence right after Equation 178: inside the word \"distribution\" there is some Latex symbol, which seems like a compilation error.\n- Going from Equation 179 to Equation 184: this part is correct, however can we simply take the integral from 0 to 1 w.r.t $\\delta$ of $\\log(\\dots) + \\beta(\\delta) + \\sqrt{2\\pi \\beta(\\delta)}$ to get Equation 184? This is often done, for example, in bandit literature to convert a high-probability regret bound to an in-expectation regret bound.", "broader_impact_concerns": "N/A", "additional_comments": "- Is there a known lower bound for BCR?", "extra_scores": {}, "extra_text": {}}, {"review_id": "s9zCBu91Zc", "reviewer": "Reviewer_mJGG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes GP-EIMS, a new posterior sampling–based variant of Expected Improvement (EI), in which the *reference value* is set to the maximum of a single posterior sample path ($g_t^*$) at each iteration $t$. The key theoretical contribution lies in an elaboration of issues in contemporary regret-proof on EI acquisition function, and the proof of sublinear Bayesian cumulative regret (BCR) [1] for GP-EIMS under standard GP prior assumptions with stationary kernels (squared exponential, linear, Matérn families with sufficient smoothness). Empirically, the algorithm has been compared with different contemporary acquisition functions on synthetic functions ranging from $d=1\\sim d=6$ and demonstrates interesting results among the acquisition functions with theoretical garantee. Since the main contribution is on theoretical analysis, a proof sketch summary is provided at the next block.\n\nStrength:\n- The paper provides a theoretical proof of Bayesian cumulative regret for both discrete and continuous domains (under strong assumptions), which is rigorous and plausible.\n- It provides an extensive discussion of the limitations in contemporary regret analyses for the Expected Improvement (EI) acquisition function.\n- The paper clearly articulates its contributions, assumptions, and limitations.\n\nWeaknesses:\n\n- Algorithmic:\n    - The proposed method is somewhat incremental, as it can be viewed as a special degenerate case of the E3I framework.\n    - The analysis focuses solely on Bayesian cumulative regret, which provides an average-case guarantee. Unlike methods such as GP-UCB, it does not establish high-probability regret bounds, limiting its robustness under adversarial scenarios.\n- Theoretical:\n    - In the continuous setting, the analysis assumes exact maximization of posterior samples. As acknowledged in the paper’s limitations, this requires a strong idealization that disregards approximation artifacts such as random Fourier features (RFF). Strictly speaking, the proof in the continuous domain is not fully complete without addressing such approximation errors.\n- Empirical:\n    - Experiments are limited to small to middle-scale, discrete search spaces, which restricts the demonstration of practical scalability.\n    - Performance is comparable to or slightly worse than PIMS, casting doubt on the method’s empirical advantage. In particular, it is counterintuitive that the PI-based posterior sampling variant outperforms the EI-based one, despite the theoretical motivation. Additionally, stronger baselines such as Joint Entropy Search are not considered, further weakening the empirical positioning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The main claims in the submission are theoretical, focusing on bounding the Bayesian cumulative regret (BCR) for a posterior-sampling-based variant of the Expected Improvement (EI) acquisition function. A proof sketch, to the best of my understanding, is outlined below:\n\n----------------\nProof Sketch\n- **Bounding Regret via Normalized Deviation (Lemma 4.1)**: \n\n    \\begin{equation}\n       BCR_T \\leq \n        \\underbrace{\\left( \\mathbb{E} \\left[  \\sum_{t=1}^T \\eta_t^2 \\cdot \\mathbb{I} (\\eta_t \\geq 0 )  \\right] \\right)^{1/2}}_{\\text{Expected squared normalized deviations}}\n        \\cdot \\sqrt{ C_1 \\gamma_T },\n    \\end{equation}\n The problem reduces to bounding the accumulation of normalized deviations $\\eta_t$.\n- **Uniform Upper Bound on Normalized Deviation**: \nBy constructing a high-probability upper bound $U$ on the sample path maximum $ g_t^*$, the normalized deviation satisfies:\n\n\\begin{equation}\n \\eta_t  \\leq \\frac{U - \\mu_{t-1}(\\mathbf x_t)}{\\sigma_{t-1}(\\mathbf x_t)} \\leq \\sqrt{\\log\\left( \\frac{\\sigma^2 + t - 1}{\\sigma^2} \\right)} + \\beta + \\sqrt{2\\pi\\beta}\n\\end{equation}\n\n- **Bound the expectation term**:\n$\\mathbb{E} \\left[ \\eta_t^2 \\cdot \\mathbb{I}(\\eta_t \\geq 0) \\right] \\leq B_t$\nand \n$\\mathbb{E} \\left[ \\sum_{t=1}^T \\eta_t^2 \\cdot \\mathbb{I}(\\eta_t \\geq 0) \\right] \\leq \\sum_{t=1}^T B_t = \\mathcal{O}(T \\log T)$\n and eventually upper bound on the accumulation of normalized deviations and hence BCR$_T$.\n\nWhile I am not deeply familiar with the full BCR literature, I have examined the derivations in Appendix C and found them plausible and technically sound. The logical steps appear coherent and well-supported.", "audience_yn": "Yes", "audience_explanation": "This paper will be of interest to the Bayesian Optimization and GP bandit communities, as it provides new progress on the regret analysis of the Expected Improvement (EI) acquisition function. In particular, it offers a rigorous sublinear Bayesian cumulative regret bound for a posterior-sampling-based variant of EI (GP-EIMS), which has been historically difficult to analyze. Moreover, the work sheds light on overlooked issues in prior regret proofs for EI-type strategies, offering a clearer theoretical foundation for future research.", "requested_changes": "There are a few points that could be considered to strengthen the paper:\n- **Comparison with $E^3I$**: one important aspect, since this-EI variant can be regarded as a degenrate version of $E^3I$, it is important to understand its empirical performance compared with it. It is not expected that EIMC is empirically better than $E^3I$, but this provide a better position of this paper in terms of its empirical performance.\n- **Clarification of randomness in expectations**: The statement \"the expectation is taken with all the randomness, that is, $f$, $\\epsilon$, and the randomness of the algorithm'' should be clarified. Specifically, the ``randomness of the algorithm'' refers only to the sampling of $g_t$ from the posterior GP, i.e., $g_t \\sim \\mathcal{GP}(\\mu_{t-1}, k_{t-1})$. Otherwise, this may be misleading.\n- **Inaccurate citation**?: The citation ``Kandasamy et al., 2018'' appears to focus on Bayesian **simple regret** rather than Bayesian Cumulative Regret (BCR). It would be more accurate to either remove this citation or clarify the distinction.\n-  **Justification for BCR focus**: For accessibility to a broader audience, it is recommended to include a sentence justifying the choice of BCR as the analysis objective, instead of the more commonly used high-probability cumulative regret bounds (e.g., those in GP-UCB)\n-  **Improved proof accessibility**: While the paper is mostly clearly written, the regret proof in Appendix C remains difficult to follow without substantial background. i strongly recommend including a proof sketch or a high-level discussion at the beginning of the theoretical section. This would help guide readers by outlining the logical structure of the proof.", "broader_impact_concerns": "N/A", "additional_comments": "**Question**:\nSince it is assumed that hyperparameters are known within this research, could the author provide some comments on how the regret bound degrades under GP model misspecification (e.g., mismatched kernel, unknown hyperparameters)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "8vNWK8WrHl", "reviewer": "Reviewer_LpXR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Contributions / Paper Summary**\n\n- **Sublinear Bayesian cumulative regret bounds for EIMS**. This paper analyzes the regret bounds of the Expected Improvement (EI) acquisition function when the improvement reference point is the maximum of a posterior sample path. The authors show that this posterior-sampling-based EI algorithm achieves sublinear cumulative Bayesian regret under standard assumptions. \n  - Specifically, the authors adapt the general approach introduced by Takeno et al. (2024) to their proposed EI from the maximum of the sample path (EIMS). They further leverage results from Wang and de Freitas (2014), combined with a few clever observations, to derive the specific regret bounds.\n\n- **Demonstrate the effectiveness of the proposal method with numerical experiments**. They also provide empirical evaluations on synthetic functions sampled from a Gaussian Process (GP) prior with known hyperparameters.\n\n---\n\n**Strengths**\n\n**Theoretical Contribution**: The paper provides a novel regret analysis for a variant of EI that uses a posterior sample as the improvement reference. This analysis addresses an important gap in the literature and is relevant to the Bayesian optimization community.\n\n**Contextualization with Prior Work**: The paper does a good job of situating its contribution within the context of recent related work. In particular, it discusses prior results and clarifies limitations and differences with previous analyses.\n\n**Rigor**: The theoretical development appears to be technically sound, especially when the authors articulate misleading assumptions about past work.\n\n---\n\n**Weaknesses**\n\n**Empirical Evaluation**: The experimental section is relatively weak and could improve significantly. \n\nIn my opinion, the cumulative regret plots, as currently presented, do not offer much insight. A summary table showing final simple regret values and statistical significance would be more informative and easier to interpret. Also, do some of the error bars have different colors?\n\n**Test functions**: The experiments focus exclusively on synthetic functions sampled from the GP prior. While this setup is analytically convenient, it limits the practical relevance of the results. The paper would benefit from evaluating on standard benchmark test functions (such as those already listed in the appendix) to better demonstrate performance in practice, or at least a better proxy of that. For instance, selecting one function where an exploitative strategy performs well and another where exploration is crucial would replicate the current experimental conditions with the short and long length scales but in a more meaningful context.\n\nImportantly, the authors emphasize throughout the paper that prior work relies on rescaling the posterior variance, which they argue hinders *practical optimization performance*. Given this motivation, expecting more than a validation experiment seems reasonable.\n\n**Writing Quality**: While the logical flow of the paper is clear, the manuscript would benefit from a thorough language revision.", "claims_and_evidence_yn": "Yes", "claims_explanation": "- **Sublinear Bayesian cumulative regret bounds for EIMS**.  While I did not verify every technical detail, the theoretical analysis appears convincing. I cross-checked the results against two related papers and found the claims to be well-supported and credible.\n\n- **Demonstrate the effectiveness of the proposal method with numerical experiments**. I find the experimental section unconvincing; however, I suspect that most readers of this paper may not place much weight on it.", "audience_yn": "Yes", "audience_explanation": "Yes, Expected Improvement is arguably the most widely used acquisition function in Bayesian optimization, so insights from its theoretical analysis are highly relevant to the audience.", "requested_changes": "**Minor Comments**\n\n- **\"Aims for optimization with fewer observations\"**: Consider reprasing it to use fewest instead.\n\n- **\"BO sequentially queries a candidate determined by maximizing an acquisition function based on a Bayesian model\"**: Consider being more precise — what is meant by “candidate” (e.g., input location)? or what is this \"Bayesian model\", of what?\n\n- Consider replacing **\"regret\"** with **\"regret bounds\"**\n\n- **\"Performs querying an input\"**: Suggest rephrasing to *“Performs queries on an input point/location”*\n\n- The term **\"twofold\"** may not be appropriate in that context\n\n- Consider using **\"not advisable\"** instead of **\"not suggestive\"**\n\n- Adding a **y-axis label** would improve the interpretability of the plots.", "broader_impact_concerns": "No concerns here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)