Des méthodes à population pour l’apprentissage par renforcement multiagent
Muller, Paul · HAL (Le Centre pour la Communication Scientifique Directe) · 2022
Cette thèse traite la question du calcul et de l'estimation d'équilibres de théorie des jeux dans des jeux à N-joueurs. Elle se concentre en particulier sur les jeux N-joueurs où N est extrêmement large. Le corps de cette thèse commence par décrire des méthodes permettant de converger vers trois types d'équilibres : corrélés, faiblement-corrélés (coarse-correlated), et alpha-Rank. Ces trois équilibres sont atteints via une altération de PSRO, un algorithme basé sur une population, c'est à dire qui calcule différentes stratégies et une manière optimale de les combiner. Plus spécifiquement, cette altération utilise l'équilibre recherché et un nouveau type d'algorithme calculant une nouvelle stratégie pour atteindre l'équilibre mentionné. Nous prouvons que notre méthode converge vers les équilibres que nous examinons, et élargissons ce résultat à une plus large classe d'équilibres que nous définissons.Ces développements apportent une réponse à la question initiale de la thèse portant sur la convergence vers tout équilibre de théorie des jeux dans tout jeu fini à N-joueurs. Cependant, les méthodes dérivées de PSRO mentionnées plus haut peinent à converger rapidement lorsque N est élevé. Pour des valeurs de N très élevées, il devient presque impossible de trouver des équilibres en un temps raisonnable. La seconde partie de cette thèse porte donc sur la question de contourner la complexité provenant du nombre d'agents, en considérant que leur nombre est en fait infini. Paradoxalement, cette approximation simplifie le calcul d'équilibres parce qu'elle élimine tout effet combinatoire provenant des N joueurs. Nous analysons d'abord ce que deviennent les équilibres (faiblement-) corrélés sous l'approximation des jeux à Champ Moyen (Jeux avec une infinité de joueurs), décrivons leur nouvelle expression, leurs propriétés, et leur comportement lorsqu'ils sont réutilisés dans un jeu à N-joueurs. Etant données des conditions raisonnables, réutiliser un équilibre à Champ Moyen dans un jeu à N-joueurs produit un équilibre (faiblement-) corrélé mathcal{O}left( frac{1}{sqrt{N}} right) -approximatif.La thèse aborde ensuite le sujet de calculer des équilibres (faiblement-) corrélés à Champ Moyen. Elle montre que deux algorithmes populaires convergent vers des équilibres faiblement-corrélés à Champ Moyen, d'une façon inefficace spatialement, via la notion de minimisation de regret à Champ Moyen. Nous définissons ensuite une nouvelle variante de PSRO, PSRO à Champ Moyen, capable de converger vers des équilibres corrélés, faiblement corrélés et de Nash dans tout jeu à Champ Moyen conforme à notre formulation. Ce résultat est obtenu via l'utilisation d'optimiseurs boite-noire pour le Nash; et d'algorithmes sans-regret-adversarial pour les équilibres corrélés et faiblement corrélés. Ces équilibres sont aussi simplifiés via l'utilisation d'un nouvel algorithme de compression, "compression de bandits". Enfin, la thèse est conclue par une application d'équilibres de théorie des jeux dans une situation réelle : les tirs au but, lors de matchs de balle-aux-pieds qui devrait être popularisé pour ce sport populaire, arrivé en Angleterre grâce à la France lors du Camp du Drap d'Or. L'analyse de théorie des jeux sert à analyser l'optimalité des stratégies adoptées par les joueurs, à caractériser les tendances comportementales de chaque joueur, et à leur faire des suggestions afin qu'ils puissent améliorer leurs comportements lors de tirs-aux-but