Exploration d'arbres appliquée à l'optimisation et à la prise de décision

Abstract

Cette thèse se concentre sur deux problèmes bien étudiés : l'optimisation et la planification. L'optimisation fait référence au problème consistant à trouver la valeur pour laquelle une fonction donnée est maximisée. La planification consiste à décider quelles actions entreprendre dans le contexte d'un problème de prise de décision séquentielle. Ces deux problèmes sont similaires dans la mesure où ils impliquent la maximisation d'une gratification définie de manière externe. Un problème d'optimisation peut être reformulé en un problème de recherche arborescente en représentant l'espace d'entrée de la fonction objective comme un arbre. De même, un problème de planification peut naturellement être exprimé comme un problème de recherche arborescente. Nous tenterons donc de résoudre ces deux problèmes par recherche arborescente. La difficulté de cette recherche réside dans la taille typique de l'arbre, seule une infime fraction pouvant être explorée. Notre objectif est donc de choisir quelle partie explorer (ou non) compte tenu des parties déjà visitées de l'arbre afin de résoudre notre problème initial, qu'il s'agisse de planification ou d'optimisation.Dans la première partie, nous nous concentrons sur l'optimisation pour deux classes différentes de fonctions. Tout d'abord, les fonctions Lipschitz qui sont une classe de fonctions lisses par rapport à une métrique, nous montrons comment toute fonction de cette classe peut être optimisée avec peu de connaissances préalables. Ensuite, un processus gaussien particulier : le mouvement brownien, que nous montrons peut être optimisé en temps sub-polynomial. Dans la deuxième partie, nous nous concentrons sur la planification et présentons une borne polynomiale sur la complexité d'échantillonnage pour une classe particulière de processus décisionnels de Markov (MDP) dans le cadre général de l'apprentissage par renforcement. Nous examinerons également le cas régularisé par entropie pour lequel nous fournirons un algorithme qui, pour tout MDP, bénéficie d'une borne de complexité simple polynomiale.