PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning

Sheng Li, Jayesh K. Gupta, Peter Morales, Ross Allen, Mykel J. Kochenderfer

arXiv:2006.11438v2cs.LGcs.AIcs.MA

TL;DR

Cooperative MARL requires coordination, yet dynamic interaction structures can be difficult to specify with domain heuristics. DICG learns soft coordination graphs with self-attention and integrates agent information through graph convolution. The paper reports improved coordination across predator-prey, SMAC, and traffic-junction tasks, including addressing relative overgeneralization in predator-prey tasks.

  • Problem

    Cooperative MARL needs coordination, while suitable coordination structures can be dynamic and existing approaches may rely on domain heuristics.

    Source: §1 · p. 1

  • Method

    DICG uses self-attention to infer soft, observation-dependent coordination graphs and graph convolution to integrate agent information differentiably.

    Source: §1 · p. 1, §3 · p. 3

  • Results

    DICG addresses relative overgeneralization in predator-prey tasks and is reported effective against MARL baselines across SMAC and traffic-junction tasks.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    The results support DICG as an architecture for learning multi-agent coordination with a trade-off between fully centralized and fully decentralized approaches.

    Source: §1 · p. 2, §5 · p. 8

Abstract

from arXiv · show

Multi-agent reinforcement learning (MARL) requires coordination to efficiently solve certain tasks. Fully centralized control is often infeasible in such domains due to the size of joint action spaces. Coordination graph based formalization allows reasoning about the joint action based on the structure of interactions. However, they often require domain expertise in their design. This paper introduces the deep implicit coordination graph (DICG) architecture for such scenarios. DICG consists of a module for inferring the dynamic coordination graph structure which is then used by a graph neural network based module to learn to implicitly reason about the joint actions or values. DICG allows learning the tradeoff between full centralization and decentralization via standard actor-critic methods to significantly improve coordination for domains with large number of agents. We apply DICG to both centralized-training-centralized-execution and centralized-training-decentralized-execution regimes. We demonstrate that DICG solves the relative overgeneralization pathology in predatory-prey tasks as well as outperforms various MARL baselines on the challenging StarCraft II Multi-agent Challenge (SMAC) and traffic junction environments.

1 INTRODUCTION

Cooperative MARL needs coordination, but centralized joint-action reasoning scales exponentially and decentralization can be suboptimal. DICG learns observation-dependent coordination structures and uses them to support joint-action reasoning across several MARL settings.

1 INTRODUCTION

  • Joint-action spaces grow exponentially with agent count, while decentralized policies can be suboptimal and susceptible to relative overgeneralization.Exploration by other agents can confound an agent’s reward with penalties from their random actions.Source: §1 · p. 1
  • Existing coordination-graph methods model local interactions, but typically assume a static, domain-dependent graph; dynamic structures may require domain heuristics or remain limited to tabular settings.The paper hypothesizes that learning a suitable dynamic graph can help address coordination issues.Source: §1 · p. 1
  • DICG uses self-attention to infer an implicit graph and a graph convolutional network to integrate agent information for joint-action or value reasoning.Differentiable graph construction and action inference let the module operate within an actor or critic and be trained end-to-end with standard policy optimization.Source: §1 · pp. 1–2
  • DICG learns dynamic coordination structures to balance centralized and decentralized methods, and is evaluated on predator-prey, SMAC, and traffic-junction tasks.The paper reports that the learned structure supports an appropriate trade-off between the two approaches.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

The background formalizes cooperative multi-agent decision-making and reviews policy optimization, coordination graphs, self-attention, and graph neural networks. DICG builds on these ideas by learning soft interaction graphs and using differentiable message passing.

2 BACKGROUND AND RELATED WORK

  • The Dec-POMDP formalization specifies agents, global state, per-agent actions and observations, transition and reward functions, policies, and discounted value quantities.The return, value, action-value, and advantage are defined from the joint reward and joint policy.Source: §2 · p. 2

2.1 Policy Optimization

  • Policy optimization uses a surrogate objective and clipped PPO for stable updates; homogeneous agents may share policy parameters in centralized-training, decentralized-execution settings.The section also notes that these approaches do not model coordination structure.Source: §2.1 · p. 2

2.2 Coordination Graphs

  • Coordination graphs encode local interactions and factor joint action-values into individual utilities and pairwise payoffs; DICG instead learns observation-dependent soft edges and uses differentiable graph message passing.The approach avoids explicitly inferring the joint action over a supplied graph.Source: §2.2 · p. 2

