A Unified Framework for Bayesian Optimization under Contextual Uncertainty
Authors: Sebastian Shenghong Tay
Chuan-Sheng Foo
Daisuke Urano
Richalynn Leong
Bryan Kian Hsiang Low
Venue: ICLR 2024 poster (2024)
Keywords: Bayesian optimization
Gaussian processes
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: Generalization of distributionally robust BO to other notions of risk such as value-at-risk, mean-variance tradeoff etc., along with a general algorithm with a regret bound.

Abstract: Bayesian optimization under contextual uncertainty (BOCU) is a family of BO problems in which the learner makes a decision prior to observing the context and must manage the risks involved. Distributionally robust BO (DRBO) is a subset of BOCU that affords robustness against context distribution shift, and includes the optimization of expected values and worst-case values as special cases. By considering the first derivatives of the DRBO objective, we generalize DRBO to one that includes several other uncertainty objectives studied in the BOCU literature such as worst-case sensitivity (and thus notions of risk such as variance, range, and conditional value-at-risk) and mean-risk tradeoffs. We develop a general Thompson sampling algorithm that is able to optimize any objective within the BOCU framework, analyze its theoretical properties, and compare it to suitable baselines across different experimental settings and uncertainty objectives.

Published as a conference paper at ICLR 2024
A UNIFIED FRAMEWORK FOR BAYESIAN OPTIMIZA- TION UNDER CONTEXTUAL UNCERTAINTY
Sebastian Shenghong Tay!? Chuan Sheng Foo Daisuke Urano",
Richalynn Chiu Xian Leong', Bryan Kian Hsiang Low!
DDepartment of Computer Science, National University of Singapore
PInstitute for Infocomm Research (I2R), A*STAR, Singapore
Centtee for Frontier AI Research (CFAR), A*STAR, Singapore
*Temasek Life Sciences Laboratory, Singapore
sebastian.tay@u nus edu, Foo.chuan.shengE star..sttttniitaaaaa......... edu. edu.s,
da daisuke@tl1.org sg, richalynn@tl1.org sg, lowkh@comp nus. edu. sg
ABSTRACT
Bayesian optimization under contextual uncertainty (BOCU) is a family of BO problems in which the learner makes decision prior to observing the context and must manage the risks involved. Distributionally robust BO (DRBO) a subset BOCU that affords robustness against context distribution shift, and includes the optimization of expected values and worst-case values as special cases. By con- sidering the first derivatives of the DRBO objective, we generalize DRBO to that includes several other uncertainty objectives studied in the BOCU literature such as worst-case sensitivity (and thus notions of risk such variance, range, and conditional value-at-risk) and mean-risk tradeoffs. We develop a general Thomp- son sampling algorithm that is able optimize any objective within the BOCU framework, analyze its theoretical properties, and compare it to suitable baselines across different experimental settings and uncertainty objectives.
INTRODUCTION
Bayesian optimization (BO) is a well-established framework for black-box optimization under the constraint of limited function evaluations (Garnett 2023) that has seen numerous successes real- world applications, including hyperparameter tuning (Chen et al. 2018)) protein design (Romero jet al.] 2013), and experimental physics (Duris et al., 2020). While standard BO assumes that the learner has full control over all input variables to the objective function, in many practical scenarios, the learner only has control over a subset variables (decision variables), while the other variables (context variables) may be randomly determined by the environment. For example, in agriculture, a farmer optimizing plant growth may have control over the amount of water the crops receive, but not the amount of sunlight. A line of research studies such scenarios in which the learner makes a decision prior to observing the context and must therefore manage the uncertainty in the final input due to the uncertainty in the context. This is done by maximizing some uncertainty objective that takes the context distribution into account, such as the expected value or the worst-case value with respect the context. Distributionally robust BO (DRBO) is subset of BOCU that generalizes these uncertainty objectives. However, there are many other uncertainty objectives under the BOCU umbrella that have thus far been seen as adjacent to DRBO, including (conditional) value-at-risk, mean-variance tradeoff, and many others.
term BO under contextual uncertainty (BOCU)
This paper unifies several of these disparate works into single general framework. We show that, by considering the first derivatives of the DRBO objective with respect to the margin, the DRBO framework may be extended to include the above-mentioned adjacent uncertainty objectives and many others. We also subsume in our framework robust satisficing (Long et al. 2023). recently proposed uncertainty objective in the operations research literature that has recently been applied in the context of BO (Saday et al., 2023). By unifying these seemingly different settings, believe our work allows BOCU problems to be studied in a new and interesting light. Moreover, our frame- work encompasses family of novel uncertainty objectives not yet studied in the literature with

---

Published as a conference paper at ICLR 2024
their own individual interpretations. Beyond theoretical interest, our unified framework has practi- cal ramifications: we develop a single BO algorithm capable of optimizing any of the uncertainty objectives within the framework which simplifies the process of any practitioner who wishes to op- timize different objectives. We provide a regret bound and the conditions under which it achieves sublinear regret, and empirically demonstrate its performance in various experimental settings and uncertainty objectives.
Related work. Our work unifies several settings in a line of research studying BO under con- textual uncertainty (BOCU). The closest works to ours are those on distributionally robust BO (DRBO) Kirschhnrr et al., 2020; Nguyen et al., 2020; Husain et al., 2023 Inatsu et al. 2022 Tay et al. 2022), an adaptation of distributionally robust optimization (DRO) in operations re-
search (Rahimian & Mehrotra (022) to the BO setting. The DRBO framework captures stochastic BO (Toscano-Palmerin & Frazier 2022) and robust BO (Bogunovic et al. 2018) which optimize expected values and worst-case values respectively. Other works under the BOCU umbrella opti-
mize for various notions of risk, including (conditional) value-at-risk (Cakmak et al. 2020 Nguyen ct al. 2021a|b b), quantiles/expecttlls (Picheny et al. 2022), and a scalar combination of mean and variance (wwazaki et al. (022). Makarova et al. (2021) also consider the mean- variance tradeoff, but do not consider the notion of observable contexts and treat the noisy observations as heteroscedastic.
Beland & Nair (017) and Cakmak et al. (2020) propose very general frameworks whose objectives are arbitrary mappings from distributions to real numbers (termed 'robustness metrics' and 'risk measures' respectively); however, they assume the context within the learner's control during the learning procedure, and the large generality of their frameworks appears to preclude meaningful regret analyses. Our framework extends DRBO in a manner that increases its generality while still being amenable to analysis.
BOCU can be considered generalize a line of work referred to as contextual BO in which the context is observed prior to making a decision (Krause & Ong, 2011] Char et al. 2019: Fiducioso al., 2019. Kirschner & Krause 2019), by viewing as a special case of DRBO in which the reference distribution is a point mass corresponding to the context at that iteration and the margin e = 0. BOCU is a subset of an even more general class of BO works that study optimization under an inability to fully control every decision due to random adversarial influences, including BO with uncertain inputs (Oliveira et al.] 2019), BO for finding equilibria in games (Marchesi et al., decisions (Hayashi et al. 2022), and causal BO (Aglietti et al. 2020 Sussex et al. 2023) among many others.
2020 TTay et al. 2023). BO with purtially-specifee
2 PRELIMINARIES
We study problems involving decision variables x E X C R", context variables с E C {c(1), (c()),(())___) c ( C RR,, |C| = n. and functions over the joint decision-context space f X x - R. We assume that X is compact and convex subset of 1 and that C is finite set (a standard as- sumption in the DRBO literature (Inatsu et al. 2022 Kirschner et al. 2020: Tay et al. 2022)). ). The decision variables can be chosen by the learner, while the context variables domly from some probability distribution. The learner chooses x prior to observing the context c. We assume that some reference distribution p is known that captures the learner's prior knowledge of the distribution governing e. Since C is finite, p (and all distributions over C) can be represented as a probability vector in , Pt, the i-th entry of p. is the probability that the random vector has value ( The learner also chooses some convex distribution distance d, e.g., one of the f f-divergences or integral probability metrics. This work is concerned with optimization problems of the form x* arg maxxex g(x; f. F.p, d, where g is scalar function and denotes additional problem-dependent parameters. We refer to g as an uncertainty objective. We sometimes omit the parameters f. p and to reduce clutter and introduce specific parameters in e as the need arises. The first examples of such uncertainty objectives are the stochastic optimization (SO) (Toscano-Palmernn
sampled ran-
& Frazier 2022) and robust optimization (RO) (Bogunovic et al. 2018) objectives:
gso(x)= = c<p
[f c)1 pp T((x), PRO (x) = min f(x, c)
(1)
cEC
where f(x) := (f(x, O)) E Rd. Throughout this work, we use bold symbols to represent vectors, and bold symbols followed by (x) to indicate vector in R² constructed by applying
function each of (l)), (x, c(2)), c().) While the SO objective is straightforward
2

---

