The Pareto Regret Frontier for Bandits

Abstract

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.

14 pages. To appear at NIPS 2015

References in corpus (5)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Further Optimal Regret Bounds for Thompson Sampling
• Adaptive Online Prediction by Following the Perturbed Leader
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• Prediction strategies without loss

Cited by in corpus (6)

• Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
• Model selection for contextual bandits
• Upper Confidence Bounds for Combining Stochastic Bandits
• Open Problem: Model Selection for Contextual Bandits
• Universal and data-adaptive algorithms for model selection in linear contextual bandits
• Comparator-adaptive Convex Bandits