Refined Lower Bounds for Adversarial Bandits
  We provide new lower bounds on the regret that must be suffered by
adversarial bandit algorithms. The new results show that recent upper bounds
that either (a) hold with high-probability or (b) depend on the total lossof
the best arm or (c) depend on the quadratic variation of the losses, are close
to tight. Besides this we prove two impossibility results. First, the existence
of a single arm that is optimal in every round cannot improve the regret in the
worst case. Second, the regret cannot scale with the effective range of the
losses. In contrast, both results are possible in the full-information setting.