2.3 Self-attention

  • Self-attention learns weights between agents to form a soft-edged coordination graph, while Figure 1 shows integrated observations supporting either direct action selection or a centralized baseline.The CTCE path uses a parameter-shared policy; the CTDE path uses an aggregator network for the baseline.Source: §2.3 · p. 2, Figure 1 · p. 3

2.4 Graph Neural Networks

  • A graph convolutional network maps node-feature inputs to node-level feature outputs, enabling local feature extraction from arbitrary graphs.The section situates this mechanism among graph-based approaches to agent interaction and communication.Source: §2.4 · p. 3

3 APPROACH

DICG learns soft, observation-dependent coordination edges with self-attention and integrates agent information through graph convolution. Its differentiable architecture supports both centralized and decentralized execution setups.

3 APPROACH

  • DICG uses self-attention weights as soft coordination-graph edges and graph convolution to integrate agent information, rather than relying on hard-coded graph structure.The resulting architecture is fully differentiable.Source: §3 · pp. 3–4
  • Graph convolution repeatedly propagates information across agents; a residual connection combines the initial and integrated embeddings to assist gradient flow through the attention module and encoder.The convolution uses attention weights and an identity degree matrix.Source: §3 · p. 4
  • In DICG-CE, integrated agent embeddings feed policy networks to produce actions, and standard actor-critic methods train the network end-to-end.The paper reports these embeddings outperform concatenated raw observations passed through an MLP.Source: §3 · p. 4
  • In DICG-DE, a centralized critic uses integrated embeddings to estimate the baseline for advantage computation, while agents act independently at execution.The paper reports that DICG embeddings outperform concatenated raw observations passed through an MLP in this setup.Source: §3 · p. 4

4 RESULTS

Across predator-prey, SMAC, and traffic junction tasks, the experiments compare DICG with centralized and decentralized baselines and examine learned coordination and information integration. DICG performs strongly as coordination demands rise, while easier traffic favors centralized execution.

4.1 Predator-Prey

  • As single-agent capture penalties rise, only DICG reliably and quickly converges to optimality; DEC slows and ends suboptimal, while CENT fails under negative penalties.Without a penalty, CENT-MLP and DEC-MLP perform similarly, though they take more steps to capture all prey than DICG.Source: §4.1 · p. 5, Figure 3 · p. 5
  • As solo-capture penalties rise, DICG assigns more attention to farther agents, matching the need to form capture teams.Figure 4 reports attention weights as graph edge strengths, averaged over five seeds.Source: §4.1 · p. 6, Figure 4 · p. 6
  • Post-DICG embeddings predict other agents’ actions more accurately than pre-DICG embeddings, consistent with agents learning others’ intentions.The comparison uses evaluation trajectories from five random agent pairs.Source: §4.1 · p. 6, Figure 5 · p. 6

4.2 StarCraft II Multi-agent Challenge (SMAC)

  • DICG-DE-LSTM has the highest, most stable, and most sample-efficient win rate in 3s_vs_5z; DICG-CE-LSTM alone wins in 6h_vs_8z.In 3s_vs_5z, DICG agents split into groups, use circular hit-and-run tactics, then reunite against weakened opponents.Source: §4.2 · p. 7, Figure 6 · p. 7

4 RESULTS

  • DICG outperforms VDN and QMIX across SMAC’s cited scenarios and centralized and decentralized baselines in medium and hard traffic.The SMAC comparison is reported in Table 1; the traffic comparison is reported in Table 2.Source: §4.2 · p. 7, Table 1 · p. 7, §4.3 · p. 7

4.3 Traffic Junction

  • In easy traffic, DICG-CE-MLP outperforms DICG-DE-MLP, while CENT-MLP also performs well in this smaller, lower-observation setting.DICG-CE-MLP is described as integrating agent information more efficiently than CENT-MLP.Source: §4.3 · p. 7

Ablation.

The hard-mode traffic-junction ablations compare learned attention and graph convolution with uniform attention and an MLP replacement. DICG-DE-MLP performs slightly better than the uniform-attention variant, while the MLP replacement performs similarly to DEC-MLP.

