Agent abstraction in multi-agent reinforcement learning

Abstract

Cette thèse est organisée en deux chapitres. Le premier chapitre sert d’introduction aux concepts et idées utilisés dans le deuxième chapitre (l’article). Le premier chapitre est divisé en trois sections. Dans la première section, nous introduisons l’apprentissage par renforcement en tant que paradigme d’apprentissage automatique et montrons comment ses problèmes sont formalisés à l’aide de processus décisionnels de Markov. Nous formalisons les buts sous forme de rendements attendus et montrons comment les équations de Bellman utilisent la formulation récursive du rendement pour établir une relation entre les valeurs de deux états successifs sous la politique de l’agent. Après cela, nous soutenons que la résolution des équations d’optimalité de Bellman est insoluble et introduisons des algorithmes basés sur des valeurs tels que la programmation dynamique, les méthodes de Monte Carlo et les méthodes de différence temporelle qui se rapprochent de la solution optimale à l’aide de l’itération de politique généralisée. L’approximation de fonctions est ensuite proposée comme moyen de traiter les grands espaces d’états. Nous discutons également de la manière dont les méthodes basées sur les politiques optimisent directement la politique sans optimiser la fonction de valeur. Dans la deuxième section, nous introduisons les jeux de Markov comme une extension des processus décisionnels de Markov pour plusieurs agents. Nous couvrons les différents cadres formés par les différentes structures de récompense et donnons les dilemmes sociaux séquentiels comme exemple du cadre d’incitation mixte. En fin de compte, nous introduisons différentes structures d’information telles que l’apprentissage centralisé qui peuvent aider à faire face à la non-stationnarité in- duite par l’adversaire. Enfin, dans la troisième section, nous donnons un bref aperçu des types d’abstraction d’état et introduisons les métriques de bisimulation comme un concept inspiré de l’abstraction de non-pertinence du modèle qui mesure la similarité entre les états. Dans le deuxième chapitre (l’article), nous approfondissons finalement l’abstraction d’agent en tant que métrique de bisimulation et dérivons un facteur de compression que nous pouvons appliquer à la diplomatie pour révéler l’agence supérieure sur les unités de joueur.

This thesis is organized into two chapters. The first chapter serves as an introduction to the concepts and ideas used in the second chapter (the article). The first chapter is divided into three sections. In the first section, we introduce Reinforcement Learning as a Machine Learning paradigm and show how its problems are formalized using Markov Decision Processes. We formalize goals as expected returns and show how the Bellman equations use the recursive formulation of return to establish a relation between the values of two successive states under the agent’s policy. After that, we argue that solving the Bellman optimality equations is intractable and introduce value-based algorithms such as Dynamic Programming, Monte Carlo methods, and Temporal Difference methods that approximate the optimal solution using Generalized Policy Iteration. Function approximation is then proposed as a way of dealing with large state spaces. We also discuss how policy-based methods optimize the policy directly without optimizing the value function. In the second section, we introduce Markov Games as an extension of Markov Decision Processes for multiple agents. We cover the different settings formed by the different reward structures and give Sequential Social Dilemmas as an example of the mixed-incentive setting. In the end, we introduce different information structures such as centralized learning that can help deal with the opponent-induced non-stationarity. Finally, in the third section, we give a brief overview of state abstraction types and introduce bisimulation metrics as a concept inspired by model-irrelevance abstraction that measures the similarity between states. In the second chapter (the article), we ultimately delve into agent abstraction as a bisimulation metric and derive a compression factor that we can apply to Diplomacy to reveal the higher agency over the player units.