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

In plain words

Teams of learning agents often need to know who to talk to. Sending every message to every teammate is wasteful and can drown out useful signals, but picking the right partners is not obvious because the team structure is never written down. This paper proposes that each agent watch what its teammates did over the recent past, estimate how strongly each pair of agents depends on each other, and then keep only a sparse set of links, sampled at random in proportion to those estimates.

Two extra training signals make the links more meaningful. One asks agents to predict how their observations will change next, so the links carry useful history. The other asks the whole set of links to reconstruct what the true game state looks like, so the links reflect the wider situation and not only one agent's view. The graph is learned together with the team's policy, end to end, in one training loop. The authors test it on StarCraft II battles and report faster early learning and stronger results than several graph-based baselines.

TL;DR

• Cooperative MARL methods often use dense or fully connected agent graphs, which are costly and carry redundant messages §1 tab. 1.
• LTS-CG samples a sparse agent-pair graph from probabilities computed on observation histories, trained with a Gumbel relaxation §4.1.1 eq. 4–eq. 6.
• Two auxiliary losses, Predict-Future and Infer-Present, shape the graph; the graph is trained end to end with a QMIX-based policy learner §4.1.2 §4.2.
• Results are author-reported on six SMAC maps and figure-based only; the paper's own text and code differ in several places (see Paper vs code).

Problem

Coordination graphs in MARL either connect all agents with unweighted or weighted edges, or they sparsify a dense graph. The authors argue that existing methods (i) use only one-step observations, so the graph ignores history, and (ii) compute action-pair payoffs whose cost is O(A^2 N^2) for N agents with A actions each §1. The paper also notes that the graph is never given and must be inferred §1 §2.

Method

Setting. Cooperative tasks are modelled as a POMDP with n agents, a shared reward and a discount factor, and each agent acts on its own action-observation history §2. The team is viewed as a dynamic graph G = (V, E) whose nodes are the agents §2.

1. Sparse graph construction §4.1.1.

• Each agent's observation trajectory is passed through a convolution along time followed by a fully connected layer eq. 4. Trajectories shorter than the maximum are zero-padded §4.1.1.
• A pair predictor maps the concatenated features of agents i and j through two fully connected layers to a probability θ_ij eq. 5.
• Edges are drawn as Bernoulli variables with probability θ. The paper uses a Gumbel relaxation so gradients can pass through the sample: the difference of two Gumbel(0, 1) noise terms is added to the logit of θ and passed through a sigmoid with a temperature s eq. 6. As s goes to 0 the sample approaches a hard Bernoulli draw.
• The graph parameters are folded into the network parameters ω. The learning objective is the expected graph loss over sampled graphs eq. 3.

2. Predict-Future §4.1.2.

• A one-layer diffusion-convolutional GRU (DCRNN-style) runs over all agents' observations, with graph convolution defined by the sampled graph eq. 7 and eq. 8. Diffusion degree K = 3 §4.1.2.
• The hidden output at each step predicts the change Δo to the next observation. The loss sums, over agents and future steps, the L2 norm between the predicted next observation (current observation plus predicted change) and the actual next observation eq. 9.

3. Infer-Present §4.1.2.

• Each agent's current observation is embedded by an MLP to e_t^i §4.1.2.
• An attention matrix μ_t^ij is computed from e_t with a learned bilinear form and normalised over the neighbours of agent i in the graph eq. 10.
• The weighted adjacency is updated as A' = C_t A (the paper writes this product without specifying elementwise or matrix multiplication; see Pitfalls). Two GCN layers with symmetric degree normalisation of A' run over the agents' embeddings eq. 11.
• A readout averages the agents' final embeddings to a single graph feature g_t eq. 12. The loss sums, over time steps, the L2 norm between g_t and the true environment state s_t eq. 13.

4. Graph loss. L_g = L_pre + L_inf eq. 14. The graph objective in eq. 3 is instantiated with this L_g.

5. Cooperative MARL with LTS-CG §4.2.

• The sampled graph's edges are re-weighted at every step by the attention computed on the current observations eq. 10.
• Each agent's message m_i is its row of the GCN output eq. 11. Its local value is Q_i(τ_i, a_i, m_i) §4.2.
• The per-agent values are combined monotonically with QMIX §4.2. The greedy joint action is the per-agent argmax eq. 15.
• Training minimises L(θ) = L_TD + λ L_g eq. 16, where L_TD is the squared TD error against a periodically updated target network eq. 17.
• The buffer initially holds a fully connected graph; later it stores the learned sparse graph and reuses it. At test time only the encoder is used to produce the graph §4.2.

# One LTS-CG training step  [§4.1] [§4.2]  (the paper has no algorithm box)
# Input: a batch of episodes with obs, last actions, state, reward
# Output: updated parameters

