Allocation dynamique de ressources et modèles 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 qu'on essayera
d'esquisser en fin d'exposé.