Graph Diffusion for Robust Multi-Agent Coordination
Authors: Xianghua Zeng
Hang Su
Zhengyi Wang
Zhiyuan LIN
Venue: ICML 2025 spotlightposter (2025)
Keywords: multi-agent coordination
offline reinforcement learning
diffusion models
Primary area: reinforcement_learning->multiagent

Abstract: Offline multi-agent reinforcement learning (MARL) struggles to estimate out-of-distribution states and actions due to the absence of real-time environmental feedback. While diffusion models show promise in addressing these challenges, their application primarily focuses on independently diffusing the historical trajectories of individual agents, neglecting crucial multi-agent coordination dynamics and reducing policy robustness in dynamic environments. In this paper, we propose MCGD, a novel Multi-agent Coordination framework based on Graph Diffusion models to improve the effectiveness and robustness of collaborative policies. Specifically, we begin by constructing a sparse coordination graph that includes continuous node attributes and discrete edge attributes to effectively identify the underlying dynamics of multi-agent interactions. Next, we derive transition probabilities between edge categories and present adaptive categorical diffusion to capture the structure diversity of multi-agent coordination. Leveraging this coordination structure, we define neighbor-dependent forward noise and develop anisotropic diffusion to enhance the action diversity of each agent. Extensive experiments across various multi-agent environments demonstrate that MCGD significantly outperforms existing state-of-the-art baselines in coordination performance and policy robustness in dynamic environments.

Graph Diffusion for Robust Multi-Agent Coordination
Xianghua Zeng'
Hang Su
Zhengyi Wang? Zhiyuan Lin
Abstract
1. Introduction
Offline Multi-Agent Reinforcement Learning (MARL) en- ables policy learning from pre-collected datasets, circum- venting the need for real-time interactions with the envi- ronment (Lange et al., 2012; Levine et al., 2020). This approach is essential in scenarios where real-time interac- tions are expensive, unsafe, or infeasible, such as robotics in hazardous environments or autonomous systems (Barde et al., 2024; Wang et al., 2024). Offline MARL offers path for deploying intelligent agents without requiring continu- ous interaction, but introduces significant challenges.
Offline multi-agent reinforcement learning (MARL) struggles to estimate out-of-distribution states or actions due to the absence real-time interactions with the environment. Although diffusion models have shown promising potential in addressing these challenges, they primarily apply independent diffusion to the historical trajectories of individual agents, which overlooks the crucial dynamics in multi-agent coordination and limits the policy robustness in dynamic environments. In this paper, we propose MCGD, novel Multi-agent Coordination framework based Graph Diffusion models to improve the effectiveness and robustness of collaborative policies. Specifically, we construct a sparse coordination graph with continuous node attributes and discrete edge attributes to identify the underlying multi-agent dynamies effectively. We then derive the transition probabilities between edge categories and present adaptive categorical diffusion to model the structure diversity of inter-agent coordination. According to the coordination structure, we define the neighbor-dependent forward noise and design anisotropic diffusion to increase the action diversity of each agent. Extensive experiments across various multi-agent environments demon- strate that MCGD significantly outperforms existing state-of of-the-art baselines in coordination performance and exhibits superior robustness to dynamic environmental changes.
The primary challenges in offline MARL arise from the ab- sence of real-time feedhack, which limits the ability to adapt policies dynamically based on ongoing interactions with the environment (Matsunaga et al., 2023). First, generalization to unseen states and actions is difficult because policies are trained on limited data, which may not fully capture the diversity of real-world scenarios. In multi-agent settings, this issue is compounded by the complexity of agent interac- tions. Second, out-of-distributio (OOD) actions and states present another challenge, as offline methods often strug- gle to handle situations not represented in the training data. This can lead to unreliable or unsafe behaviors due to the model's inability to properly extrapolate from the limited data available (Kumar et al., 2019; Fujimoto et al., 2019).
Recent advancements have integrated diffusion models (Song & Ermon, 2019; Ho et al., 2020) into both single- agent and multi-agent offline reinforcement learning (RL) to improve policy stability and performance. In single-agent offline RL, diffusion models address issues like overesti- mation bias by modeling the full distribution over actions, leading to more robust value function estimates (Janner et al., 2022; Ajay et al., 2022). This probabilistic approach helps mitigate common challenges in high-dimensional state spaces by capturing complex dependencies between states and actions, offering a more stable alternative to traditional Q-learning. For multi-agent offline RL, diffusion models like MADIFF (Zhu et al., 2023) extend this framework to model complex agent interactions, leveraging diffusion pro- cesses to simulate cooperative dynamics within multiple interacting agents. Additionally, methods such as EAQ (Oh et al.) enhance the training process by incorporating the Q-total function into the diffusion model, improving
'State Key Laboratory of Software Development Environment, Beihang University. Beijing, China DDpaatmentt of Computer Sci- ence and Technology. Institute for AI, BNRist Center, Tsinghua- Bosch Joint ML Center, Tsinghua University, Beijing, China. Cor- respondence to: Hang Su <suhangss @ isu..uua.ddu.cn>...
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Graph Diffusson for Robust Multi-Agent Coordination
speed attribute
adversary vehicle
tially, to identify the collaborative dynamics, we construct sparse graph with continuous nodes and discrete edges, retaining essential and eliminating ineffective multi-agent interactions. Next, we measure the observational differences to derive an edge transition matrix adapted to multi-agent be- haviors, and present categorical diffusion to model the struc- ture diversity in inter-agent coordination. For each agent, we define neighbor-depentee dynamic coordination structure and develop anisotropic dif- fusion to model the diversity in single-agent actions. Finally, extensive comparative evaluations on three well-established benchmarks-MPP MAMuJoCo, and SMAC-demonstrate that our framework achieves superior coordination perfor- mance and robustness, significantly outperforming state-of- the-art baselines by up to 12.8% and 14.2%, respectively. Our contributions are summarized as follows:
controlled vehicle
OOO cooperative agent
a) current diffusionn based coordination
forward noise to capture the
b) our graph diffusion-based coordination
Figure 1: Comparison between current diffusion- al- gorithms and our graph diffusion-basee based framework in an il- lustrative four-agent hunting scenario, focusing on dynamic changes in speed attributes and coordination structures. the estimation of joint action values in multi-agent settings. DOM2 (Li et al., 2023), on the other hand, overcomes the conservatism of offline RL by enabling greater exploration of strategies, thus reducing the tendency to rely on subopti- mal, overly cautious policies.
We propose the first graph diffusion model for multi-agent coordination with superior effectiveness and robustness in dynamic multi-agent environments.
We present a categorical diffusion process to simulate transitions between edge categories, modeling the structure diversity in multi-agent coordination.
Nevertheless, these methods typically apply diffusion mod-
els independently to the historical trajectories of individual agents, overlooking the crucial coordination dynamics be- tween agents. This approach limits policy robustness in dynamic multi-agent settings, as it adapts to changes in individual agent attributes but fails to capture the evoly- ing coordination strategies that emerge agents interact. Figure 1 illustrates this limitation using four-agent collab- orative hunting scenario, where four vehicles work together to capture an adversary. This scenario mimics real-world challenges in multi-agent systems, where agents must con- tinuously coordinate and adapt to both internal and external changes. The hunting strategy, trained on fixed speed at- tributes from offline data, fails to generalize to real-time shifts, such as changes in agent speed or the sudden unavail- ability of an agent. When two agents' speeds change, the diffusion-basee method can adjust the strategy through noise addition and denoising, as shown in Figure I(a), allowing the task to proceed. However, when one agent unexpectedly becomes unavailable, the remaining agents cannot adapt their coordination structure, and the hunting task fails. This example highlights critical challenge in offline MARL: the need for policies that not only adapt to individual agent attributes but also dynamically adjust to shifts in the coordi- nation structures. In real-world applications, such changes in coordination are inevitable, and robust policies must be able to handle these shifts to ensure successful and efficient multi-agent collaboration.
We develop an anisotropic diffusion process incorporating -eepbborddepedeet forward noise to model the diversity in single-agent actions.
Comparative evaluations across various challenging multi- agent environments demonstrate the significant advantages of our framework in coordination performance and policy robustness compared to state of-hhoff- baselines.
2. Related Work
2.1. Offline Multi-agent Reinforcement Learning
Offline coordination is a significant hurdle that limits ad- vancements and exploration within offline multi-agent rein- forcement learning (MARL) (Zhu et al., 2023). To address this, recent studies (Chen et al., 2021; Yang et al., 2021) have extended single-agent offline algorithms to multi-agent scenarios through policy regularization. However, these ex- tensions face persistent extrapolation errors (Fujimoto et al., 2019) in offline environments, which remain challenging to resolve fully. An alternative approach, the centralized training with decentralized execution (CTDE) paradigm (Olichock al., 2008), has driven notable progress through algorithms such QMIX (Rashid et al., 2020), MADDPG (Lowe et al., 2017), and MAPPO (Yu et al., 2022). Addition- ally, methods like MA-ICQ (Yang et al., 2021) and OMAR (Pan et al., 2022) have been developed to address distribu- tional shifts in offline settings by adopting conservatism principles. Despite their success in reducing distributional errors, these conservatism-based methods restrict the flex-
In this work, we propose a novel generative framework MCGD for Multi-agent Coordination based on Graph Diffusion models to enable diverse and adaptive collab- orative policies, as illustrated in Figure 1 (b), with enhanced effectiveness and robustness in dynamic environments. Ini-
2

---

