Timezone: »

 
Poster
The Pareto Regret Frontier for Bandits
Tor Lattimore

Thu Dec 10 08:00 AM -- 12:00 PM (PST) @ 210 C #97
in Poster Session »

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.

[ PDF] 

Author Information

Tor Lattimore (University of Alberta)

More from the Same Authors