Thumbnail

Lower Bounds and Selectivity of Weak-Consistent Policies in Stochastic Multi-Armed Bandit Problem.

El Alaoui, Issam; Audibert, Jean-Yves; Salomon, Antoine (2013), Lower Bounds and Selectivity of Weak-Consistent Policies in Stochastic Multi-Armed Bandit Problem., Journal of Machine Learning Research, 14, 1, p. 187-207

View/Open
Type
Article accepté pour publication ou publié
Date
2013-01
Journal name
Journal of Machine Learning Research
Volume
14
Number
1
Publisher
MIT Press
Pages
187-207
Metadata
Show full item record
Author(s)
El Alaoui, Issam
Audibert, Jean-Yves
Salomon, Antoine
Abstract (EN)
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 consistency, and exhibit a generalisation of the bound. We also study the existence of logarithmic bounds in general and in the case of Hannan consistency. Moreover, 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. To get these results, we study variants of popular Upper Confidence Bounds (UCB) policies.
Subjects / Keywords
Consistency; regret lower bounds; selectivity; stochastic bandits; UCB policies
JEL
D81 - Criteria for Decision-Making under Risk and Uncertainty
C73 - Stochastic and Dynamic Games; Evolutionary Games; Repeated Games