The Pareto Regret Frontier for Bandits
This work addresses fundamental trade-offs in bandit algorithms for researchers, providing exact characterizations of the Pareto regret frontier, which is incremental but precise.
The paper tackles the problem of achieving unbalanced worst-case regret guarantees in multi-armed bandits, showing that if an algorithm has low regret for some actions, it must have high regret for others, with a lower bound of Ω(nK/B) and matching upper bounds in stochastic and adversarial settings.
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 Ω(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.