Research map / Bandits and online learning / Multi-armed bandits
Stochastic Bandits Robust to 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.
Designs robust stochastic bandit algorithms against strong (observe-then-attack) adversaries, with known and unknown attack budgets, achieving additive and multiplicative attack-dependent regret bounds with matching lower bounds.
Problem
Stochastic multi-armed bandits where an adaptive adversary observes the pulled arm and its reward before altering the reward observation, under a total attack budget C; prior robust methods rely on randomization that fails under this attack model.
Approach
Successive elimination with widened confidence radius (adding C/N_k) gives robustness to attacks without randomization; a tighter analysis removes the 1/Delta_k multiplicative attack dependence. For unknown C, uses multi-phase elimination with halving assumed budgets and model selection (CORRAL / EXP3.P) over instances with budgets 2^g.
Key results
- Known-budget SE with wide radius achieves O(sum_k log T/Delta_k + KC) pseudo-regret, matching a derived lower bound up to constants.
- Unknown-budget phase elimination (PEWR) achieves tilde O(sqrt(KT) + KC^2) regret, with C^2 term shown tight for its class.
- Model-selection algorithm MSSEWR achieves tilde O(sqrt(KC) T^{2/3}) (CORRAL) or tilde O(KC sqrt(T)) (EXP3.P) pseudo-regret, matching lower bounds for multiplicative algorithm classes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SEWR with a widened confidence radius based on the known attack budget | Stochastic multi-armed bandits · Known attack budget C | realized regret upper bound: O\left( \sum_{k\neq k^*} \frac{\log(KT/\delta)}{\Delta_k} + \sum_{k\neq k^*} \frac{C}{\Delta_k}\right) -> O\left( \sum_{ | Helped |
| Use the SEWRST stopping condition N_k \leqslant T/K instead of the additive-C stopping condition (ablation) | SEWRST · Known attack budget C | realized regret upper bound: O\left( \sqrt{KT\log (KT/\delta)} + KC \right) ; O\left( \sqrt{KT(\log (KT/\delta) + C)} \right) | Mixed |
| Apply multi-phase elimination with decreasing assumed attack budgets | SEWR · Unknown attack budget C | pseudo-regret upper bound: \tilde{O}\left( \sqrt{KT} + KC^2\right) | Helped |
| Use CORRAL instead of EXP3.P for model selection among SEWRST instances (ablation) | MSSEWR · Unknown attack budget C | pseudo-regret upper bound: \tilde{O}(\sqrt{KC}T^{\frac 2 3}) ; \tilde{O}(KC\sqrt T) | Mixed |
| Use the PEWR additive-bound algorithm rather than either MSSEWR multiplicative-bound variant | Algorithms for unknown attack budget C · C = T^β, β ≤qslant 4/9 | regret upper bound: \tilde{O}(\sqrt{KT} + KC^2) ; \tilde{O}(C\sqrt{K}T^{\frac 2 3}), \tilde{O}(C^2 K \sqrt T) | Helped |
| Use the MSSEWR bound \tilde{O}(C\sqrt{K}T^{\frac 2 3}) rather than the additive PEWR bound | Algorithms for unknown attack budget C · C = T^β, β > 4/9 | regret upper bound: \tilde{O}(C\sqrt{K}T^{\frac 2 3}) ; \tilde{O}(\sqrt{KT} + KC^2) | Helped |
Surprising findings
- An attacker with only O(sqrt(T)) budget can force linear regret against the additive-bound unknown-budget algorithm.
- Attack model is strictly stronger than corruption: an attacker needs O(log T) or sublinear budget where corruption requires Theta(T) budget to achieve the same effect.
Limitations
- Best algorithm depends on the actual attack budget C; no single algorithm dominates across all C.
- Known-budget algorithms suffer linear regret if actual attack exceeds the input budget.
- Results are purely theoretical with no experiments reported.
Experimental setup
Metrics: realized regret pseudo-regret
Baselines: SE with wide confidence radius (Lykouris et al. 2018) Phase elimination for linear bandits (Ding et al.) Lipschitz bandit attack-robust model selection
Builds on: successive elimination bandits with corruption (Lykouris et al. 2018) CORRAL EXP3.P
Closest papers by meaning
- Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack (AAAI 2020 · similarity 0.93)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.93)
- Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection (NeurIPS 2026 · similarity 0.91)
- A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond (NeurIPS 2025 · similarity 0.91)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.90)
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.