PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Coordination Graphs

Wendelin Böhmer, Vitaly Kurin, Shimon Whiteson

arXiv:1910.00091v4cs.LGcs.AIcs.MA

TL;DR

Collaborative MARL struggles with exponentially large joint action spaces and coordination failures under relative overgeneralization. The paper introduces DCG, which factors joint values over coordination graphs, uses message passing for greedy action selection, and trains shared deep payoff and utility networks end-to-end. DCG solves harder predator-prey tasks than decentralized baselines and outperforms QMIX on some StarCraft II levels, while its transfer across graph topologies remains unevaluated.

  • Problem

    Collaborative MARL must handle exponentially growing joint action spaces, while decentralized value factorization can fail under relative overgeneralization.

  • Method

    DCG factors joint values with coordination graphs, maximizes them through message passing, and learns shared deep payoff and utility functions with Q-learning.

  • Results

    DCG is the only compared algorithm to solve the harder predator-prey tasks and outperforms QMIX on some StarCraft II micromanagement levels.

  • Takeaways & Limitations

    DCG enables coordination-graph value factorization on tasks with large state and action spaces while improving over existing coordination-graph methods.

  • Takeaways & Limitations

    Transfer of a learned DCG to different graphs or topologies is proposed but not evaluated in this paper.

Abstract

from arXiv · show

This paper introduces the deep coordination graph (DCG) for collaborative multi-agent reinforcement learning. DCG strikes a flexible trade-off between representational capacity and generalization by factoring the joint value function of all agents according to a coordination graph into payoffs between pairs of agents. The value can be maximized by local message passing along the graph, which allows training of the value function end-to-end with Q-learning. Payoff functions are approximated with deep neural networks that employ parameter sharing and low-rank approximations to significantly improve sample efficiency. We show that DCG can solve predator-prey tasks that highlight the relative overgeneralization pathology, as well as challenging StarCraft II micromanagement tasks.

1. Introduction

Cooperative MARL must generalize over exponentially large joint action spaces while preserving coordination. DCG addresses this with a scalable coordination-graph value factorization, parameter sharing, and message passing, and succeeds on difficult predator-prey and StarCraft II tasks.

  • Motivation: Joint action spaces grow exponentially with agent count; eight agents with six actions each already produce more than one million joint actions.Efficient MARL therefore requires generalization over large joint action spaces.
  • Motivation: Fully decentralized utility factorization can represent optimal deterministic policies but may fail under relative overgeneralization during exploration.Random actions by other agents can make coordinated actions appear worse than uncooperative alternatives.
  • Coordination graphs: Coordination graphs represent joint values through payoff functions on agent pairs or larger groups, providing richer representations than independent utilities.Local message passing can recover greedy actions, although tabular payoff representations do not scale to real-world tasks.
  • DCG: DCG combines pairwise payoffs, individual utilities, parameter sharing, and deep networks to scale coordination graphs beyond VDN and QMIX.Sharing parameters across factors improves sample efficiency compared with unfactored values.
  • DCG: DCG maximizes values through local message passing with complexity O(km(n + m)|E|), compared with O(m^n) for unfactored DQN.The method can also generalize to coordination graphs with hyper-edges.
  • Evaluation: DCG is the only compared algorithm to solve the harder predator-prey tasks, and it outperforms QMIX on some StarCraft II micromanagement levels.The authors provide an open-source implementation for reproducibility.

2. Background

