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)$$
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.
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