# Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 1 Jun 2026.

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

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [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)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [PettingZoo: Gym for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2009.14471/) (2020)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [A Survey of Safe Reinforcement Learning and Constrained MDPs: A Technical Survey on Single-Agent and Multi-Agent Safety](https://mlsanity.com/paper/2505.17342/) (2025)
- [Deep Meta Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2502.04028/) (2025)
- [C-MORL: Multi-Objective Reinforcement Learning through Efficient Discovery of Pareto Front](https://mlsanity.com/paper/2410.02236/) (2024)
- [Multi-agent assignment via state augmented reinforcement learning](https://mlsanity.com/paper/2406.01782/) (2024)
- [Multi-level Advantage Credit Assignment for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2508.06836/) (2025)
- [Cooperative Multi-Agent Assignment over Stochastic Graphs via Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.20462/) (2025)

## Abstract (arXiv)

Constrained Multi-agent reinforcement learning (CMARL) faces two intertwined challenges: the joint action space grows exponentially with the number of agents, and additional requirements couple agents in ways that reward structure alone does not capture. We introduce Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL), a framework that addresses both challenges by combining coordination graphs with Lagrangian duality. The system decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions, one for the primary objective and one for each of the constraints, so that the number of learned models is independent of the number of agents. At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff, allowing a single trained model to trace a Pareto front without retraining. We provide convergence guarantees under mild conditions, together with a compositional error bound that decomposes into separate interpretable sources, each traceable to a specific design choice and independently controllable. Experiments on cooperative navigation tasks (where teams of up to 10 agents must coordinate to reach target positions while satisfying pairwise constraints) show that our method produces Pareto fronts dominating established baselines trained at fixed reward-shaping ratios, while scaling to team sizes where centralized approaches become intractable.