# Non-Linear Coordination Graphs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 49 references that are in the map.
- First posted on arXiv 26 Oct 2022.

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

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [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)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [ROMA: Multi-Agent Reinforcement Learning with Emergent Roles](https://mlsanity.com/paper/2003.08039/) (2020)
- [RODE: Learning Roles to Decompose Multi-Agent Tasks](https://mlsanity.com/paper/2010.01523/) (2020)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Off-Policy Multi-Agent Decomposed Policy Gradients](https://mlsanity.com/paper/2007.12322/) (2020)
- [Celebrating Diversity in Shared Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.02195/) (2021)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Learning Nearly Decomposable Value Functions Via Communication Minimization](https://mlsanity.com/paper/1910.05366/) (2019)
- [Influence-Based Multi-Agent Exploration](https://mlsanity.com/paper/1910.05512/) (2019)
- [Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2006.11438/) (2020)
- [Exact and Consistent Interpretation for Piecewise Linear Neural Networks: A Closed Form Solution](https://mlsanity.com/paper/1802.06259/) (2018)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [Cooperative and Distributed Reinforcement Learning of Drones for Field Coverage](https://mlsanity.com/paper/1803.07250/) (2018)
- [Self-Organized Polynomial-Time Coordination Graphs](https://mlsanity.com/paper/2112.03547/) (2021)
- [Analysing Factorizations of Action-Value Networks for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1902.07497/) (2019)
- [Multi-vehicle Flocking Control with Deep Deterministic Policy Gradient Method](https://mlsanity.com/paper/1806.00196/) (2018)

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

- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Towards Foundation-model-based Multiagent System to Accelerate AI for Social Impact](https://mlsanity.com/paper/2412.07880/) (2024)
- [Semantically Aligned Task Decomposition in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.10865/) (2023)
- [Roadmap on Incentive Compatibility for AI Alignment and Governance in Sociotechnical Systems](https://mlsanity.com/paper/2402.12907/) (2024)
- [Deep Meta Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2502.04028/) (2025)
- [Social Environment Design](https://mlsanity.com/paper/2402.14090/) (2024)
- [Action-Graph Policies: Learning Action Co-dependencies in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.17009/) (2026)
- [A Recipe for Stable Offline Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2603.08399/) (2026)
- [Do LLM-derived graph priors improve multi-agent coordination?](https://mlsanity.com/paper/2604.17191/) (2026)
- [SACHI: Structured Agent Coordination via Holistic Information Integration in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.08391/) (2026)

## Abstract (arXiv)

Value decomposition multi-agent reinforcement learning methods learn the global value function as a mixing of each agent's individual utility functions. Coordination graphs (CGs) represent a higher-order decomposition by incorporating pairwise payoff functions and thus is supposed to have a more powerful representational capacity. However, CGs decompose the global value function linearly over local value functions, severely limiting the complexity of the value function class that can be represented. In this paper, we propose the first non-linear coordination graph by extending CG value decomposition beyond the linear case. One major challenge is to conduct greedy action selections in this new function class to which commonly adopted DCOP algorithms are no longer applicable. We study how to solve this problem when mixing networks with LeakyReLU activation are used. An enumeration method with a global optimality guarantee is proposed and motivates an efficient iterative optimization method with a local optimality guarantee. We find that our method can achieve superior performance on challenging multi-agent coordination tasks like MACO.