Robustness of Anytime Bandit Policies
Preprint
Abstract
This paper studies the deviations of the regret in a stochastic multi-armed bandit problem. When the total number of plays n is known beforehand by the agent, Audibert et al. (2009) exhibit a policy such that with probability at least 1-1/n, the regret of the policy is of order log(n). They have also shown that such a property is not shared by the popular ucb1 policy of Auer et al. (2002). This work first answers an open question: it extends this negative result to any anytime policy. The second contribution of this paper is to design anytime robust policies for specific multi-armed bandit problems in which some restrictions are put on the set of possible distributions of the different arms.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Exploration–exploitation tradeoff using variance estimates in multi-armed banditsTheoretical Computer Science, 2009
- When can the two-armed bandit algorithm be trusted?The Annals of Applied Probability, 2004
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- Optimal Adaptive Policies for Sequential Allocation ProblemsAdvances in Applied Mathematics, 1996
- Adaptation in Natural and Artificial Systems1992
- The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz InequalityThe Annals of Probability, 1990
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952