Better Algorithms for Stochastic Bandits with Adversarial Corruptions

2019/02/22 by Anupam Gupta, Gupta, Anupam, Tomer Koren +3 · 4 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1902.08647

openalex publication_date 2019/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.

Citations

• Robust Estimation of a Location Parameter
• The Nonstochastic Multiarmed Bandit Problem

Cited by

• Robust Bayesian Optimisation with Unbounded Corruptions
• Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach
• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates
• Robust Policy Gradient against Strong Data Corruption

Related

• Stochastic bandits robust to adversarial corruptions
• A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions
• Efficient and Optimal Policy Gradient Algorithm for Corrupted Multi-armed Bandits
• Stochastic Linear Optimization with Adversarial Corruption