Cette thèse, à la croisée entre la statistique séquentielle et de l’apprentissage par renforcement, s’intéresse au problème d’identification de la meilleure politique dans un Processus de décision Markovien (PDM). Ce problème a surtout été étudié dans une optique ‘‘pire des cas’’. L’objet de cette
thèse est d’aller au-delà de ce cadre pessimiste en approfondissant la compréhension de la complexité ‘‘spécifique à l’instance’’, c’est à dire du nombre d’observations dont un algorithme adaptatif aurait besoin pour trouver une politique (quasi-) optimale.
Premièrement, en s’inspirant des travaux existants dans le cas particulier des bandits multi-bras, nous démontrons une borne inférieure sur la complexité de n’importe quelle stratégie qui identifie la meilleur politique avec un niveau de confiance fixé. Ensuite nous proposons un algorithme qui atteint cette borne inférieure en échantillonnant les paires d’état-action du PDM selon les proportions optimales dictées par la borne.
Dans un deuxième temps, nous examinons des stratégies basées sur l’élimination progressive des mauvaises politiques dans le cadre de PDM épisodiques (c’est-à-dire à horizon fini). Ces stratégies reposent sur une nouvelle méthode d’exploration, qui présente un intérêt en soi. En effet, elle permet de collecter n’importe quel nombre souhaité d’échantillons depuis n’importe quelles régions du PDM en utilisant le minimum d’épisodes d’interaction possible. Ceci donne lieu à un algorithme avec des garanties valides à n’importe quel niveau de confiance, au prix d’une perte de l’optimalité asymptotique.
Gratuit
Disciplines