# Communication Gain and Delay Cost Under Cross-Timestep Delays in Cooperative Multi-Agent Reinforcement Learning

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

## Key facts

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

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

- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [Emergence of Grounded Compositional Language in Multi-Agent Populations](https://mlsanity.com/paper/1703.04908/) (2017)
- [TarMAC: Targeted Multi-Agent Communication](https://mlsanity.com/paper/1810.11187/) (2018)
- [Learning Attentional Communication for Multi-Agent Cooperation](https://mlsanity.com/paper/1805.07733/) (2018)
- [Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games](https://mlsanity.com/paper/1703.10069/) (2017)
- [Learning to Schedule Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1902.01554/) (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)
- [Learning Efficient Multi-agent Communication: An Information Bottleneck Approach](https://mlsanity.com/paper/1911.06992/) (2019)
- [Learning Individually Inferred Communication for Multi-Agent Cooperation](https://mlsanity.com/paper/2006.06455/) (2020)
- [Multi-agent Reinforcement Learning for Networked System Control](https://mlsanity.com/paper/2004.01339/) (2020)
- [Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Control](https://mlsanity.com/paper/1909.02682/) (2019)
- [Learning Transferable Cooperative Behavior in Multi-Agent Teams](https://mlsanity.com/paper/1906.01202/) (2019)
- [Learning to Ground Multi-Agent Communication with Autoencoders](https://mlsanity.com/paper/2110.15349/) (2021)
- [Scalable Multi-Agent Reinforcement Learning through Intelligent Information Aggregation](https://mlsanity.com/paper/2211.02127/) (2022)
- [Learning Agent Communication under Limited Bandwidth by Message Pruning](https://mlsanity.com/paper/1912.05304/) (2019)
- [Succinct and Robust Multi-Agent Communication With Temporal Message Control](https://mlsanity.com/paper/2010.14391/) (2020)
- [Mis-spoke or mis-lead: Achieving Robustness in Multi-Agent Communicative Reinforcement Learning](https://mlsanity.com/paper/2108.03803/) (2021)
- [Message-Dropout: An Efficient Training Method for Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1902.06527/) (2019)
- [Multi-Agent Coordination via Multi-Level Communication](https://mlsanity.com/paper/2209.12713/) (2022)
- [T2MAC: Targeted and Trusted Multi-Agent Communication through Selective Engagement and Evidence-Driven Integration](https://mlsanity.com/paper/2401.10973/) (2024)
- [DACOM: Learning Delay-Aware Communication for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.01619/) (2022)
- [FCMNet: Full Communication Memory Net for Team-Level Cooperation in Multi-Agent Systems](https://mlsanity.com/paper/2201.11994/) (2022)
- [CoDe: Communication Delay-Tolerant Multi-Agent Collaboration via Dual Alignment of Intent and Timeliness](https://mlsanity.com/paper/2501.05207/) (2025)
- [Bridging Training and Execution via Dynamic Directed Graph-Based Communication in Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2408.07397/) (2024)

## Abstract (arXiv)

Communication is essential for coordination in cooperative multi-agent reinforcement learning under partial observability, yet cross-timestep delays cause messages to arrive multiple timesteps after generation, inducing temporal misalignment and making information stale when consumed. We formalize this setting as a delayed-communication partially observable Markov game (DeComm-POMG) and decompose a message's effect into communication gain and delay cost, yielding the Communication Gain and Delay Cost (CGDC) metric. We further establish a value-loss bound showing that the degradation induced by delayed messages is upper-bounded by a discounted accumulation of an information gap between the action distributions induced by timely versus delayed messages. Guided by CGDC, we propose CDCMA, an actor--critic framework that requests messages only when predicted CGDC is positive, predicts future observations to reduce misalignment at consumption, and fuses delayed messages via CGDC-guided attention. Experiments on no-teammate-vision variants of Cooperative Navigation and Predator Prey, and on SMAC maps across multiple delay levels show consistent improvements in performance, robustness, and generalization, with ablations validating each component.