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

1. Problem Statement

In cooperative Multi-Agent Reinforcement Learning (MARL), effective coordination is essential for tasks like traffic control or robot formations. While graph structures are commonly used to model agent dependencies, existing methods suffer from three critical limitations:

• Reliance on One-Step Observations: Current methods (e.g., DCG, DICG, SOP-CG) infer graph topologies based solely on instantaneous observations. They neglect historical trajectory data, which is crucial for understanding dynamic agent behaviors, leading to suboptimal graphs that foster redundant or detrimental information exchange.
• Computational Scalability: Many coordination graph methods rely on calculating action-pair values. In a system with $N$ agents and $A$ actions, the complexity is $O(A^2N^2)$. This becomes computationally prohibitive as the number of agents or actions increases, hindering scalability in complex environments.
• Lack of Contextual Understanding: Existing graphs often fail to capture the uncertainty of relations or the full environmental context, limiting agents' ability to deduce global states from partial observations.

2. Methodology: LTS-CG

The authors propose Latent Temporal Sparse Coordination Graph (LTS-CG), an end-to-end framework that simultaneously learns a sparse coordination graph and optimizes the multi-agent policy.

Core Architecture

The framework consists of two main modules:

1. Inter-Agent Sparse Graph Learning: Generates a dynamic graph structure from historical data.
2. Cooperative MARL: Uses the learned graph to facilitate knowledge exchange and policy optimization.

Key Technical Components

A. Trajectory-Based Graph Construction
Instead of using one-step observations, LTS-CG utilizes observation trajectories ($O_T$) to capture temporal dependencies.

• Feature Extraction: A convolutional layer processes the time dimension of each agent's trajectory to extract latent behavior patterns ($z_i$).
• Probability Matrix: An agent-pair predictor (MLP) concatenates pairs of agent features ($z_i, z_j$) to generate a probability matrix $\theta \in [0, 1]^{N \times N}$.
• Sparse Sampling: A sparse adjacency matrix $A$ is sampled from $\theta$ using a Gumbel-Softmax trick (Bernoulli distribution) to ensure differentiability during backpropagation. This allows the graph structure to be learned jointly with policy parameters.

B. Meaningful Graph Learning (Two Innovative Characteristics)
To ensure the inferred graph is "meaningful" and enhances cooperation, the graph learning process is guided by two specific loss functions:

1. Predict-Future (Local Characteristic):
   • Goal: Enable agents to foresee upcoming observations.
   • Mechanism: Uses a Diffusion Convolutional Recurrent Neural Network (DCRNN) on the sampled graph to predict future state changes ($\Delta o_{t+1}$).
   • Loss: Minimizes the difference between predicted and actual future observations ($L_{pre}$). This helps agents make better immediate decisions based on anticipated environmental changes.
2. Infer-Present (Global Characteristic):
   • Goal: Allow partially observed agents to deduce the full global state.
   • Mechanism: Uses an attention mechanism to dynamically weight edges, followed by Graph Convolutional Networks (GCN) to aggregate information across the graph.
   • Loss: Minimizes the difference between the aggregated graph representation and the true global state ($L_{inf}$). This ensures the graph captures the collective environmental context.

C. Policy Learning

• The learned sparse graph is fed into an attention-based graph convolution module within the MARL agent.
• The framework builds upon QMIX, where the total value function is a monotonic mixture of individual agent values.
• The total loss function combines the Temporal Difference (TD) loss for policy optimization and the graph loss ($L_g = L_{pre} + L_{inf}$):
  $$L(\theta) = L_{TD} + \lambda L_g$$

3. Key Contributions

1. Trajectory-Based Graph Inference: The paper pioneers the use of full observation trajectories (rather than one-step snapshots) to infer latent graphs, capturing temporal dynamics and agent dependencies more accurately.
2. Scalable Sparse Graph Sampling: By sampling sparse graphs from a probability matrix derived from trajectories, the method achieves a computational complexity of $O(TN^2)$ (where $T$ is trajectory length), significantly outperforming action-pair based methods ($O(A^2N^2)$) in scalability.
3. Predict-Future & Infer-Present: The introduction of these two characteristics forces the graph to learn both temporal prediction capabilities and global state inference, resulting in more robust and meaningful coordination structures.
4. End-to-End Training: The graph structure and agent policies are optimized simultaneously, allowing the graph to adapt dynamically to the learning progress of the agents.

4. Experimental Results

The method was evaluated on the StarCraft II Multi-Agent Challenge (SMAC), Tag (MPE), and Gather benchmarks.

• Performance vs. SOTA: LTS-CG outperformed state-of-the-art graph-based methods (DCG, DICG, SOP-CG, CASEC) and non-graph baselines (QMIX, MAPPO, MADDPG) across all tested maps. It demonstrated faster convergence and higher final win rates.
• Scalability:
  • On large maps (e.g., 25m vs 25m, 27m vs 30m), methods like SOP-CG and CASEC failed to complete training due to memory limits or excessive computation time. LTS-CG successfully scaled to these scenarios.
  • In the Tag environment, LTS-CG maintained performance when scaling from 10 to 20 agents, whereas other methods degraded significantly.
• Ablation Studies:
  • Trajectories vs. One-Step: Using trajectories for graph learning yielded significantly higher win rates than using one-step observations.
  • Sampling vs. Dense: Sampling a sparse graph from the attention matrix outperformed using the dense attention matrix directly, proving that filtering irrelevant information is crucial.
  • Characteristics: Both "Predict-Future" and "Infer-Present" contributed independently to performance, with the combination yielding the best results.
• Efficiency: LTS-CG showed competitive running times and GPU memory usage, significantly lower than SOP-CG and CASEC on large maps.

5. Significance

This paper addresses a fundamental bottleneck in cooperative MARL: the trade-off between graph expressiveness and computational scalability. By shifting from static, one-step graph inference to temporal, trajectory-based sparse graph learning, LTS-CG enables agents to:

• Learn more robust coordination strategies that account for history and future states.
• Scale to larger numbers of agents without the exponential explosion in computational cost associated with action-pair calculations.
• Operate effectively in partially observable environments by inferring global states from local interactions.

The work provides a new paradigm for graph structure learning in RL, suggesting that incorporating temporal dynamics and specific structural constraints (like prediction and inference tasks) leads to superior multi-agent cooperation.