Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks

Dear Reviewer vqo3,

Thank you for your feedback. We greatly appreciate your positive assessment of our work's contributions.

We 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.

Dear Reviewer SL7m,

Thank 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.

Weakness:

(1. The comparison with related robustness measures is...) We 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:

where $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.

(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.

(3. The value of the adversarial perturbation is assumed to be known...) This 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.

[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.

Questions:

• (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.
• (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.
• (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.
• (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.
• (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$.

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.

Dear Reviewer X7S6,

Thank 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.

Weakness:

As 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. In 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.

Questions:

• (...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:

  • 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).
  • 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.

  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.

  [A] Zhu, Mingye, et al. "Leveraging Robust Optimization for LLM Alignment under Distribution Shifts." arXiv preprint arXiv:2504.05831 (2025).

  [B] Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464–501, 2011.

  [C] Huan Xu and Shie Mannor. Distributionally robust markov decision processes. Advances in Neural Information Processing Systems, 23, 2010.

  [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.

  [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.

  [F] Daniel Zhuoyu Long, Melvyn Sim, and Minglong Zhou. Robust satisficing. Operations Research, 71(1):61–82, 2023.

• (...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. However, we underscore that our results do not depend on the attacking scheme of the adversary.

• (...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.

  Algorithm	t=100	t=200	t=300	t=400	t=500
  RS1	25.27 ± 2.06	36.38 ± 2.85	46.19 ± 3.67	54.24 ± 4.35	62.35 ± 4.55
  RS1T	20.59 ± 2.07	33.18 ± 2.84	43.52 ± 3.37	53.05 ± 4.34	62.35 ± 4.95
  RS2	22.83 ± 2.10	34.69 ± 2.65	44.00 ± 2.96	52.69 ± 3.62	61.41 ± 4.24
  RS2T	20.93 ± 2.51	34.43 ± 3.17	45.54 ± 3.73	55.47 ± 4.24	65.64 ± 4.76
  RO $r=\sigma_s$	16.96 ± 2.06	29.34 ± 2.72	40.79 ± 3.46	51.47 ± 4.07	62.50 ± 4.67
  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
  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

Dear Reviewer wsUa,

Thank you for your feedback. We're grateful for your acknowledgement of the value of our work. Below, we respond to each comment in detail.

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.

Questions:

• (... 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.

  [A] Kovatchev, Boris P., et al. "Symmetrization of the blood glucose measurement scale and its applications." Diabetes Care 20.11 (1997): 1655-1658.

  [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.

  [C] American Diabetes Association. "6. Glycemic targets: standards of medical care in diabetes-2021." Diabetes Care 44.Suppl 1 (2021): S73-S84.

• (... 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.

• (... 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.

  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.