Ce document présente d’une manière unifiée plusieurs résultats liés à la résolution optimale de problèmes dits de bandit à plusieurs bras. Nous présentons et analysons des algorithmes pour la prise de décision séquentielle qui échantillonnent de manière adaptative des distributions de probabilités ayant des caractéristiques inconnues, dans le but de remplir différents types d’objectifs. Nous présentons des contributions pour la résolution de deux types de problèmes. D’une part nous nous intéressons à la maximisation de récompenses dans des variantes du modèle de bandit classique, et d’autre part nous étudions différents problèmes d’identification active, pour lesquels l’objectif est d’optimiser l’exploration de l’environnement de sorte à pouvoir répondre une question (possiblement complexe) sur les distributions sous-jacentes, mais sans la contrainte de maximiser des récompenses. Nous mettons en avant plusieurs outils communs pour traiter ces deux types de problèmes. Tout d’abord l’utilisation de bornes inférieures,qui permettent non seulement de valider l’optimalité d’un algorithme, mais qui servent aussi à guider la conception d’algorithmes asymptotiquement optimaux. Nous présentons en effet plusieurs exemples d’algorithmes inspirés par des bornes inférieures. Ensuite, nous insistons sur l’importance des inégalités de concentration auto-normalisées et uniformes en temps pour l’analyse d’algorithmes de bandits. En-fin, nous présentons plusieurs variantes d’un important principe bayésien appelé l’échantillonnage de Thompson, qui conduit`a des algorithmes asymptotiquement optimaux et faciles d’implémentation dans certains cas particuliers.
soutenue le 13/11/2020
français
English