# Inferring Latent Temporal Sparse Coordination Graph for Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 55 references that are in the map.
- First posted on arXiv 28 Mar 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (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)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Actor-Attention-Critic for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1810.02912/) (2018)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Discrete Graph Structure Learning for Forecasting Multiple Time Series](https://mlsanity.com/paper/2101.06861/) (2021)
- [Graph Convolutional Reinforcement Learning](https://mlsanity.com/paper/1810.09202/) (2018)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [ROMA: Multi-Agent Reinforcement Learning with Emergent Roles](https://mlsanity.com/paper/2003.08039/) (2020)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Learning Nearly Decomposable Value Functions Via Communication Minimization](https://mlsanity.com/paper/1910.05366/) (2019)
- [Multi-Agent Game Abstraction via Graph Attention Neural Network](https://mlsanity.com/paper/1911.10715/) (2019)
- [Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2006.11438/) (2020)
- [Multi-Agent Reinforcement Learning Based Resource Allocation for UAV Networks](https://mlsanity.com/paper/1810.10408/) (2018)
- [PIC: Permutation Invariant Critic for Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1911.00025/) (2019)
- [Learning to Score Behaviors for Guided Policy Optimization](https://mlsanity.com/paper/1906.04349/) (2019)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [DFAC Framework: Factorizing the Value Function via Quantile Mixture for Multi-Agent Distributional Q-Learning](https://mlsanity.com/paper/2102.07936/) (2021)
- [Multivariate Time Series Forecasting with Latent Graph Inference](https://mlsanity.com/paper/2203.03423/) (2022)
- [Self-Organized Polynomial-Time Coordination Graphs](https://mlsanity.com/paper/2112.03547/) (2021)
- [Graph Convolutional Value Decomposition in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2010.04740/) (2020)

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

- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.16606/) (2025)
- [Hierarchical Message-Passing Policies for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2507.23604/) (2025)
- [SDHN: Skewness-Driven Hypergraph Networks for Enhanced Localized Multi-Robot Coordination](https://mlsanity.com/paper/2504.06684/) (2025)
- [A Survey of Multi-Agent Deep Reinforcement Learning with Graph Neural Network-Based Communication](https://mlsanity.com/paper/2604.25972/) (2026)
- [Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.17393/) (2026)
- [Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization](https://mlsanity.com/paper/2610.05270/) (2026)

## Abstract (arXiv)

Effective agent coordination is crucial in cooperative Multi-Agent Reinforcement Learning (MARL). While agent cooperation can be represented by graph structures, prevailing graph learning methods in MARL are limited. They rely solely on one-step observations, neglecting crucial historical experiences, leading to deficient graphs that foster redundant or detrimental information exchanges. Additionally, high computational demands for action-pair calculations in dense graphs impede scalability. To address these challenges, we propose inferring a Latent Temporal Sparse Coordination Graph (LTS-CG) for MARL. The LTS-CG leverages agents' historical observations to calculate an agent-pair probability matrix, where a sparse graph is sampled from and used for knowledge exchange between agents, thereby simultaneously capturing agent dependencies and relation uncertainty. The computational complexity of this procedure is only related to the number of agents. This graph learning process is further augmented by two innovative characteristics: Predict-Future, which enables agents to foresee upcoming observations, and Infer-Present, ensuring a thorough grasp of the environmental context from limited data. These features allow LTS-CG to construct temporal graphs from historical and real-time information, promoting knowledge exchange during policy learning and effective collaboration. Graph learning and agent training occur simultaneously in an end-to-end manner. Our demonstrated results on the StarCraft II benchmark underscore LTS-CG's superior performance.