def train_step(batch):
    # Summarise each agent's history with conv + FC  [§4.1.1] [eq. 4]
    histories = batch.obs_and_last_action         # (B, T, n, d_in)
    z = fc(conv_over_time(histories))             # (B, n, d_z)

    # Score each ordered agent pair  [§4.1.1] [eq. 5]
    theta = fc(fc(concat(z_i, z_j)))              # (B, n, n), in [0, 1]

    # Sample a sparse graph with a Gumbel relaxation  [§4.1.1] [eq. 6]
    adjacency = gumbel_bernoulli(theta, s)        # (B, n, n)

    # Predict-Future: forecast the next observation change  [§4.1.2]
    # [eq. 7] [eq. 8] [eq. 9]
    delta_obs = dcrnn_diffusion(obs, adjacency, steps=3)
    loss_pre = sum_l2(obs + delta_obs - obs_next)

    # Infer-Present: attention-weighted GCN readout vs the true state
    # [eq. 10] [eq. 11] [eq. 12] [eq. 13]
    weights = attention(e_t, neighbours_of=adjacency)
    h = gcn(e_t, adjacency_times(weights))
    g_t = mean_over_agents(h)
    loss_inf = sum_l2(g_t - state)

    # Policy: per-agent Q with messages, mixed by QMIX  [§4.2] [eq. 15]
    q_total = qmix(q_per_agent(obs, h))
    loss_td = td_error(q_total, target_q_total)

    # Total objective  [§4.2] [eq. 16]
    loss = loss_td + lam * (loss_pre + loss_inf)
    update_parameters(loss)

Hyperparameters

Values below come from the paper's text where stated. The source also contains hyperparameter tables, but they are commented out in the LaTeX and are therefore not part of the published paper; they are not used here. Official-code values are marked as code and are not the paper's own claims.

Results

Author-reported. Setup: StarCraft II (SMAC) maps, including 8m, 10m_vs_11m, 3s5z, 1c3s5z, 8m_vs_9m, MMM2, plus 25m and 27m_vs_30m for scale §5 fig. 3 fig. 4. Tag and Gather (MPE and the Climb-game extension) are also used §5 fig. 6. Baselines: QMIX, DCG, DICG, SOP-CG, CASEC §5.1.1; DDN, MAPPO, MADDPG §5.1.2.

The win-rate results are plots only; the paper gives no table of win rates, so this card reports only what the text says about them.

• Six SMAC maps: LTS-CG converges faster early than the compared methods on all six maps, with early-training thresholds stated as 0.6 million steps for 8m, 2 million for MMM2 and 1 million for the others §5.1.1 fig. 3.
• Lower variance than some baselines on specific maps (CASEC on 3s5z, DICG on 8m_vs_9m, DCG on 10m_vs_11m) §5.1.1.
• Large maps (25m, 27m_vs_30m): SOP-CG and CASEC did not complete the runs; DCG did not finish 27m_vs_30m. Text reports QMIX outperforming DCG and DICG there §5.1.1 fig. 4.
• Non-graph baselines (3s5z, 8m_vs_9m): MAPPO converges faster initially on 3s5z, LTS-CG ends slightly higher; LTS-CG beats MAPPO on 8m_vs_9m. DDN is not competitive. MADDPG stays below 50% win rate after 2 million steps §5.1.2 fig. 5.
• Tag (10 agents / 3 adversaries, 20 / 5) and Gather: LTS-CG scales from 10 to 20 agents; SOP-CG and CASEC did not finish 20 agents in 7 days; DCG drops when scaling §5.2 fig. 6.
• Trajectories versus one-step observations: a trajectory-based graph beats both one-step variants on 3s5z and 10m_vs_11m §5.3.1 fig. 7.
• Sampling versus using the attention matrix directly: sampling wins on 3s5z and 10m_vs_11m §5.3.2 fig. 8.
• Loss variants: any graph loss beats none on 8m_vs_9m, 3s5z and Gather; L_pre adds value on top of L_inf §5.3.3 fig. 9.
• Graph-loss weights: performance first rises and then falls as λ grows (sweep 0, 1, 10, 50) §5.3.4 fig. 10. For separate L_pre and L_inf weights in {0, 1, 5, 10, 50}, the best reported pair is 10 and 10 on 8m_vs_9m §5.3.4 fig. 11.

Runtime and GPU memory (author-reported, same hardware as §5). Format: 1k steps (s) / 1m steps (h) / GPU memory tab. 2 tab. 3 tab. 4.

tab. 1 compares graph types and complexity: LTS-CG is sparse, uses trajectories, and has graph cost O(TN^2), against O(A^2 N^2) for the action-pair methods tab. 1 §5.5.

Paper vs code

Official code: https://github.com/Wei9711/LTSCG, linked in the paper §5, at commit ec18028f8e11190c973d9b00613e0c052086473a, Apache-2.0 (LICENSE file). The LTS-CG run is src/config/algs/ltscg.yaml with learner LTSCG_learner and controller Ltscg_mac ltscg.yaml (README run command).

1. The policy does not use the sampled graph. The LTS-CG controller runs its GCN on the dense attention matrix only, and does not read the stored graph ltscg_controller.py. The sampled graph enters only the graph-loss path, where it multiplies the attention weights LTSCG_learner.py. The paper says the sampled graph's edges carry the messages used by the policy §4.2. A reimplementation that follows the paper gates messages with the sampled graph; the released code does not. (The DICG controller does read the graph: dicg_controller.py.)

