Cette thèse est structurée en quatre sections. La première constitue une introduction au problème de la formation d'agents coopératifs non exploitables dans les jeux à somme non nulle. La deuxième section, soit le premier chapitre, fournit le contexte nécessaire pour discuter de l'étendue et des outils mathématiques requis pour explorer ce problème. La troisième section, correspondant au deuxième chapitre, expose un cadre spécifique, nommé Best Response Shaping, que nous avons élaboré pour relever ce défi. La quatrième section contient les conclusions que nous tirons de ce travail et nous y discutons des travaux futurs potentiels.
Le chapitre introductif se divise en quatre sections. Dans la première, nous présentons le cadre d'apprentissage par renforcement (Reinforcement Learning) afin de formaliser le problème d'un agent interagissant avec l'environnement pour maximiser une récompense scalaire. Nous introduisons ensuite les Processus Décisionnels de Markov (Markov Decision Processes) en tant qu'outil mathématique pour formaliser le problème d'apprentissage par renforcement. Nous discutons de deux méthodes générales de solution pour résoudre le problème d'apprentissage par renforcement. Les premières sont des méthodes basées sur la valeur qui estiment la récompense cumulée optimale réalisable pour chaque paire action-état, et la politique serait alors apprise. Les secondes sont des méthodes basées sur les politiques où la politique est optimisée directement sans estimer les valeurs. Dans la deuxième section, nous introduisons le cadre d'apprentissage par renforcement multi-agents (Multi-Agent Reinforcement Learning) pour formaliser le problème de plusieurs agents tentant de maximiser une récompense cumulative scalaire dans un environnement partagé. Nous présentons les Jeux Stochastiques comme une extension théorique du processus de décision de Markov pour permettre la présence de plusieurs agents. Nous discutons des trois types de jeux possibles entre agents en fonction de la structure de leur système de récompense. Nous traitons des défis spécifiques à l'apprentissage par renforcement multi-agents. En particulier, nous examinons le défi de l'apprentissage par renforcement profond multi-agents dans des environnements partiellement compétitifs, où les méthodes traditionnelles peinent à promouvoir une coopération non exploitable. Dans la troisième section, nous introduisons le Dilemme du prisonnier itéré (Iterated Prisoner's Dilemma) comme un jeu matriciel simple utilisé comme exemple de jouet pour étudier les dilemmes sociaux. Dans la quatrième section, nous présentons le Coin Game comme un jeu à haute dimension qui doit être résolu grâce à des politiques paramétrées par des réseaux de neurones.
Dans le deuxième chapitre, nous introduisons la méthode Forme de la Meilleure Réponse (Best Response Shaping). Des approches existantes, comme celles des agents LOLA et POLA, apprennent des politiques coopératives non exploitables en se différenciant grâce à des étapes d'optimisation prédictives de leur adversaire. Toutefois, ces techniques présentent une limitation majeure car elles sont susceptibles d'être exploitées par une optimisation supplémentaire. En réponse à cela, nous introduisons une nouvelle approche, Forme de la Meilleure Réponse, qui se différencie par le fait qu'un adversaire approxime la meilleure réponse, que nous appelons le "détective". Pour conditionner le détective sur la politique de l'agent dans les jeux complexes, nous proposons un mécanisme de conditionnement différenciable sensible à l'état, facilité par une méthode de questions-réponses (QA) qui extrait une représentation de l'agent basée sur son comportement dans des états d'environnement spécifiques. Pour valider empiriquement notre méthode, nous mettons en évidence sa performance améliorée face à un adversaire utilisant l'Arbre de Recherche Monte Carlo (Monte Carlo Tree Search), qui sert d'approximation de la meilleure réponse dans le Coin Game. / This thesis is organized in four sections.The first is an introduction to the problem of training non-exploitable cooperative agents in general-sum games. The second section, the first chapter, provides the necessary background for discussing the scope and necessary mathematical tools for exploring this problem. The third section, the second chapter, explains a particular framework, Best Response Shaping, that we developed for tackling this challenge. In the fourth section, is the conclusion that we drive from this work and we discuss the possible future works.
The background chapter consists of four section. In the first section, we introduce the \emph{Reinforcement Learning } framework for formalizing the problem of an agent interacting with the environment maximizing a scalar reward. We then introduce \emph{Markov Decision Processes} as a mathematical tool to formalize the Reinforcement Learning problem. We discuss two general solution methods for solving the Reinforcement Learning problem. The first are Value-based methods that estimate the optimal achievable accumulative reward in each action-state pair and the policy would be learned. The second are Policy-based methods where the policy is optimized directly without estimating the values. In the second section, we introduce \emph{Multi-Agent Reinforcement Learning} framework for formalizing multiple agents trying to maximize a scalar accumulative reward in a shared environment. We introduce \emph{Stochastic Games} as a theoretical extension of the Markov Decision Process to allow multiple agents. We discuss the three types of possible games between agents based on the setup of their reward structure. We discuss the challenges that are specific to Multi-Agent Reinforcement Learning. In particular, we investigate the challenge of multi-agent deep reinforcement learning in partially competitive environments, where traditional methods struggle to foster non-exploitable cooperation. In the third section, we introduce the \emph{Iterated Prisoner's Dilemma} game as a simple matrix game used as a toy-example for studying social dilemmas. In the Fourth section, we introduce the \emph{Coin Game} as a high-dimensional game that should be solved via policies parameterized by neural networks.
In the second chapter, we introduce the Best Response Shaping (BRS) method. The existing approaches like LOLA and POLA agents learn non-exploitable cooperative policies by differentiation through look-ahead optimization steps of their opponent. However, there is a key limitation in these techniques as they are susceptible to exploitation by further optimization. In response, we introduce a novel approach, Best Response Shaping (BRS), which differentiates through an opponent approximating the best response, termed the "detective." To condition the detective on the agent's policy for complex games we propose a state-aware differentiable conditioning mechanism, facilitated by a question answering (QA) method that extracts a representation of the agent based on its behaviour on specific environment states. To empirically validate our method, we showcase its enhanced performance against a Monte Carlo Tree Search (MCTS) opponent, which serves as an approximation to the best response in the Coin Game.
This work expands the applicability of multi-agent RL in partially competitive environments and provides a new pathway towards achieving improved social welfare in general sum games.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/32217 |
| Date | 07 1900 |
| Creators | Aghajohari, Milad |
| Contributors | Courville, Aaron |
| Source Sets | Université de Montréal |
| Language | English |
| Detected Language | French |
| Type | thesis, thèse |
| Format | application/pdf |
Page generated in 0.011 seconds