Research map / Adversarial robustness and security / Certified and empirical robustness
Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes robust satisficing acquisition algorithms (AdveRS-1, AdveRS-2, and a p-parameterized AdveRS-G) for GP bandit optimization under unknown adversarial input perturbations, with regret bounds and experiments against STABLEOPT.
Problem
Gaussian process bandit optimization where an adversary perturbs the chosen action by an unknown, possibly varying budget; the goal is to consistently achieve a satisficing threshold tau rather than maximize worst-case reward.
Approach
Replace robust optimization's ambiguity set with robust satisficing objectives (fragility-based RS-1, critical-radius-based RS-2, and a unifying p-fragility RS-G), each turned into a GP-UCB-style optimistic acquisition rule so no perturbation budget must be specified.
Key results
- AdveRS-2 consistently meets the threshold tau with sublinear lenient regret in the synthetic experiment where StableOpt with misspecified radius suffers linear regret.
- Regret bound of AdveRS-1 is 4 beta_T sqrt(T gamma_T) + B sum epsilon_t for lenient regret, and 4 beta_T sqrt(T gamma_T) for RS regret; AdveRS-2 achieves 4 beta_T sqrt(T gamma_T) for both.
- In the insulin dosage experiment, both AdveRS-1 and AdveRS-2 outperform StableOpt when its radius r is suboptimal, though no algorithm achieves sublinear regret there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AdveRS-2 instead of STABLEOPT with a misspecified ambiguity radius | Synthetic experiment, ε_t = 0.5 · Synthetic experiment (Assumption holds) | lenient regret | Helped |
| Use AdveRS-1 instead of STABLEOPT with a misspecified ambiguity radius | Synthetic experiment, ε_t = 0.5 · Synthetic experiment (Assumption holds) | lenient regret | Helped |
| Use RS-G with p = 2 (ablation) | Synthetic experiment · Synthetic experiment | lenient regret | Helped |
| Use AdveRS algorithms instead of STABLEOPT with a misspecified ambiguity radius | AdveRS-1 and AdveRS-2 · Insulin dosage | regret | Helped |
| Set the ambiguity radius to the perturbation standard deviation | STABLEOPT · Insulin dosage | regret | Helped |
| Use RS-1 or RS-2 actions instead of the RO baseline | Robustness to worst case attack · Worst-case attack robustness | Area(ε) | Helped |
| Use RS-2 rather than RS-1 | Robustness to worst case attack · Worst-case attack robustness | threshold achievement | Helped |
| Use RS-1 rather than RS-2 when τ is unattainable | Robustness to worst case attack · Worst-case attack robustness | robustness | Helped |
| Use AdveRS-1 or AdveRS-2 instead of STABLEOPT | Synthetic experiment · Synthetic experiment (Assumption fails) | lenient regret | No clear effect |
| Use AdveRS-1 or AdveRS-2 instead of STABLEOPT with a correctly specified ambiguity radius | Synthetic experiment · Synthetic experiment, robust satisficing regret | robust satisficing regret | Helped |
| Use AdveRS-1 or AdveRS-2 instead of STABLEOPT | Insulin dosage · Insulin dosage | regret | Mixed |
Surprising findings
- When the satisficing threshold is unattainable, all algorithms suffer linear regret, consistent with the theory; the RS-G with p=2 showed the smallest regret in the synthetic experiment.
Limitations
- Regret bounds for AdveRS-2 assume the threshold tau is achievable (Assumption on tau <= max f).
- Assumes the perturbations are observed and the perturbation model is known in the adversarial setting.
- Selecting tau requires domain expertise; maximizing UCB/LCB is assumed solvable by an oracle.
Experimental setup
Datasets: UVA/PADOVA T1DM simulator
Benchmarks: synthetic proof-of-concept function insulin dosage (UVA/PADOVA T1DM simulator) inverted pendulum
Metrics: lenient regret robust satisficing regret area under worst-case reward curve
Baselines: StableOpt
Builds on: GP-UCB StableOpt robust satisficing fragility formulation
Closest papers by meaning
- Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.88)
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.88)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.87)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.87)
- Improved Regret Analysis For Parallel Gaussian Process Bandit Optimization (NeurIPS 2026 · similarity 0.87)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.