Bayesian Optimization of Robustness Measures under Input Uncertainty: A Randomized Gaussian Process Upper Confidence Bound Approach
Authors: Yu Inatsu
Venue: Accepted by TMLR ()

Abstract: Bayesian optimization based on the Gaussian process upper confidence bound (GP-UCB) offers a theoretical guarantee for optimizing black-box functions. In practice, however, black-box functions often involve input uncertainty. To handle such cases, GP-UCB can be extended to optimize evaluation criteria known as robustness measures. However, GP-UCB-based methods for robustness measures require a trade-off parameter, $\beta$, which, as in the original GP-UCB, must be set sufficiently large to ensure theoretical validity. In this study, we propose randomized robustness measure GP-UCB (RRGP-UCB), a novel method that samples $\beta$ from a chi-squared-based probability distribution. This approach eliminates the need to explicitly specify $\beta$. Notably, the expected value of $\beta$ under this distribution is not excessively large. Furthermore, we show that RRGP-UCB provides tight bounds on the expected regret between the optimal and estimated solutions. Numerical experiments demonstrate the effectiveness of the proposed method.

Published in Transactions on Machine Learning Research (07/2025)
Bayesian Optimization of Robustness Measures under Input Uncertainty: A Randomized Gaussian Process Upper Confi- dence Bound Approach
Yu Inatsu
inatsu. you gwwnntech...ooom.oo.oommmmmmoome ac.jp
Department of Computer Science Nagoya Institute of Technology
Reviewed on OpenReview: https: // openreveew. net/ forum? id- FDzo
Abstract
Bayesian optimization based the Gaussian process upper confidence bound (GP-UCB) offers theoretical guarantee for optimizing black-box functions. In practice, however, black-box functions often involve input uncertainty. To handle such cases, GP-UCB can be extended to optimize evaluation criteria known as robustness measures. However, GP- UCB-based methods for robustness measures require a trade-off parameter, 3, which, as in the original GP-UCB, must be set sufficiently large to ensure theoretical validity. this study, we propose randomized robustness measure GP-UCB (RRGP-UCB), a novel method that samples / from chi-squared-basee based probability distribution. This approach eliminates the need to explicitly specify B. Notably, the expected value of B under this distribution is not excessively large. Furthermore, we show that RRGP-UCB provides tight bounds on the expected regret between the optimal and estimated solutions. Numerical experiments demonstrate the offectiveness of the proposed method.
1 Introduction
In this study, we address the optimization problem of robustness measures for black-box functions under input uncertainty. In various practical applications, particularly in engincering, black-box functions with high evaluation costs are frequently used. In practice, these functions often exhibit input uncertainty. Tet f(x, w) be black-box function, where E X' and E are input variables referred as design vari- ables and environmental variables, respectively. The design variable the environmental variable is uncontrollable and follows certain probability distribution. In practical applications, identifying the optimal design variables for black-box functions that include stochastic envi- ronmental variables requires the use of measures that depend solely on the design variables while accounting for the influences of environmental uncertainty. Robustness measures are evaluation criteria defined only in terms of the design variables, effectively removing influence environmental uncertainty. Examples of such robustness mcasures include the expectation mcasure [f w)), which takes the expected value over the distribution of the environmental variables, and the worst-case measure inf f(x, w)), which considers the worst-case scenario. In this paper, consider the following optimization problem for given robustness measure F(x):
completely controllable, whereas
arg max F(x). =EX
Bayesian optimization (BO) (Shahriari et al. 2015), based on Gaussian processes (GPs) Williams & Ras- mussen 2006), a powerful approach for optimizing black-box functions. Numerous BO methods have been developed for optimizing black-box functions without input uncortainty. In contrast, applying stan- dard Ga-based BO methods to the optimization robustness measures under input uncertainty is not straightforward. The main difficulty lies in the fact that even if the black-box function f follows GP, the

---

