mlsanityData to 7 Oct 2026

Universally Expressive Communication in Multi-Agent Reinforcement Learning

arXiv 2206.06758 ↗First posted 14 Jun 2022cs.MA cs.DM cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

Allowing agents to share information through communication is crucial for solving complex tasks in multi-agent reinforcement learning. In this work, we consider the question of whether a given communication protocol can express an arbitrary policy. By observing that many existing protocols can be viewed as instances of graph neural networks (GNNs), we demonstrate the equivalence of joint action selection to node labelling. With standard GNN approaches provably limited in their expressive capacity, we draw from existing GNN literature and consider augmenting agent observations with: (1) unique agent IDs and (2) random noise. We provide a theoretical analysis as to how these approaches yield universally expressive communication, and also prove them capable of targeting arbitrary sets of actions for identical agents. Empirically, these augmentations are found to improve performance on tasks where expressive communication is required, whilst, in general, the optimal communication protocol is found to be task-dependent.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 48 of its 76 references that are in the map. First posted on arXiv 14 Jun 2022.

Builds on

48 of 76 references.

References · 48

  1. 2017Graph Attention Networkscited by 8,854
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  6. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  7. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  10. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  11. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  12. 2016Learning to Communicate with Deep Multi-Agent Reinforcement Learningcited by 561
36 more
  1. 2016Learning Multiagent Communication with Backpropagationcited by 355
  2. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 307
  3. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  4. 2020Can Graph Neural Networks Count Substructures?cited by 235
  5. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  6. 2020Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Taskscited by 207
  7. 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
  8. 2018TarMAC: Targeted Multi-Agent Communicationcited by 201
  9. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  10. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  11. 2016Sample Efficient Actor-Critic with Experience Replaycited by 185
  12. 2020Random Features Strengthen Graph Neural Networkscited by 184
  13. 2015Multiagent Cooperation and Competition with Deep Reinforcement Learningcited by 180
  14. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  15. 2018Learning Attentional Communication for Multi-Agent Cooperationcited by 170
  16. 2018Graph Convolutional Reinforcement Learningcited by 148
  17. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  18. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  19. 2018Learning when to Communicate at Scale in Multiagent Cooperative and Competitive Taskscited by 114
  20. 2022A Survey of Multi-Agent Deep Reinforcement Learning with Communicationcited by 103
  21. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 96
  22. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  23. 2017Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Gamescited by 93
  24. 2019Learning to Schedule Communication in Multi-agent Reinforcement Learningcited by 89
  25. 2019Multi-Agent Game Abstraction via Graph Attention Neural Networkcited by 81
  26. 2020Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learningcited by 58
  27. 2018Covariant Compositional Networks For Learning Graphscited by 54
  28. 2019Coloring graph neural networks for node disambiguationcited by 49
  29. 2019Simplified Action Decoder for Deep Multi-Agent Reinforcement Learningcited by 47
  30. 2019Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Controlcited by 46
  31. 2019Learning Transferable Cooperative Behavior in Multi-Agent Teamscited by 40
  32. 2020Succinct and Robust Multi-Agent Communication With Temporal Message Controlcited by 29
  33. 2018Deep Multi-Agent Reinforcement Learning with Relevance Graphscited by 13
  34. 2019Analysing Factorizations of Action-Value Networks for Cooperative Multi-Agent Reinforcement Learningcited by 12
  35. 2020Event-Triggered Multi-agent Reinforcement Learning with Communication under Limited-bandwidth Constraintcited by 10
  36. 2022Remember and Forget Experience Replay for Multi-Agent Reinforcement Learningcited by 2

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Topology Enhanced MARL for Multi-Agent Cooperative Decision-Making of CAVscited by 1
  2. 2025Graph Neural Networks, Deep Reinforcement Learning and Probabilistic Topic Modeling for Strategic Multiagent Settingscited by 0