# Breaking the Curse of Dimensionality in Multiagent State Space: A Unified Agent Permutation Framework

arXiv: https://arxiv.org/abs/2203.05285 · HTML: https://mlsanity.com/paper/2203.05285/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 34 references that are in the map.
- First posted on arXiv 10 Mar 2022.

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [Google Research Football: A Novel Reinforcement Learning Environment](https://mlsanity.com/paper/1907.11180/) (2019)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Graph Convolutional Reinforcement Learning](https://mlsanity.com/paper/1810.09202/) (2018)
- [Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks](https://mlsanity.com/paper/1810.00825/) (2018)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Celebrating Diversity in Shared Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.02195/) (2021)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Evolutionary Population Curriculum for Scaling Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.10423/) (2020)
- [PIC: Permutation Invariant Critic for Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1911.00025/) (2019)
- [Guided Deep Reinforcement Learning for Swarm Systems](https://mlsanity.com/paper/1709.06011/) (2017)
- [UPDeT: Universal Multi-agent Reinforcement Learning via Policy Decoupling with Transformers](https://mlsanity.com/paper/2101.08001/) (2021)
- [From Few to More: Large-scale Dynamic Multiagent Curriculum Learning](https://mlsanity.com/paper/1909.02790/) (2019)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [Multi-Agent MDP Homomorphic Networks](https://mlsanity.com/paper/2110.04495/) (2021)
- [Action Semantics Network: Considering the Effects of Actions in Multiagent Systems](https://mlsanity.com/paper/1907.11461/) (2019)
- [Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach](https://mlsanity.com/paper/2105.08268/) (2021)
- [Multi-Agent Policy Transfer via Task Relationship Modeling](https://mlsanity.com/paper/2203.04482/) (2022)
- [Experience Augmentation: Boosting and Accelerating Off-Policy Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2005.09453/) (2020)

## Built on by (most cited first, 6 of 6)

- [Combining Transformer based Deep Reinforcement Learning with Black-Litterman Model for Portfolio Optimization](https://mlsanity.com/paper/2402.16609/) (2024)
- [Heterogeneous Multi-Agent Reinforcement Learning for Zero-Shot Scalable Collaboration](https://mlsanity.com/paper/2404.03869/) (2024)
- [Knowing What Not to Do: Leverage Language Model Insights for Action Space Pruning in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2405.16854/) (2024)
- [A novel multi-agent dynamic portfolio optimization learning system based on hierarchical deep reinforcement learning](https://mlsanity.com/paper/2501.06832/) (2025)
- [Emergent Heterogeneous Swarm Control Through Hebbian Learning](https://mlsanity.com/paper/2507.11566/) (2025)
- [Wireless Communication Enhanced Value Decomposition for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2604.08728/) (2026)

## Abstract (arXiv)

The state space in Multiagent Reinforcement Learning (MARL) grows exponentially with the agent number. Such a curse of dimensionality results in poor scalability and low sample efficiency, inhibiting MARL for decades. To break this curse, we propose a unified agent permutation framework that exploits the permutation invariance (PI) and permutation equivariance (PE) inductive biases to reduce the multiagent state space. Our insight is that permuting the order of entities in the factored multiagent state space does not change the information. Specifically, we propose two novel implementations: a Dynamic Permutation Network (DPN) and a Hyper Policy Network (HPN). The core idea is to build separate entity-wise PI input and PE output network modules to connect the entity-factored state space and action space in an end-to-end way. DPN achieves such connections by two separate module selection networks, which consistently assign the same input module to the same input entity (guarantee PI) and assign the same output module to the same entity-related output (guarantee PE). To enhance the representation capability, HPN replaces the module selection networks of DPN with hypernetworks to directly generate the corresponding module weights. Extensive experiments in SMAC, Google Research Football and MPE validate that the proposed methods significantly boost the performance and the learning efficiency of existing MARL algorithms. Remarkably, in SMAC, we achieve 100% win rates in almost all hard and super-hard scenarios (never achieved before).