Graph Diffusion for Robust Multi-Agent Coordination

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.

$\bullet$ W1: Testing Environments with Dynamic Agent Numbers. We would like to clarify that our original manuscript already includes evaluation in dynamic settings where agent availability changes. Specifically, 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. The corresponding results are reported in the “Coordination Structure” column of Table 2. We believe the confusion may stem from Appendix 7.4.2, which focuses on attribute variation (e.g., speed changes) rather than agent removal.

To further address your concern, we have extended our evaluation by increasing the number of agents and landmarks to 8. During testing, we randomly deactivate 1 to 4 agents by setting their velocities to zero. As shown in Table 4 of the anonymized supplementary material, MCGD consistently outperforms baselines such as DOM2 and MADIFF under all conditions. Notably, the performance gap widens as more agents go offline, highlighting MCGD’s robustness and adaptability in highly dynamic environments.

These results support our claim that MCGD is well-suited for handling general coordination under dynamic agent configurations.

$\bullet$ W2: Scalability Comparison. While 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.

In Appendix 7.4.2, we first evaluate computational efficiency by comparing sampling time under increasing agent numbers (8 to 64). Despite the added complexity of structural diffusion, MCGD remains competitive with existing baselines such as MADIFF.

To further assess planning performance at scale, we additionally conduct experiments on the MPE Spread task with 8, 16, 32, and 64 agents. As 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. This trend highlights MCGD’s ability to effectively model complex collaboration patterns under growing agent populations.

These results confirm that our framework is not only computationally scalable, but also capable of maintaining strong coordination performance in large-scale environments.

$\bullet$ W3: Real World Applications: We agree that real-world validation is an important direction to further demonstrate the practical applicability of our framework.

Our team is currently working on deploying the proposed method in real-world multi-robot hunting scenarios. While we do not yet have quantitative results ready for inclusion in this version, we are actively collecting data and refining the deployment process. We plan to report these findings as part of a more extensive evaluation in a future journal extension of this work.

References:

[1] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.

[2] Madiff: Offline multi-agent learning with diffusion models, Zhu et al, NeurIPS 2024.

[3] Diffusion-based Episodes Augmentation for Offline Multi-Agent Reinforcement Learning, Oh et al, ICML 2024.

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.

$\bullet$ W1: Diversity Metrics in Anisotropic Diffusion. As mutual information-based metrics [1] require costly conditional entropy estimation over agent identity, we adopt System Neural Diversity (SND) [2] to measure action diversity. On 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. As 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.

$\bullet$ W2 and Q1: Intuition behind Transition Matrix. The 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$. The formulation of $Q$ follows prior categorical diffusion work [3]. While we use cosine similarity for simplicity, our framework supports alternative metrics, ensuring adaptability across environments.

$\bullet$ W3: Continuous Action Attribute. In continuous action spaces, the matrix $A_t$ stacks raw actions (dimension $d$) for all agents. At inference, each agent $n_i$ retrieves the $i$-th row of $\hat{A}_t$ as its action, enabling decentralized execution.

$\bullet$ W4, Q2, and Q3: Q-loss in Anisotropic Diffusion. Following [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).

The 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.

$\bullet$ W5: Generated Coordination Graph. Though trained with nearest-neighbor (NN) graphs as supervision, our graph diffusion model adaptively predicts more informative coordination structures. As 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.

$\bullet$ W6: Capturing Agent Interaction Using Graph Structure. While 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.

Building 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.

$\bullet$ W7: Inconsistency between Subscripts and Superscripts. We have reviewed the manuscript and corrected all inconsistencies.

$\bullet$ W8: Adjusting for Figure 1 and Figure 4. Figure 4 has been updated with a fading color scheme to better illustrate temporal progression. In Figure 1, the right subplot depicts a vehicle going offline and remaining stationary, overlapping with its initial position.

$\bullet$ W9: Updated Reference. We have corrected the references to ensure the years and versions are up-to-date.

References:

[1] Celebrating diversity in shared multi-agent reinforcement learning, Li et al, NeurIPS 2021.

[2] Controlling Behavioral Diversity in Multi-Agent Reinforcement Learning, Bettini at al, ICML 2024.

[3] Graph-Constrained Diffusion for End-to-end Path Planning, Shi et al, ICLR 2024.

[4] Diffusion Policies as an Expressive Policy Class for Offline Reinforcement Learning, Wang et al, ICLR 2023.

[5] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.

[6] Dpm-solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps, Lu et al, NeurIPS 2022.

[7] Graph Convolutional Reinforcement Learning, Jiang et al, ICLR 2020.

[8] Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control, Zhang et al, ICLR 2025.

[9] Scaling Safe Multi-Agent Control for Signal Temporal Logic Specifications, Eappen et al, CoRL 2024.

[10] Graph Policy Gradients for Large Scale Robot Control, Khan et al, CoRL 2020.

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.

$\bullet$ W1.1: Action Selection in Continuous Space. In 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. This 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.

$\bullet$ W1.2 and W3.2: Explanation of Average Observation. To 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.

Ablation 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.

During testing, due to decentralized constraints, agents substitute their own observation for the averaged neighbor input, consistent with standard MARL practices.

$\bullet$ W1.3: Gaussian Diffusion over Discrete Actions. In 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.

$\bullet$ W2: Rationale of Covariance Matrix. The 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.

$\bullet$ W3.1: Observation Similarity for Collaboration. Our method leverages observation similarity in both initializing the dynamic coordination graph and defining the transition matrix in categorical diffusion.

For 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.

In 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.

$\bullet$ W4: Learned Coordination Graph. We 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.

Initially, 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.

In 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.

$\bullet$ W5: Adjusting for Figure 5. We have reduced the color saturation in Figure 5 to enhance visual clarity.

References:

[1] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.

[2] Madiff: Offline multi-agent learning with diffusion models, Zhu et al, NeurIPS 2024.

[3] Diffusion-based Episodes Augmentation for Offline Multi-Agent Reinforcement Learning, Oh et al, ICML 2024.

[4] Directional diffusion models for graph representation learning, Yang et al, NeurIPS 2023.

[5] Graph Convolutional Reinforcement Learning, Jiang et al, ICLR 2020.

[6] Graph-Constrained Diffusion for End-to-end Path Planning, Shi et al, ICLR 2024.

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.

$\bullet$ W1 and Q1: Scalability Comparison. To 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.

As 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.

To 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.

References:

[1] Beyond Conservatism: Diffusion Policies in Offline Multi-agent Reinforcement Learning, Li et al, CoRR 2023.

[2] Madiff: Offline multi-agent learning with diffusion models, Zhu et al, NeurIPS 2024.

[3] Diffusion-based Episodes Augmentation for Offline Multi-Agent Reinforcement Learning, Oh et al, ICML 2024.