The background formalizes collaborative MARL and explains why ordinary DQN becomes infeasible as joint spaces grow. Value factorization and coordination graphs provide structured alternatives whose expressiveness and maximization depend on graph topology.

  • MARL formulation: A Dec-POMDP models agents acting in a shared environment with partial observations, joint actions, collaborative rewards, and discounted returns.Episodes are finite, and each agent observes the state only partially.
  • MARL formulation: The goal of collaborative MARL is to learn a policy that chooses joint actions maximizing expected discounted future rewards through an optimal Q-value function.Greedy action selection uses the action with the highest optimal Q-value.
  • Deep Q-learning: DQN approximates Q-values with neural networks trained by minimizing mean-squared Bellman error, using replay buffers and target networks for stability.Double Q-learning further stabilizes training by selecting next actions with the current network.
  • Deep Q-learning: Applying DQN directly to MARL is infeasible because state and action spaces grow combinatorially and all actions must be evaluated for maximization.Value factorization methods were developed to enable efficient maximization.
  • Coordination graphs: Coordination graphs assign vertices to agents and edges to payoff functions, with message passing locally maximizing the induced Q-function.The empty-edge case yields VDN, while additional edges represent pairwise joint actions and can help avoid relative overgeneralization.
  • Coordination graphs: Pairwise graphs use up to 1/2(n^2 − n) edges, whereas degree-d hyper-edges can require up to n!/(d!(n−d)!) factors.Message convergence is guaranteed for acyclic graphs, while normalization often helps cyclic graphs converge.

3. Method

DCG learns coordination-graph utilities and payoffs with shared deep networks using local histories, low-rank approximations, and optional privileged state information. Its design targets scalable learning while retaining richer coordination than independent utility factorization.

  • Architecture: DCG learns coordination-graph utility and payoff functions with deep neural networks while restricting inputs to participating agents’ local histories.This avoids separately learning functions for every payoff and reduces dependence on observing the full joint action space.
  • Architecture: DCG shares parameters across payoff and utility functions through a common recurrent neural network to improve sample efficiency.This differs from prior approaches that learn independent payoff functions without conditioning on state or histories.
  • Low-rank approximation: Low-rank payoff approximation replaces |Ai||Aj| action-pair outputs with 2K A outputs, while rank K = min{|Ai|, |Aj|} preserves expressiveness.Lower ranks share parameters and updates, speeding learning in large action spaces.
  • Topology transfer: Permutation invariance is implemented by averaging payoffs computed from both agents’ perspectives, while retaining asymmetric payoff matrices.The intended benefit is transfer or generalization to different graph topologies, which the paper does not evaluate.
  • Privileged information: DCG-S adds a privileged bias function using global state information during training while keeping execution decentralized.Both DCG variants are trained end-to-end with DQN loss and Double Q-learning.
  • Design rationale: DCG provides a flexible function class between independent and unfactored value representations, tailored to task-specific coordination needs.Its design addresses relative overgeneralization while avoiding the sample demands of fully expressive alternatives.

4. Related Work

Related work addresses cooperative MARL through decentralized policies, factored value functions, centralized critics, coordination graphs, and graph neural networks. These approaches trade off scalability, representational capacity, learnability, and sample efficiency in different ways.

  • Independent Q-learning models each agent as an independent learner, but changing policies make each agent’s task nonstationary.
  • VDN sums independent utilities, while QMIX uses a state-dependent monotonic mixing network so the central value remains independently maximizable.
  • Actor-critic methods decentralize execution while allowing critics to condition on global states and all agents’ actions during training.
  • Centralized joint Q-functions provide broader conditioning but do not support parameter sharing as extensively as value factorization, reducing sample efficiency.
  • Mean-field MARL and related low-rank factorizations reduce sample complexity for settings with hundreds of agents by sharing pairwise payoff parameters.
  • Coordination graphs represent joint values with pairwise payoffs, while graph neural networks must learn the joint maximization required for Q-learning.

5. Empirical Results

