The Pareto Regret Frontier for Bandits
  Given a multi-armed bandit problem it may be desirable to achieve a
smaller-than-usual worst-case regret for some special actions. I show that the
price for such unbalanced worst-case regret guarantees is rather high.
Specifically, if an algorithm enjoys a worst-case regret of B with respect to
some action, then there must exist another action for which the worst-case
regret is at least {\Omega}(nK/B), where n is the horizon and K the number of
actions. I also give upper bounds in both the stochastic and adversarial
settings showing that this result cannot be improved. For the stochastic case
the pareto regret frontier is characterised exactly up to constant factors.