Ablation

  • In hard-mode traffic junction, DICG-DE-uniform-MLP performs slightly worse than DICG-DE-MLP, while AMLP-DE-MLP performs similarly to DEC-MLP.The ablation results are shown in a zoomed-in view averaged over five random seeds; Table 3 compares success rates.Source: Figure 8 · p. 8, Ablation · p. 8, Table 3 · p. 8
  • DICG-DE-uniform-MLP replaces learned attention with uniform weights of 1/n, while AMLP-DE-MLP replaces graph convolution with an MLP over concatenated agent embeddings and attention weights.Source: Ablation · p. 8
  • The ablations were tested in hard mode, where the number of agents is large and the authors expected attention and graph convolution to matter more for coordination.Source: Ablation · p. 8

5 CONCLUSIONS AND FUTURE WORK

DICG uses self-attention to infer an implicit coordination graph and graph-convolution message passing to compute agent baselines or actions. The paper reports coordination results across predator-prey, StarCraft II micromanagement, and traffic-junction tasks, and identifies sample efficiency as future work.

5 CONCLUSIONS AND FUTURE WORK

  • DICG combines self-attention-based implicit graph construction with graph-convolution message passing to compute agent baseline values in decentralized execution or actions in centralized execution.Source: §5 · p. 8
  • The authors report that DICG solves relative overgeneralization in predator-prey tasks and performs effectively across StarCraft II micromanagement and traffic-junction tasks.Source: §5 · p. 8
  • Future work aims to improve DICG sample efficiency, including by incorporating it into off-policy methods such as deep Q-learning and soft actor-critic.Source: §5 · p. 8

A EXPERIMENT DETAILS

The appendix describes shared PPO settings and points to environment-specific settings in later subsections. It also states that the code is available.

A EXPERIMENT DETAILS

  • The appendix identifies Table 4 as the source for PPO and optimizer parameters.Source: Table 4 · p. 10
  • The appendix reports PPO hyperparameters shared across experiments and says that environment-specific settings appear in following subsections.It notes that batch size is measured in environment steps, nonlinear activations are tanh, and the DICG-DE aggregator is a single linear layer mapping embeddings to one dimension.Source: A EXPERIMENT DETAILS · p. 10
  • The authors state that code for the work is available.Source: A EXPERIMENT DETAILS · p. 10

A.1 Predator-Prey

The predator-prey appendix modifies the environment so predators can observe other predators. It also specifies the field of view and selected training settings.

A.1 Predator-Prey

  • The authors modify the open-source predator-prey environment so other predators are visible in each predator's observation.Source: §A.1 · p. 10
  • Each predator has a 5 × 5-grid field of view centered on itself.Source: §A.1 · p. 10
  • Training uses a maximum of 200 steps per episode, a batch size of 6 × 10^4, and a policy entropy coefficient of 0.1.All approaches except DICG-DE-MLP use an MLP critic, and DICG uses two GCN layers.Source: §A.1 · p. 10

A.2 StarCraft II Multi-agent Challenge (SMAC)

The SMAC experiments use the open-source implementation and scenario definitions, with DICG configured using two GCN layers.

A.2 StarCraft II Multi-agent Challenge (SMAC)

  • DICG uses two GCN layers in the SMAC network architecture.Other network architecture details are listed in Table 7.Source: §A.2 · p. 10
  • The authors redefine each micromanagement scenario’s controlled-agent and opponent counts, unit types, and episode time limits.Map configurations and PPO parameters are listed in Table 6.Source: §A.2 · p. 10
  • The experiments use the open-source SMAC implementation by Samvelyan et al. [32].Source: §A.2 · p. 10
  • Except for DICG-DE-LSTM, the other approaches use an MLP feature baseline for the critic.Source: §A.2 · p. 10

A.3 Traffic Junction

The traffic-junction experiments use the maximum-agent add-rate setting from the referenced curriculum and skip curriculum training.

A.3 Traffic Junction

  • The experiments use the maximum-agent add-rate setting, described as the most difficult curriculum setting, without curriculum training.Source: §A.3 · p. 10
  • The study uses the traffic-junction implementation by Sukhbaatar and Fergus [36].Environment settings and network configurations are listed in Tables 8 and 9.Source: §A.3 · p. 10
  • Cars have a vision range of one grid, and the policy entropy coefficient is 0.02.Source: §A.3 · p. 10
  • Except for DICG-DE-MLP, the other approaches use an MLP baseline for the critic.Source: §A.3 · p. 10

B DESCRIPTIONS FOR COMPARED BASELINE APPROACHES

The comparison includes value-decomposition, coordination-graph, and communication-based MARL baselines, spanning value-based off-policy and on-policy methods.

B DESCRIPTIONS FOR COMPARED BASELINE APPROACHES

Loading 2006.11438v2…