The best of both worlds: stochastic and adversarial bandits

Sebastien Bubeck, Aleksandrs Slivkins

We present a new bandit algorithm, SAO (Stochastic and Adversarial Optimal), whose regret is, essentially, optimal both for adversarial rewards and for stochastic rewards. Specific…