De la propagation d'une épidémie à l'optimisation du trafic routier, en passant par l'étude des environnements biologiques, les systèmes multi-agent sont omniprésents dans la nature et en ingénierie. Cependant, si les progrès en intelligence artificielle et en particulier en apprentissage par renforcement ont permis de résoudre des jeux complexes tels que le Go, Starcraft et le Poker, les méthodes récentes ont toujours du mal à s'attaquer à des applications de plus d'une douzaine de joueurs. Cette difficulté est connue sous le nom de la malédiction des nombreux agents : quand le nombre d'agents augmente, le jeu devient bien plus difficile à résoudre car le nombre d'interactions à étudier entre les joueurs devient intraitable. Dans cette thèse, nous étudions comment l'apprentissage par renforcement et les jeux à champ moyen peuvent bénéficier mutuellement l'un de l'autre. D'un côté, les jeux à champ moyen peuvent permettre à l'apprentissage par renforcement multi-joueurs de passer à l'échelle en termes de nombre d'agents, étant donné qu'ils comportent par définition une infinité de joueurs. De l'autre côté, l'apprentissage par renforcement s'est avéré efficace pour résoudre des jeux stochastiques et complexes et pourraient ainsi permettre de trouver des équilibres de Nash dans des jeux à champ moyen compliqués, sans avoir à connaître le modèle ou à résoudre un système forward-backward d'équations stochastiques ou aux dérivées partielles. Au cours de cette dissertation, nous définissons précisément les jeux à champ moyen, les processus décisionnels de Markov et l'apprentissage par renforcement, avant de détailler les différentes configurations que le lecteur peut rencontrer en cherchant à entremêler l'apprentissage par renforcement avec les jeux à champ moyen. Puis, nous présentons une approche unifiée des algorithmes, aussi appelés méthodes itératives, servant à résoudre des jeux à champ moyen, soit à l'aide de la programmation dynamique quand le modèle est connu, soit avec de l'apprentissage par renforcement lorsqu'il ne l'est pas. Puis, nous zoomons sur deux méthodes itératives : Fictitious Play (FP) et Online Mirror Descent (OMD). Nous prouvons leur convergence vers l'équilibre de Nash sous la condition de monotonicité dans le cas exact, avec ou sans bruit commun, dans des jeux à champ moyen à une ou plusieurs populations. Nous démontrons numériquement leur convergence dans un large set d'exemples et soulignons qu'OMD converge plus rapidement. Dans la dernière partie, nous proposons trois contributions démontrant que l'apprentissage par renforcement profond peut résoudre des jeux à champ moyen. La première présente comment des agents qui utilisent ce paradigme apprennent à se regrouper ensemble, dans un environnement continu et multi-dimensionnel. Puis, nous nous attaquons à la généralisation par rapport à la distribution initiale, et démontrons que l'apprentissage par renforcement profond permet le calcul de politiques population-dépendantes. Enfin, nous proposons deux algorithmes permettant à FP et OMD de passer à l'échelle, ne requérant pas de sommer ou moyenner des réseaux de neurones.
M. Olivier PIETQUIN ULille, Google Research Directeur de thèse M. Romuald ÉLIE Université Gustave Eiffel, DeepMind Co-directeur de thèse M. François CHARPILLET Inria, CNRS, Université de Lorraine Examinateur Mme Émilie KAUFMANN CNRS, Inria Examinatrice M. François DELARUE Université Côte d'Azur Rapporteur M. Marcello RESTELLI Politecnico di Milano Rapporteur M. Matthieu GEIST Université de Lorraine, Google Research Invité M. Gergely NEU Universitat Pompeu Fabra Invité
Thèse de l'équipe SCOOL soutenue le 08/12/2022
français
English