  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.
