An algorithm with nearly optimal pseudo-regret for both stochastic and
  adversarial bandits
  We present an algorithm that achieves almost optimal pseudo-regret bounds
against adversarial and stochastic bandits. Against adversarial bandits the
pseudo-regret is $O(K\sqrt{n \log n})$ and against stochastic bandits the
pseudo-regret is $O(\sum_i (\log n)/\Delta_i)$. We also show that no algorithm
with $O(\log n)$ pseudo-regret against stochastic bandits can achieve
$\tilde{O}(\sqrt{n})$ expected regret against adaptive adversarial bandits.
This complements previous results of Bubeck and Slivkins (2012) that show
$\tilde{O}(\sqrt{n})$ expected adversarial regret with $O((\log n)^2)$
stochastic pseudo-regret.
