Efficient and Optimal Policy Gradient Algorithm for Corrupted Multi-armed Bandits
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
In this paper, we consider the stochastic multi-armed bandits problem with adversarial corruptions, where the random rewards of the arms are partially modified by an adversary to fool the algorithm. We apply the policy gradient algorithm SAMBA to this setting, and show that it is computationally efficient, and achieves a state-of-the-art O(Klog T/Delta) + O(C/Delta) regret upper bound, where K is the number of arms, C is the unknown corruption level, Delta is the minimum expected reward gap between the best arm and other ones, and T is the time horizon. Compared with the best existing efficient algorithm (e.g., CBARBAR), whose regret upper bound is O(Klog2 T/Delta) + O(C), we show that SAMBA reduces one log T factor in the regret bound, while maintaining the corruption-dependent term to be linear with C. This is indeed asymptotically optimal. We also conduct simulations to demonstrate the effectiveness of SAMBA, and the results show that SAMBA outperforms existing baselines.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. First posted on arXiv 19 Feb 2025.
Builds on
0 of 0 references.
No references here yet.
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
- 2026A Diffusion Analysis of Policy Gradient for Stochastic Bandits
- 2026Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment
- 2026Regret Analysis of Retry-Based Bandits
- 2026A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits
- 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs
- 2025Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
- 2026Offline Local Search for Online Stochastic Bandits