From the archives
Explore First, Exploit Next: The True Shape of Regret in Bandit Problems
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: Mathematics of Operations Research
Date: September, 2018
Arxiv Number: 1602.07182
Hal Number: 01276324
Authors: Aurélien GarivierPierre MénardGilles Stoltz
Abstract: We revisit lower bounds on the regret in the case of multi-armed
bandit problems. We obtain non-asymptotic, distribution-dependent bounds and provide simple
proofs based only on well-known properties of Kullback-Leibler divergences. These bounds
show in particular that in the initial phase the regret grows almost linearly, and that the
well-known logarithmic growth of the regret only holds in a final phase. The proof
techniques come to the essence of the information-theoretic arguments used and they involve
no unnecessary complications. First version: Feb. 2016
Direct link: available on pubsonline.informs https://doi.org/10.1287/moor.2017.0928
Keywords:
