Learning the distribution with largest mean: two bandit frameworks

Abstract

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.