# Scaling Team Coordination on Graphs with Reinforcement Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 9 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [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)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [A Closer Look at Invalid Action Masking in Policy Gradient Algorithms](https://mlsanity.com/paper/2006.14171/) (2020)
- [Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Control](https://mlsanity.com/paper/1903.04527/) (2019)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2006.11438/) (2020)
- [Autonomous Visual Assistance for Robot Operations Using a Tethered UAV](https://mlsanity.com/paper/1904.00078/) (2019)
- [Team Orienteering Coverage Planning with Uncertain Reward](https://mlsanity.com/paper/2105.03721/) (2021)
- [Team Coordination on Graphs with State-Dependent Edge Cost](https://mlsanity.com/paper/2303.11457/) (2023)
- [Multi-Agent Chance-Constrained Stochastic Shortest Path with Application to Risk-Aware Intelligent Intersection](https://mlsanity.com/paper/2210.01766/) (2022)

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

- [Grounded Curriculum Learning](https://mlsanity.com/paper/2409.19816/) (2024)
- [GACL: Grounded Adaptive Curriculum Learning with Active Task and Performance Monitoring](https://mlsanity.com/paper/2508.02988/) (2025)
- [CARoL: Context-aware Adaptation for Robot Learning](https://mlsanity.com/paper/2506.07006/) (2025)

## Abstract (arXiv)

This paper studies Reinforcement Learning (RL) techniques to enable team coordination behaviors in graph environments with support actions among teammates to reduce the costs of traversing certain risky edges in a centralized manner. While classical approaches can solve this non-standard multi-agent path planning problem by converting the original Environment Graph (EG) into a Joint State Graph (JSG) to implicitly incorporate the support actions, those methods do not scale well to large graphs and teams. To address this curse of dimensionality, we propose to use RL to enable agents to learn such graph traversal and teammate supporting behaviors in a data-driven manner. Specifically, through a new formulation of the team coordination on graphs with risky edges problem into Markov Decision Processes (MDPs) with a novel state and action space, we investigate how RL can solve it in two paradigms: First, we use RL for a team of agents to learn how to coordinate and reach the goal with minimal cost on a single EG. We show that RL efficiently solves problems with up to 20/4 or 25/3 nodes/agents, using a fraction of the time needed for JSG to solve such complex problems; Second, we learn a general RL policy for any N-node EGs to produce efficient supporting behaviors. We present extensive experiments and compare our RL approaches against their classical counterparts.