Robust Bayesian Satisficing
Authors: Artun Saday
Y. Cahit Yıldırım
Cem Tekin
Venue: NeurIPS 2023 poster (2023)
Keywords: robust satisficing
regret minimization
Gaussian processes

Abstract: Distributional shifts pose a significant challenge to achieving robustness in contemporary machine learning. To overcome this challenge, robust satisficing (RS) seeks a robust solution to an unspecified distributional shift while achieving a utility above a desired threshold. This paper focuses on the problem of RS in contextual Bayesian optimization when there is a discrepancy between the true and reference distributions of the context. We propose a novel robust Bayesian satisficing algorithm called RoBOS for noisy black-box optimization. Our algorithm guarantees sublinear lenient regret under certain assumptions on the amount of distribution shift. In addition, we define a weaker notion of regret called robust satisficing regret, in which our algorithm achieves a sublinear upper bound independent of the amount of distribution shift. To demonstrate the effectiveness of our method, we apply it to various learning problems and compare it to other approaches, such as distributionally robust optimization.

Robust Bayesian Satisficing
Artun Saday
Yaşar Cahit Yıldrım
Bilkent University
Bilkent University
artun. saday@bikeet.ed.. edu.tz
ed
Cem Tekin
Bilkent University
cemt cemtekin@ee, www.eeeee..kkkeeeeeee edu.
Abstract
Distributional shifts pose a significant challenge to achieving robustness in contem- porary machine learning. To overcome this challenge, robust satisficing (RS) seeks a robust solution to an unspecified distributional shift while achieving a utility above desired threshold. This paper focuses the problem of RS in contextual Bayesian optimization when there a discrepancy between the true and reference distributions the context. We propose novel robust Bayesian satisficing algo- rithm called RoBOS for noisy black-box optimization. Our algorithm guarantees sublinear lenient regret under certain assumptions on the amount of distribution shift. In addition, we define a weaker notion of regret called robust satisficing regret, in which our algorithm achieves a sublinear upper bound independent of the amount of distribution shift. To demonstrate the effectiveness of our method, we apply it to various learning problems and compare other approaches, such as distributionally robust optimization.
Introduction
Bayesian optimization (BO) 2 is powerful technique for optimizing complex black-box functions that are expensive to evaluate. is particularly useful situations where the function is noisy or has multiple local optima. The approach combines probabilistic model of the objective function with search algorithm to efficiently identify the best input values. In recent years, BO has become popular method for various sequential decision-making problems such parameter tuning in 3], vaccine and drug development 44, and dynamic treatment regimes (5).
machine learning
Contextual BO 6 is an extension of BO that allows for optimization in the presence of contexts, ie.. exogenous variables associated with the environment that can affect the outcome. A common approach to BO when the context distribution is known is to maximize the expected utility 7 g). Often, however, there exists a distributional mismatch between the reference distribution that learner assumes and the true covariate distribution the environment decides. When there is uncertainty surrounding the reference distribution, choosing the solution that maximizes the expected utility may result in suboptimal or even disastrous outcome. A plethora of methods have been developed to tackle distribution shifts BO; the ones that are most closely related to our work are adversarially robust BO (STABLEOPT) [9] and distributionally robust BO (DRBO) [1O]. STABLEOPT aims to maximize the utility under an adversarial perturbation to the input. DRBO aims to maximize the utility under the worst-case context distribution in known uncertainty set. We focus the contextual framework uncertainty set. This provides an additional level of robustness distribution shifts, even when the true distribution lies outside of known uncertainty set.
DRBO. However, unlike DRBO, our algorithm does not require as input an
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we introduce the concept of robust Bayesian satisficing (RBS), whose roots have been set by Herbert Simon [TT] his Nobel Prize in Economics speech in 1978. Simon mentioned that "decision makers can satisfice either by finding optimum solutions for a simplified world or by finding satisfactory solutions for a more realistic world". Satisficing can be described as achieving a satisfactory threshold (aka aspiration level) utility under uncertainty. It has been observed that satisficing behavior is prevalent in decision-makinn uncertainty and exhibit bounded rational behavior due to the immense complexity of the problem, computational limits, and time constraints [12]. Since its introduction, satisficing in decision-making has been investigated in many different disciplines, including economics [33, management science [7] The concept of satisficing has also been recently formalized within the multi-armed bandit framework in terms of regret minimization [99 20 21 22
scenarios where the agents face risks and
[4 15), psychology [16], and engineering
and good arm identification [23] Recently, it has been shown that satisficing designs can be found with a sample complexity much smaller than what is necessary to identify optimal designs
[23
Moreover, (11 demonstrated that when the future rewards are discounted, i.e., learning is time- sensitive, algorithms that seek satisficing design yield considerably larger returns than algorithms that converge to an optimal design. The concept of robust satisficing (RS) is intimately connected satisficing. In the seminal work of Schwartz et al. 241, robust satisficing described as finding a design that maximizes the robustness to uncertainty and satisfices. Long et al. [25] cast robust satisficing as an optimization problem and propose models to estimate a robust satisficing decision efficiently.
Inspired by this rich line of literature, we introduce the concept of robust Bayesian satisficing (RBS) as an alternative paradigm for robust Bayesian optimization. The objective of RBS is to satisfice under ever-evolving conditions by achieving rewards that are comparable with aspiration level even under an unrestricted distributional shift.
Contributions. Our contributions can be summarized as follows:
We propose robust Bayesian satisficing, a new decision-makee -maiing framework that merges robust satisficing with the power of Bayesian surrogate modeling. We provide detailed comparison between RBS and other BO methods.
To measure the performance of the learner with respect to an aspiration level r, we introduce two regret definitions. The first one is the lenient regret studied by [22) and [23] The second one the robust satisficing regret, which measures the loss of the learner with respect to a benchmark that tracks the quality of the true robust satisficing actions. We also provide connection between these two regret measures.
We propose Gaussian process (GP) based learning algorithm called Robust Bayesian Optimistic Satisficing (RoBOS). RoBOS only requires as input an aspiration level r that it seeks to achieve. Unlike algorithms for robust BO, does not require as input an uncertainty set that quantifies the degree of distribution shift.
We prove that RoBOS achieves with high probability Ö(TTVT) robust satisficing regret and Ö( + ET) lenient regret, where 'rr is the maximum information gain over T rounds and E, := Σi= amount of distribution shift in round t.
1 C is the sum of distribution shifts by round T, where q is the
We provide detailed numerical comparison between RoBOS and other robust BO al- gorithms, verifying the practical resilience of RoBOS in handling unknown distribution shifts.
Organization. The remainder of the paper is organized as follows. Problem formulation and regret definitions are introduced in Section 2 RoBOS is introduced in Section 3 and its regret analysis is carried out in Section 4 Experimental results are reported in Section Conclusion, limitations, and future research discussed in Section 6 Additional results and complete proofs of the theoretical results in the main paper can be found in the appendix.
2 Problem definition
Let f: x -> be an unknown reward function defined over a parameter space with finite action and context sets, X' and C == {cI...., cx) respectively. Let Po represent the set of all distributions
2

---

Table Comparison of optimization objectives.
Method
Inputs
Objective
SO
f. Pt
Find X' that maximize Bo (f(,, c]]
S
P T S,P,, A. 5.U4
Find x E X' that satisty Bew (I c]] 2
WRO
Find X that maximize min.ea, I (I)
DRO
Find x E X that maximize inf Eeep f c)]
PEll Find x E X' that minimize kxx) where
RS
Pt.T
k(x) min lo s.t. Bewrlf(r, c)) 2 T kd(P,P)), VP Po. 2
over C. The objective is to sequentially optimize f using noisy observations. At each round t E [T]. in turn the environment provides a reference distribution P. Po. the learner chooses an action 32 E X and the environment provides context C2 C together with noisy observation y: fzz, c.) + Te- where T)e is conditionally o-subgaussian given 2 C1 ,.....,,,.-...... Ct-1, 9t1 Ix; C.. We assume that is sampled independently from time-dependent, unknown distribution P E Po. which can be different than P.. We represent distributions Pt and P; with n-dimensional non-negative vectors Wt, and Wi such that ||w,]| || II = 1. We represent the distance between P, P' E Po with ((P, In particular, we consider maximum mean discrepancy (MMD) as the distance measure.
Optimization objective. To motivate robust Bayesian satisficing, we review and compare var- ious optimization objectives. Throughout this section, we assume that is known. The key novelty of our work is combining the new robust satisficing objective from [25] with Bayesian surrogate modeling to address unmet real-world challenges faced by BO. Robust satisficing aims to perform satisfactorily well over wide range of possible distributions on C. This is different from stochastic optimization (SO) (26] which aims to optimize for a given reference distribution P. distributionally robust optimization (DRO) (27 28 which aims to optimize the worst-case scenario in an ambiguity set Ld, usually taken as ball of radius r centered at Pt, and worst-case robust optimization (WRO) [29]. which aims to optimize under the worst-case contexts from an uncertainty set A of contexts, and satisficing (S) [30) which seeks for a satisfactory solution that achieves threshold т. Table I compares different optimization objectives. In RS, the objective is to find ot E X' that solves in each round t
K7,1 min k s.t. Ee c)] 2 - -A(P, P.), VP E E EE k20.
(1)
To find 27, we can first compute the fragility of x E X as
(xr = min s.t. [[ c)] 2 r AA(P,P)), VP k20.
(2)
When ① is feasible, the RS solution round / the one with the minimum fragility, i.e., x. E arg min (r,((r) and K,,, min (x). Similar to DRO, RS utilizes a reference distribution assumed to be a proxy for the true distribution. However, unlike DRO, we do not define an ambiguity set Ur that represents all plausible distributions on C but rather define a threshold value т, which we aim to satisfy. cases where we are not confident that the reference distribution P. accurately represents the true distribution P", finding a meaningful ambiguity set can be difficult. In contrast, has a meaningful interpretation and can be expressed as percentage of the SO solution computed under the reference distribution Pa over C given b
7x := max xEX
Unlike DRO, in RS, we certain that our formulation covers the true distribution P.". The fragility can be viewed as the minimum rate of suboptimality one can obtain with respect to the threshold per unit of distribution shift from P.. The success of action is measured by whether it achieves the desired threshold value T in expectation. Depending on the objective function and the ambiguity set, the RS solution can differ from the DRO and the SO solutions (see Figure for an example).
One particular instance this when P. the empirical context distribution. AWhen f is unknown, Z, cannot be computed exactly. However, one can reflect the uncertainty about f by using a GP surrogate model, by which upper and lower bounds Ze can be computed.
3

---

Fe-R [xx.c]]
[c-x:([(xc)]]
RS: r- 0.65 2
-22
C (Heatmap of f(x c))
DRO: - AIP: Pt)
Expected Reward
AIP;
X
DRO: r= 3AIP;
0.50
0.4
0.25
12
0.00
4.00
-1.33
1.33
3
Figure 1: Examples of RS, DRO, and SO solutions where Ze is the solution to the SO problem given in (3. For DRO, U, corresponds to a ball centered at P. with radius r. Rhombus, cross, and hexagon correspond RS and two other suboptimal solutions, respectively. Note that the SO solution corresponds to the point with hexagon, i.e., a suboptimal solution. When the radius of the ambiguity ball of DRO captures the discrepancy between P. and P perfectly, it selects the RS solution. When the ambiguity ball is too small or too large, fails to find the RS solution and selects a suboptimal solution.
An intriguing question is whether RS is more interpretable than U4 of DRO. While 25 provides a detailed discussion of the pros and cons of these two approaches, below we compare them on an important dynamic drug dosage problem.
Example 1. Type Diabetes Mellitus (TIDM) patients require bolus insulin doses (id) after meals for postprandial blood glucose (pbg) regulation. One of the most important factors that affect pbg meal carbohydrate (cho) intake [3]]. Let X and C represent admissible id and cho values. For E X. e C, let g(z, c) represent the corresponding (expected) bpg value. Function 9 depends on the patient's characteristics and can be regarded as unknown. The main goal of pbg regulation is to keep pbg close to target level K in order to prevent two potentially life-threatening events called hypoglycemia and hyperglycemia. This requires I, be chosen judiciously based on current ct- Patients rely on method called cho counting to calculate et. Often, this method is prone errors 132y. The reported cho intake &, can differ significantly from ct. In order to use DRO, one needs to identify range of plausible distributions for cho calculation errors, which is hard to calculate and interpret. On the other hand, specifying T corresponds to defining an interval of safe pbg values around K that one is content with, which is in line with the standard clinical practice (33]. We provide experiments on this application in Section
Regret measures. We consider RS from a regret minimization perspective, where the objective is to choose sequence of actions Z....., that minimize growth rate of the regret. In particular, we focus on two different regret measures. The first one is the lenient regret [22 given
T
RS = Σ (T Eowp [f(x),
(4)
1=1
where (+)+ = max(0,.). The lenient regret measures the cumulative loss of the learner on the chosen sequence of actions w.r.t. specified threshold that we aim to achieve. If an action achieves r the expectation accumulates no regret, otherwise, it accumulates the difference. Achieving sublinear lenient regret under any distribution shift is an impossible task. Note that even the RS action or computed with complete knowledge of only guarantees an expected reward least as large as ((P", Pt). Therefore, our lenient regret upper bound will depend distribution shifts.

---

We also define new notion of regret called robust satisficing regret, given
RT
Σ (T- Pi) Eo- (f c)))
(5)
RT measures the accumulated loss of the learner with respect to the robust satisficing benchmark Kit, (Pt, Pt) under the true distribution. In particular, the true robust satisficing action
achieves
Pe [f(=) [(([ttt]] c)] 2 - A Pt).
= Pt and ( is feasible for It is obvious that RT S. Ry. When there is no distribution shift, i.c., Pr = all t, then the two regret notions are equivalent.
In order to minimize the regrets in (4) and (). we will develop an algorithm that utilizes Gaussian processes (GPs) as a surrogate model. This requires us to impose mild assumptions on f. which are detailed below.
Regularity assumptions. We assume that belongs a reproducing kernel Hilbert space (RKHS) with kernel function k. We assume that k((x,, c), (x', ,')) (x(x, (eee<")ke( d') is the product kernel formed by kernel functions xx and ke defined over the action and context spaces respectively, Let the Hilbert norm |l of be bounded above by B. This is common assumption made in BO literature which allows working with GPs as a surrogate model.
GP surrogate and confidence intervals. Define 2 == == x C. Our algorithm uses a GP to model f, defined by prior mean function (u(2) [=] and a positive definite kernel function k(2, 2') = [1) (f()) ((='))). Furthermore we assume μu(2) = 0 and k(2, I 1, E Z. The prior distribution over f is modeled GP k(z, z')). Using Gaussian likelihood with variance À >> 0, the posterior distribution of f, given the observations y. [y ................................ 3r]] at points
Z: [=1.-... =e]_ is modeled as GP with posterior mean and covariance at the beginning of round
t 2 given as
p<(z) 12-1(2) (K (a X1-11) 9--1 k,,
(x, = k(2,2') 1 (x)T)))) [K,
(=) = kx(2,2)
where (2) = [k(2, 21. .,()),...(())))))) 21] K2 is the t x t kernel matrix of the observations with (Kt)as (2,, 25) and is the identity matrix. Let (2) == be (2(2, 2) represent the posterior
variance of the model. Define pan 0 and o=(=) = k(z, 2).
The maximum information gain over rounds is defined as [
log (det + +A-'KA))
max ACA'CC: Al=
where K, is the kernel matrix of the sampling points A. The following lemma from + which is based on [35| Theorem 2] provides tight confidence intervals for functions f with bounded Hilbert norm in RKHS.
Lemma 1.
34 Theorem 1] Let E (0, X x== max (0ax(1,4 A}, and
B.( :16):=om a 1og((dtttK + i)) + 2 2
8 + B.
Then, the following holds with probubility least 1 8: [x, c) - [xx c) S (,(5)or(z,c) c), Vo E X, Vc 1221
For simplicity, set À = 1 in the rest of the paper, and observe that log(det( (iaidet(KK,111 + 1 1,-1) < 21 When the confidence parameter is clear from the context, we use Br to represent B,(6) to reduce clutter. We define upper confidence bound (UCB) and lower confidence bound (LCB) for (x. c) E X' x C as follows:
(cb, := (1 + (x, c), (x, (x, (2,
For X, denote the corresponding UCB and LCB vectors in R" by ucb [ucb, (I)..,, [f(z, ,(,,,,,,,
and leb,, (e,.(,,,,,....,,bb(((,,, Also let fo
5

---

3 RoBOS for robust Bayesian satisficing
To perform robust Bayesian satisficing (RBS), we propose a learning algorithm called Robust Bayesian Optimistic Satisficing (RoBOS), whose pseudocode is given in Algorithm]] [ At the beginning of each round t. RoBOS observes the reference distribution wt. Then, it computes UCB index ucb, (x, c) for each action-conted pair (x, c) E X' x C. by using the GP posterior mean and standard deviation at round UCB indices, T and wy are used to compute the estimated fragility of each action æ, at round t, given as
por || we llar
if (we, ucb,)) 2
R (x)
+00
if (wr, ucb") <
where (C) represents the probability simplex over C, M represents the by kernel matrix and [w]]] M == Vw Mw is the MMD measure. Specifically, given the kernel kc : C x - R4, M is the kernel matrix of the context set C, i.e., Mij (c,, ej). The estimated fragility (x) of an action r, is an optimistic proxy for the true fragility Kr,((x), Note that when R ( < 0. the threshold J is achieved under any context distribution given the UCBs of rewards of z. On the other hand, if T > Eewp, (ucb,(z, c)], then T cannot be achieved under the reference distribution given the UCB indices, thus ( (I) oc. The next lemma, whose proof is given in the appendix, relates (T,((x) with (x))
Lemma 2. Fix R. With probability least 8, ( S Krr (z) for all æ X and
To perform robust satisficing, RoBOS chooses as 24 the action with the lowest estimated fragility, i.e., I2 = arg m (z). After action selection, Ct and yt are observed from the environment, which are then used to update the GP posterior.
Algorithm 1: RoBOS
Inputs X, C, GP kernel k, l40 a, confidence parameter 6, B
for f = 1,,2,.. 2.... do
1. Observe the reference distribution wy
Compute (c,, c) (4(x, c) + (,r,(,, e) for all x E and e
3. Compute (I)) as in
4. Choose action V2 = arg min (x)
5. Observe P and y/ f(x,, ct) + Tt
Use (It, Ct, } to compute p++1 and 0++1
end
Regret analysis
We will analyze the regret under the assumption that ① is feasible.
Assumption 1. Let &e == arg max (we, fa) be the best action under the reference distribution.
We assume that S (wis fe.) for all [T]) i.e. the threshold is at most the solution to the SO problem.
If Assumption I does not hold in round then [I is infeasible, which means that K,,; oc and there is no robust satisficing solution. Therefore, measuring the regret in such a round will be meaningless. In practice, if the learner flexible about its aspiration level, Assumption can be relaxed by dynamically selecting at each round to be less than (we, lcbly) where
arg maxxex (wr, lcb".
The following theorem provides an upper bound on the robust satisficing regret of RoBOS based on the maximum information gain given (6)
Theorem 3. Fix ó E (0, 1). When RoBOS is run under Assumption 7 with confidence parameter 8/2 and B, = (8/22)) where (,)5) defined in Lemmal 7 then with a probability of at least 8, the
IIndedd, our algorithm can be straightforwardly adapted to work with dynamic thresholds t., t > When we also change the thresholds in our regret definitions 4 and (5) to Te, and update Assumption 1 such that E (we, fa.). E 'T', all derived regret bounds still hold.

---

robust satisficing regret Ry of RoBOS is upper- bounded as follows:
12
R4 S 4,8r $
T 2 + 2log
8
Proof Sketch: Assume that confidence bounds in Lemma Thold (happens with probability at least Ky, (P, Pt) Pe [f c)] be the instantaneous regret. Robust
1 8/2). Let rf?
satisficing regret can be written as R2j = Et= rI[(" 2 0). We have
r S RT,elluz we M (wg ucb 2/ (wt ( (e(2),)))
(8)
S Kr,elluy we IlM (T Rr,allu wi willM) + 23, (wi (r(2),))
(9)
= |ml1 - we (Rr, - K7,1) + 28, (w), oz
- (3 (x,,
where (8) comes from the confidence bounds Lemma 1 p comes from the fact that our algorithm
at each round guarantees (wf, ucb,,) r R, w wy al and the last inequality is due to Lemma 2 The rest of the proof follows the standard methods used in the Gaussian process literature together with an auxiliary concentration lemma.
Our analysis uses the fact that under Assumption D both the fragility KiT,t and the estimated fragility RT, are finite. We also note that when > (W), Sa,) and P. * P:" then fi,,t 0o, and the instantaneous regret is (T (T- ( P.) - Pe (are c))) O. Setting fT as in Lemma Theorem gives regret bound of ((TrV The next corollary uses the bounds on "r from 36 to bound the regret for known kernel families.
Corollary 1. When the kernel k(z,z) is either Mátern-v kernel or squared exponential kernel, the robust satisficing regret of RoBOS, on an input domain of dimension d, is bounded by: Ö(T 2u 13d and Ó O(V respectively.
Next, analyze the lenient regret of RoBOS. As discussed in Section lenient regret is stronger regret measure under which even 2t can suffer linear regret. Therefore, our lenient regret bound depends the amount of distribution shift 6 = || wyl M. t [T]. We highlight that regret analysis of RoBOS different than that of DRBO in [0], which done under the assumption that ||w, wellM I é, for some (e))eety as input while RoBOS does not require (Et)aetry as input. Also note that é, S é,
0, t E (T). The major difference is that DRBO requires
Before stating the lenient regret bound, we let B' max llffllll.. It is known that B' < (M Amax(M'
represents the largest eigenvalue of M and B represents an upper bound on the RKHS norm of (10).
B By (inxxMM11nn where Xmax
Theorem 4. Fix 8 E (0, 1). Under Assumption ! when RoBOS is run with confidence parameter 5/2 with 3e = (,(5 where 3r is defined in Lemma ! then with probability of least 1 the lenient regret Ri of RoBOS is upper-bowe bounded as follows:
12 5
T
2yr + 22oog R S 4BT
+
B
Σ
4
Proof Sketch: When (w,, ucb")) 5, let Wh arg aax
T- (ww
be the context
-w l|ar
distribution that achieves (x)) We have
r = (wi f2.)
T (wā ucb".) + (w, ucb", - Smy)
< r (wi, ucb",, + (x
(10)
where (IOp follows from the confidence bounds in Lemma
Consider W. wt- By Assumption 1 and the selection rule of RoBOS (i.e., (we, ucb"..) ) 2 7), obtain
r S <- (we,uch) + (3, (e )) < 28 (w; o
7

---

Consider of + w/. Continuing from 10)
r S | wellar Mr T {wi ucb
|l wellas 23 (w/ ox
|wo we wellarki, + 23, (wg ve(stt))) ))
(I1)
|w - wellarkr, (ft) + (wf oeldies .))
(12)
- wellas (1e, fa,) - ( ucble.) .
28 (z(.
(13)
1/ a1 wellar
w wellaslles f&. MMM + 23, ()
(14)
S B' (w] ox (24,,))
(15)
where (1I) comes from the definition of ( 12) follows from 2, arg mingex (
[3]
results from the assumption on F in Assumption [ (14 utilizes Lemma [an and the Cauchy-Schward
inequality; and finally (13) follows from the detnition of e,. The remainder of the proof follows
similar arguments as in the proof of Theorem
Theorem 4 shows that the lenient regret scales as Ó(TTVT + Er), where Er := - Gt. An important special case in which Ey is sublinear is data-driven optimization. For this case, P. P
is fixed for E [T), P1 is the uniform distribution over the contexts, and Pt > Se,, >> 1 is the empirical distribution of the observed contexts, where de is the Dirac measure defined for c E C such that (A) = 1 if e A and 0 otherwise. The next result follows from steps similar to the proof of
10 Corollary 4].
Lemma 5. Consider data-driven optimization model with 8 E (0. Under Assumption 7 when RoBOS is run with confidence parameter 8/3 with 3r == (,/6/),, where Be is defined in Lemmal then with a probability of at least 5
12 )
TTT2
R2 - 4
2yr + 2 log '
+ B'a B'2VT 2 /
2lo
25
5 Experiments
We evaluate the proposed algorithm on one synthetic and one real-world environment. We compare the lenient regret and robust satisficing regret of RoBOS with the following benchmark algorithms. Our implementation is available at httttt://ggthuie com/ Bilkiiiittt. www.eenttCYYBRR///CC
SO: As the representative of SO we use stochastic version of the GP-UCB algorithm that samples at each round point di = arg max Re-,, [ucb, (zr,c). c)].
DRBO: For the DRO approach we consider the DRBO algorithm from [0]. DRBO, at each round samples 2, = arg max peu, Ee- (ucb,(2: (z).)).
WRBO: For the WRO approach we consider a maxi-min algorithm call WRBO, that maximizes the worst-case reward over the context set. Note that when the ambiguity set 44 of DRBO is Po. i.e., the set of all possible distributions on C, DRBO reduces to WRBO which samples each round the point 2, = arg max min.ec ucb, (z,
Synthetic environment. The objective function is given Figure Lefft. The reference distribution and the true distribution are chosen to be stationary with P. - (2,, 1) and P (0, 25). We denote the true MMD distance A A(P,, P.r)) with e, and run different instances of DRBO with ambiguity balls radius r = 3e, r = e, and r = e/3. When the radius of the ambiguity ball is e. DRBO knows the exact distributional shift. The threshold is set to 60% of the maximum value of the objective function, i.c., 7 = 0.6 max fzz c) se 0.65 We use an RBF kernel with Automatic Relevance Determination (ARD) and lengthscales 0.2 and 5 respectively for dimensions X and C. Simulations are run with observation noise ~ (O, 0.022).
Results for the robust satisficing and lenient regrets are given in Figure 2 Under this configuration, the RS solution, as noted in Figure I is the only solution that achieves the desired threshold r. Hence, algorithms that converge to a different solution accumulate linear lenient regret, can be seen in Figure 2 Right). When DRBO is run with an overconfident ambiguity set (radius e/3). it converges to suboptimal solution (hexagon); when the ambiguity set is underconfident (radius 3e), it converges
8

---

D1850: 3e
50-
15-
DR80.
0R80
40
RC
10
Ru6Os
30
20
0-
150
100
200
Round
Round
Figure 2: Results for synthetic environment. Plots show robust satisficing regret (left) and lenient regret (right) averaged over 50 independent runs with error bars corresponding to standard deviations divided by 2.
Xe
RoBOS
0.05
DRBO
Avg. Reward
0.50
0.45
0.1
0.3
0.4
0.6
0.7
0.9
1.0
Figure 3: Average reward for different and values in RoBOS and DRBO. is selected linearly between minimum and maximum function values. The radius r of the ambiguity ball for DRBO is selected from 0.1c to 10c. Plots show average of 10 independent runs each with 200 rounds.
another suboptimal solution (cross). Only when the distribution shift is precisely known and the ambiguity set is adjusted accordingly (radius c), DRBO converges to the RS solution. Refer to Figure to see the exact solutions converged.
We also investigate the sensitivity of the choice of r in RoBOS compared to the choice of r in DRBO. Figure compares the average rewards of RoBOS and DRBO for wide range of r and values. While RoBOS is designed to satisfice the reward rather than to maximize, its performance remains competitive with DRBO across diverse hyperparameter settings. Notably, for [0.1, 0.3). RoBOS opts for the solution indicated by cross in Figure [ signifying a trade-off: with smaller т. RoBOS prioritizes robustness guarantees over maximizing the reward.
Insulin dosage for TIDM. We test our algorithm on the problem of personalized insulin dose allocation for Type Diabetes Mellitus (TIDM) patients. We the open-source implementation of the U.S. FDA-approved University of Virginia (UVAYPADOVA TIDM simulator [37 []. The simulator takes in input the fasting blood glucose level of the patient, the amount of carbohydrate intake during the monitored meal and the insulin dosage given to the patient, it gives an output of the blood glucose level measured 150 minutes after the meal. We assume the insulin administered to the patient right after the meal. Similar to [5), we set the target blood glucose level as K = 112.5 mg/dl and define the pseudo-reward function as r(t) ll((t) K' where o(t) is the achieved blood glucose level at round t. We further define safe blood glucose level range as 102.5 122.5 mg/dl. For our setup, this corresponds to setting the threshold
-10. At each round t, the environment picks the true and reference distributions as P. N(G. 2. 2.25) and P.- ~ Nis. + N, N) where & 2/(20, 80) and N the random term setting the distributional shift. We define the action set X' to be the insulin dose and the context set C to be the amount of carbohydrate intake. Here distributional shift can interpreted as the estimation error the patient on their carbohydrate intake. We ran our experiments with N ~ ( 6) and with N, ~ U((6/ lo///+ 2). 6/ log((+2)) Simulations are run with observation noise 7) (0, 1). For the GP surrogate, we used a Matérn-1 kernel with length-scale parameter 10. As seen in Figures 4a and 4b when the amount of distribution

---

DISS:: 3r
1000
DRSO:
500
200
RuBos
600
400-
1000
200-
01
150
200
1050
200
Round
Round
(a)
DIRSO: Je
400
WRBO
600
900
SC
RUBOS
25 400-
200
100
200
01
0-
100
150
Round
Round
(b)
Figure 4: Results for insulin dose allocation simulation where e, is the true MMD distance between the true and reference distributions at round t, and the threshold = 10 specifies satisficing threshold of 10 mg/dl away from the target blood glucose level. On (b), the true MMD distance as en/ log(() decays with f. Plots show robust satisficing regret (Left) and lenient regret (Right) averaged over 50 independent runs with error bars corresponding to standard deviations divided by 2.
shift at each round known exactly by DRBO, can perform better than RoBOS. However, when the distributional shift is either underestimated or overestimated, RoBOS achieves better results. Plots of the average cumulative rewards of the algorithms can be found in the appendix.
Conclusion, limitations, and future research
We introduced robust Bayesian satisficing new sequential decision-making paradigm that offers a satisfactory level of protection against incalculable distribution shifts. We introduced the first RBS algorithm RoBOS, and proved information gain based lenient and robust satisficing regret bounds.
In our experiments, we observed that when the range of the distribution shift can be correctly estimated with tight uncertainty set U4 centered the reference distribution, DRBO [10] can perform better than RoBOS, especially when it comes to maximizing total reward. This not unexpected since one guarantee better performance with more information about the distribution shift. Nevertheless, in cases when the estimated shift does not adequately represent the true shift or when the main objective is to achieve desired value instead of maximizing the reward, RoBOS emerges robust alternative.
Our fundamental research RBS brings forth many interesting future research directions. One potential direction is to extend RoBOS to work in continuous action and context spaces. This will require more nuanced regret analysis and computationally efficient procedures to calculate the estimated fragility at each round. Another interesting future work is to design alternative acquisition strategies for RBS. For instance, the UCB approach we pursued in this work.
investigate Thompson sampling based approach instead of
Acknowledgements: Y. Cahit Yıldırm was supported by Turk Telekom part of 5G and Beyond Joint Graduate Support Programme coordinated by Information and Communication Technologies Authority.
10

---

References
[1] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger. Information- theoretic regret bounds for Gaussian process optimization in the bandit setting. IEEE Transac- tions on Information Theory, 5865):325033265 2012.
[2] Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
[3] Jasper Snoek, Hugo Larochelle, and Ryan Adams. Practical Bayesian optimization of machine learning algorithms. Advances in Neural Information Processing Systems, 25, 2012.
[4] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Advances in Neural Information Processing Systems, volume 24, 2011.
[5] liker Demirel, Ahmet Alparslan Celik, and Cem Tekin. ESCADA: Efficient safety and context aware dose allocation for precision medicine. In Advances in Neural Information Processing Systems, volume 35, pages 27441-27454, 2022.
[6] Andreas Krause and Cheng Ong. Contextual Gaussian process bandit optimization. Advances in Neural Information Processing Systems, 24, 2011.
[7] Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs. In 22nd International Conference on Artificial Intelligence and Statistics, pages 1177-1184, 2019.
[8] Johannes Kirsehner and Andreas Krause. Stochastic bandits with context distributions. In Advances in Neural Information Processing Systems, volume 32, 2019.
[9] Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. Advances in Neural Information Processing Systems, 31, 2018.
[10] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. 108:2174-2184, 2020.
[11] Herbert A Simon. behavioral model of rational choice. The Quarterly Journal of Economics, 69(1):99-118, 1955.
[12] James CT Mao. Survey of capital budgeting: Theory and practice. Journal of Finance, pages 349-360, 1970.
[13] Robert Bordley and Marco LiCalzi. Decision analysis using targets instead of utility functions. Decisions in Economics and Finance, 23(1):53-777 -3,74,,44444 2000.
[14] Terry M Moe. The new economics of organization. American Journal of Political Science, pages 739-777, 1984.
[15] Sidney G Winter. The satisficing principle in capability learning. Strategic Management Journal, 21(10-11)9911999, 2000.
[16] Barry Schwartz, Andrew Ward, John Monterosso, Sonja Lyubomirsky, Katherine White, and Darrin R Lehman. Maximizing versus satisficing: happiness is matter of choice. Journal of Personality and Social Psychology, 83(5):1178, 2002.
[17] Hirotaka Nakayama and Yoshikazu Sawaragi. Satisficing trade-off method for multiobjective programming. In Interactive Decision Analysis, pages 113-122. 1984.
[18] Michael A Goodrich, Wynn C Stirling, and Richard L Frost. A theory of satisficing decisions and control. JEEE Transactions on Systems, Man, and Cybernetics- Piternetics-PrtA.. A: Systems and Humans, (8(6):763-77, 1998.
[19] Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Satisficing in multi-armed bandit problems. IEEE Transactions on Automatic Control, 62(8))3788-3800 2016.
[20] Alihan Hüyük and Cem Tekin. Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning, (203)))133-16666 2021.

---

[21] Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Mathematics of Operations Research, 47(4):2815-28333 2022.
[22] Nadav Merlis and Shie Mannor. Lenient regret for multi-armed bandits. AAAI Conference on Arlificial Intelligence, volume 35, pages 8950-8957, 2021.
[23] Xu Cai, Selwyn Gomes, and Jonathan Scarlett. Lenient regret and good-action identification in Gaussian process bandits. In International Conference on Machine Learning, pages 1183-1192, 2021.
[24] Barry Schwartz, Yakov Ben-Haim, and Cliff Dacso. What makes a good decision? robust satisficing as a normative standard of rational decision making. Journal for the Theory of Social Behaviour, 4 41(2):009-277 2011.
[25] Daniel Zhuoyu Long, Melvyn Sim, and Minglong Zhou. Robust satisficing. Research, 71(1):61-88) 2023.
Operations
[26] Anton Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization. 12(2):479-50) 2002.
[27] Herbert E Scarf. A min-max solution of inventory problem. Rand Corporation Santa Monica, 1957.
[28] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv: 1908. 05659, 2019.
[29] Dimitris Bertsimas, Omid Nohadani, and Kwong Meng Teo. Robust optimization for uncon- strained simulation-based problems. Operations Research, 58(1):611-178, 2010.
[30] Herbert A Simon. Rational choice and the structure of the environment. Psychological Review, 63(2):129, 1956.
[31] John Walsh, Ruth Roberts, and Timothy Bailey. Guidelines for optimal bolus calculator settings in adults. Journal of Diabetes Science and Technology. 5(1):129-135, 2011.
[32] Tomoyuki Kawamura, Chihiro Takamura, Masakazu Hirose, Tomomi Hashimoto, Takashi Higashide, Yoneo Kashihara, Kayako Hashimura, and Haruo Shintaku. The factors affecting on estimation of carbohydrate content of meals in carbohydrate counting. Clinical Pediatric Endocrinology,, 24(4): 1534)):553115 165, 2015.
[33] Lindy Kahanovitz, Patrick M Sluss, and Steven J Russell. Type diabetes-a clinical perspective. Point of Care, 16(1):37, 2017.
[34] Christian Fiedler, Carsten W Scherer, and Sebastian Trimpe. Practical and rigorous uncer- tainty bounds for Gaussian process regression. In AAAI Conference on Artificial Intelligence, volume 35, pages 7439-7447, 2021.
[35] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844-853, 2017.
[36] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90, 2021.
[37] Boris P Kovatchev, Mare Breton, Chiara Dalla Man, and Claudio Cobelli. In silico preclinical trials: proof of concept in closed-loop control of type diabetes, 2009.
[38] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, Bernhard Schölkopf, et al. Kernl mean embedding of distributions: A review and beyond. Foundations and Trends@ in Machine Learning, 10(1-2):1-141, 2017.
12

---

A
Table of notations
Table 2: Table of notations
Notation
Description
aspiration level (threshold)
| M X' C we wt
/ww Mw MMD measure with kernel matrix M
Action set Context set True distribution at round & Reference distribution at round
fz ucb
(1), [xr cn)]
upper confidence bound of fo given by [ucb; (z,
Kr,(
max max (CC)
Tw-will
T-(w,fa)
if (wi, f2) 2T if (w,, fa) <T
+o0
(
max (())())
T- (wr
T Tw- l|ar
if (we, ucb")) 2T
+00
(we, ucb <T.
it
arg max (Wi, fa)
arg min Ne, (x) when (we: fae arg min 8 when (we fure
24
(T,,( when (we, fa.)
R7.
(1() when (we, fā.) 2
at
arg max (() 1w- (s) when (10,, 2
(w, arg maxw w, 1|xe
1l when (w,, ucb")) 27
B Additional experimental results
Cumulative Reward
-500
Cumulative Reward
-500
-1000
1000
-1500
DRBO:
DRBO: 3+
-1500
DRBO:
-000
WRBO
-2000
WRBO
SO
-2500
RoB0S
-2000
50
200
150
200
Round
Round
Figure 5: Cumulative rewards of the insulin dosage for TIDM experiments given in the main paper. Left and right plots are continuations of Figures and and 4bb respectively. Plots show average of 50 independent runs with enror bars corresponding to standard deviation divided by 2. The pseudo- reward function is defined as r(t) - (o(() K'.
C Proofs
C.1 Proof of Lemma 2
Assume that the confidence intervals in T Toold. When (i,e(x)) ao, we also have Ky, (x) When (x)) oo and (x)( oc, the inequality holds.
13

---

Recall that when (we, ucb{)) 2 T, wh arg max -- (-(w,ob
- wer-w represents the context
distribution that achieves (2). When (wi, fa) 2 T, let प. == arg max T- (mm.fa)) the context distribution that achieves (x)) When (,) < oo and KT,,, (x) < oo, we have
Bu-wwllx be
7 (w ucb"))
{w fu)
(x,1(2) - (zT,(())
1 we M
100 - we ||
T (20 ucb"))
T (w fu)
1 we 11 M
10 We 11 A
( fo ucb"))
1 wi ||
S 0.
C.2 An Auxiliary Concentration Lemma
Lemma 6. (ATO) Lemma 71) Let St 2 0 be non-negative stochastic process with filtration Fi, and define my Ft Further assume that S S B for z 1. Then for any 2 with probability at least 8 it holds that
Σ
m
<
2
Σ
S. + 4B log 8B (4B) +
t=1
T
6B
< 2
St + 8B log
8
C.3
Proof of Theorem
3
The robust satisficing regret is upper bounded by the sum instantancous regrets r/ == T Ki, |oo wellM (wi; Snx) as follows:
R
(T KT, ((P, P.) Eaury (22,, e)])
Σ (T Nr. - w. walar (10 S2,) )
Σ 1l1 2)
(16)
Assume that the confidence intervals in Lemma hold (an event that happens with probability at least 8/2). For the instantaneous regret we have
r = r - Ky,el Vr,ellug [ - we MlM {wt, uub''. + (wf, ucb -aas)
< t k we ll (wi, ucb',, 2,, (wi, oe(x,, -))
(17)
< T Kr,ellus we W.llM - (T Rr.llw, - willx) + 23, , (x(,))))
(18)
|!!/ well (fll. ke,s) 2,3 (w,, (x,,
< 23; oz (2).
(19)
In the derivation above, 177 follows from the confidence bounds given in Lemma T (18 follows
from (wi, ucb(,) > Ri. (xx) willM and K,, (x:); 19 is due Lemma
From this point on, we bound the robust satisficing regret by following standard steps bounding regret of GP bandits (see e.g., (10). First, by plugging the upper bound on r!" obtained in 19 to
14

---

16 and using monotonicity of 3e, we obtain
R 23T
fwt or (((:)))
(20)
T (ut, oe ))2
< 2/r
(21)
1=1
T (ut Nut,or(aa or(e,,
< 2
(22)
where (TT) uses the Cauchy-Schward inequality and uses the Jensen inequality.
To complete the proof we use Lemma relate the expectation of the posterior variance in (22 to
the posterior variance of the observations. Namely, have with probability at least 6/2
T Σ (wz (1 )9) < 2 Σ Col c,)² + 8 8
12 5
(23)
Next, to relate the sum of variances that appears in 23 to the maximum information gain. We use log(1 + x) for all æ E [0, obtain
T
T
Σ ( a)2
<
2 log(1 + or(2,, ())
4
(24)
where 24 follows from
33
Lemma 3].
Finally, to bound the robust satisficing regret, we plug the upper bound in 24 to the r.h.s. of (3
and use it to upper bound 22 as follows
2 22T 2og
12 5
Rř s 4
Let A and be the events that Lemma D and Lemma 6 hold. Setting the confidence of each event to 1 - 8/2, we can bound from below the probability that both events hold
P(An B) = P(Āu B) 2 1 - P(A) P(B) = -
completing the proof of Theorem 3
C.4 Proof of Theorem
Define the instantaneous regret as r := 7= (wt, Sz,). We have
R2 Σ (T Eew (S (x1,,
Entor 0).
(25)
Assume that the confidence intervals Lemma I Thold (an event that happens with probability least 1 - 8/2). Then, for the instantaneous regret we have
r = (wt, ucb",) ) + (w,, ucb', fax)
< r (w) ucb",) + 2,3 oe(
(26)
When, w. Wt. by Assumption 1 and the selection rule of RoBOS (i.e., (wi, ucb',.) 7), obtain
r < ST- ucb + (3, (z )) < 28, (w, ox(2,,
15

---

When w # wi, continuing from 266 we obtain
T {wi ucb
r S 1!wi
well Ar
(w] (x1,)) :))
| wellas
(wiz, ucb
x || |00 well
+ (1 o
(27)
|| |00t we 1las
(wi) uebg.)
1/ - wellar
+ 23 (wf oe
(28)
100 wt 1|
(we, f2.) (1T), ucb
1 wellas
+ 23r or( -))
(29)
|00 wellmr
(we - fa.)
Jao wellas
+ 2/3( (e
(30)
1002 - wellas
|| |00g we 1lll [[ā, M-
1 wellas
+ 28, Oe .))
(31)
1 wellas
I -
-1a-- + 23, (wg (x(s)))))
- 2 (wi, ( )) + BBB..
(32)
Since the final bound is non-negative, it can be used bound all terms r/l(r) 2 0) in Fyy In the derivation above, (26) follows from Lemma ! (27) uses the fact that w is the distribution that
achieves R (xx); (28 uses the fact that xy minimizes (r,( (29) uses Assumption I (30) again
uses Lemma (31] follows from the Cauchy-Schward inequality; and (32) follows from the facts
| - wx|las M and B' = m|ax=II/an MM- From this point on, the regret bound follows the same
arguments as in the proof of Theorem 3
In particular, using (32) we write
R/T 2,r Σ (wi ( )) + B' E' 4
(33)
We complete the proof by continuing from (2)). by using the same steps as in the proof of Theorem 3 starting from (20), which leads the regret bound in the statement of Theorem 4
C.5 Proof of Lemma
The first term of I Lemma 5 directly follows from Theorem For the second term, we use the result
of 38 Theorem 3.4), which is restated below.
38
Theorem 3.4] Assume k(c,, c4) S for all Cr Cy E C. Then, with probability at least 5
d(p", P.: < Vt
(2 + (20og(1/)))
To use the lemma above, let 6, -....
26
Then,
p (app)))
P.) >
T²t²
28
2 +
2 log
<
Vt
25
212
π
Using union bound, we obtain
1
212
T
26
28 n2
8
P 31 [TE [T] :( P.) Vt 1
2 22lg
25
2222
72
3
The inequality above implies that
2222
8
PP V d(p", P.)
2
2log
< 1
V
28
3
16

---

Since & $ VFI
2 2 v log
have with probability least 1
12
147 s 1
T
2yr + 2og
B'
8
t=1
12
T
1
x²t2
T
22 + 2og
(8)
B'c
B
2+
2 llo
Vt 1
1=2
12
T
1
T222
s 548r T
22 + 2
+ B'G + B')
2+
2 log
8
Vt 1
28
1=2
12
T-1
1
x
-,8 /
T
2nT log
(8)
B'a B'
Σ
+
V
log
Vt
28
1=1
12
π 2T2
27r + 2og
+
B'e + B'2VT
2
/2 22
8
28
Also, note that
1
1|00 - w1 11 = 1|w0
MM <
IM = 0(1)
[w:||
=1
17


Reviews:
[{"review_id": "D6LNOnf5ar", "reviewer": "Reviewer_gjzH", "summary": "I think the main contributions of this paper are as follows:\n\n- Proposes a new decision-making framework called robust Bayesian satisficing (RBS) which combines robust satisficing with Bayesian optimization. RBS aims to achieve a satisfactory solution under distributional shifts by observing a predefined satisfactory threshold. This is different from distributionally robust optimization which requires an ambiguity set and stochastic optimization which optimizes for a given reference distribution.\n\n- Defines two regret measures to evaluate the performance of RBS algorithms: lenient regret and robust satisficing regret. Lenient regret measures the cumulative loss of an algorithm's chosen actions with respect to an aspiration level. Robust satisficing regret measures the loss with respect to the robust satisficing benchmark which is the aspiration level minus the fragility (a measure of suboptimality per unit distribution shift). The paper shows the connection between these two regret measures.\n\n- Proposes an RBS algorithm called Robust Bayesian Optimistic Satisficing (RoBOS) which uses Gaussian processes to model the objective function. RoBOS only requires an aspiration level as input and does not need an ambiguity set. RoBOS chooses actions to minimize the estimated fragility which is an optimistic estimate of the true fragility.\n\n- Proves that RoBOS achieves sublinear robust satisficing regret and lenient regret under certain assumptions. The regret bounds depend on the maximum information gain and the sum of distribution shifts.\n\n- Demonstrates the effectiveness of RoBOS on synthetic problems and compares it with other robust Bayesian optimization algorithms.", "questions": "In addition to the previous section:\nI am curious how this approach can be utilized for test-time distribution shifts and adaptations. ", "limitations": "They covered this part very well in my view.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Robust Bayesian satisficing is a novel framework that combines robustness to distributional shifts with satisficing behavior. This provides an alternative to existing paradigms like distributionally robust optimization and stochastic optimization. RBS does not require precise knowledge of the ambiguity set and can handle unknown distribution shifts. Also, the paper provides theoretical guarantees on the regret of RoBOS under some assumptions. The robust satisficing regret and lenient regret of RoBOS grow sublinearly with time. The regret bounds show the dependence on maximum information gain and the sum of distribution shifts, providing insight into how RoBOS handles distributional shifts. In addition, the experimental results verify the theoretical findings on the sublinearity of the regret bounds. Finally, the paper is well-written, clear, and easy to follow.", "weaknesses": "- Some assumptions seem to be strong for this problem. For example, the bounds require the sum of distribution shifts to be sublinear in time which may not always hold in practice. It would be good to discuss how the algorithm behaves when these assumptions are violated.\n\n- The experiments are limited to synthetic problems. It would be good to evaluate RoBOS on some real-world benchmark problems to demonstrate its effectiveness in practical settings. Comparisons with more algorithms on these problems would also strengthen the experimental evaluation. There are many datasets for distributional shifts that the author can leverage to verify their algorithm.\n\n- Although as defined in the conclusion as a future direction, it would be beneficial to discuss the effects of continuous context in this problem, since the focus is on deterministic contexts in this paper. Analyzing RoBOS when contexts are stochastically generated would provide greater insight into how it handles uncertainty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and valuable insights.\n\n### Weaknesses\n- **(Some assumptions...)**\nIndeed to achieve sublinear lenient regret, some assumptions have to be made on the distribution shift. Nothing much can be said in an adversarial environment where the reference distribution $P\\_t$ is judiciously chosen away from the true distribution $P^*\\_t$ in each round. However, one interesting practical setting is the case where the reference distribution is the empirical distribution. This corresponds to data-driven optimization setting discussed in [10]. For this case, $P^*\\_t = P^*$ is fixed for $t \\in [T]$, $P\\_1$ is the uniform distribution over the contexts, and $P\\_t = \\sum\\_{s=1}^{t-1} \\delta\\_{c\\_s}$, $t>1$ is the empirical distribution of the observed contexts, where $\\delta\\_x$ is the Dirac measure defined for $c \\in {\\cal C}$ such that $\\delta\\_c(A) = 1$ if $c \\in A$ and $0$ otherwise. Under this setting, one can put a probabilistic bound on the amount of distributional shift $\\epsilon\\_t$, which can be used to bound the regret similarly to the proof of  [10, Corollary 4]. We are able to show that the lenient regret of RoBOS when run with $\\beta (\\delta/3)$ is bounded with probability at least $1-\\delta$ by\n\\begin{equation*}\n    R^{\\textit{l}}\\_T \\leq 4 \\beta\\_T \\sqrt{T\\left( 2 \\gamma\\_T + 2\\log \\left(\\frac{12}{\\delta}\\right)\\right)} + B' \\epsilon\\_1 + B'  2 \\sqrt{T} \\left(2 + \\sqrt{2 \\log \\left( \\frac{\\pi^2 T^2}{2\\delta} \\right)} \\right) ~.\n\\end{equation*}\n\n- **(The experiments are limited...)** We note that we included a real-world experiment in our supplemental document, now moved to the main paper, concerning insulin dosage allocation for Type 1 diabetes patients. For more detail about the experiment, we kindly refer the reviewer to our response to reviewer KF6g's first question. \n\n- **(...discuss the effects of continuous context...)**\nIn the original paper, we assume that at each round $t\\in[T]$, contexts are drawn stochastically from the true distribution $P^*\\_t$ over a finite context set. We studied the continuous context case in the response phase, and observed that our regret bounds hold with only minor differences in the regret analysis. The proof for the continuous case closely follows the discrete case, however, instead of expressing the expectations as an inner product (e.g., $\\langle w\\_t, f\\_x \\rangle$), we work with the general representation (e.g., $\\mathbb{E}\\_{c\\sim P\\_t}[f\\_x]$). Due to linearity of expectations, our derivations continue to hold. Also in the analysis of the lenient regret, in equation (37), instead of using the Cauchy-Schwarz inequality, we use the definition of the MMD distance to bound the term $\\mathbb{E}\\_{c \\sim P\\_t}[f(\\hat{x}\\_t, c)]  -  \\mathbb{E}\\_{c \\sim \\bar{P}^t\\_{\\hat{x}\\_t}} [f(\\hat{x}\\_t,c)] \\leq B \\Delta(P\\_t, \\bar{P}^t\\_{\\hat{x}\\_t})$, where $B$ is an upper bound on the RKHS norm of $f$ and $\\Delta(\\cdot,\\cdot)$ is the MMD distance.\n\n\n### Questions\n**(...test-time distribution shifts...)**\nIndeed a promising area of application is the test-time distributional shifts. RoBOS presents itself as a possible solution to this problem especially when the test-time distributional shift is difficult to foresee. Many engineering products are designed to be deployed in unpredictable environments with multiple contingent factors. The safety guarantees of RoBOS with respect to all possible distributional shifts may give it an edge in such environments. For instance, when $P\\_t$ is the training distribution, one can train a model to achieve the maximum accuracy, i.e., $\\hat{x}\\_t = \\arg\\max\\_{x \\in {\\cal X}} \\mathbb{E}\\_{c \\sim P\\_t}[f(x,c)]$. However, this will be of no use when the test distribution $P^*\\_t$ is significantly different from $P\\_t$. Instead, with robust satisficing, one seeks to achieve an accuracy that we are content with, e.g., $\\tau=0.9$ (represents $90\\\\%$ accuracy). Then, the robust satisficing solution guarantees at test time, an accuracy that is at least $\\tau - \\kappa\\_{\\tau,t} \\Delta(P^*\\_t, P\\_t)$."}, {"review_id": "hwOiqxZbWz", "reviewer": "Reviewer_bA8n", "summary": "This paper studies robust satisficing in contextual Bayesian optimization under distribution shift in the distributions of the context. \nThey show that under some assumptions their algorithm achieves sublinear lenient regret and under some relaxed assumptions they achieve sublinear robust satisficing regret. \n\nThey compare their method agains distributionally robust optimization approach [10] for contextual Bayesian optimization.", "questions": "1) Why did you choose to use MMD distance to measure the discrepancy between distributions. \n2) In Table 1, there must be a space between $\\min$ and $k$ for RS objective.\n3) I do not fully understand why one would prefer RS over DRO. Can you please clarify this point? When it would make sense to use RO, RS and DRO?\n4) Line 141: Please provide references that GP assumption is common. \n5) Lemma 1: Where does the det operator appear appear in Lemma 1? Why is it introduced there? What is $\\gamma_{t-1}$? What is $e$?\n6) If LCB is never used, why it is introduced?\n7) How restrictive the regularity assumption on $f$?\n8) Optimism in the face of uncertainty is a well-known concept but I am not sure how it is motivated in Section 3 and how your model is optimistic. Can you please elaborate on this? \n9) For the fair comparison of methods: To make a fair comparison between DRBO and your method you should consider robust regret introduced in [10].\n10) Is $\\tau$ fixed throughout the algorithm? Referring to footnote at Page 7, I understand that you claim $\\tau$ can be selected adaptively but I think it must be selected adaptively otherwise $\\hat \\kappa_{\\tau, t}(x)$ can be infinity, right? \n11) Can you please intuitively explain what does the model in (1) satisfy and what is it robust against? Why $\\tau$ can be explained as $Z_t? \n12) I find it unnatural that the regret bound in Theorem 3, is not dependent on $\\tau$. I understand it is because $\\tau$ appears also in the RS regret definition. I think a more natural approach would be separating these two $\\tau$'s and seeing that the regret only depends on the difference of these two $\\tau$'s. (similar argument goes for the lenient regret) Can you also show the regret guarantee on the robust regret as defined in [10]?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I have my reservations against points that I mentioned below, but I believe this research direction is valuable and interesting.", "weaknesses": "The writing of the paper can be improved. The clarity and coherence of the writing could be enhanced. There are instances where the ideas are not effectively communicated, leading to confusion for the reader. Furthermore, the structure of the paper could benefit from more logical organization and smoother transitions between sections. Additionally, some grammatical and punctuation errors need to be addressed, as they can detract from the overall quality of the paper. A revision focusing on refining the writing style and ensuring a more polished presentation would greatly strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and valuable insights.\n\n### Weaknesses\n**(...refining the writing style and ensuring a more polished presentation...)**\nWe have undertaken a thorough revision to address the concerns raised. Specifically, we've refined the writing for better clarity, restructured the content for a more logical flow, and ensured smoother transitions between sections.\n\n### Questions\n1) MMD distance, defined using a kernel function, is a prevalent measure for distributional shifts in RKHS [A, B, 10]. Its overlap with kernel-based methods is notable, and with kernels like RBF and Matérn-$\\nu$, MMD acts as a metric. Its ease of computation and clear interpretation aids theoretical analysis.\n2) Fixed.\n3) We kindly refer the reviewer to our global response.\n4) Some of the work that utilizes GP's in the RKHS setting are [1, 10, 31] which are also referred to in the main paper. Now we also cite them in the GP assumptions section.\n5) There was a writing error, now fixed and confidence bounds updated to a more recent version. In the final version $\\gamma\\_t$ (the maximum information gain) is defined in its proper place.\n6) Fixed.\n7) The assumption that $f$ belongs to an RKHS with bounded Hilbert norm is a very common one in the literature [1, 31]. The RKHS assumption induces smoothness conditions \n\\begin{equation*}\n    |f(x) - f(y)| = |\\langle f, k(x,\\cdot) - k(y,\\cdot) \\rangle| \\leq \\lVert f\\rVert\\_{\\mathcal{H}} \\lVert k(x,\\cdot) - k(y,\\cdot)\\rVert\n\\end{equation*}\nby Cauchy-Schwarz inequality.\n8) RoBOS's optimism arises from its use of the UCB of the objective function, similar to algorithms like GP-UCB, ensuring a balance between exploration and exploitation. Lemma 2 emphasizes this: with a probability of at least $1-\\delta$, we have $\\hat{\\kappa}\\_{\\tau,t}(x) \\leq \\kappa\\_{\\tau,t}(x)$ for all $x\\in\\cal X$ and $t \\geq 1$. This indicates that the algorithm's estimated fragility is always less than or equal to the actual fragility, confirming RoBOS's optimistic nature.\n9) In the response period, we conducted experiments comparing DRBO and RoBOS on the robust regret from [10], figures given in the response pdf. Our findings show that RoBOS, even with linear robust regret, can outperform DRBO in cumulative reward. This occurs when the ambiguity set isn't a tight representation of the distributional shift, leading the DRO solution DRBO converges to, to be suboptimal under the true distribution.\n10) $\\tau$ can indeed be fixed or time-varying, note that our algorithm works even when the $\\hat{\\kappa}\\_{\\tau,t}(x)$ is infinite for some $x\\in \\mathcal{X}$. We only require that the robust satisficing problem is feasible, meaning the following optimization objective has a solution. Find $x^*\\_t \\in \\mathcal{X}$ that solves in each round $t$\n\\begin{equation}\n    \\kappa\\_{\\tau,t} = \\min k ~ \\text{s.t.} ~ \\mathbb{E}\\_{c\\sim P}[f(x,c)] \\geq \\tau - k \\Delta(P,P\\_t), ~\\forall P \\in {\\cal P}\\_0 ~, x \\in {\\cal X}, ~k \\geq 0 ~. \\tag{1}\n\\end{equation}\nwhich is feasible under $\\tau \\leq \\mathbb{E}\\_{c\\sim P\\_t}[f\\_{\\hat{x}\\_t}]$, for all $t\\in [T]$, where $\\hat{x}\\_t := \\arg\\max\\_{x \\in {\\cal X}} \\langle w\\_t, f\\_x \\rangle$. If this assumption does not hold in round $t$, then the robust satisficing problem is infeasible, which means that $\\kappa\\_{\\tau,t} = \\infty$ and there is no robust satisficing solution. Therefore, measuring the regret in such a round will be meaningless. In practice, if the learner is flexible about its aspiration level, this assumption can be relaxed by dynamically selecting $\\tau$ at each round to be less than $\\langle w\\_t, \\text{lcb}^t\\_{\\hat{x}'\\_t} \\rangle$, where $\\hat{x}'\\_t := \\arg\\max\\_{x \\in {\\cal X}} \\langle w\\_t, \\text{lcb}^t\\_x \\rangle$. The optimism principle ensures that if the primary problem (1) is feasible, the problem with estimated fragility $\\hat{\\kappa}{\\tau,t}$ remains so. Given feasibility, an expert can set the satisficing goal $\\tau$, see our example on diabetes.\n11) The model in (1) tries to find a solution that achieves the desired threshold $\\tau$, i.e.\\ satisfice. The model picks the solution that has the lowest fragility $\\kappa\\_{\\tau,t}(x)$. The fragility can be viewed as the minimum rate of suboptimality one can obtain with respect to the threshold, per unit of distribution shift from $P\\_t$. Since the fragility is calculated over all possible context distributions $\\forall P \\in {\\cal P}\\_0$, the model gives robustness guarantees under all possible distributional shifts. In particular, the true robust satisficing action $x^*\\_t$ achieves \n\\begin{align*}\n    \\mathbb{E}\\_{c\\sim P^*\\_t}[f(x^*\\_t,c)] \\geq \\tau - \\kappa\\_{\\tau,t} \\Delta(P^*\\_t,P\\_t) ~\n\\end{align*}\nunder the true distribution $P^*\\_t$, no matter what the distributional shift is. $\\tau$ can be explained as a percentage of $Z\\_t$ when $f$ is known (not in the learning problem, where $f$ is unknown). Only knowing $Z\\_t$ (but not $f$ or optimal $x$), the decision-maker can set $\\tau$ as the percentage of $Z\\_t$ that it is content with. This is just one example of how $\\tau$ can be selected. See our response to your previous comment for another example.\n12) The $\\tau$ value found within our regret definitions is identical to the $\\tau$ utilized as an input to our algorithm. It represents the aspiration level that our algorithm strives to reach, and forms the benchmark against which we define our regret notions. Its absence in the regret bound is due to its direct link with the objective function $f$, assuming $\\tau \\leq \\mathbb{E}\\_{c\\sim P\\_t}[f\\_{\\hat{x}\\_t}]$.\n"}, {"review_id": "3BJEFeps2u", "reviewer": "Reviewer_Gzxd", "summary": "This paper studies a contextual Bayesian optimization problem when the true and reference distributions of the context can be different due to distribution shifts. The authors propose an algorithm called robust Bayesian satisficing algorithm (RoBOS) based on the idea of robust saisificing (RS). Through theoretical analysis and empirical results, the authors demonstrate their results on two notions of regret: lenient regret and robust satisficing regret. For the theoretical part, the authors have a thorough analysis and show that RoBOS achieves with high probability $\\tilde{\\mathcal{O}}(\\gamma_T \\sqrt{T})$ robust satisficing regret and  $\\tilde{\\mathcal{O}}(\\gamma_T \\sqrt{T} + \\sum_{t=1}^T \\epsilon_t)$ lenient regret, where $\\gamma_T$ is the maximum information gain and $\\epsilon_t$ is the amount of distribution shift in round $t$. For the empirical part, the authors propose two synthetic benchmarks and one real-world benchmark, and for all cases, they demonstrate RoBOS outperforms distributionally robust BO (DRBO).", "questions": "There are a few places where terms are not defined in the statement, or they are confusing:\n1. In lines 102 and 103, can you be more specific on the difference between $\\kappa_{\\tau,t}$ and $\\kappa_{\\tau,t}(x)$? In particular, in both optimization problems, what are the decision variables, and what is fixed?\n2. In Lemma 1 (line 155), the term $\\gamma_{t-1}$ is not defined, the term appears in line 185, which should be moved earlier.\n3. The definition of $B’$  should be moved from line 227 to the statement of Theorem 4.\n4. In Figure 3, the first line, should be benchmark “2”.\n\n\nQuestions for the empirical results:\n1. In Figure 1, why $\\tau = Z_0/2$?\n2. In line 256, the true distribution is picked randomly from the set $\\mathcal{U}_t$, can you be more specific on this? \n3. In Figure 3, the latter 2 plots seem incomplete. For lenient regret, why does the plot only plot for $t \\le 100$? For robust satisficing regret, only RoBOS is complete.\n4. In both synthetic benchmarks, could you justify the choice of $\\tau$? In particular, are the experimental results consistent for a wide range of $\\tau$?\n\nQuestions for the theoretical results:\n1. Page 10 of the appendix, line 288: is the reward function $r(t)=-|o(t-K)_+|$?\n2. How is Eq (29) in line 323 derived? Why can we set $B=1$ in Lemma 5? It might be good to be more specific here.\n\n", "limitations": "The authors stated their proposed method RoBOS may be worse than DRBO if the goal is to maximize the reward, which is the main limitation of their work. The other potential limitation I think is the robust satisficing model might be sensitive to the choice of $\\tau$.\n\nI suggest the author also analyze their results in other performance measures and see how sensitive their results are with respect to the choice of $\\tau$.\n\nThere is no potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Distribution shift is an important challenge in Bayesian Optimization, and it is great authors propose a new algorithm that attempts to address these issues, it also brings in some new interesting future research questions. The proposed question and results are new, to my best knowledge. I also like the algorithm, which naturally combines the empirical fragility and common algorithms in the contextual Bayesian optimization setting.  The paper is well-written in most parts except for a few minor parts.\n\n", "weaknesses": "My biggest concern is the two regrets defined in the paper: the lenient regret and the robust satisficing regret, which depends explicitly on the threshold $\\tau$. In particular, previous papers in robust satisficing [1] also did the analysis using common performance measures such as average performance. The authors also lack justification for their proposed new notion: robust satisficing regret, beyond matching the definition of robust satisficing which might favor RoBOS. In addition, think the theoretical analysis employed is standard in the literature.\n\nI think the following issues need to be addressed:\n1. Could you also demonstrate (theoretically or empirically) the performance of RoBOS if the goal is to maximize the reward?  \n2. How sensitive is the choice of $\\epsilon$ in DRBO/ WRBO versus the choice of $\\tau$ in RoBOS? \nIn the literature, e.g., Figure 1 of [1], they measured the performance of the robust satisficing model over a sequence of $\\tau$ and solve the distributional robust optimization model over a sequence of radius of $r$, then they compared the efficient frontier on both average performance and CVaR. This might be a way to further justify the effectiveness of RoBOS.\n\nReference:\n\n[1] Daniel Zhuoyu Long, Melvyn Sim, and Minglong Zhou. Robust satisficing. Operations Research, 71(1):61–82, 2023.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and valuable insights.\n\n### Weaknesses\n\n- **(...justification for robust satisficing regret)**\nRobust satisficing regret evaluates how our algorithm fares against the robust satisficing action. In particular, the true robust satisficing action $x^*\\_t$ achieves \n\\begin{equation*}\n    \\mathbb{E}\\_{c\\sim P^*\\_t}[f(x^*\\_t,c)] \\geq \\tau - \\kappa\\_{\\tau,t} \\Delta(P^*\\_t,P\\_t) ~.\n\\end{equation*}\nRobust satisficing regret, evaluated at each round, measures the expected reward of the action chosen by our algorithm against the guaranteed reward of $x^*\\_t$. When the selected action meets or exceeds this guaranteed reward, no regret is accumulated. However, if the chosen action falls short of this guarantee, then regret is accrued. Based on the above discussion, we think that robust satisficing regret is the right choice when evaluating the loss of the learner w.r.t. robust satisficing benchmark. That being said, we agree with the reviewer about the importance of investigating the cumulative reward performance of RoBOS. Even though our goal is to satisfice the aspiration goal, it is still meaningful to analyse the cumulative reward. For instance, Figure 1 of the main paper shows a scenario in which the robust satisficing solution attains the optimal reward at the true distribution $P^*\\_t$, while DRO with imprecise uncertainty sets cannot do so. Since RoBOS converges to the robust satisficing solution, in this example RoBOS is expected to attain higher cumulative reward than DRBO.\n\n- **(...performance of RoBOS in reward maximization...)**\nDuring the response phase, we compared RoBOS and DRBO in terms of their cumulative rewards. The results can be found in the response pdf. \n\n- **(...sensitivity to $\\tau$...)**\nDuring the response phase, we compared RoBOS and DRBO in terms of their sensitivity to the choice of $\\tau$ and $\\epsilon$. The results can be found in the response pdf.\n    \n    \n### Questions\n#### Definitions\n1) $\\kappa\\_{\\tau,t}$ and $\\kappa\\_{\\tau,t}(x)$ can be defined as following. In RS, the objective is to find $x^*\\_t \\in \\mathcal{X}$ that solves in each round $t$\n\\begin{equation*}\n\\kappa\\_{\\tau,t} = \\min k ~ \\text{s.t.} ~ \\mathbb{E}\\_{c\\sim P}[f(x,c)] \\geq \\tau - k \\Delta(P,P\\_t), ~ \\forall P \\in {\\cal P}\\_0 ~ , x \\in {\\cal X}, ~ k \\geq 0 ~ .\n\\end{equation*}\nTo find $x^*\\_t$, we can first compute the {\\em fragility} of $x \\in {\\cal X}$ as\n\\begin{equation*}\n\\kappa\\_{\\tau,t}(x) = \\min k ~ \\text{s.t.} ~ \\mathbb{E}\\_{c\\sim P}[f(x,c)] \\geq \\tau - k \\Delta(P,P\\_t), ~ \\forall P \\in {\\cal P}\\_0, ~ k \\geq 0 ~ .\n\\end{equation*}\nIn the first problem $\\tau$ and $P\\_t$ are fixed while the decision variable is $x\\in\\mathcal{X}$. In the second problem, $x$, $\\tau$ and $P\\_t$ are fixed and we compute the minimum $k$ that satisfies the constraints.\n2) Fixed.\n3) Fixed.\n4) Fixed.\n\n#### Empirical\n1) Figure 1 illustrates a proof of concept example where $\\tau$ is chosen to be achievable for only one action, highlighted by the green rhombus.\n2) In the second synthetic experiment we pick the true distribution $P^*\\_t \\sim \\mathcal{N}(\\mu\\_t +  N\\_t, 5^2)$ where $\\mu\\_t$ is the mean of the reference distribution $P\\_t$ and $N\\_t\\sim \\mathcal{U}(-6,6)$ is set as to  make sure the distributional shift is not greater than $\\epsilon$.\n3) We appreciate your careful review of our work. However, we'd like to clarify that all our plots do extend until $t=200$. It's possible that there may have been some technical issues with the visualization during the pdf loading process. We recommend viewing the file in a different pdf reader. We apologize for any inconvenience caused and we are here to assist if further clarifications are needed.\n4) In the first proof of concept synthetic experiment, $\\tau$ is chosen to be achievable only by one of the actions. In the second synthetic experiment, $\\tau$ was selected as half of the function maximum arbitrarily. Further, a discussion about how to select $\\tau$ in a real-world setting is given in our global response. We have made revisions in response to your comments and have conducted an additional experiment to analyse RoBOS' sensitivity to $\\tau$. We also compare this with DRBO's sensitivity to the choice of $\\epsilon$. These results are included within the response pdf.\n\n#### Theoretical\n1) The pseudo reward function we defined for the insulin dosage allocation experiment is $-|o(t) - K|$. Here $o(t)$ is the blood glucose level of the patient, measured 150 minutes after their meal, and  $K=112.5$ mg/dl is the target blood glucose level. Our pseudo reward function measures the discrepency in patients blood glucose compared to the target level.\n\n2) In the mentioned equation $\\langle w^*\\_t, \\sigma\\_t(x\\_t,\\cdot)^2\\rangle$ corresponds to $m\\_t$ in Lemma 5. Hence $S\\_t$ correspods to $\\sigma\\_t(x\\_t, c\\_t)^2$, $c\\_t\\sim P^*\\_t$. Due to our assumption on the kernel that $\\sigma(x\\_t,c\\_t) \\leq 1$, $B$ in Lemma 5 can be set to 1.\n"}, {"review_id": "VIqGkj4IXV", "reviewer": "Reviewer_KF6g", "summary": "The paper proposes robust Bayesian satisficing, a new setting of BO that is similar to distributionally robust BO. Robust Bayesian satisficing aims to achieve a 'good enough' expected value given by some threshold $\\tau$ and relaxed by the distribution distance between a reference and a true distribution. The paper proposes 2 new notions of regret, design an algorithm with regret bounds, and empirically compare this algorithm to DRBO and other suitable baselines.", "questions": "No additional questions other than those raised in Weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Robust satisficing as a new optimization objective for BO is interesting and presents an alternative 'good enough' objective along with a relaxation based on distribution distance that is sensible. It enables distributionally robust BO in another way that does not involve uncertainty sets. \n2. The new regret definitions make sense, and the proposed algorithm is supported by theoretical guarantees on its performance via regret bounds.\n3. The empirical evaluations present support the claim that the proposed algorithm performs well with the proposed regret definitions.\n4. Overall I believe that this work has relevance to the community, subject to the issues raised in the Weaknesses section being addressed properly.", "weaknesses": "Technical concerns:\n1. How is the threshold $\\tau$ to be selected in a real world problem? The paper states that it 'can be expressed as a percentage of the SO solution', but when $f$ is unknown, the expected value of the SO solution is unknown as well. From Algorithm 1, $\\tau$ is an input prior to any BO rounds. This is an important question to answer, since one of the claimed advantages over DRBO is that there is no need to pick uncertainty sets which may be unknown a priori. But now you have to pick $\\tau$ which is also unknown a priori, so it seems that you have replaced one hyperparameter for another. In order to satisfy Assumption 1, it is claimed that $\\tau$ can be dynamically selected, but that makes the regret and thus the regret bounds not well-defined, since the regret is a function of a constant $\\tau$.  If $\\tau$ is to be dynamically selected and learned, then the algorithm and regret bounds should be explicitly written to take this into consideration, instead of claiming in a footnote that it 'can be straightforwardly adapted to work with dynamic thresholds'.\n2. The experiments in the main paper are simple synthetic benchmarks which by themselves are not comprehensive enough an empirical evaluation. I see that you have an interesting real world benchmark on insulin dose allocation in the appendix, why is it hidden there without a reference from the main paper? Why aren't WRBO and SO tested on that benchmark?\n\nClarity issues:\n1. The equation below line 102 defining $\\kappa_{\\tau, t}$ and the preceding sentence does not quite make sense. It seems to me that you do not need that sentence and equation, simply define fragility as in Eq. (1), and then the following sentence makes clear what $x_t^*$ and $\\kappa_{\\tau, t}$ are.\n2. In all the figures, heatmaps are uninterpretable without a colorbar indicating the values that each color corresponds to.\n3. Lemma 1 uses the maximum information gain $\\gamma$ before it is defined, and includes a definition for determinant when determinant is not used there.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and valuable insights.\n\n\n### Weaknesses\n#### Technical Concerns\n- **(...how $\\tau$ can be selected in a real-world problem...)** One real-world experiment concerning safe dose allocation for diabetes patients is presented in the supplementary document. Type 1 Diabetes Mellitus (T1DM) patients require bolus insulin doses (id) after meals for postprandial blood glucose (pbg) regulation. One of the most important factors that affect pbg is meal carbohydrate (cho) intake [C]. Let ${\\cal X}$ and ${\\cal C}$ represent admissible id and cho values. For $x \\in {\\cal X}$, $c \\in {\\cal C}$, let $g(x,c)$ represent the corresponding (expected) bpg value. Function $g$ depends on the patient's characteristics and can be regarded as unknown. The main goal of pbg regulation is to keep pbg close to a target level $K$ in order to prevent two potentially life threatening events called hypoglycemia (e.g., pbg $<$ 70 mg/dl) and hyperglycemia (e.g., pbg $>$ 180 mg/dl). This requires $x\\_t$ to be chosen judiciously based on current $c\\_t$. Patients rely on a method called cho counting to calculate $c\\_t$. Often times, this method is prone errors [D]. The reported cho intake $\\zeta\\_t$ can differ significantly from $c\\_t$. In order to use DRO, one needs to identify a range of plausible distributions for cho calculation errors, which is hard calculate and interpret. On the other hand, specifying $\\tau$ corresponds to defining an interval of safe pbg values around $K$ (e.g., pbg $=$ 125 mg/dl) that one is content with, which is in line with the standard clinical practice [E]. We will move this experiment from the supplemental document to the main paper. In addition, in response to the comments of reviewer Gzxd and KF6g, we performed new experiments that compare accumulated rewards of RoBOS and other competing benchmarks. Moreover, we also carried out simulations that shows sensitivity of the results to the aspiration level $\\tau$ set by the learner. These results can be found in the response pdf.\n\n- **(...$\\tau$ expressed as a percentage of SO solution...)** The interpretation that $\\tau$ can be chosen as a percentage of the stochastic optimization problem $Z\\_t$ pertains to the case when $f$ is known. We discussed this under the optimization objective subsection before the regret definitions. We will clarify this issue in the revised version. Nevertheless, in learning problems in which $f$ is unknown but the value of $Z\\_t$ is known, this interpretation can still be used. \n\n- **(...an alternative way of setting $\\tau$ when $f$ is unknown...)** For instance, with the power of Bayesian modelling $f$ can be estimated with confidence bounds which can be used to pick a meaningful $\\tau$ value. For example, picking $\\tau \\geq \\max\\_{\\mathcal{X}\\times\\mathcal{C}} \\text{ucb}\\_t(x,c)$ almost  certainly sets us to failure ($\\tau$ not achievable with high probability). In contrast, picking $\\tau \\leq \\langle w\\_t, \\text{lcb}^t\\_{\\hat{x}'\\_t}\\rangle$, where $\\hat{x}'\\_t := \\arg\\max\\_{x \\in {\\cal X}} \\langle w\\_t, \\text{lcb}^t\\_x\\rangle$, guarantees with probability at least $1-\\delta$ that the optimization problem (1) is feasible. \n\n- **(...regret bounds for time-varying $\\tau$...)** By going over the original proofs, it can be verified that indeed $\\tau$ can be selected dynamically, $\\tau\\_t$, $t \\geq 1$. To see this, we also change the thresholds in our regret definitions to $\\tau\\_t$, and update Assumption 1 such that $\\tau\\_t \\leq \\langle w\\_t, f\\_{\\hat{x}\\_t}\\rangle$, $t \\in [T]$, all derived regret bounds  still hold.\n\n- **(...experiments...)** The real-world experiment is taken to the main paper with the addition of WRBO and SO benchmarks. During the response phase, we also performed new experiments including comparing cumulative rewards of different algorithms on the true distributions and sensitivity analysis w.r.t. $\\tau$. These can be found in the response pdf. \n    \n\n#### Clarity\n1) We thank the reviewer for their suggestion and we note that we have slightly updated the definitions to increase clarity. As you suggested, $\\kappa\\_{\\tau,t}$ can be computed in two steps. We wrote the first equation to highlight robust satisficing as a single optimization problem. \nIn RS, the objective is to find $x^*\\_t \\in \\mathcal{X}$ that solves in each round $t$\n\\begin{equation}\n    \\kappa\\_{\\tau,t} = \\min k\n    ~ \\text{s.t.} ~ \\mathbb{E}\\_{c\\sim P}[f(x,c)] \\geq \\tau - k \\Delta(P,P\\_t), ~ \\forall P \\in {\\cal P}\\_0 ~ , x \\in {\\cal X}, ~ k \\geq 0 ~ . \\tag{1}\n\\end{equation}\nTo find $x^*\\_t$, we can first compute the *fragility* of $x \\in {\\cal X}$ as  \n\\begin{equation*}\n    \\kappa\\_{\\tau,t}(x) = \\min k ~ \\text{s.t.} ~ \\mathbb{E}\\_{c\\sim P}[f(x,c)] \\geq \\tau - k \\Delta(P,P\\_t), ~ \\forall P \\in {\\cal P}\\_0, ~ k \\geq 0 ~ .\n\\end{equation*}\nThe robust satisficing objective is feasible when (1) has a solution.\n\n2) Colorbars added where necessary.\n\n3) Fixed."}]

Author rebuttal:
We sincerely thank the reviewers for their careful reading of our paper and constructive comments. Here we address the common questions raised by the reviewers.
- **(Real-world experiments and how to select $\tau$)** One real-world experiment concerning safe dose allocation for diabetes patients is presented in the supplementary document. Type 1 Diabetes Mellitus (T1DM) patients require bolus insulin doses (id) after meals for postprandial blood glucose (pbg) regulation. One of the most important factors that affect pbg is meal carbohydrate (cho) intake [C]. Let ${\cal X}$ and ${\cal C}$ represent admissible id and cho values. For $x \in {\cal X}$, $c \in {\cal C}$, let $g(x,c)$ represent the corresponding (expected) bpg value. Function $g$ depends on the patient's characteristics and can be regarded as unknown. The main goal of pbg regulation is to keep pbg close to a target level $K$ in order to prevent two potentially life-threatening events called hypoglycemia (e.g., pbg $<$ 70 mg/dl) and hyperglycemia (e.g., pbg $>$ 180 mg/dl). This requires $x\_t$ to be chosen judiciously based on current $c\_t$. Patients rely on a method called cho counting to calculate $c\_t$. Often times, this method is prone errors [D]. The reported cho intake $\zeta\_t$ can differ significantly from $c\_t$. In order to use DRO, one needs to identify a range of plausible distributions for cho calculation errors, which is hard calculate and interpret. On the other hand, specifying $\tau$ corresponds to defining an interval of safe pbg values around $K$ (e.g., pbg $=$ 125 mg/dl) that one is content with, which is in line with the standard clinical practice [E]. We will move this experiment from the supplemental document to the main paper. In addition, in response to the comments of reviewer Gzxd and KF6g, we performed new experiments that compare accumulated rewards of RoBOS and other competing benchmarks. Moreover, we also carried out simulations that shows sensitivity of the results to the aspiration level $\tau$ set by the learner. These results can be found in the response pdf.
- **(Advantages of RS over DRO)** RS has multiple advantages over DRO depending on the problem setup. The main difference is that it considers the goal of satisficing rather than optimizing. Satisficing is argued to be normatively better than optimizing by many decision theorists and philosophers [16, 17, 18], especially under settings of deep uncertainty. Once the normative shift is made from optimizing to satisficing, a reasonable approach for decision-making is to maximize the robustness of the action to the uncertainties of the environment. RS achieves this by selecting the action that achieves the desired threshold under all possible context distributions the environment can produce. When no such action is present, RS picks the action that achieves the threshold under the biggest set of context distributions and minimizes the margin of error with respect to the threshold. Consider the case where $\tau = Z\_r := \max\_{x \in \mathcal{X}}\min\_{P\in\mathcal{U}(r)} \mathbb{E}\_{c\sim P} [f(x,c)] $, where $\mathcal{U}(r)$ is the ambiguity ball of radius $r$ centered at $P\_t$. For this setting DRO solution implies
\begin{align*}
    &\tau - \mathbb{E}\_{c\sim P} [f(x\_{\text{DRO}},c)] \leq 0 \qquad \forall P \in \mathcal{U}(r) \\\\
    &\tau - \mathbb{E}\_{c\sim P} [f(x\_{\text{DRO}},c)] \leq \infty \qquad \forall P \in {\cal P}\_0 \setminus \mathcal{U}(r) 
\end{align*}
whereas the RS solution implies
\begin{align*}
    &\tau - \mathbb{E}\_{c\sim P} [f(x\_{\text{RS}},c)] \leq \kappa\_\tau \Delta(P,P\_t) \qquad \forall P \in \mathcal{U}(r) \\\\
    &\tau - \mathbb{E}\_{c\sim P} [f(x\_{\text{RS}},c)] \leq \kappa\_\tau \Delta(P,P\_t) \qquad \forall P \in {\cal P}\_0 \setminus \mathcal{U}(r) 
\end{align*}
Algorithmically, RoBOS needs less information than DRBO since unlike DRBO, RoBOS does not utilize an ambiguity set for which the true distribution is assumed to be in. It is shown in the experiments that when the ambiguity ball is not selected correctly, DRBO solutions can be suboptimal or even disastrous w.r.t. the satisficing goals. In contrast, it would be better to use DRO if we have a tight and trustable ambiguity set and the goal is optimizing rather than satisficing. In addition, in some applications such as blood glucose regulation, RS is more interpretable than DRO (see our previous response).

### References
- [A] Gretton et al., A kernel two-sample test. 2012.
- [B] Sejdinovic et al., Equivalence of distance-based and rkhs-based statistics in hypothesis testing. 2013.
- [C] Walsh et al., Guidelines for optimal bolus calculator settings in adults. 2011
- [D] Kawamura et al., The factors affecting on estimation of carbohydrate content of meals in carbohydrate counting. 2015.
- [E] Kahanowitz et al., Type 1 diabetes–a clinical perspective. 2017.


Meta-review: This work studies (contextual) Bayesian optimization with shifts in the distribution of contexts. The authors propose a new algorithm motivated by the idea of robust satisificing. The paper makes meaningful algorithmic and analytic contributions to multiple communities (Bayesian optimization, distribution shifts). The reviewing team has raised several issues with the exposition. In addition to addressing the carefully, I recommend the authors to candidly discuss the limitations of their work in the camera-ready version.
Decision: Accept (poster)