Quelques idées sur les problèmes de bandits

Un agent doit choisir, à chaque instant, une action parmi une famille d'actions disponibles. Chaque action conduit à une récompense aléatoire de distribution inconnue. Comment doit-il s'y prendre pour maximiser la somme des récompenses qu'il recueille ? Une bonne politique doit réaliser un savant équilibre entre l'exploitation des actions qui se sont révélées payantes par le passé et l'exploration de nouvelles possibilités qui pourraient s'avérer encore meilleures.

L'étude mathématique de ces problèmes dits de bandits (en référence à la situation paradigmatique d'un joueur faisant face à une lignée de machines à sous) remonte aux années 1930. De nombreux travaux ont suivi : on présentera principalement dans cet exposé les algorithmes dits "optimistes", qui accordent toujours le bénéfice du doute aux actions mal connues, et qui ont l'avantage de pouvoir être appliquées dans une grande variété de situations.