Deep Coordination Graphs

By Wendelin Böhmer, Vitaly Kurin, Shimon Whiteson. 2019

219 citations recorded by the source corpus.

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 factorizing 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 and parameter sharing improves generalization over the state-action space. We show that DCG can solve challenging predator-prey tasks that are vulnerable to the relative overgeneralization pathology and in which all other known value factorization approaches fail.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition, Reinforcement Learning, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Reinforcement Learning

In Graph Learning

Citations in the corpus

Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning (2020, methodology): “Bhmer et al. (2019) also extend coordination graphs to the deep RL setting, making use of parameter sharing and limiting the graphs to contain only pairwise edges, in order to consider more complex scenarios.”
Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge? (2020, methodology): “In this case, random occurrences of such successful coordination events are a needle in a haystack and monotonic value factorisations cannot represent the non-monotonic team reward function [3].”
Weighted QMIX: Expanding Monotonic Value Function Factorisation (2020, methodology): “As shown in [2], QMIX fails to learn a policy that achieves positive test reward, and our results additionally show the same negative results for MADDPG and MASAC.”
AI-QMIX: Attention and Imagination for Dynamic Multi-Agent Reinforcement Learning (2020, methodology): “This factored representation is less expressive than learning the full joint action value function [5]; however, these methods tend to perform better empirically than those that learn joint action value functions, potentially due to these representations exploiting independence properties among…”
Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning (2020, background): “While factored value functions can only represent a limited subset of all possible value functions (Böhmer et al., 2020), they tend to perform better empirically than those that learn unfactored joint action value functions (Oliehoek et al.”
Towards Open Ad Hoc Teamwork Using Graph-based Policy Learning (2020, methodology): “These baselines will allow us to investigate what advantage GNNs provide in training and generalization performance, when action probabilities help learning, which method of integrating action probabilities is most useful, and how GPL’s approach to computing action values compares to prior methods.”
Deep Multi-Agent Reinforcement Learning for Decentralized Continuous Cooperative Control (2020, background): “Despite being more expressive, QTRAN does not scale well to complex environments, such as StarCraft II (Samvelyan et al., 2019; Bohmer et al., 2019) and may not generalise well to continuous action spaces due to the point-wise nature of its auxiliary losses.”
Local Information Agent Modelling in Partially-Observable Environments (2021, methodology): “We evaluate LIAM in three different multi-agent environments: double speaker-listener [Mordatch and Abbeel, 2017, Lowe et al., 2017], level-based foraging (LBF) [Albrecht and Stone, 2017, Papoudakis et al., 2020], and a modiﬁed version of predator-prey proposed by [Böhmer et al., 2020].”