Cette thèse se concentre sur deux problèmes bien étudiés : l'optimisation et la planification. L'optimisation se réfère au problème de trouver la valeur pour laquelle une fonction donnée est maximisée. La planification consiste à décider des actions à entreprendre dans le contexte d'un problème de prise de décision séquentielle. Les deux problèmes sont similaires dans la façon dont ils impliquent la maximisation d'une gratification définie de l'extérieur. Un problème d'optimisation peut être reformulé en un problème de recherche d'arbre en représentant l'espace d'entrée de la fonction d'objectif comme un arbre. De même, un problème de planification peut naturellement s'exprimer sous la forme d'un problème de recherche dans les arbres. C'est pourquoi nous allons essayer de résoudre ces deux problèmes par la recherche dans les arbres. La difficulté de cette recherche réside dans la taille typique de l'arbre pour lequel seule une infime fraction peut être explorée. Notre but est donc de choisir la partie à explorer (ou non) en fonction de la partie déjà visitée 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 de fonctions différentes. D'abord les fonctions de Lipschitz qui sont une classe de fonction lisse par rapport à une métrique, nous montrons comment une fonction de cette classe peut être optimisée avec peu de connaissances préalables. Puis un processus gaussien particulier : le mouvement brownien que nous montrons peut être optimisé en temps sous-polynomial. Dans la deuxième partie, nous nous concentrons sur la planification et présentons un algorithme à nombre polynomial d'échantillons pour une classe particulière de processus décisionnels de Markov (MDP) dans le cadre général de l'apprentissage du renforcement. Nous considérerons également le cas régularisé d'entropie pour lequel nous fournirons un algorithme qui, pour tous les MDPs, jouit d'un nombre d'échantillons polynomial.
M. Aurélien GARIVIER Ecole Normale Supérieure de Lyon Rapporteur M. Matthieu GEIST Université de Lorraine actuellement en détachement auprès de Google Brain. Rapporteur Mme Alexandra CARPENTIER Otto-von-Guericke-Universität Magdeburg Examinateur M. Rémi MUNOS INRIA Lille - Nord Europe actuellement en détachement auprès de DeepMind. Co-directeur de thèse M. Michal VALKO INRIA Lille - Nord Europe actuellement en détachement auprès de DeepMind. Co-directeur de thèse
français
English