Published in Transactions on Machine Learning Research (07/2025)
resulting robustness measure F generally does not follow GP. However, recent studies have proposed BO
methods specialized for specific robustness measures by utilizing the GP assumption for f, without requiring distributional information about F (Iwazaki et al., 2021b Nguyen et al. 2021b a Kirschner et al. 2020 In
addition, methods have been proposed for optimizing general robustness measures (Cakmak et al.
2020 as
well as for multi-objective robust optimization using BO (Inatsu et al. 2024a).
However, a theoretical evaluation of the performance of BO is vital. Regret, defined as the difference between the solution obtained by optimization algorithm and the true optimal solution, is commonly used to evaluate the performance of such algorithms. In particular, within the standard BQ framework without input uncertainty, the Gaussian process upper confidence bound (GP-UCB) algorithm (Srinivas et al. 2010) is a prominent example of a BO method with theoretical performance guarantees. GP-UCB has been shown to achieve sublinear regret with high probability by appropriately tuning the trade-off parameter 8r, which is specified by the user. It is highly scalable, and numerous extensions have been proposed, including multi- objective BO, multi- filtii-ii BO, high-dimensional BO, parallel BO, multi-stage BO, and BO of robustness
measures (Zuluaga et. al.] 2016 Kandasamy el al. 2016 2017; 2015 Rolland al. 2018 Contal el al.;
2013
Kusakawa et al.] [002
Iwazaki et al.) 2021b Nguyen et al. 2021b Kirschner et al., 2020 Inatsu
ct al. 2024a). These extended GP-UCB- methods also provide thcorctical guarantees for regret-like
performance metrics.
However, to ensure theoretical validity, the trade-off parameter 3, in GP-UCB and its variants must in- crease on the order of log with iteration t. This results in overly conservative behavior in practice. Such conservatism can significantly impair practical performance (Takeno et al., 2023). To solve this problem, the improved randomized GP-UCB (TRGP-UCB) (Takeno et al. 2023) was proposed, which replaces the deterministic setting of 3r with random sample drawn from a two-parameter exponential distribution. IRGP-UCB avoids the need to increase 8, by logt, thereby mitigating the conservativeness of the theoreti- cally recommended values in GP-UCB. Furthermore, the cumulative regret of BÒ using IRGP-UCB has been shown to remain sublincar in expectation and achieves a tighter bound than that of the original GP-UCB Additionally, an optimization method was introduced within the level-set estimation framework that applies a similar sampling- based technique to replace the trade-off parameter in 2024b). Thus, RRGP-UBB not only resolves the limitations of the original GP-UCB but also shows promisc for generalization across variety of settings, similar to its predecessor. In this study, we propose a new BO method for robustness measures by extending the randomized GP-UCB-base method used in IRGP-UCB.
methods (Inatsu et al.,
1.1 Related Work
BO is a powerful tool for optimizing black-box functions with high evaluation costs. It typically comprises three main steps: constructing a surrogate model, selecting the next evaluation point, and evaluating the function. GP or the kernel ridge regression model (Williams & Rasmussen 2006) is commonly used as the surrogate model. The next evaluation point is determined by optimizing a utility function known as an acquisition function. Research in BO has focused on the design of new acquisition functions. For standard black-box optimization problems, widcly used acquisition functions include expected improvement (Močkus) 1975), Thompson sampling (Thompson 1933). entropy search (Hernández-Lobatee et al 2014), knowledge gradient (Wu & Frazier 2016), and GP-UCB Srinivas et al., 2010). Many of these acquisition functions have been extended to accommodate various BO settings, such as multi-objective optimization, constrained optimization, high-dimensional problems, and optimization involving robustness measures.
When optimizing a black-box function in the presence of input uncertainty, such as that introduced by environmental variables, robustness measures too have to be optimized. These are defined solely in terms of the design variables and reflect the uncertainty associated with the environmental variables. Representative robustness measures include the expectation measure (Beland & Nair 2017), worst-case measure (Bogunoiic
ctt al. 2018), probability threshold robustness (PTR) mcasure [wwzzaki ct al. 2021a), valuo-at-risk Nguyen
ee al. 2021b), conditional value-at-risk Nguyen el al.
2021a),, mean-variance measure (Twazaki et al. 2021b).
and distributionally robust measure KKircchner et al.
2020 Tay et al. 2022 2024). Corresponding acquisitin
functions for the BO of robustness measures include GP-UCI B-basod mothods (Bogunovic et al. 2018 Twazaki
et al. 2021a Nguyen al.
2021b a [wazaki al.
2021b Kirschner et al. 2020). knowledge gradient-basee
methods (Cakmak et al.
2020
Thompson sampling-based methods [Twazaki et al.] 2021a Tay et. al.
2

---

Published in Transactions on Machine Learning Research (07/2025)
2024 and approximation-based methods (Tay et al. 2022). In particular, GP-UCB-based optimization methods for robustness measures provide theoretical guarantees with respect to regret. Furthermore, Inaisu et al. (2024a) proposed the bounding box-based multi-objective BO (BBBMОBO) method a theoretically optimization method for multi-objective robust BQ involving multiple general robustness measures. If we consider the special case in which only a single robustness measure is involved, the method proposed in [natsu et al. (2024a) provides theoretically guaranteed optimization method based on GP-UCB for general robustness measures. However, in GP-UCB-based optimization methods for robustness measures, establishing theoretical guarantees requires the trade-off parameter Sr to increase with the iteration index 4, resulting in a conservative setting that adversely affects practical performance. On the other hand, Tay et al. (2024) propose a BO method for a robustness measure defined as the weighted sum of the distributionally robust expectation measures and their right derivatives, using a method based on Thompson sampling. Furthermore, they provide theoretical bounds for Bayesian regret, which has a slightly different dcfinition from the regret considered in this study. However, while Thompson sampling does not require trade-off parameters like GP-UCB in terms of algorithm design, is necessary to use GP-UCB, which requires the trade-off parameter 8, to increase with iteration t, when performing theoretical analysis. As result, this influence is also included in the theoretical bounds they derived.
guaranteed GP-UCB-basse
Two studies closely related to the present work are Inatsu et al. (2024a) and Takeno et al. 2023 The former addresses BO for Pareto optimization with multiple robustness measures using a GP-UCB-base framework. As a special case, it also considers optimization for a single robustness measure and provides high-probability regret bounds for general robustness measures. The latter study, Takeno al. (2023). introduces randomized approach to GP-UCB in which the trade-off parameter 3, is sampled from evo-parameter exponential distribution. This approach avoids the need to increase Br logarithmically and achieves lighter regret bound than standard GP-UCB under certain conditions. However, the regret bounds achieved by Takeno et al. (2023) depend heavily on the problem setting, the specific definition of regret, and the choice of the sampling distribution for 3. As pointed out by Inatsu et al. (2024b), these factors must be carefully tailored to the target problem to replicate the theoretical guarantees different contexts. Therefore, a direct substitution of the trade-off parameter in the method of Tnaasu et al. (2024a) with a random sample from a two-parameter exponential distribution will not suffice to obtain a tighter regret bound. To the best of our knowledge, rescarch has been conducted on BO methods based on GP-UCB for general robustness measures that achieves lighter regret bound without requiring the growth of Br.
1.2 Contribution
In this study, we propose randomized robustness measure GP-UCB (RRGP-UCB), a new algorithm for efficiently optimizing robustness measures of black-box functions. RRGP-UCB modifies the BBBMOBO framework in Inatsu et al. (2024a) by introducing random sampling for the trade-off parameter and selecting points with high uncertainty between the optimistic and average-based maxima. This enables tighter theoretical analysis of regret for solutions based the surrogate model's average prediction. Table [ summarizes the correspondence between IRGP-UCB, BBBMOBO, and RRGP-UCB, while presents theoretical bounds on cumulative regret for representative robustness measures and existing methods. Tn addition, Figure ! shows the behavior of 8, in the proposed method and the relationship of 3e with respect to the increase in iteration f. The main contributions of this study are as follows:
RRGP-UCB introduces a randomized trade-off parameter Be for GP-UCB in robustness measure optimization. This randomization, along with certain modifications, eliminates the need to explicitly specify the parameter 3 or to increase it on the order of log t. As a result, it avoids the problem of overly conservative behavior.
RRGP-UCB applies to general robustness measures. We theoretically show that the expected cu- mulative regret is sublinear for many robustness measures, including the expectation measure.
RRGP-UCB extended various robustness optimization scttings: controllable environmental variables (simulator settings), uncontrollable settings, finite input spaces, and continuous input spaces.
3

---

Published in Transactions on Machine Learning Research (07/ (225))
Histogram Rf
Iteration vs B.!?
230000
Propases setting
2
8PTT T4/C-
Confodecc pammette
Frequency
150000
50000
3.0
3.5
4.0
4.5
5.0
5.5
6.0
200
400
600
800
1000
R
Iteration
Figure 1: Comparison of Bg in the proposed method and existing methods when |X x 2 = 1000. The figure the left shows the histogram of 8²/² in the proposed method with 1000 000 samplings. The figure the right shows 3t at the theoretically recommended value in the proposed method, the setting where the black-box function is assumed to be an element of a reproducing kernel Hilbert space (RKHS setting) [Bogunovic et al., 2018 Nguyen et al. 2021b Kirschner et al. 2020 Inatsu et al. 2024a). the setting where the black-box function is assumed to be a sample path from a GP (Bayesian sctting) (Nguyen et al. 2021a) and BO method for PTR measure (BPT-UCB) [[wazaki et al. 2021a). The pink area in the figure on the right represents the 95% confidence interval, and for the RKHS setting, Bayesian setting, and BPT-UCB, + /2(lo((() + + log(1/0.05)): /2 log(12 x 12/2(2/((6 0.05)), (I 2//26//(6 x 0.05)) 1/10 were used 8//2, respectively.
Table 1: Theorctical guarantec of regret in IRGP-UCB, BBBMOBO, and RRGP-UCB (Proposed).
Method
Confidence parameter
Next point to be evalusted
Regret
IRGP-UCB
Takeno et al.
2023
B 2oo X (2) xi
ang maX uch (x))
maX f(a) f(x.)
BABMORO Inatsu et al.
2024a
& n 2(h log[1/8))
max (neb) (er/ (xx) 10b/ (())))
max F(x) F(5.)
Propused
A log((1X (I]) x²
arg u (ucl/[ilue) lbb/"((u))
maXag F(x) F(h.)
xd: Cliisqqared distribution with two degrees of freeddom Maximum information gain, (-4, max(..0)
R. ang ma Jch. (un), (un), ài ang max o(pe-11x, w)), arg muxxEN (uob(S((e) lobS((t)))
Experimental results on both synthetic and real-world datasets show that RRGP-UCB achieves performance comparable to or better than existing methods.
2 Preliminary
Problem Sctup Let f: x + be an expensive-to-cvaluate black-box function, where X' and Ω are finite set For each (æt, (x) E X x Ω we observe f(æ,, w.) with noise &, as follows: 3r = f(x,, wx) + St: where El,...,E; are mutually independent and follow some distribution with zero mean. Let x X a design variable and E f2 an environmental variable, where w uncontrollable and follows distribution ps. In black-box optimization involving environmental variables, two types of settings are considered: simulator settings (Cakmak al.] 2020 Nguyen et al. 2021b Beland & Nair 2017; Twazaki et. al. 2021a) and uncontrollable settings (Kirschner et al. 2020 Inatsu al. 2024a 2022 [wazaki et al. 2021b). In the simulator setting, the value of aD can be arbitrarily selected during optimization, whereas in the uncontrollable setting, to cannol be controlled even during optimization ion. In the main text, we focus on the simulator setting; the uncontrollable setting is discussed in Appendix
B Let A(w) be a function of w, and let p(-) be a mapping from the function (()) to the real numbers. For any function y(æ; w) defined on X x Ω.
The case where X' and continuous discussed Appendix
4

---

Published in Transactions on Machine Learning Research (07 2025))
Table 2: Theoretical bounds on cumulative regret Rí for existing and proposed methods for expectation (EXP), value-at-risk (VaR), conditional VaR (CVaR), and distributionally robust expectation (DREXP) measures.
Method
EXP
VaR
CVaR
DREXP
DRBO
Kirschner et al.
2020
Rr So VTBr
Ri Sa VT
V-UCB
Nguyen et al.
2021b
Hr S. /1Br
CV-UCB
Nguyee al.
2021a
RT Sa VTBT
ВВBМОBθ
(Inatsu et al.
2024a
Hp S. VT Rp Sa v' T1B
Ry Sa vT E[ & VT
Ry Sa v /T RT) S VTTT
Proposed
R[] S VT
E[RT] S /TTT
Definition of cumulative regret Ry is not necessarily the same for each method
Ry S. a + P(R, s a) 2 1-8
when is fixed, p(x w) a function of w and is denoted by ((z.)). In particular, when is fixed, we define ((f = F(a:) a robustness measure of f in Representative robust measures include: the expectation measure (x) (z, w)], the worst-case measure F2 = infwen f(x w), the best-case measure Fa(x)) sup fa, w), the a-value-at-risk measure Fa(x;a) = in E R a S P(f(x, w) S b)}. the a-conditional value-at-risk measure (); = (xf w)]l((rr w) < F1 at), and the mean absolute deviation measure Fa(x:) = [x) w) (z))),,, where the expectation or probability is taken with respect to w. Our goal is to identify the following x" using as few function evaluations as possible:
x arg max F(x).
#EX
We emphasize that while the optimization target is F(æ), we cannot directly observe F(x); instead, only the noisy evaluations of f(x, w) are available.
Regularity Assumption We introduce regularity assumptions for the function f. Let : (X, x (x + be positive-definite kernel such that k((z, w), (z, w)) S for all (x, w) E X x Q. Assume that f is a sample path from a GP GP(O, k((z, w). (a', w')) with zero mean and kernel function k(,,)) We further assume that the noise terms é, are independently drawn from normal distribution with mean zero and variance 0² moises and that Et are mutually independent.
In this study, we predict F based on surrogate model of the black-box function f. We assume that the prior distribution of is a GP GP k((æ, w), (æ',w')), w'))), Given the dataset {(z,, wy, 85) )j) the posterior distribution of f remains a GP. The posterior mean (1, w) and posterior variance of w) are given by standard results from the GP regression Williams & Rasmussen
Gaussian Process
2006
(e(e,, w) (,, w) (K, + 0 n I,) -1y of (z. w) = k((x,, w) (x. w)) k,(x, w) (K, + notoo It) ka w).
where (x, w) is the t-dimensional vector whose j-th element is k((n,, wn) (mz, Wy)); V: (y1, ....... I: is the t x identity matrix, and K, is the t x kernel matrix with the (j, k)-th element k((0), wy), (axx; wi) )..
Notations We summarize particularly important notations used in the main text in Table 3
3 Proposed Method
In this section, we propose BO method to efficiently identify x". First, in Section 3.1 we construct
credible intervals for F(x) based on credible intervals for f(z, w). Next, in Section 3.2 we present a method for estimating the optimal solution. In Section 3.3 we describe method for selecting 2, and we The pseudo-code of the proposed algorithm is provided in Algorithm 1
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 3: Notations used in the main text and their meanings.
Notation
Meaning
a
Design variable
w
Environmental variable
X
Set of design variables
Q
Set of environmental variables Black-box function defined on X' Ω
(x, w)
Observetion noise following a normal distribution Variance of the noise ditribution
noise
pf w)
Arbitrary function defined on X' x Ω
((x,))
In (0x w), a function with respoct to w when æ is fixed Robustness measure, a mapping from functions with respect to w to real numbers
p())
F())
Target robustness measure defined by F(x) p(f(x.)))
xx
Optimal solution defined by arg = F(x)
-(:.))
Kernel function defined on (X' x 12) x (X' Q2)
pa(a, un)
Posterior mean based on GP for fax w)
of (æ, w)
Posterior variance based on GP for f(æ, w)
u (a, w)
Upper confidence bound for f(x, w)
(mn, w)
Lower confidence bound for f(x w)
3e
Parameter for adjusting the confidence bound width
ucb,
Upper confidence bound for F(x)
lob,(w) (x)
Lower confidence bound for F(x)
dt
Estimated solution for the optimal solution defined by â; = arg max ZEX ((pt-1(x..))
(+)
Operator defined by (a)+ = max(a, 0}
Optimistic maximum solution defined by 2; = arg max (ucb,-1 1 (x) - max leb.-1 (x))
æt
Next design variable to be evaluated
&
Random variable following the chi-squared distribution with two digrocs of freedom Next environmental variable to be evaluated
w
Ta
Instantaneous regret regarding the optimal solution and estimated solution
R
Cunulative instantaneous regret regarding the optimal solution and estimated solution Maximum information gain
Yt
E2
Conditional expectation given the dataset D.-1 = ((x1, wT, 81, ( wt (1-1,((-1))
f
Optimal index given by = arg maxieist E,-1
Algorithm RRGP-UCB for robustness measures.
Input: GP prior GP(O, k) for 1,2, do
Generate & from chi-squared distribution with two degrees of freedom
Compute 3 log( 12)) + &
Compute Qx- w) for each (x, w) E X Ω Compute Qx-1(x) for each a E X
Estimate &, by è; = arg max p(u- (x., Select next evaluation point æ, by equation Select next evaluation point w, by equation Observe Y/1 = f(x, wi) + E, at point (æ,, w,)
Update GP by adding observed data end for

---

Published in Transactions on Machine Learning Research (07 (07/2025)
3.1 Credible Interval for Robustness Measures
For each (ær, w) E X' x Ω and L 1 1, let Q w) (ar, w)), ( w)] denole credible interval for f(x, w), where (x, w) and (x, w) are given by
4-- (x, w) - 1 (x, w) 8//2 ot (x, (x, w), up-1 (x, w) - M4-1 (x., w) + 32/20,,01000 w).
02-1
Here, 8, 2 a user-defined trade-off off parameter. Due to the properties of GPs, the posterior distribution of f(x, w) after observing data a normal distribution with mean 14-1 w) and variance d2_1(xr, w). Therefore, by selecting an appropriate value of Be D the interval Q w) contains f(x, w) with high probability. Next, for each a; we define 1 the set of functions over w, as follows:
G--((a)) (g(ar,)) +) for any
Qc.1 un)]
If (ax,( w) is a high-probability credible interval for f(x, w) for all w 52, then the function f(x,-) lies in G.-1 (x) with high probability. Therefore, the following incquality holds with high probability:
inf E(m.)EGG- 1
p(g(x,) p(s( F(x)
sup ((x.))C
p(g(,r,)).
(1)
We can thus construct a high-probability credible interval for F(xr) using the left- and right-hand sides of equation ! However, computing the exact bounds in equation [ is generally intractable. To address this, we introduce the lower bound (cb;-1(x) and upper bound ucb;-1 (x), which satisfy:
1cb) S inf p(g(a, )),
sup p(g(z,-)) S ucb;-1(x). ((C
(2)
a(a,))EG, (m))
Inatsu et al. (2024a) showed that, for commonly used robustness measures, including expectation, the bounds leb,-1 (x) and (cb can be analytically caleulated using (2, w) and u w) I Inatsu et al.) (2024a) differs from this study in that it deals with multi-objective optimization for robustness measures under input uncertainty and adopts the assumption that black-box functions are in RKHS, On the other hand, it shares commonalities with this study in that it adopts a GP as a surrogate model and calculates upper and lower bounds for robustness measures based on equation 2 Therefore, the computational mel hods for lcb;-1(x) and ucb;-1(x)) presented in [natsu et al. 20224a for various robustness measures are applicable to the setting of this study. Representative robustness measures and their corresponding (x)) and ucb;-1(x)) (x) are summarized in Table 4 On the other hand, even for robustness measures not listed in Table 4 it is possible to approximate icb;-1 (2r) and ucby-1(a:) by sampling. First, we generate S sample w) from the posterior distribution of the function f(x, w) and then estimating lcb.-1 (z)) and ucb;-1 1ob;--(2)) (æ) as follows:
paths [x, (x,,w,,..... ..., (2) (()).,
( min ((rls)(z,) (xx,)), ucb = (()())(r))) (ar
15e5s
i5e55
Using these bounds, we define the credible interval Q-)( = [lcb;-1(x), ucb:- [x)] for F(w).
3.2 Estimation of Optimal Solution
We present a method for estimating the optimal solution xt at each iteration t 2 1. Recall that in this setting, the value of the objective function F(#) is unobservable; we can only access noisy observations of (x,ww). As a result, directly estimating x* from the observed data is not possible. To address this, we define the estimated solution à; based on the estimate of F(x) calculated from the posterior mean of f as follows:
c arg max ( #ex
For example, if s//2 = 1.96, then f(z,, w) Qt- (x, w) holds with probability 0.95.
In Tables 3 and 4 in Tnatsu al. (2024a), the terms "risk measure" and "Bayes risk" used instead of "robustness measure" and "expectation measure," respectively.

---

Published in Transactions on Machine Learning Research (07 2225))
Table 4: Values of (cb)(x:) and (x) for commonly used robustness measures (Table 3 in Inatsu et al. (2024a)).
Robustuess measure
Definition
leb,(æ))
ucby(a)
Expectation
Elfmael
E/ xr
Worst-case
inf infwen fa.w
inf infwen fuaee
in MM
Best-case
s0 Ja.s
supeee ha
o-Value-st-risk
ibf R a S Fifa,s & 6]}
inf (6 E R [ o I Flleaw S b)} 1n et (ar; 'daa'
inf E R o S F(M S 61} In eh, (x; ")de''
a- a-conditional value-at-risk
Elfaallew S. [)(2;;]]
Mean absolute deviation
El//a El
Elmin [l 8e. 1nl) STR (h (...).)))
[ [|max [4 m
Standard deviation
VBllie. E, fa
E[[min (onnin//eesa [ /2 [6 w P) STR (ha [e
y /f[max [4, P. M8
Variance
Bliaw Else@l"
Bimin aaw 1
STR' (. dem
E. U.axx (M.x..l 1
Distriutionaaly robust
infp, F(m:;]
inf P leb, (2:: P)
inl Pe (ar
Monotonic Lipschinz map
M(F(z))
min Milnbb ), (t. (x))
max Max{MMln [M (z)) M(cch, (21))
Weighted sum
Flmm)(()) (2))
allcb"""/aa (as) a,leb; "T (a))
ayucb, [m]] (a) axuccy
Probabilistic threshold
Fl 2
Flew 0)
F(.... 2
Ja = [iz, wr), 1,,. 11(2, W), Me E uala, ue), by (a; = inrfe X < 2
n, (175)) inf R Pilaan S. b) 2 o) Vu, (1;20) = ib R a( S 6) a) a (0,
New huww af Rie Naw Ellaaeel , STR(a,
max(min( 6).0)
p(z;; Pi: Robustness mensure P(n)) defined based on the distribution
leb; P), ueb; P): leb)(z)) and ueby(a) for F(x: P)
leb. (ob"")(z) uz). 11 (ar):
lobi(z)) and ucbi(z) for (m)
M(): Monotonic Lipechitz continions map with Lipechit mostant K
01.03 2 0
Expeciation and probability are taken with respect to distribution of and a-value-at-risk mecning a-quanlile
3.3 Acquisition Function
We introduce acquisition functions to determine the next evaluation point (æ,, wt). In this study, the estimated solution á and the next evaluation point æ are not necessarily identical. In previous studics on BO under robustness considerations and envirommental variability (Kirschner et al. 2020 Tnatsu et al., 2024a), Ie is typically chosen based on the upper bound of a credible interval for a robustness measure, while w, is selected to maximize the posterior variance of f(z,, We propose a modification to the method for selecting 2 and partially adopt the aforementioned approach. In particular, as w, is selected based on the posterior variance of f; this eliminates the need for hyperparameter tuning in the acquisition function, unlike the credible interval for F(z), which depends on a user-specified parameter (r. To address this, we avoid fixing 3e explicitly and instead treat it a realization from probability distribution. For example, Takeno et al. (2023) proposed IRGP-UCB within the standard BO framework, in which 3, for GP- UCB is randomly sampled from a two-parameter exponential distribution. Similarly, [nnatu et al. (2024b) proposed the randomized straddle method for level-set estimation, where 3r in the straddle acquisition function (Bryan et al. 2005) is drawn from a chi-squared distribution. These methods remove the need to manually specify hyperparameters and also yield tighter theoretical guarantoes than conventional GP-UCB or straddle mothods. However, these algorithms are designed for problems in which the target function f itself is modeled as a GP, and their theoretical guarantees critically depend on f following GPs. In contrast, the target function in our setting is F(x), which generally does not follow GP, even if f does. Therefore, to derive a theorctically sound acquisition strategy, we modify the GP-UCB method to suit the context in which æt is selected based on the upper bound of the credible interval for F(x). Before introducing this method, we reformulate standard GP-UCB in the conventional BO setting without input uncertainty and highlight its essential structural properties. The following lemma characterizes GP-UCB in this simplified setting:
Lemma 3.1. For a black-box function f(x) modeled as GP, let (x-((x) denote the posterior mean, of (x)) the posterior variance, and Bg 2 0 a user-defined parameter. Define (=) ( + /.//2 -0)((0))) and (x)) = (x) - 21/20,11(2) (x), and
(u)
= arg max Up- 1 (x), (f) = arg max (1: - max 1ا- (+))+ WEX
#EX
MEX
a(f) = arg max (4- 1 (z), x (f)
arg max (1-1(2x) - 4 (x),
#EX
# (a 0 (n)
8

---

Published in Transactions on Machine Learning Research (07/2025)
where (a)+ denoles a if 0, and otherwise is Then, the equality u (1)) = ( holds.
The proof is provided in Appendix C Using this lemma, define the selection rule for ay follows.
Definition 3.1 (Selection rule for æ:). Let ç & be independent random variables drawn from the chi- squared distribution with two degrees of freedom, where f, Ec: .1.... are mutually independent. Define 3. 2 ll' x (2) + ξ.. Assume that 1cb;-1(x) and ucb;-1 are lower and upper bounds that satisly equation 2 and let dt be defined by equation Then, #t is selected as follows:
3t = arg max (ucb)-1(x)) lcb;-(
(4)
=E (+s
where 2, arg max
max lcb;-1
Here, Lemma 3.1 provides different perspective on Definition 3. The acquisition function in Definition 3.1 appears, at first glance, to be unrelated to the usual GP-UCB. However, the usual GP-UCB can be expressed in the same form as Lemma 3.1 and since this equivalent expression is similar to Definition 3.1 the proposed acquisttion function can also be interpreted as an acquisition function based on GP-UCB. Finally, basod on of selected by equation we determine we follows.
Definition 3.2 (Selection rule for wt). The next environmental variable w, is selected follows:
wi arg max of (x w) WEl
(5)
where ny is given by equation
4 Theoretical Analysis
In this section, we provide theoretical guarantees on the expected regret of the proposed algorithm. Detailed proofs are given in Appendix To evaluate the quality the estimated solution, we define the instantaneous regret re and cumulative regret R₂ as follows:
= - -=()))))((E)) R. = -(((")) Σ
In addition, to derive theoretical guarantees for the proposed method, we introduce the concept of maximum information gain "/- This quantity is widely used in the thcoretical analysis of Ga-based BO and level-set estimation (Srinivas et al. 2010 Bogunovic al.) 2016 Gotovos al. 2013), and is expressed follows:
7t
sup (( (1))) ( (n) ()) cxx
log del (I + moiie Ki),
where (Ir1), w())). (I) w() are arbitrary elements of x Ω K, a & kernel matrix with the (i, entry given by k( ((( w()) (IG), Wy))). For commonly used kernels, such the linear, Gaussian, and Matérn kernels, 7t. is known grow sublinearly under mild conditions (see, e.g., Theorem in Srinivas et al. (2010)): ). Let h(a) o0) + [0, co) be non-decreasing, concave function satisfying h(0) 0, and denote by H the set of all h(a). We then define a class of functions g(a) oo) - [0, co), denoted by Q, follows:
2 a(a) = Σ Subs
Σ Assa
|n, E N, Gi Aij 2 0, > 0, (.) E H
For Q, we impose the following assumption on ucbe-1(x1),. (c,)- and the width term /// 0 (x)e, wt). Assumption 4.1. There exists function g(z) Q such that for any t 2 1, F, 3r, and o,- (x,, w), the following inequality holds:
ucb,_1(x;)) lcb, (xx) S /228 max Tr- (x w)).
(6)
west

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 5: Specific forms of ((a) for commonly used robustness measures (modified version of Table 4 in Inatsu ct al. (2024a))
Robustness measure
Definition
q(a)
Expoctation
Fa
Worst-case
inl wel Sn,w
Best-case
wt Ja.w
Q-value-at-risk
inf R
I P( S {b}
a-conditional value-at-risk
E
Ju. sar I (1((2;)) a.)
Mean absolute deviation
E Bllfa,w - E u
2a
Distributionally robust
inf F P)
q(a; F)
Monotonic Lipschitz map
M(F((M) (x))
K (1(TM) (a)
Weighted sum
og (((m) (2c) + 02 F(m2) (x)
011 mes (a) + C22 (m))
lew = f(x, w)) u2(2; = ib E IR PPS S 2 a} E (0,1)
Fa:: P): Robustness measure F (ax) defined based on distribution
q(a; F): function q(a) for F'(x) satisfying Assumption 4.1
M(-): Monotonic Lipschitz continuous map with Lipschitz constant K
(a): function q(a) for (x) satisfying Assumption 4.1
01 2 0
Expectation and probability are taken with respect to distribution of w, and a-value-at-risk is same meaning a-quantile
In this study, g(a) plays the same role as g(a) in Inequality (3) of Inatsu et al. 2024a). J but while their g(a) does not have any assumptions regarding concave functions, ours does. The reason for this is that, unlike Inatsu et al. (2024a), we are subjecting the expected value of (cumulative) regret to theoretical analysis. This analysis requires an incquality evaluation of the expected value, which they did not need to perform. In particular, we need to use Jensen's inequality, which requires
impose additional assumptions regarding concave functions. Similarly to equation 2 it also shares commonalities with Inatsu et al. (2024a) in terms of requiring ((a) satisfying equation G They provide ((a) for various robustness measures, including the expectation measure. In this study, we impose stronger assumptions on g(a) than those in their; however, since the ((a) provided by Inatsu et al. (2024a) satisfies Assumption 4.1 and g(a) E 2, their results can be applied. Representative robustness measures and their corresponding (a) functions are summarized in Table Then, the following thcorem holds.
Theorem 4.1. Assume that equation 2 the regularity assumption, and Assumption 4.1 hold. Suppose that ,, are independent random variables following the chi-squared distribution with two degrees of freedom, and that f.,E....,,E&&I,..... are mutually independent. Define 3, = 2 log(| x [ + &c. Let
g(a)= = En Seh, (Ey=1 Ayants be a function satisfying Assumption 4.1 Then, Algorithm is performed,
the following inequality holds:
RiR
< 2t
Sihi
2 Xig (tC2,vy) Σ 5=1
1-1///2 '-0// (Cr1)4/22
1=1
where uiy min(uy, 1),C of randomness, including f,,,,... Ct, .1,...,Br.
C1
C2.2u
W. E1,3
The expectation is taken over all sources
Togg( +o m
If y is a sublinear function, the following convergence holds:
1 lim - Σ 2 dij (ICa.v)) 1- (Ci (Cmn) t-00 /
(7)
Tnatsu al. 20244a) derives q(a) for measures such the standard deviation and variance, but these rely constants dependent: the norm in the RKHS, which differ from our setting and are thus excluded. The probabilistic threshold also omitted as no explicit form q(a) is provided.
10

---

Published in Transactions on Machine Learning Research (07/2025)
Then, if each (a) is continuous at 0, it follows from Theorem 4.1 that the B[Ri]/t satisfies
E[Re]
lim 21000
0.
(8)
As a special case, according to Table in Inatsu et al. (2024a), ((a) corresponding to the expectation measure satisfies q(a) a; i.., S; 8 Xo = Vi = and h1(a) a. In this case, E[Rg] satisfies
E R. S 1V = C x x2)) + 2)
Similarly, g(a) corresponding the worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures satisfies g(a) 2a for the mcan absolute deviation mcasure and q(a) for the other measures. For these robustness measures, including the expectation measure, the following corollary holds:
Corollary 4.1. Under the assumptions of Theorem 4.1 the following inequality holds for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures:
E[Rc] S CVICOT.
where Cp = (22log(12 x Q() +2/ log(1 + o moise); and C 8 for the mean absolute deviation measure and for the other measures.
While Theorem 4.1 and equation provide guarantee the expected value of the cummlative regret, they do not directly provide a guarantee on the expected value of the instantancous regret. Specifically, they do not answer the question regarding which estimated solution e;, for 1 < S t, achieves the smallest value of E[r.]. this end, we define the index the optimal estimated solution up to time as follows:
f arg
arg min Eemmin-----l E(-1(F(x") F(t:)).
(9)
1sist
where E-111] the conditional expectation given the datasct D defined as follows:
D {x1 wi, 61, B1), (I--1, W,-1,
for t 2, and Do = 0. Then, the following theorem holds.
Theorem 4.2. Under the assumptions of Theorem the following inequality holds:
Elrd
[
Σ Schi 7
Σ 2 Aej (1C2,1)) 1- (- (Cro)66/3
where i is given by equation 9 and hz(-) along with all coefficients defined in Theorem 4.1 Tn addition, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following bound holds:
Ri
Com
E E(ra]
S SCV
where C and Co are given in Corollary
4.1
From Theorem
4.2 if Y is a sublinear function and hz(-) is continuous at 0, then using h₂(0) = -0 and
equation 18 [T: satisfies
lim E[rg] - 0. 100
Therefore, the expected regret associated with index converges to zero as / - oo. However, computing requires solving equation 9 which is generally intractable analytically. Nevertheless, i can alternatively be written as follows:
f arg
argg max E E
13ist
11

---

Published in Transactions on Machine Learning Research (07/)025)
Therefore, & can be defined without using the unknown x². The reason for expressing f as in equation 9 is to simplify the evaluation of inequalities in theoretical analysis, such equation 23 Furthermore, the posterior distribution of f given Di-1 follows GPs. By using this, we can generate sample paths fi...., JM from this postcrior. For cach sample path fy. we evaluate F(x) and use these M evaluations to estimate F)-1[F(=)]] In this way, l can be approximaled from the sampled paths. In contrast, for the expectation measure, the following theorem shows that one can use t itself as a substitute for f.
Theorem 4.3. Under the assumptions of Theorem 4.1
the following holds for the expectation measure:
E Rd
Cone
E rr E[r
S 4
where Co is given in Corollary 4.1
Theorem 1.3 states that when considering the expectation measure as a robustness measure, an upper bound on rr is given, while for other robustness mcasures, cstimation of f is still requirod. If the number of samples M generated from the posterior distribution is sufficienlly large, the estimated f can be expected to be close to the true f, but whether it is possible to accurately derive the true i without estimation remains an important direction for future work. Nevertheless, in the synthetic function experiments conducted in Section 5.1 E[r]] is used as the evaluation metric instead of E[ry]. but the behavior of the convergence of B[ra] to the proposed method has been confirmed in all settings. Therefore, similarly to how an upper bound for E[ra] is given by Theorem 4.3 it expected that some kind of upper bound holds for E[re] in other robustness measures.
In this section, we have presented theoretical guarantees for the expected value of both the regret and the cumulative regret. However, we have not addressed high-probability bounds. Such bounds can nonetheless be readily derived via Markov's inequality. In fact, for a non-negative random variable X, Markov's inequality yields P(X > a) S E[X]/a. By setting a = 8 3''E[X,, we obtain that X S [[[] with probability at least 1- 8. Hence, for any non-negative value J satisfying B[X] S J, we can conclude that X s 8-1J with probability at least 6. 8. Applying this argument to the regret and cumulative regret, which are both
non-negative, and invoking Theorems and 4. 1.2
we obtain the following result:
Theorem 4.4. Let 8 E (0, 1). Under the assumptions of Theorem 4.1 for any t 2 1, the following inequality holds with probability at least 1 5:
R. S 25-11
Σ Giti
Σ 2 Xij (1Ca.u)) 1-//1/ ) (C (Cin))
where hx(-) and all coefficients are as defined in Theorem 4.1 In addition, for the index i defined in equation g the following inequality holds with probability at least 8:
r; S 28-1
Σ 1=1
Sihs
Σ i
1
81
2 Aas (1C2my)) 1/1/12 1- (Crr)ba12)
Although Theorem 4.4 provides high-probability bounds, these bounds are not tight with respect to 8. In fact, the right-hand sides of both inequalities depend on 8-1. In contrast, most high-probability bounds based on the GP-UCB framework such those in Srinivas et al. (2010) involve a log(6-1) term instead of 8-1. Therefore, deriving tighter high-probability bounds with respect to 8 than those in Theorem 4.4 remains an important direction for future work. Nevertheless, 8 is a probability parameter specified in advance by the user and is constant. Therefore, when considering the order with respect to & by treating 6 as a constant, the high-probability bound in the proposed method is lighter than that in GP-UCB-basee methods such as (Srinivas et al. (2010). For example, the standard BO on the input space X' with no input uncertainty is equivalent to maximizing the expectation measure on X' Ω using [Ω] 1. From Theorem 1 of Srinivas al. (2010), the order of the high-probabilityy upper bound for the cumulative regret is vty log t, whereas in the proposed method, it is Vhy according to Corollary 4.1 Furthermore, when considering the
12

---

Published in Transactions on Machine Learning Research (07 (07/2025)
expectation measure robustness measure in the presence of input uncertainty, according to Theorem and 2 in Inatsu et al. (2024a), at time & the order of the high-probability bound for Tr' is Vt-lng, where e' S On the other hand, the high-probability bound for Tr in our proposed method is vt- However, given in Table 1 the definitions of in Sriiivas al. (2010); Inatsu et al. (2024a) and this study differ slightly, so it is important to note that these high-probability bounds cannot be directly compared.
4.1 Extension to Other Settings
In this section, provide results for uncontrollable settings. Furthermore, provide overview of methods and results for extending the proposed method to continuous spaces, and explain issues involved. Details on the extension to contimuous spaces and to general uncontrollable settings are given in Appendix A and
B
Uncontrollable Setting when X' and are Finite We consider the case rolontrollable settings, i.e., w1, wi...., we follow the distribution p and cannot be controlled even during optimization. We assume that wi....; wy mutually independent. The difference between the proposed algorithm in this setting and Algorithm D is only in how w, is obtained. Specifically, in this setting, the acquisition function equation 5 cannot be used, and t sampled from P becomes at time t. We give the pseudo-code for the case where X' and Ω are finite in the uncontrollable setting in Algorithm 2 When Algorithm 2 is performed, similar theorems as in the simulator setting hold.
Theorem 4.5. Assume that the regularity assumption, Assumption 4.1 and equation hold. Suppose that X' and are finite. Also suppose that w,,..., we follow Pt, and fi....,5t are random variables following the chi-squared distribution with two degrees of freedom, where fis W1,.... Wty & are mutually independent. Let Ω (w()), ...... w()), Pj P(w w()) and Punin minisssa Pý, and assume that Puain 0. Define 3, 2 llog(IX' X' 21) + & Let q(a) Σm= Shhs
EE= j=1 \sja"t) be function satisfying is performed, the following holds: 2
Assumption 4.1 Then, under the uncontrollable setting, if Algorithm
Σ 2nd Aej (1C2 1-//12 1- (C'r)
[RR S
2t
Sihi
where f/j = min(ung 1), C
2pmin
C2,, E|0tt//2 and the expectation is taken over all Br In addition, for the expectation, worst-
log(1+Omoted
sources of randomness, including f5é1, Wi...., wR, , case, best-case, a-value-at-riste a-conditional value-at-risk, and mean absolute deviation measures, the fol- lowing inequality holds:
E[Re] < (2 x 2)) + 2)7.
where is 8 for the mean absolute deviation measure and 4 for the other measures.
Theorem 4.6. Under the assumptions of Theorem 4.5 the following holds:
Rd
2n Aa (tC2.wg) 2-/0 ) (C (Crrlt//)
Sih
t
i
1=1
where f given by equation and the function h₂(-) and all coefficients are as defined in Theorem 4.5 addition, for the expectation, worst-case, best-case, a-valuo-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
E[Ra]
S sC /
[7 /i 22)) + 2)%
E rr
t
where C is given in Theorem 4.5 Furthermore, in the expectation measure, the following holds:
E [[
(oggg ( x 12) + 2)7
Bir.]- <
< 4
t
13

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 2 RRRG--CB for robustness measures in the uncontrollable setting when X' and Q are finite.
Input: GP prior (P(O,, k:) for = 1,,,.... do
Generate & from chi-squared distribution with two degrees of freedom
Compute Br 2 log(( (2) + &
Compute Q2-1 w) for cach (x, w) E x Ω
Compute Q()( for each x E X
Estimate de by 2; = arg max p(441((2 ))
Select next evaluation point at by equation Generate we from p
Observe Y/ [a1, w)) Ex point (æa, ())
Update GP by adding observed data
end for
Here, note that by using Theorems 4.5 and 4.6 and Markov's inequality, high-probability bounds similar to those in Theorem 4.4 can also be obtained in this setting.
Extension to Continuous Spaces In this section, we provide an overview of the extension of the proposed method to contimuous spaces. In Algorithm 1 or 2 Br is defined using |X Ω). Therefore, if X or Ω is continuous space, this definition cannot be used directly. In this case, discrelization of the continuous space is necessary, and to perform a theoretically valid discretization, additional assumptions on the differentiability of f, such as Assumption 2.1 in Takeno et al. (2023). are required. In fact, in Appendix A the proposed method extended lo continuous spaces under similar assumptions. However, this approach has two issues. First, to propose a theoretically valid method, is necessary to increase the number of discretized points according to time t, resulting in Br needing be large according to time t, as Theorem A.I Thus, one of the advantages of the proposed method, namely that Br does not need increase according to time t, is lost. Second, icalr valid discretization requires constants such are used to define 3.. However, although these constants 0₁ and bı are determined by the kernel function, their actual values are difficult to calculate, resulting in the need for estimation or heuristic adjustment of these values. Therefore, the advantage of the proposed method, which eliminates the need for estimation or tuning of Br, also lost. Although an extension to continuous space is provided in Appendix A the two issues mentioned above remain, and resolving these issues is an important direction for future work.
and b in Assumption A.T and these
5 Numerical Experiments
In this section, we verify the performance of the proposed method using both synthotic benchmark functions and real-world data on carrier lifetime values of silicon ingots used in solar cells. In all experiments, a GP model with zero mean function is used as the surrogate model. Further details regarding the experimental settings, as well additional experiments not included in the main text, are described in Appendix D
5.1 Synthetic Function
The input space was defined as a subset of [-M, - M-M, MiP;
there each coordinate was uniformly discretized into grid points. Three different configurations of (M, D, s) were considered the
in the experiments: (5, 2, 50), (2.5, 4, 15), and (2, 6,6,7) 7). The black-box function varied depending dimension D. When D 2, f was sample path drawn from GP, referred to the 2D synthetic function. When D = 4, the black-box function was defined as f(11, 22, W1, w2) = fu(m1 + W1, + 0.5w2) (4D synthetic function), where Su(a,b) b) is Himmelblau's function with translation and scaling. For the case D=6, f was defined as the sum of four independent GP sample paths f1....,fe fa (6D synthetic function), where the dependencics of each function were specified as follows: fi on (I1, 4z) f2 on ( 23, wi), fa on (23, W1, W2), and fa on (w1, W2, wz). In each setting, the kernel function k(.,.) used in the GP surrogate model was defined as follows:
14

---

Published in Transactions on Machine Learning Research (07/ 2205)
(2D synthetic function): k(0, 0¹) = exp(1l 22)
(4D synthetic function): k(0, 0*) = exp(110 ||0100-0'11///0000 0')13/10).
(6D synthetic function):
(10 = 1.25 exp
where 0 = (2, T2 0: = (I2, Ty, w1), : 0g3 = (2s. w1, w2) and 0₂ = (W1, W2, wy).
Among these settings, only the 2D synthetic function setting used surrogate model that matched the true black-box function. The remaining two settings intentionally introduced a mismatch between the surrogate model and the black-box function. In addition, all experiments were conducted under the assumption that observations were corrupted by independent Gaussian noise with mean zero and variance 10 10-6, To evaluate robustness, three robustness measures were considered, using the probability mass function p(w) of w defined for each setting:
(EXP): Expectation measure, F(x:) = [a] w)) = Foxp(ar).
(PTR): Probability threshold robustness measure, F(x) = P(f(x, w) 2 h).
(EXP-MAE): Weighted sum of expectation measure and mean absolute deviation,
F(x)= Fexp(x) (x) aBllf(x w) - Fexp(x)]].
In the 2D, 4D, and 6D synthotic function settings, the values of ah) were set (0.5, 1), (0.18, 4), and (), respectively. In this experiment, only the acquisition function was changed, and the evaluation metric was the regret re = F(x*)= - F(t.). To compare performance, nine methods were evaluated, including the proposed method: random sampling (Random). uncertainty sampling (US), Bayesian quadrature (BQ) (Be- land & Nair 2017), BPT-UCB (Twazaki et al. 2021a), BPT-UCB (fixed, BBBMOBO (Inatsu et al. 2024a)
BBBMOBO (fixed), the proposed method (Proposed), and Proposed (fixed). The random method selected (x,, w.) uniformly at random, while US selected (æ,, w:) by maximizing (x, w)). For the remaining seven methods, 2y was selected according to each method's acquisition function. For all methods except BPT-UCB and BPT-UCB (fixed), w, was selected using equation
5 The method for selecting w, in BPT-UCB and BPT-UCB (fixed) is described in Appendix D BQ and BPT-UCB were originally proposed for the EXP and PTR measures, respectively. Although BBBMОBO was designed for Pareto optimization over multiple robustness measures, it can be applied to a single robustness measure as well. The trade-off parameters used in BPT-UCB, BBEMOBO, and Proposed were set to thcoretical values. In contrast, the methods marked with (fixed) used fixed values smaller than the theoretical ones. Note that in the EXP setting, BBBMOBO (fixed) and Proposed (fixed) are the same (see Appendix D for details). Under these settings, single random initial point was selected, and the algorithms were run for 300 iterations. This process was repeated 100 times, and the average 7 was calculated at each iteration. As shown in Figure 2 Random and US, which are not designed to maximize robustness measures, performed poorly in all settings BQ, BPT-UCB, and BPT-UCB (fixed) were effective for EXP and PTR, but their performance for EXP-MAE in the 2D synthetic function was insufficient. This is because these methods are not tailored for EXP-MAE. For BBBMOBO and Proposed, as well as BBBMОBO (fixed) and Proposed (fixed), performance tended to be similar. This is because the only difference lies in whether a, set to ã; or selected via equation aside from the trade-off parameters. For BBBMОBO (fixed) and Proposed (fixed), using smallle-than--theerettill trade-off parameters led to improved practical performance, achieving favorable results in many settings. However, in the 4D synthetic function under the EXP measure, regret was not fully reduced. One reason is that the surrogate model fails to correctly express the true black-box function. Furthermore, small tradc-off parameters limit exploration, often resulting in convergence to local optima. In fact, Figure 5 of [rrinvas et al. 2010) shows the results of BO (Mean Only) using only the posterior mean, and Figure 5 of Inatsu et al. (2024a) compares the differences 8 for the expectation mcasure, suggesting that in both cases, small tends to lead to local optima. In contrast, the Proposed method, by employing random trade-off parameters, occasionally explores more broadly. This increases the likelihood of escaping local solutions and,
15

---

Published in Transactions on Machine Learning Research (07 (025)
20 synthetic function (EXP)
2D synthelic function (PTR)
20 synthotic function XP-MME)
1e-00
Iex00
Tex00
-2-02
1e-02
Roegret
04-04
1e-04
1e-48
1e-08
1e-48
RFT--U3 (ted)
UTT-CC
TTT-CC rlad
1e-08
Ie-08
EEGINCEO Hind
16-08
BEGHOED rlad
50
100
150
200
250
300
50
100
150
200
250
300
50
100
150
200
250
300
Ineration
Ioortion
Ioortion
synthatic function (EXP)
synthetic function (PTR)
synthatic function [EXP (XP-MAE)
Ie+01
Bev0s
7e401
le-05
Je-03
7e-01
Rinker
RFT-CC3
ART-LER
ECGPO00
EEGINCEO
EEGHOED
Frppaed
Frageadd
Fragased
Pegmsnl/Beett
50
200
250
200
50
200
Iteraton
Iteralin
lleraiin
6D synthetic function (EXP)
6D synthetic function (PTR)
60 synthetic function (EXP (EXP-MAE)
1e:0
1e401
1640
2e-00
Ze400
7e400
J4-01
1e-01
14-01
Randeer
ESOPCEO
ESCINCEO
EEOPOED
Fripaied
Frigeied
14-03
Fragiied
50
100
200
250
300
50
100
200
250
300
50
100
200
250
300
Figure 2: Average regret across 100 simulations for each method. Top, middle, and bottom rows correspond 2D, 4D, and 6D synthetic function settings, respectively. Left, center, and right columns show results for EXP. PTR, and EXP-MAE, respectively. Since BBBMOBO (fixed) and Proposed (fixed) are the same in EXP, only Proposed (fixed) is displayed in the figures on the left column. Error bars represent twice the standard error.
consequently, improves performance. This demonstrates a key advantage of using randomly varying trade-off parameters beyond the theoretical guarantees. The trade-off parameters in BBBMOBO are on the order of Olog(t))X' x 2))). Since they are often larger and more conservative than the 3, values used Proposed, Proposed generally outperformed BBBMOBO, except in the 4D synthetic function (EXP) setting. Overall, the Proposed method performed comparably to better than the baseline methods across most settings.
16

---

Published in Transactions on Machine Learning Research (07/2025)
5.2 Synthetic Function Experiments under Uncontrollable Settings
In this section, changed the experiment in Section 5.1 to the uncontrollable setting, where we cannot be selected and is obtained randomly according to the probability mass function p(w). The method for selecting 2e was the same as in Section 5.1 As in Section 5.1 Figure 3 shows that the proposed method oulperforms the comparison methods in most settings. On the other hand, in the experiments in Section 5.1 the regret of Proposed (fixed) did not decrease in the 4D synthetic function (EXP), while in Figure 3 the regret decreased more than Figure [ This because w could not be selected, and as a result of random sampling, more exploration was performed, making it possible to avoid local solutions.
5.3 Carrier Lifetime Data
In this section, we conducted experiments using the carrier lifetime dataset (Kutsukake et al. 2015 which quantifies the performance of silicon ingots used in solar cells. The original dataset includes 6586 two- dimensional coordinates on the surface of a silicon ingot and the corresponding carrier lifetime values, denoted by [T z2) at each coordinate (2), In this experiment, we focused on the subset X = {(2a+6, 6, 26+6) S a I 88, I b S 72], which includes 6336 of these points. The set of design variables X was defined as a subset of X, specifically X' = {(22a 4, 18b - 2) I S a 8, 1 < < 8). In addition, we defined Ω {(2a 12, 26- 10) 1 S 11,1 b S 9}. This results in |X] = 64, |S2] = 99, and |X x Q2 6336, with the set X' 2 {- w x E X, E Ω}} equal to X. For each input (21, #1, W2) E X x Ω the black-box function was defined as f(11, 22, w1, W2) = LT(x1 + w1. 22 + W2). The kernel function used in the surrogate model was the Matérn 3/2 kernel, defined as follows:
k((21, F2; w1, W2), (41, 222 w/, w²2)) = 4 (1 1 03
v3 0'1l2
exp
25
25
where 0 = (x1 + 22 + w2) and 0' = (+² + w/, 222 + w2y) The experiment was performed under the assumption of no observation noise. However, to ensure numerical stability when computing the inverse of the kernel matrix, a nominal noise variance of hosse = 10-6 was added. The same three robustness measures and nine methods as described in Section 5.1 were employed. The probability mass function was set to p(w)= = 1/99, and the parameters (h, a) (2.9,4) 4). Under this setting, one initial point was selected at random, and each algorithm was run for 500 iterations. This procedure was repeated 100 times, and the average regret was computed for each iteration. As shown in Figure E the Proposed method demonstrated performance comparable to that of the baseline methods, even on the carrier lifetime dataset.
6 Conclusion
In this paper, we proposed a new method for BO of robustness measures for black-box functions with input uncertainty. The proposed method estimated the optimal solution using posterior means, sampled the parameters of GP-UCB from probability distribution, and determined the next evaluation point based on the estimated solution, credible intervals, and posterior variance. In Section $ we provided upper bounds on the expected regret and cumulative regret and showed that their orders for commonly used robustness measures, including the expectation measure, were O(Vrs/t) and O(Vhx), respectively.
Compared to existing methods, the proposed method offered the following three advantages. First, unlike the mothods in Beland & Nair (2017): [wazaki et al./ (2021a), which were tailored to specific robustness measures, our method was applicable more generally to any robustness measure satisfying the condition in equation 2 Second, in contrast to the method in Inatsu et all (2024a), which was also not restricted to particular robustness measure, our method did not require hyperparameters for the acquisition function. Third, we derived the order of the expected regret and cumulative regret defined in terms of the estimated solution based on the posterior mean. To the best of our knowledge, this study is the first. to establish expected (cumulative) regret bounds for various robustness measures.
However, the proposed method also had certain limitations. Most significantly, while it randomly replaced the parameters of GP-UCB, key feature of the method, this mechanism alone did not significantly improve
17

---

Published in Transactions on Machine Learning Research (07 (025)
20 synthetic function (EXP)
20 synthelic function (PTR)
2D synthotic function XP-MAE)
1e-00
Iex00
Te400
-2-02
1e-02
1e-04
1e-48
1e-08
1e-46
BFT-UC3 (ted)
UTT-CC
TTT-CC rlad
1e-08
SCOPOEO Mard)
Ie-08
EEGINCEO Mind
16-08
BEGHOED riad
50
100
150
200
250
300
50
100
150
200
250
300
50
100
150
200
250
300
Iorrtonn
Iooration
Borotion
synthatic function (EXP)
synthetic function (PTR)
synthatic function [EXP EXP-MAE)
1e+01
Bev01
7e401
1e-0s
Je-03
7e-01
Rinker
AFT-IC3
ART-LER
ECGPR00
EEGINCEO
Frppxed
Frigeaad
Fragaadd
Pegmsnl/Bect
50
200
50
200
250
50
200
250
Iteraion
Rteslon
lteraiin
6D synthetic function (EXP)
6D synthetic function (PTR)
60 synthetic function (EXP-MAB
1e:0
1e401
10403
2e-10
Ze400
7e400
1e-01
1e-01
10-01
Rander
ESOPCEO
ESCINCEO
EEOPOED
Fripaied
Frigeied
14-03
Fragiied
50
100
200
250
300
50
200 250
50
100
200
250
300
Figure Average regrets across 100 simulations under the uncontrollable sctting for cach method. Top. middle, and bottom rows correspond 2D, 4D, and 6D synthetic function settings, respectively. Left, center, and right columns show the results for EXP, PTR, and EXP-MAF, respectively. Since BBBMOBO (fixed) and Proposed (fixed) are the same in EXP, only Proposed (fixed) is displayed in the figures the left column. Error bars represent twice the standard error.
practical performance. Additionally, although we derived high-probability bound for the thcorctical anal- ysis, the appearance of 5-1 in the bound, which was not light compared to typical GP-UCB-based bounds with respect to ò, posed limitation. Furthermore, although the proposed method can be extended to continuous spaces, it has the disadvantage of losing the advantages of the proposed method, namely, that 3, does not need be adjusted and that no increase in required. Finally, it was generally difficult caleulate the best. index i among the estimated optimal solutions d;.
18

---

Published in Transactions on Machine Learning Research (07/2025)
Carrier Ilfetime data (EXP)
Carrier lifetime data (PTR)
Carrier ilfatime data (EXP- EXP--AEE)
1e40
1eH0
1e401
1e+00
1e+00
14T-0C3 taad
1e400
-0-00
Ie-
01
10-01
1e-02
1e-02
BFT-UC3 (tud)
TTT-CC rladd
Ie-03
16-03
LEGHOED riad
100
200
300
400
500
0
100
200
300
400
500
100
200
300
400
500
ioraton
nooatin
Morotin
Figure 4: Average regrets on carrier lifetime dataset over 100 simulations for each method. Left, middle, and right columms correspond to results for EXP, PTR, and EXP-MAE, respectively. Since BBBMOBO (fixed) and Proposed (fixed) are the same in EXP, only Proposed (fixed) is displayed in the figures on the left column. Error bars represent twice standard error.
Addressing these disadvantages remains important direction for future study.
Acknowledgments
This work was supported by JSPS KAKENHI (JP20H00601,JP2331060)) and JST ACT-X (JPMJAX24C3).
References
Justin Beland and Prasanth B Nair. Bayesian optimization under uncortainty. In NIPS BayesOpt 2017 workshop, volune 2, 2017.
Iijaa Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher, Truncated variance reduction: A unified approach to Bayesian optimization and level-sct estimation. Advances in neural information processing systems, 29, 2016.
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. Advances in neural information processing systems, 31, 2018.
Brent Bryan, Robert C Nichol, Christopher R Genovese, Jeff Schneider, Christopher J Miller, and Larry Wasserman. Active learning for identifying function threshold boundaries. Advances neural information processing systems, 18, 2005.
Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. Tn H. Tarochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Н. Tin (ods.). Advances in Neural Information Processing Systems, volume 33, pp. 20130-20141. Curran Associates, Inc., 2020. URL https://prroceedings www.pss.capp.p..ppppprrr filles/paper/222/fiiee pddf
Emile Contal, David Buffoni, Alexandre Robicquct, and Nicolas Vayatis. Parallel Gaussian process opti- mization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 225 240. Springer, 2013.
Alkis Gotovos, Nathalic Casati, Gregory Hitz, and Andreas Krause. Active learning for level estimation. Third
In Proceedings of the Twenty- Third international joint conference on Artificial Intelligence, pp. 1344-14411 13500
2013.
19

---

Published in Transactions on Machine Learning Research (07/2025)
José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27, pp. 918 926. Curran Associates, Inc., 2014.
Yu Inatsu, Shion Takeno, Masayuki Karasuyama, and Ichiro Takeuchi. Bayesian optimization for distribu- tionally robust chance-constrained problem. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Leurning Research, pp. 9602 9621. PMLR, 17-23 Jul 2022. URL Sttps::/proceediie
mlr, press/v162/inatsuu22 html
Yu Inatsu, Shion Takeno, Hiroyuki Hanada, Kazuki Iwata, and Lchiro Takeuchi. Bounding box-based multi- objective Bayesian optimization of risk measures under input uncertainty. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4564 4572. PMLR, 02 04 May 2024a. URL
mlr pwwps///ss8 inatsn24a..nee..ee..
Yu Inatsu, Shion Takeno, Kentaro KUTSUKAKE, and Tchiro Takeuchi. Active learning for level set esti- mation using randomized straddle algorithms. Transactions on Machine Learning Research, 2024b. ISSN 2835-8856. URL https://opennrevier
Shogo Iwazaki, Yu Inatsu, and Ichiro Takeuchi. Bayesian quadrature optimization for probability threshold robustness measure. Neural Computation, 33(11))3413-3440 2021a.
Shogo Iwazaki, Yu Inatsu, and Ichiro Takeuchi. Mcan-variance analysis in Bayesian optimization under uncertainly. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th Internalional Con- ference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, html.
pp. 973 981. PMLR, 13 15 Apr 2021b. URL http:::/ppocceeednngg mlr. /ttpp//ceeeeaaaaaa..reeer///////
Kirthevasan Kandasany, Jell Schneider, and Barnabés Póezos. High dimensional Bayesian optimisation and bandits via additive models. In International conference on machine learning, pp. 295 3044.. PMLR, 2015.
Kirthevasan
Kandasamy, Gautan Dasarathy, Junier B Oliva, Jeff Schneider, and Barnabés Póczos. Gaussian process bandit optimisation with multi-fidelity evaluations. Advonces in neural information processing systems, 29, 2016.
Kirthevasan Kandasany, Gautam Dasarathy, Jeff Schneider, and Barnabás P6czos. Multi-fidelity Bayesian optimisation with continuous approximations. In International conference on machine learning, pp. 1799 1808. PMLR, 2017.
Johannes Kirschner, Liija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenly Third Interna- tional Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learn- ing Research, pp. 2174-2184. PMLR, 26 28 Aug 2020. URL kirschner20a.hn html
mlr. prtsss/ve8//
Shunya Kusakawa, Shion Takeno, Yu Inatsu, Kentaro Kutsukake, Shogo Iwazaki, Takashi Nakano, Toru Ujihara, Masayuki Karasuyama, and Ichiro Takeuchi. Bayesian optimization for cascade-type multistage processes. Neural Computation, 34(12):2408-2444 2431, 2022.
Kentaro Kutsukake, Momoko Deura, Yutaka Ohno, and Ichiro Yonenaga. Characterization of silicon in- gots: Mono-like versus pirh-performance multierystalline. Japanese Journal of Applied Physics, 54(8S1): 08KD10, 2015.
Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference: Novosibirsk; July 1-7, 1974, pp. 400-404. Springer, 1975.
20

---

Published in Transactions on Machine Learning Research (07/2025)
Quoe Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Optimizing condi- tional value-at-risk of black-box functions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and
J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4170 files/paper)
4180. Curran Associates, Inc., 2021a. URL https:://procedddin wtw.:/dpinnnnnniis..oo.mem www.:eeuurrccpppppeeee 220/5111220ee2ee6666444000506002 pdf
Quoc Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Value-at-risk oplimiza- tion with Gaussian processes. In International Conference on Machine Learning, pp. 8063 8072. PMLR,
2021b.
Paul Rolland, Jonathan Scarlett, Tija Bogunovic, and Volkan Cevher. High-dimensional Bayesian optimiza- tion via additive models with overlapping groups. In International conference on artificial intelligence and statistics, pp. 298-307. 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(():148-11) 175, 2015.
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 International Conference on Machine Learning, ICML'10, pp. 1015 1022 USA, 2010. Omnipress. ISBN URL http://dl www.argm...a....................
acm org/ citation. cfm/id ottp://ccaaaacoo..coooaa...3310. 3104451
Shion Takeno, Yu Inatsu, and Masayuki Karasuyama. Randomized Gaussian process upper confidence bound with tighter Bayesian regret bounds. In International Conference on Machine Leurning, pp. 14449003355.. PMLR, 2023.
Sebastian Shenghong Tay, Chuan Sheng Foo, Urano Daisuke, Richalynn Leong, and Bryan Kian Hsiang Low. Efficient distributionally robust Bayesian optimization with worst-case sensitivity. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 21 111180221200 PMLR, 17-23 Jul 2022. URL httpp::/pproceeding.. mlr pprass/v62/taay//// html
Scbastian Shenghong Tay, Chuan-Sheng Foo, Daisuke Urano, Richalymn Leong, and Bryan Kian Hsiang Low. A unified framework for Bayesian optimization under contextual uncertainly. The Twelfth International Conference on Learning Representations, 2024. URL httpp://opparrrriee.eet/// wtw.oo/rw.et//oouuneee. ooNNk
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285 285-294 1933.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. the MIT Press, 233) 2006.
Jian Wu and Peter Frazier. The parallel knowledge gradient method for batch Bayesian optimization. Tn D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL httpsatt///oocoeediiiie www.:ngs...rriss...o cc/ paper_ http:ppppppopeeeeeeoccooooooeeee
pddf
Marcela Zuluaga, Andreas Krause, el al. e-pal: An active learning approach to the multi-objective optimiza- tion problem. Journal of Machine Learning Research, 17(104):1-2 -2, 2016.
21

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 3 RRGP-UCB for robustness measures when X' is continuous and Ω is finite.
Input: GP prior GP(O, k), (n(() ( 1 1 x K2
for t= l, do
Generate & from chi-squared distribution with two degroes of freedom
Compute 3. 2 log (g E
Compute Qr-1 w) for each (xx w) E X $2 Compute Qt-1(x) for each a E X
Estimate &t by é; arg maX p Select next evaluation point I; by equation Select next evaluation point w; by equation Observe Y/1 = f(;; wi) + Et at point (æ), wt)
Update GP by adding observed data end for
Appendix
A Extension of the Proposed Method to Continuous Settings
In this section, consider the case where X' and Ω are not finite sets. We consider the following three cases scparately: Only X' is continuous, only Ω is continuous, and both X' and Ω are continuous.
A.1 Extension Continuous Settings when X' is Continuous and Ω is Finite
Let X' be continuous set, and let Ω be finite set. Suppose that X' is a compact and convex set with X C r0, In this setting, the only difference between Algorithm ] and an extension of the proposed method
is the distribution 3.. Specifically, by using (2) with 1 1 xi S <62 ..., we define Bg = 2 kq + Et-
Theoretically valid values of x( , ,.. ...)
and the theoretical analysis given in Appendix A.1.1 The
pseudo-code for the case when X' is continuous and Ω is finite is provided in Algorithm 3
A.1.1 Theoretical Analysis in the Continuous Setting when X is Continuous and Ω is Finite
To derive the theoretical guarantee, we introduce additional two assumptions. Assumption A.1. There exist a1 bj > 0 such that
(x w²) Oz,
(- by (-()))
sup æEX
) s an exp
for jE (1,...,,4l
d1). 1)),
Ω
Assumption A.2. There exists a non-dccrcasing, concave function (a) such that di (0) = 0 and
(p(f(x,-)) plf(2', ,)) S
max [f(z, w) - f(x', will for α. x' e X. wel!
note that when w is fixed, f(x, w) is a GP on X. In GP-based BOs, similar assumptions (2010); Takeno el al. (2023) Here, for the Bayes risk (expectation), worst-case, best-case, a-value-at-risk a-conditional
For Assumption A.1
to Assumption A.1 are used in, for example, Srinivas el al.
ri-ues and mean absolute
deviation measures described in Table in Inatsu et al.
(2024a). we can use (m) in the table as (i(a) in Assumption A.2 Details are described in Appendix C.5] Then, the following theorem holds.
Theorem A.1. Assume that the regularity assumption, Assumptions 4.1 A. and A.2 and equation 2 hold. Suppose that &,,...,&e are random variables following the chi-squared distribution with two degrees of freedom, where ,.,,,..,,,,I,,--..... (F/2))d:)((() and define &. = 2 2lg (1) + & Let (a) and ((a) ΣEn Cchi EEe Aiga be functions
are mutually independent. Let (1) = (1 [b,dirt? ( /Tog(a di [9]] +
22

---

Published in Transactions on Machine Learning Research (07/2025)
satisfying Assumptions A.2 and
4.1
respectively. Then, if Algorithm is performed, the following holds:
π²²
#1 2 Xis (tC2uns,) ) /22 (C(n))
E R Σ
tqı
+
2t
Si
m Crungi E1 /// (2-1)))) and the expectation is taken over all sources of randomness, inchuding f. E.E....., Ev: .1.....,3r.
where V/3 = (in, 11.C1
Unlike the case where X' is finite, since Cz diverges with the order of (log t) (C 2 also diverges with the order of (log t) Hence, even if lime 7t/ = 0, that is, Y is sublinear, if n diverges with the order of (log1)"1//"/ or higher, the argument for the function h₂(-) diverges to infinity. On
the other hand, if the order of 7/t is slower than (loge)"u/"", then lim B[R,]/t under the assumptions
that q-(-) and h-)))) are continuous at O. Next, as in the case of X, for six robustness measures including the expectation measure, the following corollary holds.
Corollary A.1. Under the assumptions of Theorem A.1 for the expectation, worst-case, best-case, o-value- at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
E R <
6 +
C4t2looo (1)) + +2)))
where C is 2 for the mean absolute deviation measure, and 1 for the other measures.
Furthermore, for the index given by equation the following theorem holds.
Theorem A.2. Under the assumptions of Theorem A.I the following holds:
E rrd
S
[ed t
π
Sihi
Σ 3=1
2 Xis ( (Crx))//1
6t
t
1=1
where & given by equation g and functions (-), 1x(-) and all coefficients are as defined in Theorem A.1 Moreover, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
π +4V
C1 (2 xx + 2)7
Elr C
where C is given in Corollary A.1 In addition, for the expectation measure, f satisfies f= and
Bird = E[rd] S n² + +41 (2 Ri (1) + 2)
60
Proofs are given by using the same argument as in the proof of Theorem 4.2 and 4.3
A.2 Extension to Continuous Settings when X' is Finite and Ω is Continuous
Let X' be finite set, and let Ω be a continuous set. Suppose that Ω is compact and convex set with Ω C r], In this setting, the difference between Algorithm [ and an extending method is not only the difference in the distribution of B.. Specifically, the method for estimating the optimal solution & and the method for selecting a, also need to changed.
Let > and let Ot be finite subset of Ω2 For E St let [w], be the element of Pr closest to w. Then, for (x, w) E X x Ω2 we define u4 (xx w), 17 (x, w) and wi_1 (xx w) as follows:
p (xx, w) pe- 1 (æc, (w)+)), it_ (2,, w) 4- (2r, (w)+) m_, (w)::) /3/22 1//0,__(000 (w)::) i (x, w) ( [w)+) (x, (w, (w]:) + B/ o 0 [w):).
23

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 4 RRGP-UCB for robustness measures when X' is finite and Ω is continuous.
Input: GP prior GP(O, k), {n/ JeNN. 1 1 ( K2 < finite subsets Q, 92.,... C for t= 1.2,.. do
Generate & from chi-squared distribution with two degroes of freedom
Compute B 2 log x(()) + E
Compute (2, (2x, w) for each (x, w) E E x Ω
Compute (x) for each E.
Estimate é by d arg max 0(4111(0) Select next evaluation point 2; by equation 12
Select next evaluation point w, by w, = arg max (-1 w)
Observe y/1 = f(;, w;) + Et point (xx, w,)
Update GP by adding observed data end for
Furthermore, for each æ, we define set of functions with respect to w, ( as follows:
Gz-((x) (g(xx.) for all w Ω g w) Q/ (x)
where (a, = 1/-1( (z, w), (1), inequalities:
u/ (ar, w)]- Suppose that lob,_ and 1 satisfy the following (x) < inf p ))
sup p(g(z, +) I ucb]_1(x)
(10)
ala, ala,))G)__
a( Je (x)
For commonly used robustness measures described Table in Inatsu et al. (2024a), we can use lcb["] (ax) and (eb["(((2) (2x in the table as leb(_1(x) and ucb]_1(x), respectively. Using this, we define the credible interval (.)(()) = ( (x), (x)] Here, we emphasize that Q[-(x)) is the credible interval for p(f) (xx-)) (z), not F(z), where fl (ax, w) f(x, [w]cc. We define the estimated solution a by using (x, as follows:
: arg max ((11_1(0,)))
(11)
#EX
The next point to be evaluated æ, is selected follows.
Definition A.1 (Selection rule for when Ω is continuous). Suppose that E,, are random variables following the chi-squared distribution with two degrees of freedom, where f, fi...., & are mutually
independent. For the sequence xx()) with 1 < x2 < K2 S ..,, we define 3, log (2) + & Then, for
(2)
lcb/_,(x) (x) and ucb[_ (x) satisfying equation 10 and & given by equation we select æ, as follows:
Ct arg max (ueb) (ueb/_1(w) (c))
(12)
we
where a/ arg max (ucb[_,(') maxxxx lob (x))+.
For Wo, the same rule as in Algorithm [ that is, is selected by
w: arg max max (Z w).
wen
The pseudo-code for the proposed method is provided in Algorithm
A.2.1 Theoretical Analysis in the Continuous Setting when X' is Finite and Q is Continuous
First, introduce the following two assumptions.
Assumption A.3. There exist az by > 0 such that
Ōf(x,u) w)
(-
PP sup wes
L
< a2 exp
for j db...,,d,.. E X.
Owj
br
24

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Assumption A.4. There exists non-decreasing concave function 92(a) such that 92(0) 0 and
lo(f(x,))) - (lf. s 92
max (x, w) - f(x,, [a]i))
well
for any E X, 94 and ((x,w)
For Assumption A.3 if x is fixed, then f(z, w) is GP on Ω. Hence, in the case of Assumption A.1 obtain sufficient condition for Assumption A.3 by using the derivative of the kernel function. Furthermore, for Assumption A.4. we can use (a) in Table 4 in Inatsu et al. (2024a) 92(a) if the target robustness measure is the Bayes risk (expectation), worst-case, best-case, a- a-value-at-risk, o-conditional value-at-risk, or mean absolute deviation measure described in the table. Details are given in Appendix C,5 In addition, for the optimal solution x* arg max F(x) and estimated solution $/, we define the regret r! and cumulative regret R! as follows:
r =(xx)) - F(+)), R
Here, for ueb|_ (2te,, leb|_ and 28,/2 oe- 1 (az,, ue), we introduce the following assumption. Assumption A.5. There exists function q² (xr) Q such that
ucbf_ (a.) lcb, (a+)) S q (2.5 WEfl
max 1 w))
for any 1 1, Be and 0 w)
As in the case of q(a), for the Bayes risk (expectation), worst-case, best-case, a-valuc-at-risk, a-conditional value-at-risk, and mean absolute deviation measures described in Table 4 in Inatsu et al. (2024)), we can use ((") in the table (a). Then, the following theorem holds.
and and equa- Theorem A.3. Assume that the regularity assumption, Assumptions A.3 tion 10 hold. Let -. = (yloo(t((//((azzlll
+ vT/2)], and let S4 be set of discretization for Ω with each coordinate equally divided into T/. Suppose that Ee are random variables following the chi-squared distribution with two degrees of freedom, where (,,1,-..,,,,1,,.---- & mutually indepen- dent. Let xx(2) [bzdbr(((/lll((addd)]] (log(a2d2)(x1)) + (= and define 3. = 2 2og x
+ fc. Let g2(a) and
(a) = Σi= G EE Agjans) be functions salisfying Assumptions A.4 and A.5 respectively. Then, if
Algorithm 4 is performed, the following holds:
E[R]] 21qp
21
2 Ais (1C2ueo)) 1-/ (Cir))(/1)
66
E1 (2-)))))))) and the expectation is laken over all
where b/y = min 11.C Tog(1+o moine)
C2.
sources of randomness, inchuding f, E........ 31 ,,....,,p..
3r.
Here, since Cr diverges with the order of (log 1) (220/(2-15)) if t diverges with the order of (10g
higher, the argument for the function h! (.) tends to infinity. On the other hand, the order of 7s is slower than t (log (loge) "'yy'" lim E[R]]/t = 0 holds if q2(-) and (.())) are continuous at O. Next, for six robustness measures including the expectation measure, the following corollary holds.
Corollary A.2. Under the assumptions of Theorem A.3 for the expectation, worst-case, best-case, a-value- at-risk, a-conditional value-at-rist riskk and mean absolute deviation measures, the following holds:
72 ( + Cit(2log x3 + 2)7
E R < C
where C is 2 for the mean absolute deviation measure, and 1 for the other measures.
25

---

Published in Transactions on Machine Learning Research (07 (02))
Here, we define i as follows:
i arg min F+-1(F(x")) F(+.).
(13)
15ig
Then, the following theorem holds. Theorem A.4. Under the assumptions of Theorem
A.3
the following holds:
E[R]]
2qp
n
Sih!
7
Σ j=1
s;
2n Ai (1C2.)n))
1/x0// (Cin)
67
==1
where f is given by equation 13 and functions 92(+), (.) and all coefficients are defined in Theorem A.3 Moreover, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
n²
C1 log mi (2) + 2)
E|r]] SC
+ 4V
(14)
3t
where C is given in Corollary A.2
Proofs are given by using the same argument in the proof of Theorems 4.2 and 4.3 in the expectation measure. Under the expectation measure, since á corresponds to the posterior mean of Fl (z),, there is gap with the index given in equation 13 As result, even in the of the expectation measure, f does not necessarily equal Nevertheless, the upper bound of E[r[] can be expressed as the right-hand side in equation 14 plus 2t-
Finally, consider
Theorem A.5. Under the assumptions of Theorem A.3. for the expectation measure, the following holds:
n²
Ci C2 ki (2)
2)7
+
+4V
2 3t
The proof is given in Appendix C.9
A.3 Extension to Continuous Settings when X' and Ω are Continuous
Let X' and Q be continuous sets. Suppose that both X' and Ω compact and convex sets with X' x Ω rj, Let d = di +dg. In this setting, there is difference from Algorithm in terms of implementation, but the way that the partition of and theoretical choice of n; different. Therefore, by replacing the notations in Algorithm we show the pseudo-code of the proposod method in Algorithm
A.3.1 Theoretical Analysis in the Continuous Setting when X' and Ω are Continuous
To derive the theoretical guarantee, we introduce the following two assumptions. Assumption A.6. Let X θ and (æ, w) 0. Then, there exist az, by such that
af(0) 00,
(-(#1
I 2 for j E dl.
P sup .e0
> ( ag exp
byg
Assumption A.7. There exists a non-decreasing and concave function vz(a) such that ga (a()) = and
le(((x, :) - (z, S 43
max [x w) (xx [
((s(x,))) pl5 ((x)e,))) ))1 < ds
[fx un) [[[=)), [m)}+)]]
max
wen
for any E X, 2t and f(x w).
26

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 5 RRGG-UCB for robustness measures when X' and Q are continuous.
JIEN. 1 1 x K2 (3) S finite subsets Q2, I2.... C Input: GP prior GP(O, k); (N(() J.NN for t= 1,2,... do
Generate & from chi-squared distribution with two degroes of freedom
Compute B 2 log (()) +
Compute (2, (2c, w) for each (x, w) E E x Ω
Compute (x) for each E.
Estimate é by d arg max P(u4-1 (x.
Select next evaluation point 2; by equation 12
Select next evaluation point w, by w, = arg max pi-1(1r) w)
Observe y/1 = f(x, ()) + Et point (xx, w;)
Update GP by adding observed data
end for
For Assumption A.7 we can use (a) in Table 4 in Inatsu et al. (2024a) as 43(a) the target robustness measure the Bayes risk (expectation), worst-case, best-case, a-value-al-risk, a-conditional value-at-risk, or mean absolute deviation measures described in the table. Details are described in Appendix C.5) Then, the following theorem holds.
Theorem A.6. Assume that the regularity assumption, Assumptions A.5
A.6 and A.7 and equation 10
hold. Let नt (ggrr(((/logaaadl) + v and let X x Q be set of discretization for X Ω with each coordinate equally divided into ir. Suppose that &I....,e are random variables following the chi- mutually independent.
squared distribution with two degrees of freedom, where f.
Let (3) = (1 + F yod' and define B, 22og (3) + te. Let qa(a) and (a) = - GAA (Σ)= Acja"ti be
functions satisfying Assumptions and A.5 holds:
respectively. Then, if Algorithm 5 is performed, the following
E[R.] < 2tq3
π
+
2t
Sih!
Σ 2 Aay (C) (C1n)%//33
6t
where v/j = min 1}. C1 = log(1+a C2.,, = 1/3////22 and the expectation is taken over all sources of randomness, inchuding f, F,.1...., Et. S1......
The proof is given in Appendix C.10 Here, since C2 diverges with the order of (log t)/u/(2-// w4y), the order of Tt. is (1 higher, then the argument for the function k((+)) tends to infinity. On the other
hand, if the order of 7/e is slower than (loge) " lim E RiR]]/t= 0 holds if qs(-) and h.(+) are continuous at 0. Next, for six measures including the expectation measure, the following corollary holds.
Corollary A.3. Under the assumptions Theorem A.6 for the expectation, worst-case, best-case, a-value- at-risk, a-conditional valuo-at-risk, and mean absolute deviation measures, the following holds:
2² + 41 E < d (
x + 2)7c
where C is 2 for the mean absolute deviation measure, and 1 for the other measures.
Furthermore, for f given by equation 13 the following theorem holds.
Theorem A.7. Under the assumptions of Theorem A.6 the following holds:
B t
π
n Aay (tC2mg,)) 1-////2 2- (Ci (112)
E
<
2qs
+ 2
Sih!
6t
i=1
/=1
27

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 6 RRGP-UCB for robustness measures in the uncontrollable setting when Ω is finite.
Input: GP prior GP(O, k); finite Ω2 {14 heN, S x K2
(4)
for t= 1, do
Generate & from chi-squared distribution with two degroes of freedom
Compute 3. 2 log ((4)) + E
Compute Qr-1 w) for each (xx w) E X $2 Compute Qi-1(x: for each a E E
Estimate &t by é; arg m p(uc-1(
Select next evaluation point It by equation Generate wy from P*
Observe Y/1 = f(x;; wi) + E, at point wx)
Update GP by adding observed data
end for
where i is given by equation 13 and functions q3(+), ()()) and all coefficients are defined in Theorem A.6. Morcover, for the expectation, worst-case, best-case, o-valuc-at-risk, a-conditional value-at-risk, and mcan absolute deviation measures, the following holds:
π
C C2 N4 (3) + 2)
E < C
4V
3/
where C is given in Corollary
A.3
The proof is given by using the same argument as in the proof of Theorems 4.2 and 4.3 Finally, for the expectation measure, the following theorem holds.
Theorem A.8. Under the assumptions of Theorem A.6. for the expectation measure, the following holds:
n
C2 ki + 2)7
<
+
v
31.
As in Appendíx C.9
can prove Theorem
A.8
B Extension of the Proposed Method to Uncontrollable Settings
In this section, we consider the case of uncontrollable settings, i.e., Wi...., we follow the distribution Pd and cannot be controlled even during optimization. Hereafter, we assume that Wi...., We are mutually independent.
B.1 Extension Uncontrollable Settings when Ω is Finite
Let Ω be finite set.. In this case, if X' is finite continuous, the only difference between the proposed method and Algorithmm 1 or is whether or not w, is sampled from pa. Moreover, if we set ( = | x ?
in Algorithm 3 we can express the case when X' finite, i.e., Algorithm [I We give the pseudo-code for the case where Ω is finite in the uncontrollable setting in Algorithm 6 Note that the & in Algorithm T includes
both the finite and continuous cases.
B.2 Theoretical Analysis in Uncontrollable Settings when Ω is Finite
Let Ω (1) w()),, P5 (w -0()) and Puii min SiSS Next, introduce the following assumption.
Assumption B.I. For any j E (I,..., J). Pj 0 holds.
28

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Then, for the upper bound of the incquality for the theoretical analysis for finite continuous X, it is sulficient to replace C1 in the upper bound of the inequality in the results of Section or Appendix A.1.1 with C" = Pmmin C1.
Theorem B.1. Assume that the regularity assumption, Assumptions 4.1 and B.1 and equation hold. Suppose that X' and Ω are finite. Also suppose that Wi...., follow P", and EI,..., are random variables following the chi-squared distribution with two degrees of freedom, where f, Et, w1 wi,...,. Wr.
E are mutually independent. Let xi |x x St), and define Br 2 log Ki
(4) + & Let g(a) be a function satisfying Assumption 4.1 Then, under the uncontrollable setting, if Algorithm i performed, the following holds:
E Shh, (E/=1 == Aıya"t)
R
S 21
Sehis
Σ
2 Nej (1C2
1-//22 (Cnn)a/
where v/j = min 13, 11
C2.ng = EJg, (2 1 and the expectation is taken over all sources of randomness, including f. Wi...., wt ......, Br. In addition, for the expectation, worst- case, best-case, a-valuc-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the fol- lowing inequality holds:
minn
E[Rc] S C (2 2)) + 2)%
where C is 8 for the mean absolute deviation measure and 4 for the other measures.
Theorem B.2. Under the assumptions of Theorem B.1 the following holds:
R4 t
Σ 2 Xa (1C2ws))
1-4//12 (C (C12))6612)
where i is given by equation and the function ha(-) and all coefficients defined in Theorem B.1 In addition, for the expectation, worst-case, best-case, a-valne-at-risk, a-conditional valuo-at-risk, and mean absolute deviation measures, the following holds:
E R[R
Ci(2log(1 22) + 2)%
Bir
SCV
1
where C is given in Theorem B.1 Furthermore, in the expectation measure, the following holds:
E[R.]
(2lggg XX 8 x 21) 2)%,
Eir.]
4
Theorem B.3. Assume that the regularity assumption, Assumptions 4.1 A.1 A.2 and B.1 and equation 2 hold. Suppose that X' and are continuous and finite, respectively. Also suppose that wi...., we follow p*, and E are random variables following the chi-squared distribution with two degrees of freedom, where f, Wi...., Ew,,,....,, ",,,...,,,,,,.........
are mutually independent. Let x = (1+ [b+rddr (Vldire"(loo(aaddd [[]) +
))) and define 3, = 2log nit + ft. Let (a) and g(a) = Σn G/, (E Aya''s be functions satislying Assumptions A.2 and 4.1 respectively. Then, under the uocontrollable setting, if Algorithm f performed, the following holds:
Σ 201 Aij (tC2, .) 1-1///2 (C (Cn))s
E R
S tq1
+
2t
Sih4
6t
where V/g min 1), CK
Cz E|3, 12 and the expectation is taken over all sources of randomness, including f,0 1.8....,8E wi,-.... we, Br BI,..., In addition, for the expectation,
2p
log(1+o motee)
29

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 7 RRRP-UCB for robustness measures in the uncontrollable setting when Ω is continuous.
Input: GP prior GP(O, k), continuous set S2, (x( HeN: N1 for t= l, do
(6)
.., finite subsets Q2, Q2....
Generate & from chi-squared distribution with two degroes of freedom
Compute B log (() + E
Compute Q (2c, w) for each (x, w) E E x Ω
Compute (x) for each E.'
Estimate é by d arg max P(u (x. .)) Select next evaluation point 2t by equation 12
Generate w, from
Observe y/1 = f(;; w;) + Et point (It, w;) Update GP by adding observed data
end for
worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
n + +44 mit + +)2
E R
< C
where C is 2 for the mean absolute deviation measure, and 1 for the other measures.
Theorem B.4. Under the assumptions of Theorem B3 the following holds:
E 1
R[R
Sihi
Σ 2 Xis (102 1-4/12 (Cra))'s12)
(
where 8 given by equation and functions (+).,, he(-) and all coefficients are as defined in Theorem B.3. In addition, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
π² + +4/
(2 (4) + 2)
Elra] S C
where, C given in Theorem holds:
B.3 Moreover, for the expectation measure, satisfies i= t, i.e., the following
E(ro] S x² + +aV 6L.
(2 k 2)
1.
Proofs are given in Appendix C.11
B.3 Extension Uncontrollable Settings when Ω is Continuous
Let Ω be contimous set. In this case, if X is finite continuous, the only difference between the proposed
method and Algorithm 4 or is whether not w; is sampled from p* We give the pseudo-code for the case
where Ω is continuous in the uncontrollable setting in Algorithm 7 Note that X' in Algorithm includes both the finite and continuous cases.
B.4 Theoretical Analysis in Uncontrollable Settings when Ω is Continuous
First, we introduce a similar assumption to Assumption B.I When Ω is finite, Assumption B.1 means that there is no wi e Ω such that (w = w(x) = 0, and this requires that the points that cannot be realized values of are not included in Ω. On the other hand, when is continuous, a similar assumption is that there is no Ω and e such that (www e Nei(a; <)) O, where Nei(a; c) the open ball with center a and radius > 0. Therefore, introduce the following assumption:
30

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Assumption B.2. For any Ω and 0, (w Nei(a;e)) 0 holds.
Furthermore, we introduce new assumplion the partition of Ω. Here, let. 8
be family
of subsets in Q. Then, S is the partition of Ω if & satisfies U f2 = Ω and f2, n, 92 = for any i i j.
Assumption B.3. There exist partitions S S of Ω satisfying the following two conditions:
1. For any 1 2 1, Pmiin minigige minnes, P E E 0.
2. There exists non-stochastic sequence (,, 1..... such that
( a) o b)l S
for any 22 1, {(01, w1, v1. 31). (II-1, 11-1, 3e 2 3e), f e S and b E Ω
Then, the following theorem holds.
Theorem B.5. Assume that the regularity assumption, Assumptions A.3
B.2 and B.3
and equation 10 hold. Suppose that X and Ω are finite and continuous, respectively. Let T [bgdgrt? (ydgrtt(//oo((aydy (o2o((/dd)/))) v2/2)]. and let Ω be a set of discretization for & with each coordinate equally divided into T/! Suppose that Wi....; w, follow p and Ei...., are random variables following the chi-squared distribution with two degrees of freedom, where fl Et, Wi...., We, , & are mutually independent. Define ( [bod2rt? (Vlogazzd X1) + / |X| and 3, = 2 2 K (5) & Let (2(a) and qe (a) = Ei= Sehi (Σj=1 \uaa")) be functions satisfying Assumptions A.4 and A.5 respectively, For the sequence .1,..., 4 satisfying Assumption [33] define ft + + 4. Then, under the uncontrollable setting, if Algorithm is performed, the following holds:
n
81 2 Aay (1C2m1g))) 1- ) (vp: + Pmima G
E[R]] I 2tq2
Gih!
6t
where 14j = ming J),C; log(1+o meise C2. BBj Bis (2 Pmiint given in Assumption B.3. and the expectation taken over all sources of randomness, including f, Et, Wı,.... we, $1..... addition, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
... P..
E[R]] S C (
+ +4 +//1((2 1(2 log Ki + 2) + Prmin,t P
where C is 2 for the mean absolute deviation measure, and 1 for the other measures.
Theorem B.6. Under the assumptions of Theorem B.5 for f defined by equation 13 the following holds:
Bir < E[R]] < 292
n Ai (1C2.gg)) 1-v/g/2 2 (sp + pmin, Crijs//3
+
6t
In addition, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-al-risk, and mean absolute deviation measures, the following holds:
2² + 4
(2 l2 (( 2)( Priin Cire)
Elr! < C
31
Moreover, for the expectation measure, the following holds:
2 n²
(2log ni + 2)( + C17))
+
+ +4/
3t
31

---

Published in Transactions on Machine Learning Research (07 (07/2025)
B.2 and B.3 and equation 10fhod.. Suppose that X' and Ω are continuous. Tet. F, = [bydr[ log (azd) + + 2) and let X, be a set of discretization for X' x Q with each coordinate equally divided into tr. Suppose that Wi...., Wi follow Pt, and E1,....,E Se are random variables following the chi-squared distribution with two degrees of freedom, where J, wi...... ut: .I....... are mutually independent. Define K (1 7()) )7 and 3. = 2 log Ki + St. Let (a(a) and (a = Ei=1 Gi,y (Ej=>>yaa") Agaa") be functions satisfying Assumptions
Theorem B.7. Assume that the regularity assumption, Assumptions A.5
A.6
A.7
A.7 and A.5 respectively. For the sequence .1..... be satislying Assumption [3.3] let 4r = 4 + ................................ 4 Then,
under the uncontrollable setting, if Algorithm is performed, the following holds:
B[R]] < 2tqs
π
+
2t
Shh
Σ j=1
2 Aay (tC2,,ng.)) 1////12 ) (ox + Pmin
6t
==1
C2, BiB 2[Bpu/(0-vi) Pmin,t is given in Assumption B.3 and the expectation is taken over all sources of randomness, including f, WI...., Wt, .I........ P... In addition, for the expectation, worst-case, best-case, a-value-at-risk, a-conditional value-at-risk, and mean absolute deviation measures, the following holds:
where b/y min 13. C1
2
moise
x22 + 4 4 12 (5) 2) + P C1:1e) E|R| S C so (
where C is 2 for the mean absolute deviation measure, and 1 for the other measures.
Theorem B.8. Under the assumptions of Theorem B.7 for 8 defined by equation 13 the following holds:
B[r]]] < < 203
π
+
n Xi (1C2 1/1///2 1- (gx, + P Crr))//13
6t
i=1
In addition, for the expectation, worst-case, best-case, a-valuc-at-risk, a-conditional value-at-risk, and mcan absolute deviation measures, the following holds:
x² + +41
(2 Kip (5)
+ +2)(() + Pmiin
Moreover, for the expectation measure, the following holds:
n²
(2 (2 Ki (5)
2)(pp + Pminnt Cirn))
1
<
+ 1/
31
t
Proofs are described in Appendix
C.12 In the next section, we provide specific examples that satisfy
Assumption B.3
B.5 Specific Examples Satisfying Assumption B.3
For simplicity, assunne that X' = Ω [0, 1j. Let pa be the uniform distribution on Ω. For each 2 1, we define = -[t1/27. Here, we consider partition of Ω into intervals with length o, that is, S₁ = 1,..., Q: 13 U (l(e- - 1)/er. 1]}- Then, for any 2 E St, Pmintt = dr > 0 because (w E (22)) = ei Next, since the difference between posterior variances satisfies
[IG - 1)/0r.j/0) (())))))))))))))))))))))))))))
o a) (2t, b) = (a:-1 a) a (xt, b)) (or-1 (wi, a) - o.-1(11,, b)),
the following holds:
02 (Ir,, -0, 1 b)l = ( a) + (2t, b) 0 (m,, a) a 1 b) 220t-1 a) -1-1 (xt. b)
32

---

Published in Transactions on Machine Learning Research (07/2025)
Furthermore, from Theorem E.4 in Kusakawa et al. 2022) for linear, Gaussian and Matérn kernels, the posterior standard deviation is a K-Lipschitz continuous function for any &. 2 and observed data. Therefore, if the true kernel function is the Gaussian kernel k((2, w), w')) = k(0,0) = exp(-1 - - 0'11/2), the following incquality holds:
( a) - 1 b) S v2 la b111-
Moreover, since the length of f2 is e the following holds:
l a) - (x), b)l s 2 a) ( b) s 2222lla - b111 = 2
This implies that 4 = =2v2er Hence, the following inequality holds:
2k 222 - 1/2 <2v2 (1 1+ / k <x-1/aak 2V2(1++2V 2) 6vê.
P: = 2v2
Thus, by substituting Pe S 6vt and Pmin,: = lt = [t//2 into Theorem B.7 the following holds for the expectation measure:
n² + 4 1(2 (2ggg : + 2)(6Vi++ (2/21/1mx)) 3
[
From the definition, (5()) satisfics log Ri (5) Ollog)). In addition, from Theorem 5 in Srinivas et al. (2010)
for the Gaussian kernel, Tt satisfies it O(llog ()*). Therefore, we obtain
E[R]] 0(ts/
C Proofs
C.1 Proof of Lemma 3.1
Proof. The value max (2)) is constant that does not depend on æ. This implies that a( at Therefore, if (f) =a(", then (z=""= -= On the other hand, if ( = =a(() that is,
23 0 (x! u (x- (z S u (0! - -
then 3. o, 21/20 (0- (1) I 33.33 (0) From the definition of a66, 14-1(17) S 14 141 (at (1) Since
81/20 ())))) < 0/ (0-1(11 the inequality (== + 3//22/011///1 (-) - B1 1 (-
holds. This implics that (z-1(z)()) S (=)(()))). Finally, since a. xt u (1)) S (x) (1) and
"x-)(x(")) (4) ( hold.
C.2 Proof of Theorem 4.1
Proof. For 1, we define Dz-1 {(x1, w1, U1, B1), (xI-1, wt-1 11-1, and Do 0. Let & be realization from the chi-squared distribution with two degrees of freedom, and /2ple,/2 Then, from the proof of Lemma 5.1 Srinivas et al. (2010), with probability at least 5, the following holds for any (x,20 w) E X Ω:
(x w) = pt- (a- w) - ////2 oz (a, w) S f(x, w) S ( w) + 3/ (x,, w) u (,, w),
where Bs = 2 log([ X x 21/5). From the definition of 6, since 3s 2 2log(1 x R1 + & = B,, the following inequality holds with probability at least 1 -: 8:
4-1(x, w) S f(x, w) S 1 w).
Hence, f(x,-) E Gx-1(x) holds. In addition, from the theorem's assumption, since ucb;-1(x)) and Icb,-1 (x: satisfy equation 2. the following holds:
1c)) & F(x) S (x))
33

---

Published in Transactions on Machine Learning Research (07 2025)
Therefore, for F(x") F(t), the following inequality holds:
F(x") - F(ē;) = (F(x*) max
+ (max 1 - F(éi))
mEx
s (ucb)- 1
max Icby (a:)) + (max leb, (2:) - F(tt))
#EX'
v (ucb;-1 (a=)
max 1cb)-1(a))) + (p(1411 - F(2:))
#Ex
(ucb;-1(zt))
max lcb;-((x)) + ( lebblbbll1 (
#EA
< (ucb)-1(it)) lcb;-1(ā;)) - (ucb,-1(ăt) - 1
< (ucby- 1 (20,)
lcb; (o:)) - (ueb, (2x)) - lcbt-1 (
2(ccb (2x+) lob, (x:));
where the third inequality is derived by -x, ())( the definition of dt, and maX lcb;-1(x)) S max p( -) = p(pe-1(0 .). Morcover, from Assumption 4.1 there exists function
n
9;
((a) Σ
Sihy
Niya
j=1
such that ucb,-1(x;) -cb,,,
(xx) & q(2,)) o 01-1 (2x, w.)) Thus, we have
F(x") - F(x,) - --
(15)
Let F-) be a distribution function of F(x*) F(t,) under the given D.-1. Then, from equation 15 we get
Fr-1 (2g -z- (æ,, w.))) 2 1
By taking the generalized inverse function for both sides, we obtain
F - 5) & 2/(23 oz ( wi)).
Taking the expectation with respect to & for both sides, we have
EG [1 6)] s EE, (
(x,,
Here, since & follows the chi-squared distribution with two degrees of freedom, 8 follows the uniform dis- tribution on the interval (0, 1). Hence, noting that 1 - 5 also follows the uniform distribution on (0, 1), F(x")- F(t)) does not depend on 8, from the property of the generalized inverse function, under the given Di-1 the distribution of F equal to that of F(x*)-F(at) Let E--1 be conditional expectation under the given D.-1- Then, get.
E 8)] E,-1(F(x") - F(2,)).
Furthermore, since Be 2oo(((X' 11) + f,, noting that
Bg / w.))) E,, (2 0.-1 wr))),
obtain
E- - F(+)) < Es, (29 σ ( wr))
Thus, by taking the expectation with respect to D.-1 for both sides, have
E(rx] E[F((*) F(+:)) B[24 220222222000111 ( wx)))
34

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
Therefore, the following inequality holds:
E R
E
< E
2 22 1 wx)) (x))
= 2E
Sihe
Σ
X 12 - (x0s wz))
1=1
k=1
1=1
2
h4
123 0k-1 wk))))
1=1
In addition, since hx(+) is concave function, the following holds:
82
h
Aig 1 (x,,
h4
Xij (23) 0 2o wk)
k=
k=
< th;
Xig (2 !2 1 wx))
k=1
th;
2 A13
(0) ok 1 2))
j=1
km
Furthermore, from Jensen's inequality, we get
ox 1 wx)) ] $ the Σ
(z2 (o))) {1)
h4
Aes 22
2 A
Σ
(17)
jml
Here, if Vig S 1, by letting =2/(2 (1i) and 0 = 2/v1g, using Hölder's inequality we obtain
1/n
1/6
( (22//ax- 0 ux) Σ 18% uis 0k- (o: wx)) S
Σ
24g (ork, ws)
k-
1=1
Moreover, by using Hölder's inequality for expected values, the following inequality holds:
>
1/n
(akk wv 1)
1/0
E
Σ 10 12 O wk))
<
E
Σ
0%
IE
Σ
v1:0 0
From the defimition, since Bi,..., Br are independent and identically distributed random variables, the fol- lowing equality holds:
E
2/1 k
1)-
2/v
- (EE
1/1
10--(18 -(18 (8tt/11e-ws))) 1-r1//2 = -(1B (01/12-21)) 2-2///2 (18)
In addition, from the proof of Lemma 5.4 in Srinivas 2010), the following inequality holds:
Σ ( w6) $ Cin-
Hence, we have
Miy σ k- (xkk, 20x) 1)
1/0
1 o wx)) )) u///2
Σ
E
$
(Crr))a/22
(19)
k=l
35

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
Thus, get
1-1/1/2
Σ (3 ok (o0,, (x0,
w))) _ (E |
(Crx) (102 1-1///12 ) (CiT)
Similarly, if Vij > 1, by letting 0 = 2, using the same argument we obtain
1/2
1/2 ))
E Σ 1B (xk, $
3his k
Σ
2013
(okk, w),)
o
k-1
1-v/s/2 /2
1o12
ui 112 (2-v1(s)
2015 (x wkx)
x
E
k
Therefore, since 0x, w) S 1, noting that 2:1 (ok; wk) S 1 (kk wk) we get
1-////2
1///2
E
Σ 1/ ok (2k. wx))
E
(2-)()))))))
k-
20
(akk 20x)
-
1-1/,112
o (aok: wik) ))
U//12
(20)
/ 12 (2-1//5)
3k
R=1
(1C2,v)) 12 (C Connaaa
Hence, for any Mi > O, the following inoquality holds:
(Bk 1 w) 1-4// (Cra)
E
(21)
Thus, noting that h.).) is monotonic non-decreasing function, by substituting equation 21 into equation we obtain
17
] the Σ 2 Aes (tC22mu)
E
h4
22 0k-1 )
1-1/1/2 2-v/// (Cri)ks/))
(22)
Finally, by substituting equation
22 into equation 16 we get
E
R < 2t
Schi
Σ 5=1
2 Xi① (1C2.ug)
1/////2 "
1=1
C.3 Proof of Theorem 4.2
Proof. For the expectation E[ral, the following equality holds:
Biral = Ep., /rall = Ep,, (B=,1 1 F(;:)l.
where Ep,.1 is the expectation with respect to Dr-1- From the definition of f, the following inequality holds for any 1 < i <
E-1[F((x)) - F(+:)) < E,-1(F((")) F(2.)).
(23)
This implies that
E-11F((x*) F(E)) < Σ
E [Fxx)) - -F(2)).
i=1
36

---

Published in Transactions on Machine Learning Research (07 (025))
Therefore, using this we get
Blrg] = ED. [ - - P[;;]] S ED,
Σ
E. EE-1 [F((") - F(a:))
1
1=1
EE D [8 18--1 (F(x*) F(2::]]
E[Rd]
Σ
B[F((") F(E)) = B Σ F(x") (((=)) F(ē.)
C.4 Proof of Theorem 4.3
Proof. We show = t. Let Ω = (w ..... w(0}} and P(w wll)) = Ps. where j E {1,.... Lt, and the probability is taken with respect to w. Then, from the definition of the expectation measure, F(x) can be expressed as follows:
I. F(x) Σ f2, w j=l
Therefore, the following equality holds:
[--1F[()]] = Ee (or,,(()]]] Piun (20 (w,,w())) 1lu
Here, from the definition of &e, the following inequality holds for any a E X:
p(u--1 (xx, )) S
Hence, for any i tt....,t). the following holds:
E [- p(pc-1(0t,.) S p(u)-1(00,,) [F(E))
This implics that 8= t.
C.5 Equality between (m)) (a) in Table 4 in Inatsu al. (2024a) and (a),, g2(a), and Φs(a)
Proof. For any x, x', f(x, w) and f'(x', w), we derive g(a) satisfying
p(
sup |f w) - f''x',,, -'(e',
(we
Since x, xt, f(x,, w) and f'(x', w) are arbitrary, we can assume that |p(((x,)) p( = :)) (( .) without loss of generality. For the distributionally robust, monotone Lipschitz map, and weighted sum measures, we can use g (a) in Table 4 in Inatsu et al. (2024a) by introducing additional assumptions about monotonicity, concavity, and taking zero at point zero.
Expectation
Let Ew! [:] be an expectation with respect to w. Then, the following holds:
p(((x,))) p( Enw [f(x, w) Eny ( (((x,ww) w)]
Evl fxx w) f((x',
Eno (1, w) f'(a', w)ll S sup [sx w) f'(x', wen
This implies that q(a)=
37

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Worst-Case
For any > O, from the definition of infinuum there exists w such that
f' w²) S inf f' w) te.
wes
Thus, we have
inf wen
f(,,w) inf f'(x', w) S inf f(z, f' w²) + c f(x, - ,'(x', te wen
wEs
I sup [f w) - f (a', w)l + wen
Since e arbitrary, we get
p(S(x,))) - ((f((a')))) inf
(æz w) inf
f'(x', w) S sup (f w) - ,''x', w))
WEB
WEB
wEi
This implies that q(a)
Best-Case For any > 0, from the definition of supremum, there exists w" such that
sup f(x, w²) S f(x, w²) +c.
weG
Hence, we obtain
sup fæx un) sup ('(,', w) f(a, w0) + sup f' (w) S far, w²) f' (('''""'))))) te [f u)) - f'(x',,,, w)) +
we weR
wen
S sup wen
Since 6 arbitrary, we have
p(((x,)) )) p(l'(a',)) sup ((x w) sup f'(x', w) S sup [s w) ,'(x', wEl
wef
well
This implies that q(a)= =
a- -alle--ttRiss Let a E (0,1) and = sup (f w) f2'(x', w)] f'xx'w)]
Then, we have f(x, w)
['(w', +k. Here, for any E IR, the inequality (f (x' w)+ S b) S (f w) S b) holds, where IP is the probability with respect to w. Here, if a S P. (f'('', w) s b) holds, then a S (f(( w) S
holds. This implies that
()) pls((, inf E IR a (s w) S b)} S inf E |a (f' w) < b)}
inf E R a Fu (f w) S b)} + ((f ..)) + k.
Therefore, we get
p( p(5'(a',)) ()) sk= sup [s w) f' w)).
wen
This implies that g(a) = a.
a-Conditional Value-at-Risk Let (0, 1). From Nguyen et al. 2021a), the a-conditional value-at-risk can be rewritten follows:
p(( )) 1 a
/ vy(azaa)da'
Thus, using the result of the a-value-at-risk, we have
- uy'; - /- (1y(a:
< ( sup [s w) - ['x2", w))lda Jo wen
sup [f w) - f'(2', wel
This implies that q(a)=
38

---

Published in Transactions on Machine Learning Research (07/2025)
Mean Absolute Deviation From the triangle inequality |a] |b| I aa bb, the following holds:
p(S(z,))) (( (((()))))<(((aaa)))))
(a w) Eu [f( w)ll E. (I w) E.. (" ww),
Ew (x, w) Ew (2 w)ll - 1f'( w) - Ewlf w)ll
I Bw [f w) f'(x', ()) - (Ewlf(x, - f w))l
Bu [[ w) - f'(x', w)ll + L (w w) f'
sup [x w) f' w)] + sup [ w) - (a''
wEn
weG
sup [f( w) - ['(x', (w))-
wEn
This implies that g(a) = 2a.
Distributionally Robust Let be candidate distribution of w, A be a family of candidate distri- butions, and pr(-) be robustness measure with respect to P. The distributionally robust measure is +)) Let qa(+) be function satisfying (pp(f(x.)) pf(f'(x', S
defined p p(f(z, )) qa (sup (xx w) - (' w))) for any P. Additionally, assunne that qa(+) is a non-decreasing concave function satisfying (0( = 0. For any E > 0, from the definition of infimum, there exists distribution
P' E A such that
p(f'(a',))) = inf pr( 2 PEA
Therefore, the following inequality holds:
plf(xx,)) - plf (z', s inf pr pr(f(x. pp (z', te PEA
< (s pp (J'(('' +
sup [f fxx', w|ll [ER
$ qa
Since 6 > 0 is arbitrary, we get
p(s(x,))) - p(f(ce') s aa
sup [s w) - ('(',w))) wen
This implies that g(a) = qa(a).
Monotone Lipschitz Map Let M be K-Lipschitz function, and p(-) be a robustness measure. The target robustness measure is defined pl-) (M o (.)) Let Φ(a) be function satisfying
(0(((z,))) (l'
sup [fx w) f' (((e,w))) wil)
(ee
Additionally, assume that q(a) is non-decreasing concave function satisfying q(0) 0. Then, for the robustness measure p(-), the following holds:
plf(x.))) p(f M(((( -iaU < Klp(f(m,)) -(('(('',,)))
Kÿ sup [( w) - (2(x,w))] wen
This implies that g(a)= = Kū(a).
Weighted Sum Let an, 02 2 O, and let p:(-) be robustness mcasure. The target robustnoss measure is defined as p(-) = (-pi(-) + (2)2(.). Let qe(a) be a function satisfying
(p((f(z,)) :) - p.(f'(x', -))) < q.
sup ff w) f'(a', wi)) west
f(d''w)))
39

---

Published in Transactions on Machine Learning Research (07/2025)
Additionally, assume that q:(a) is non-decreasing concave function satisfying q:(0) = 0. Then, for the robustness measure p(-), the following holds:
aI @Ipi( 1) + 02p2 (arp + a2pe("aa)
=a(li(((xx))) -i (f -)) (2("'xx))))
S 0n9
sup [f), f-'',((( a292
sup wEn
[f w) (' w)ll
wen
This implies that g(a) = (a) + a2))(a).
C.6 Proof of Theorem A.1
Proof. For t 2 1, let T = (Vlg(odd/))) + v=/2)]. Suppose that 24 is a set of discretization for X with each coordinate equally divided into тr Note that [&& +( For each E X, let {ar]e be the element of Ne closest to æ. Then, It can be expressed as follows:
rt F(x") F(ē)) =(x") F((x")) + -(xx")))F((a F(t)).
Therefore, the following equality holds:
Σ (F(#") -F(x=)))) E ((F((=))) -
E R E
(24)
Let & be realization from the chi-squared distribution with two degrees of freedom, and let 8 = exp(E./2j Then, from the proof of Lemma 5.1 in Srinivas et al. (2010), with probability at least - 8, the following inequality holds for any wx) E (Xt (+)) x f2:
(,,1, w) = -h- (xe, w) - 8 oz- ( w) S [(x w) S ( w) + 3/8 02 01-1 w) u 1,51, w),
where B5
(#x)) x 01/8). From the definition of 8, noting that ( x 2t5
(1 + 7 |12
kt and A5 = 2 log )) + E. = Br, the following holds with probability at least 1 - 5:
4-1 w) S f(x, w) S u1-1(z, (z.w).
Hence, for the function f(x,, w) with respect to w, each element E 24 U ( satisfies f(x. E ( Moreover, from the theorem's assumption, since ucb;-1(x)) (x) and (cb satisfy equation the following inequality holds:
lcb;-1 I F(x) S ucb;-1(x).
Therefore, noting that [x=],, d. E XG U ( F(xx*)) F(t:) can be evaluated as follows:
F((x*)() F(2,)= (F([x*]))
max ( 1obxx -(t))
#E.
=EX
< (ucb,- ([x*)() max Icb, (z)) + (max lob, (x) ) - F F(t.))
=EX
#Ex
< (ucb,- ([x*)() max lcby (x)) (1((,-1(0,)
F(+:))
=EX
< (ucb, - (wt) max (cb;-1(x))) + (ucb, (2,) - lcb, (2)))
=EX
(ucb, - (#t)) lcb;-1(8,)) + (ucb; (#.) lcb,-1
(ucb,- (xx) lcb,- (x,))
(ucb,-1 lcb,
2(ucb; (xx) - 1cb;-1(x;))
40

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where the third inequality is derived by (1-1(x,-) E Gi-1(x), the definition of it and maXzex lcb;-1(2)) 1 max (2,,) :)) = (121; ))) Furthermore, from Assumption 4.1 there exists a function
(()) = Σ Siha 1=1
Xıja"
such that (xb) lcb;-1(x11) & ((2))) ot- (Iiz, wi)) This implics that
F((='}) ( 20(23) oz- 0 (2,, w,)).
Since the hand side does not depend on εes using the same argument as in the proof of Theorem 4.1 we get
B[F((=*]+) F():)) (22 0z- 0z (m,, wr))]
Thus, using the same argument as in the derivation of equation 16 equation 17 equation and equation 22 we obtain
E
((p(w*))) -
21
Σ
G/i
7
1
Σ
201 Aes (1C2mi,)) 1- 1//22 (C17)
(25)
1=1
j=1
Here, BI...., Be do not have the same distribution, and equation monotonicity of (2), the following holds:
18 does not holds. Nevertheless, from the
1)
1/n
1/n
-(IR gmall 1-My/2 (IR) (
(qu/le--1))) 1-14,/2
E
MR
Hence, we have equation
25 On the other hand, from the definition, the following inequality holds:
F(x") F(xx1)) plf(x" ,.)) - p(f([=")(1 s 91
max wen
ff w)) f((x= Jc w)]l
a fax w) Then, the following holds:
Let Lina= sup supisisd, suPzex
Bey
"a x' E X. E Q f(x w) - f(æ', w)l & Lmazelaa - x'll1.
Therefore, we get In addition, noting that || - [x"] S dir/Te, we obtain
1s( w) - -[(x"') [c: wi) S Liman |x== [x"]ella-
If(x", w) f((x"']]]) le. w)l S Lmandir/Te
Thus, since
max [f(=", (w)) - f(xx wi)l z q1 (Lmead(1/Te) wefl
@i
using the concavity qı (a) we get
B[F(x") - F(xx")))) S E [g1 (Lmandir/me S q1 (E [
(26)
Moreover, Lmaz satisfies E E[Lma < b1 Moo(aadd [[]] + R/2 (see, Appendix C.7 This implies that E. (I/Ted 1- By substituting this into equation 26 we have
E[[((x") F(xx((1)))) "e)] S 91 (1-2).
Therefore, the following holds:
E
(((('')-(((<11a)))
Σ
qn (k
q1 (k 2) s tq t
tq
π
(27)
Finally, by substituting equation
25 and equation
27 into equation
24 obtain the desired result..
7
41

---

Published in Transactions on Machine Learning Research (07 (07/2023 /025)
C.7 Upper Bound of [[[m
Proof. For any j E (l.....d) d and w E Ω if supeER' dn, f(x, w/ following inequality holds:
I L, then Lmax S L. Therefore, the
d
0f(z, w)
d1
PiImaa > L) -
sup mEx
> S
a1 exp
dx,
b1
j=1 wel
j=1
WEB
L
d1
[2/eepp exp
bj
Let ajdi [2] J. Then, using the property of the expectation in non-negative random variables, [[[maaz] can be evaluated as follows:
B B[I
P(Immax L)dL
$ Je JeL
00
000
= bi Vlog J +
Je (I./b)) al
bi
blvlog J + Jbi V
1
1
(L/bi)² dL
biv/tog 2 (0//2)
blvlog J + Jb1
$ (V2log
biV
S b, Vog. + 2
where ((-) is the cumulative distribution function of the standard normal distribution, and the last incquality is derived by Lemma H.3 Takeno
(2023)
C.8 Proof of Theorem A.3
Proof. For each t 2 1, let -.- = [b2dgtt? (attartt(///(aaaaae 1og(u2d2|2T) + /=/2)]- Suppose that Q2 is a set of discretization
for Ω with each coordinate is equally divided into 7!. Note that [0a (1. For each Ω let [w]e be the element of Ω closest to w. Then, the following equality holds:
- F(x")=>-- ((())) F(x")= FF(("" F)(x)) Fi() (+!) F(#!).
This implies that
1 (F((*))F((())) + - F(((1)) E
E[R|] E
- -
(28)
Let & be a realization from the chi-squared distribution with two degrees of freedom, and let exp(E. Then, from the proof of Lemma 5.1 in Srinivas et al. (2010), with probability at least 1 - 8, the following holds for any (x, w) E X x Ωy:
4-1,6 (xc, w) = 14-1(x, w) - B. (0, w) I f(x, w) S 1111 w) + 3//22 01-1(x1, w) = u4-1,6 w),
where 35 = 2log((X' x 2,l/8). From the definition of 8, since |X x Qel = (7/)d2/x) = x() we have Bs 2 log (2))
Br. Hence, the following inequality holds with probability at least - 5:
4-, w) S f(x, w) S 14 (xr,
42

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Therefore, the following holds for any f2:
4-1 (w])) f(x, [w]e] u-11 [w]c).
Thus, for the function ff (xe, w) with respect to w, (x, (x) holds. Here, from the theorem's 's assumption, since ucb)__(2)) and lcbl_ satisfy equation 10. the following holds:
1cb|_1(x) & (x) S (c)
Hence, we obtain
(x")) F. (ω.) s 2(ucb[_1 lcb[_1(x:)
Furthermore, from Assumption A.5 there exists function
=1a)== = ΣS Gh!!
Σ Ayya
such that (xx) - 1eb[_1(00) S (2 12 az 1 (xx,, w..)) This implies that
(((")) - P( (a.) < 2g (28 o. 1 (2x, w.)).
Noting that the left-hand side does not depend on &,, using the same argument as in the proof of Theorem we get
(aF) - Fi (a+)) < (28) ( (æI,
Therefore, using the same argument as in the derivation of equation 16
equation
17
equation
21 and
equation
22 we obtain
- -
< 21 G
Σ 20 dij ((C2,nn.)'
1-////2 (C (Cin))
(29)
On the other hand, from the assumption, the following incquality holds:
F(x") (x =(s((" (x 5.42 mnax [()""w)) - f(x", [km]:)]]
Let Thas suPzEx suPisiEd, suPweR
8 Dwg [(x, wn) Then, the following holds:
ww w E E 2,, w) - f(x, w')l S Tin ll wi I|
Hence, we have In addition, noting that w| - [w]ell & d2r/T! T! we get
If(x" w) - f(xx,[w))) S D/naz w [w]ell1-
|f(x", w) f(x", (w)::) S Lar//
Thus, since
max w)) - f(=", [u]]))]]]] I 92 (Innader/TT)) wen
using the concavity of (a(a) we obtain
[[F(x") - F((xx)) <
L) (Lmaedrr/Ti]
[ [2nn/darr/T)
(30)
43

---

Published in Transactions on Machine Learning Research (07/2025)
Here, by using the same argument in Appendix C.7
get E [[ by( b2([Vog(a2d2)11) + v This
implies that E U2azd2r/Th x=? Substituting this into equation 30 we have
E[F(x")
(xx)) F/ 22 (t
Therefore, the following incquality holds:
E (F(())) - (x()))
-(F(a')-F((("))
22 (k( = Σ (2 2) S tqp
E k-
t-
S tgp
π
(31)
6t
By using the similar argument, the following inequality also holds:
E
Σ (nf((a))
- S 1g2
n
(32)
61
Finally, substituting equation result.
29 equation
31
and equation
32 into equation
28
obtain the desired
C.9 Proof of Theorem A.5
Proof. For rf, the following holds:
= F(F(x") =( - (! + (+) -F( E(F(x)) F((2)) +
2 (33)
1
Here, we define i as follows:
i= arg min R [F(x*) (*!)).
1sis
Then, noting that
E,-1F((x") - F/ (+\)) < Σ E [F(x") - (+)))
the following inequality holds:
B[F(x*) (x)) < Σ
-(F((*)-FF(()
B F F( + F(a)) - ((())
1=1
E R
E[R
(34)
t
2
Next, we show 8=t. t. From the definition, & can be rewritten as follows:
i i= arg max R, 1.
1315
Let Ω (w)() ..... w()}. Then, the following equality holds:
F(!! = E., E. [f(e], [w]+] =
Σ
Pu (w = (
5=1
Therefore, we get
J
E- =
Σ
Pm (w (E) (I(e), w0())]] =
P. m (w w0)) (r ( (0002000
j=1
j=1
En [1t- 1 (2) [nm)=)]
Ew ( w)] = p (+t,
44

---

Published in Transactions on Machine Learning Research (07/2025)
Hence, from the definition of é!, we have Ex-1(F((E)) ( This implics that i = t. Hence,
equation 34 can be expressed as follows:
E R F[F(=)) F -
+
(35)
Thus, substituting equation 35 into equation 33 wc obtain the desired result.
C.10 Proof of Theorem A.6
Proof. For r/, the following equality holds:
+ = F(x") F( = F(x") Fl (1=*),) + (1x")) 1/ (e)) + F. (a!) - F(t!).
Let imax= = suPisisa
0f(0) 00,
From Assumption
A.7 the following incqualities hold:
F(x*) - F/ ([x") S q3
f(x", w) -f(((==],,,, -[((="1,,(w))))))
max wEn
(#!) F(#!)= S 43
[( w) s(a). (w))))))))))
max
WEG
In addition, the following incqualitics hold:
Emaw dr
le, If(=" w) f[[x=)[ [e, [w]+)]
& Lmazz w)) ([x*),, [20]))l12
F1 dr
Lmmx Tt. [/(0), w) - [(0), [w)o]] s Lmaz ( w) (#) [w)x)]l=
Here, under Assumption A.6 from Lemma H.1 in Takeno et al. 2023 we have B[[.maz] S by bs(Vlog(a3d)) + v Hence, we get
F[F(x*) F! ((xx)))) S gg(( (+) F(#))) s g).
On the other hand, noting that [x= # X, u ( and ((X, U (+1)) x Oel (1 + = nr the same argument in the proof of Theorem
(3) by using
A.3
obtain
((=*),) F/ (+)) < B (28 0 wr)))
By combining these, and using the same argument as in the proof of Theorem A.3 result.
get the desired
C.11 Proof of Theorems B.I.B.4 B.4
Proof. For each 1, let D,-1 f(x,, wi 81 (1,.881,,......... Bi)...., W1 Bt-1)) and Do 0. Suppose that & is realization from the chi-squared distribution with two degrees of freedom. Then, by letting 8 x using the same argument as in the proof of Theorem 4.1 the following holds with probability
least 1- 8::
F(x") F(t)) & 2(ucb:- - (0bx1((x))))
Furthermore, from Assumption
there exists a function
((a) = Σ
Sihy
Xija
1=1
1=1
45

---

Published in Transactions on Machine Learning Research (07/2025)
such that ucb-- (2x+)
lcb;-1
((23)/2 or- (20,, wi (mm)))))
where
wi
(maz)
arg max wen 20//2 oz- (2,, w) Hence, the following incquality holds:
F(x") F(ē)) - 2q(23)) σt- (2e, w (max) )).
Therefore, by using the same argument in the proof of Theorem 4.1 we have
Brr F(=(=") - F(a.) & (224 0 wi
(maz) }}}-
Note that under the uncontrollable setting, the expected value of the of the posterior variances in equation 19 and equation 20 is replaced by the following:
E
Σ th (a0ks w
(max)
Here, for each k, under the given DR-1 and 3k, o (atk w (max)) holds:
constant value. Then, the following
1 w
(maz),
I Σ ( (x2, S Pmin Σ 1 w(l)).
5=1
j=1
Since wE does not depend on D and BR, the following equality holds:
Σ j=1
P (ark, w( = Flog wv Dx 3x).
Hence, we have
(ok, wk w (man))
Pmmnn FF -0 (00k, 101))
Therefore, we get
E
Σ
2 o (2 w (
(mar))
I Pmin C1 Cj.
By combining these, and using the same argument in the proof of Theorem 4.1 we obtain Theorem B.1 Thcorems can also be obtained by using the same argument.
C.12 Proof of Theorems B.5
we evaluate Blo (akk un (mazly] by using the same argument as in the
Proof. To show Theorems
B.5
B.
proof of Theorems B.1 B.4 Under the given
Dx-1 = {(21, Wi, V1, B1)..... (xk-11 Wi Uk- Bk-1), Tb. 8kh.
o w w( (1nax) a constant. Moreover, since Da-1 and wa are mutually independent, using the tower property, the partition S₁ satisfies
P 1 wx) D Dp-1] P Pmin.
Σ PP w. (wi E { 10) (a (w we E Ô
feES
Eun, 1o (Ios, unx DD 57
NESt
where the last incquality is derived by using the inequality
P Pan, Poo,,(10 (we E ②) 2 1.
46

---

Published in Transactions on Machine Learning Research (07/2025)
Here, for 22 E Sk, if w (mex) Rz from Assumption B.3
the following holds for any w Sg:
oh (2 wk
(maz)
S w)
Therefore, we get
oi (0 wk (mar))
La Eus B 1 (xtk, wT)) we E 22y].
Thus, we obtain
( (0 mmar)) 1k 1
Σ
Ew. 1 D we 2 S Eur ( ux)]
DES
This implies that
Blok-1 (00k, w (max))] }] S is + P 1 wn]].
Hence, the following inequality holds:
Blox- (Ik, w
(marr) ) 1
Lk +
Pminn Bloo (I)s wa)]
k=
k=1
= Pt +
Σ
P & (00 wR)1
k=1
-1 S Pt + Pmnin,
Bio2-1 (x),
k=
where the last inequality is derived by Pminn1 ... 2 Pmin.t.
Therefore, since
Eio (xx,, wH)l S + Pmin, Crnss
+ P Punin,
km
we have the desired result.
Experimental Details and Additional Experiments
In this section, we give details of the numerical experiments.
D.1 Experimental Details
In the 2D synthetic function setting, the black-box function I was sampled from GP k), where the kernel function is given by
k(0,0') cxp(-lle 02) 0, X
In the 4D synthetic function setting, fa is defined as follows:
ba (1a2 + 11) + (a + b2 7) + 104.8905
/3281.531
In the 6D synthetic function setting, we first generated the sample paths fı, f2, fs. fa independently from GP(O, k) defined on {-2, -4/3, 22/3,0, 0, 2/3, 2/3. Here, for 0, 0' E R3, we used
k(0,0") exp(- 0 111//11
Using this, we defined the black-box function as follows:
[(1 22, 33, w1, W2, wa) fi (11, + 22, w1) fa(oa, w1, (2) Sa(wi, W2, wz).
47

---

Published in Transactions on Machine Learning Research (07 (07/2025)
For the setting in the 2D (6D) synthetic function setting, the black-box function was generated for each simulation based on the above, and a total of 100 different black-box functions were used as the true function.
For the probability mass function p(w), we used p(w) 1/50 for the 2D synthetic function setting, and p(w) = ((w))((()) for the 4D synthetic function setting. Here, for a E 1-2.5+2.5(i 1)/7 1.... 15) = A, ((a) defined as follows:
0.25 1 +5)
((a) ( - + 0.75Ø(a' + 5)}
where o(-) is the probability density function of the standard normal distribution. In the 6D synthetic fanction setting, we used p(w)= = $1 (w2))))))) where
@(b - 1) Σ EVEB o(b' - 1)) (2(() = EvEB o(b)) 5s(b) = EvEB o(b +
6(b)
Φ(b+1) 1)
(b)
and b E (-2+ 2 - 1)/3
7) = B.
The details of each acquisition function are as follows:
Random In Random, 2t was chosen uniformly at random from X, and we was chosen randomly from Ω based on the probability mass function p(w).
US In US, my and w, were chosen by (I,, w.) = arg max (x.w)) o2 (2c, w).
BQ In BQ, used the property that the integral of GP is again GP. Given a dataset {(xj, Wj, (yj,y)) W;) )- the expectation with respect to w of GP(O, k) is again GP, and its posterior distribution is given by (P(ā)( k(x, æ'),, where (x) and k(æ, x') are given by
Σ p(w)),(a,, (w) } (K: + onoiee 1e) yss WER
[x)
(a (x, x²)
Σ p(w))p(w (alpp((o'((((( (k((2r, w), (at', "aa,,w")))
w. En
T Σ plw) (o) m } well
(K, + o2 nniso I,)
Σ En
Let f, max (x( and 67(x) (x, In BQ, 2, was selectod basod on the expected improvement (EI) maximization in (P(p k(æ, x')) for fr. That is, for 2n,t by (z,, + )(2m.))
(((w)-ff the value of El calculated o.(x)
BPT-UCB In BPT-UCB, we first defined = 0.5 min 1,00085/211000 0.05 x c/(8) x 21)) where wo
used e = in Section 5.1 and e = 2 in Section 5.3 Next, we defined h..w.. = h + 27j [1r( w) h < m
and otherwise w Using this, we defined p. (æ) and 72 (x) follows:
(x(x)= = Σ 2 [1( w) he.wee
or(2,,
wEs
[1, u)) - -ha,
{{ (1-9 & (uu(a,
w) - -1 -Ma. )
(x)) = Σ 2
0e( w)
0e(2,, w)
WEN
48

---

Published in Transactions on Machine Learning Research (07/2025)
For B, by
[xx 3x0.0b we defined BPTUCB(z) (.(x) + 11/10 2 (z). (x)) Then, F++1 and w were selected
2/10
2+41 arg max () #EA
[e((0e11 w) N 1.
{1-
[ee[Be+1, w)
W1+1 arg max & wED
0r(2x-11 w)
0e(2x+1, w)
BPT-UCB (fixed) In BPT-UCB (fixed), the definition of BPTUCB(z) in BPT-UCB was changed to BPTUCB(2) (x) + (x)) and #++1 and w441 were selected using the same procedure as BPT-UCB.
BBBMOBO In BBBMOBO, we used 3 2log( 1 0.05)) and I; Et. where ãt given in Definition 3.1
BBBMOBO (fixed) In BBBMOBO (fixed), used 3r and æ; 3t, where it is given in Definition
Proposed In Proposed, was selected by Definition 3.1
Proposed (fixed) In Proposed (fixed), æt was selected by Definition 3.1 where we used Br = 9.
Values ucb;-1(x)) and Icby-1 (ar) in EXP, PTR and EXP-MAE were calculated by using results Table in Inatsu et al. (2024ap. Here, ucb;-1(2:) and Icb;-1(x: for -aTl[] w) - [ax)( were calculated by using the results of the mean absolute deviation and monotonie Lipschitz map in the table. Combining these and the results for the weighted sum, calculated ucb,-1(x) and lcb;-1(x) for EXP-MAE
D.2 Identity of BВBMOBO (fixed) and Proposed (fixed) in the Expectation Measure
In the expectation measure, ucb;-1(x) and lcb;-1(x)) are calculated as follows:
ucb;-1(2) (x) Ew 1u (x, w) + 3//22 (0, w)], leb;-1(x) = Euwlue- w) 8//22 (x_
Therefore, equation 4 in Definition 3.1 is given by a, arg max Ewlor-1(2,, w)]. Also, the definition of ã. can be rewritten as ã. arg = ucb;-1(x)) (xr). Here, the difference between BBBMOBO (fixed) and Proposed (fixed) is only whether to use D; D, or equation 4 in Definition 3.1 In Proposed (fixed), when I; = arg max Enw (0,-1(x w)] = Lt. is consistent with BBBMOBO (fixed). Also, when a, = arg max Ew 100-1111,) w)] = Zz.
ucb,-1 = (ā,, w) + 3 1/12 o, (i,, w)] = Em (2,, w)] + B. 2 Em. 1 w)]
< 1 w) + /// FEa ,0 (i,, w)]
< Emm w) / Em |o=- (0t, w)] ucb. (dte).
Here, the first inequality follows from the definition of ã,, -. = arg max x Ew | 1 w)], and the second inequality is derived by the assumption, x; arg max Enp fo (I,, w)) é, Therefore, ueb,- (..) S ueb;-1 (i:), but on the other hand, from the definition of Z₁, ucb;-1(#;) ucb;-1 (.t). In the EXP experiments in Section 5 there were no cases where multiple æ values maximized (x)) As a result, H. = &t, which is consistent with BBBMОBO (fixed).
ucb;-1($.)). Hence, ucb;-1(ā.)
49


Reviews:
[{"review_id": "G8XyQmEbdQ", "reviewer": "Reviewer_DyNJ", "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": "**Strengths:**\n\n* The paper has provided clear motivations for introducing the randomized trade-off parameter into GP-UCB with robustness measures. The related works are carefully discussed such that the contributions of the proposed method are clear.  \n\n* The proposed RRGP-UCB is general enough to handle various robustness optimization settings such as controllable environmental settings, uncontrollable settings, finite input spaces, and continuous input spaces. The algorithm design and theoretical results are discussed for each setting.\n\n**Weakness:**\n\n* Even though strong theoretical results are provided for various robustness settings, the experiments didn't demonstrate significant empirical results. In many cases (as shown in Figs. 2&3), fixed $\\beta_t$ can achieve lower or comparable regret than using the designed randomized policy even without tuning in various settings and different methods ($\\beta_t=9$ is used for both BBBMOBO (fix) and Proposed (fix) in all the experiments). Since the major contribution of this paper is to extend the randomized trade-off parameter to BO with input uncertainty, such empirical results decreased the significance of the proposed method. In addition, the algorithms designed for continuous input spaces are not tested in the experiments.\n\n* The writing of this paper needs to be improved. The complex notations and some confusing claims make it hard to follow. See detailed comments below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 proposed a new Bayesian optimization (BO) algorithm, called RRGP-UCB, for optimizing functions with input uncertainty. Instead of using deterministic trade-off parameter $\\beta_t$ , RRGP-UCB randomly samples $\\beta_t$ from a chi-squared distribution such that $\\beta_t$ will not keep increasing with $t$ as in the conventional GP-UCB. In contrast to some existing methods designed for handling only specific robustness measures, RRGP-UCB is applicable to any robustness measure (e.g., expectation, worst-case, value-at-risk, etc.) that satisfies certain conditions. Both theoretical and empirical results are provided to show the performance of the proposed method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The author(s) discussed only the setting with discrete input space in the main paper and put all the other results in the appendix. However, since the robustness of the proposed method is one contribution as claimed in the introduction, I suggest the authors to consider put some important results (both theoretical and empirical) of the other settings (e.g., continuous input spaces) in the main paper such that the contributions of the proposed method can be identified more easily.\n\n2. The notations in this paper are complex, especially those for various $x$. It's better to provide a summary of the notation such that the paper is easier to follow. Also, there exist some confusing notations or typos. For example,\n\n* Is $\\tilde{x}$ in Lemma 3.1 and that in the definition of $\\gamma_t$ the same? If yes, what is $\\tilde{w}$ in $\\gamma_t$? Otherwise, it's better to use other notations in the definition of $\\gamma_t$\n\n* In the equation below (4), should it be ucb_t or ucb_{t-1}?\n\n* In (2), how are the lower bound lcb() and upper bound ucb() computed? Inatsu et al. (2024a) has provided several methods for approximating them. Which is used in this work?\n\n* Lemma 3.1 is proved using specific definitions of $u_{t-1}$ and $l_{t-1}$. Does it still hold when replacing $u_{t-1}$ and $l_{t-1}$ with ucb(x) and lcb(x), respectively? If yes, why not use ucb(x) and lcb(x) directly in Lemma 3.1? Otherwise, what's the relationship between Lemma 3.1 and Definition 3.1?\n\n3. In Figs. 2&3, why are the results of BBBMOBO (fixed) missing in all the EXP graphs?\n\n4. In the experiment discussion, it is claimed that \"small trade-off parameters limit exploration, often resulting in convergence to local optima\". How is it demonstrated in the empirical results?", "broader_impact_concerns": "There is no ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SCZQidnAJs", "reviewer": "Reviewer_HJS8", "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": "**Strengths:**\n\n* Generally applicable to common robustness measures\n* Tighter expected theoretical bounds across common robustness measures\n* Detailed appendix extending to various settings, including continuous domains and uncontrollable $w$\n\n**Weaknesses:**\n* Experimental results do not indicate that the proposed method is significantly better than existing methods empirically, which is acknowledged by the authors", "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 focuses on the robust Bayesian optimzation setting, where an additional environment variable $w$ is present and can be selected. The authors propose a Gaussian process upper confidence bound-based method, where the trade-off parameter $\\beta_t$ is sampled from a two-parameter exponential distribution, following IRGP-ICB, rather than increasing by $\\log t$ every iteration as in GP-UCB. They show that this leads to tight bounds on expected cumulative regret bounds across various robustness measures. Experimental results on both synthetic and real-world datasets were also shown.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Can the authors clarify the following:\n\n* $\\tilde{x}_t$ and $x_t$ are defined in both Lemma 3.1 and Definition 3.1 in slightly different ways. Why are there multiple definitions? Lemma 3.1 does not seem to be used as well.\n\n* On the information gain defined at the end of page 7. Why is it defined with $(\\tilde{x}_t, \\tilde{w}_t)$, instead of say $(x_t, w_t)$? Also, where is $\\tilde{w}_t$ defined?\n\n* In Equation 8, why define $\\hat{t}$ using $F(x^*)$, which is unknown? Theorem 4.2 and 4.4 are also based on Equation 8. What about only using the alternate definition of $\\hat{t}$ that does not depend on $x^*$, already defined in the paper, for theoretical analysis?\n\nMinor:\n\n* Correct capitalization in bibliography for \"gaussian\", \"bayesian\", etc", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TVWyQ2VRkw", "reviewer": "Reviewer_Nk3H", "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": "A major strength of this paper lies in its introduction of randomized $\\beta$ into the context of optimizing robustness measures. This eliminates the need for manual specification of $\\beta$, making the approach more practical and broadly applicable, which is an aspect other researchers can benefit from.\n\nAdditionally, the proposed method is applicable to a wide range of robustness measures, an advantage developed from the work of Inatsu et al. (2024a). The paper also establishes a bound on the expected regret and identifies the optimal solution for the expectation measure.\n\n---\n\nHowever, the paper would benefit from improved clarity in several points and more robust support for some of its key claims.\n\n+ Claims:\n\n  + The paper claims that \"To the best of our knowledge, no research has been conducted on BO methods based on GP-UCB for general robustness measures that achieves a tighter regret bound without requiring the growth of $\\beta_t$.\" However, the high-probability bound in this work is also not tigher than GP-UCB. Could the authors provide support for the above claim?\n\n  + Is Assumption 4.1 same as the one in Inatsu et al. (2024a), as claimed? If I am not mistaken, Inatsu et al. (2024a) only require the function $q$ to be strictly increasing. If the assumption here (defined by the set $Q$) differs, probably the author needs to provide justification.\n\n  + While the paper claims to support continuous inputs (theoretically justified in Appendix A), the experiments are limited to discrete input spaces. Including empirical validation for continuous inputs would strengthen the experiments.\n\n  + The claim \"To the best of our knowledge, this study is the first to establish regret bounds for various robustness measures.\" may not be entirely accurate as Inatsu et al. (2024a) also provide such bounds.\n\n+ Clarity:\n\n  + What is the symbol $|^{\\forall}$ in the definition of $G_{t-1}(x)$?\n\n  + $\\rho(f(x,w)) = F(x)$: $F(x)$ does not depend on $w$, but $\\rho(f(x,w))$ depend on $w$?\n \n  + $G_{t-1}(x)$ is a set of functions over $w$ but it is defined as $\\\\{g(x,w) \\| \\dots\\\\}$ (elements are scalars?)\n\n  + Instead of referring readers to Inatsu et al. (2024a), the paper should explicitly define the bounds $lcb_{t-1}(x)$, $ucb_{t-1}(x)$, and $q(a)$ for all applicable robustness measures. This would enhance clarity and make the paper more self-contained.\n\nAdditionally, the paper mentions several limitations that may reduce its appeal relative to existing methods.\n\n  + Computing $\\hat{t}$ (the index of the optimal solution) is intractable. Does this imply that the guarantee on the expected value of the instantaneous regret is not practically meaningful?\n\n  + The high-probability bound appears to be loose due to the presence of $\\delta^{-1}$ compared to other GP-UCB-based bounds.", "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 extends the existing randomized Gaussian Process Upper Confidence Bound (GP-UCB) framework to optimize black-box functions under input uncertainty. By sampling the trade-off parameter $\\beta$ from a chi-squared-based distribution, it overcomes the need for manual specification of $\\beta$ required in conventional GP-UCB methods. Moreover, the proposed approach provides tight bounds on the expected regret and numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "While experiments with continuous inputs would strengthen the work, it is more critical for the paper to improve the support for (or revise) the claims discussed in the \"Weaknesses\" section (excluding the experiments) and to improve clarity on the points mentioned above.", "broader_impact_concerns": "I have no concerns regarding the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)