Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks
Authors: Artun Saday
Y. Cahit Yıldırım
Cem Tekin
Venue: NeurIPS 2025 poster ()
Keywords: robust satisficing
regret minimization
adversarial attacks
Primary area: general_machine_learning

Abstract: We address the problem of Gaussian Process (GP) optimization in the presence of unknown and potentially varying adversarial perturbations. Unlike traditional robust optimization approaches that focus on maximizing performance under worst-case scenarios, we consider a robust satisficing objective, where the goal is to consistently achieve a predefined performance threshold $\tau$, even under adversarial conditions. We propose two novel algorithms based on distinct formulations of robust satisficing, and show that they are instances of a general robust satisficing framework. Further, each algorithm offers different guarantees depending on the nature of the adversary. Specifically, we derive two regret bounds: one that is sublinear over time, assuming certain conditions on the adversary and the satisficing threshold $\tau$, and another that scales with the perturbation magnitude but requires no assumptions on the adversary. Through extensive experiments, we demonstrate that our approach outperforms the established robust optimization methods in achieving the satisficing objective, particularly when the ambiguity set of the robust optimization framework is inaccurately specified.

Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks
Artun Saday
Yaşar Cahit Yıldırm* Bilkent University, Ankara, Türkiye cahit. c wwl.iriimmmiieeent edu,
Bilkent University, Ankara, Türkiye artun artun.saday0in sadayybiktiii edu.
Cem Tekin Bilkent University, Ankara, Türkiye cemtekinβee. bilkent. edu. tr
Abstract
We address the problem of Gaussian Process (GP) optimization in the presence unknown and potentially varying adversarial perturbations. Unlike traditional robust optimization approaches that focus maximizing performance under worst- case scenarios, we consider a robust satisficing objective, where the goal is to consistently achieve predefined performance threshold even under adversarial conditions. We propose two novel algorithms based on distinct formulations robust satisficing, and show that they are instances of general robust satisficing framework. Further, each algorithm offers different guarantees depending on the nature of the adversary. Specifically, sublinear over time, assuming certain conditions on the adversary and the satisficing threshold r, and another that scales with the perturbation magnitude but requires no assumptions on the adversary. Through extensive experiments, we demonstrate that our approach outperforms the established robust optimization methods in achieving the satisficing objective, particularly when the ambiguity set of the robust optimization framework is inaccurately specified.
derive two regret bounds: one that is
Introduction
Bayesian optimization (BO) is framework particularly suited for sequentially optimizing difficult- to-evaluate black-box functions f. using a probabilistic model such Gaussian process (GP) [ BO uses a probabilistic surrogate model (c.g., GP) with an acquisition function to decide where to sample next. Designing acquisition functions tailored to specific problems is significant research area in the BO literature. The performance of a BO algorithm is often evaluated by its regret, which quantifies the difference between the objective function values at the chosen points and the optimal point, or another predefined success criterion.
BO has proven effective in applications such hyperparameter tuning (2) engineering design (.). experimental design 4. and clinical modeling [5] In these settings, robustness to distribution shifts and environmental variability is essential. For instance, machine learning models must generalize beyond training data, while engineering designs must transfer from simulation to real-world deploy- ment. In high-stakes domains like autonomous driving or patient treatment, ignoring uncertainty can lead to severe failures. Robust optimization (RO) addresses this by seeking solutions that perform well under worst-case scenarios defined by an ambiguity set (6) However, the ambiguity set be carefully defined: if it is too narrow, it may exclude relevant uncertainties; if too broad, it can lead to conservative solutions that underperform under typical conditions g
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

fix)
RS-G. (RS/1)
RS-G, p- (RS-2)
pm2
Figure 1: Illustration of how different RS formulations trade off reward guarantees with respect perturbation magnitudes during action selection. Decision of each formulation can be interpreted selecting the action (diamonds) by enforcing the widest fragility-cone (dashed lines) limit the performance degradation beyond 7 due to the perturbation. The fragility-cone is the reward guarantee of the solution RR G, T (nr.pp((RRS RS. + 6)} defined in (IO). It characterizes the shape of the constraint on performance degredation. For more details, see Section and Appendix B
Satisficing, a term coined by Herbert Simon 9 introduces a pragmatic approach to decision decision-making where the goal is achieve outcome that is good enough (f():) 7) rather than optimal. This concept is especially relevant in environments where the optimal solution is either unattainable or impractical due to computational informational constraints. Satisficing has been studied in the context of multi-armed bandits (MAB) by [0 11 12 13), while [4] investigates the problem in a non-Bayesian setting using the RKHS framework. Building on this concept, robust satisficing (RS) extends the principle of satisficing by aiming to optimize confidence in achieving sufficiently good outcome, thus providing robust framework for decision-making under uncertainty. Unlike simple satisficing. which may serve as a stopping heuristic, RS focuses on ensuring reliable performance across a variety of scenarios. Decision theorists such as [15] and [16] argue that RS offers superior alternative to RO, as it emphasizes acceptable performance across a broad range of scenarios rather than focusing solely on worst-case outcomes. [17 proposes an optimization formulation for RS which inspires our approach. [18) builds on this by combining RO and RS in unified framework that accounts for both outcome and estimation uncertainties. our work we extend the RS literature by proposing a novel formulation, RS-G, which generalizes 17 by allowing nonlinear decay of the reward guarantee via a tunable parameter.
One form of uncertainty that RO and RS seek to address are adversarial perturbations. In many learning systems, small, targeted changes to the input can induce large deviations in output, un- dermining reliability. While this phenomenon is well studied in neural networks [19] 20),, similar vulnerabilities exist continuous control and optimization settings, where the selected input may be corrupted by noise external interference. Addressing such perturbations requires robust strategies that extend beyond worst-case formulations, particularly when the perturbation model or budget only partially known. This motivates our development of an RS approach for adversarially perturbed GP optimization.
Related Works Research on robustness, particularly adversarial robustness. in GP optimization is extensive. [21] tackles BO with outliers by combining robust GP regression with outlier diagnostics. [22, closely related to our work, introduces the setting of adversarial robustness in GP bandits. They propose an RO based algorithm that assumes a known perturbation budget, while we adopt an RS approach without this assumption.
(23] addresses similar problem where the learner selects #t but observes outputs at a different point I; ~ Pa.- using a GP model for probability distributions. In the noisy input setting, [24] proposes entropy search algorithm. Adversarial corruption of observations, rather than inputs, is considered by [25] 26). Contextual GP optimization considers uncertainty in the context distribution. [27] address this using RO with known ambiguity set, while (28 extend the approach by adopting RS without assuming knowledge of the ambiguity set. A
complementary direction is explored by 22 30 31) focusing on the BO of risk measures while (32 jointly optimizes the mean and variance of f(r, w) using a GP.
Contributions We propose new RS-based acqusition functions for the first time for a variant the GP optimization problem called Adversarially Robust GP Optimization introduced in (22). where an adversary perturbs the selected action. Based on principles of robust satisficing, we introduce two novel algorithms for finding robust action while achieving small lenient and robust satisficing

---

Objective
Formulation
[(x)
Standard
arg max f(x)
T- 10
R81
RO
arg max min f(x + 8) óEA.(m)
RS2
RD = 0.5
arg min & s.t.
RS-1
RO 0.25
1( 6) 2 VĀ E xc (I), k 2
arg max S.I. x f(x + 0) T, vO (x)
RS-2
E 0
arg min k s.t.
RS-G
f(x + +6+ [kd(a, x x+ 6)]P,
4A E Ax (z), k
3
Figure 2: (Left) Illustration of RO and RS solutions. Highlighted contours represent f(x) T, i.c. the satisficing threshold. (Right) Formulations of different optimization objectives.
regret, based on two distinct RS formulations (RS-1 and RS-2 in Figure 2). We show that these formulations are edge cases of a general robust satisficing framework (RS-G in Figure 2 (right)) with smoothness parameter p 2 1. We demonstrate how a spectrum of robust solutions can be obtained by varying (see Figure D We provide theoretical bounds on the regrets of our algorithms under certain assumptions. Finally, we present experiments, including in-silico experiments on an FDA-approved simulator for diabetes management with realistic adversarial perturbations, to demonstrate the strengths of our algorithms addressing the shortcomings of other approaches known in the literature.
2 Problem Formulation
Let f an unknown function defined on the domain X' C Rmm endowed with a pseudometric d(.;)): X x X' - IR. Further assume that f belongs a Reproducing Kernel Hilbert Space (RKHS) H. with the reproducing kernel k(:-)) X' x X > IR, and has bounded Hilbert norm [| I B, for some B > 0. This assumption ensures that f satisfies smoothness conditions such as Lipschitz continuity with respect to the kernel metrid? 33 and allows the construction of rigorous confidence bounds using GPs (34]. At each round E [T), where T represents the time horizon, the learner picks a point ã, E X. in response to which the adversary selects a perturbation 8G. The learner then observes the perturbed point 2, E, + 6₁ along with the noisy sample at that point ye f(z)) + me. where Te are independent R-subGaussian random variables. the adversary is allowed to play always choose
any nerturbation &e, matter what action ét the learner chooses, the adversary a perturbation & such that ãt + 6e = arg min x fxx and the optimization problem would be hopeless. Hence each round perturbations the adversary can play. We define for each point I E X, the ambiguity ball
assume unknown perturbation budget 6, that bounds set of
A.(x)
{a'
x X and d(x,x') <
(1)
The ambiguity ball (T] defines the set of all permissible perturbations of the adversary, when the perturbation budget is Hence in response to action the adversary plays the perturbation 5, E A,,
Remark 1. In the presented setting, it is not possible to learn the function optimum in general. As an example consider the arm MAB problem with X' x2) with f(x1) and f(x2) 1.
FFor the kernel metric, we have ff()) - f(x') x) k(- x 11 S [l not necessarily Lipschitz continuous with respect to an arbitrary metric on X. Hence in our analysis, we assume the pseudometric d(-, is the kernel metric. Additionally, when the feature map k(,, 2) is injective, this pseudometric is also metrie.
Note that
3

---

Then at each round t. a sufficiently strong adversary can always choose a perturbation 6, such that Ft 21, hence the learner can never observe the optimal action.
2.1 Robust Satisficing
The key difference between RS and RO lies in their objectives. While RO seeks to optimize for worst- case outcomes, RS prioritizes achieving satisfactory performance across various scenarios. RO relies heavily on defining an ambiguity set, typically as a ball with radius r. centered around a reference value of the contingent variable. The choice of greatly impacts performance. Overestimating leads to conservative solutions that overemphasize unlikely worst-case scenarios, while underestimating risks overly optimistic solutions. Figure (left) demonstrates the effect of different choices of r.
In our context, the contingent variables are the adversarial perturbations. In other settings, such as data-driven optimization with distributional shifts, contingent variables might represent different uncertainties, such as deviations from an empirical distribution [35]. Unlike RO, which requires an ambiguity set, RS relies only on the satisficing threshold т, representing the desired outcome. This makes T more interpretable and adaptable to real-world problems, where it can be chosen by domain experts. We now present two formulations based on the RS approach, assuming the function f is known.
RS-1 We adapt the novel formulation by 17 to our adversarial setting. Let (+) max(: 0}. The objective of this formulation is to find x RS-1 E X that solves the optimization problem Ri == mingex Ki (z) where nyy (z) is the fragility of action
X defined as
Ky (z) == min k s.t. f(x + 2 kd(x, x 6), Ag (z) 2
(2)
This is equivalent to solving
(a++6) max (x) d(2x+8)
if ff) 2 if f(x) <
Ky (2))
+00
When (2 is feasible, the RS-1 action is defined as RS arg min Kr (I)). The fragility of an action can be seen as the minimum rate of suboptimality the action can achieve w.r.t. the threshold T, per unit perturbation, for all possible perturbations. Crucially, while the RO formulation only considers perturbations possible under a given perturbation budget the RS-1 formulation (2) considers all possible perturbations. This way RS gives safety guarantees even when the perturbation budget of the adversary is unknown. Figure 2 (left) highlights the RS-1 action RS-I together with optimization objectives.
RS-2 Inspired by the literature on robust satisficing, we present another formulation called RS-2, similar to the one (6). Formally, the objective of RS-2 to find Rs-22 E X that solves the following optimization problem 6 == maxzex (Iz where (z) is the critical radius of action x E X defined as
(= d(x,,') s.t. f(x + +) T, Võ E (x(x,))
a' e'e
The robust satisficing action is defined as the one with the maximum critical radius, RRS522 arg maxzex (xr) If
f(x)= r and is a local maximum, then (z) = because 5 = 0 is the only perturbation satisfying the inequality condition. If fx) < т, then c, (x) -00, as no satisfies the condition, and by convention, we take the supremum of the empty set as the critical radius, which is -o0. Unlike RO, RS-2 does not assume knowledge of the adversary's budget c, but instead searches for the action that achieves the threshold under the widest possible range of perturbations. This target-driven approach aligns RS-2 with the philosophy of robust satisficing. Figure ,RS-2 alongside other optimization objectives. If 7 [()), where ã := arg max f(x) is the optimal action, no action can meet the threshold, even without perturbations, hence we introduce the following assumption moving on.
highlights
Assumption 2.2. T < maxxex f(x).
Assumption 2.2 ensures that the optimization problems 2 for RS-1 and (4) for RS-2 are feasible, thereby guaranteeing that a robust satisficing action is well-defined in both cases. However, since f is

---

unknown, it may not be immediately clear to the learner whether specific threshold T satisfies this assumption. If the learner is flexible with the satisficing threshold, Assumption 2.2 can be relaxed by dynamically selecting 7 at each round to be less than ( where diz := arg max Icb,(z).
The function Icb, represents the lower confidence bound of the function, whose proper definition given in Section [ Additionally, in many real-world tasks, T can be chosen to satisfy Assumption 2.2 using domain- sppliiiieeiiiccc information. For example, in hyperparameter tuning where the objective f(a) represents model accuracy, f()) is upper bounded by I (the maximum possible accuracy) and can be lower bounded by the accuracy of the best-known model (e.g., 0.97).
Remark 2.3. Our formulation treats the perturbation as an arbitrary adversarial quantity rather than as a random variable. Therefore, direct comparison with probabílistic robustness measures such as Value-at-Risk (VaR), Conditional Value-at-Riss. (CVaR), or distributionally robust optimization (DRO) is not immediate, since these formulations assume access a known or estimable perturbation distribution. Incorporating such measures would require modifying the problem setting to include a random covariate the objective, f(x, E), and redefining the satisficing condition with respect the distribution of ç. While one could, for example, define a variant of robust satisficing conditioned on reference estimate of this distribution, such an approach restricts the power of the adversary and leads to less general setting than the one considered here. We emphasize these conceptual differences to clarify the distinction between adversarial and probabilistic robustness.
2.2 GP Regression
It is well established in the literature that function f H. from RKHS with reproducing kernel k(,-)) -) with bounded norm |l. ll S B can be approximated using GPs. Given dataset of observation pairs D, (Ii, == using Gaussian likelihood with variance À >> 0 and prior distribution GP Mxx x²) r)),, the posterior mean and covariance of a Gaussian process can be calculated as
(x) = (I: + A ye.
(x) = k( x²)
(K, + AI.) ke(x)) (5)
with of = he ()) where column vector (z) = [,(2,, ==) K; is the x kernel matrix with elements (Kt)ij = 2z)) These posterior mean and variance functions enable the construction of confidence intervals for the function f(xx), which are integral to the optimization strategies we
employ. Specifically, in our adversarial setting, these confidence intervals are used to bound the fragility K. (z) and the critical radius e, (z) of each action, as discussed in the next section.
2.3 Regret Measures
In BO it is common to measure the success of an algorithm using a regret measure, which usually measures the discrepancy between the reward of the action played against the reward of the optimal action. We use lenient regrel and robust satisficing regrel defined respectively as:
R4 (T f(x)))+
RT Σ
(T (T- KrE; f(x)))*
(6)
Lenient regret, introduced by [II], is natural metric for satisficing objectives. It captures the cumulative loss with respect to the satisficing threshold. Sublinear lenient regret is unattainable under unconstrained adversarial attacks, as a sufficiently large perturbation budget allows the adversary to force any action below т. Thus, upper bounds on lenient regret must depend on perturbation magnitude or impose constraints on the budget and threshold т. Robust satisficing regret (28), instead evaluates loss relative to the RS-1 benchmark, comparing the true reward of x; against the guaranteed reward of RS-I under perturbations of at most e,. The RS-1 action ensures f (2 >
T Kr under such budget.
3 Algorithms and Theoretical Results
Confidence Intervals Our algorithms utilize the GP-based upper and lower confidence bounds
defined as (x:) = (x) (,0:-1(xx) and (x) = 14 (2) 3,r (2:). respectively, where 3 a I-dependent exploration parameter. For theoretical guarantees, ,9, is set as Lemma 3.1
which is based on [37] but argued to be less conservative and more practical [38]
5

---

2 (og(det([1 A (A)), where Lemma 3.1. 138 Theorem 11 Let E (0,1), X max A}, and
B((5) = B+ Vx log(dot( π
A K +XL-11) + 2og
Then, the following holds WPAL ç: leba(x) S {(x) ucba Vo X, 14 1.
We label the event in Lemma 3.1 as E and refer to it as the good event. Our analyses will make use of the maximum information gain defined as 7t ACX:]A|==+
max
K A is the kernel matrix given by the sampling set A. Following the work of [34), the use of y is common in the GP literature. Since f an unknown black-box function, K, for RS-1 and E, for RS-2 cannot be calculated directly. The proposed algorithms leverage upper and lower confidence bounds to estimate these values while balancing the exploration-exploitttio trade-off.
Algorithm AdveRS-1
1: Input: Kernel function k X, T, R, B, confidence parameter Ç, time horizon T
2: Initialize: Set Do = 9 (empty dataset), (z) = 0, ou(x) 1 for all x
3: for to T do
4: Compute (x) 14_1 (x) + 3,0,-1 (z)), Vo X
5: Compute (x) as in Va E EX
6: Select point arg min (x))
7:
Adversary selects perturbation 5, E A, (5t)
8:
Sample 24 Σ + ò, observe y1 (zx) + 17
9: Update dataset D, = D:-1 U (IT,, }t)
Update GP posterior as in (5)
11: end for
Algorithm 2 AdveRS-2
5: Compute (x) as in Vx E X'
6:
Select point arg max (xr(
Algorithm for RS-1. To perform BO with the objective of RS-1, we propose Adversarially Robust Satisficing-1 (AdveRS-I) algorithm, whose pseudo code given in Algorithm [ At the beginning of each round f, AdveRS-1 computes the upper confidence bound ucb:(x) of each action E X. Using the ucb, in (2). computes the fragiittt defined as:
ucb. + +0)
+
(x)((x)
max (x).
d(a, + 8)
(x))(x)) т. and otherwise (x)( == oc. Further, we define the minimizer Ry,, minzex (xr)( The optimistic fragility, (x), provides an optimistic estimate of the true fragility (x) for each action. AdveRS-1 selects the action with the smallest optimistic fragility, Tt arg mil (x)) to encourage exploration. Additionally, we define the pessimistic frugility (x) which uses lcb instead of the ucb equation (7). and Ey, := millge (x)) The following lemma relates the estimated and true fragilities of an action.
Lemma 3.2. Given & holds, the inequality. RT,((x) S (x) S (x) is true for all x E X,
Lemma 3.2 is a result of the monotonicity fragility result in 117, with the proof provided in the Appendix. The following Corollary which illustrate how K (x) and (x:) contribute to quantifying the robustness of an action z at round f, follows from Lemma 3.2 and the RS-1 objective (2).
Corollary 3.3. Under Assumption 2.2 with probability at least G. AL E (T) holds that:
f(a. + 8) 2 Er, d(ār, T. + 5), 4e E (āt); conversely, 38' E À (ōx) s.f. f(x + 8*) S T- Ry,e d(ā,. Et 8").
Algorithm for RS-2 For the RS-2 objective, we follow similar path and propose the Adversarially Robust Satisficing-2 (AdveRS-2) algorithm which is given in Algorithm 2 The algorithm follows

---

similar structure to Algorithm 1 with only the lines that differ being shown, along with their corresponding line numbers. AdveRS-2, again, makes use of the confidence bounds to create an optimistic estimate of the critical radius (xx) of each action. Specifically, we define the optimistic critical radius as:
(T,( == max d(z, x') s.t. ucb(x + 2) TT Ag (()))))))) x'EX'
(8)
with Er,, = m E,, AdveRS-2 uses the optimistic critical radius for exploration, sampling at each round & the action ū = arg max (x, which has the largest optimistic critical radius. Further we define the pessimistic critical radius e, (1x), which uses the leb instead of the ucb in equation (8) The following Lemma bounds the true critical radius e, (x) of each action ø.
Lemma 3.4. Given & holds, the inequality, Lr,(2) S (x) S (x)(2) is true for all x E Ex 1.
Corollary 3.5. Under Assumption 2.2 with probability at least 1 - C. Vt E [T] it holds that f(, + 8) 2 T, 4ō E E.., (ite and that when De, (it) is a strict subset of A (8)), 38 AZ, (#))
s.r. f(ă, + S T.
Corollary 3.5 gives information about the achievability of satisficing threshold T. In practice, a learner might use this information tune the either more ambitious or more conservative one.
Regret analysis of AdveRS-1 Regret analysis of Algorithm D is done with the distance function defined as the kernel metric, d(x,x')= = Vk(x, x) 2k(r x²) + k(r', x²), and we make use of the Lipschitz continuity of f.
Theorem 3.6. Let Ç E (0, 1), and let f E H with II S B. Let k(..-) be the reproducing kernel ni be conditionally R-subgaussian. Under Assumption 2.2 when the distance function d(.,.) is the kernel metric and 3r as defined in Lemma 3.7 the lenient regret and robust satisficing regret of A 1 are bounded above by:
H, and n
R2 S 43T + B
Σ
E
R S
Proposition 3.7. In the context of Theorem 3.6 the linear term B ET= c in the lenient regret bound unavoidable. Specifically, there exists an instance of the problem setup where this term manifests as a lower bound on the lenient regret for any algorithm.
Regret analysis of AdveRS-2 The RS-1 formulation provides reward guarantees under any pertur- bation 8 E (x. ), ensuring that f( 2 7 fiT RS- Rs- + 5). In contrast, the RS-2 formulation does not provide reward guarantees for every possible perturbation but offers stronger guarantee, R52) 2
for restricted set of perturbations 5 E A., (5-2)) where e, is defined in (4). This distinction is reflected in the regret analysis of AdveRS-2. To bound the regret of AdveRS-2, introduce the following assumption.
Assumption 3.8. Assume that the perturbation budget of the adversary 6, S, for all & Z 1.
Remark 3.9. Assumption 3.8 which is stronger than Assumption 2.2, ensures that at each round t < T. there exists an action x X meeting the threshold against any sivversay-ssllctee perturbation 5; E A., (z). Without Assumption 3.8, achieving sublinear lenient regret is impossible, as there will always be a perturbation
A., (I)) causing fa + 5) S T for any x. Theorem 3.10. Under the assumptions of Theorem 3.6 Assumption 3.8 and the robust satisficing regret of AdveRS-2 are bounded above by: Ry, Rt S "T..
both the lenient regret
While the lenient regret bound of AdveRS-2 requires further assumptions on the perturbation budget of the adversary, it is also stronger than the regret bound of A and matches the standard regret bound V(T of GP-UCB (37]. When the kernel k(,, .) is the RBF kernel or the Mátern-y 2iet:3m 40m-
kernel, the regret bound reduces to ((VT) and (T
respectively, where m is the dimension
of the input space [39].
4 Unifying the RS Formulations
The reward guarantee of the RS-1 solution in (2) falls off linearly with the magnitude of the perturba- tion. On the other hand the reward guarantee of the RS-2 solution stays constant up perturbation
7

---

magnitude of Cr. than disappears. In practice one might want to be more flexible with the reward guarantee of their solution. For example one might desire the solution obtained to give a guarantee that stays close to for small perturbations, while not giving too much importance to larger perturba- tions as they may be deemed unlikely, depending on the structure of the problem. Motivated by this, we propose the following robust satisficing formulation RS-General (RS-G). For p 2 1 define the p-fragility of an action as,
Kr (2) == min l s.t. f(x + 2 -- [ Vg E (z). h 220. (10)
The RS-G action is x RS-G := arg min pz).
Proposition 4.1. Let RSSG denote the solution obtained from the RS-G formulation when applied with power parameter p. It holds that limp- 2BS-G -285-2
The parameter p controls the trade-off the RS-G formulation. Specifically, at 1, the reward guarantee decreases linearly with perturbation magnitude. As p increases, it enhances reward guarantees for small perturbations but diminishes for large perturbations. As approaches infinity, the formulation converges RS-2, offering robust guarantees for perturbations within A., (x) but none for those outside it. A more detailed comparison of the RS-G formulation with RS-1 and RS-2 is available in Appendix B Algorithm I can be readily adapted the RS-G framework by replacing optimistic fragilities with optimistic p-fragilities Ry p.(x))))) which are (IO) calculated on (2)), instead of (x)) We call this general algorithm AdveRS-CO Similarly, we can generalize our RS regret to the RS-G formulation R == Ei= (r & - fxx))) This measures, at each time step the discrepancy, between the played action, and the reward guarantee of the JRS-GG solution, for specific p. Finally, we bound the general RS regret in the next corollary.
Corollary 4.2. Under the assumptions of Theorem 3.6 AdveRS-G satisfies RT S 443
Experiments
In each experiment, we compare the performance of AdveRS-1 and AdveRS-2 against the RO baseline [22), which is run with an ambiguity ball of radius r that is equal to, smaller than, and greater than the true perturbation budget e, each round and use the Euclidean distance as the perturbation metric. We use the following attack schemes in our experiment:
Random Attack: 6, ~ Uniform( A,, (i+))
LCB Attack: 6, arg
lcb, (ā, + 5)
Worst Case Attack: d, arg minse (Rx) f(ū + 5)
The results of all experiments are averaged over 100 runs, with error bars representing std/2.
Additional experiments can be found in the Appendix Our code available at: https
wtttchub.co//illlae CAE--CCCBBROORAEE AdveRS
Synthetic experiment In the first experiment, we use the proof-of- function in Figure 2 modified version of the synthetic function from (22]. We the threshold -10 and conduct
two experiments:
(a) e, = 0.5 (Assumption 3.8 holds) and (b) e, 1.5 (Assumption 33. fails to hold). For the RO representative,
STABLEOPT 22 with radius parameters r 6t. r 4e,,
and r = 0.5e,- The observation noise follows 7/ ~ NO 1). and the GP kernel is a polynomial kernel trained on 500 samples from the function. Figure shows that STABLEOPT performs poorly when the adversary's perturbation budget is misestimated, leading to linear regret, while AdveRS-2 consistently meets the threshold T, achieving sublinear lenient regret. AdveRS-1, though not always reaching т, still outperforms STABLEOPT when is misspecified. As depicted in Figure 3b when Assumption 33.8 fails, all algorithms experience linear regret, consistent with Remark 3.9 This figure also illustrates that AdveRS algorithms maintain robustness towards the goal even when is unattainable. Additionally, RS-G with p = 2 exhibits the smallest regret, suggesting that tuning the p parameter can be beneficial for certain problems. Figure 4 our algorithms consistently beat the RO baseline in RS regret, even when STABLEOPT run with the perfect knowledge of the adversarial budget.
8

---

Random Attock
LOB Attack
Worst Case Astack
1230
2000
Begest
(3844
BS44 pin
(a)
0000
80
(3
10
33
100
Bound
Roud
Round
LCB
2000
1000
3000
pim (184))
3003
4290
RSG. yow (18.5)
BSC p-2
BD m-
2000
(b)
2031
BD
BD
200
1291
60
40
000
Bound
Round
Bound
Figure 3: Lenient regret results for synthetic experiment shown in two scenarios: (a) satisfying and (b) failing to satisfy Assumption 3.8
Random Ataak
LCB Attaci
Worns Chae Attack
230
1231
(RS-21
D5 Staare
RD
RD
2.0
130
Roand
Round
Round
Figure 4: Robust satisficing regret results for synthetic experiment.
Insulin dosage In adversarial contextual GP optimization, the learner selects an action 22 E after observing reference contextual variable cf E C, which is then perturbed by adversary. Then, the learner observes the perturbed context ç₁ = ct + 6, along with the noisy observation f(x,, ca) + Л)- We apply this to insulin dosage selection problem for Type Diabetes Mellitus (TIDM) patients using the UVA/PADOVA T1DM simulator [40] T1DM patients require bolus insulin administrations usually taken before meal 41. improve postprandial blood glucose (PBG) prediction [2].
Contextual information about the carbohydrate intake known to
80
(100, 0,
10, (1ll. o,
BS-C, p- (RS-1)
RS-G, p- (RS-1)
Leuient. Regret
RS-C, p- oz (RS-2)
RS-G, p 0o (RS-2)
Regret
RS-G. p-2
RS-G, p-2
10
RO
RO =
RO
RD
RO
R0 3-0,
20
Round t
Round
Figure Lenient and RS regret results of insulin dosage experiment.
However, the carbohydrate announcements prior to meal consumption can deviate from the actual carbohydrate intake, hence robustness to contextual shifts are important diabetes management. Maintaining PBG around a neighbourhood of a target level K as K т, K + r] mg/dl. represents a satisficing objective defined as -lf(x) - K| 2 r. The action space units of insulin in the
range [0, 15), and the context is carbohydrate intake, perturbed by 6, NN(0, of) with a, 32,

---

representing roughly 2 slices of bread. As shown in Figure 10, although no algorithm achieves sublinear regret, both AdveRS-1 and AdveRS-2 outperform STABLEOPT when the radius r is suboptimal. While STABLEOPT performs best when r = s. selecting this parameter can be difficult. In contrast, the parameter can be more easily chosen by clinician, aligning with common clinical practice [1].
Robustness to worst case attack We consider the robustness of the solutions from Figure 2 (left), under worst case adversarial perturbations of increasing magnitude. Specifically we inspect minges, [(= + 6) where x" corresponds to the points selected by each objective. To evaluate the robustness of solution w.r.t. achieving T, calculate the following:
Area(e) )one())=/" { max (O.T min (E))((x")
fa" + +6) de'.
The lower this value is, the better the robustness of the method to range of different perturbations up e. A clear discrepancy can be seen between our methods and the RO baseline, with both RS-1 and RS-2 actions demonstrating greater robustness. Further, while RS- 2 is better in achieving т, RS-1 is more robust to discrepancies when т not attainable.
115-2 (IS-4)
(il) fic" 8)
20
0:25
-10
Aroa(o)
15-
-30
6-
-40
(from O to 1/3 of domain range)
(from 0 to 1/3 of domain range]
Figure 6: (Left) Rewards for the points selected by each algorithm, under worst case attack with perturbation budget e. (Right) Area under the curves as a function of perturbation magnitudes.
6 Conclusion
In this paper, we addressed GP optimization under adversarial perturbations, where both the pertur- bation budget and strategy are unknown and variable. Traditional RO approaches rely on defining an ambiguity set, which is challenging with uncertain adversarial behavior. We introduced a robust satisficing framework with two formulations. RS-1 and RS-2, aimed achieving a performance threshold 7 under these conditions. We also showed these two formulations can be united under more general RS formulation. The RS-I-based algorithm offers lenient regret bound that scales with perturbation magnitude and a sublinear robust satisficing regret bound. The RS-2- 2-aeed algorithm provides sublinear lenient and robust satisficing regret guarantees, assuming experiments show that both algorithms outperform robust optimization methods, particularly when the ambiguity set in RO is misestimated. Despite its promise, our framework has limitations. Selecting can be challenging without domain expertise, and the regret bounds for AdveRS-2 assume that achievable. Future work could focus on adaptive selection and applying the RS formulations to broader settings, such as distribution shifts and supervised learning. Additionally our framework focuses on the case with known adversarial perturbations. A promising future direction is to develop an RS approach in setting where the perturbations not observed. Another future direction would be to learn the parameter p in the RS-G formulation during algorithm run time.
achievable. Our
A Acknowledgements: This work was supported by the Scientific and Technological Research Council of Türkiye (TÜBÍTAK) under Grant 124E065: TÜBÍITAK 2024 Incentive Award; by the Turkish Academy of Sciences Distinguished Young Scientist Award Program (TÜBA-GEBIPP GEBIP-2023). Y. Cahit Yildurm was supported by Turk Telekom as part 5G and Beyond Joint Graduate Support Programme coordinated by Information and Communication Technologies Authority.
10

---

References
[1] Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
[2] Jia Wu, Xiu- Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperpa- rameter optimization for machine learning models based on Bayesian optimization. Journal of Electronic Science and Technology, 17(1):26-40, 40, 2019.
[3] Rémi Lam, Matthias Poloczek, Peter Frazier, and Karen E Willcox. Advances in Bayesian optimization with applications in aerospace engineering. In 2018 AIAA Non-Deterministic Approaches Conference, page 1656, 2018.
[4] Mahdi Imani and Seyede Fatemeh Ghoreishi. Bayesian optimization objective-based experi- mental design. In 2020 American Control Conference (ACC), pages
IEEE, 2020.
[5] Ahmed Alaa and Mihaela van der Schaar. Autoprognosis: Automated clinical prognostic modeling via Bayesian optimization with structured kernel learning. In International Conference on Machine Learning. pages 139-148. PMLR, 2018.
[6] Aharon Ben-Tal and Arkadi Nemirovski. Robust opimizzaion-mmchhodoooyy and applications. Mathematical Programming. 92:453-480, 2002.
[7] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint (ttd::990.05555 2019.
[8] Vishal Gupta. Management Science, 65(9):4242-42666 2019.
Near-optimal Bayesian ambiguity sets for distributionally robust optimization.
[9] Herbert A Simon. A behavioral model of rational choice. The Quarterly Journal of Economics, 69(1):99-118, 1955.
[10] Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Satisficing in multi- aallid bandit problems. IEEE Transactions on Automatic Control, 62(8):3788-3880 2016.
[11] Nadav Merlis and Shie Mannor. Lenient regret for multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8950-8957, 2021.
[12] Alihan Hüyük and Cem Tekin. Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning, (10(6))1233-11) 1266, 2021.
[13] Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Mathematics of Operations Research, 47(4):2815-2833 2022.
[14] 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. PMLR, 2021.
[15] 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, 41(2):209-227, 2011.
[16] Andreas L Mogensen and David Thorstad. Tough enough? Robust satisficing decision norm for long-term policy analysis. Synthese, 200(1))36, 2022.
[17] Daniel Zhuoyu Long, Melyyn Sim, and Minglong Zhou. Robust satisficing. Operations Research, 71(1):61-82, 2023.
[18] Zhiyuan Lou, Zhi Chen, Melvyn Sim, Jingui Xie, and Peng Xiong. Estimation and prediction procedures for unified robust decision models. Available at SSRN 4890089, 2024.
[19] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint 132.::1312.6199 2013.
[20] Shixiang Gu and Luca Rigazio. Towards deep neural network architectures robust to adversarial examples. arXiv preprint
2014.

---

[21] Ruben Cartinez-Canting Kevin Tee, and Michael McCourt. Practical Bayesian optimization in the presence of outliers. In International Conference on Artificial Intelligence and Statistics, pages 1722-1731. PMLR, 2018.
[22] Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. Advances in Neural Information Processing Systems, 31, 2018.
[23] Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1177-1184. PMLR, 2019.
[24] Lukas Fröhlich, Edgar Klenske, Julia Vinogradska, Christian Daniel, and Melanie Zeilinger. Noisy-input entropy search for efficient robust Bayesian optimization. In International Confer- ence on Artificial Intelligence and Statistics, pages 2262-2272. PMLR, 2020.
[25] Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett. Corruption-toles tolerant Gaussian process bandit optimization. In International Conference on Artificial Intelligence and Statistics, pages 1071-1081, PMLR, 2020.
[26] Iliaa Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett. A robust phased elimination algorithm for corruption -oolerant Gaussian process bandits. Advances in Neural Information Processing Systems, 15:23951-23964 2022.
[27] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 2174-2184. PMLR, 2020.
[28] Artun Saday, Y Cahit Yildırm, and Cem Tekin. Robust Bayesian satisficing. Advances in Neural Information Processing Systems, 36, 2024.
[29] Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. Advances in Neural Information Processing Systems, 13:20130-2011 2020.
[30] Quoe Phong Nguyen, Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Value-at- risk optimization with Gaussian processes. In International Conference on Machine Learning. pages 8063-8072. PMLR, 2021.
[31] Quoc Phong Nguyen, Zhongxiang Dai. Bryan Kian Hsiang Low, and Patrick Jaillet. Optimizing conditional value-at-risk of black-box functions. Advances in Neural Information Processing Systems, 111117044888 2021.
[32] Shogo Twazaki, Yu Inatsu, and Ichiro Takeuchi. Mean-variance analysis in Bayesian optimiza- tion under uncertainty. International Conference on Artificial Intelligence and Statistics, pages 973-981. PMLR, 2021.
[33] I. Steinwart and A. Christmann. Support Vector Machines. Information Science and Statistics. Springer New York, 2008
[34] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process op- timization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning, 2010.
[35] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, al. Wilds: A benchmark of wn-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
[36] Miriam Zacksenhouse, Simona Nemets, Mikhail Lebedev, and Miguel AL Nicolelis. Ro- bust satisficing linear regression: Performance/robustness trade-off and consistency criterion. Mechanical systems and signal processing, 1950:09944494 2009.
[37] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits, In International Conference Machine Learning, pages 844-853, PMLR, 2017.
12

---

[38] Christian Fiedler, Carsten W Scherer, and Sebastian Trimpe. Practical and rigorous uncertainty bounds for Gaussian process regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7439-7447 2021.
[39] 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. PMLR, 2021.
[40] 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.
[41] Thomas Danne, Moshe Phillip, Bruce A Buckingham, Przemyslawa Jarosz-Chobot, Banshi Saboo, Tatsuhiko Urakami, Tadej Battelino, Ragnar Hanas, and Ethel Codner. Ispad clinical practice consensus guidelines 2018: Insulin treatment in children and adolescents with diabetes. Pediatric Diabetes, 19:115 15 135, 2018.
[42] Chiara Zecchin, Andrea Facchinetti, Giovanni Sparacino, and Claudio Cobelli. How much is short-term glucose prediction in type diabetes improved by adding insulin delivery and meal content information to egm data? A proof-of-concept study. Journal of Diabetes Science and Technology, 10(5): 149-1160, 2016.
[43] Alonso Marco, Philipp Hennig, Jeannette Bohg. Stefan Schaal, and Sebastian Trimpe. Auto- matic lqr tuning based on Gaussian process global optimization. In 2016 IEEE International Conference Robotics and Automation (ICRA), pages 270-277. IEEE, 2016.
[44] Alonso Marco, Felix Berkenkamp, Philipp Henmig, Angela Schoellig. Andreas Krause, Stefan Schaal, and Sebastian Trimpe. Virtual vs. real: Trading off simulations and physical experiments reinforcement learning with Bayesian optimization. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 1557-1563. IEEE, 2017.
[45] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
[46] Daniel J Russo, Benjamin Van Roy, Abbas Kazeroumi, Ian Osband, Zheng Wen, et al. A tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 3 and 5 support the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
All assumptions are given in the main paper while proofs are kept in supple-
mentary document.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental setup is described detail in Section 5 to support repro- ducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We include our code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //iips.cc/pill wttpcccppppcccceeeeeeeeee..c.ett httaa//gggieee//eeuubbiissssssss /Cc////oddiiisssseeeeeee ssioiiliccyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Important details are mentioned in Section 5 while minor implementation details are visible in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are present where suitable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: used a modern computer with no special hardware for the experiments, as they do not require intensive computations. Therefore did not see it necessary to disclose our compute sources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://eerripssccppiiiiiieeeeee ptt i
Answer: [Yes]
Justification: Research conducted conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The authors does not foresee any societal impact of the conducted research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work is theoretical in nature and does not have foreseeable societal impact.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All copyrights are respected.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We did use LLM's for the core method development.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: ptttp:://neuris... http://erriis.ccoommeeereneeee/e cc/Coonferennces/2225LLLL for what should or should be described.
20

---

A
Table of Notations
Notation
Description
Action set
satisficing level (threshold)
d(...) X X X' + R
Distance metric on X'
A (2)
{r'- - xxx'' X and d(z,z') S c}, set of perturbations in e-ball
arg maX f(x)
Action selected by each algorithm Point sampled after perturbation, 3, + 6
de
Perturbation of the adversary round
True perturbation budget of the adversary at time t
max (u)
f(x(4)))
if f(x) 2
(x)
((2,+t8)
+0c
if <T
Kr
min My (x)
arg x Ny, (2)
maxseA= (x)10
T (2+d)
if ucbb(()) 2 if ucb:(()) <
Rra(()
d(x
to0
Ry,
minsex Kr,e( (x)
maxxsax (n/10
(xbb)
if lcb if lcb, <T
(x))
2(2,2+5)
+00
K
minzex Kr, (x) (x)
e (z)
max d(z, x') s,t. f(x + 8) 2 T, V8 E Ax(x)
x <
RS22
arg max,, Cr (x
(x))
max d(z, x') s.t. ucb, (x +
T, 4g E (x
maxsex (x,
(1))
eax d(r, x') 8.1. Icb, (x + 8)
2 T, A8 (x)
max Sr, (x)
Table 1: Table of notations
B Unified Formulation RS-G
The p-fragility (x) of action r E X' is
Kr.p (x) min s.t. f(x + 2 [kd((r, 5)}", Vg Az)
This means the RS-G action RRG gives the reward guarantee of f 2 [nr RS-G .2BS.GG ")}" When 1. this guaratee is a linear cone facing downward from T. at the choosen point. Since the p-fragility is is the minimum that satisfies this inequality, this means the guarantee the z action can be represented by the widest cone drawn from т. When 2, instead of linear cone, the guarantee takes quadratic form and so on. We generalize the notion of cone for all p and define the fragility-cone of an action z' E X' as the following function: Cone (x) := 7 ((r,pd(a' x))P Then we can say that the solution RSSG which minimizes fi,,p, is the solution that maximizes the wideness of the fragility-cone, as Ky,p controls how wide the cone is. Figure D gives a visual representation of RS-1, RS-2 and RS-G with p 2 solutions, and their respective fragility-cones. Which formulation should be used depends on the structure of the problem and the goal of the optimizer. If, for example large perturbations are considered unlikely, RS-G with larger p might be better suited.
21

---

C Proofs
C.1 Proof of Lemma 3.2
Assume the good event & holds. Consider the first inequality Ry, ,,) S kz)x). When (x)((x) 0c, then Kyr (z)
well. When (x) oo and Ny (x) co, the inequality holds. Let dz,t == arg max (x+6)(
d(2,zt0) Les == arg max (w){0 d(c,ato)
(z and
det == arg maxsEA= (w)) a(1,era8
T=(())) When (r), k,,,,,(x)))) < 0o we have
ucbi + =g,1)
T- f(x + dr,1)
(x) - Rer (x)
d(x, x + )2,1)
d(x, x + Ōmst)
T ucbi( + )n.t)
T T- [(x + dm,))
d(x, 62,()
d(x, + dw
f(x + 52,() ucbi(æ + 8g,e)
d(x, + 0z,1)
00.
Similarly for Kr (x) S (x,e(x) we have
f(x: + 6z,1)
T lcb, + s,,t))
(+,((x) - (x)
d(r, x + 61,1)
d(r, x + ),,1)
x -- f(x + 62,1)
T lcb,(x + )2
d(r, x + 6r,1)
d(r, 02,t)
lcb(æ + 82,1) f(x + 82,e)
d(x, + 8z,1)
0..
C.2 Proof of Lemma 3.4
Assume the good event & holds. Consider the inequality (x) S (x,()).. (ace(r))Assuun Assume that this inequality false for some x, then 38 s.t. 8 A (2) and 5 & (x, since (x),()) (x)
(z)(x)
and f( + 5) 2 r > ucb, (a + 5). which is contradiction. Similarly assume (x) S (x) is
false for some x. Then 38 s.t. 8 (+),()) and 8 & (z) since (e, (x) C (z)
and (x + 6) 2 r > (( + 8), which is a contradiction. Therefore Lemma 3.4 is true.
C.3 Proof of Theorem 3.6
Lenient Regret Bound of AdveRS-1 The regret bound of AdveRS-1 follows a similar structure to the bound in (28) but instead of the MMD metric, we utilize the Lipschitz continuity of f. Define the instantaneous regret at round as rf := f(z + 5.). The cumulative regret Rt = EE= (r+)+. Assume that the good event & holds. Then the instantaneous regret can be bounded as
N = - [(ē, + 5,) S r - ucb,(ā, + 6,) + 2,, + 6,)
(11)
the adversary does not perturb the action, i.e., 6, = 0, then we have S ucb, (5.) + 2,, (5:)
by Assumption 2.2 and the selection rule of the algorithm we have (..) 2 T, hence
r < 23,0,
231))(zt).
If 8, o 0, continuing from 11
< - ulbuub, (ū, + 6.) + 2,3 + de)
(12)
< d(ār, T. + 6.) T - ucb, (ā+ + 6t) + 28,0, + 8n) d d(,,, + 5z)
(13)
5 d(Ør, 3, + 6,) (6x) 2, (i: + 6,)
(14)
< d(z,, 2, + 5, (8) + 2,,0 (3, + 5,)
(15)
22

---

Define 82,1 == arg max x
Then we can write above as,
ucba ( + ōg.e)
=(ā tt +6))
+ 28r
(16)
d(ž, )3,1)
f()) ((t)--(i- + 85.1)
S dd(i,, 34 + 6c)
+ 2 + 6.)
(17)
d(e, à 62,1)
S dd(Er, + 6.) Bd( a 02,1)
+ 23, 0b)
(18)
d(ē dg,t)
S 2 6.) + Be, (3) Bec
(19)
comes from the definition and (5) follows from H, being the minimizer of (x)) follows from Assumption 2.2 and the confidence bounds. Finally (88) follows from the Lipschitz continuity of f with respect to the kernel metric d, and (19) from ([ + 6t) S cz. From this point on, we bound the lenient regret by following standard steps for bounding regret of GP bandits. First
(77
note that since (9) is nonnegative, it is also a bound for (rl)+. By plugging this upper bound to 6 and using monotonicity of 3r, we obtain
T
Fy S 23r
Σ
+BY 4
(20)
1=1
1=1
28T
T
ce(2) + B
Σ 6
(21)
where 21 uses the Cauchy-Sehie Sacchy-Schwartzii inequality. Next, to relate the sum of variances that appears in to the maximum information gain, we use a log(1 + a) for all [0, to obtain
Σ (x))))²
2 log([ + (2x))
1=1
< 4YT,
(22)
where 22 follows from
37 Lemma 3]. Putting
22 in the regret definition we get the final bound
B2 S 43T V TTT + B Σ c
Robust Satisficing Regret Bound of AdveRS-1 Define the instantaneous regret round / as r
(r(t)+. Kr fāa + 5z). The cumulative regret is R... (r Assume that the good
event & holds. Then the instantancous regret can be bounded as
r < r - Kt - ucb, (ā+ + (5, ( 6.)
(23)
< Ky - (r Kr,
+,) 23, (āx 6c)
(24)
< T - KG - (r (-- (x)))) + 23,0; 6,)
(25)
(K kr) + 2,,,0 + +
(26)
< 23ror(Te + +6) = (3x
(27)
24
follows from the guarantee of the RS formulation ucb, (8, + 5) 7 - d 3. + 8) for
any 8 (x,))) (ā.). (27) follows from Fy, < Ky,t since ucb, (x) 2 f(x) for all x. Then bound
the cumulative robust satisficing regret, following the same standard steps as in the proof of the cumulative lenient regret bound, obtain upper bound of:
R 43T TTT.
23

---

C.4 Proof of Theorem 3.10
Under the good event &, Assumption 2.2 and Assumption 3.8 we can bound the lenient regret of AdveRS-2 as:
1 f(tz
6t) min ucb, (it + +6 - f0x + 6t)
(28)
(29)
de de (5x)
min ucb,(Tr + 6) fā; + 6z) (5.)
(30)
min ucbi + 6) f(āx + 6t)
(31)
(ā..,
ucbi( + +d) ʃ(ā; + 5t)
(32)
(33)
Note that from Assumption 2.2 under & we have ucb, (+) 2 r which means (+,( 2 0. Then by definition, for any 8 E A (e). ucb, (3: + 6,) 2 T, which gives (29 30) is true because C, (2-2() by Lemma 3.4 and 2, (x, RS-2)
S 7 by the equation (8) Hence A, (ā₂) S A., (.))
Similarly, (3T) follows from Assumption
3.8 For (32). observe that 6, E A., (fz). no matter the
attacking strategy of the adversary. Finally
33 holds under the good event &. The rest of the proof is
the same as the previous ones. Noting that R
< Rl by definition, and hence shares the same upper
bound completes the proof of Theorem 3.10
C.5 Proof of Corollary 3.3
By the definition of (z). we have lc, 2 that under & f(x) 2 leb:(x) Va E X, we obtain the first inequality. For the second inequality observe that from the definition of (xx( we know that 38' E (ā,) such that ucb, (7: + 8') ( T. 8'). Noting that f(x) S ucb:(x)) for all under & concludes the proof.
AS E (ā;). Noting
C.6 Proof of Corollary 3.5
By Lemma 3.4 we have A.,, (Tx) C (īx), then for any d A.,, (Zx), we have f(ā, + 8) >
lcb;(;; 8) under the selection rule and the good event & Conversely again by Lemma 3.4
have A., (#t) S Az,, (.t). Assuming X' continuous, 38' E A,, such that f(ū; + 8') = т. Noting
that 8' E Az,, completes the proof.
C.7 Proof of Proposition 3.7
Consider the following instance of our problem. Let X [0, 1] and f(x) = x, noting that this an element of RKHS with a linear kernel. The Lipschitz constant of this function is 1. Let the satisficing goal v = which the function maximum. e, < 1, no matter what action chosen by the learner, the adversary can choose perturbation 6, -; to obtain reward f(x, + 6,)
Eg, making the instantancous lenient regret (r f + 5z))* 2 e, This constitute a worst case lower bound, hence the bound is tight and the linear penalty term is not avoidable in general.
C.8 Proof of Proposition 4.1
WLOG assume that 36 e (x) such that f(x+0) S Let {6 (x < Notice that (10) is then equivalent to
(x) == min k s.t. f(x + 6) T [kd(,,==))) V8 (x)))
since for any d & A (z), the inequality constraint already holds for any k 0.
Then write the equivalent formulation for action that satisfies f(z) 2
J - f(x + 1/D
(x) = sup (E)
d(x, 8)
24

---

As - oc, note that for each fixed x and & E A'(x), -T- f(z 8)) 4 monotonically. Hence, by monotone convergence,
T- + 8)1
(x)
sup (E)((2)
sup (E)) d( +
d(z, x +0)
min (=)
d(z, + 6) (
pr,p
Since (x) decreases pointwise to 1/E, (z) for all tion by uniform convergence:
exchange the limit and the minimiza-
lim min (x)p(() min lim (x)p(()
min #EX (x)2)
max = =x = RS-2 #E
ZeR
zEX p-000
C.9 Proof of Corollary 4.2
The proof is almost identical to the RS regret proof for AdveRS-1, we include it for completeness. Define the instantancous regret round t r 7 [N / f(,, + +o). The cumulative regret
R7 ΣT_ (r Assume that the good event & holds. Then the instantaneous regret can be bounded as
r v r [NSee] - ucb, (++ + 5,) ( + 62)
(34)
[ u (r ( 8, + 5:)1 + 23: +6)
(35)
< T [K - (T PR (f:) (0, 6,)
(36)
of (R.rpp. - x))) + 23,0, (ā. 6.)
(37)
- 23,0r + 6.) = 23)0)
(38)
(35) follows from the guarantee of the RS-G formulation (āz + 2 p + 6)]²
for any E (++) (37 follows from KT,p. S Kr,p.t since ucb, (x) 2 f(x) for all x. Then we bound the cumulative robust satisficing regret, following the same standard steps obtain upper bound of:
R S TTT
D Implementation details of the algorithms
We note that maximizing UCB and LCB over compact domain is non-trivial due to the non- convex nature of the posterior mean and variance. Like foundational works (e.g., (34), we focus on theoretical guarantees and assume an oracle optimizer, abstracting computational details. This challenge common across all GP-based methods, including the RO algorithms we compare against, and in practical BO, various optimization (e.g., gradient descent or -ewatn) techniques are used to address it.
In our experiments, we work with discretized domains and the implementation of the acquisition functions of our algorithms have complexity ((V3) where N |X Notably, this complexity the same as that of RO-based algorithms. Specifically, in all algorithms that we implement (RS or RO based), action-speeee sppccifcc calculations are performed an inner loop, while an outer loop used the selection of best action.
E
Additional Experimental Results
F.1
Inverted Pendulum Experiment
In this experiment, we focus on optimizing parameterized controller to achieve robust performance in controlling an inverted pendulum. The state vector 8ş consists of four variables: cart position, pendulum angle, and their derivatives. The simulation is conducted using OpenAl's Gym environment.
25

---

Random Attack
LCB Attock
Werst Case Atiads
Lruen Boget
Letken Ieegntt
2.0
pimoe (RS-))
Leukest Rogert
BS-G, 2
BD mis
30
04
100
590
203
150
230
123
100
200
253
Bouzd
Rouad
LCB
1.90
000
BSS.I. (RS-9)
68 Boggs
1.30
RS-C, 2
0.75
0.30
RD
RD UL
RD
40
14.0
0030
100 100
300
103
200
60
130
253
Boand:
Roand
Round
Figure 7: Lenient and RS regret results of the inverted pendulum experiment. Perturbation budget is = 2.5 and r = 0 for all t. STABLEOPT run with: éx, 3e,, and r 0.3ez, Attack schemes are indicated in the supertitles.
The system dynamics are described by 8k-1 = h(8) ux), where 8& is the 4-dimensional state vector, and ug [-10, 10] is the control action representing the voltage applied to the controller step k. We implement& a static feedback controller similar to the one in [43]. defined as Fsy. where F 1 is the gain matrix. We structure F Linear Quadratic Regulator (LQR) using the linearized system dynamics (A, B) around the equilibrium point. The parameterization, which has been shown be learnable by GP's [3 is given by F dlqr( A, B, W. (0), W (0)) with the following parameterization:
W. (0) = diag ( 10,00.00000
1,2,3 E [-3,2].
W. (0) = 10
04 E [1.5].
We discretize the parameter space into 4096 points and compute the cost for each parameter by simulating it over 2000 seconds, using the same cost function as in [44]. After the simulation, the cost function standardized and clipped the range [-2. For the GP kernel, we use Radial Basis Function (RBF) kernel with Automatic Relevance Determination (ARD), with hyperparameters selected using 400 samples prior the experiment.
For adversarial perturbations, we consider an adversary that damages the learning process by perturb- ing the selected parameter. The unknown perturbation budget is constant with e; The satisficing goal is set to = which corresponds to ~ 25 percentile of the objective function. Figure 7 shows the regrets of the algorithms over time horizon of T 250. AdveRS family of algorithms matches the STABLEOPT that has the perfect knowledge of the adversarial budget, and they outperform STABLEOPT otherwise. While AdveRS-1 achieves linear regret, can still perform better than STABLEOPT when the perturbation budget is misspecified.
E.2 Misspecified Kernel
In this experiment, we evaluate the performance of our algorithms when the GP is run with a kernel that is not aligned with the true function. Specifically, we use the function shown in Figure 2 but unlike Experiment 1, we replace the polynomial kernel with an RBF kernel, using lengthscale of 0.1 and variance of 10. All algorithms are run with the same parameters in Experiment I with - 10 and = 0.5. F shows that AdveRS-2 maintains strong performance even when the kernel misspecified,, while AdveRS-1 outperforms STABLEOPT when the ambiguity ball not correctly estimated. Figure shows the RS regrets and we see that our algorithms achieve sublinear results, while STABLEOPT with misspecified ambiguity radius can achieve linear RS regret. All plots show the mean results over 100 independent runs with error bars showing std/2.
26

---

Random Atark
LCB Attadi
Woest Cuse Attack
1030
Lruie Reget
p (RS-2)
Letkes Rogeet
1230
B5-4, x.
1230
200
RD
RD
Dig
110
42
130
Round
Round
Round
Figure 8: Lenient regret results for synthetic experiment using misspecified kernel, with a per- turbation budget of 6z 0.5 and r = -10 for all t. STABLEOPT run with: r = 6t, = 4et, and 0.5c
Rarriken Attack
LCB Attack
Wirsi Chao Attack
530
558 Bogns
120
88 Dezpes
0-
Round
Figure 9: Robust satisficing regret results for synthetic experiment using misspecified kernel, with perturbation budget of ez 0.5 and 10 for all t. STABLEOPT run with: r = 6t, r 4e,, and 0.5c,
E.3 Robust Satisficing with Thompson sampling
Thompson Sampling. Thompson sampling from the GP posterior and then choosing
45 46
selects the next point by sampling function
E arg max f(x). SEA
2t
This randomized policy implicitly balances exploration and exploitation by occasionally sampling from regions of high uncertainty.
Algorithm 3 AdveRS-G-TS
1: Input: Kernel function k. X, r, p. time horizon
2: Initialize: D, 0 (empty dataset), and (z(x)) 0, oo(x) Vo X
3: for l 1 to T do
4: Sample [x(x))
1
Vor X
5: Compute p.,,, (z) using (39
Vx X
6:
Select &N = arg mingex K
7:
Adversary selects perturbation ó Ae, (it)
8:
Sample 2; = 5, + 5G, observe y1 = f (xt) + 17p
9:
D. = D.-1 U ((),)))))
10: Update GP posterior using 5
11:
end for
Algorithm for RS-G using Thompson sampling. In order perform Bayesian optimization with the objective as RS-G, building on the algorithm family of AdveRS, we propose Adversarially Robust Satisficing-Genen General-
Sampling (AdveRS-G-TS) algorithm (see Algorithm 33)
At the beginning of each round I, AdveRS-G-TS samples random representative fe from the posterior distribution of GP. Then, replacing the f in (10) instead with fo and rearranging in it
27

---

computes the Thompson p-fragility defined as:
1/8 +
T f- + o0) d(z, +
[T.,,(() =
max
(39)
bEAx (x))0
if f((x) 2 r, and otherwise p. co. For each action, the Thompson p-fragility p. (a) provides random sample of the true fragility (z),(z)) smallest random fragility, म, = arg min Fr,, to guide exploration and exploitation.
then selects the action with
Insulin dosage experiment using AdveRS-G-TS
B54
BSC
DO 1.
BO
Loains
10
Roual
Boxad
Figure 10: Lenient and RS regret results of insulin dosage experiment. Note that the results for algorithms other than AdveRS-G-V G-TS are the same in an]0aand are averaged over 100 random runs, while AdveRS-G-TS results are averaged over runs.
E.4 Effect of and r
Table shows the varying effects of the parameters. The lenient regret of all algorithms calculated on the synthetic function from Experiment 1. The perturbations are sampled i.i.d. from normal distribution (00, 0.3²). For this experiment, report results from 20 random runs. Results show that the target oriented nature of RS approaches makes them better suited for the satisficing objective under unknown perturbations.
Alg. AT
-30.00
-00.00
-10.00
0.00
10.00
RSI
103.83
201.97
287.81
651.38
1478.62
RS2
47.09
104.01
185.39
434.30
626.48
RSG
52.70
113.03
177.90
619.17
1505.98
RO, 10.10
112.29
207.81
335.10
458.96
645.07
RO, r0.57
94.20
180.79
293.17
537.80
1489.18
RO. 1=1.05
74.30
138.19
224.45
723.06
1695.44
RO, 1=1.52
55.05
126.99
258.48
1053.13
2121.94
RO, r=2.00 60.05
284.83
722.58
1523.14
2721.97
Table 2: Average lenient regrets for synthetic experiment for RS-1, RS-2 and RO algorithms with varying 7 and values. Best values are in bold for each value.
28


Reviews:
[{"review_id": "P5AI7TrY59", "reviewer": "Reviewer_wsUa", "summary": "This paper tackles GP optimization with unknown adversarial perturbations by replacing the ambiguity set based RO with an RS framework. The authors propose two algorithms AdveRS-1 and AdveRS-2, corresponding to RS formulations RS-1 and RS-2 based on fragility and critical radius, respectively. They also provide a unified framework controlled by a power parameter. They show that AdveRS-1 delivers a linear lenient regret bound and a sublinear robust satisficing regret, while AdveRS-2 attains sublinear bounds for both with an attainable threshold assumption. Experiments demonstrate that RS-based methods outperform standard RO, particularly when the ambiguity set is misspecified.", "questions": "- In all experiments, the satisficing threshold is set to -10. Can the authors justify this choice, and offer guidance on how it should relate to the problem’s reward scale?\n- I understand selection of the power $p$ is proposed as future work in the Conclusion, but do the authors have any concrete strategies or preliminary results on how to tune $p$ as a hyperparameter or choosing adaptively at runtime?\n- Could the authors include a more detailed discussion of computational cost, possibly both in terms of theoretical complexity and empirical runtime?", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well written and thoughtfully structured.\n- Each framework and its corresponding proposed algorithm are presented clearly and concisely, with intuitive explanations of when and why they work.\n- The assumptions required to improve the theoretical bounds are explicitly stated and seem reasonable.\n- Experiments demonstrate meaningful improvements over standard RO baselines and clearly illustrate in which regimes each RS method excels.\n\nWeaknesses\n- Guidance on selecting the satisficing threshold is limited. Although as the authors continuosly mention, domain-specific tuning is expected, practical heuristics or rules of thumb are missing. Since performance hinges on whether the threshold is attainable, for fair comparison against RO with misspecified ambiguity set, additional sensitivity analyses especially would strengthen the paper.\n\nOverall, I believe it is a well-written paper that introduces a strong framework and methodology and effectively highlights its advantages.", "was_revised": true, "final_justification": "I advocate the acceptance of this paper, and I am keeping my score on 5 (accept).", "rebuttal": "Dear Reviewer wsUa,\n\nThank you for your feedback. We're grateful for your acknowledgement of the value of our work. Below, we respond to each comment in detail.\n\n**Weaknesses:** We include an additional sensitivity analyses in the supplementary PDF Section E.4, where we compared the effects of changing $\\tau$ and the ambiguity ball radius $r$ (for RO based methods) on the lenient regret.\n\n**Questions:**\n- (... satisficing threshold ...) For the insulin dosage experiment, we use a safe range of the PBG level as $[K-10, K+10]$ mg/dL (i.e. $-|f(x) - K| \\geq -10$), where $K$ represents the PBG target (e.g., set by a clinician). We set $K=110$ which is a rounded approximation of the clinical center of the BG scale $112.5$ mg/dL mentioned in reputable resources in diabetes management [A], [B], that can be regarded as the \"safest value\". We set $\\tau=-10$ for simplicity as it is known that the range [100, 120] mg/dL resides within well-established target PBG ranges stated in clinical guidelines (e.g., [C]). In practice, both $K$ and $\\tau$ would be selected by a clinician using domain expertise and clinical assessment of the patient. For the synthetic function, we again set $\\tau = -10$, a round value chosen so that behavioral differences of formulations are clearly conveyed. The coincidence has no further significance. We also present an additional experiment in supplementary PDF Section E.1 (parameterized controller selection for an inverted pendulum) that uses $\\tau = 0$. In general, $\\tau$ should be selected by considering the function maximum and the reward scale, which requires domain expertise in most cases. We highlight that still, in most cases choosing $\\tau$ would be more straightforward for the domain expert, in comparison to choosing the ambiguity radius $r$ for the RO approach. \n\n    [A] Kovatchev, Boris P., et al. \"Symmetrization of the blood glucose measurement scale and its applications.\" Diabetes Care 20.11 (1997): 1655-1658.\n\n    [B] Kovatchev, Boris P., et al. \"Algorithmic evaluation of metabolic control and risk of severe hypoglycemia in type 1 and type 2 diabetes using self-monitoring blood glucose data.\" Diabetes Technology \\& Therapeutics 5.5 (2003): 817-828.\n\n    [C] American Diabetes Association. \"6. Glycemic targets: standards of medical care in diabetes-2021.\" Diabetes Care 44.Suppl 1 (2021): S73-S84.\n\n- (... selection of the power $p$ ...) The key insight we have of $p$ is that, lower $p$ values give higher importance on the effect of larger perturbations, while higher $p$ values give more importance to the effect of small perturbations. Selection of $p$, thus, depends on the behaviour of the function at the global scale considered together with the nature of the adversary. This suggests that a possible heuristic would be to dynamically adapt $p$ based on the posterior distribution of the GP and distribution of the perturbations of the adversary. However, this may require further assumptions on the nature of the unknown function and behaviour of the adversary.\n\n- (... run time ...) In Section D of the supplementary material we include a discussion about the implementations of the algorithms. In our experiments we worked with discretized domains and the implementation of the acquisition functions of our algorithms have complexity ${\\cal O} (N^2)$ where $N = |{\\cal X}|$. Notably, this complexity is the same as that of RO-based algorithms.\n\n    To provide an empirical runtime comparison, we ran the insulin dosage experiment again. On our server, while RS-1, RS-2 and RO with $r = 3\\cdot\\sigma_s$ runs in 173 seconds, RO with $r = \\sigma_s$ and RO with $r = \\sigma_s / 3$ runs in 172 seconds. This matches our general observation that the runtimes can be considered practically equivalent."}, {"review_id": "Lc7Ml4P5xl", "reviewer": "Reviewer_X7S6", "summary": "This paper aims to solve the robust satisficing problem under adversarial attack. The authors first define two different formulations: RS1 and RS2, and extends the UCB/LCB to the corresponding optimistic/pessimistic bounds, followed by a unified algorithm.", "questions": "1. Could you provide some real-world cases for the RS1 and RS2 formulations?\n2. In the experiment, what if the attacker always return the same perturbed point within a budget? Will this attack affect the performance?\n3. Can the critical radius/action fragility extend to other existing acquicition functions, e.g., EI or PI?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strength\n1. In general, this paper is well-presented and easy to follow.\n2. The robust satisficing problem can be quite important and applicable to many real-world cases.\n3. Solid experiment.\n\n### Weakness\n- In the current setting, the authors assume the learner can explicitly observe the perturbed point $x_t$ (Line 89) and develop their algorithm based on this assumption. However, this could be infeasible for many real-world cases. As pointed out in [1,2] the perturbed value cannot be observed. \n- Also, if the pertubed value is explicitly observed, it is straightforward to learn a GP without any ambiguity, making the decision much easier.\n- The key design of acquisition function, i.e., the extensions of UCB/LCB to optimistic/pessimistic fragility, as well as the optimistic critical radius, are quite intuitive.\n\n[1] Yang et al., \"Efficient robust Bayesian optimization for arbitrary uncertain inputs\", NeurIPS 2023\n\n[2] Oliveira et al., \"Bayesian optimisation under uncertain inputs\", AISTATS 2019", "was_revised": true, "final_justification": "The authors' rebuttal addresses most of my concerns, especially about the information the learner can observe. Therefore, I will increase my score to 4 (borderline accept)", "rebuttal": "Dear Reviewer X7S6,\n\nThank you for your feedback. We greatly appreciate your acknowledgement of the strengths of our work and your thoughtful criticisms. Below, we respond to each comment in detail. If you have any further questions, we are eager to engage in a more detailed discussion.\n\n\n**Weakness:**\n\nAs the reviewer highlights, there is work on GP's where the inputs are not directly observed. [1] incorporates input uncertainty into the posterior using an MMD based method, and [2] (reference no 23 in the paper) defines a GP over probability distributions. To account for input uncertainty in the surrogate model, however, both approaches rely on additional assumptions about the nature of perturbations. In particular, both [1] and [2] assume that perturbations follow a distribution. Further, [1] requires that the learner can sample from the perturbation distribution, whereas [2] assumes access to a reference distribution that approximates the true query location.\nIn our setting, no such assumptions are made, making the uncertain input formulation inherently more challenging. Even if the adversary samples the perturbation from a distribution, they may change this distribution from round to round. Without additional constraints on the adversary, it's not possible to reliably estimate the perturbation distribution, and construct an uncertainty aware surrogate model. That being said, after introducing additional assumptions about the adversary's behaviour, we believe our robust satisficing framework could be extended to explicitly account for input uncertainty, which would make an interesting direction for future research. We appreciate the reviewer pointing out this related line of work. We will discuss its relation to our work in detail in the revised paper.\n\n\n**Questions:**\n\n- (...real-world cases for RS...) Apart from the insulin dosage experiment in the paper, both RS-1 and RS-2, as well as RS-G, can be readily applied to many real-world problems where RO is already used. Some examples include:\n    - The real-world robot control tasks given in [1] and [2] fit into our model with a slight environmental twist. Consider the scenario (for example in space missions) where the communication with the robot is discrete. An autonomous drone is sent to location $x_t$ to perform a measurement task, but due to fuzzy control or environmental necessities, ends up at location $\\tilde{x}_t$. The robot can share $\\tilde{x}_t$ along with the measurement it took when the communication is available (e.g. at the base).\n    - One recent promising use of RO (DRO in particular) is for preference alignment in LLM's [A]. The authors tackle the problem of distribution shifts due to synthetic data in LLM preference alignment using a DRO based method. One challenge which the authors mention in the paper is that DRO can suffer from over-pessimism, which manifests as poor generalization. An RS based approach can possibly be a strong alternative and a promising future research avenue.\n    \n    Apart from these, portfolio optimization and inventory and supply chain management are among the domains where RO has been extensively studied [B]. Both RO and RS have also been used in Markov decision processes (MDPs) with uncertainty present [C, D, E]. Further, [F] presents several examples where RS-1 can be used, such as portfolio optimization and the knapsack problem.\n\n    [A] Zhu, Mingye, et al. \"Leveraging Robust Optimization for LLM Alignment under Distribution Shifts.\" arXiv preprint arXiv:2504.05831 (2025).\n\n    [B] Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464–501, 2011.\n\n    [C] Huan Xu and Shie Mannor. Distributionally robust markov decision processes. Advances in Neural Information Processing Systems, 23, 2010.\n\n    [D] Xiaoting Ji, Yifeng Niu, and Lincheng Shen. Robust satisficing decision making for unmanned aerial vehicle complex missions under severe uncertainty. PloS one, 11(11):e0166448, 2016.\n\n    [E] Haolin Ruan, Siyu Zhou, Zhi Chen, and Chin Pang Ho. Robust satisficing mdps. In International Conference on Machine Learning, pages 29232–29258. PMLR, 2023.\n\n    [F] Daniel Zhuoyu Long, Melvyn Sim, and Minglong Zhou. Robust satisficing. Operations Research, 71(1):61–82, 2023.\n\n- (...return same perturbed point...) The point attacker returns depends on both the perturbation budget of the attacker, and the point chosen by the learner. In general, the adversary woul not be able to return the same perturbed point for every point the learner chooses due to budget limit. If the attacker can force the same point no matter what point the learner choose, this means the adversary is too strong and, indeed, learning the objective function is impossible.\nHowever, we underscore that our results do not depend on the attacking scheme of the adversary.\n- (...extend to other acquisition functions...) While extending the notion of critical radius and the fragility to EI or PI would not be straightforward, they can be more readily adapted to other known acquisition functions. For instance, rather than employing an upper confidence bound (UCB) strategy, one could utilize Thompson Sampling to estimate the fragility and critical radius of each action by drawing sample functions from the Gaussian process (GP) posterior. We explored this alternative and obtained encouraging preliminary results. In particular, we extended and reran the insulin dosage experiment presented in the paper to include Thompson Sampling variants of RS-1 and RS-2, denoted RS1T and RS2T, respectively. Below, you can see the lenient regrets across timesteps as a table. As in the main experiments, the results are averaged over 100 runs, with error bars indicating half the standard deviation (std/2). The results show that lenient regret of TS-based RS algorithms are very similar to that of AdveRS-1 and AdverS-2.\n\n    | Algorithm               | t=100        | t=200        | t=300        | t=400        | t=500        |\n    |-------------------------|--------------|--------------|--------------|--------------|--------------|\n    | RS1                     | 25.27 ± 2.06 | 36.38 ± 2.85 | 46.19 ± 3.67 | 54.24 ± 4.35 | 62.35 ± 4.55 |\n    | RS1T                    | 20.59 ± 2.07 | 33.18 ± 2.84 | 43.52 ± 3.37 | 53.05 ± 4.34 | 62.35 ± 4.95 |\n    | RS2                     | 22.83 ± 2.10 | 34.69 ± 2.65 | 44.00 ± 2.96 | 52.69 ± 3.62 | 61.41 ± 4.24 |\n    | RS2T                    | 20.93 ± 2.51 | 34.43 ± 3.17 | 45.54 ± 3.73 | 55.47 ± 4.24 | 65.64 ± 4.76 |\n    | RO $r=\\sigma_s$         | 16.96 ± 2.06 | 29.34 ± 2.72 | 40.79 ± 3.46 | 51.47 ± 4.07 | 62.50 ± 4.67 |\n    | RO $r=\\sigma_s / 3$     | 20.28 ± 2.23 | 36.74 ± 3.12 | 51.59 ± 3.76 | 66.26 ± 4.61 | 81.27 ± 4.93 |\n    | RO $r=3 \\cdot \\sigma_s$ | 24.95 ± 2.28 | 42.42 ± 3.47 | 57.98 ± 4.26 | 71.93 ± 4.44 | 86.17 ± 5.44 |"}, {"review_id": "reDVaNsvXO", "reviewer": "Reviewer_SL7m", "summary": "This paper proposes a Bayesian optimization method for efficiently identifying robust solutions under adversarial perturbations in the optimization problem of expensive-to-evaluate black-box functions. Representative robustness measures such as worst-case measures have the problem of selecting overly conservative solutions depending on the parameters that determine the range of perturbations. In contrast, this paper considers robust satisficing, a moderate robustness measure. First, two definitions of robust satisficing, RS-1 and RS-2, are given. RS-1 is defined as the minimum value of slope at which the threshold can be reduced in linear order according to the magnitude of the perturbation, while RS-2 is defined as the maximum magnitude of the perturbation that causes the threshold to be violated. Furthermore, by generalizing the linearity in RS-1, the authors propose RS-G, a general robust satisficing that connects RS-1 and RS-2. In the proposed method, an acquisition function based on GP-UCB is given for decision-making, and theoretical bounds for two types of regrets, $R^l_T$ and $R^{rs}_T$, are provided. Due to the presence of adversaries, the standard regret $R^l_T$ is not sublinear, while the proposed method achieves a sublinear regret bound for $R^{rs}_T$, which accounts for the degree of perturbation. Numerical experiments are conducted to compare the performance with comparison methods.", "questions": "This paper is well written. I believe that Weaknesses 2 and 3 are issues for future consideration and do not diminish the value of this paper. However, Weakness 1 requires further explanation. Furthermore, the content of this paper can be improved by clarifying the following unclear points:\n\n1. Among the various robustness measures, what are the advantages of robust satisficing? Existing studies [30] and [31] consider VaR and CVaR, which are threshold-based robustness measures. Additionally, PTR is also a threshold-based measure, as it represents the probability of exceeding the threshold, and thus resembles the robustness measures discussed in this paper. Additionally, distributionally robust measure [27] is an intermediate robustness measure between worst-case and expectation measures. Considering these points, a detailed explanation of the specific advantages of robust satisficing is necessary.\n\n2. Can the RKHS assumption be changed? As in the continuous setting of Srinivas et al. [34], if we assume probabilistic Lipschitz continuity as in Theorem 2 of [34], and normality of the observation noise, it seems possible to adapt the Bayesian setting. \n\n3. Can this method be applied in a situation where only $\\tilde{x}_t$ is known, and the values of the adversarial perturbations $\\delta_t$ and the actual inputs $x_t$ are unknown? Is there any possibility of extending this method to such a setting?\n\n4. In the footnote on page 3, it is stated that Lipschitz continuity is not necessarily required for $f$, but in line 230, Lipschitz continuity is used. Is Lipschitz continuity ultimately required?\n\n5. In equation (2), is $k$ allowed to take negative values?", "limitations": "Yes. These are stated in Conclusion. However, in my understanding, this paper assumes that the values of the adversarial perturbations and the exact inputs after perturbation are known. Therefore, I believe that the limitation should also include the fact that the paper does not address cases where the values of the adversarial perturbations are unknown. On the other hand, the main focus of this paper is the development of a methodological framework and theoretical analysis for Bayesian optimization of robustness measure under adversarial perturbations, so it does not fall under the category of potential negative social impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The strengths of this paper are as follows:\n\n1. It deals with Bayesian optimization problems under adversarial perturbations using RS-1, RS-2, and their generalizations, RS-G, which are robustness measures that are not overly conservative.\n\n2. The authors designed an acquisition function based on GP-UCB and demonstrated that a theoretically sub-linear regret bound can be achieved for regret that accounts for the influence of perturbations, even under adversarial perturbations.\n\n3. Numerical experiments compare the robustness of the proposed method with existing methods under various perturbation conditions, demonstrating its effectiveness.\n\nOn the other hand, the weaknesses of this paper are as follows:\n\n1. The comparison with related robustness measures is insufficient. The distributionally robust measure [27] is also moderate robustness measure. Furthermore, while RS-1, RS-2 and RS-G are threshold-based robustness measures, value-at-risk (VaR) [30], conditional VaR (CVaR) [31], and probability threshold robustness measures (PTR), $PTR= \\mathbb{P} _{\\delta} ( f( x + \\delta ) > \\tau)$, are also  threshold-based measures. It is necessary to explain these characteristics and the differences from the proposed method in more detail.\n\n(PTR): Iwazaki et al., Bayesian Quadrature Optimization for Probability Threshold Robustness Measure, Neural Computation 33 (12), 2021 \n\n2. The robustness of robust satisficing strongly depends on the given threshold $\\tau$. As mentioned in  Conclusion, depending on the value of $\\tau$, overly conservative or optimistic solutions may be obtained, and the problem remains of how to deal with situations where domain knowledge is insufficient and it is not possible to design a reasonable $\\tau$. \n\n3. The value of the adversarial perturbation is assumed to be known. In the proposed method, the surrogate model is calculated using $(x_t,y_t)$ under the assumption that the value of the perturbation $\\delta_t$ given by the adversary and the value of $x_t$ including the perturbation are known for the input $\\tilde{x}_t$ given in advance. On the other hand, in actual situations, if the adversary secretly provides the perturbation $\\delta_t$ and the user receives $x_t = \\tilde{x}_t + \\delta_t$ without knowing the situation, the user only knows $(\\tilde{x}_t,y_t)$, so the problem remains that the surrogate model calculation using $(x_t,y_t)$ cannot be performed.\n\n[Quality: 3]\nThe proposed method performs theoretical analysis of regret under the RKHS setting based on GP-UCB theory. Numerical experiments confirm the practical performance of the proposed method under various adversarial perturbations. The paper also explains the theoretical limitations of the problem setting, namely that the regret bound becomes linear for standard  regret due to the existence of adversarial perturbations.  On the other hand, it appropriately explains that the upper bound of the regret including adversarial perturbations becomes sublinear. Furthermore, it mentions that setting the threshold $\\tau$ in cases where little prior information is available is a problem as a limitation and possibility for future development of this method.\n\n[Clarity: 3]\nThis paper appropriately explains the problem setting, assumptions and results of the theorems, and their interpretations. Furthermore, in the definition of robust satisficing, the paper uses figures as well as mathematical formulas to visually explain the meaning of these robustness measures, making them easier to understand.\n\n[Significance: 3]\nThis paper provides ideas for designing practical methodologies for BO for robustness measures in the presence of adversarial perturbations. It can be expected to derive the regret bounds under adversarial perturbations for other robustness measures in a manner similar to this paper. Additionally, unlike overly conservative robustness measures such as worst-case measures, this paper highlights the importance of considering robustness measures like robust satisficing, which strike a moderate balance.\n\n[Originality: 3]\nIt has been shown that existing GP-UCB for maximization problems can be extended to acquisition functions for robust satisficing under adversarial perturbations. Furthermore, as a point that can advance the field of robust BO, a new methodology for performing regret analysis has been provided by considering robust satisficing as a moderate measure. This enables the exploration of extensions to multi-objective optimization using multiple robust satisficing measures. In this sense, this research is highly original. \n\nBased on the above, I have evaluated this paper as 5, as it meets all the criteria for acceptance.", "was_revised": true, "final_justification": "The author's rebuttal cleared up my confusion, but it was not enough to raise my rating to 6. Furthermore, the most significant limitation of this paper, namely, the assumption that the adversarial perturbations are known, still remains. However, while I agree this as a limitation, I do not consider it a fatal flaw. The reason is that constructing a reasonable model without knowing the values of adversarial perturbations is inherently a challenging problem, and thus this issue should be addressed in future work. Hence, I believe this limitation should not lower the evaluation of this paper. Therefore, I have not changed my initial score of 5.", "rebuttal": "Dear Reviewer SL7m,\n\nThank you for your feedback. We greatly appreciate your positive assessment of our work's quality, clarity, significance, and originality. Below, we address the weaknesses and questions you raised.\n\n**Weakness:**\n\n(1. The comparison with related robustness measures is...)\nWe thank the reviewer for their suggestion and agree that comparison with related robustness measures is relevant. But we also note that this would require some change in the problem formulation, as currently we do not model the perturbation as a random variable. The measures the reviewer mentions, such as VaR, CVaR, and DRO, are probabilistic measures. For direct comparison, the problem formulation could be altered to contain a random covariate in the objective function, i.e., $f(x, Z)$, instead of just considering $f(x)$. Then, depending on whether the distribution of $Z$ is known or not, one can propose variations of our RS measures tailored to the problem formulation. One possibility when the distribution of $Z$ is known is to consider the robustness measure:\n$$\n    \\kappa\\_{\\tau,p}(x) = \\inf\\_{k \\geq 0} k \\quad \\text{s.t.} \\quad \\mathbb{P}\\_Z \\left( f(x,Z) \\geq \\tau - [k  d(Z, z\\_\\text{ref})]^p \\right) \\geq 1 - \\delta~,\n$$\nwhere $z\\_\\text{ref}$ is the best estimate of the random covariate. We further note the assumption that input perturbations follow a distribution would limit the power of the adversary. Since the setup in our paper sets no limitation on the adversary, it is more general. We will emphasize these differences in the revised version of the paper.\n\n(2. The robustness of robust satisficing strongly depends on...) Indeed, the performance of our algorithms depend on the satisficing threshold $\\tau$. In general, achieving good lenient regret for larger $\\tau$ values is more difficult. However, we argue that selecting $\\tau$ is much more interpretable and straightforward compared to selecting the ambiguity ball radius $r$ for the RO approach. The insulin dosage experiment also serves as an example to show how a domain expert might approach setting $\\tau$ in a real-world setting.\n\n(3. The value of the adversarial perturbation is assumed to be known...)\nThis is a very good point, one which is raised by other reviewers as well. There is work on GPs where the input is not directly observed. For example, to account for input uncertainty in the surrogate model, [A] (reference no 23 in the paper) assumes that perturbations follow a distribution and defines a GP over probability distributions. Further, they assume access to a reference distribution estimating the true query location. As our setting does not have any such assumptions on the adversary, adapting it to uncertain inputs remains an open problem. We will mention this as an important future research direction.\n\n[A] Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs. In The 22nd international conference on artificial intelligence and statistics, pages 1177–1184. PMLR, 2019.\n\n**Questions:**\n- (1. Among the various robustness measures...) Following our discussion from the weakness section, while VaR and CVaR are threshold-based robustness measures, they measure mainly the magnitude of the tail-end of outcomes. VaR, for example, measures the level of loss that will not be exceeded with probability $1 - \\alpha$. The proposed RS measures are different in the sense that they also give consideration to likely outcomes. For example, the proposed measures require an action to achieve $\\tau$ when there is no perturbation, and be close to $\\tau$ when the perturbation is small. This separates the RS measures from VaR and CVaR.\n- (2. Can the RKHS assumption be changed...) It is indeed possible to adapt our results to the Bayesian setting. Since one can come up with high probability upper and lower confidence bounds in the Bayesian setting as well, the analysis follows.\n- (3. Can this method be applied in a situation...) As we argued in the weakness section, it is possible to extend our methods to such a setting by incorporating input uncertainty-aware surrogate models. However, this will probably require a more restricted adversary, and remains as an area of future work.\n- (4. In the footnote on page 3...) It is true that we use the Lipschitz continuity of $f$ with respect to the kernel metric in our analysis. The footnote on page 3 states that $f$ is not necessarily Lipschitz with respect to any metric, but it is Lipschitz with respect to the kernel metric, and that we assume $d(\\cdot, \\cdot)$ is the kernel metric moving forward.\n- (5. In equation (2)...) Yes, we allow $k$ to have negative values. However, notice that the fragility being negative means that the objective function lies entirely above the satisficing threshold, i.e., $f(x) > \\tau,$ $\\forall x\\in{\\cal X}$, which implies that the learning problem becomes trivial. In practical cases, where adversarial perturbations can drive the system towards values less than the threshold, we do not observe negative $k$.\n\n**Limitations:** We agree with the reviewer that a limitation of our work is the assumption that adversarial perturbations are observable. In the revised version, we will mention this as a potential direction for future work."}, {"review_id": "a1ypo8bjnZ", "reviewer": "Reviewer_vqo3", "summary": "This paper introduces a novel framework for robust satisficing (RS) in Gaussian Process bandit optimization, where the goal is to reliably achieve a threshold performance level under unknown adversarial perturbations. Unlike traditional robust optimization, which focuses on worst-case outcomes, the authors propose two RS-based formulations (RS-1 and RS-2) that ensure satisfactory performance across a range of perturbations without requiring prior knowledge of the adversary’s strength. They develop algorithms (AdveRS-1 and AdveRS-2) with provable regret bounds and introduce a general RS-G framework that interpolates between RS-1 and RS-2 via a tunable parameter. Empirical results show that these methods outperform existing robust optimization approaches.", "questions": "Please see the listed strengths and weaknesses.\nAlthough, I have no specific questions.", "limitations": "Yes, some limitations are acknowledged at the end of the paper. I believe this work shares similar limitations with previous studies, but they are not critical.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* Clear and well-written paper with helpful illustrations.\n* Related work is well-situated and comprehensive.\n* The paper clearly identifies a setting gap: combining robust objectives, lenient regret, and input perturbations during interaction (beyond standard reported point-only attacks). The algorithm design is also novel.\n* Proposed algorithms make a solid contribution to the robust GP bandits literature. \n* Introduces novel objectives grounded in robust optimization theory.\n* Provides sub-linear regret guarantees for the proposed setting. \n\nNo major weaknesses were identified.\nOne could argue that the motivation for choosing these specific objectives and the interaction protocol could be elaborated further. Additionally, the regret analysis largely build upon prior work.\nHowever, I do not consider these points to be significant weaknesses of the paper.\nThe insulin dosage experiment could be used to further illustrate and motivate the defined interaction protocol, as well as the robust objective and the threshold τ.\n\nMy rating falls between 4 and 5. In my view, there is no obvious reason to reject this paper (will rethink this after I read other reviews); however, some may find it less useful, less motivated, or lacking in novelty, though I consider this a subjective judgment. Overall, the paper is solid and makes meaningful contributions. I find it particularly clever how the authors identified a gap in the literature, namely, the combination of lenient regret, input attacks, and robust objectives. To the best of my knowledge, this setting has not been explored before.", "was_revised": true, "final_justification": "I have been positive about this paper from the beginning and find it interesting, but I am maintaining my positive score because I remain unconvinced about its potential for high impact.", "rebuttal": "Dear Reviewer vqo3, \n\nThank you for your feedback. We greatly appreciate your positive assessment of our work's contributions.\n\nWe agree that the insulin dosage experiment could be used to further illustrate and motivate the problem formulation and the robust satisficing objective. Following your feedback, we will mention this experiment earlier in the paper to set a better context for the rest of our paper. We would be eager to address any questions you might have following the initial reviews and our rebuttals."}]

Author rebuttal:

Meta-review: This paper addresses the problem of Gaussian Process optimization under adversarial attacks by adopting robust satisficing as the objective. The authors develop algorithms for two RS formulations based on fragility and critical radius. All reviewers appreciate the clarity and the solid technical contributions of this work.

A concern raised during the rebuttal was that the paper assumes knowledge of the adversarial perturbation. After discussion, the reviewers agreed that this assumption is acceptable and does not diminish the overall contribution. The authors are encouraged to expand the discussion of this limitation in the revision, particularly by comparing their approach with methods in the literature that do not rely on this assumption. In addition, it would be helpful to provide a more detailed discussion of the relationship between the proposed method and other robustness measures.
Decision: Accept (poster)