Apprendre la distribution avec la plus grande moyenne : deux cadres de bandits.

Résumé Au cours des dernières années, le modèle de bandit à bras multiples est devenu de plus en plus populaire dans la communauté de l'apprentissage automatique, en partie en raison d'applications telles que l'optimisation du contenu en ligne. Cet article passe en revue deux tâches d'apprentissage séquentiel différentes qui ont été considérées dans la littérature sur le bandit. Elles peuvent être formulées comme l'apprentissage (séquentiel) de la distribution ayant la moyenne la plus élevée parmi un ensemble de distributions, avec certaines contraintes sur le processus d'apprentissage. Pour les deux (minimisation du regret et identification du meilleur bras), nous présentons des algorithmes récents, asymptotiquement optimaux. Nous comparons les comportements de la règle d'échantillonnage de chaque algorithme ainsi que les termes de complexité associés à chaque problème.