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

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\sqrt{n\log n})$ and against stochastic bandits the pseudo-regret is $O({\sum }_i(\log n)/{\Delta }_i)$. We also show that no algorithm with $O(\log n)$ pseudo-regret against stochastic bandits can achieve $\tilde{O}(\sqrt{n})$ expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show $\tilde{O}(\sqrt{n})$ expected adversarial regret with $O((\log n{)}^2)$ stochastic pseudo-regret.

Cited by in corpus (14)

• AI Safety Gridworlds
• Corruption-robust exploration in episodic reinforcement learning
• Power Constrained Bandits
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Stochastic Linear Bandits Robust to Adversarial Attacks
• Stochastic bandits robust to adversarial corruptions
• Corralling Stochastic Bandit Algorithms
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Modeling Friends and Foes
• Optimality of the Subgradient Algorithm in the Stochastic Setting
• Self-Tuning Bandits over Unknown Covariate-Shifts
• Banker Online Mirror Descent