Across predator-prey and StarCraft II tasks, DCG addresses coordination failures while balancing representational capacity, reliability, and sample efficiency through graph structure, parameter sharing, and low-rank payoffs.

  • The evaluation compares DCG topologies, baseline Q-learning algorithms, coordination-graph baselines, low-rank approximations, and StarCraft II controllers.Experiments cover relative-overgeneralization predator-prey tasks, artificial decentralization, and six SMAC levels.
  • 5.1. Relative Overgeneralization: For punishment p = −2, QMIX, IQL, and VDN obtain return 0, whereas fully connected DCG learns near-optimal policies quickly and reliably.QTRAN, CG, and LRQ can represent the joint value but require more samples or learn unreliably because of large joint action spaces or imperfect maximization.
  • 5.1. Relative Overgeneralization: Fully connected DCG is more reliable than CYCLE, LINE, and STAR topologies, whose high deviations reflect seeds that either succeed or fail completely.The paper attributes this advantage to the fully connected graph’s larger function class and fewer assumptions.
  • 5.2. Artificial Decentralization: In the non-decentralizable hunting task, DCG and CG learn near-optimal coordination, while decentralized baselines remain suboptimal and non-parameter-sharing variants perform worse.DCG can propagate information from the agent that finds the indicator through shared graph edges.
  • 5.1. Relative Overgeneralization: Low-rank payoff approximations significantly improve sample efficiency in the coordination task and slightly improve it in the hunting task without materially reducing performance.Rank K = 1 already performs slightly better than the full independent-payoff architecture in the hunting task.
  • 5.4. Scaling Up to StarCraft II: On SMAC, DCG-S matches QMIX while DCG and DCG-S perform comparably to their VDN counterparts, indicating scalability without reducing sample efficiency.The authors conclude SMAC likely does not exhibit relative overgeneralization; both variants use rank-1 payoffs in the reported experiments.

6. Conclusions & Future Work

The paper presents DCG as a scalable coordination-graph value-factorization architecture and reports results across relative-overgeneralization and StarCraft II tasks. It also introduces low-rank payoffs, privileged bias functions, and extensions to hyper-edges and changing graph topologies.

  • Conclusions: DCG uses coordination-graph value factorization with message passing, enabling deep Q-learning on tasks where decentralized baselines fail.The paper states that centralized critics are less sample efficient than DCG in these settings.
  • Conclusions: Fully connected DCG performed best in all experiments and is recommended without prior task-topology knowledge.Its computational complexity scales quadratically rather than exponentially with joint value estimates.
  • StarCraft II: DCG-S performs competitively with QMIX on StarCraft II micromanagement tasks, while DCG and DCG-S remain comparable to their VDN counterparts.These results indicate that added payoffs and message passing do not reduce sample efficiency on SMAC.
  • Future Work: The architecture supports low-rank approximations for large action spaces and can be extended with hyper-edges connecting more than two agents.Low-rank approximations and coordinate ascent can also be used for high-order hyper-edges.
  • Future Work: DCG’s permutation invariance may support transfer across graph topologies and training on dynamically generated graphs.The paper identifies attention-based graph generation and state-dependent coordination choices as future directions.

A.1. Baseline algorithms

The baseline appendix describes independent, factorized, centralized-critic, coordination-graph, and low-rank alternatives to DCG. It also reports that LRQ learns the relative-overgeneralization task only with enough factors and does so slowly with substantial seed variance.

  • Baseline algorithms: IQL models each agent as an independent Q-learner, but other agents’ changing policies make the learning problem nonstationary.Parameter sharing can nevertheless make IQL sample efficient in practice.
  • Baseline algorithms: VDN sums independent utility functions, while QMIX uses a monotonic mixing hypernetwork conditioned on the global state.Both preserve decentralized greedy action selection through their factorization constraints.
  • Baseline algorithms: QTRAN learns a centralized critic and distills a decentralized VDN-greedy policy under equality and inequality constraints.The appendix uses QTRAN-base, whose combined loss includes temporal-difference, optimal-action, and non-optimal-action terms.
  • Baseline algorithms: The CG baseline shares a recurrent encoder but does not share utility or payoff parameters across agents and edges.Its implementation otherwise follows the same algorithms as DCG.
  • Low-rank approximation: LRQ approximates the full joint value as a sum of K products of agent-specific factor functions rather than using message passing.Coordinate ascent maximizes the approximation, and the experiments vary K over 1, 4, 16, 64, 256, and 1024.
  • Low-rank approximation: Given enough factors, LRQ learns the relative-overgeneralization task slowly and with high variance between seeds.With the original large joint-history input, the approximation did not learn; input restrictions and parameter sharing enabled comparison with DCG.