Graph Diffusion for Robust Multi-Agent Coordination
ibility of agent coordination, limiting adaptability across varied scenarios. To enhance multi-agent coordination, dif- fusion models capable of capturing complex distributions have recently been introduced into offline MARL (Zhu et al., 2023; Li et al., 2023; Oh et al.). However, these algorithms independently apply diffusion models to the historical tra- jectories of individual agents, neglecting the inter-agent coordination structure, which reduces their robustness to environmental changes.
3.1. Offline Multi-agent Reinforcement Learning
We model the fully cooperative multi-agent task as a de- centralized partially observable Markov decision process (Dec-POMDP) (Olichoek et al., 2016), described as P,P, O R,,) with agents I = mpz) ? In this context, S and A denote state and action spaces, respectively, and y E [0, 1] is the discount factor. At each timestep t, every agent n, observes a local observation of E 12 produced by the function (o af) and chooses action of E A. All chosen actions form a joint action A, A and lead to transition to the next global state S according to the function P(S++1|S, A.), resulting in joint reward = R(S, At). In offline set- tings, rather than interacting with the environment in real- time, we have access to a historical dataset DD to learn multi- agent policies that maximize the discounted cumulative reward. The offine dataset 'D typically consists of multi- agent observation-action trajectories, where each trajectory t [Oo, Ao. O,, Ai,.... Or, Arl includes the joint ob- servations and actions at each time step.
tuple .M {#1, n22
In response, this work introduces a graph diffusion-based multi-agent coordination framework to explicitly capture the coordination structure and utilize distinct diffusion pro- cesses for structure and action diversity, achieving superior adaptability and performance in dynamic environments.
2.2. Diffusion Models
Diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020) have emerged as a powerful generative framework for modeling complex data distributions. They have shown significant success in continuous generation tasks such image synthesis (Dhariwal & Nichol, 2021; Rombach et al., 2022), animation creation (Ho et al., 2022; Luo & Hu, 2021), and molecule design (Corso et al.; Trippe et al.). Recently, two distinct strategies have been proposed to adapt diffu- sion models for generating graphs with discrete structures (Austin et al., 2021; Hoogeboom et al., 2021). The first ap- proach (Chen al.; Hoogeboom et al., 2022) embeds graph data into continuous space by adding Gaussian noise to the node features and adjacency matrix, enabling the model to learn the underlying graph distribution. An alternative strategy (Vignac et al.; Hua et al., 2024) avoids continuous perturbations, which are less effective at capturing the struc- tural properties of graph data. Instead, it directly models cat- egorical diffusion for discrete graph data by estimating the transition probabilities between different categories. How- ever, existing graph diffusion models primarily focus on the independent diffusion of discrete attributes across nodes and edges. This limitation makes them unsuitable for adaptively modeling the diversity of discrete multi-agent structures and continuous single-agent actions in offline multi-agent reinforcement learning.
3.2. Denoising Diffusion Probabilistic Model
The denoising diffusion probabilistic model (DDPM) (Ho et al., 2020) is a generative model that synthesizes continu- ous or discrete data through a forward noising process and a corresponding reverse denoising process.
In continuous diffusion, DDPM introduces Gaussian noise to the original data X, q(X) at each iteration k. perturb- ing it progressively as follows:
- V1 B, (1)
where denotes the identify covariance matrix, and 13& E (0, 1) controls the scale of the Gaussian noise added at iter- ation In the reverse process, DDPM employs trained, parameterized Gaussian transition kemne pe to iteratively denoise samples, gradually reconstructing the original data distribution from the noisy samples as follows:
Pe(Xx-1|X) (x+) (Xe-1: k), k),, (2)
where 14 and Eg represent the predicted average value and covariance matrix parameterized by 0.
To address these challenges, we propose the first graph dif- fusion model for modeling multi- agentt collaboration, which combines categorical diffusion for inter-agent structures with continuous diffusion for multi-agent actions, facilitat- ing more effective and robust collaboration.
For discrete diffusion on data X (c.g., graph structures), DDPM computes the transition probabilities between cate- gories to replace the Gaussian noise, yielding the noisy data at iteration as follows:
3. Preliminaries
((xxXXx-1) = cat(Xx/Xx-1Q00
(3)
In this section, we formally define the fundamental concepts and provide a summary of the primary notations, as detailed in Appendix 7.1.1.
where Qr. represents the transition matrix applied to the discrete data X5-1 at iteration kt and cat denotes the cate- gorical distribution over possible categories of Xg. During
3

---

Graph Diffusson for Robust Multi-Agent Coordination
the denoising process, the posterior distribution pe is com- puted using the Bayes rule as follows:
forward noising
reserve denoising
policy sampling
noisy muiti-
A'x
graph diffusion modds
estimated inter- egent edges
agent artions
Po(Xa-1lA X) x cat Xx BR O pQ) ). (4)
E
Gj coondination graph structure
where QBa.: Q Qz .......QP. QB. 1Q 1'T represents the transpose of the transition matrix QBa and o denotes the Hadamard product.
perturbed inter- agent edges
predicted single- agent actions
O,
Qc
of
historical trajectortes
distibution
oooperative environment
4. Methodology
The overall architecture of MGCD, including forward noising process, reverse denoising process, and policy sampling process.
Figure 2:
In this work, we propose the first graph-based diffusion framework for offline multi-agent reinforcement learn- ing, including categorical diffusion discrete edges and anisotropic diffusion on continuous nodes, to model the di- versity of inter-agent coordination and single-agent actions, respectively. The proposed framework consists of three pri- mary processes: forward noising, reverse denoising, and policy sampling, as detailed in Figure Specifically, we perturb forward the nearest-neighbor coordination graph constructed from multi-agent historical trajectories, design the graph transformer network to reversely recover the clean attributes of discrete edges and continuous nodes, and em- ploy the trained diffusion model to sample collaborative policies for multi-agent decentralized exccution.
The marginal distribution g( (G,) should have closed-
form expression for efficient calculation.
The Gaussian noise should be anisotropic and dependent on the inter-agent coordination E,.
4.1.1. CATEGORICAL NOISING ON EDGES
Considering the relevance among multiple agents, we define an adaptive transition matrix between edge categories and present a categorical diffusion process on the discrete edges to model the diversity in inter-agent coordination.
For clarity, we denote the timestep in an episode as [t) the diffusion iteration as { k= and the agent as {m;]] [m:)
To quantify the multi-agent relevance, for each pair of agents n; and nj. we calculate the cosine similarity G. between their observations of, of E O2 as a measure of the likeli- hood of diffusion occurring between n, and ny. Intuitively, high similarity the agents' observations reflects a strong alignment of their states and indicates the potential for sub- stitutable coordination, thereby increasing the likelihood of diffusion between them. Leveraging this metric. we construct similarity matrix C' E R [Z]]]] and derive the transition matrix Qr between edge categories as follows:
4.1. Forward Noising Process
To capture the collaborative dynamics among agents, we identify the essential multi-agent interactions to construct the sparse coordination graph G. = (Ae, Ex) at timestep t. For each agent n; E I. we establish undirected edges connecting it with its & nearest neighbors defined by their observation difference, resulting in k-nn coordination graph. In the graph G,, A, [ represents the d-dimensional continuous node attributes that encode the actions of each is binary adjacency matrix
Q₂ = ec-
(6)
agent, while E. E {0. |) [Z) where each entry indicates the presence (or absence) of an edge between two agents. For discrete action spaces, we represent each agent's s action using a one-hot vector of dimension d, where is the number of discrete actions.
where D the diagonal degree matrix of C, normalizing the similarity values. Theorem 4.1 establishes the rationality of the transition matrix Q2 for categorical diffusion, confirming the necessary properties identified in prior studies (Yi et al., 2024; Shi et al.).
Theorem 4.1. The transition matrix Qt satisfies the follow- ing beneficial properties of symmetry, additivity, locality, and convergence:
In this subsection, we present a graph diffusion process over the graph G. to simulate the dynamic multi-agent behavior when online coordination, detailed as follows:
(G = (v/ - S.AA + B&e, Qo.) (5) where c and Qá, the forward noise and transition ma- trix applied A and E respectively, at iteration k. To guarantee the efficiency and adaptivity of the forward noising process, three desirable properties are required:
1Q,)" =Q:, Qtitt, Qr, Qtp
lim Q: = 1 11a
lim Q2 I, t
The detailed proof is provided in Appendix 7.2.1.
The transition matrix Q2 should be adaptive to the multi- agent historical trajectories.
By incorporating the scale parameter 3g. the categorical noising of edge discrete F, at diffusion iteration & is formal-
4

---

Graph Diffusion for Robust Multi-Agent Coordination
I. Forward Noising
III. Policy Sampling
ni
0
0.6
1.2
1.4
0
1.3
1.1
8
1.4 1.1
0.6
discrete edges
transition matrix
perturbed edges
fully-connected graph
denoised graph
nearest-neig neighbor coordination graph
WOO
a 4
af
d
neighboring actions
anisotropic noise
noisy action
a
decentralized actions
estimated actions
II. Reverse Denoising
a
fir Ecress entroy(E #G)
a
offline historical trajectories
ud I|A,- 4511"
a
online cooperative environment
multi-agent estimated actions
diffusion loss
estimated graph
denoising network
Figure 3: Detailed designs of our proposed graph diffusion- coordination framework.
ized as follows:
the closed-form expression for the marginal distribution qG' (G;) as follows:
( Eat(E) Qa = cC--D)
(( (G,) = (VaRA, (1-a))e E.QK). (12)
(8) where cat(-) represents the categorical distribution, param- eterized by the product 1 Qs Utilizing the symmetry and additivity properties in Theorem 4.1, we derive the closed-form expression for categorical noising on E,;
where deontes the multi-agent d-dimensional anisotropic Gaussian noise, with each component for agent nı drawn from (0, M.).
4.2. Reverse Denoising Process
(E cat( cat(E Ex
Qix = QB. = (CC-D)
In this subsection, we design graph diffusion network to reverse denoise the perturbed coordination graph, with the goal recovering the original attributes of inter-agent coordination and single-agent actions.
4.1.2. ANISOTROPIC NOISING ON NODES
Instead of the noising process on historical trajectories in- dependent of aater-agent coordination, define forward Gaussian noise conditioned neighboring agents' actions and then design an anisotropic diffusion continuous nodes to model the diverse single-agent actions.
Given the edge attributes E and E,, we apply the Bayes rule to derive the posterior distribution of E follows:
( E.) x cat cat(E%,11,).. O E.Qg.., (13)
where @ denotes the pairwise Hadamard product operation.
For each agent n, E I, we encode the action information of its neighbors in the original coordination graph G, as A C A, and calculate the covariance matrix Σ, E Raxd of A characterize the anisotropy of its diffusion process. The forward noising over the single-agent action at at iteration k is formalized as follows:
To predict the unperturbed edge attributes Et, we employ a graph transformer network (Yun et al., 2019) to construct graph denoising network fa. This network takes as input the noisy graph G*x = (Ak, Ek) and outputs the estimated edge attribute ÉG and node attribute Ab
To optimize the graph diffusion model parameterized by 0, employ the cross-entropy loss Loe to quantify the discrepancy between the clean edge attribute F, and the predicted edge attribute Lig as follows:
g(at,ela Naai V - E.). (10)
Given the parameters ag 1 3, and ãk I ag the closed-form expression of the marginal distribution of af x is derived as follows:
Lee B(O,,A)E Σ
cross-cntropyy (E Eig). (14)
q(aixx la!) = Na Vilkivvan Vākat (1 E.)..).
(11)
where Ei,, and Ét,, denote the (i, entry in the discrete attributes in E, and E respectively.
The detailed proof is provided in Appendix 7.2.2.
By integrating the categorical diffusion over discrete edges and anisotropic diffusion over continuous actions, we derive
To further optimize the denoising network fe. we compute the Fuclidean distance between the clean node attribute A,
5

---

Graph Difflsson for Robust Multi-Agent Coordination
and the predicted node attribute A/. and incorporate the Q-loss (Wang et al.) define the anisotropic diffusion loss
Algorithm 1 MCGD Sampling Algorithm
1: Input: diffusion parameter K, graph diffusion model
Lad, follows:
fe-, and Q-value function 2% for each agent n4 Initialize: initial observation of for each agent ni
Lad = A.)r
E(1d i=1
a1|l 12 (o),
3: for each timestep / do
4: for each agent n, do
(15)
where af E At denotes the predicted action of agent n, E I, of represents the average observation of agent nu and its neighbors, and À is the regularization coefficient.
5: Select action of based on 27
6: Construct the fully-connected graph G
7:
for each diffusion iteration k do Predict the clean attributes E3 and Ag. based on the denoising network fo Sample the edge attributes 1 from the pos-
8:
To reduce model complexity and maintain scalability, we process each neighboring observation using a shared- parameter MLP, followed by a mean pooling operation over the resulting features. This replaces concatenation, which can significantly increase the parameter count as the number of neighbors grows. By limiting the neighbors to those with higher similarity, the averaging operation is performed over semantically similar features, thereby mitigating informa- tion loss.
9:
terior distribution pe - Et)
10:
end for
11: Execute the single-agent action oj E A
12: end for
13:
end for
The training details of our MCGD framework are provided in Appendix 7.1.2.
di diffusion processes, respectively.
At each diffusion iteration k. we employ the denoising net- work fo to predict the denoised edge attribute EG and node attribute A (line 8 in Algorithm 1). Using the edge at- tributes Eg and Eg. we derive the posterior distribution po (E LEj EG), from which we sample the edge attribute _ at iteration 1 (line 9 in Algorithm 1), as follows:
4.3. Policy Sampling Process
In this subsection, we design a policy sampling process based on the trained graph diffusion model to generate multi- agent collaborative behaviors, with the aim to progressively denoise the inter-agent coordination and multi-agent actions in decentralized execution setting. The whole sampling process is summarized in Algorithm 1.
EL_1~ ~ cat( E O ((E,,,)QQ.
(16)
Based on the sampled edge attribute E and the predicted node attribute Ab, we construct the perturbed coordination graph G = (Áj. E = which will be used in the next denoising iteration k - 1. After the final denoising iteration, we extract the single-agent action af from the final predicted node attribute ÅG as the sampled action of agent n, E Z at timestep / (line 11 in Algorithm 1).
At each timestep t, each agent n. E I obtains its local ob- servation of from the environment and selects the optimal action at according to its trained Q-value function 2% (line 5 in Algorithm 1). Instead of the noise initialization used in prior methods (Li et al., 2023; Zhu et al., 2023), for each agent nı, we generate N random action samples from the continuous action space to construct a candidate set. We then evaluate each candidate using the trained Q-function 27 and select the action with the highest Q-value, provid- ing more informed and value-guidee sampling strategy. Since the optimal action is selected from finite set of sam- pled candidates, this approach is naturally applicable both discrete and continuous action spaces and does not require differentiability or closed-form maximization over actions. For the actions of other agents that are inaccessible, we replace them with a standard Gaussian noise of the same dimensionality, thereby forming the multi-agent actions A,.
Under decentralized execution, each agent n, extracts its own action by retrieving the i-th row of A₁, ensuring consis- tency with the fully decentralized setting. In discrete action spaces, the denoised continuous output is passed through softmax layer, and the final discrete action is selected via an argmax operation over the corresponding softmax probabilities.
5. Evaluation
Using the actions A, continuous node attributes, ini- tialize a fully connected coordination graph G = (A., Fx) (line 6 in Algorithm 1), where the edge attribute E; is de- fined such that off-diagonal entries are set to 1. The at- tributes E, and A, are treated as the initial perturbed data Fix and A%x in the context of categorical and anisotropic
In this work, conduct comparative experiments across different multi-agent environments, aiming to validate our method's s ability to model the complex and diverse behav- iors of cooperative agents. Specifically, we evaluate whether MCGD outperforms state-of-the-an baselines in coordina- tion performance and demonstrates superior robustness to
6

---

Graph Diffusion for Robust Multi-Agent Coordination
Table I: Comparison between MCGD and baselines on offline Expert or Good datasets across the MPE, MAMuJoCo, and SMAC benchmarks: "average value + standard deviation". " Bold: the best performance, underline: the second performance.
Method
Expert MPE
Good MAMuJoCo
SMAC
Spread
Tag
World
Zhallcheetah
Zant
4ant
3m
2532
5ui6m
8m
MA-ICU
79.2 1 4.3
92.6 1: 15.5
81.5 - 20.7
1735. 2 748.3
1186.2 2: 663.9
1214.9 738.4
18.8
2: 0.6
19.6 0.3
16.3
0.9
19.6 = 0.3
MA-CQL
74.1 1.58
68.3
13.2
20.5
2722.8
1022.6
1304.8
604.3
1039.1
617.5
19.6
0.3
0.88
13.8 4.1.
11.3
OMAR
2.4
07.9
16.4
81.8
= 21.0
2963.8 = 410.5
1073.3 = 374.1
9618
18.4
0.2
1.5
16,2 15.
STBC
87,5 7.3
77.4 17,4.110 13.9
97.3
19.1
2386.6 1 440.3
1764.1 1. 457.4
1721.8 1 302.3
0.3
19.2
0.333.3.
15.2
0.11
18.11..3
DOM2
58.2 6.3
98.2 1: 14.4
90.5
1: 17.1
1678.8
248.5
2187.4 1: 190.3
1836.2 1: 241.6
19.4 0.2
19.0 0.4
18.1
0.7
18.2 1: 0.4
MADIFF
82.1 5,9
103.0 +:
13.7
3446.5
213.3
2479.3
2414.5
4: 128.3
1.7
1.1
18.0
19.2
19:2::0.
MCGD
93.88 2.7
109.6 + 13.3
110.9 11.6
3917,4 193.7
2782.7
+ 203.9
2609922
= 165.2
0.1
20.7=00.1
18.9 = 0.5
20.1 0.2
(%6. Avg.T
5.1(5.7)
6.6/6.4)
11.1(115)
260.6(6.5)
(0122(11222
191.718.11
2.5(12.8)
1.1.5.6)
0.9(5.0)
0.9(1.7
Table 2: Comparison between MCGD and baselines shifted environments including MPE Spread, MPE Tag, MPE World, and MAMuJoCo 2halfcheetah, with dynamic changes in agent attributes and coordination structure: "average value + standard deviation". Bold: the best performance in each graph, underline: the second performance.
Method
atteibute
MPE. Spread
coordination structure
apent attribute
MPR Tng
covrdiaation structure
agent attribute
MPR World
coordination structure
agent attribute
MAMaJoCo 2holfcheett
coordiaation stricture
MA-KQQ
61.3= 13.7
34.1 18.7
83.7 + 13.1
47.8 15.3
63.4=144
17.3
158322 547.7
712.6 375.2
MA-CQL
50.4 6.3
35.6 1: 14.3
62.1 1: 16.7
41.2:1.1.17 21.7
51.11 11.0
37.2 1: 18.5
2678.3 2:1 900.9
968.4 162.7
OMAR
68.5 9.7
38.2 à: 14.9
85.6 4: 29.3
41.7 26.8
71.14 15.2
40.9
2298.0 357.2
925.3 1 3644.5
MA-STRC
60.1 = 19.2
44.8 + 25.0
64.4 21.5
40.3+26.1
02.0 38.3
40.5
2307.4 670.3
1053.1 + 492.5
DOMI
74.0 16.1
67.2 a 19.1
89.1 a 21.7
$1.52222.2
11.5 34.
09.41:26.3
3178. 4: 370.5
1788.7 a: 367.4
MADIFF
06.7 12.9
63.9 16.4
91.6 18.4
03.2
25.4
2741.99 990.4
1427
MCGD
78.4 16.2
65.3 # 15.6
99.3 4 20-3
733 # 19.5
104.2 19.4
79.5 2 21.6
3518.4 2750
1925.8 # 318.3
(%% Avg-T
4.4(5.9)
8.1(14.2)
7.7(8.4)
8.6/13.2)
12.4:13.5)
0.9(14.2)
339.7(10.77)
177. (10.1
dynamic environmental changes (e.g., agent attributes and coordination structure). For fair evaluation, we run each offline experiment five times with different random seeds and report the average episodic return obtained in online rollout as the performance measure.
an enemy team controlled by hand-coded AI. Four different maps are explored: three Marines per team (3m), two Stalk- ers and three Zealots per team (2s3z), five Marines versus six Marines (5m_vs_6m), and eight Marines per team (8m). The off-the-grid offline datasets (Formanek et al., 2023) are used here, with varying quality levels-Good, Medium, and availalee for each map.
5.1. Experimental Setup
5.1.1. BENCHMARKS
5.1.2. BASELINE
We conduct extensive evaluations on three following well- established multi-agent benchmarks:
We compare the MGCD framework with the various state- of-the-art art baselines including: offline MARL algorithms such as MA-ICQ (Yang et al.. 2021), MA-CQL (Jiang & Lu, 2023), and OMAR (Pan et al., 2022)), the extension of the single-agent diffusion policy, MA-SIBC (Chen et al., 2022)), and ceffussion-based MARL methods such as DOM2 (Li et al., 2023) and MADIFF (Zhu et al., 2023).
Multi-Agent Particle Environments (MPE) (Lowe et al., 2017). Multiple 2D particles work together to achieve shared objectives across various scenarios. In the Spread task, three particles are positioned randomly and must cover three landmarks without colliding. In the Tag task, three predators cooperate to capture a pre-trained, faster-moving prey. In the World task, three predators catch pre-trained prey, which aims to collect food while evading capture. For the offline datasets, we use four datasets from (Pan et al., 2022), each corresponding to different levels of training quality, Expert, Medium-Replay Medium, and Random.
5.2. Numerical Results
To evaluate the effectiveness of collaborative policies, we report numerical results for both MCGD and baseline meth- ods, using offline Expert and Good datasets across three environments. The average values and standard deviations of the episodic returns for each model are summarized in Table 1. Notably, our MCGD framework consistently achieves state-of-the performance across all multi-agent cooperative scenarios, with smaller deviations in most set- tings, which demonstrates its advantages in terms of both effeectiveeess and stability. The fact that the DOM2 and MADIFF algorithms rank second and third in each task un- derscores the potential of diffusion models in addressing the -uttof-distriuution challenge in offline multi-agent re- inforcement learning. When compared to diffusion- based
Multi-Agent MuJoCo (MAMuJoCo) (Peng et al., 2021). Independent agents control different robotic joints to max- imize forward speed. Three configurations are chosen: 2- agent halfcheetah (2halfcheetah), 2-agent ant (2ant), and 4-agent ant (4ant). The offline datasets are sourced from (Formanek et al., 2023), which includes varying quality Levels-Good Medium, and foor-for each control task.
StarCraft Multi-Agent Challenge (SMAC) (Samvelyan al., 2019). A team of agents collaborates to fight against
7

---

Graph Diffusson for Robust Multi-Agent Coordination
Apern
Ageer
Agoir
Laskrok
Agera
Agren Aper?
Skited Ela Rark www.eooooannnnn (24) Stuadard Enstoanset
x
x
x
#Stundard Enstronnnt
NJ Shitted Envirmmnnn (2A)
Shuthed Envirmmnnt
Figure 4: Visualization of two episodic trajectories in the MPE Spread task with three agents and three landmarks, showing: a) the standard environment, b) dynamic agent attributes (2A), and c) dynamic coordination structure (CS) in the shifted environment.
Figure 5: Visualization of dynamic learned coordination graph over timesteps in the MPE Spread task with three agents and three landmarks under different settings: stan- dard environment, dynamic agent attributes, and dynamic coordination structure.
baselines, MCGD achieves improvements of at least 5.7%, 6.5%, and 4.7% in the MPE, MAMujoco, and SMAC bench- marks, respectively. These significant advantages further highlight the importance of the underlying multi-agent ordination framework when applying diffusion models to historical trajectories. The experimental results on Medium and Poor datasets are provided in Appendix.
shifted environments. The team reward is defined as the sum of the distances between each landmark and its closest agent. When an agent collides with another, it incurs a penalty, which is subtracted from the team reward. Two example episodic trajectories are visualized in Figure 4, illustrating the coordinative behavior of agents in the task.
To further validate the policy robustness, we design shifted environments (details are provided in Appendix 7.3.2) by altering agent attributes and coordination structures. Specif- ically, we randomly modify the particle speed in the MPE environment and adjust the power, density, and friction of joints MAMuJoCo to simulate dynamic changes in agent attributes. Additionally, we randomly select a particle or joint to fix its speed or power attribute as zero, simulating changes in coordination structures caused by the sudden disconnection of agent. For each selected task, train the collaborative policies using the offline datasets gener- ated in standard environments and evaluate them in shifted environments. The corresponding experimental results are shown in Table 2. We observe that MCGD consistently achieves the highest episodic return across all shifted envi- ronments, underscoring the robustness of our framework. Furthermore, more challenging scenarios with dynamic coordination structures, MCGD's performance advantage becomes even more pronounced. This superiority can be attributed to the modeling of diverse edge structures and node actions within the multi-agent collaboration graph, facilitated by our defined graph diffusion process.
In the standard environment, each agent quickly approaches one two landmarks to minimize the distance to the closest landmark. When the minimum speed of Agent 0 decreases, anisotropic diffusion within the MCGD framework dynam- ically reallocates the target landmarks for all three agents, altering their motion trajectories. Additionally, the diffu- sion process's neighbor dependence helps prevent collisions caused by excessive action uncertainty when two agents are close to one another. This cooperation ensures the success- ful completion of the task.
When Agent goes offline and can no longer move, cat- egorical diffusion alters the coordination structure among the remaining agents. With Agent 0's influence removed, the remaining two agents shift their focus from minimizing the distance to a single landmark to minimizing the sum of distances to multiple landmarks.
To illustrate how the learned coordination graph evolves during task execution, we further provide a case study on the MPE Spread task in Figure 5, where the horizontal axis indicates timesteps and the vertical axis shows different experimental settings.
Initially, although pearest-neighte graph is used for ini- tialization, large positional differencee between agents cause the forward diffusion process to disrupt coordination edges. As a result, the model predicte no edges, and agents act independently. As agents move closer, the learned graph
5.3. Qualitative Analysis
To investigate the effectiveness and robustness of the MCGD framework, we focus on the MPE spread task involving agents and landmarks, conducted in both standard and
8

---

Graph Diffusion for Robust Multi-Agent Coordination
Table 3: Comparison of different processing methods for neighboring abservations--avrrgge observation (AO) and feature concatenation (FC) on offline Good datasets in the SMAC benchmark, in terms of average reward and computation time.
5m6m
SMAC
average reward
spent time
average reward
spent time
average reward
spent time
average reward
spent time
MCGD-AO
22.1 + 0.1
174.38
10.45
20.7 0.1
179.01 9.83
18.9 + 0.5
177.52
14.77
20.1 0.2
184.74 11.37
MCGD-FC
0.3
196.40 = 8.77
20.5 + 0.1
203. 18 = 16.04
1..4
207.54 + 13.80
19.4 0.4 210.39 + 10.08
MCXD
MEGID-D
MCGD-AD
MADLE
highlighting the importance of the two key modules in the MCGD framework. Although MCGD-CD performs satis- factorily in simpler tasks such as 3m and 2s3z, it struggles in other complex scenarios, reflecting the limitations of fixed coordination structures in multi-agent collaboration and highlighting the need for modeling coordination struc- ture diversity in MCGD.
3m
2532
20-
Ipiode Meem
1.
10-
Medus
Good
Median Rin
Suakm
We further validate the design of processing neighboring observations through an ablation study using the SMAC benchmark, comparing two variants: MCGD-AO (with ob- servation averaging) and MCGD-FC (with feature concate- nation). As shown in Table 3, MCGD-AO achieves both higher average rewards and lower computational cost across all tasks. The inferior performance of MCGD-FC is largely attributed to increased parameteriization and greater opti- mization difficulty, further supporting the effectiveness and generality of our averaging- approach.
20
23-
Epioddo Raum
15
60-
Medium
Figure 6: Ablation study on categorical diffusion and anisotropic diffusion within the MCGD framework, evalu- ated in SMAC environments.
gradually recover the underlying coordination structure, en- abling effective collaboration such as landmark assignment and collision avoidance.
6. Conclusion
This work proposes the first graph diffusion model for of- fline multi-agent coordination, which employs categorical diffusion on discrete edge attributes and anisotropic dif- fusion on continuous node attributes to capture structure diversity and action diversity, respectively. Extensive eval- uations across three benchmark multi-agent environments demonstrate the effectiveness of the MCGD framework in coordination and its superior robustness to dynamic changes in environmental conditions.
In modified setting where the speed of Agent is re- duced, coordination edges emerge primarily between the other agents. Agent 0, due to its reduced speed, require more timesteps to engage in coordination, delaying the full coordi- nation graph reconstruction. In a more extreme case where Agent 0 inactive, it remains isolated, and coordination is exclusively formed between the other two agents. These visualizations demonstrate the adaptive nature of the learned graph, which dynamically reflects the agents' interaction context and task demands.
In future work, we aim to introduce more complex and adaptable collaboration graph structures to support broader range of agent interactions. Real-world validation remains a critical direction to further demonstrate the practical appli- cability of our framework. Our team is currently working on deploying the proposed method in real-world multi-robot hunting scenarios. Although quantitative results are not yet available for inclusion in this version, we are actively col- lecting data and refining the deployment process. We plan to report these findings as part of a more extensive evaluation in a future extension of this work.
5.4. Ablation Studies
To verify the functionality of key modules, categorical dif- fusion and anisotropic diffusion, we have designed two model variants, MCGD-CD and MCGD-AD, Specifically, in MCGD-CD, we ignore the dynamics of the multi-agen coordination structure and fix it to the k-nearest neighbor- ing graph, whereas MCGD-AD, we perform indepen- dent diffusion on multi-agent trajectories and aggregate the observations from neighboring agents based on the coordi- nation structure. We experimentally compare the MCGD framework and its variants with the best performing base- line, MADIFF, using offline datasets categorized as Good, Medium, and Poor in the SMAC environment. As shown in Figure 6. the full MCGD framework outperforms all datasets, with both variants also surpassing the baseline,
Impact Statement
This paper contributes to advancing the field of Machine Learning. While there are numerous potential societal im- plications of our research, we believe none require specific emphasis in this context.

---

Graph Diffusion for Robust Multi-Agent Coordination
Acknowledgments
Fujimoto, S., Meger, D., and Precup, D. Off-polics deep reinforcement learning without exploration. In Interna- tional conference machine learning, pp. 2052-2062. PMLR, 2019.
This work was supported by NSFC Projects (Nos. 92248303, 92370124, 62350080, 62441612, 62322202), and 62432006, BNRist (BNR2022RC01066) and National Key Laboratory under grant -----0-D0
Ho, J., Jain, A., and Abbeel, Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-666 33:6840-6851, 2020.
References
Ackermann, J., Gabler, V., Osa, T., and Sugiyama, M. Reducing overestimation bias in multi-agent do- mains using double centralized critics. arXiv preprint arXiv:1910001465. 2019.
Ho, J., Salimans, TT, Gritsenko, A., Chan, W., Norouzi, M., and Fleet, D. Video diffusion models. Advances in Neural Information Processing Systems, 35:8633-8646, 2022.
Ajay, A., Du, Y., Gupta, A., Tenenbaum, J., Jaakkola, T., and Agrawal, P. Is conditional generative model- ing all you need for decision-making? arXiv preprint arXiv:2211.15633 2022.
Hoogeboom. E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:1245: 12454-12465, 2021.
Austin, J., Johnson, D. D., Ho. J., Tarlow, D., and Van Den Berg, R. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34: 34:17988 179711111999, 2021.
Hoogeboom, E., Satorras, V. G., Vignac, C., and Welling, M. Equivariant diffusion for molecule generation in 3d. In International conference on machine learning, pp. 8867- 8887. PMLR, 2022.
Barde, P., Foerster, J., Nowrouzezahrai, D., and Zhang, A. A model-based solution to the offline multi-agent reinforce- ment learning coordination problem. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 141 141-150, 2024.
Hua, C., Luan, S., Xu, M., Ying, Z., Fu, J., Ermon, S., and Precup, D.. Mudiff: Unified diffusion for complete molecule generation. In Learning on Graphs Conference, pp. 33-1. PMLR, 2024.
Janner, M., Du, Y., Tenenbaum, J., and Levine, S. Planning with diffusion for flexible behavior synthesis. In Interna- tional Conference Machine Learning, pp. 9902-9915. PMLR, 2022.
Chen. H., Lu, C., Ying, C., Su, H.. and Zhu, J. Offline rein- forcement learning via high-fidelity generative behavior modeling. arXiv preprint arXiv:2209. 2et122299.4444. 14548, 2022.
Chen, I.,, Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A., and Mordatch, I. De- cision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 34:15084 15097, 2021.
Jiang. J. and Lu, Z. Offline decentralized multi-agent rein- forcement learning. In ECAL, pp. 1148-1155, 2023.
Kumar, A., Fu, J., Soh, M., Tucker, G.. and Levine, S. Stabilizing off-policy q-learning via bootstrapping error reduction. Advances in neural information processing systems, 32, 2019.
Chen, T., ZHANG, R., and Hinton, G. Analog bits: Gen- erating discrete data using diffusion models with self- conditioning. The Eleventh International Conference on Learning Representations.
Lange, S., Gabel, T., and Riedmiller, M. Batch reinforce- ment learning. In Reinforcement learning: State-of-the- art, pp. 45-73. Springer, 2012.
Corso, G., Stärk, H., Jing, B., Barzilay, R., and Jaakkola, T. S. Diffdock: Diffusion steps, twists, and turns for molecular docking. The Eleventh International Con- ference on Learning Representations.
Levine, S., Kumar, A., Tucker, G., and Fu, Offline rein- forcement learning: Tutorial, review, and perspectives 2020.
open problems. arXiv preprint urXiv:2005.00
Dhariwal, P. and Nichol, A. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8790 2021.
Li, Z., Pan, L., and Huang, L. Beyond conservatism: Diffu- sion policies in offline multi-agent reinforcement learning. arXiv preprint arXiv:2307 01472, 2023.
Formanck, C., Jeewa, A., Shock, J., and Pretorius, A. Off- the-grid marl: a framework for dataset generation with baselines for cooperative offline multi-agent reinforce- ment learning. arXiv preprint arXiv:2302.00 0052/, 9, 2023.
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-compettivee environments. Advances in neu- ral information processing systems, 30, 2017.
10

---

Graph Diffusion for Robust Multi-Agent Coordination
Luo, S. and Hu, W. Diffusion probabilistic models for 3d point cloud generation. In Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pp. 2837-28435 2021.
Shi, D., Tong, Y., Zhou, Z., Xu, K., Wang, Z., and Ye, J. Graph-constrained diffusion for end-to-end path planning. In The Twelfth International Conference Learning Representations.
Matsunaga, D. E., Lee, J., Yoon, J., Leonardos, S., Abbeel, P., and Kim, K.-E. Alberdice: addressing out-of- distribution joint actions in offline multi-agent rl via alter- nating stationary distribution correction estimation. Ad- vances in Neural Information Processing Systems, 36: 72648-72678, 2023.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International conference on machine learning, Pp. 2256-226622 2265. PMLR, 2015.
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Oh, J., Kim, S., Kim, G., Kim, S., and Yun, S.-Y. Diffusion- based episodes augmentation for offline multi-agent rein- forcement learning. In ICML 2024 Workshop on Struc- tured Probabilistic Inference {{& Generative Modeling-
Trippe, B. L., Yim, J., Tischer, D., Baker, D., Broderick, T., Barzilay, R., and Jaakkola, T. S. Diffusion prob- abilistic modeling of protein backbones in 3d for the scafflica problem. In The Eleventh International Conference on Learning Representations.
Oliehoek, F. A., Spaan, M. T., and Vlassis, N. Optimal and approximate q q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353, 2008.
Vignac, C., Krawezuk. I., Siraudin, A., Wang. B., Cevher, V., and Frossard, Digress: Discrete denoising diffu- sion for graph generation. In The Eleventh International Conference on Learning Representations.
Oliehoek, F. A., Amato, C., et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Packer, C., Gao, K., Kos, J., Krähenbühl, P., Koltun, V., and Song, D. Assessing generalization in deep reinforcement learning. arXiv preprint 18Xiv:1810.1 12282, 2018
Wang. X., Xu, H., Zheng, Y., and Zhan, X. Offline multi- agent reinforcement learning with implicit global-to-local value regularization. Advances in Neural Information Processing Systems, 36, 2024.
Pan, L., Huang, L., Ma, T., and Xu, H. Plan better amid conservatism: Offline multi-agent reinforcement learning with actor rectification. In International conference on machine learning, pp. 17221-17237. PMLR, 2022.
Wang. Z., Hunt, J. J., and Zhou, M. Diffusion policies as an expressive policy class for offline reinforcement learning. In Deep Reinforcement Learning Workshop NeurIPS 2022.
Peng, B., Rashid, T., Schroeder de Witt, C., Kamienny, P.-A., Torr, P., Böhmer, W., and Whiteson, S. Facmac: Factored multi-agent centralised policy gradients. Ad- vances in Neural Information Processing Systems, 34: 12208-12221, 2021.
Yang, Y., Ma, X., Li, C., Zheng, Z.,, Zhang, Q., Huang, G., Yang, J., and Zhao, Q. Believe what you see: Implicit constraint approach for offline multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34:10299-1003 10312, 2021.
Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21(17)):1-51, 2020.
Yi, K., Zhou, B., Shen, Y., Liò, P., and Wang, Y. Graph denoising diffusion for inverse protein folding. Advances in Neural Information Processing Systems, 36, 2024.
Yu, C., Velu, A., Vinitsky, E.,, Gao, J., Wang, Y., Bayen, A., and Wu, Y. The surprising effectiveness of ppo in cooper- ative multi-agent games. Advances in Neural Information Processing Systems, 35:2461 1-46224, 2022.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent difffusion models. In Proceedings of the IEEE/CVF con- ference on computer vision and pattern recognition, pp. 10684-10695, 2022.
Yun, S., Jeong, M., Kim, R., Kang, J., and Kim, H. J. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Samvelyan, M., Rashid, T., Schroeder de Witt, C., Farquhar, G., Nardelii, N., Rudner, T. G., Hung, C.-M., Torr, P. H., Foerster, J., and Whiteson, S. The starcraft multi-agent challenge. In Proceedings of the 18th International Con- ference on Autonomous Agents and MultiAgent Systems, pp. 2186 2186-2188, 2188, 2019.
Zhu, Z., Liu, M., Mao, I.,, Kang, B., Xu, M., Yu, Y., Ermon, S., and Zhang, W. Madiff: Offline multi-agent learning with diffusion models, arXiv preprint arXiv:2305.172: 17330 2023.

---

Graph Diffusion for Robust Multi-Agent Coordination
7. Appendix
7.1.2. MCGD TRAINING PROCESS
7.1. Framework Detail
We summarize the training process of MCGD framework in Algorithm 2. At each training episode, we randomly sample multi-agent historical trajectory from the of- fline dataset DD Within this trajectory we initialize nearest-neighboring coordination graph G, = (A,, Bx) at each timestep and sample a parameter K as the number of diffusion iterations (lines and in Algorithm 2). For the discrete edges E,, we apply the closed-fone expression of categorical diffusion calculate the perturbed structure F (line in Algorithm 2). For each agent nG I, we calcu- late the covariance matrix Σ, which defines the anisotropic structure of the Gaussian noise applied to its action space (line Algorithm 2). We then employ the closed-form continuous diffusion on the agent's 's action af to obtain noisy action d (line 10 in Algorithm 2). Integrating the perturbed edges and each agent's action, derive the per- turbed coordination graph G (Akr Ei) and optimize the graph diffusion model by minimizing the training losses Lee and Lod (lines 13 and 14 in Algorithm 2).
7.1.1. NOTATIONS
To facilitate comprehension, we summarize the primary no- tations related multi-agent reinforcement learning and graph diffusion models, along with their corresponding de- scriptions, in Table 4.
Table 4: Glossary of Notations.
Notation
Description
M
Markov decision process
I
Single agent; Agent set State and action spaces
S,A
P;O
Transition and observation functions Reward function; Discount factor Multi-agent observations, states, and actions Single-agent observation, state, and action
R:y
0:5:A
0,8,a
D;r
Replay buffer; Historical trajectory
X
Random variable
Algorithm MCGD Training Algorithm
GP
Prior and posterior distributions Gaussian noise; Transition matrix
Input: offline multi-agent dataset D
N:Q
Initialize: graph diffusion model fo and Q-value func- tion 2ø; for each agent mi
E
Average value and covariance matrix
G
Coordination graph; Coordination edges Similarity matrix; Diagonal degree matrix
3: for each training episode do
O;D
4: for each training step do
K,T
Diffusion iterations; Timesteps
5: Construct the nearest coordination graph Ge
f
Graph denoising network
Sample the diffusion parameters K Calculate the perturbed edge attribute E for each agent n. do
L
Loss function
Calculate the covariance matrix E, Calculate the noisy single- agent action a Optimize the Q value function Q end for
10:
11:
12:
13:
Derive the perturbed coordination graph G Optimize the graph diffusion model fo by mini- mizing Lee and Lad
14:
15:
end for
16:
end for
12

---

Graph Diffusion for Robust Multi-Agent Coordination
7.2. Theorem Proof
Next, show that C - D is semi-negative definite. For any vector x E R we have:
7.2.1. PROOF FOR THEBOEM 4.1
z=(C (C
D) x Fx x=" D'DD Dx
Proof. We begin by considering the Taylor expansion of the matrix exponential for Q.::
7
Diçaa
(C- DY
= Σ
= =1+
(17)
+-==
i=1
==1 i!
Di
Σ
2 J. +
Σ
D Digg
where I denotes the identity matrix.
2
i=1
i,=1
1=1
Symmetry. Since both the similarity matrix C and the diagonal degree matrix D are symmetric, it follows that:
1
(Cas (24 - .2,)))
2
1,j=1
(C CDD)" = -C)
(18)
S 0.
Thus, the transpose 0, is:
(24)
Thus, C- D is semi-negative definite, and all eigenvalues except for the one corresponding to 1 are negative.
[0. T
TT +
[[C D)1?
We can now express Qf terms of the eigenvalue decom- position of C D:
+ il (C (C- 1)}
(19)
of = (C-D) = VeAVVT
(25)
QF
where the matrix of eigenvectors of and A is the diagonal matrix of eigenvalues 0 è1 x2 2 ... 2 A
Therefore, Of is symmetric.
As Do, the matrix exponential e. behaves follows:
Additivity. Using the properties of the matrix exponential, we have:
Qu+ee (CCC-D)())))
eA lim t-0000
=11 0
if if 1.
(26)
(20)
Therefore, in the limit as f - oc, the matrix Of converges to the rank-1 matrix formed by the eigenvector correspond- ing to the zero eigenvalue:
Thus, Of satisfies the additivity property.
Locality, From the Taylor expansion, each term in the series for Q involves powers of For i > 1, we have:
lim O -17 1-000
(27)
(C DD' t-5
(C DD'D)'0' 0.
lim
(21)
This completes the proof of the convergence of Qf as l. +
i!
when C - D is irreducible.
Therefore, as - the transition matrix reduces to:
oc ++)
(C-
DD'E
1
lim Q 10
lim t-2
=1. (22)
i=1
This establishes the locality of OF as f approaches zero.
Convergence. First, note that the matrix C' -D has an eigenvalue of 0:
(C - (-D)1 C1 = 0
(23)
where and 0 are the vectors of all ones and zeros, re- spectively. If C is irreducible, then the geometric multiplicity of the eigenvalue 1, and the corresponding normalized eigenvector
13

---

Graph Diffusion for Robust Multi-Agent Coordination
7.2.2. FORWARD ANISOTROPIC PROCESS
Proof. Given the anisotropic noising process iteration k, derive the following expression for xi
dhe - /1 - - + Buei,
(28)
where 6i,K (0, (.) represents the anisotropic noise of agent ni.
By recursively unrolling the forward process, we rewrite L as follows:
d
/ Bral R-1 + Bheik
k
II j=1
V B50i,0 + Σ V 81(1 - 3k)) ... B1 (x.g.
(29)
Using ag = 1 3y and āk = ITI= Ori, we express the marginal distribution of di as:
d
Vona
BJ CH.j
Ej- (30)
Since each noise term Et is independently sampled from (0, Σ,), we know that:
E|gy] = 0, Cov(G,,) Σ,
(31)
The mean and variance of the weighted sum of independent and identically distributed Gaussian noises are given by:
Ck Bj
eij
Bj Eleiyl O,
(32)
Cov
Σ
aR Bj
eij
3j aj
Cov(es.)
Oij
3 Okk Σ₁
aj
j=1
Ork O.j+1(1 (1aa))
j=1
= (1
0k Ei
(33)
Therefore, the distribution of this weighted sum of Gaussian noises is given by:
k
Σ
B
ak eLj ~ N(0, (1- 2.),,
(34)
Finally, based on the previous steps, the marginal distribu- tion of at_ can be written as follows:
((atplat,o) = (aaa as Varai,on (1 (1-a0 (.)))
(35)
14

---

Graph Diffusion for Robust Multi-Agent Coordination
7.3. Environmental Details
7.3.2. SHIFTED ENVIRONMENTS
7.3.1. IMPLEMENTATION DETAILS
The parameter settings for agent attributes are summarized in Table 5. In the MPE experiments, design the shifted Spread, Tag, and World environments by reducing the mini- mum speed of a single random agent from the original value of 0.8 to 0.3. For the MAMuJoCo experiments, we design the shifted 2halfcheetah environment following prior work (Packer et al., 2018). Specifically, we randomly sample val- ues for the following three parameters: power (influencing the multiplied force), density (affecting the weight), and friction (determining the sliding friction of the joints).
All experiments are conducted on Linux servers with 64-core Intel Xeon Platinum 8336C CPU (2.30 GHz) and an NVIDIA A800-SXM4-80GB GPU. Across all experi- ments, the diffusion parameter K is varied within the range [50, 200), with a learning rate of 2e 4, a batch size of 32, a reward discount y of 0.99, and the Adam optimizer utilized.
For the MPE experiments, we employ the earlier version of the environment provided by OMAR (Pan et al., 2022), where agents receive distinct, environment-speccffe rewards that depend on their individual actions and contributions to the collective task. To ensure fairness and consistency in comparisons, we utilize OMAR's datasets and environments, ensuring all baseline models were trained and evaluated under identical conditions.
Table 5: Parameter setting in the shifted MPE and MAMu- JoCo environments.
MPE
Standard
Shifted
Speed
[0.8, 1.0)
[0.3, 1.0)
MAMuJoCo
Standard
Shifted
In the MAMuJoCo experiments, we rely on off-the- shelf dataset (Formanek et al., 2023), which includes Good, Medium, and Poor quality datasets for each task. Each dataset is generated using three independently trained MA- TD3 policies (Ackermann et al., 2019), supplemented with exploration noise to enhance behavioral diversity.
Power
1.0
0.8, 1.2
Density
1000
[750, 1250)
Friction
0.4
[0.25, 0.55]
Similarly, for the SMAC experiments, we utilize a sepa- rate off-the-shelf dataset (Formanek et al., 2023) that in- cludes Good, Medium, and Poor quality datasets for each map. These datasets are constructed using three indepen- dently trained QMIX policies (Rashid et al., 2020), with exploration noise deliberately introduced to the policies to encourage behavioral diversity.
15

---

Graph Diffusion for Robust Multi-Agent Coordination
7.4. Supplemental Experiments
7.4.2. SAMPLING EFFICIENCY
7.4.1. SENSITIVE ANALYSIS
To assess the efficiency and scalability of our framework, we incrementally increase the number of agents and record the time required (in ms) for the policy sampling process in both our graph diffusion model and the baseline diffusion model, MADIFF, as shown in Table As shown in the table, while our proposed graph-basee based diffusion model introduces some additional time overhead compared to the baseline, the gap remains relatively small and stable as the number of agents increases. This demonstrates the sampling efficiency and scalability of the MCGD framework.
To investigate the effect of the regularization coefficient À on framework's performance, increase its value from 0.1 to 20.0 in the MPE Tag task, evaluating performance at the Random, Medium-Replay, Medium, and Expert levels. We then report the resulting episodic returns to evaluate performance at each setting, as shown in Table 7. For the expert dataset, smaller values of lead to better perfor- mance, because the policy already well-trained, and the regularization does not need be strong. In contrast, larger values of À tend to improve performance in the other datasets, as regularization plays more significant role in preventing overfitting and stabilizing offline learning.
Table Wall-clock time spent on sampling multi-agent policies in the MCGD and MADIFF models.
Method
8
16
Teg-Meclun-tuaiyy
MADIFF
145.47
149.36
148.19
149.84
MCGD
153.69
154.27
155.38
154.94
75
Averp "ploote
80-
74
25-
70-
Tap Molian
Tip Experi
1100
20-
127.5
Spencts
15500
102.5
01 02
0.5
1.0
2.5
50
10.0 15.0 20.0
0.1 0.2
05 1.0 58 160 150 250
Reguleriaation CoeTTleeet
Regalaitnnka Cooffliionn
Figure Sensitivity analysis on the À value in offline datasets from the Tag task at the Random, Medium- Medium, and Expert levels.
16

---

Graph Diffusson for Robust Multi-Agent Coordination
Table 7: Comparison between MCGD and baselines on offline Medium-Replay, Medium, and Random datasets across the MPE benchmark: "average value + standard deviation". Bold: the best performance, underline: the second performance.
Random Tag
Medium-Repp Replly
Medium
Method
Spread
World
Spread
Tag
World
Spread
Tag
World
MA-ICQ
6.3 1: 3.5
2.2 1 2.6
1.0 = 3.2
11.2 1 8.4
28.3 1 19.2
9.7 6.4
24.5 1 8.6
55.8 i 19.3
53.7 1. 21.8
MA-CQL
24.0
5.0 1 8.2
0.6 2.0
15.3 1 7.6
22.8 1 19.4
15.9
15.91144. 14.2
8.11
57.4
44.3
14.1
OMAR
5.3
11.1
5.9
35.6 15.2
41.6 17.9
21. 15.6
41.7 21.3
$3.4225.9
45.6 16.0
MA-SBBC
5.1 3.9
1.16
7.4=399
8.2 4.6
12.7 7.3
9.1 5.9
51.6 14.2
47.1 17.9
22.2
DOM2
37.4 113
29.6 8.1
38.9 = 11.8
63.1 + 9.5
68.2 + 16.7
65.9 + 10.6
78.6 8.1
82.6 = 18.2
84.5 23.4
MADIFF
7.2 3.6
1.6 2.6
0.7 3.1
35.1 + 7.2
53.9 11.4
16.4-12.5
60.3 + 10.6
72.7 9.4
87.2
+ 13.9
MCGD
41.8
43.7
11.8
48.3
10.1
74.4 10.3
78.3 + 9.6
79.3
14.2
88.6 9.3
94.8 12.4
99.4 12.8
Table 8: Comparison between MCGD and baselines on offline Poor and Medium datasets across the MAMuJoCo benchmark: "average value + standard deviation". Bold: the best performance, underline: the second performance.
Poor
Medium
Method
2halfcheetah
2ant
4ant
2halfcheetah
2ant
4ant
MA-ICQ
271.4 183.6
583.4 = 327.9
658.4 + 392.7
749.2 296.4
581.4 257.4
1025.8 + 437.1
MA-CQL
293.5 138.6
437.6 291.4
593.1 + 385.5
963.4 316.6
638.2 244.9
900.4 + 281.6
OMAR
362.7 - 314.2
837.5 = 194.2
509.4 + 241.4
2797.0 + 445.7
772.5 + 216.4
917.3 = 349.2
MA-SIBC
216.4 + 208.5
883. = 372.5
976.4 + 241.3
1386.8 + 248.8
1038.4 + 294.5
1529.4 + 371.6
DOM2
803.0 + 274.6
916.2 = 181.6
1137.9 + 224.5
2851.2 = 145.5
1431.7 + 304.8
1691.5 + 183.3
MADIFF
814.2 + 245.7
934.8 = 174.2
1362.8 + 274.3
2194.7 + 319.6
1247.3 + 358.1
1728.9 + 249.3
MCGD
1244.7 + 159.2
1479.3 164.9
1738.4 + 149.2
3168.4 + 210.8
1867.2 247.1
2074.3 156.2
7.4.3. ADDITIONAL RESULTS
For a comprehensive evaluation of MCGD and baselines, we conduct comparative experiments across offline datasets from various difficulty levels in the MPE, MAMuloCo, and SMAC benchmarks. Specifically, we report collaborative performance the Random, Medium-Replay and Medium datasets in the Spread, Tag, and World tasks from the MPE benchmark (Table 7), performance on the Poor and Medium datasets in the 2halfcheetah, 2ant, and 4ant tasks from the MAMuJoCo benchmark (Table 8), and performance on the Poor and Medium datasets the 3m, 2s3z, 5m6m, and 8m tasks from the SMAC benchmark (Table 9). As shown in these tables, our MCGD framework consistently and sig- nificantly outperforms all baseline methods across different datasets and environments, improving the average episodic return by at least 4.1, 317.2, and 0.3 in MPE, MAMuJoCo, and SMAC, respectively. In the most challenging (Random or Poor) scenarios, MCGD increases the average returns in MPE from 35.3 to 44.6 MPE, in MAMuloCo from 1037.3 1487.5.am in SMAC from 9.1 10.3, achieving average improvements of 9.3 (3(26.3%) 450.2 (4..4(4).4%) and 1.2 2%) over baselines and demonstrating the effective- ness advantage of our method.
17

---

Graph Diffusion for Robust Multi-Agent Coordination
Table 9: Comparison between MCGD and baselines offline Poor and Medium datascts across the SMAC benchmark: "average value + standard deviation". Bold: the best performance, underline: the second performance.
Poor
Medium
Method
3m
2s3z
5m6m
Sm
3m
253z
5m6m
8m
MA-ICQ
4.9 + 0.5
7.8 + 0.3
9.1 + 0.6
6.4 + 0.3
18.1 = 0.7
17.2 + 0.6
15.3 0.7
18.6 13.6:00 0.8
MA-CQL
5.8 = 0.4
10.1 + 0.7
10.4 + 1.0
4.6 2.4 2.4
18.9 0.7
14.3 - 2.0
17.0 + 1.2
16.8 3.1
OMAR
4.7 + 0.4
5.8 + 0.6
9.6 + 1.2
5.9 + 0.5
16.3 + 0.5
14.5 + 0.4
14.8 + 0.6
16.3 + 0.7
MA-SIBC
5.2
7.4
8.1 0.3
6.9 0.7
17.4 0.9
16.8 0.5
16.5 - 0.5
18.1 0.4
DOM2
9.1
9.6
8.9
18.7 5.7
17.1 0.5
17.2
18.0 0.7
MADIFF
8.9
0.9
8.9 0.3
5.1 0.1
17.2
17.4 0.3
1..5
19.2 0.7
MCGD
10.4 + 0.2
11.3 0.5
10.7 + 0.8
8.8 + 0.3
20.6 0.6:0.33
18.8 0.7
18.3 0.6
19.7 0.4
18


Reviews:
[{"review_id": "xEy88lbOLp", "reviewer": "Reviewer_PGtc", "summary": "This paper uses a graph diffusion approach to study MARL problems. This method incorporates graph diffusion in order to incorporate changes in multi-agent coordination dynamics (such as an agent dropping out). The goal of the approach is to be able to more seamlessly handle out-of-distribution states and actions than alternative MARL approaches. Experimental results indicate that the method performs well empirically.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive feedback. We have addressed all comments and revised the manuscript accordingly. Responses are organized by reviewer Weaknesses (W) and Questions (Q), with relevant figures and tables provided in the [anonymized supplementary material](https://anonymous.4open.science/r/MCGD_Rebuttul-23DF).\n\n$\\bullet$ W1 and Q1: Scalability Comparison.\nTo ensure fair and comparable evaluation, we adopt similar experimental settings to prior diffusion-based offline MARL works [1-3], where most tasks involve fewer than 10 agents. However, this does not suggest our method is limited to small-scale scenarios.\n\nAs detailed in Appendix 7.4.2, we compare the policy sampling time of our method with MADIFF, showing that despite the additional cost from structural diffusion, our approach remains computationally competitive.\n\nTo assess scalability and collaborative performance in larger-scale settings, we further conduct experiments on the MPE Spread task with 8, 16, 32, and 64 agents. As presented in Table 1 of the anonymized supplementary material, MCGD consistently outperforms MADIFF and DOM2 across all scales, with performance gains increasing as the number of agents grows. These results demonstrate that our graph diffusion-based design not only scales well but is also more effective in modeling complex multi-agent coordination.\n\nReferences:\n\n[1] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.\n\n[2] Madiff: Offline multi-agent learning with diffusion models, Zhu et al, NeurIPS 2024.\n\n[3] Diffusion-based Episodes Augmentation for Offline Multi-Agent Reinforcement Learning, Oh et al, ICML 2024.", "claims_and_evidence": "Yes, it seems that the authors have presented experimental results that support the claims with empirical evidence.", "methods_and_evaluation_criteria": "I am not an expert in applied MARL research, so I am not sure what is standard, but the examples seemed logic and reasonable to me.", "theoretical_claims": "I skimmed the proof and it seemed reasonable.", "experimental_designs_or_analyses": "It seems that most of the MARL settings considered have relatively few number of agents (I believe less than 10 agents, is that correct)? I'm curious how well the method scales to more agents, especially given the computational costs of diffusion models in general.", "relation_to_broader_scientific_literature": "I am unsure of the state of the art as I am not an expert in this domain.", "essential_references_not_discussed": "I am unsure of whether references are complete, but it seems the authors made a solid effort.", "other_strengths_and_weaknesses": "The paper is overall well written and it seems the authors have made an effort to provide a detailed explanation of the forward and backward denoising process.", "other_comments_or_suggestions": "Please see questions below.", "questions_for_authors": "(1) How well can the method scale and how expensive is it compared to the other baselines?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U5G92zRNSf", "reviewer": "Reviewer_YBYW", "summary": "This paper introduces MCGD, the first offline MARL algorithm based on graph diffusion models. MCGD employs a discrete diffusion process on graphs to model cooperative relationships among agents, while using a continuous anisotropic diffusion process to model each agent’s action distribution. The authors claim that MCGD can better model the dynamic interactions between agents. The effectiveness of MCGD is validated on multiple offline MARL datasets, with ablation studies conducted for both diffusion processes. Notably, MCGD demonstrates strong robustness, particularly in scenarios where agent attributes and interaction patterns undergo sudden changes.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive feedback. We have addressed all comments and revised the manuscript accordingly. Responses are organized by reviewer Weaknesses (W) and Questions (Q), with relevant figures and tables provided in the [anonymized supplementary material](https://anonymous.4open.science/r/MCGD_Rebuttul-23DF).\n\n$\\bullet$ W1.1: Action Selection in Continuous Space.\nIn the policy sampling phase, each agent $n_i$ generates $N$ random actions from the continuous space to form a candidate set, which is evaluated by the trained Q-function $\\mathcal{Q}_{\\phi_i}$ to select the action with the highest Q-value.\nThis replaces the Gaussian noise initialization used in prior methods [1,2], offering a more value-guided and sample-efficient strategy. As selection is over a finite candidate set, the approach naturally applies to both discrete and continuous spaces without requiring action differentiability or closed-form maximization.\n\n$\\bullet$ W1.2 and W3.2: Explanation of Average Observation.\nTo reduce model size and improve scalability, we apply a shared MLP to each neighboring observation and use mean pooling over the extracted features. Compared to concatenation, this approach is more parameter-efficient and robust, particularly as the number of neighbors increases. By focusing on similar neighbors, it also mitigates potential information loss.\n\nAblation results on SMAC (Table 2 in anonymous link) show that MCGD-AO (average observation) outperforms MCGD-FC (feature concatenation) in both performance and efficiency, validating our design.\n\nDuring testing, due to decentralized constraints, agents substitute their own observation for the averaged neighbor input, consistent with standard MARL practices.\n\n$\\bullet$ W1.3: Gaussian Diffusion over Discrete Actions.\nIn discrete action spaces, we use one-hot encoding to represent actions and apply softmax decoding at the diffusion model's output. This embeds discrete actions into a continuous latent space for Gaussian diffusion, while allowing valid discrete action reconstruction via softmax followed by argmax during inference.\n\n$\\bullet$ W2: Rationale of Covariance Matrix.\nThe node attribute $A_t$ represents the joint action across all agents in the coordination graph. To enhance coordination modeling, we extend prior works [1–3] by introducing an adaptive covariance matrix in the anisotropic diffusion to capture action uncertainty while preserving the collaboration structure. Inspired by [4], we modify only the covariance (not the mean), avoiding training instability and ensuring convergence and computational efficiency during diffusion.\n\n$\\bullet$ W3.1: Observation Similarity for Collaboration.\nOur method leverages observation similarity in both initializing the dynamic coordination graph and defining the transition matrix in categorical diffusion.\n\nFor initialization, we follow prior work [5] that uses observation similarity to form initial neighbor sets. This provides a flexible starting point, while the diffusion process adaptively refines the graph, enabling coordination even among heterogeneous agents.\n\nIn categorical diffusion, cosine similarity between observations defines edge transition probabilities, capturing substitutable coordination. This aligns with adaptive categorical diffusion designs [6]. Other similarity metrics scaled to [0,1] can also be used, ensuring flexibility across environments and observation modalities.\n\n$\\bullet$ W4: Learned Coordination Graph.\nWe illustrate the evolution of the coordination graph in Figure 1 (anonymized supplementary), using the MPE Spread task. The x-axis denotes timesteps, and the y-axis represents different settings.\n\nInitially, the diffusion process disrupts edges due to large agent distances, resulting in independent behavior. As agents converge, the graph recovers a structured form, enabling coordinated behaviors such as landmark assignment.\n\nIn modified scenarios, edges shift toward active agents, with Agent 0 either delayed in coordination or excluded entirely. These cases highlight the model’s ability to adapt the graph structure based on real-time agent dynamics.\n\n$\\bullet$ W5: Adjusting for Figure 5.\nWe have reduced the color saturation in Figure 5 to enhance visual clarity.\n\nReferences:\n\n[1] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.\n\n[2] Madiff: Offline multi-agent learning with diffusion models, Zhu et al, NeurIPS 2024.\n\n[3] Diffusion-based Episodes Augmentation for Offline Multi-Agent Reinforcement Learning, Oh et al, ICML 2024.\n\n[4] Directional diffusion models for graph representation learning, Yang et al, NeurIPS 2023.\n\n[5] Graph Convolutional Reinforcement Learning, Jiang et al, ICLR 2020.\n\n[6] Graph-Constrained Diffusion for End-to-end Path Planning, Shi et al, ICLR 2024.", "claims_and_evidence": "The claims regarding the effectiveness of the proposed algorithm are well-supported by strong experimental results.", "methods_and_evaluation_criteria": "The authors validate their approach with commonly used datasets. The proposed graph-based diffusion model is intuitively reasonable, but I have some doubts regarding certain details.", "theoretical_claims": "No, I did not check the details of the proof.", "experimental_designs_or_analyses": "I have not verified the validity of the experimental results, as the authors have not provided the code, and some details remain unclear to me.", "relation_to_broader_scientific_literature": "The proposed algorithm builds upon works in graph diffusion and offline MARL.", "essential_references_not_discussed": "I have not found any.", "other_strengths_and_weaknesses": "### Strengths\n\n1. The experimental results of MCGD are impressive.\n\n2. The algorithm proposed in the paper is novel to me, and the motivation is intuitive.\n\n### Weaknesses\n\n1. Some descriptions in the paper are unclear, making it difficult to understand certain technical details. During sampling, the authors mention using the Q-function to select the optimal action (Line 5 in Algorithm 1). This raises several questions: 1) In a continuous action space, how is the optimal action selected from the Q-function? 2) The Q-function takes as input the average observation of neighboring agents—how is this obtained during testing when other agents’ observations are not directly available? 3) For discrete action spaces, how does the Gaussian diffusion process generate the node action attributes? \n\n2. Additionally, is the node attribute $A_t$ the same as the joint action of the agents? If so, what is the rationale behind defining forward noising in anisotropic noising using the covariance matrix of the agent's action?\n\n3. Some algorithm designs appear rather arbitrary and lack generality. The authors propose using the similarity in the raw observation space as a measure of cooperation between agents. However, observation similarity does not necessarily imply suitability for collaboration, as some tasks may require cooperation between agents with different characteristics. Moreover, such similarity is influenced by the specific meaning of each dimension in the observation space, which varies across different environments. While this property may hold in the environments tested by the authors, it is difficult to claim general applicability. Additionally, using the average observation of neighboring agents as input to the Q-function also lacks generality. Directly averaging observations can lead to significant information loss; for example, if two neighboring agents have values of 0.5 and 0.5 in a certain dimension, their average would be indistinguishable from another pair with values of 0.9 and 0.1, despite the differences in underlying distributions.", "other_comments_or_suggestions": "1. I am particularly interested in how the learned coordination graph structure evolves during task execution. It would be helpful if this could be illustrated in a case study similar to Figure 4.\n\n2. The color saturation in Figure 5 is too high.", "questions_for_authors": "See weaknesses. If the authors can address my concerns, I am willing to increase my rating.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bXtvmMd06a", "reviewer": "Reviewer_PSeB", "summary": "This paper introduces Multi-agent Coordination based on Graph Diffusion (MCGD), a novel framework for offline multi-agent reinforcement learning (MARL) that uses graph diffusion models to enhance coordination in dynamic environments. MCGD constructs a coordination graph to capture multi-agent interactions and uses a form of categorical and anisotropic diffusion processes to model agent interactions and actions. The framework outperforms existing state-of-the-art baselines in coordination performance and policy robustness across various multi-agent environments.\n\n## update after rebuttal\nI appreciate the additional experiments and hope any remaining corrections are fixed in the final version of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive feedback. We have addressed all comments and revised the manuscript accordingly. Responses are organized by reviewer Weaknesses (W) and Questions (Q), with relevant figures and tables provided in the [anonymized supplementary material](https://anonymous.4open.science/r/MCGD_Rebuttul-23DF).\n\n$\\bullet$ W1: Diversity Metrics in Anisotropic Diffusion.\nAs mutual information-based metrics [1] require costly conditional entropy estimation over agent identity, we adopt System Neural Diversity (SND) [2] to measure action diversity.\nOn SMAC tasks, we sample $N_1$ observations and generate $N_2$ actions per agent. SND is then estimated using Sinkhorn divergence over pairwise action distances. \nAs shown in Table 3 (anonymized supplementary), MCGD consistently outperforms MADIFF and DOM2, especially in scenarios with more agents and heterogeneous unit types, validating its effectiveness in modeling diverse coordination.\n\n$\\bullet$ W2 and Q1: Intuition behind Transition Matrix.\nThe matrix $Q$ is based on cosine similarity between agent observations, indicating that agents in similar states are more likely to substitute each other in coordination roles; that is, a higher $Q_{ij}$ implies agent $n_j$ can replace $n_i$.\nThe formulation of $Q$ follows prior categorical diffusion work [3].\nWhile we use cosine similarity for simplicity, our framework supports alternative metrics, ensuring adaptability across environments.\n\n$\\bullet$ W3: Continuous Action Attribute.\nIn continuous action spaces, the matrix $A_t$ stacks raw actions (dimension $d$) for all agents.\nAt inference, each agent $n_i$ retrieves the $i$-th row of $\\hat{A}_t$ as its action, enabling decentralized execution.\n\n$\\bullet$ W4, Q2, and Q3: Q-loss in Anisotropic Diffusion.\nFollowing [4, 5], we add a conservative Q-loss to complement the surrogate loss [6] in offline RL. The full training objective is provided in Equation 1 (anonymous link).\n\nThe term $\\overline{o}^t_i$ in the Q-value denotes the mean-pooled encoding of neighboring observations, which reduces parameters and enhances generalization when local similarity holds. As shown in the ablation study on observation processing (Table 2, anonymous link), MCGD-AO (average observation) outperforms MCGD-FC (feature concatenation) in both performance and efficiency, validating this design.\n\n$\\bullet$ W5: Generated Coordination Graph.\nThough trained with nearest-neighbor (NN) graphs as supervision, our graph diffusion model adaptively predicts more informative coordination structures.\nAs shown in Figure 1 (anonymized supplementary), the denoised graph evolves with agent dynamics—remaining sparse when agents are far apart, and gradually forming structured coordination as they converge. In modified scenarios, the model shifts focus to active agents, deviating from the static NN pattern.\n\n$\\bullet$ W6: Capturing Agent Interaction Using Graph Structure.\nWhile prior methods [7–10] have applied interaction graphs in MARL, our work introduces the first graph diffusion-based framework that jointly models structural and action diversity in offline settings.\n\nBuilding on observation-based heuristics [7], we employ categorical diffusion for edge dynamics and anisotropic diffusion for continuous actions, enabling behavior-adaptive coordination. We plan to explore the integration of advanced graph learning techniques [8–10] in future work.\n\n$\\bullet$ W7: Inconsistency between Subscripts and Superscripts.\nWe have reviewed the manuscript and corrected all inconsistencies.\n\n$\\bullet$ W8: Adjusting for Figure 1 and Figure 4.\nFigure 4 has been updated with a fading color scheme to better illustrate temporal progression.\nIn Figure 1, the right subplot depicts a vehicle going offline and remaining stationary, overlapping with its initial position.\n\n$\\bullet$ W9: Updated Reference.\nWe have corrected the references to ensure the years and versions are up-to-date.\n\nReferences:\n\n[1] Celebrating diversity in shared multi-agent reinforcement learning, Li et al, NeurIPS 2021.\n\n[2] Controlling Behavioral Diversity in Multi-Agent Reinforcement Learning, Bettini at al, ICML 2024.\n\n[3] Graph-Constrained Diffusion for End-to-end Path Planning, Shi et al, ICLR 2024.\n\n[4] Diffusion Policies as an Expressive Policy Class for Offline Reinforcement Learning, Wang et al, ICLR 2023.\n\n[5] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et\nal, CoRR 2023.\n\n[6] Dpm-solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps, Lu et al, NeurIPS 2022.\n\n[7] Graph Convolutional Reinforcement Learning, Jiang et al, ICLR 2020.\n\n[8] Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control, Zhang et al, ICLR 2025.\n\n[9] Scaling Safe Multi-Agent Control for Signal Temporal Logic Specifications, Eappen et al, CoRL 2024.\n\n[10] Graph Policy Gradients for Large Scale Robot Control, Khan et al, CoRL 2020.", "claims_and_evidence": "The major claims are supported by results on a set of multi-agent benchmarks with off-the-shelf datasets. The graph diffusion model for multi-agent coordination using a graph transformer network appears novel.\n\nHowever, the claim that the anisotropic diffusion process models the diversity in single agent actions is not adequately explored. “Diversity” could be quantified better (such as a metric based on mutual information [1] or SND [2]) and supported with experiments.", "methods_and_evaluation_criteria": "For categorical noising, a transition matrix (Eq. 6) is derived from the cosine similarity between agent observations. The intuition behind this formula is not readily apparent. An explanation could be a high similarity between agent observations implies a high value at $Q_{ij}$ meaning the agents are connected. The authors could further address the motivations of this transition matrix.\n\nThe continuous node attributes $A_t$ in graph $G_t = (A_t, E_t)$ are $d$ dimensional and encode the agent actions. It is unclear if this means it stores the actions of all agents (with a common dimension $d$) or is some form of action embedding. The method to extract an action for each agent from the predicted $\\hat{A}^t$ is not obvious.\n\nThe Q-loss used in the anisotropic diffusion loss (Eq. 15) is not explained in the main body. For instance, how are the Q-values estimated? Is this estimated from the offline data directly using a standard Bellman error objective? Additionally, the incorporation of average agent observations into the Q-value is not a common practice (to the best of my knowledge) and warrants further explanation.\n\nLastly, the ground truth $E$ (edge matrix) which is used to train the denoiser is the nearest-neighbor graph. It would help to explain how the final denoising network generated something better than just using the nearest neighbors (as evident in Fig.5, the MCGD-AD baseline).", "theoretical_claims": "Theorem 4.1 is sound.", "experimental_designs_or_analyses": "I did not find any issues in the experiments following prior Offline MARL approaches and the ablation study on the categorical and anisotropic diffusion. The claims of capturing agent diversity could be better quantified or supported with evidence.", "relation_to_broader_scientific_literature": "This paper directly addresses the Offline MARL setting like MADIFF (Zhu et al) and methods like OMAR (Pan et al). The idea of capturing agent interactions in multi-agent systems using a graph has been examined previously [3-6] but not via diffusion of the interaction graphs (to the best of my knowledge).", "essential_references_not_discussed": "References used throughout the review are shown below.\n\nReferences:\n\n[1] Celebrating Diversity in Shared Multi-Agent Reinforcement Learning, Li et al, NeurIPS 2021\n\n[2] Controlling Behavioral Diversity in Multi-Agent Reinforcement Learning, Bettini et al, ICML 2024\n\n[3] Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control, Zhang et al, ICLR 2025\n\n[4] Scaling Safe Multi-Agent Control for Signal Temporal Logic Specifications, Eappen et al, CoRL 2024\n\n[5] Graph Convolutional Reinforcement Learning, Jiang et al, ICLR 2020\n\n[6] Graph Policy Gradients for Large Scale Robot Control, Khan et al, CoRL 2020", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- The usage of subscripts and superscripts of $t$ is inconsistent (e.g., Pg6 L312 uses a superscript $t$ unlike earlier) and should be fixed.\n- Fig. 4 would be better understood if the trajectory states were faded based on time (solid at end of trajectory, faded at beginning).\n- If Fig. 1 it would be good to depict the missing ninth agent  (there are nine on the left but only eight on the right).\n- Some references need to be fixed with the year:\n    - Shi, D., Tong, Y., Zhou, Z., Xu, K., Wang, Z., and Ye, J. Graph-constrained diffusion for end-to-end path planning\n    - Trippe, B. L., Yim, J., Tischer, D., Baker, D., Broderick, T., Barzilay, R., and Jaakkola, T. S. Diffusion probabilistic modeling of protein backbones in 3d for the motif-scaffolding problem.\n    - Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffusion for graph generation\n- For the following, the latest reference is ICLR 2023 :\n    \n    Wang, Z., Hunt, J. J., and Zhou, M. Diffusion policies as an expressive policy class for offline reinforcement learning", "questions_for_authors": "1. What is the intuition behind Eq. 6 and the use of cosine similarity?\n2. Could there be added background on the Q-loss used in the anisotropic diffusion loss?\n3. What other works consider the incorporation of average neighborhood agent observations into the Q-value loss?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qg3aOAGI8A", "reviewer": "Reviewer_DRJr", "summary": "This paper introduces MCGD (Multi-agent Coordination based on Graph Diffusion), which is a novel framework for offline multi-agent reinforcement learning (MARL) that aims to improve coordination effectiveness and robustness of the policies in dynamic environments. Specifically, MCGD uses graph to model the relationship and coordination of agents. When doing sampling, MCGD uses categorical diffusion to model discrete edge attributes (the correlation between agents) and use anisotropic diffusion to model continuous node attribute (actions of the agents). The authors conducted extensive experiments in different platforms to demonstrate the outstanding performance compared with benchmarks.\n\n## Score updated after Rebuttal", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive feedback. We have addressed all comments and revised the manuscript accordingly. Responses are organized by reviewer Weaknesses (W) and Questions (Q), with relevant figures and tables provided in the [anonymized supplementary material](https://anonymous.4open.science/r/MCGD_Rebuttul-23DF).\n\n$\\bullet$ W1: Testing Environments with Dynamic Agent Numbers.\nWe would like to clarify that our original manuscript already includes evaluation in dynamic settings where agent availability changes. \nSpecifically, during testing on the MPE Spread task, we randomly selected one of the three agents and set its velocity to zero to simulate a sudden offline event. \nThe corresponding results are reported in the “Coordination Structure” column of Table 2. \nWe believe the confusion may stem from Appendix 7.4.2, which focuses on attribute variation (e.g., speed changes) rather than agent removal.\n\nTo further address your concern, we have extended our evaluation by increasing the number of agents and landmarks to 8. \nDuring testing, we randomly deactivate 1 to 4 agents by setting their velocities to zero. \nAs shown in Table 4 of the anonymized supplementary material, MCGD consistently outperforms baselines such as DOM2 and MADIFF under all conditions. \nNotably, the performance gap widens as more agents go offline, highlighting MCGD’s robustness and adaptability in highly dynamic environments.\n\nThese results support our claim that MCGD is well-suited for handling general coordination under dynamic agent configurations.\n\n$\\bullet$ W2: Scalability Comparison.\nWhile our core experiments follow prior diffusion-based offline MARL settings [1-3], which typically involve fewer than 10 agents, this does not indicate a limitation of our framework in large-scale scenarios.\n\nIn Appendix 7.4.2, we first evaluate computational efficiency by comparing sampling time under increasing agent numbers (8 to 64). \nDespite the added complexity of structural diffusion, MCGD remains competitive with existing baselines such as MADIFF.\n\nTo further assess planning performance at scale, we additionally conduct experiments on the MPE Spread task with 8, 16, 32, and 64 agents. \nAs reported in Table 1 of the anonymized supplementary material, MCGD consistently outperforms MADIFF and DOM2 across all settings, with the performance gap widening as the number of agents increases. \nThis trend highlights MCGD’s ability to effectively model complex collaboration patterns under growing agent populations.\n\nThese results confirm that our framework is not only computationally scalable, but also capable of maintaining strong coordination performance in large-scale environments.\n\n$\\bullet$ W3: Real World Applications:\nWe agree that real-world validation is an important direction to further demonstrate the practical applicability of our framework.\n\nOur team is currently working on deploying the proposed method in real-world multi-robot hunting scenarios. \nWhile we do not yet have quantitative results ready for inclusion in this version, we are actively collecting data and refining the deployment process. \nWe plan to report these findings as part of a more extensive evaluation in a future journal extension of this work.\n\nReferences:\n\n[1] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.\n\n[2] Madiff: Offline multi-agent learning with diffusion models, Zhu et al, NeurIPS 2024.\n\n[3] Diffusion-based Episodes Augmentation for Offline Multi-Agent Reinforcement Learning, Oh et al, ICML 2024.", "claims_and_evidence": "The authors claim that by using MCGD the coordination of agents can be improved especially in dynamic environments. To show this, in the introduction part of the paper, the authors mentioned the case where one agent suddenly becomes unavailable to demonstrate the importance of designing algorithms to tackle general dynamic environments. However, such environments are not tested in the experiments according to the shifted environments in appendix 7.4.2. It would be nice if the authors could have more experiments about changing the number of agents (agents become unavailable or adding new agents to the env) to demonstrate the capability of dealing with environmental changes. \n\nBesides, the agent number of the experiments is greatly limited. In MPE envs, the number of agents is less than 10. Although the authors listed the sampling time comparison result when the number of agents varies from 8 to 64 in 7.5.2, but the planning performance of these experiments is not discussed. In order to better demonstrate the generalizability of the framework, experiments and planning performance comparison when the number of agents is different is beneficial.", "methods_and_evaluation_criteria": "The authors tested the proposed framework in multiple simulation platforms with benchmarks in different tasks, which is pretty comprehensive and clear. It would be better if more experiments, especially real world robotics experiments, can be included.", "theoretical_claims": "The proofs look good to me.", "experimental_designs_or_analyses": "See Claims And Evidence part of the review.", "relation_to_broader_scientific_literature": "This paper studies the MARL problem, which is an important method in multi-agent motion planning. The proposed MCGD framework improves the coordination performance and robustness in dynamic environment, which is important for future real world applications and generalization to more practical scenarios.", "essential_references_not_discussed": "References look good to me.", "other_strengths_and_weaknesses": "The paper is written and organized clearly with useful illustrations and diagrams.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents MCGD, a novel offline multi-agent reinforcement learning (MARL) framework leveraging graph diffusion models to enhance coordination and adaptability in dynamic environments. The method combines categorical diffusion to model inter-agent relationships and anisotropic diffusion for action modeling. The work is evaluated across standard offline MARL benchmarks and extended to dynamic scenarios involving changing agent availability and population sizes. 

Several key sections, such as those involving the use of Q-values, coordination graphs, and the diffusion processes were found difficult to follow in the original submission, but the authors’ response helped  clarify these in the rebuttal. Some algorithmic decisions (e.g., using observation similarity for graph construction or averaging neighbor observations) were initially questioned for their generality. The rebuttal provides solid empirical and theoretical rationale, though further elaboration in the final paper would strengthen these justifications.
Decision: Accept (spotlight poster)