Research map / Bandits and online learning / Multi-armed bandits
Adversarial Attacks on Combinatorial 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.
Characterizes polynomial attackability of combinatorial multi-armed bandits (CMAB) via a gap condition, proposes a base-arm-zeroing attack, and shows attackability can differ between known and unknown environments.
Problem
Understanding when combinatorial semi-bandits (CMAB) are vulnerable or intrinsically robust to reward poisoning attacks, given the exponential number of super arms.
Approach
Defines polynomial attackability for CMAB and shows a sufficient and necessary condition based on a gap between target and competing super arms; proposes an attack that sets non-target base-arm outcomes to zero; shows attackability in known vs unknown environments can differ.
Key results
- Attack on probabilistic maximum coverage: target arm pulls grow linearly after about 5,000 iterations while attack cost grows sublinearly.
- Online shortest path with unattackable targets: attack cost is linear while target pulls remain nearly constant, consistent with the theory.
- Hard example shows an instance polynomially attackable with known mean vector but not efficiently attackable when mean is unknown to the CUCB-based setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply the proposed reward-poisoning attack | CUCB with Greedy oracle on probabilistic maximum coverage · Probabilistic maximum coverage (Flickr) | target arm pulls | Helped |
| apply the proposed reward-poisoning attack | online minimum spanning tree · Online minimum spanning tree (Flickr) | target arm pulls | Helped |
| apply the proposed reward-poisoning attack to a random target | online shortest path · Online shortest path (Flickr), random target | target arm pulls | Helped |
| apply the proposed reward-poisoning attack to an unattackable target | online shortest path · Online shortest path (Flickr), unattackable target | target arm pulls | No clear effect |
| apply the proposed reward-poisoning attack | cascading bandits · Cascading bandits (MovieLens small) | target arm pulls | Helped |
| use the attack heuristic for online influence maximization | online influence maximization with IMM oracle · Online influence maximization | percentage of target nodes selected | No clear effect |
Surprising findings
- Attackability of the same CMAB instance can differ depending on whether the adversary knows the environment parameters.
- Influence maximization with diffusion (beyond one step) did not show target pulls growing under the heuristic attack.
Limitations
- Characterization limited to reward poisoning; does not cover environment poisoning.
- Attack cost bound may not be optimal; no lower bound provided.
- Unknown-environment attackability is open for shortest path and influence maximization.
Experimental setup
Datasets: Flickr MovieLens small
Benchmarks: probabilistic maximum coverage online minimum spanning tree online shortest path cascading bandits online influence maximization
Metrics: attack cost number of target super arm pulls
Baselines: CascadeKL-UCB CascadeUCB1 CascadeUCB-V
Builds on: CUCB Combinatorial semi-bandit framework (Chen et al.) MAB attackability (Jun et al.) linear bandit attackability (Liu and Shroff)
Closest papers by meaning
- Offline Learning for Combinatorial Multi-armed Bandits (ICML 2025 · similarity 0.88)
- When Are Linear Stochastic Bandits Attackable? (ICML 2022 · similarity 0.87)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.87)
- Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond (ICML 2024 · similarity 0.85)
- Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection (NeurIPS 2026 · similarity 0.85)
- Stealthy Adversarial Attacks on Stochastic Multi-Armed Bandits (AAAI 2024 · similarity 0.85)
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.