Research map / Bandits and online learning / Multi-armed bandits
A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
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 BARBAT, an elimination-based framework for stochastic bandits under adversarial corruption that removes the O(KC) term of BARBAR, using static epoch lengths and epoch-varying failure probabilities, and extends it to multi-agent, batched, graph and semi-bandit settings.
Problem
Stochastic bandits with adversarial reward corruptions; BARBAR's regret has an O(KC) term that does not match the Omega(C) lower bound, and FTRL-based alternatives are computationally costly and hard to parallelize.
Approach
Use data-independent (static) epoch lengths N_m ~ K 2^{2(m-1)} so the adversary cannot inflate epochs, allocate fixed pulls to suboptimal arms and remaining pulls to the estimated best arm, and use epoch-varying failure probabilities delta_m ~ 1/(mK 2^{2m}) to avoid a global delta and the need to know T.
Key results
- BARBAT achieves regret O(C + sum_k log(T)log(KT)/Delta_k + K log(1/Delta)log(K/Delta)/Delta), removing the multiplicative K from BARBAR's O(KC) term.
- MA-BARBAT requires communication cost V log(VT) and reduces each agent's individual regret by a factor of V.
- Experiments with 50 trials report that the proposed methods outperform baselines (DRAA, IND-BARBAR, IND-FTRL, Shannon-FTRL, Tsallis-FTRL, HYBRID, LBINF variants) in regret on simulated instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace BARBAR's dynamic epoch lengths with BARBAT's static epoch lengths and epoch-varying failure probabilities | Stochastic multi-arm bandits · Multi-arm bandits | regret bound: KC + \sum_{\Delta_k > 0}\frac{\log^2(T)}{\Delta_k} -> O\left(C + \sum_{\Delta_k > 0}\frac{\log(T)\log(KT)}{\Delta_k} + \ | Helped |
| Extend BARBAT to cooperative agents that share epoch reward messages | MA-BARBAT · Multi-agent multi-arm bandits | individual regret: The paper states collaboration reduces each agent’s individual regret by a factor of V. | Helped |
| Use BB-BARBAT for batched feedback | Batched bandits · Batched bandits, static grid | regret | Mixed |
| Extend BARBAT to strongly observable directed graph feedback | SOG-BARBAT · Strongly observable graph bandits | regret bound: O(\alpha C) -> O(C) | Helped |
| Use DS-BARBAT for d-set semi-bandit feedback | DS-BARBAT · d-set semi-bandits | regret | Helped |
| Use MA-BARBAT instead of DRAA, IND-BARBAR, or IND-FTRL | Cooperative multi-agent multi-arm bandits · Cooperative multi-agent multi-arm bandits | individual regret | Helped |
| Use SOG-BARBAT instead of Shannon-FTRL or Tsallis-FTRL | Strongly observable graph bandits · Strongly observable graph bandits | regret | Helped |
| Use DS-BARBAT instead of HYBRID, LBINF, LBINF_LS, or LBINF_GD | d-set semi-bandits · d-set semi-bandits | regret | Helped |
| Increase corruption level | MA-BARBAT and baselines · Cooperative multi-agent multi-arm bandits | individual regret | Mixed |
Limitations
- Regret has a log^2(T) dependence rather than optimal log(T) for the gap term
- Batched bandit upper bound has a gap with the lower bound
- Only centralized multi-agent setting with no communication delays considered
Experimental setup
Benchmarks: simulated multi-armed bandit instances
Metrics: pseudo-regret individual regret communication cost running time
Baselines: BARBAR Shannon-FTRL Tsallis-FTRL Elise DRAA IND-BARBAR IND-FTRL HYBRID LBINF LBINF_LS LBINF_GD
Builds on: BARBAR Follow-the-Regularized-Leader Active Arm Elimination
Closest papers by meaning
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.91)
- Stochastic Graphical Bandits with Adversarial Corruptions (AAAI 2021 · similarity 0.91)
- Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.89)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.88)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.88)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · similarity 0.88)
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.