From the archives
Learning the distribution with largest mean: two bandit frameworks
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: ESAIM: Proceedings and Surveys
Date: December, 2017
PageStart: 114
PageEnd: 131
Arxiv Number: 1702.00001
Hal Number: 01449822
Authors: Emilie KaufmannAurélien Garivier
Abstract: Over the past few years, the multi-armed bandit model has become
increasingly popular in the machine learning community, partly because of applications
including online content optimization. This paper reviews two different sequential learning
tasks that have been considered in the bandit literature ; they can be formulated as
(sequentially) learning which distribution has the highest mean among a set of
distributions, with some constraints on the learning process. For both of them (regret
minimization and best arm identification) we present recent, asymptotically optimal
algorithms. We compare the behaviors of the sampling rule of each algorithm as well as the
complexity terms associated to each problem. Le modèle stochastique dit de bandit à
plusieurs bras soulève ces dernières années un grand intérêt dans la communauté de
l’apprentissage automatique, du fait notamment de ses applications à l’optimisation de
contenu sur le web. Cet article présente deux problèmes d’apprentissage séquentiel dans le
cadre d’un modèle de bandit qui peuvent être formulés comme la découverte de la distribution
ayant la moyenne la plus élevée dans un ensemble de distributions, avec certaines
contraintes sur le processus d’apprentissage. Pour ces deux objectifs (minimisation du
regret d’une part et identification du meilleur bras d’autre part), nous présentons des
algorithmes optimaux, en un sens asymptotique. Nous comparons les stratégies
d’échantillonnage employées par ces deux types d’algorithmes ainsi que les quantités
caractérisant la complexité de chacun des problèmes. DOI:
https://doi.org/10.1051/proc/201760114
Direct link: accessible sur le site d'ESAIM:PS
Volume: 60
Keywords:
