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 (31)

• Model Selection in Contextual Stochastic Bandit Problems
• Stochastic Linear Optimization with Adversarial Corruption
• Corruption-robust exploration in episodic reinforcement learning
• Adversarial Attacks on Linear Contextual Bandits
• Power Constrained Bandits
• Better Algorithms for Stochastic Bandits with Adversarial Corruptions
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Stochastic Linear Bandits Robust to Adversarial Attacks
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
• Corralling Stochastic Bandit Algorithms
• Upper Confidence Bounds for Combining Stochastic Bandits
• Unifying the stochastic and the adversarial Bandits with Knapsack
• Linear Contextual Bandits with Adversarial Corruptions
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack
• Reliability and Battery Lifetime Improvement for IoT Networks: Challenges and AI-powered solutions
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
• Banker Online Mirror Descent
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions
• Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
• Customs Fraud Detection in the Presence of Concept Drift
• 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
• Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations