An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits

2016/05/27 by Peter Auer, Auer, Peter, Chao-Kai Chiang +1 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1605.08722

openalex publication_date 2016/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algorithm that achieves almost optimal pseudo-regret bounds against adversarial and stochastic bandits. Against adversarial bandits the pseudo-regret is O(K√(n log n)) and against stochastic bandits the pseudo-regret is O(∑_i (log n)/Δ_i). We also show that no algorithm with O(log n) pseudo-regret against stochastic bandits can achieve O(√(n)) expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show O(√(n)) expected adversarial regret with O((log n)²) stochastic pseudo-regret.

Citations

• The Nonstochastic Multiarmed Bandit Problem

Cited by

• Bandit Regret Scaling with the Effective Loss Range
• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback

Related

• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• The best of both worlds: stochastic and adversarial bandits
• Bandit algorithms: Letting go of logarithmic regret for statistical robustness
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Bandits with Side Observations: Bounded vs. Logarithmic Regret