The best of both worlds: stochastic and adversarial bandits
This addresses a key issue in algorithm design for multi-armed bandits, providing a unified solution that adapts to unknown input types, which is incremental as it builds on prior separate treatments.
The paper tackles the problem of designing a bandit algorithm that performs optimally in both stochastic and adversarial reward settings, achieving square-root worst-case regret for adversarial rewards and polylogarithmic regret for stochastic rewards.
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.