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

Zihong Gao; Hongjian Liang; Lei Hao; Liangjun Ke

cs.AIApr 4, 2026

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

Authors: Zihong Gao, Hongjian Liang, Lei Hao, Liangjun Ke

Organizations: The State Key Laboratory for Manufacturing Systems Engineering School of Automation Science and Engineering, Xi’an Jiaotong University

Abstract

Communication is essential for coordination in \emph{cooperative} multi-agent reinforcement learning under partial observability, yet \emph{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 \emph{communication gain} and \emph{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 \textbf{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.

Figures & tables

Figure 1: Temporal misalignment under cross-timestep communication delays.

Figure 2: Overall architecture of CDCMA.

Task	Difficulty	CDCMA	CoDe	DACOM	TGCNet	T2MAC	SMS	G2ANet	ATOC
Cooperative Navigation	easy	-1.70 (0.07)	-3.11(0.14)	-3.16(0.43)	-2.08(0.32)	-2.23(0.04)	-2.57(0.11)	-2.24(0.09)	-2.51(0.62)
	medium	-1.80 (0.36)	-3.09(0.05)	-3.14(0.13)	-2.21(0.35)	-2.27(0.08)	-2.67(1.01)	-2.48(0.07)	-2.43(0.14)
	hard	-1.78 (0.22)	-4.36(2.55)	-3.52(1.02)	-2.35(0.34)	-2.51(0.44)	-2.81(0.47)	-2.71(0.07)	-2.75(0.22)
	super_hard	-1.89 (0.13)	-4.42(2.75)	-3.00(0.21)	-2.56(0.36)	-2.53(0.17)	-3.04(0.64)	-2.94(0.06)	-2.79(0.45)
Predator Prey	easy	-0.93 (0.03)	-1.82(0.03)	-1.97(0.23)	-1.53(0.14)	-1.10(0.15)	-1.46(0.27)	-1.17(0.01)	-2.38(0.38)
	medium	-0.91 (0.04)	-1.83(0.03)	-2.19(0.42)	-1.60(0.14)	-1.27(0.22)	-1.36(0.17)	-1.40(0.05)	-2.75(0.54)

Table 1: Mean episode reward (win rate) across tasks under four bounded stochastic delay regimes. The highest mean is in bold.

Panel of Figure 3 — Figure 3: Ablations and sensitivity analyses.

Panel of Figure 4 — Figure 4: Decision-distribution information gaps.

Method	Train	Test
Method	easy	medium	hard	super_hard
CDCMA	$\textbf{-1.70}(\textbf{0.07})$	$\textbf{-1.82}(\textbf{0.15})$	$\textbf{-1.84}(\textbf{0.19})$	$\textbf{-1.93}(\textbf{0.09})$
CoDe	$-3.11(0.14)$	$-3.42(0.19)$	$-3.59(0.71)$	$-4.02(1.88)$
DACOM	$-3.16(0.43)$	$-3.21(0.27)$	$-3.37(0.39)$	$-3.29(0.45)$
TGCNet	$-2.08(0.32)$	$-2.28(0.33)$	$-2.41(0.41)$	$-2.65(0.47)$
T2MAC	$-2.23(0.04)$	$-2.31(0.12)$	$-2.62(0.55)$	$-2.74(0.59)$

Table 2: CN zero-shot cross-difficulty generalization. Train: easy ; entries are mean(std) episode reward.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Category	Symbol	Meaning
Delayed communication semantics	$\boldsymbol{u}_{t}$	Joint environment–communication action $(\boldsymbol{a}_{t},\boldsymbol{m}^{s}_{t})$
	$m^{s}_{ji,t}$	Message sent from agent $j$ to agent $i$ at timestep $t$
	$m^{r}_{ij,t}$	Message from agent $j$ that is available to agent $i$ at receiver timestep $t$
	$m^{\mathrm{tar}}_{ji,t}$	Timely reference condition for sender $j$ at receiver timestep $t$
	$m^{\emptyset}$	Null / masked message input
	$d_{ji,t}$	Sampled communication delay for link $(j\!\to\!i)$ at timestep $t$

Appendix

Table 3: Summary of the main paper-specific symbols.

Hyperparameter	MPE	SMAC
Discount factor	0.96	0.99
Actor learning rate	$10^{-3}$	$10^{-4}$
Critic learning rate	$10^{-2}$	$10^{-3}$
Actor hidden dimension	64	64
Critic hidden dimension	128	128
Message dimension	64	64

Appendix

Table 4: Hyperparameters of CDCMA and its ablations.

Panel of Figure 5 — Figure 5: Delay model: parameter table and corresponding distribution shapes.

Panel of Figure 6 — Figure 6: Mean win rate vs. training episodes across two SMAC tasks and four delay difficulties.

Panel of Figure 7 — Figure 7: Mean episode reward vs. training episodes on Cooperative Navigation (CN) and Predator Prey (PP) across four delay difficulties.

Figure 8: Mean win rate vs. training episodes on 1o_10b_vs_1r under the delay-free condition.

Panel of Figure 9 — Figure 9: Qualitative OTG diagnostics on Predator Prey. Left: ground-truth observation trajectories. Middle: OTG-predicted trajectories. Right: per-timestep prediction loss. Lighter circles indicate farther future steps.

Task	Low-gain $\Delta Q$	High-gain $\Delta Q$	$\Delta Q$ ( $\hat{c}\leq 0$ )	$\Delta Q$ ( $\hat{c}>0$ )	Sign agreement (%)
PP	-0.019	0.088	-0.013	0.076	79.1
1o_10b_vs_1r	-0.012	0.121	-0.018	0.109	82.1

Appendix

Table 6: CGDC consistency diagnostics.

\Delta Q

denotes the raw full-critic value difference between retaining and masking a received message.

Panel of Figure 10 — Figure 10: Replay snapshots of CDCMA policies on 1o_2r_vs_4r and 1o_10b_vs_1r under cross-timestep delays.

Explore similar work

Decoupled Delay Compensation: Enhancing Pre-trained MARL Policies via Learned Dynamics Filtering
May 25, 2026Maxim Mednikov, Oren GalMulti-Agent Reinforcement Learning Agentic Reinforcement Learning
University of Haifa, Israel
Structural Equivalence and Learning Dynamics in Delayed MARL
May 5, 2026Jules Sintes, Ana Bušić, Jiamin ZhuPartially Observable Markov Decision Process Multi-Agent Reinforcement Learning
Inria · DIENS, École Normale Supérieure, PSL University · Paris, France +2
Value-Aware Prediction for Robust Multi-Agent Coordination Under Communication Loss
Jul 20, 2026Kemal Devrim Kafadar, Eren Özaltun, Mahmud Efnan Şanlı +4Multi-Agent Reinforcement Learning Multi-Agent Coordination
Department of Computer Engineering, Istanbul Technical University, Istanbul, Türkiye. · Department of Computer Science, University of Stuttgart, Stuttgart, Germany. · Istanbul Technical University Artificial Intelligence and Data Science Application and Research Center, Istanbul, Türkiye. +1

May 25, 2026, cs.MAJ/K move · Enter open · S save

Decoupled Delay Compensation: Enhancing Pre-trained MARL Policies via Learned Dynamics Filtering

Maxim Mednikov, Oren Gal

University of Haifa, Israel

Multi-Agent Reinforcement Learning Agentic Reinforcement Learning State Estimation Extended Kalman Filter

Open paper AskPDF arXiv

Real-world multi-agent reinforcement learning (MARL) systems must often operate under stale observations, stochastic communication delays, and intermittent packet loss. Policies trained under idealized synchronous conditions frequently exhibit significant performance degradation in these regimes because they act on outdated feedback. We propose a modular execution-stage state-estimation layer that replaces delayed communicated observations with current belief-state estimates. The framework integrates a learned Gated transition model with a recursive Kalman filtering layer to estimate instantaneous states from asynchronous measurements. A primary advantage of this approach is its modularity, The estimator serves as a plug-in for pre-trained policies, requiring no modifications to the original MARL training algorithm, architecture, or reward structure. Evaluation across diverse multi-agent and continuous-control benchmarks demonstrates that the proposed layer consistently enhances robustness to communication latency and message loss. The most significant performance gains are observed in coordination-intensive and dynamically unstable tasks where temporal consistency is critical for control.

Abstract

Explore similar work

Decoupled Delay Compensation: Enhancing Pre-trained MARL Policies via Learned Dynamics Filtering

Structural Equivalence and Learning Dynamics in Delayed MARL

Value-Aware Prediction for Robust Multi-Agent Coordination Under Communication Loss