Regret lower bounds and extended Upper Confidence Bounds policies in stochastic multi-armed bandit problem
Preprint
Abstract
This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistence, and exhibit a generalisation of the logarithmic bound. We also show the non existence of logarithmic bound in the general case of Hannan consistency. To get these results, we study variants of popular Upper Confidence Bounds (ucb) policies. As a by-product, we prove that it is impossible to design an adaptive policy that would select the best of two algorithms by taking advantage of the properties of the environment.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
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- Optimal Adaptive Policies for Sequential Allocation ProblemsAdvances in Applied Mathematics, 1996
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952
- On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two SamplesBiometrika, 1933