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