Deep Coordination Graphs

Wendelin Böhmer, Vitaly Kurin, Shimon Whiteson

Abstract

Cooperative multi-agent reinforcement learning (MARL) faces a fundamental trade-off between the scalability of decentralized methods and the representational power of joint-action models. Decentralized approaches often suffer from "relative overgeneralization," failing to learn optimal strategies that require tight coordination. This paper presents Deep Coordination Graphs (DCG), a framework that factors the joint value function into pairwise payoffs. By leveraging deep neural networks, parameter sharing, and message passing, DCG provides a sample-efficient way to model agent dependencies. Experimental results on Predator-Prey and StarCraft II (SMAC) show that DCG effectively overcomes coordination pathologies and outperforms state-of-the-art decentralized baselines.

Introduction

In cooperative MARL, the joint action space grows exponentially with the number of agents, making centralized learning intractable. To address this "curse of dimensionality," methods like Value Decomposition Networks (VDN) and QMIX factor the joint value function into individual agent utilities. While scalable, these methods assume a level of independence that can lead to game-theoretic failures. Specifically, they are prone to relative overgeneralization, where agents learn sub-optimal policies because the optimal joint action appears poor during exploration when not perfectly synchronized.

Deep Coordination Graphs

The Deep Coordination Graph (DCG) framework addresses these limitations by modeling interactions between pairs of agents.

Value Factorization

DCG approximates the joint Q-value as the sum of individual utilities ($f^i$) and pairwise payoffs ($f^{ij}$) for agents connected in a coordination graph $\mathcal{E}$: $$Q(s, a) \approx \sum_{i} f^i(a^i|s) + \sum_{\{i,j\} \in \mathcal{E}} f^{ij}(a^i, a^j|s)$$

Factorization spectrum: (a) independent utilities (VDN/QMIX), (b) pairwise payoffs (DCG), and (c) full joint modeling.

Implementation Details

  • Deep Representation: Utilities and payoffs are modeled using deep neural networks (e.g., GRUs) conditioned on agent histories.
  • Parameter Sharing: To maintain sample efficiency, all agents share the same utility network, and all edges share the same payoff network. Agent-specific behavior is enabled via agent IDs or embeddings.
  • Low-Rank Approximation: To handle large action spaces, DCG uses a low-rank approximation for the payoff matrices, significantly reducing the number of parameters.
  • Action Selection: Finding the greedy joint action is performed via max-plus message passing, an iterative algorithm where agents coordinate with neighbors to maximize the total payoff.

Experimental Evaluation

The authors evaluated DCG on two benchmarks: a custom Predator-Prey grid-world and the StarCraft Multi-Agent Challenge (SMAC).

Overcoming Relative Overgeneralization

In the Predator-Prey task, agents are punished for unsuccessful solo capture attempts. This environment is specifically designed to trigger relative overgeneralization. As shown in the results, decentralized methods like VDN fail to learn the task when punishment is significant ($p = -1.5$), whereas DCG consistently reaches near-optimal performance.

Performance on Predator-Prey with punishment p=-1.5. DCG (red) successfully learns the coordinated strategy, while decentralized baselines (blue/pink) fail.

StarCraft II Results

On the "super hard" maps of SMAC, such as MMM2, a variant called DCG-S (which utilizes privileged global state information during training) outperformed the state-of-the-art QMIX algorithm, demonstrating superior win rates and faster convergence.

Conclusion

Deep Coordination Graphs provide a powerful "sweet spot" for multi-agent coordination. By focusing on pairwise interactions and utilizing parameter sharing, DCG captures the dependencies necessary to solve complex tasks without the computational burden of full joint-action modeling. Future work includes exploring dynamic graph topologies where agents learn which neighbors to coordinate with on-the-fly.

Summary updated

BibTeX
@inproceedings{bohmer2020deep,
  author = {Wendelin Böhmer and Vitaly Kurin and Shimon Whiteson},
  title = {{Deep Coordination Graphs}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=uLy8RW8qvb},
}
Figure