Intitulé de la thèse : Regrets optimaux dans les processus de décision Markoviens
Les processus de décisions Markoviens sont une manière naturelle de modéliser l’interaction entre un agent et son environnement qu’il est pertinent de penser comme un jeu où, à tout instant, l’agent est un joueur qui observe son environnement dans son intégralité et prend une décision en conséquence. Cette décision consiste en le choix d’une « action » qui a deux conséquences notables : elle influe sur la manière dont l’environnement évolue (changement d’état) et sur la récompense que l’agent obtient. L’objectif de l’agent est de jouer les bonnes actions pour obtenir autant de récompenses que possible.Dans cette thèse, on s’intéresse au problème où l’agent observe le système dans son intégralité mais n’en connaît pas les rouages. Plus précisément, il doit apprendre les effets de chacune des actions en fonction de l’état de son environnement. Préfère-t-on choisir une action qui semble avoir été la meilleure jusqu’alors ? Ou, faut-il considérer cette autre action qui a été mauvaise jusqu’ici, mais qui peut tout-à-fait avoir été mauvaise faute de malchance ? Ce dilemme est appelé le « dilemme d’exploitation-exploration » et trouver le juste équilibre entre ces deux choix est le cœur de ce style de problème d’apprentissage.
L’objectif de cette thèse est la conception d’algorithmes qui gèrent le dilemme d’exploitation-exploration de manière optimale. Le prisme est essentiellement théorique et l’approche est systématique : On commence par montrer qu’aucun agent ne peut apprendre « trop vite » en décrivant une borne inférieure sur les performances possibles, puis, fort de cette borne inférieure, on construit un algorithme d’apprentissage qui l’atteint. Cette approche est employée dans les deux variations principales de ce problème (l’analyse à modèle fixé et l’analyse pire cas). Au-delà des performances moyennes, on s’intéresse également au comportement temporel local des algorithmes d’apprentissage classiques et on introduit de nouvelles métriques pour les quantifier.
Mots clés : Intelligence artificielle, Apprentissage par renforcement, Processus de décision markoviens, Regret
École doctorale : ED MSTII – Mathématiques, Sciences et Technologies de l'Information, Informatique
Laboratoire d’accueil : Laboratoire d'informatique de Grenoble (LIG - CNRS/Inria/UGA - Grenoble INP-UGA )
Direction de thèse : Bruno GAUJAL
> Pour connaitre tous les prix de thèse 2025