A.2. DCG Algorithms

The implementation appendix points readers to pseudocode and an open-source PyMARL implementation for the algorithms used in the paper.

  • A.2. DCG Algorithms: Algorithms 1, 2, and 3 compute utilities and payoffs, form the joint Q-value, and return greedy joint actions.The implementation is available in the PyMARL framework.

A.3. Hyper-parameters

The appendix reports shared implementation settings for all algorithms, including PyMARL-based recurrent agent encoders and training hyper-parameters. It also describes architecture-specific networks for DCG, QMIX, QTRAN, and LRQ.

  • Common settings: All algorithms use PyMARL, with hyper-parameters kept close to the framework defaults and consistent across methods.This provides a common implementation basis for the comparisons.
  • Common settings: Training uses γ = 0.99, decayed ϵ-greedy exploration, and evaluation on 20 greedy trajectories every 2000 time steps.Results are smoothed per seed before means and standard errors are computed.
  • Agent encoders: Agents encode histories with a shared 64-neuron linear layer and GRU, with one-hot agent IDs distinguishing shared parameters.The CG baseline instead uses 512-neuron recurrent layers.
  • Architecture-specific networks: DCG utilities and payoffs are linear projections from GRU outputs, while QMIX generates a two-layer mixing network from the global state.QMIX uses ELU activations and 32-neuron hypernetwork layers.
  • Architecture-specific networks: QTRAN’s critic conditions on all agents’ recurrent outputs, other agents’ actions, and the current agent ID.Its critic uses four 64-neuron linear layers with ReLU activations.
  • Architecture-specific networks: LRQ main-text results use the CG state encoding with K = 64.The appendix also reports LRQ-specific architecture and optimization settings.
  • Optimization: Optimization applies one RMSprop update after each episode using batches of 32 episodes from a 500-episode replay buffer.Gradients with norm at least 10 are clipped, and target networks are copied every 200 episodes.

A.4. StarCraft II details

The StarCraft II evaluation uses six SMAC maps with matched hyperparameters and rank-1 payoff approximations, while comparing DCG variants against QMIX and VDN. Greedy joint actions are selected through iterative message passing and evaluated using the resulting joint Q-value.

  • Experimental setup: Six SMAC maps were evaluated with identical hyperparameters; micro focus was supplied by the SMAC authors.Results compare DCG-S, DCG, QMIX, and VDN; both DCG variants use rank-1 payoff approximations.
  • Experimental setup: Figure 8 reports mean cumulative test-episode reward with shaded standard error for QMIX, VDN, VDN-S, DCG, and DCG-S.The compared DCG configurations use fully connected graphs, rank K = 1 payoff approximations, and, for DCG-S, an additional state-dependent bias function.
  • Experimental setup: Results differ from Samvelyan et al. because of slightly different parameters and updating after every episode with PYMARL’s episode runner.The authors report that these choices substantially improved QMIX performance.
  • Results: DCG-S clearly outperforms QMIX on the super-hard MMM2 map and learns faster on so many baneling, while QMIX performs better on 3s vs 5z.The authors attribute the latter possibility to the small number of agents and note that SMAC may not strongly exhibit relative overgeneralization.
  • DCG computation: The DCG implementation computes utility and payoff tensors using a rank K approximation before evaluating the joint Q-value.Unavailable actions are assigned −∞, while low-rank approximations produce payoff tensors for the coordination graph.
  • DCG computation: Greedy action selection performs k forward and backward message passes, then retains the joint action with the highest computed Q-value.Message normalization may be applied to support convergence, and the final action maximizes the joint Q-value over all agents.
Loading 1910.00091v4…