Sur le Gradient de la Politique pour les Systèmes Multi-Agents Coopératifs

Guillaume Bono, Jilles Steeve Dibangoye, Laëtitia Matignon, Florian Pereyron, Olivier Simonin

TL;DR

This paper tackles the challenge of decentralized multi-agent reinforcement learning (RL) by extending policy gradient methods to Dec-POMDPs under a centralized training with decentralized execution (CTDC) paradigm. They introduce theoretical foundations and an actor-critic algorithm (ACDC) that learns decentralized policies from collective experiences, showing competitive performance against existing methods.

What Problem Does This Paper Address?

Reinforcement learning (RL) has seen remarkable progress in single-agent settings, but its application to decentralized partially observable Markov decision processes (Dec-POMDPs) lags behind. This is largely due to assumptions that hold for single agents but break down in multi-agent systems, particularly regarding partial observability and decentralized execution. Existing multi-agent RL often either assumes full observability or requires agents to act identically during training and execution. This paper addresses this gap by exploring the CTDC paradigm, where learning can occur centrally, but agents must execute their policies independently. This allows for leveraging richer information during training while maintaining decentralized control at deployment, a more realistic scenario for many applications.

Methods

The core contribution lies in extending the theoretical underpinnings of policy gradient methods to Dec-POMDPs within the CTDC framework. The authors generalize the policy gradient theorem and compatible function approximation theorems from single-agent MDPs to multi-agent Dec-POMDPs. They establish that a centralized critic can be compatible with decentralized policies if it decomposes into a sum of individual critics, which are linear combinations of individual policy features. This theoretical work leads to the development of an Actor-Critic for Decentralized Control (ACDC) algorithm. ACDC uses a centralized critic to guide the learning of individual decentralized actors. The algorithm is iterative, involving policy evaluation (collecting trajectories) and improvement (updating actor and critic parameters). They also propose a natural actor-critic variant (NACDC) for potentially faster convergence.

Datasets

The paper evaluates their ACDC algorithm on several standard Dec-POMDP benchmarks from the literature: Dec. Tiger, Broadcast Channel, Mars, Box Pushing, Meeting in a Grid, and Recycling Robots. They also compare their results against planning algorithms like FB-HSVI and MCEM.

Key Insights and Ideas

  • CTDC is a powerful paradigm for Dec-POMDPs: The ability to train centrally while executing decentrally offers a significant advantage, allowing for richer data utilization without compromising independent action.
  • Theoretical foundations for multi-agent policy gradients are crucial: Extending single-agent theorems to the multi-agent setting provides the necessary rigor for developing effective algorithms.
  • Compatible approximations are key to decentralized learning: The paper highlights how compatible approximations of value functions enable decentralized policy updates while maintaining theoretical guarantees.
  • RNNs offer superior history representation: For complex tasks, recurrent neural networks (RNNs) as internal state representations significantly outperform truncated history approaches, suggesting their importance in capturing nuanced temporal dependencies.
  • Centralized critic is separable: The theoretical work shows that the centralized critic can be decomposed into individual critics, which is crucial for scaling to a larger number of agents.

Key Results

The experimental results demonstrate that the CTDC paradigm, implemented through their ACDC algorithm, generally outperforms CTCC and DTDC across various benchmarks and horizons. ACDC shows competitive performance compared to state-of-the-art methods like MCEM. Specifically, for shorter horizons, ACDC with RNNs converges faster and to better solutions than truncated history representations. The paper also notes that while ACDC performs well, there's still room for improvement, particularly in achieving global optima due to the inherent limitations of policy gradient methods and the challenge of perfectly compressing agent histories.

Limitations and Future Work

The authors acknowledge several limitations. The current implementation of ACDC faces the well-known exploration-exploitation trade-off. Furthermore, the representation of individual agent histories remains a challenge; learning to project these histories into states close to individual occupation states is an open problem. They also mention that while ACDC can be made to run distributively, the current implementation is centralized. Future work will focus on addressing the history representation problem and exploring the scalability of ACDC by leveraging the separability of the compatible joint critic for large-scale decentralized multi-agent applications.

Summary updated

Abstract

L'apprentissage par renforcement (RL) pour les processus décisionnels de Markov partiellement observables décentralisés (Dec-POMDPs) accuse un certain retard par rapport aux progrès spectaculaires du RL mono-agent. Ceci s'explique en partie par un certain nombre d'hypothèses valables dans le cadre mono-agent, mais invalides dans les systèmes multi-agents. Pour combler ce retard, nous explorons les fondements mathématiques des méthodes par ascension du gradient de la politique dans le paradigme de l'entraînement centralisé pour un contrôle décentralisé (CTDC). Dans ce paradigme, l'apprentissage peut avoir lieu de façon centralisée tout en gardant la contrainte d'une exécution décentralisée. En partant de cette intuition , nous établissons dans ce document une extension multi-agents du théorème du gradient de la politique et du théorème de compatibilité des fonctions d'approximation de la valeur. Nous en tirons des méthodes « acteur critique » (AC) qui parviennent (i) à estimer le gradient de la politique à partir d'expériences collectives mais aussi (ii) à préserver le contrôle décentralisé du système à l'exécution. Nos expérimentations montrent que nos méthodes ne souffrent pas de la comparaison avec les techniques standard en RL sur un ensemble de bancs de test de la littérature.
BibTeX
@inproceedings{bono2018sur,
  author = {Guillaume Bono and Jilles Steeve Dibangoye and Laëtitia Matignon and Florian Pereyron and Olivier Simonin},
  title = {{Sur le Gradient de la Politique pour les Systèmes Multi-Agents Coopératifs}},
  booktitle = {HAL},
  year = {2018},
}

Loading related content...

Figure