Research map / Adversarial robustness and security / Attacks on text and graphs
Stealthy Adversarial Attacks on Stochastic Multi-Armed Bandits
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 a homogeneity-test detector for reward poisoning attacks on stochastic bandits, shows existing attacks are easily detected, and designs stealthy attacks against UCB1 and epsilon-greedy whose success depends on environment and first-pull reward.
Problem
Reward poisoning attacks on stochastic multi-armed bandits are usually studied without considering attack detection; existing attacks aggressively lower non-target rewards and can be detected, so the real attackability of MAB algorithms under detection is unclear.
Approach
A confidence-interval-based homogeneity test on each arm's observed rewards detects aggressive poisoning; the paper then defines stealthy attacks (detected with probability at most delta) and constructs an attack that shifts non-target arms' first observations so the manipulated sequences remain homogeneous, analyzing when it succeeds for UCB1 and epsilon-greedy and for general algorithms.
Key results
- Existing attacks against UCB1 and epsilon-greedy are detected with high probability in simulations (N=10, T=10000; N=30, T=20000), with detection nearly unaffected by N and T.
- The proposed stealthy attack forces the target arm to be pulled linearly many times under detection, while the baseline attack is quickly detected and fails to trap the learner.
- Theory: with UCB1 a stealthy attack succeeds with probability about 1 - eta when the target-arm gap is below beta(1); stealthy attacks provably fail when the gap exceeds beta(1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply homogeneity-test detection to reward-poisoning attacks | UCB1 and ε-greedy · stochastic MAB simulations | attack detection | Helped |
| use the proposed stealthy attack instead of the baseline attack | UCB1 with detection · stochastic MAB simulations | target-arm pulls | Helped |
| use the proposed stealthy attack instead of the baseline attack | UCB1 with detection · stochastic MAB simulations | attack continuation | Helped |
| use the proposed stealthy attack when Δ⁰₁K < β(1) | UCB1 · stochastic MAB | target-arm pulls: T-\left(\frac{9\sigma^{2}}{(\Delta^{0}_{1K}-\beta(1))^2}+\frac{9N\sigma^{2}}{d^2}\right)\log T -(N-1) | Helped |
| use the proposed stealthy attack when Δ⁰₁K < β(1) | ε-greedy · stochastic MAB | target-arm pulls: T - t_{2} - N\left(C + C\log\frac{T}{CN} + \sqrt{3(C + C\log\frac{T}{CN})\log \frac{1}{\eta}}\right) | Helped |
| attempt a stealthy attack when Δ⁰₁K > β(1) | UCB1 and ε-greedy · stochastic MAB | target-arm pulls | Hurt |
| use a constructed learning algorithm with its corresponding stealthy attack | general stochastic MAB algorithms · any sub-Gaussian environment | target-arm pulls: T-O(\log T) | Helped |
| use a stealthy attack against an EARR algorithm when Δ₁K⁰>2β(1) | EARR bandit algorithm · stochastic MAB | target-arm pulls | Hurt |
Surprising findings
- Stealthy attacks provably cannot succeed when the first-pulled arm's reward gap exceeds beta(1), so attackability is not universal for MAB, contrary to prior belief.
Limitations
- Stealthy attacks cannot succeed when the target gap condition (Delta_1K > beta(1)) holds, limiting attackability.
- Experiments are limited to simulated Gaussian bandits with a single attack baseline.
- Detector response after detection is out of scope.
Experimental setup
Datasets: simulated Gaussian bandit environments
Benchmarks: simulated Gaussian multi-armed bandit instances (N=10, 30)
Metrics: detection probability target arm pulls attack cost
Baselines: existing reward poisoning attack (Jun et al. style attack) UCB1 epsilon-greedy
Builds on: UCB1 epsilon-greedy
Closest papers by meaning
- Adversarial Attacks on Stochastic Bandits (NeurIPS 2018 · similarity 0.92)
- When Are Linear Stochastic Bandits Attackable? (ICML 2022 · similarity 0.91)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.89)
- Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection (NeurIPS 2026 · similarity 0.88)
- Adversarial Attacks on Combinatorial Multi-Armed Bandits (ICML 2024 · similarity 0.85)
- uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs (ICLR 2025 · similarity 0.84)
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.