Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach

Yan Li, Lingxiao Wang, Jiachen Yang, Ethan Wang, Zhaoran Wang, Tuo Zhao, Hongyuan Zha

TL;DR

This paper tackles the "curse of many agents" in multi-agent reinforcement learning (MARL) by introducing a principled approach called Mean-Field Proximal Policy Optimization (MF-PPO). MF-PPO leverages permutation invariance in cooperative MARL problems, formulating them as mean-field MDPs and employing a novel permutation-invariant actor-critic architecture. This leads to provably optimal policies with sample complexity independent of the number of agents, outperforming existing methods in experiments.

What Problem Does This Paper Address?

Multi-agent reinforcement learning (MARL) aims to train multiple agents to cooperate or compete in a shared environment. A major hurdle is the "curse of many agents," where the complexity of the joint state and action spaces grows exponentially with the number of agents, making learning intractable. This paper focuses on cooperative MARL settings where agents are homogeneous and their identities don't matter (permutation invariance). The challenge is to develop MARL algorithms that can scale to a large or even infinite number of agents while still finding optimal policies efficiently.

Methods

The authors propose Mean-Field Proximal Policy Optimization (MF-PPO), an actor-critic algorithm designed for cooperative MARL with permutation invariance.

  • Mean-Field MDP Formulation: They reformulate the problem as a mean-field Markov Decision Process (MDP). In this formulation, an agent's state includes its local state and a distribution representing the states of all other agents. This allows for a more tractable representation of large-scale MARL systems.
  • Permutation Invariant Actor-Critic Architecture: The core innovation is a permutation-invariant neural network architecture for both the actor (policy) and critic (value function). This architecture, inspired by Deep Sets, ensures that the network's output is invariant to the order of agent inputs. This inductive bias drastically reduces the search space for policies and value functions from exponential to polynomial dependence on the number of agents.
  • Theoretical Guarantees: MF-PPO is theoretically proven to converge to the globally optimal policy for the mean-field MDP with a sublinear rate. Crucially, its sample complexity is independent of the number of agents, meaning it scales well with more agents.

Datasets

The authors evaluate their MF-PPO algorithm on the Multi-Agent Particle Environment (MPE), a standard benchmark for MARL research. They specifically use the cooperative navigation and cooperative push tasks within MPE.

Key Insights and Ideas

  • Permutation Invariance as a Scalability Lever: The paper demonstrates that exploiting permutation invariance in cooperative MARL is not just a theoretical curiosity but a practical necessity for scaling to many agents. This invariance allows for a significant reduction in the complexity of learning.
  • Mean-Field as a Natural Extension: Formulating the problem as a mean-field MDP provides a principled way to handle a large number of homogeneous agents, treating their collective behavior as a distribution.
  • Inductive Bias for Efficiency: The permutation-invariant neural architecture acts as a powerful inductive bias. This bias not only reduces model complexity but also leads to better generalization and performance, as shown in experiments.
  • "Blessing of Many Agents": Contrary to the "curse of many agents," the paper's theoretical results suggest that in this specific mean-field setting, having more agents can actually be beneficial for learning efficiency and convergence.

Key Results

  • Theoretical Convergence: MF-PPO is proven to converge to the optimal policy for the mean-field MDP with a sublinear rate.
  • Agent-Independent Sample Complexity: The algorithm's sample complexity does not depend on the number of agents, making it highly scalable.
  • Empirical Performance: In the MPE benchmark, MF-PPO significantly outperforms existing methods (MLP, GCN, MF-A) across various numbers of agents (N=6, 15, 30, 200).
  • Parameter Efficiency: MF-PPO achieves higher performance with fewer model parameters compared to competitors like GCN, highlighting the effectiveness of its permutation-invariant architecture. For instance, Figure 4a shows MF outperforming GCN even with fewer parameters.

Limitations and Future Work

  • Computational Cost: While sample complexity is independent of the number of agents, the computational cost per update can still be significant, especially with a large number of agents. The authors mention that dual embedding techniques could be incorporated to improve computational efficiency by sampling agents.
  • Homogeneous Agents: The current framework is primarily designed for homogeneous agents. Extending it to heterogeneous agents or mixed cooperative-competitive settings would be a valuable future direction.
  • Theoretical Analysis Complexity: The theoretical analysis of convergence is complex, involving detailed proofs of policy evaluation and improvement steps, and relies on assumptions about network width and function class richness.

The authors suggest that their work provides a principled foundation for scalable MARL and opens avenues for further research into efficient and provably convergent MARL algorithms.

Summary updated

Abstract

Multi-agent reinforcement learning (MARL) becomes more challenging in the presence of more agents, as the capacity of the joint state and action spaces grows exponentially in the number of agents. To address such a challenge of scale, we identify a class of cooperative MARL problems with permutation invariance, and formulate it as a mean-field Markov decision processes (MDP). To exploit the permutation invariance therein, we propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. Moreover, its sample complexity is independent of the number of agents. We validate the theoretical advantages of MF-PPO with numerical experiments in the multi-agent particle environment (MPE). In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors with a smaller number of model parameters, which is the key to its generalization performance.
BibTeX
@inproceedings{li2022permutation,
  author = {Yan Li and Lingxiao Wang and Jiachen Yang and Ethan Wang and Zhaoran Wang and Tuo Zhao and Hongyuan Zha},
  title = {{Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=H4J8FGHOhx_},
}
Figure