2. Attention is not restricted to graph neighbours. Eq. 10 normalises over the neighbours N_i eq. 10. The attention module applies softmax over all agents attention_module.py.

3. GCN nonlinearity and normalisation differ. Eq. 11 uses ReLU and symmetric degree normalisation eq. 11. The GCN uses tanh and multiplies the adjacency directly, with no degree normalisation gcn_module.py.

4. Edge sampling is a two-way hard Gumbel softmax, not eq. 6. Edge logits come from convolutions over episode observations plus fully connected layers, not from θ = FC(FC(z_i ‖ z_j)) eq. 5. The sample is hard (one-hot, straight-through) with temperature 0.5 GTSModel.py LTSCG_learner.py.

5. The edge model reads previously stored graphs. The encoder averages the batch's stored graphs and uses them as edge weights in a message step before the edge logits GTSModel.py. The paper does not describe this input.

6. Diffusion cell normalisation. The DCRNN cell adds self-loops and row-normalises a single matrix cell.py cell.py. Eq. 8 uses separate out- and in-degree normalisations eq. 8.

7. Predict-Future loss. The code computes an MSE between MLP embeddings of the predicted and the actual next observation, not the L2 norm of eq. 9 LTSCG_learner.py. The decoder runs for the full input length; the config's horizon: 12 is not used by the decoder forward pass GTSModel.py ltscg.yaml.

8. Infer-Present loss. The code compares an MLP of the mean-pooled GCN output with an MLP of the state, using MSE LTSCG_learner.py. Eq. 13 sums L2 norms against the raw state eq. 13.

9. Loss weights. The main learner adds the three terms with unit weights LTSCG_learner.py. The graph_loss_weight key in the config is read only by the _pre and _inf learners LTSCG_pre_learner.py LTSCG_inf_learner.py.

10. Graph initialisation. The buffer's initial graph is fully connected minus self-loops episode_buffer.py, which matches the paper §4.2. Whether the learned graph is written back to the buffer is not verified: the learner writes it into the sampled batch LTSCG_learner.py.

11. Config leftovers. The GTS block still lists traffic-dataset values (num_nodes: 207, dim_fc), which the learner overwrites ltscg.yaml LTSCG_learner.py.

12. TD target. The code uses double-Q action selection by the online network, with the target network evaluating it ltscg.yaml LTSCG_learner.py. Eq. 17 uses a plain max over the target network eq. 17.

Pitfalls

• Dense versus sparse policy. The released policy never uses the sampled sparse graph, at training or test time (Paper vs code, item 1). Results from the released code may not reflect the sparse-graph behaviour that the paper's ablations describe §5.3.2.
• Attention product is ambiguous. The paper writes A' = C_t A §4.1.2 without saying whether it is a matrix or elementwise product. The code uses elementwise multiplication LTSCG_learner.py.
• Default λ versus best sweep value. The default is λ = 1 §5, but the reported best pair of individual weights is 10 and 10 §5.3.4 fig. 11. The text says that choosing λ per scenario needs further experiments §5.3.4.
• Unnamed constants. The text names "b" and "c" as weights, but neither appears in eq. 16 or in the code §5 eq. 16.
• Gumbel temperature is not stated in the paper. The code uses 0.5.
• Figure captions and text disagree on Fig. 4. The caption says SOP-CG and DCG did not complete 2 million steps and CASEC ran out of memory fig. 4. The text says SOP-CG and CASEC did not complete either map and DCG did not finish 27m_vs_30m §5.1.1.
• Complexity is stated two ways. The abstract says cost depends only on the number of agents. The body gives O(TN^2) with T the observation length used for graph learning §1 tab. 1. The cost of the trajectory length matters for long episodes.
• Baseline changes. DDN uses 64 agent dimensions instead of 256 for consistency across methods §5.1.2. CASEC uses λ_sparse = 0.3 and SOP-CG uses the tree organisation §5.1.1. These are not the baselines' published defaults.
• Memory cost. LTS-CG uses more GPU memory than QMIX and DICG on all three reported maps (e.g. 11.91 GB against 1.93 GB for QMIX on 25m) tab. 2 tab. 3 tab. 4.
• Five seeds, figure-only results. Variance is shown as shading in the curves §5.3.1; no table of final win rates is given.

Lineage

• Builds on: QMIX for the value mixing §4.2; DCRNN for the Predict-Future recurrent unit §4.1.2; Gumbel-based differentiable sampling for the graph §4.1.1; GCN message passing §4.1.2.
• Compared against: DCG, DICG, SOP-CG, CASEC, G2ANet-style one-step sparse graphs (as an ablation) §5.1.1 §5.3.1; DDN, MAPPO, MADDPG §5.1.2.
• The paper also relates itself to later graph-based MARL works it cites §5.5; those works are not covered by a card here.