Published as a conference paper at ICLR 2024
way to handle contextual uncertainty, it has two shortcomings: first, its correctness is dependent on p being the true distribution from which с is sampled; second, the expected value says nothing about how bad individual realizations of f f c) may be, fact which risk-averse learners may be dissatisfied with. RO is more risk-averse but may be too pessimistic as it does not incorporate any knowledge about the distribution of and simply assumes that the worst possible value is attained. Distributionally robust optimization (DRO) is generalization that allows an 'interpolation' between these two objectives (Kirschner et al. 2020 Nguyen et al. 2020; Tay al. 2022):
(DRO(x; 6) = o(x e) == min
q (')(x)
qEl((..d.))
((p,d,c)== RR : 0. 0.1 1, 1.
where the margin e 2 0, and U(p, d, c) is the uncertainty set and contains elements that are valid probability distributions e-close to the reference distribution p in terms of d. Intuitively, DRO con- siders how poor the expected value may be if an adversary were allowed to shift the context dis- tribution a distance с away from p. In this work, we consider only distances such that d(p..) is convex function of q. The uncertainty set constraints are then convex, and v(x, c) is the optimal value of a convex optimization problem. v(x, e), also termed the worst-case expected value (under e-distribution shift), is non-increasing in e, and is itself a convex function of (Boyd & Vanden- berghe| 2004 Sec. 5.6). SO is recovered when é = O, and RO is recovered when 2 fx = d(p, ex) where ex a probability vector with zeroes everywhere except at an index in arg min; (x) The learner thus chooses their level of risk aversion via Fig. Dess[]llussse Dillustrates v(x, e) as a function of e and the relationship between SO, RO and DRO.
A GENERAL FRAMEWORK WITH FIRST DERIVATIVES
We have seen thus far that v(x, E) encapsulates the uncertainty objectives SO, RO, and DRO de- pending on the value of c. It turns out that, by including information about the first derivatives of v(x, c) with respect to c, we can include even more uncertainty objectives that have been studied in the BOCU literature. Define the right derivative of u(x, E) at as
v(x, + h) v ex
8( 8(x, 6) = lim h10
h
Since v(x,e) e) is convex function of E with domain [0, oo), 5(x, E) exists and is finite everywhere on the open interval (0, oo) (Rockafellar 1997 Thm. 23.4), and is non-positive since o(x, e) is non-increasing in Special care must be taken ensure that 5(x, 0) is finite]] with with particular choice of distribution distance d; distribution distances that fulfill this condition include the total variation (TV) distance, maximum mean discrepancy (MMD), and the Wasserstein metric, among others (Gotoh et al. 2020 Staib & Jegelkal, 2019). When d(x, 0) is finite, it is the worst-case
sensifivity (WCS) uncertainty objective (Gotoh et al. 2020 Tay al. 2022
gwcs (x) 6(x, 0).
The worst-case sensitivity may be considered an uncertainty objective as Gotoh et al. (2020) showed that the worst-cass sensitivity corresponds to different 'notions of risk' depending on d. For example, when is the TV distance, 5(x, 0) is the range max; f(x); min, f(x); (assuming p has non- zero mass on the indices attaining the maximum and minimum): when d is the maximum mean discrepancy (MMD), 6xx, 0) is a quantity closely related to the variance Vo-plf(x, c)] (Staib & Jegelka, 2019); when d is specific f-divergence, 8(x, 0) is linked to the conditional value-at- risk (Nguyen et al., 2021a). Just as DRO may be interpreted as an interpolation between SO and RO, in order to interpolate between the expected value (SO) and these notions of risk (WCS), learner may choose as their uncertainty objective a scalar combination of the expected value and these notions of risk (wwazaki et al. 2021), which we refer to the mean-risk tradeoff (MR) with tradeoff parameter (3 0:
9MR (MR(x; 3) = E [f c)] + +1888x000 0) exp
(5)
MR as a function of @ is the linearization of u(x, c) around c = 0 (see Fig. 1b. By the convexity of exx, e) in e, 9MR (x; 8) v(x,3) (3 for all 8 > 0.
For example, 6(x,0 0) = oc if belongs a particular family of smooth f-divergences (ooooh et al.
2020
3

---

Published as a conference paper at ICLR 2024
Table I: Various uncertainty objectives studied in the literature, their expressions, and the parameters required to recover them from our general uncertainty objective Equation 7 indicates that all objectives indented under it are special cases.
A bolded objective
Uncertainty objective
Expression
Dist. robust opt. (DRO) 2
v(x, == min qEU(p.d.c))m enq
E [f(x,c)) c)]
1
0
[0, 00)
Stochastic opt. (SO)
EI [f c)l
1
0
0
Robust opt. (RO)
min f(x, c) oEC
1
0
[2x: 00)
Robust satisficing (RS) (6)
max K s.t. Ve, (x, E) 2 Tx + ke
0
1
[0, 00)
v(x, + h) - v(x, c)
Worst-case sensitivity (WCS) (4)
8(x, 0) = lim
0 1
0
1J0
h.
Mean-risk tradeoff (MR)
5)
IF
[f(x, c)] + 30(x, 0)
1 [0, oo)
0
exp
The uncertainty objectives WCS and MR only use the quantity 8(x, 0). A natural question arises: are there uncertainty objectives that rely on 5(x, e) for some >> 0? Robust satisficing (Long et al., 2023 Saday al. 2023), a recently introduced concept in the operations research literature, one such objective:
[us(x; r) == max s.t. Vc, v(x, c) 2 T Icc k=
where T S. 1eep [f(x, c)], otherwise the constraint is violated at = 0 for all k. In robust satis- ficing, the learner chooses the parameter т that represents 'good enough' expected value under the reference distribution. The quantity DRS (x; T), also known as the antifragility, is the maximum non-positive slope such that the linear function + IRs (x; 7) lower bounds v(x, e) for all O. The interpretation is as follows: the learner accepts some baseline expected value т, and in the case of distribution shift, accepts decrease in the expected value proportional to the distance between the reference and true distributions; the decision x that minimizes this decrease per unit distance is considered most robust. Fig. illustrates the relationship between т, v(x, e), and the robust satisfic- ing objective (the gradient of the dotted line). The following proposition (proof's of all results are in Appendix A establishes the link between robust satisficing and the first derivatives of v c).
Proposition 3.1. Suppose the distribution distance d is such that 5(x, 0) is finite. Fix a T < minxex Eccp [x, c)). For all x E X. there exists an Ex 2 such that (x;(x; E du(x, where Øo(x, <x) is the subdifferential of v(x, E) at Ex.
Conversely, fix an 2 O. For all x X, there exists a Tx S Ecup [f c) such that 8(x, e) (xs(x;;) Tx). In particular, (wcx(x) = 8(x, 0) gRS (x; Eewp [f(x,c))
In other words, the robust satisficing objective and the subderivatives of v(x, e) are closely related. For fixed т, the robust satisficing objective is subderivative of v(x, e) at some value of 6x (which may be different for each decision x); likewise, for a fixed c, the right derivative at (which is subderivative) is the robust satisficing objective for some Tx (which again may be different for each decision x). This close link suggests that the right derivative o(x,e) e) at values of other than 0 also be considered uncertainty objectives. This aligns with intuition: the smaller the magnitude of the (always non-positive) gradient at a certain value of 6, the smaller the potential decrease in exx, e) at larger values of e by the convexity of e(x,e).
3.1 GENERAL UNCERTAINTY OBJECTIVE
The discussion thus far suggests that both v(x, e) and 6(x, e) are useful quantities in the study of BO under contextual uncertainty. We incorporate both quantities and introduce the scaling parameters > 0 and B 2 0 to obtain the general uncertainty objective
g(x; 8, E) av(x, e) + (6(x
(7)
Table shows the values of parameters a, 8 and e required to recover the uncertainty objectives described in this work. With suitable choice of parameters, 9(x; a, B,c) recovers all of them
4

---

Published as a conference paper at ICLR 2024
Beupl fx, c)] s0
DRO,
WCS
RO
MR, B 8=6 =
RS, 6 c"
v(x, c)
C
0
E'
E"
é
Figure I: Diagram illustrating the convex function v(x, E) for some decision x, and how the various uncertainty objectives relate to the function. The values of DRO, SO, RO, and MR are their dots' vertical coordinates, while the values of RS and WCS are the gradients of their dotted lines.
exactly with the exception of robust satisficing, which has the following caveat: from Prop with a fixed choice c, (x; 0, 1) 6(x. c) ORs (x; Tx), which is the robust satisficing objective for possibly different value of Tx for each decision x. practitioner who wishes to optimize the robust satisficing objective with the same for every decision x using our general objective must know priori the specific 6x for each that corresponds т. This is generally possible since f is assumed to be unknown. Nevertheless, optimizing gx; 0, 1, still corresponds to optimizing the robust satisficing objective, only with a different Tx for each x.
Our general objective also allows for the optimization of novel uncertainty objectives that have been explicitly studied so far. The learner is free choose values of a, B and that do not recover previously studied uncertainty objectives and instead result in uncertainty objective with alternative interpretations as desired. For example, choosing a, c all be greater than results in uncertainty objective that favors decisions with large worst-case expected values under distribution shift (v(x, E) term), and that also do not decrease in worst-case expected value too much increases (8(x, c) term). Such objective would be similar to MR except that the objective is calculated at values of e other than 0, which more explicitly accounts for distribution shift. This general uncertainty objective may also be used if the learner wishes to maximize of DRO and RS objectives with the level of interpolation decided by the relative values of a and B. We observe experimentally (see Appendix B) that BO algorithms that maximize objective with a, 3 greater than 0 are also 'robust' to the choice of uncertainty objective in that they also have relatively good performance under both DRO (a 1, 3 0) and RS (a 0, objectives.
'interpolation'
A GENERAL ALGORITHM
We present a general BO acquisition function based on Thompson sampling (Thompson 1933 Russo Van Roy| 2014) that optimizes the general uncertainty objective Equation 7 for any valid choices of I and e, and is thus capable of optimizing any of the uncertainty objectives in the BOCU literature covered in this work.
We first formalize the learning setting. We assume the unknown function is sampled from Gaus- sian process (GP) with mean 0 and kernel (covariance function) k(x,, c; c; xxx''') c'), with &(x, c; xx c) = 1. At each iteration f, the learner chooses decision X; X' while E C is sampled from Př, and the learner receives a noisy observation y: = fxx,, C₁) + Êe, where each & is i.i.d. noise sampled from the Gaussian distribution (0, o²). We assume that the sequence of true distributions {p; 17 fixed but unknown to the learner. Under these assumptions, the posterior mean and variance of decision-context pair (x, c) at the start of iteration / (having had
observations) are
Pt- (x, c) kx-1(x, c) (K,-1 + o I2I) y
(8) where 1,, c) = k(x, c; x;, c.), and K;- 1,6 = k(xi, Cj X,, Cj). Finally, the learner has their choice of uncertainty objective parameters (ar, 3, {{)){ and reference distributions (p.)
(x, c) k(x, c; xx 1 c) (K₂- + I²I) 1k-1(x,
5

---

Published as a conference paper at ICLR 2024
Algorithm TS-BOCU
Input: GP with kernel k. maximum iteration T, uncertainty objective parameters
(a, 8, (=)))=)), reference distributions {Pr)
2: for iteration t 1 T do
3: Sample model fe from GP posterior given D
4: Select == arg maxxex O(x; ft, Pt, 6x)
5: Observe C; ~ př
6: Observe 1/1 f(x,, c1) + + & N0
7: De := {(x,, Cri (T)]==)
8: end for
9: return Dr
The proposed acquisition, named TS-BOCU (Thompson sampling for BO under contextual un- certainty), is described in Algorithm [ As with all Thompson sampling-basee algorithms, TS- BOCU relies on a function Se sampled from the GP posterior at iteration t. The surrogate objective g(x; fe, Pt, at 3, Et) is the same as the general uncertainty objective Equation 7 except that the un- known true function f is replaced with the known sampled function fe. and we make the dependence on ft and Pa explicit. å can then be computed by computing o(x, <) and 5(x, c) (which relies on two computations of e and in turn can be computed by solving the convex optimization problem Equation] 2
The learner chooses the decision that maximizes this surrogate objective.
4.1 THEORETICAL ANALYSIS
We analyze the T-period Bayesian cumulative regret (Russo & Van Roy 2014) of TS-BOCU
BayesRegret = Σ B [xx(x)) (xx)]
where gc(x) = g(x; Pt, ot B, (e) (making the dependence on f and Ps explicit), x = arg x (x), and the expectation taken over the prior distribution of the underlying function f and the random outcomes of the experiment formalized as the history HT = (x1, C1, //...., XT-1. -r-1, Cr 11, Cr) Our main result bounds the Bayesian regret incurred by TS-BOCU and provides the conditions under which the algorithm achieves sublinear regret.
Theorem 4.1. If the following assumptions hold:
1. The kernel k is the squared exponential kernel or Matérn kernel with 2:
2. the distribution distance d is the total variation (TV) distance;
3. for all < T, the true distribution P satisfies the following:
(a) d(p;, Př) S Cz:
(b) for all c [[C]], Pi.. 2 Pmmin > O.
then TS-BOCU (Algorithm) incurs T T-period Bayesian regret bounded by
BayesRegret(T) S (
VT(Ann + A2) In (T2
Σ E [Beo]) )
8 VIn (T2 + Vnn Pmin ((ArTr + A2) In (T27(m))
where Pr = max ((x. (1/2) I + Krl the maximum information gain, B =
maxxex [[f(x)],, Ti = Emb., A = In(1 + 2 Ag = } Lmb and L, and are
kernel-dependent constants.
The proof of Theorem 4.1 adapts proof techniques from Russo Van Roy 2014 for bounding the Bayesian regret of Thompson sampling algorithms and from Kirschner et al. 2020 for the extension
II practice, approximate taking the limit h J. 0 in Equation when computing 5(x, e), choose h as small possible while still retaining numerical stability.

---

Published as a conference paper at ICLR 2024
to the DRBO setting. Our analysis focuses on bounding the regret incurred due to the derivative term in the general uncertainty objective Equation 7
The proof relies on an upper confidence bound
sequence U, of the form
Ux(x) (x) + (8)(x)
(10)
0x(x)= == min q (x)x(x) qEld(p)d..)))
(x(x = max
lim
min (.
q p- min qEld(ps,d.es)
q
(11)
(xx) (x) 0 h
(x(x) = ((-1 + V (xx (x-((x) VBior-1(x))
We verify that Ue is well-defined under the assumptions of Theorem. 4.1
Proposition 4.2. If the distribution distance d is the total variation (TV) distance, then the derivative upper confidence bound (x(x) defined in Equation 11 exists.
Conditions for sublinear regret. The maximum information gain Yr in Equation is kernel- dependent quantity that is standard in BO regret bound analysis (Srinivas et al. 2010). As long as Yr (T')) (as the case for the popular squared exponential kernel), all terms the regret bound are sublinear in T with the possible exception of the Σ E [Be,] term. This term also appears in the analysis of Kirschner al. (2020) for DRBO under the 'general' setting, and can be guaranteed to be sublinear with additional assumptions. For example (under the 'data-driven' setting of Kirschhnrr et al. (2020)) if Pž is constant p* for all t, 62 d(p:,p"), and Pe is the maximum likelihood estimate of p" given {c then Pt
with probability Rao 1957), , implying that + 0 with probability 1 and thus that Σx= IE [ei] is sublinear. B is constant that does not depend on I", and is a random variable independent the sequence { generated in the aforementioned manner. We thus conclude that E [ Eim [ea] is sublinear under the additional assumptions above.
p" as t
function of f that can be bound
Ei EE BB,]
Necessity of assumptions. Under the assumption that the kernel is the squared exponen- tial kernel or a Matérn kernel with > 2, the derivatives of GP sample paths f satisfy J) S (J/b)) for all i {1,...,,) m} and kernel-dependent constants and b (Ghosal & Roy| 2006). This high probability bound is standard requirement (Kandasamy jet al., 2018: [Srinivas et al. 2010)0 that enables analysis of continuous decision sets via an iterative discretization argument. The assumption that is the TV distance aids analysis considerably as TV admits a closed form for the optimal solution of the convex optimization problem Equation 2 (see Lemma A.11 in Appendix (ppenddi/A..II.... The derivative term presents significant challenges: the limit term causes difficulties without a closed form, and the inner term is a difference of worst-case expected values which, informally speaking, 'erases" the dependency on the uncertainty set and precludes bounding it in terms of the margin that bounds the regret incurred due to the derivative term thus relics on the closed form induced by TV several times. Also, for Proposition 4.2) showing the existence of 8, (x) for general d involves proving the uniform convergence of the limit term, a task that is again aided by the closed form induced by TV. Despite this assumption, we show empirically in Sec. 5hat TS-BOCU displays the sublinear property even when d is the MMD. We thus conjecture that similar result exists for some general class of distances and leave the proof of such an extended result to future work.
((sup(x.e)exxx @f(x.c)
was done for the v(x, <) term. The proof of Theorem 4.1
Thompson sampling enables tractability, Interestingly, the general objective can be optimized eas- ily with Thompson sampling, whereas it is unclear whether there are UCB-based acquisitions (Srini- vas al. 2010 Chowdhury & Gopalan 2017 Kirschner et al. 2020) that are both tractable and the- oretically justified. The upper confidence bound sequence U, in Equation I0 is difficult to compute as 6, is the solution of a bilevel optimization problem. UCB-based acquisitions require an explicit computation of the upper confidence bound, whereas Thompson sampling does not require it and only requires the ability to sample from the posterior. In fact, the Bayesian regret of Thompson sampling holds simultaneously for all possible choices of upper confidence bound sequence U, and thus performs well as the best choice of U, would predict (Russo& & Van Roy 2014). The BOCU framework presented in this work is an interesting example of a family of BO problems in which Thompson sampling is significantly easier to run than its UCB CCB-aaeed counterparts.
7

---

Published as a conference paper at ICLR 2024
DRO (a 1, 0)
WCS (a 0, 1)
GEN (a 1,8 1)
TV
MMD
TV
MMD
TV
MMD
250
280
230
GP
130
009
203
368
3008
308
2000
2003
340
3003
382
3000
36.2
3002
1008
3428
HARTMANN
801
3300
2.00
2003
008
400
1203
623
200
208
000
PLANT
300
301
252
00-
200
13-
902
306
3003
382
322
204
102
INFECTION
133
303
340
100
403
1303
403
300
180
2003
Figure 2: Mean and standard (over 10 RNG seeds) of cumulative regret (lower is bet- ter) incurred against iterations by the acquisitions Random, UCB-SO, UCB-RO, UCB-BOCU-1, UCB-BOCU-2, and TS-BOCU with varying objective functions, uncertainty objectives, and dis- tribution distances. UCB-BOCU-2 does not appear in the DRO experiments as it is equivalent to UCB-BOCU-1 when | O.
EXPERIMENTS
Experimental settings. We evaluate our algorithm with different underlying functions f: 1) samples from GP prior; 2) the Hartmann 3-D function; 3) a plant growth simulator constructed
8

---

Published as a conference paper at ICLR 2024
from world data where the decision and context variables are the pH and concentration of NHg of the nutrient medium respectively, and the output is the maximum leaf area of a plant (Tay et al, 2022); and 4) COVID-19 epidemic model from Frazier et al. (2022) where the decision variables are proportions of test kits allocated to 3 different sub-groups, the context variables are the initial number of cases within these sub-groups and the transmission probability, and the output is the number of resultant cases. The decision and context variables for the GP samples and Hartmann function are decided from among their input variables arbitrarily. We choose special cases of our general uncertainty objective: 1) the DRO objective with
1, 3 = 0: 2) the WCS objective with a = 0. 1; and 3) a general objective (termed GEN) not studied in previous work with = 1,8 1. We use TV and MMD as the distribution distances d. We use Gaussian and uniform distribution for the reference and true distributions respectively, and keep them constant for all iterations. For DRO and GEN, we set the margin to be the distance between the reference and true distributions; for WCS, e = 0 as per its definition. Refer to Appendix C.1 for a full description of the experimental settings.
Baselines. To the best our knowledge, our algorithm is the only algorithm in the literature de- signed to handle all 3 uncertainty objectives tested; we the WCS (for TV and MMD) and GEN objectives within the BOCU learning procedure. Never- theless, we empirically compare our algorithm's ability solve general uncertainty objectives to that of previous algorithms (and naive extensions) in the BOCU literature. We include a simple random acquisition baseline, UCB algorithms for SO and RO as used in Kirschner al. (2020),
aware of any BO works that handle
and two naive extensions of the UCB algorithm for DRBO from Kirschner et al. (2020). named UCB-BOCU-I and UCB-BOCU-2, that incorporate tractable but theoretically unsupported deriva- tive 'upper bound' terms. When / = 0, these algorithms revert to the original DRBO algorithm. Refer to Appendix
C.2 for a precise description of (CB-BOCU-L and UCB- -CB-BOCU-2.
Analysis. The cumulative regret plots for each experimental setting are shown in Fig. 2 We observe that TS-BOCU consistently demonstrates the sublinear property across all experimental settings and achieves a low cumulative regret relative to the baselines in most settings. Random and SO tend to struggle on most settings while RO has inconsistent performance. The UCB-BOCU variants perform well on the DRO setting as expected since they were designed for that setting, However, UCB-BOCU-L does not perform well on any setting where 3 = 1 and the uncertainty objective in- performs better in these settings, but uses theoretically
cludes the derivative term. unsupported heuristic. TS-BOCU enjoys both theoretical guarantees and good empirical perfor- mance. Finally, we observe that TS-BOCU performs well when MMD is used even though the theory was proved only for TV, which lends credence to the belief that the theory can be extended to a more general class of distribution distances. The code for the experiments may be found at https://githin com/ sebt sh uni fied- framework- BOCU
CONCLUSION
This work proposed the BOCU framework, a natural extension of DRBO that unifies several un- certainty objectives studied in the BO literature, and developed general algorithm that optimizes any uncertainty objective within the framework and whose performance is both theoretically and empirically supported. We believe work: one interesting question is whether the assumptions of Theorem [4. can be relaxed, such as by considering a more general class of distribution distances. Furthermore, as described in the related work section, there are still many disparate BO lines of research such as BO with uncertain inputs (Oiveerr et al. 2019) and causal BO Aglietti et al. (2020) that do not fit within the BOCU framework. It is an open question as to whether there are even more general yet still theoretically interesting frameworks that subsume these other settings.
work lays the foundations for several directions of future
REPRODUCIBILITY STATEMENT
We follow standard practices to ensure the reproducibility of our work. The source code for the experiments (along with all datasets) is provided in the supplementary material (available online at Framework BOCU) for full reproducibility of
https://g www.:ttt.bccooooeeeeooooooottttt sebt wttp://////.tt.toonooiieieeee

---

Published as a conference paper at ICLR 2024
the experimental results. All algorithms fully described, and all theoretical results have clearly stated assumptions and full proofs in the appendix.
ACKNOWLEDGEMENT
This research/project is supported by A*STAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Industry Alignment Fund Pre Positioning (IAF-PP) (Award A19F4a0101).
REFERENCES
Virginia Aglietti, Xiaoyu Lu, Andrei Paleyes, and Javier González. Causal Bayesian optimization. In Proc. AISTATS, pp. 3155-3164. PMLR, 2020.
Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson and Eytan Bakshy. BoTorch: A framework for efficient Monte-Carlo Bayesian optimization. In Proc. NeurIPS, pp. 21524-21538, 2020.
Justin J Beland and Prasanth Nair. Bayesian optimization under uncertainty. In NeurlPS BayesOpt 2017 Workshop, volume 2, 2017.
Dimitri Panteli Bertsekas. Nonlinear Programming. Athena Scientific Optimization and Computa- tion Series. Athena Scientific, 1999.
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust opti- mization with Gaussian processes. In Proc. NeurIPS, 2018.
Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. In Proc. NeurlPS, pp. 20130-20141, 2020.
Ian Char, Youngseog Chung, Willie Neiswanger, Kirthevasan Kandasamy, Andrew O. Nelson, Mark Boyer, Egemen Kolemen, and Jeff Schneider. Offline contextual Bayesian optimization. In Proc. NeurlPS, volume 32, 2019.
Yutian Chen, Aja Huang, Ziyu Wang, Ioannis Antonoglou, Julian Schrittwieser, David Silver, and Nando Freitas. Bayesian optimization AlphaGo. arXiv:1812.06855, 2018.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proc. ICML, pp. 844-8 853, 2017.
Joseph Duris, Dylan Kennedy, Adi Hanuka, Jane Shtalenkova, Auralee Edelen, P. Baxevanis, Adam Egger, T. Cope, M. McIntire, S. Ermon, et al. Bayesian optimization of free-electron laser. Physical Review Letters, 124(12):12480) 2020.
Marcello Fiducioso, Sebastian Curi, Benedikt Schumacher, Markus Gwerder, and Andreas Krause. Safe contextual Bayesian optimization for sustainable room temperature PID control tuning. arXiv:1906.1 1at.i1906..086... 2019.
Peter I. Frazier, J. Massey Cashore, Ning Duan, Shane G. Henderson, Alyf Janmohamed, Brian Liu, David B. Shmoys, Jiayue Wan, and Yujia Zhang. Modeling for COVID-19 college reopening decisions: Cornell, case study. In Proc. National Academy of Sciences, volume 119, 2022.
Jacob Gardner, Geoff Pleiss, Kilian Weinberger, David Bindel, and Andrew G Wilson. GPyTorch: Blackbox matrix-matris Gaussian process inference with GPU acceleration. In Proc. NeurIPS, pp. 7587-7597, 2018.
Roman Garnett. Bayesian Optimization. Cambridge University Press, 2023.
Subhashis Ghosal and Anindya Roy. Posterior consistency Gaussian process prior for nonpara- metric binary regression. Annals of Statistics, 34(5):2413-244 2006.
10

---

Published as a conference paper at ICLR 2024
Jun-ya Gotoh, Michael Jong Kim, and Andrew E. B. Lim. Worst-case sensitivity. arXiv:2010.10794 2020.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array program- ming with NumPy. Nature, 585(7825):357-362, 2020.
Shogo Hayashi, Junya Honda, and Hisashi Kashima. Bayesian optimization with partially specified queries. Machine Learning, 111(3):01191000 2022.
Hisham Husain, Vu Nguyen, and Anton van den Hengel. Distributionally robust Bayesian optimiza- tion with ø-divergences. arXiv:2203.02123 2023.
Yu Inatsu, Shion Takeno, Masayuki Karasuyama, and Ichiro Takeuchi. Bayesian optimization for distributionally robust chance-constrainee problem. In Proc. ICML, pp. 9602-9621. PMLR, 2022.
Shogo Iwazaki, Yu Inatsu, and Ichiro Takeuchi. Mean-variance analysis in Bayesian optimization under uncertainty. In Proc. AISTATS, pp. 973-981, 2021.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Parallelised bayesian optimisation via thompson sampling. In International Conference on Artificial Intelli- gence and Statistics, pp. 133-142. PMLR, 2018.
Johannes Kirschner and Andreas Krause. Stochastic bandits with context distributions. In Proc. NeurlPS, volume 32, 2019.
Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In Proc. AISTATS, pp. 2174-2184, 2020.
Andreas Krause and Cheng Ong. Contextual Gaussian process bandit optimization. In Proc.
NeurlPS, volume 24, 2011.
Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Proc. AISTATS, pp. 92-107. PMLR, 2022.
Daniel Zhuoyu Long, Melvyn Sim, and Minglong Zhou. Robust satisficing. Operations Research, 71(1):61-82) -2, 2023.
Anastasiia Makarova, Ilnura Usmanova, Ilija Bogunovic, and Andreas Krause. Risk-averse het- eroscedastic Bayesian optimization. In Proc. NewrIPS, volume 34, pp. 17235-17245, 2021.
Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Learning probably approximately correct maximin strategies in simulation-based games with infinite strategy spaces. In Proc. AAMAS, pp. 834 842, 2020.
Andrew Mastin and Patrick Jaillet. Log- quad-uuaaaiic bounds for the Gaussian Q-function. arXiv preprint arXiv:1304.248: 2013.
Quoe Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Optimizing conditional value-at-risk of black-box functions. In Proc. NewrIPS, pp. 4170-4180, 2021a.
Quoe Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Value-at-risk optimization with Gaussian processes. In Proc. ICML, pp. 8063-8072. 201Ib.
Thanh Nguyen, Sunil Gupta, Huong Ha, Santu Rana, and Svetha Venkatesh. Distributionally robust Bayesian quadrature optimization. In Proc. AISTATS, pp. 1921-1931, 2020.
Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs. In Proc. AISTATS, pp. 1177-1188 184. PMLR, 2019.

---

Published as a conference paper at ICLR 2024
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An imperative style, nigh-perffomance deep learning library. In Proc. NeurIPS, pp. 8026 8026-8037, 2019.
Victor Picheny, Henry Moss, Léonard Torossian, and Nicolas Durrande. Bayesian quantile and expectile optimisation. In Proc. UAI, pp. 1623-1633. PMLR, 2022.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proc. NeuriPS, volume 20, 2007.
Hamed Rahimian and Sanjay Mchrotra. Frameworks and results in distributiinaally robust optimiza- tion. Open Journal of Mathematical Optimization, 3:1-85, 2022.
Calyampudi Radhakrishna Rao. Maximum likelihood estimation for the multinomial distribution. Sankhyā: The Indian Journal of Statistics (1933-1960), 18(1/2):199-148, 1957.
Ralph Tyrell Rockafellar. Convex Analysis, volume 11. Princeton University Press, 1997.
Philip A Romero, Andreas Krause, and Frances H Arnold. Navigating the protein fitness landscape with Gaussian processes, In Proc. National Academy of Sciences, volume 110, pp. E193-E201, 2013.
Daniel Russo and Benjamin Van Roy. Learning optimize via posterior sampling. Mathematics of Operations Research, 22(4):1221-1243, 2014.
Artun Saday, Yaşar Cahit Yildırm, and Cem Tekin. Robust Bayesian satisficing. In Proc. NeurIPS, 2023.
Shubhanshu Shekhar and Tara Javidi. Multi-scale zero-order optimization of smooth functions an RKHS. 2XXi:2005.04832.. 2020.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimiza- tion in the bandit setting: No regret and experimental design. In Proc. ICML, pp. 1015-1022, 2010.
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in ker- nel methods. In Proc. NeurIPS, pp.
2019.
Scott Sussex, Anastasiaa Makarova, and Andreas Krause. Model-based causal Bayesian optimiza- tion. In Proc. ICLR, 2023.
Sebastian Shenghong Tay, Chuan Sheng Foo, Urano Daisuke, Richalynn Leong, and Bryan Kian Hsiang Low. Efficient distributionally robust Bayesian optimization with worst-case sen- sitivity. In Proc. ICML, pp. 21180-21204, 2022.
Sebastian Shenghong Tay, Quoc Phong Nguyen, Chuan Sheng Foo, and Bryan Kian Hsiang Low. No-regret sample-efficient Bayesian optimization for finding Nash equilibria with unknown utili- ties. In Proc. A/STATS, pp. 3591-3619, PMLR, 2023.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-299 1933.
Saul Toscano-Palmerin and Peter I. Frazier. Bayesian optimization with expensive integrands. SIAM Journal on Optimization, 32(2):417-444, 2022.
Sattar Vakili, Jonathan Scarlett, Da-shan Shiu, and Alberto Bernacchia. Improved convergence rates for sparse approximation methods in semel-based learning. In Proc. ICML, pp. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2024
A PROOFS
A.1 PROOF OF PROPOSITION 3.1
Suppose the distribution distance d is such that 6(x,0) 0) is finite. Fix 7 S millxx Beup (x, c)}, For all x E X. there exists an Ex 2 0 such that
Proposition
3.1
gRS(x;T) E @x(
where do(x, Ex) is the subdifferential of v(x,e) E) Ex- Conversely, fix an 2 O. For all x E X, there exists a Tx S Beep [f(x, c)] such that
5(x,e) gx)(x;;x);
in particular,
9wcs(x) = 6(x, 0) JRS
x: E c-p
[f(x
(12)
Proof. Part
For the first part of the proposition, the subdifferential 0v(x, ex) is defined θv(x, ex) {c E R Ve' 2 v(x,=') 2 ex) + ole' -xx)
and we will show that grs (x; r) this set for some 6x
Let k (x; (), which is say that A is the largest non-positive real number such that the following inequality holds for all 2
v(x, c) 2 7 kc.
(13)
If k 0, then & is in Óu(x, &x) since 6(x, 2x) E Ov(x, &x) and 8(x, 2x) = 0.
If 0, we first show that this inequality holds with equality for least one value of c. As proof by contradiction, suppose not, i.e., v(x,e) e) > T + ke for all 2 0. Then, the gap b(e) =
vxx e) - > 0 for all e 2 O.
b(C) is continuous function on the interval [0, 2x] by the following argument: Since v(x, <) is convex function with domain [0, oo). it is continuous everywhere on the open interval (0, oo).
Since the proposition assumes that 8(x, 0) is finite, v(x, e) is right-diifereeniable at 0 and is thus right-continuous at = v(x, <) is thus a continuous function on the interval [0, εx], and thus so is b(c).
Since b(e) continuous on [o, &x]. by the extreme value theorem, e == min.e b(e) > exists. is the smallest gap between o(x, <) and kc on the interval [0, 2x]. Now choose
k 2
W = k min
7x
k > and, since <0 S kk/ < Furthermore, for all E [0,
k c
T + W'= r + ke min
2 &x
$ r + ke c
Ex
< r ke +
- <((x E).
Note that, for Ex. v(x,e) v(x, εx), and + decreasing in e. We therefore conclude that A' satisfics the required incquality constraint Equation 13 for all e >> 0, which leads to a contradiction since 0 k' < Io but ho defined to be the largest valid number. We therefore conclude that Equation 13 holds with equality for at least one value of
Let Ex be this value of that satisfies Equation 13 with equality. For all 2 0, 7 ke can be rewritten
as
+ ke v(x,(x) + k(e 6x)
13

---

Published as a conference paper at ICLR 2024
Since + he u(x, e) for all 0, we conclude that & is in ax(x, 6x) which completes the proof of the first part of the proposition.
Part 2:
For the second part of the proposition, with a fixed e 2 0, define the linear function of E' 2 0
a(c') == o(x,)) c) 6(x; <) - c) By the convexity of uxx c), a(e') S v(xx for all e' 2 0. In particular,
Tx = a(0) S vxx, 0) E [f c)]
c~p
as desired. Observe that a('') can be rewritten in terms of Tx: a(é') = Tx + e)x,
To show that 5(x,c) (xs(x; 7x), it remains show that there is 0 k > 8(x, such that v(x, <') 2 Tx + ke' for all e' 2 Let k: = 6(x, <) + for some y > 0. If 0,
Tx ke Tx + (ō(x, E) + 7
aat) +
v(x, E) + +E
> o(x E) as desired. I 0, first observe that, by definition of 5(x, 0), v u(x, e') v(x, 0) 0(x, 0) as e' O.
e'
Thus, there must be some e' such that
v(x, E') v(x,0)
< <6(x, 0) +7-
e
Rearranging,
u(x, c') u(x, 0) < (6(x, 0) + +7) v(x, e') < v(x, 0) + (ō(x, 0) + 7)) v(x, e') < - kē'
as desired. To show Equation completes the proof.
choose to obtain Tx = v(x, = Eeup [f(x, c)l, which
A.2 PROOF OF THROREM 4.1
Theorem 4.1 If the following assumptions hold:
1. The kernel k is the squared exponential kernel or Matérn kernel with >> 2;
2. the distribution distance d is the total variation (TV) distance;
3. for all S T, the true distribution pł satisfies the following:
(a) d(p:, P?) S Czi
(b) for all e E [[C]], Pi., 2 Pimin > 0.
then TS-BOCU (Algorithm
7 incurs T T-period Bayesian regret bounded by
BayesRegret S 0 a (00a(VTTT) (OVT(ArrT A2) 12) (T2 (C)
Σ E Bc,]))
+ (I In Ci Pmil v T(AIT + A2) In Tm [C])
(14)
where TT (xx, (1/2) In I + σ Krl is the maximum information gain, B maxxex [[f(x)].. 7 = mab, A = In(1 + o 2)-1, A₂ = Lm? and L, a and are kernel-dependent constants.
14

---

Note that Published as a conference paper at ICLR 2024
Proof. Under the assumption that the kernel is the squared exponential kernel or Matérn kernel with 2, GP sample paths f satisfy the high probability bound ((suP(x.e)xxxxc @((x.c)
Pz. J)
ae (J/b)/ for all {L,..., m) for some kernel-dependent constants a and b GGhssa & Roy 2006).
To enable the analysis of a continuous, infinite decision set X' C IT we adopt the iterative dis- cretization method first developed by [Srinivas et al. 2010) and refined for Thompson sampling by KKandasayy et al. (2018). The general idea is to use an increasingly fine sequence of discretiza- tions of X and show that, due to the assumed high probability bound on the GP sample paths, decision x and its closest neighbour in the f-th discretization [x], share very similar function values.
Recall that X' is a compact and convex subset of R. for simplicity and without loss of generality, in this proof, we assume X' is subset of the [0. 11 hypercube. Let be the discretization of the [0, 1]md hypereube at iteration with Ti t'maby T equally spaced decisions along each dimension. Define
such that | < T(". [x]= is then defined as [x]x = arg min ||x ||x - [x]=ll I ||x [x]ell I m/T, for all x E X.
x'122-
In this proof, to reduce clutter, we define (making the dependence on ex, I, Pr, explicit)
(x) v(x, Esj f. Pt. (x) == 5(x. c: f..
The proof relies on an upper confidence bound sequence Ug of the form
U,(x) = (xx(x) + (x)
(x(x)
inf q (x()
qEl(p)dd..))
8x(x) : max
inf fx (x (x) 1-0 (g(l(paderott))
lim
qT 4p
inf
q pp))
qEM((p,d..s)
(x(x) == (x + v 11,),-((x). L((x) px-1(x) (B
where (B))T1 a sequence defined as Ar = 2l((( + 1)I & (2T) 1/22)
The initial part of the proof adapts the method of Russo & Van Roy (2014) and Kandasamy et al. (2018) in expressing the T --periodd Bayes regret Thompson sampling algorithm (accounting for discretization)
BayesRegret(T)
Σ E (x -x:
E E (x,) - (x())) Hi]
(x - (xx)) - U.((x])) 9(([x])) - ((x()))
+ *a((x())) (x((x))e) H.]]
Σ E (Uo((x))))) (x((x))))) (ec((x)) ((((3))) + (oe((x))e)
(x()))
(xx(x)) so((xi).))
Σ E -(())) ((x())))))) (c((x))))
+ ((vx((x))) - a((x;))) + ((x+()) -e((x())))
+x(vx((x)))) + (((5)))))((()())))))))))) - -x((x.)
15

---

Published as a conference paper at ICLR 2024
a(vi((x;]) vx(x))) + ((6x((x)))) -z
(E (ee(( ([x)) + +B [vux((xx - de ((x()))
D1
[e((x)))) ((((x)))e) +E [x((1x)))) ((x())))
D2
(EE (ex() vx()x]] + 13 (ve((x))) vx()))))
(IE ((x,)e) 6x(x,) )] + E ((x) 10) 6z (x55))
D4
where (i) follows since, conditioned the history Hr, Uf is deterministic and and x are identi- cally distributed due to the manner in which each X2 is chosen (Thompson sampling), therefore [x,] and [x]] are identically distributed as well.
Applications of Lemma A. to bound Dj (DRO objective regret), Lemma A.3 to bound D2 (DRO derivative regret), Lemma A.6 to bound D3 (DRO objective discretization error), and Lemma A.7 to bound D2 (DRO derivative discretization error) bound the terms in the sum separately to arrive at
T(Ar A2) (Te))alic)) + Σ E [BEe]
BayesRegret (T) S a0
1n (Te)& + Vin (TH + IIn [c]
+ 30
Puin
T(A17
+ 3T²
+ 2
+
4E [Be]]
6
3
0
a
T(ArT A2) In (T T: CT) +
E (Bc,)) )
+ 3 (L
(T2TT/l + / |n + Pmi V T(AnT + In (C))
which completes the proof.
A.3 PROOF OF LEMMA A.1
Lemma A.1. If the following assumptions hold:
The kernel is the squared exponential kernel or a Matérn kernel with v > 2; 2. for all T, the true distribution Pt satisfies d(pr, ((),,p)) S for all t T,
then the sequence of decisions {x,)T_ chosen by Algorithm 1 has a corresponding sequence of discretized decisions {[xx)e)T that satisfies
T
[(x((x))))) vx([xx)() + [ox((())) (x((x))))
T(AiT + A2) (TZ)&alIe1)
T
+
Σ E Bea
(15)
where (x(x) == u(xx J. f. Pt, d), A 1h::1(11 1n===(0---2-1111 A₂ = 1 Lm² 5/2 L, a and b are kernel- dependent constants, and B is complexity parameter that depends on distribution distance d and
16

---

Published as a conference paper at ICLR 2024
f. For example, B has the following specific forms for maximum mean discrepancy (MMD) and total variation (TV):
maxxEx [|[(x)]la-~ if MMD,
B
maxxex ||f(x)]
if = TV.
Proof. Define
q == arg min qEulpp.d.es)
q q"ux((x:)))
qf arg min q [[((()))))
qEl((p..d.s))
We first bound the sum of E [e (xx)) ey [x]))] terms in Equation 15
The proof adapts the proof
techniques of Kirschner et al. (2020) to the Thompson sampling algorithm.
T
E ((x(())))) - ue ((xx)))))
Σ
E
qe ((x.))))))) qf [((xx))))
T
E
p
(xxi)))))) q6 f((xx]e)
E Pi
(ue((x))e)) f(xx))) + (Pī af) (((x)))))))
(16)
We first focus each E IP plies the law of total expectation and makes explicit the random variables with which the expecta- tions taken with respect to (recall that all expectations without explicit subscripts are taken with respect to f and Hr).
([x)))))) f((x)):))
term. The following analysis repeatedly ap-
p (ux((x))) - f((x)))))
[p: (ui((xilt) f((x))))]
(17)
S.H.lle.)
(4)
E [u((((x))) - (aa0))((([() f(xx)e,, ct) Is, H, [cai]]
E
f.H.lle
[ur([xi]rr c)) - f(xx)e cz)
f.H.
[ c.) f((x)]e. cx) Hc]
H.
(286)
u (1x,) c.) ,, 1f(xx111 cx) H.]
H,
E
(ue ([xeles ct) Me- - ((x
H. V c.)
E (x)
(18)
where (i) follows since ux(())))) is constant given all random variables in H, except c, and f([x)]e) is constant given f and x;; (ii) follows since C₁ ~ p and is independent of f and He \ {c.): and (iii) follows since u, constant given H,.
We refer to the proof of Theorem 4 in Tay et al. 2022) (Equation 81 onwards) to obtain
E (p:
qf)
TT)TF((()) f[x]))))
$ 2E [Be]]
maxxex
if d = MMD if d = TV.
B ==
maxxex [[f(x)]
17

---

Published as a conference paper at ICLR 2024
Substituting these into Equation 16. following cretization,
Srinivas et al. (2010) and accounting for the dis-
E [x,,)x [x(x),]
(19)
T
E
+ 2E [Ber]
(20)
T
E
TTr (11
+
E [Bc]]
t=1
T
E
T3rV
(0 10 |
I
4bm
+
E
[Bee]
1=1
E
TBT
Lmbabr)/2 02 02 Di=1
ci)
+2 [Bec]
3
(188)
E
2 VTBTV
Lmpabx In
-
In(1 + t0= +0-00000000000000 (x,,
+2 E
r _ [=1
[&
3
11=
(i0)
2 (1r In - Lmn +
TBr
E [Be]
(21)
t=1
where (i) uses the Cauchy-Schwarz inequality; (ii) follows from Lemma A.9 for some kernel-
dependent constant L; (tii) follows since x/ [n(1 + x) 2 and is increasing for all x > and k(x, c; c) 1, therefore a ? [x,, Ct) < a In(1 + to 3) + a o 1 ct)); and (iv) follows from Lemma 5.3 in Srinivas et al. (2010) on bounding the sum predictive variances with the information gain of the selected points.
Remark A.2. Step (it) of the above chain of inequalities a necessary step that was omitted from the proof of Theorem 11 in Kandasamy al. (2018), in Equation of their paper. The sum of posterior variances of the discretized decisions {xx,] i=1 cannol be directly bound by the informa- tion gain, since each [x1]e was not selected by the algorithm and are present only in the analysis.
The algorithm selects {x and thus Lemma A.9 is needed to bound the difference in posterior variances.
We next bound the sum of E (v [x] b) - êr ([x]]+)] terms in Equation 15 by adapting the proof of For any decision E X, re-define
Lemma 2 in Russo & Van Roy 2014).
qe
arg min q (x;))) qEM((..d..))
qf
arg min q [(() qEU()..de)))
Considering the term at iteration for any such x,
E [xx(x) (x)] = q f(x)
q.' T u, (x)
< E
q T (f(x) -x(())]
E
Tee (x(, cx(
EEC
Te ( un(x - -
LEEC
Σ (f( ((xxxx))lf((xcc) u((xc)>00
<
Loec
18

---

Published as a conference paper at ICLR 2024
Σ - (x 0]]
SEC
Σ
E [. -x > 0] H.]]
He
SEC
Conditioned on H, (f(x, c) (x(x))) (x) (x,
c)). Using the fact that,
if X o2), and μ Σ 0, the expectation E [X 0]] -o ov exp( (#² dx S
v2v expl -1((-(1)) 202 we continue with
0)-1(x.c)
(-
11 (-2
E [x) - 0x S
E
exp
2
2
CEC
0 (x, c)
E
Hi
(12 + 1)1211111
REC
(t2 + 1)
where the last inequality follows since k(x, x; c) 1 by assumption, for all x E X and C. The sum of E [(x((x)))) - d<([x]])]] terms can then be bounded with
T
Σ
E (ex((x)))) (x+)))
max(0,,E - -xx)))
x
T
1
(12 + 1)
1=1 x
<
Finally, combining this result with Equation 21 and substituting in the value of Br, we arrive the result
(x,( ve (x))
( (x,))
1=1
2 ImP2bbr/22) In (111)(1(((2m)11)) ( 1r (mrln(1+
2T <
2 Σ E [Ber]
(v (VT(AAT + A2) (T9)2;1Ic)) + Σ E Bcal
=0
where A In(1 - and A₂ 5bb which completes the proof.
A.4 PROOF OF LEMMA A.3
Lemma A.3, the assumptions Theorem 4.1 hold, then the sequence of decisions (xx) T chosen by Algorithum I has corresponding sequence of discretized decisions {[x,)<171 that satisfies
E (xx(())))) - (1x.o)))) + E [<<((x]1))) - 8.(1x,1)]
0 Pmil v T(AIT + A2) (T9IT8IcC) + v in (19)&811()) + vincel
(22)
where 8,(x) = 8(x, ex: f. f.Pr. d), A = In(1 + o -)-- A = t LLm²abr=/? and L, a and are
kernel-dependent constants.
19

---

Published as a conference paper at ICLR 2024
Proof. Define the following:
1
(p:(x)
arg max (u h00 h (et
lim
min
q'p qel((pdde))
min
q'
q.
arg min q (P:((x))c) qEU(pp,dee..)
9: == arg min q (x((x))))) qEM(p,,de))
4 = arg min q f((x)))
(EM(pr,dect))
9: == arg q f(x())) qell(p.d..s)
We begin with each (<((x)))) - ((x()) term, leaving out the sum and expectation for now.
((x)))) - ((,,))
lim (( - T (x:((()))))) (a - q.) (((x))))))
h-0
lim 1
h h (h(e,- - e sp: ((x1))) - h(e,- - - e TT(()))))
(e,- ext) (p(((x))))) (ej- *((x(())
p(((xx)e) - +i((xxl)):+ - -((x)()) + +(xx))))
pe((x))e)s f((xole)s + f((xx]))) -Pe((x))))
((((x))))) f((x)))))) + f((x)e)) - <<((xx)))) - (e((x))))o)
S (we((x)))))- f((x)))))-) (f((x))))-
where (t) follows from applying Lemma A.12 and defining i- = arg min; uee (xx)))))) it arg m (xxe(()))) Gr. > 0), and similarly defining j and j+ with respect to f((x)), and q: and (ti) follows from applying Lemma A.13 where o some index in [n].
Putting back the expectation, taking steps similar to those between Equation 17 and Equation 18 in the proof of Lemma A.I.
E (xx.))) - de ((x.1)) S E [(u((xe)))))-- - -(xx)))-)+((((())))))))))))))))) ( (x(x))))oo]
(uu(tesl))) [ HH (c.H)
E H. H.Mo)
(BII(ZN))) (ct)) - (((xx)))))) )
[(un((x)))))-- - u- (( + (1--1 (xxeec) - (e((x)]))o)]
E H.Mo,)
[VBror-((xx)))) + (BLoo-1(xxii))
2
R He((c))
VB,
Br
max maxxo-1((xx)eee cEjm]
(8)
E Milee
VB+-
1
pj Te- (1x0)))
Pinin
2
E
E
VB cx) He [ci]]
Pmin Hel(o.)
c.
2
[VBlo--
Pmin
H.
2
E
(23)
Puni
20

---

Published as a conference paper at ICLR 2024
where (i) follows since max 0r-1 ((xl(( Ec=1 definition of Pmin in Assumption 4(a).
T1-1((xele)e
p; 1 by Poin
1
Observe that the right hand side of Equation 23 is that of Equation 18 in the proof of Lemma A.1
multiplied by Puis constant. Summing over and following the steps from Equation 20 to Equa-
tion 21 in the proof of Lemma A. yields
Σ E (xt)
6x(xi) <
2 Pmin
TBr Tr Ir
( o 2)-1+
_
(24)
We now bound the sum of E [x((x)) (xx))
terms in Equation 22 For any decision x E X.
E [6x(xx) (x)) (x()) > 0]]
(6)
S
IE
(x) 8c(x) > o]]
E
( - 8((x) > 0] H1]
17
(20)
(-):(2))) 1 [[6,(x) - 8x(x) > 01 H1
(01))
[
2
E
H1
(12 + 1)1,&11
(60) 2V2 2m
VBB. + 22 [c| (t2 + 1)
where (i) follows since (x) < O: (ii) follows since &x(x) is constant given H, {ce) (it))
follows from Lemma A.4, and (rv) follows from Lemma A.5
The sum of E (c(()))))) 8. ((xx)))) then becomes
be((x;]e) (xx(1)))) <
- -1(x)))))(( - (x(x)))) > oi]
(5x(x) (5x)) (x(x)) 0
E
XEX
2
VB + 2 2nn
(t2 + 1)/aal
(vBr+ 2V
V2ll
Combining this result with Equation 24 and substituting in the value of Br yields
T
E - 6o((x)1)) + E (xx(()))))) (xxxt1)))
2m1
T3r 1r 1n
1 Lmizabb3/2) + 2222T (vBr+ + 22
V
Puin
/T(ANTT + 12) (T2)2,1ci)) + 'nn (T9)&81ci) vincc
0 Panin
where A In(1 -2) and A2 1 Tmm which completes the proof.
21

---

Published as a conference paper at ICLR 2024
A.5 PROOF OF LEMMA A.4
Lemma A.4. Under the assumptions and definitions of Lemma A.3
for any x E X and S T,
V2T
[ox((x) 5((x) > 0 He
Σ
(12 1)|2
Proof. Let be the event {x)(x) - (x) > 0}. and B be the event {l((x) = f(x) I ux(x)) ie., the event that f(xx is outside the confidence bounds.
y [[]((x)) - (x)x > 0J He = [PA
2
P(B H.)
U (1f(x,c) < G(x,c)) ((fx)x)))<Gx...)) (f(xx))))) ( H.)
=P
OEC
(69)
P(U[(x,)) < lxxx, c)} H.)
CEC
+ + +P((((x,c) > 1x c)} H))
(602)
2|C|P <0)
(25)
where (i) follows since, by the definition of 8, (x)x,, if f(x) is inside the confidence bounds, 6x(x)
(x) S O, therefore B C A and [ B: (ii) applies the union bound; and (iéi) follows by defining the random variable X distributed as (v, 1) and recognizing that, conditioned on Hf, both f(, c) - (x c) and (x(xx)) c) f'x, e) are distributed as WV(3Br,,-10 c), ox c)).
Using & to denote the distribution function of the standard normal random variable,
P(X < = P X
V B < - /B.
Be
(0
4
$
2T (t2
&
where (1) follows from the Chernoff bound Mastin & Jaillet 2013). Combining this result with
Equation 25 completes the proof.
A.6 PROOF OF LEMMA A.5
Lemma A.5. Under the assumptions and definitions of Lemma A.3
for any x E X' and S T,
[xx) s (VB++ 2
Proof. Define
q" = arg argmin (cu(p..deeth))
q qT (x((x)
q = arg
mig min qel(peddee
q T (x).
8x(x) lim ((á q²) (x)(
h
( (x)x+ (x(xx)-
22

---

Published as a conference paper at ICLR 2024
max Po (x, c)
min fr c)
CEC
max ut (x, c)
min & ( c) CEC
eEC
(x,-1(x,)) + ( o)) CEC
min ( (
max CEC
(4) 22 B: + max /4-1 c)
min M (x) CEC
CEC
where (t) follows from Lemma 1.12 and (ti) follows since k(x, c; c) and hence the posterior variance 0x-1(x, c) I 1 for all t, x and c. Taking expectations,
E H1
8x(x 22 Be
E H.
max 14- 11-1 c)
min (x.1
(26)
CEC
H. |EEC
We now bound EH, [maxcec 14- (x, c)]. Recall the closed form of the posterior mean (x=1((x, c):
Pr- (x, c) k c) (K,-1 + +o²1)=
= - c) y1-1
where we have defined a, ax c) = (K,-1
ki (x, c). Now, denote the relevant random
variables in H, as X,-1 (x+) and C--1 = {c+ with yt-1 having its usual definition.
E max - (x,,
E
max a 1 c) yt-1 X1-1, C--1 NA-1,,--1]] CEC
(27)
H.
CEC
X1-1,C--1 yr-1
Since y:-1 conditioned on C,-1 is distributed as \O0, K,-1 + o²1), for each E C, a ax_1(x,c) yr-1 is distributed as NO0, ((0,a--1(x,0) c)
( + o'T)),-((x,c))
k c) [K + II) (x, =1 2 (x, c). Henee,
max a a LeC
1x, (x,c) ( yt-1 X C.-1 = E
(28)
Y--1
2 max Ac CEC
Ag N o (x.
The random variables Ae are in general not independent. However, the following method to upper bound IE [Z] does not assume independence. Letting b be some strictly positive constant,
EE
82
IE
max bbg CEC
E [e.h [Ac]
cEC
Cle20((1-07 =(x,)))
(#8) < Cle
where (i) applies Jensen's inequality; (i)) uses the definition of the moment generating function of
a Gaussian random variable; and (did) follows since the posterior variance < o c) $ 1.
Setting 6 2 In [C| and rearranging the terms, arrive
E E < 22 CC]
Combine this result with Equation
27 and Equation
28 to conclude that
F H.
max N 1 c) CEC
< 122m
due Sivaraman htttt:tt///m/t
23

---

Published as a conference paper at ICLR 2024
Finally, observe that mincge' Mc-1 (x, c) maXeec (x,-1(x,c) c). Since yt-1 conditioned on X,-1, Ct-1 has mean 0, - (x, c) has the same distribution as f4- (x, c). We use this fact to conclude from Equation with previous result that
E 5x(x)) s (VBV 22
which completes the proof.
A.7 PROOF OF LEMMA A.6
Lemma A.6. If the kernel is the squared exponential kernel or a Matérn kernel with then for all t & T and x E X,
1
[1xx(x) vx([x)(1]] S 21E [Be]]
(29)
2f2
where complexity parameter that depends on distribution distance d and f. For example, B has the following specific forms for maximum mean discrepancy (MMD) and total variation (TV):
maxxex [[f(x)]lm=+ if d MMD
B
maxxex [|f(x))]
if TV
Proof. For this proof, define
q1- arg min q [[(()
qEM(p))d
S2 = arg min q f((x)))
(EM(ps.dess)
E [[x) - 2x((x))) = E |1 f(x) q f((x):))
E [[(q] q22) [f(x) 4 (f(x) f((x)()
< E [[(q) - -2) [ (f(x) - f((x),))
(
< 2E [Bec] + E c (f(x) f([]]))
(1)
< 2E [Ber] +
2/2
where (i) follows the proof of Theorem in Tay et al. (2022) (Equation onwards) since qi and q2 are at most 26, distance from each other via the triangular inequality with p.; and (ii) follows from Lemma A.S. which completes the proof.
A.8 PROOF OF LEMMA A.7
Lemma A.7. the following assumptions hold:
1. The kernel le is the squared exponential kernel or a Matérn kernel with v >> 2;
2. the distribution distance d is the total variation (TV) distance.
then for all t < and x E X.
1
E [1x)(x)) (c(()),))
(30)
Proof. For this proof, define
q
arg min
q T f(x)
q1 arg min q f(x)
gell(p.d..))
24

---

Published as a conference paper at ICLR 2024
q2 h arg min
q f(()))))
Q2 = arg min q f([x]x)
qEU((p...e.)
lim 1 ((q) q1) f(x)((x - (q2 (2) (e)[(((x))))
E [xx (x(x)] = E
h
E
lim h-+0
(h(e, ext) [f(x) hle, -e,1) [T([x]))
E
(|c 0₁ Tf(x) (ej 901) - ][((x()))
[x((x) 1(x)+ [(x)))) [(x))))++
$ [1x( f(xx)))))- + +((xx))s+ - f(x)++]]
B [[(f(x))- f((x)))-) + (f((x)) f(x)o)]
(68) 1
2
where (i) follows from applying Lemma A.12 and defining { = arg f(x),, it arg max; 91, > 0), and similarly deñning j and j+ with respect to f((x):) and q2: and (fi) follows from applying Lemma A.13 where is some index in [n]; and (iti) follows from applying Lemma A.8 which completes the proof.
A.9 PROOF OF LEMMA A.8
Lemma A.8. If the kernel is the squared exponential kernel or a Matérn kernel with v > 2, then for all L T, E X and
1 2/
E [1f(xxcc) [[xx),,)]]
(31)
Proof. Recall that, under the assumption that the kernel lo is the squared exponential ker- nel or a Matérn kernel with v > 2, GP sample paths f satisfy the high probability bound ((suP(xx.)) 2f(x.c) > J) < ae (J/b)² for all i {1,...,m) for some kernel sumeeldependent con- stants and 6 (Ghosal & Roy 2006). The lemma then follows directly from the proof of Lemma 12 in Kandasamy et al. (2018), by choosing L in that proof to be sup;= (x @f(x.c) and noting that the presence of the context variable does not affect the g norm since it is the same in (x, c) and (xx),.). c).
A.10 PROOF OF LEMMA A.9
Lemma A.9. If the kernel is the squared exponential kernel or a Matérn kernel with 2, then for all I S T, x E X and c E C,
4Lm
- -x c))
where L is a kernel-dependent constant.
Proof. The proof relies on the following lemma developed in Shekhar & Javidi (2020) and re-stated as in Li & Scarlett (2022;
Lemma A.10 Shekhar & Javidi 22200), Proposition and Remark 5), For any in the RKHS Hss associated with kernel k with RKHS norm [[ less than Wr, if the kernel k is the squared exponential kernel or a Matérn kernel with v > 2, and is constant, then f is guaranteed to be Lipschitz continuous with constant depending only the kernel parameters.
25

---

Published as a conference paper at ICLR 2024
We will first show that the terms making up the GP posterior covariance at any iteration are in Hx with RKHS norms bounded by fixed constants, as in the proof of Lemma F.2 in Vakili et al. (2022). With the above lemma, this implies their Lipschitz continuity, which allows the discretization error to be bounded.
To simplify notation, define the joint decision-context space 2 == X' x C, and joint decision-contexx vectors z E 2, z = (x, c) for some x and c. The kernel originally denoted k(x, c; xxxx'') .c') can now be simply denoted k(z, z²), and the kernel vectors and matrices defined the start of Sec. 4 can be cast in terms of z similarly. The posterior variance at iteration of (x, c) Equation g can now be simply denoted o Let [z]: denote ([x],,c).
Define
g(z,) -) v=())] k.-((-)
v(-) = (K,-1 - k(-)(t)
Note that (z) k(2,z) 2).
[k(2,, )lze. v (k(z.)) A:1( +1) V //(2, 2) =
by the reproducing property and the assumption that k(z,z) for all z.
l1 >l (v(z) [aa))kkk- (k-1(),v(z)) k(- ()))())))))) Hh.
@ v(z) K2-Iv(z)
v(z) (K,-1 + 0 o²1) v(z)
v(z) (K,-1 + +0²1) v(z) - v(z) T (o²1) v(z)
4(2,2) - -o'v(zTTv(l
S ((6,2) z)
2 klz z) =
where (i) follows from the reproducing property, and (ii) follows since the GP posterior variance (z) could be negative if this inequality were not true for all z.
Since (k(2,-)lxz I and [lg(z, ,l,, < 1. by Lemma A.10 k(z,-) and g(2, are Lipschitz continuous with some kemnel-dependent constant L. Since ([2))..) are also I--Lipschizz continuous. Recall that the choice of discretization X, leads to | [z]ellz S m 74- Using these facts,
arbitrarily chosen, k([z]e.)) and
Lm
[k(2, 2) k([z)), [2]:)| S 2) - k((2),, 2)]
2Lm
s (k(,,z) - k(z, 2)
2Lm
Tt
By the same argument, 10(z, 2) ((2),, [2]:]] < 2.m
We thus conclude with
(0) o2 = |k(2, 2) - q(2,2, - *[[x],, [2]+) + <(z)),, [z]{]
< |k(z,z) z) A(z],. (z])) + [g([)) [z]c) q(2, z)
4Lm
Tt
which concludes the proof.
A.11 PROOF OF LEMMA A.
Lemma A.11. Without loss of generality, suppose the entries of f E B are ordered such that
h f2 2 ... 2 Jn. For given reference probability distribution p and margin e, let l be the first
26

---

Published as a conference paper at ICLR 2024
index such that Ex=1 Pi > 2. If d is the total variation distance and q is probability vector such that, if < n,
0,
for 1 2 i k,
2==1 Pj
k
2 for i h
Pi.
for k + 1 1 < n,
Pn
+ 21
for i = n,
or if or k does not exist (i.e.
Σ Li=1 Pi S 5)
0,
for 1 <i< <
qi
1, for i
then q E arg min dEu(..de q r.
Proof. q is the solution to the convex optimization problem
min qEa*
90(q) = q
s.t.
((()) q: S isisn
gn+1(9) = lq p 0
h(q) =
q is optimal if there exists Lagrange multipliers X Kuhn-Tucke (KKT) conditions are satisfied (Rockafellar 1997] Theorem. 28.3). These conditions require the primal feasibility of q and the dual feasibility À as well as the following conditions on complementary slackness and stationarity:
1=+1 0 and v E R such that the Karush-
X.g((q) = igign+1
0 E 0g) + (g) + v
where & denotes the subdifferential.
We first verify that q is feasible. It straightforward to that 1 17 q and q Ž in all cases. We now show that p all, S 6. In the case that k < n,
p 1/lp
=
Pp: - qil
+ 1pk
9k + 1pp 9nl
$)
Σ
(pm (pn+7 )
pi +
Pk
Pi
2
Pn
k-1
Σ P4 +
D3 +
where the last equality follows since does not exist,
Ei=1 Ps á by definition of k. In the case that
n-1
1p- = Σ
Pi + (1 - (1-Pm)
n-1
= 2 Σ
Ps
1=1
27

---

Published as a conference paper at ICLR 2024
S
where the last inequality follows since Ei= Pi á since h = n. or it does not exist.
Clearly, if A: or k does not exist, is optimal since f = min; ft. which is the minimum expected value that any probability distribution can attain. We continue to verify the complementary slackness and stationarity conditions in the case that lo < The subdifferentials are
(g) (f)
0y: (q) = (-e)), 1sisn
0h(9) = {1}
where e; is a vector with all entries equal to 0 except the i-th entry. The subdifferential of 9++1 depends on q - p which has the form
Pi.
for 1 S < k. for k for h + S < n,
k-1 Ej=1 Pj
q p
2
for j = n.
2
The entries of the subdifferential of In+1 are then given by
for S ki
1 if EØ=1 < [-,,]] otherwise
k-1
for i = k,
(g)+ E
[,1]],
for k + 1 S < n,
(1),
for n
Without loss of generality, we set the k-th entry of 0g.+ (q) to be -1
To satisfy complementary slackness, since 9: for S 5 n,
A = 0, for k S i is n. It remains to choose the values of X for 1 S i k A and such that they satisfy dual feasibility
and stationarity.
The stationarity condition can be
system of variables, we introduce auxiliary variables o; E []], for k + 1 < i < indicating the specific value of the subgradient index that satisfy the stationarity equations since the subdifferential for these indices is the range [-1, 1]. The stationarity equations then become
equations. In addition to the dual
f: A; - Ant1 +v=0, 0, for 1 S < k
(32)
fk An-1 + ====00 =0
(33)
f: + Ant1d; + -v= 0, for k + 1 S iic < n,
(34)
An+1 -V= 0.
(35)
To satisfy Equation 33 and Equation 35 choose
-fn An+1
fk - fn
An+1
2 0.
2
For < í < k, to satisfy Equation
32 choose each X; to be
A fi Ap- +
ft fk 0.
For + +lissiiii n, satisfy Equation 34 choose each a, be
fi
An+1
fk St
Ji- Sa
E [-1,0]
ft - fm
fr - fm
where the last inclusion arises since satisfied, q is optimal and the proof is complete.
ft [0,1] and fi-fa Jn
[0, 1]. Since all KKT conditions
fx-F-
28

---

Published as a conference paper at ICLR 2024
A.12 PROOF OF LEMMA A.12
Lemma A.12. If d is the total variation distance and q = arg qelua(()) q then for all h S ge.k where k == arg max, (ff 4e.s > 0},
9eth 9: = h(e, ek)
where is a vector with all entries equal to except the k-th entry and i arg mingmin;.. ft.
Proof. The proof uses the closed form of q. prescribed in Lemma A.1I Observe that the index defined here is the same as that defined in Lemma A.11 when it exists, and that when S 9e,ks the index k for 4 is the same as that for The result follows from subtracting the closed form of qe+h from q When & does not exist in Lemma A.11 then qe+h qe and k in this Lemma, thus the result still holds.
A.13 PROOF OF LEMMA A.13
Lemma A.13. Let and f be vectors in IR", and suppose without loss of generality that the entries of ip are ordered such that 1p Z 422 2 ... Pp. Let q == arg min q yp and q
arg min (EUL(p.e) q with d being the total variation distance. Let i == arg max max,(4; {4p : q > 0}
and j == arg max, max qi > 03. Then, there exists some index E [n] such that
ff - p; S fc iPt
Proof. The result trivial when i j. The rest of this proof focuses on the case of i + j. The proof uses the closed form of q. prescribed in Lemma A.II Observe that the index i defined here is the same as & defined in Lemma AI.I when it exists. When does not exist in Lemma A. then arg min, fa and choosing & satisfies the inequality. We now focus on the case when
exists.
Suppose i. Then, by the ordering of entries in ip, choosing & = satisfies the inequality. if then we require the existence of an index such that / 2 and fr 2 fj- As a proof contradiction, suppose such index does exist, i.e., for all 2 i, fm Sj- Then, by Lemma A.11 4m 2 pm
for all m 2 i. Let = arg ming Su- Again by Lemma lo P. + t- With these facts, consider a lower bound on the amount of probability mass in q, attained by supposing o 2 and qk 0 for all k < i, k # j:
n
n
9k
2
43
Qk +
2
A=
Pk +
2
k=
Pk + =1
k=
where the last equality uses Lemma Le11 q. We have arrived at contradiction, since the amount of probability mass in must sum to I. Thus, when j < i, there must always exist an index & such that & and 2 fz- Choosing this index l satisfies the inequality and completes the proof. 0
A.14 PROOF PROPOSITION
If the distribution distance d is the lotal variation (TV) distance, then the deriva- tive upper confidence bound (x( defined in Equation 11 exists.
Proposition 4.2
Proof. Recall the definition of (x(x)
(x(x) : max lim h0 h (d
min
q
min qeu(p.dde))
q T x))
29

---

Published as a conference paper at ICLR 2024
The extreme value theorem for metric spaces states that continuous function attains its maxi- mum compact set. Thus, sufficient condition guarantee the existence of (x(x) is that lims-o T (mil q' millqe(((p...e. q (p) is continuous function.
From an application Danskin's theorem (Bertsekas) 1999 Prop. B.25), we obtain that the optimal value of distributionally robust convex optimization problem minqet((pp.dcc)) yp is convex function of 4 E R" This implies that the function Lipschitz continuous on the compact set u,(x)} (Rockafellar 1997 Theorem. 10.4), stronger condition of continuity. Thus, T (m th.,.th) 4p minget(pppdde q (p) is continuous function on A. It remains to be shown that the limit as - of function also continuous.
A == {p (x)
First rewrite Equation 11 as the limit of functions indexed by positive integers E Z by defining m
(x(x)
max ((p) 2, (x <xx)_))
Ç = lim Sm
m-00c
Sm (4p) = m
min qEUd(piddeect
q TTp x0 min qeu().d
q
By the uniform limit theorem, if each Sn is continuous and converges uniformly S. then Ç is continuous. Recall the definition of uniform convergence: (m converges uniformly to Ç if for all y there exists M such that, for all m Z .M and all yp E A. IC({)) - (mm+)) t7.
We have previously shown that each Sm is continuous for any choice of convex distribution distance d. We now prove the uniform convergence of Sm. when d the total variation (TV) distance.
For some vp E A. consider a permutation of the entries of such that (breaking ties arbitrarily, without loss of generality)
Po; 2 Po, 2 ... 2.. Po..
To ease notation, for the rest of this proof, we drop the iteration subscript from the reference distribution and the margin 6, Apply the permutation to &p and the reference distribution p to get
80" = -(Po1) Pozy Po.)
Dd (Po, Poz ... Po
Now define
Φ min T0
gel(("..de..)
Under this permutation of entries, q. will have the form prescribed in Lemma A.11 Note that we are solving an equivalent problem since the objective and constraint functions are all finite sums of vector entries (a feature of TV) and permuting them does not change their sums. As in Lemma A.1I
let k be the first index such that D Di=1 P? define
E/. Then, noting that k does not exist if >n 2i=1 P 2
E p - : if l exists, 20,
80
otherwise.
l exists, for any m >
(m(xp) = mmma +
- 9.)
1
(9 T Txp
( C.
h
p4 +
+ h
2 (i))
(G. + (oupi)
2
1
v
2
where (i) uses the closed form prescribed in Lemma A. and the fact that, for h < cf, the in- dex ls stays the same. Since the final term is constant with respect to m, conclude that
30

---

Published as a conference paper at ICLR 2024
(m( oo (1(4)) (((p) when m 1 If k does not exist, for any O, Sm (mp)) = -im (( = ((4p) = since all terms in this sequence share the same form ac-
cording to Lemma A.11
Consider the index set {0r, O2...., C [n] (order does not matter). Every 40 E A is associated with one such index set by the above construction. A can therefore be partitioned into finite number of equivalence classes (specifically, 2n classes), where each such equivalence class contains all 4 E A with the same index set.
Observe that, for 6i and 422 in the same class, ct:: = cP2, since c only depends on 6, and the index set. Give each index set meta-index [2n). and let ca denote the value of c² shared by all in index set a. Now choose
M
max ac(2") Co
where the maximum is guaranteed to exist since all Ca > 0 and the maximization is over a finite set. For all m 2 M and all y A, Sm (4p) = ((p)) and thus (m (m())= - ((()) = O. We thus have uniform convergence, which completes the proof.
B EMPIRICAL STUDY OF TS-BOCU WITH WRONG HYPERPARAMETERS
We also study the performance of TS-BOCU on various uncertainty objectives when the hyperpa- rameters are purposely misconfigured, i.e., when TS-BOCU is given values of a. 3 and e that differ from that of the true uncertainty objective. The results are shown in Fig. 3 for the DRO, WCS, and GEN objectives (identical to those in Sec. 5), and TS-DRO (TS-BOCU with a = 1, 3 = O), TS-WCS (a 0,
1), and TS-GEN (a 1, B = 1), evaluated on all uncertainty objectives including those with different values of a, 3 and We first observe that TS-BOCU with the same hyperparameters as the true uncertainty objective generally performs close to the best, as expected. The next interesting observation is that, under the DRO and WCS objectives. TS-GEN always per- forms better than the other 'wrong' algorithm (i.e., better than TS-WCS under the DRO objective, and better than TS-DRO under the WCS objective). This empirically supports the interpretation that choosing values of a and ,3 to be both greater than 0 results in an algorithm that 'interpolates' between DRO (a 1) and RS (8 1) objectives in the sense that it performs decently well on both and can be seen as 'robust' to the choice of uncertainty objective used to evaluate performance.
C EXPERIMENTAL DETAILS
C.I EXPERIMENTAL SETTINGS
Supposing the decisions have dimension m and the contexts have dimension L, all experiments have domain [0, 1| x [0, 1] by normalizing to this set from their original domains. We set the number 1024, and the number of contexts |C| n = 64. The reference distribution Pa at all iterations is a Gaussian with mean 0.5 1, and covariance 0.2 Ie (where 1, and I, are a vector of ones and the identity matrix respectively), discretized into probability vector of size n. The true distribution P at all iterations is a uniform distribution over [0, 1] discretized into probability vector of size n. The margin at all iterations is d(p:. P?).
of decisions X
During the learning procedure, use GP with mean 0 and a ARD squared exponential kernel with k(x, c; x, c) = 1 and lengthscale 0.1 for each dimension. We set the observational noise standard deviation 0.01, and the number of initial observations the start of each learning procedure to be
For BS-BOCU, approximate sampling from the posterior using random Fourier features (Rahimi & Recht 2007) with 1024 features. For all UCB algorithms, we set 3 = 2 for all iterations.
Samples from GP prior: procedure described above.
2, l- = 2. The GP prior is the same that used in the learning
Hartmann 3-D: 2, l 1. The first two variables in the input are the decisions, while the
remaining is the context. This function is described at [htpp:: /www. s fu. -ssu/ jano/ hart. html
31

---

Published as a conference paper at ICLR 2024
DRO (a 1, = 0)
WCS (a = B, = 1)
GEN (a = 1, = 1)
TV
MMD
TV
MMD
TV
MMD
2569
00
2080
15
350
GP
230
1590
580
230
230
430
1000
380
700
3.0
1000
1090
582
1003
352
HARTMANN
1359
2000
1590
000
030
400
-20
230
120
3000
383
PLANT
325
25
23
INFECTION
2500
130
2003
1500
30
1000
280
1080
280
1000
230
1000
383
1500
380
1000
323
2000
Figure 3: Mean and one standard enror (over 10 RNG seeds) of cumulative regret (lower is better) incurred against iterations by the acquisitions TS-DRO (TS-BOCU with = 1,3 = 0), TS-WCS (a = 0, 3 1), TS-GEN (a 1,9 = 1) with varying objective functions, uncertainty objectives, and distribution distances.
32

---

d.e(p.d.ecc)) Published as a conference paper at ICLR 2024
Plant growth simulator: eroscedastic GP fit to private training data on the growth of Marchantia plants within nutrient medium as a function pH (with domain [2.5, 6.5]) and amount ammonium NH3 (with domain [0, 30] in mM). This underlying function is the same that in Tay et al. (2022).
1, 1. This underlying function is the mean function of het-
COVID-19 infection simulator: m = 2, = This underlying function is function fit to COVID-19 simulator outputs with kernel ridge regression, using the same kernel as described above. The simulator was obtained from lbttps://githui wttp://eeeeee-eeeeee//ee- group-testing The decision variables sub-groups. the context variables are the initial number of cases within these sub-groups and the transmission probability, and the output is the number of resultant cases. This underlying function the same as that in Tay et al. (2022). For the full list of simulator hyperparameters, refer to their code.
proportions of test kits allocated to 3 different
The experiments were implemented in Python using NumPy (Harris et al. 2020). PyTorch (Paszke)
al. 2019), GPyTorch (Gardner et al., 2018 and BoTorch (Balandat al. 2020 For full details, refer to the code repository
C.2 BASELINES
In this section, we provide details on the baselines UCB-BOCU-1 and UCB-BOCU-2. These base- lines are naive extensions of the UCB algorithm for DRBO from Kirschner et al. (2020) that are computationally tractable but (as far as we can tell) have no theoretical guarantees on their perfor- mance.
UCB-BOCU-I:
(x) = (x)((x) + (x)
0. 11"(()) = min q (xux(x)
qEulip.d.es)
(x) = h
1 min q [x(x)) min qEU()..d.e))
q ('6((2))
At each iteration 1, UCB-BOCU-1 chooses x, = arg max U. U, (x). As compared to the true upper confidence bound U, described in the main paper, UCB-BOCU-1 replaces the maximization over all functions & in the derivative upper bound term with a difference between the worst-case expected values using the upper and lower confidence bounds of the function values. Note that the limit as h + 0 is infinity if (x)x > (x),, and as such the limit is replaced with a small constant > 0. Supposing that the derivative definition in the objective were similarly replaced with h, UCB-BOCU-1 actually uses derivative upper bound that upper bounds the true derivative with high probability. However, the regret analysis that emerges from this choice leads to factor of h-1 on the regret upper bound. Since we tend choose small values of h for good finite difference estimation of the derivative, this leads to very large upper bound on the regret which explains the poor empirical performance.
UCB-BOCU-2:
(19 = (x,(()) + (x)
1. (x)
min q" (x)
qElllp,,des)
1 (x) lim h (EU((..de.)))
q [x(x)) min q qT (Tuu(x)
min
qel((p)d))))
At each iteration f, UCB-BOCU-2 chooses X, arg max tr(2) (x). UCB-BOCU-2 replaces the maximization over all functions &o in the derivative upper bound term by simply choosing the upper confidence bound function instead. Unlike UCB-BOCU-I, the limit exists and the value of the derivative upper bound converges. This possibly explains its better empirical performance. However, there is theoretical guarantee that this choice of derivative upper bound has high probability of being greater than or equal to the true derivative, and thus there is (as far as we can tell) no theoretical upper bound the regret incurred by UCB-BOCU-2.
33


Reviews:
[{"review_id": "4Mc5wP9Oi0", "reviewer": "Reviewer_Lem3", "summary": "The paper extends the distributionally robust Bayesian optimization (DRBO) framework to a more general framework called “BO under contextual uncertainty” (BOCU). BOCU targets the problem of maximizing some uncertainty objective that takes the context distribution into account. Example problems include worst-case sensitivity, mean-risk trade-offs, DRBO, robust satisficing. The paper develops a general Thompson sampling algorithm that can optimize any objective within the framework. The paper also derives Bayesian regret bound for their developed framework. Finally, some experiments are conducted to illustrate the sublinear regret properties of the framework.", "questions": "Apart from my comments and questions in the Weaknesses section, the authors could answer the additional following questions:\n+ In Theorem 4.1, are the assumptions used common assumptions used in this particular research topic? What are the implications of these assumptions? Is it possible for these assumptions to be occurred in practice?\n+ Also, from Theorem 4.1, is the maximum information gain \\gamma_T bounded as in the standard BO algorithms? Which kernels will guarantee this maximum information gain to be bounded?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper is very well written and easy to understand. The problem settings, the previous works, the concepts are all well described.\n+ The paper tackles an interesting problem which is to unify different problems (with the same theme of BO under contextual uncertainty) into one framework. The paper also proposes a general method that can solves this unified framework with different objectives. Theoretical analysis is also conducted to guarantee the performance of the proposed method.\n+ The proposed method seems to be sound and reasonable to me.\n+ The experiments (though a bit limited) are also conducted in order to understand the behaviours of the proposed method and to confirm the theoretical analysis.", "weaknesses": "To me, the main weaknesses of the paper are in the experimental evaluation. I list in the below some weak points that I found from the experimental evaluation:\n+ The problems used in the evaluation (GP, Hartmann 3, plant growth simulator, COVID epidemic model) have quite low dimensions, ranging from 2 to 5.\n+ I found the analysis regarding the experiments could be further elaborated. Currently, there is only one paragraph explaining a lot of results in one figure (Figure 2), I have to think a lot in order to understand what the reported results convey.\n+ For the COVID infection problem, I found the results of DRO are not too good. I’m just wondering what are the issues of these cases?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "e1FOa7vxjI", "reviewer": "Reviewer_9tD6", "summary": "A framework for Bayesian optimization under contextual uncertainty unifies various formulation of Bayesian optimization, including distributionally robust optimization, stochastic optimization, robust optimization, robust satisficing, worst-case sensitivity, and mean-risk tradeoff.  The authors provide theoretical analyses on regret bounds and experimental results to compare several Bayesian optimization algorithms.", "questions": "* Table 1 can have a column for the corresponding references.  It would help understand and compare diverse algorithms\n\n* Could you explain the intuition and meaning of knowing $\\boldsymbol p$ at the beginning?\n\n* I am not sure that the ICLR paper format allows it, but the table captions should be located on top of the tables.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "* This work serves the comprehensive understanding of Bayesian optimization under contextual uncertainty.\n* Paper is well-organized.", "weaknesses": "* Paper is hard to follow.  For example,\n\nThe sentence \"While standard BO assumes that the learner has full control over all input variables to the objective function, in many practical scenarios, the learner only has control over a subset of variables (decision variables), while the other variables (context variables) may be randomly determined by the environment\" is too complex.  There are two whiles in one sentence.\n\nThe sentence \"We assume that, at every iteration, some reference distribution $\\boldsymbol p$ is known that captures the learner's prior knowledge of the distribution governing $\\boldsymbol c$\" is grammatically wrong.\n\n\"a probability vector in $\\mathbb{R}^n$\" should be \"a probability vector in $[0, 1]^n$\" for readability and understandability.\n\nI think there are other grammar and presentation issues.  Please revise your submission carefully.\n\n* I think that some assumptions are too strong.  For example, the assumptions on finite sets of $\\mathcal{X}$ and $\\mathcal{C}$ are not practical.  Moreover, I do not understand why $\\boldsymbol p$ is known at the beginning of the optimization.  This assumption is not practically meaningful.\n\n* Since theoretical results are built on the assumptions on finite sets of $\\mathcal{X}$ and $\\mathcal{C}$, they are limited.\n\n* Reasoning and justification behind experimental results are not appropriately provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "XX2vE9T675", "reviewer": "Reviewer_B6kd", "summary": "The paper studies robust BO when there is context uncertainty, and designs a TS algorithm based on a general framework that incorporate a large number of risk-sensitive learning objectives. The authors substantiate its efficacy with theoretical analysis and validate the algorithm's performance and adaptability through experiments.", "questions": "1. Is the first-derivative objective only previously proposed for GP, or is also applicable in other areas? Is 3.1 only novel in GP literature, or for the first time also in other areas? \n\n2. Why finite context and action space? These read very limited. Are they also required by prior works?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clear and easy to follow. The propose method is solid and with decent theoretical and numerical evidence.", "weaknesses": "The significance is of question to me - though it is good to have a unified form for multiple previously proposed objectives, the unification achieved in this paper seems straightforward (adding two parameters) and the additional technical challenge (e.g., in algrotihm design or analysis) is unclear, and it is not clear whether those new objectives are really of significance for practitioners.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "UZptIADEBl", "reviewer": "Reviewer_WGc6", "summary": "Many problem settings in Bayesian optimization (BayesOpt) require robust solutions to the optimization problem, where the decision maker needs to choose solutions that work well under different contexts that are not controllable.\nThis paper presents a formulation that generalizes many different BayesOpt settings related to robust optimization, and proposes using Thompson sampling as the optimization policy.\nThe authors first show a regret bound of this policy that is sublinear given specific assumptions and subsequently demonstrate the empirical performance of the policy under various optimization settings.\n\nEdit: After the rebuttal, I've increased my score from 6 to 8.", "questions": "- Instead of having both $\\alpha$ and $\\beta$, can't we follow the formulation of mean-risk tradeoff and only vary the weight for the $\\delta(\\mathbf{x})$ term, unless, for example, $\\alpha = \\beta = 1$ gives a different objective than $\\alpha = \\beta = 0.5$ (assuming the same $\\epsilon$)?\n- As I understand, if $\\epsilon_t = d(\\mathbf{p}_t, \\mathbf{p}^*)$ does not approach $0$ with probability $1$, we don't obtain the sublinear regret result.\nHow does this might affect performance in practice?\nCan we still perform well if $\\mathbf{p}_t$ is sufficiently different from $\\mathbf{p}^*$?\nAre there situations where $\\mathbf{p}^*$ is very hard to learn?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and has a clear exposition.\nI enjoyed reading through the formulation of the distributionally robust optimization problem and how it generalizes to previously proposed settings, especially by incorporating the right derivative of the objective.\nThis general framework allows relating many problem formulations that have been proposed in the literature.\nAs explained in the paper, by setting the hyperparameters, one can even realize novel optimization formulations that \"interpolate\" the previously proposed formulations at the extremes, which allows more expressiveness in designing optimization objectives that fit a user's preference.\nThe proposed TS seems to work well across the experiments.", "weaknesses": "The authors can consider inspecting why in various cases (in the Infection problem for DRO), TS-BOCU has almost linear regret.\nIt would be interesting to see if there are types of problems that the policy tends to perform badly on.\n(Perhaps this is connected to the insight that the algorithm resulting from setting $\\alpha, \\beta > 0$ tends to be more robust?)\n\nI am a bit confused about the assumption that $\\mathcal{X}$ and $\\mathcal{C}$ are finite: Is it necessary for the theoretical guarantee (since Section 4.1 mentions that the result can be extended to infinite sets)?\nIn the experiments (for example, with the Hartmann functions), are you constraining the search spaces to be finite?\nMy understanding is that  the algorithm can run on continuous search spaces too.\n\nI think the paper can benefit from extending the discussion at the end of Section 3.1 and offer guidance for setting $\\alpha$, $\\beta$, and $\\epsilon$ in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)