The best of both worlds: stochastic and adversarial bandits

Abstract

We present a new bandit algorithm, SAO (Stochastic and Adversarial Optimal), whose regret is, essentially, optimal both for adversarial rewards and for stochastic rewards. Specifically, SAO combines the square-root worst-case regret of Exp3 (Auer et al., SIAM J. on Computing 2002) and the (poly)logarithmic regret of UCB1 (Auer et al., Machine Learning 2002) for stochastic rewards. Adversarial rewards and stochastic rewards are the two main settings in the literature on (non-Bayesian) multi-armed bandits. Prior work on multi-armed bandits treats them separately, and does not attempt to jointly optimize for both. Our result falls into a general theme of achieving good worst-case performance while also taking advantage of "nice" problem instances, an important issue in the design of algorithms with partially known inputs.

Cited by in corpus (19)

• Better Algorithms for Stochastic Bandits with Adversarial Corruptions
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Linear Contextual Bandits with Adversarial Corruptions
• Upper Confidence Bounds for Combining Stochastic Bandits
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
• Banker Online Mirror Descent
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack
• Reliability and Battery Lifetime Improvement for IoT Networks: Challenges and AI-powered solutions
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Adversarial Dueling Bandits
• Interference management for coexisting Internet of Things networks over unlicensed spectrum
• Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
• Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
• Customs Fraud Detection in the Presence of Concept Drift