mlsanityData to 7 Oct 2026

A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond

arXiv 2502.07514 ↗First posted 11 Feb 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We investigate various stochastic bandit problems in the presence of adversarial corruptions. A seminal work for this problem is the BARBAR~citegupta2019better algorithm, which achieves both robustness and efficiency. However, it suffers from a regret of O(KC), which does not match the lower bound of Omega(C), where K denotes the number of arms and C denotes the corruption level. In this paper, we first improve the BARBAR algorithm by proposing a novel framework called BARBAT, which eliminates the factor of K to achieve an optimal regret bound up to a logarithmic factor. We also extend BARBAT to various settings, including multi-agent bandits, graph bandits, combinatorial semi-bandits and batched bandits. Compared with the Follow-the-Regularized-Leader framework, our methods are more amenable to parallelization, making them suitable for multi-agent and batched bandit settings, and they incur lower computational costs, particularly in semi-bandit problems. Numerical experiments verify the efficiency of the proposed methods.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 20 of its 36 references that are in the map. First posted on arXiv 11 Feb 2025.

Builds on

20 of 36 references.

References · 20

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2019Batched Multi-armed Bandits Problemcited by 97
  5. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  6. 2020Inference for Batched Banditscited by 63
  7. 2014Nonstochastic Multi-Armed Bandits with Graph-Structured Feedbackcited by 61
  8. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  9. 2019Regret Bounds for Batched Banditscited by 49
  10. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  11. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  12. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
8 more
  1. 2020Double Explore-then-Commit: Asymptotic Optimality and Beyondcited by 24
  2. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  3. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  4. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  5. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  6. 2023Collaborative Multi-Agent Heterogeneous Multi-Armed Banditscited by 4
  7. 2023On Interpolating Experts and Multi-Armed Banditscited by 4
  8. 2024Multi-Agent Stochastic Bandits Robust to Adversarial Corruptionscited by 3

Built on by

Not cited yet.