Deep Coordination Graphs
Authors: Wendelin Boehmer
Vitaly Kurin
Shimon Whiteson
Venue:  (2020)
Keywords: multi-agent reinforcement learning
coordination graph
deep Q-learning
value factorization
relative overgeneralization

Abstract: 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.

Under review as a conference paper at ICLR 2020
DEEP COORDINATION GRAPHS
Anonymous authors
Paper under double-blind review
ABSTRACT
This paper introduces the deep coordination graph (DCG) for collaborative multi- agent reinforcement learning. DCG strikes a flexible trade-off between represen- tational 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 gener- alization over the state-action space. We show that DCG can solve challenging predator-prey tasks that are vulnerable the relative overgeneralization pathol- ogy and in which all other known value factorization approaches fail.
INTRODUCTION
One of the central challenges in cooperative multi-agent reinforcement learning (MARL. Oliehook & Amato 2016) coping with the size of the joint action space, which grows exponentially in the number of agents. For example, this paper evaluates tasks where eight agents each have six actions to choose from, yielding a joint action space with more than a million actions. Efficient MARL methods must thus be able to generalize over large joint action spaces, in the same way that convolutional neural networks allow deep RL to generalize over large visual state spaces.
Even though few benchmark tasks actually require agent policies to be independently executable, one common approach to coping with large action spaces is to decentralize the decision policy and/or value function. For example, Figure [ shows how the joint value function can be factorized into functions that each depend only on the actions of one agent (Sunehag et al., 2018 Rashid et al.) 2018). Consequently, the joint value function can be efficiently maximized if each agent simply selects the action that maximizes its corresponding utility function. This factorization can represent any deterministic policy and thus can represent at least one optimal policy. However, that policy may not be learnable due to a game-theoretic pathology called relative overgeneralization! (Panait jet al. 2006); during exploration other agents act randomly and punishment caused by uncooperative agents may outweigh rewards that would be achievable with coordinated actions. If the employed value function does not have the representational capacity to distinguish the values of coordinated and uncoordinated actions, optimal policy cannot be learned.
However, Castellini et al. (2019) show that higher-order factorization of the value function works surprisingly well in one-shot games that are vulnerable to relative overgeneralization, even if each factor depends on the actions of only a small subset of agents. Such a higher-order factorization undirected coordination graph (CG, Guestrin et al.] (002a), where each
can be expressed vertex represents one agent and each Htyper-)edge one payoff function over the joint action space of the connected agents. Figure I shows CG with pairwise edges and the corresponding value factorization. Depending on the CG topology, the value can thus depend nontrivially on the actions of all agents, yielding richer representation. Although the value can no longer be maximized by each agent individually, the greedy action can be found using message passing along the edges (also known as belief propagation, |Pearl 1988). Sparse cooperative Q-learning (Kok & Vlassis (006) applies CGs to MARL but does not scale to modern benchmarks, as each payoff function ( and f23 in Figure [p) is represented as table over the state and joint action space of the connected agents. Castellini et al.] (2019) use neural networks to approximate payoff functions, but only in one-shot games, and still require unique function for each edge in the CG. Consequently, each agent group, represented by an edge, must still experience all corresponding action combinations, which can require executing a significant subset of the joint action space.
Not be confused with generalization in the context of function approximation.

---

Under review as a conference paper at ICLR 2020
(a) sum of independent utilities
(b) sum painwise payoffs
(c) no factorization
parameter- sharing
parameter- sharing
ala',a", _ f (s))ss) (((4))) ((a))s) g(a',a", aP(s)) = (a ,0)) + (a) (1)))
q(a',at,a"(s)
Figure I: Examples of value factorization for 3 agents: (a) sum of independent utilities (as in VDN, Sunchag et al. 2018) corresponds to an unconnected CG. QMIX uses monotonic mixture of util- ities instead of a sum (Rashid et al. 2018); (b) sum of pairwise payoffs (Castellini et al. 2019), which correspond to pairwise edges; (c) no factorization (as in QTRAN, Son et al. (2019) corre-
sponds to one hyper-edge connecting all agents. Factorization allows parameter sharing between factors, shown next the CG, which can dramatically improve the algorithm's is sample complexity.
To address these issues, this paper proposes the deep coordination graph (DCG), deep RL al- gorithm that scales to modern benchmark tasks. DCG represents the value function as CG with pairwise payoffs (Figure (aygure [b) and individual utilities (Figure [p). This improves the representational capacity beyond state-of- offe-of-thheart value factorization approaches like VDN (Sunehag et al. (2018) and QMIX (Rashid et al., 2018). To achieve scalability, DCG employs parameter sharing between pay- offss and utilities. Parameter sharing has long been staple of factorized MARL. Methods like VDN and QMI condition an agent's 's utility on its history, that is, its past observations and actions, and share the parameters of all utility functions. Experiences of one agent are thus used to train all. This can dramatically improve the sample efficiency compared to unfactored methods (Foerster et al.) 2016 2018; Lowe et al.. 2017; Schröder de Witt al. 2019 Son al. 2019), which correspond to a CG with one hyper-edge connecting all agents (Figure It). DCG takes parameter sharing one step further by approximating all payoff functions with the same neural network. To allow unique out- puts for each payoff, the network is conditioned on a learned embedding of the participating agents' histories. This requires only one linear layer more than VDN and has thus less parameters as QMIX.
DCG is trained end-to-end with deep Q-learning (DQN, Mnih et al. 2015), but uses message passing to coordinate greedy action selection between all agents in the graph. For message passes over n agents with m actions each, the time complexity of maximization is only (kmm(n + m [E1). where the number of (pairwise) edges, compared to O(m") for DQN without factorization. | S 2
We compare DCG's performance with that of other MARL Q-learning algorithms in a challenging family of predator-pin -rey tasks that require coordinated actions. Here DCG is the only algorithm that solves the harder tasks. We also investigate the influence of graph topologies on the performance.
2 RELATED WORK
A general overview over cooperative deep MARL can be found in OroojlooyJadid Hajimezhad (2019). Independent Q-learnig (IQL 1993) decentralizes the agents' policy by modeling each agent as an independent Q-learne. However, the task from the perspective of a single agent becomes nonstationary as other agents change their policies. To address this, Foerster et al. (2017) show how to stabilize IQL. when using experience replay buffers. Another approach to decentralized agents is centralized training and decentralized execution (Focrster et al. 2016) with factorized value function. Value decomposition networks (VDN, Sunchag et al. 2018)) performs central Q-learning with value function that is the sum of independent utility functions for each agent (Figure Ta). The greedy policy can be executed by maximizing each utility independently. QMIX (Rashid et al. (018)) improves upon this approach by combining the agents' utilities with mixing network, which is monotonic in the utilities and depends on the global state. This allows different mixtures in different states and the central value can be maximized independently due to monotonicity. All of these approaches are derived in Appendix A.I and can use parameter sharing between the value/utility functions. However, they represent the joint value with independent values/utilities and are therefore susceptible to the relative overgeneralization pathology. We demonstrate this by comparing DCG with all the above algorithms.
2 The method can be generalized to CG with hyper-edges, that is, to payoff functions for more than 2 agents.
2

---

Under review as a conference paper at ICLR 2020
Another straightforward way decentralize in MARL is to define the joint policy product of in- dependent agent policies. This lends itself to the actor-critic framework, where the critic is discarded the global state and all agents' actions during train- ing. Examples are MADDPG (Lowe et al. 2017) for continuous actions and COMA (Foerster et al.) 2018) for discrete actions. |Wei et al. (2018) 8) specifically investigate the relative overgeneralization pathology in continuous multi-agent tasks and show improvement over MADDPG by introducing policy entropy regularization. MACKRL (Schröder de Witt al.] 2019) follows the approach in Foerster et al. (2018), but uses common knowledge to coordinate agents during centralized training. Son et al. (219) define QTRAN, which also has centralized critic but uses a greedy actor w.r.t. a VDN factorized function. The corresponding utility functions are distilled from the critic under constraints that ensure proper decentralization. [Böhmer et al. (2019) present another approach to decentralize centralized value function, which is locally maximized by coordinate ascent and de- centralized by training IQL agents from the same replay buffer. Centralized joint Q-value functions do not allow to share parameters to the same extent as value factorization, and we compare DCG to QTRAN to demonstrate the advantage in sample efficiency. That being said, DCG value factor- ization can in principle be applied any of the above centralized critics equally improve sample efficiency at the same cost of representational capacity. We leave this to future work.
during execution and can therefore condition
Other work deals with gigantic numbers of agents, which requires additional assumptions to reduce the sample complexity. For example, Yang et al. (2018) introduce mean-field multi-agent learn- ing (MF-MARL), which factorizes tabular value function for hundreds of agents into pairwise payoff functions between neighbors in a uniform grid of agents. These payoffs share parameters similar to DCG. Chen et al. (018) introduce a value factorization for similar setup based on a low-rank approximation of the joint value. This approach is restricted by uniformity assumptions between agents, but uses otherwise parameter sharing similar to DCG. The value function cannot be maximized globally and must be locally maximized with coordinate ascent. These techniques are designed for much larger sets of agents and do not perform well in the usual MARL settings con- sidered in this paper. While they use similar parameter sharing techniques DCG, we do therefore not compare against them.
Coordination graphs (CG) have been extensively studied in multi-agent robotics with given payoffis (e.g. Rogers et al., 2011 Yedidsion et al., 2018). Sparse cooperative Q-learning (SCQL., Kok & Vlassis 2006 uses CG in discrete state and action spaces by representing all utility and payoff functions as tables. However, the tabular approach restricts practical application of SCQL to tasks with few agents and small state and action spaces. Castellini et al. (2019) use neural networks to approximate payoff functions, but only in one-shot games, and still require a unique function for each edge in the CG. DCG expands greatly upon these works by introducing parameter sharing between all payoff's (as in VDN/QMIX), conditioning on local information (as in MF-MARL) and evaluating in more complex tasks that are vulnerable to relative overgenerallization.
BACKGROUND
7) OOliehoek & Amato, 2016). S denotes a finite or continuous set of environmental states and A' the discrete set of actions available to agent i. At discrete time t, the next state S E S is drawn from transition kernel 8111 ~ P(-|se; a.), conditioned on the current state s, E S and joint action a E AA: A' ... x A" of all agents. A transition yields collaborative reward re r(st, a.), and y E [o. 1) denotes the discount factor. Each agent é observes the state only partially by drawing observations of E O² from its observation kernel o; ~ (-(s)) The history of agent i's observations of E O' and actions of E A' is in the following denoted as T/- == (of- d6. of of.-..,, -f-1 of) E (O x A' x O', Without loss of generality, this paper restricts itself to episodic tasks, which yield episodes (Su, {o ag. To: ... ST, {of in of varying (but finite) length T.
In this paper we assume a Dec-POMDP for n agents (S, (A') P,r,(O' (o')
3.1 DEEP Q-LEARNING
The goal of collaborative multi-agent reinforcement learning (MARL) is to find an optimal policy T S x A + [0, 1]. that chooses joint actions a, E A such that the expected discounted sum of future reward is maximized. This can be achieved by estimating the optimal Q-value function?
We overload the notation fyy( to also indicate the inputs x and outputs y of multivariate functions f.
3

---

Under review as a conference paper at ICLR 2020
/ P(s'|s, a) maxq" (+Is') (1)
9- (a)s)
Ex-
Σ Err
so=s au=a
= r(s, + +
c=0
The optimal policy x= (-(xs) chooses greedily the action A that maximizes the corresponding optimal Q-value q" (a]s)) ) In fully observable discrete state and action spaces, q" can be learned in the limit from interactions with the environment (Watkins & Dayan 1992). For large or continuous state spaces, g" can only be approximated, e.g., with a deep neural network (DQN, [Mnih et al., 2013). parameterized by 6, by minimizing the mean- mean-squared Bellman loss with gradient descent:
LoON
IE
1 T
Σ t=d
(re + max 90(-| - go go(as|s:)) {st, Tt, $t+1)E ~ D]. (2)
The expectation is estimated with samples from an experience replay buffer D holding previ- ously observed episodes (Lin 1992). and 0 denotes the parameter of a separate target network, which is periodically replaced with copy of 0 to improve stability. Double Q-learning fur- ther stabilizes training by choosing the next action greedily w.r.t. the current network 9o. i.e. (prargmast qo (-1s++1) S1+1) instead of the target network max go(-|su+1) (van Hasselt al. 2016
In partially observable environments, the learned policy cannot condition on the state st- Instead, Hausknecht & Stone (2155) approximate Q-function that conditions the agent's history [-, i.e., 9o a ). by conditioning a recurrent neural network (e.g., a GRU, Chung et al. 2014) on the agents' observations o, (ot,.... of) and last actions a;- that is, q conditions on the recurrent network's 's hidden state h4 (hr Or, a;-1), where to is initialized with zeros.
Applying DQN multi-agent tasks quickly becomes infeasible, due the combinatorial explosion of state and action spaces. Moreover, DQN value functions cannot be maximized without evaluating all possible actions. To allow MARL Q-learning with efficient maximization, various algorithms based on value factorization have been developed. We derive IQL (Tan 1993). VDN (Sunchag al. 2018). QMIX (Rashid et al. 2018 and QTRAN (Son et al.. 2019
Appendix A.I
3.2
COORDINATION GRAPHS
An undirected coordination graph (CG, Guestrin et al. 2002a G (V.E) contains vertex 82 E V for each agent 1 < i S n and set of undirected edges {2, j] E E between vertices e and Vy. The graph is usually specified before training, but Guestrin et al. (2002b) suggest that the graph could also depend on the state, that is, each state can have its own unique CG. A CG induces a factorization" of the Q-function into utility functions f and payoff functions f (Fig. 1 and Ip):
( a)
1 M
Σ f'(aa(ss) + E C'EV
Σ (a' as)s)). FiJLEE
(3)
The special case & = Ø yields VDN, but each additional edge enables the representation of the value of the actions of pair of agents and can thus help to avoid relative overgeneralization. Prior work also considered higher order coordination where the payoff functions depend on arbitrary sets of actions (Guestrin et al., 2002al Kok & Vlassis, 2006 Castellini et al., 2019), corresponding to graphs with hyper-edges (H (Figure b. For the sake of simplicity we restrict ourselves here to pairwise
n! edges, which yield at most | 2 (n²2 n.) edges, in comparison to up at (n-4)t hyper-edges of degree d. The induced function q can maximized locally using max-plus, also known as belief propagation (Pearl 1988). At time each node sends messages 2 (a!) E IR over all adjacent edges {i,j) E E, which can be computed locally:
14 + max ( + (d',
Σ (
(4)
(MEE)E
This process repeats for a number of iterations, after which each agent can locally find the action a that maximizes the estimated Q-value:
af
arg max
( (a'(s)))
Σ H (aa)).
(5)
al
{R.)EEE
4 The normalizations ক and 말े are strictly necessary, hut allow potentially generalize to other CGs.
4

---

Under review as a conference paper at ICLR 2020
Convergence of messages is guaranteed for acyclic CGs (Pear 1988
Wainwright al. 2004). but
messages can diverge in cyclic graphs, for example fully connected CGs. Subtracting a normal- ization constant Gjj == En 14 /AA from each message n² before it is sent often leads to
convergence in practice (Murphy al. 1999. Crick & Pfeffer 2002 Algorithm B in the appendix for details.
Yedidia et al. 2003). See
4 METHOD
We now introduce the deep coordination graph (DCG), which learns the utility and payoff functions of a coordination graph (V, with deep neural networks. A direct implementation as in Castellini et al. (2019) would learn a separate network for each function I and f However, properly ap- proximating these Q-values requires observing the joint actions of each agent pair in the edge set E. which for dense graphs can be a significant subset of the joint action space of all agents A. We architecture that shares parameters across functions and restricts
address this issue by focusing them to locally available information, i.e., to the histories of the participating agents.
Sunehag et al. (2018) introduces parameter sharing between the agents' utility functions (u() x ( [T.) to dramatically improve the sample efficiency of VDN. Agents can have different action spaces A'' but the choice of unavailable actions during maximization can be prevented by setting the utilities of unavailable actions -o0. Specialized roles for individual agents can be achieved by conditioning fg on the agent's 's role, or more generally on the agent's ID) (Foerster et al.) 2018 Rashid et al. (018). The DCG uses the same utility functions and adds payoff functions specified by pairwise edges in a given CG (Guestrin et al., 2002a). We take inspiration from highly scalable methods (Yang et al. 2018 Chen et al. 2018) and improve over SCQL (Kok & Vlassis 2006) and the approach of Castellini et al. (2019) by incorporating the following design principles:
restricting the payofis (a IT +/) to local information of agents and j only; ii sharing parameters between all payoff and utility functions through common RNN;
iii. low-rank approximation of payoff matrices (t, -IT/. F²) for large action spaces;
iv. allowing transfer/generaaiizaion to different CG (as suggested in Guesstin et al. (20026);
v. allowing the use of privileged information like the global state during training.
Restricting the payoff's input (i) and sharing parameters (ii) improves sample efficiency signif- icantly. As in Sunehag et al. (2018), all utilities are computed with the same neural network (T((" = fø [u') hz;) but unlike Castellini al. (211)), all payoff's are computed with the same neural network f (a', aa [T; +²) (2)== R fg(a', a² [h;, h,), too. Both share parameters though a common
RNN h; = (-1h of, a)_1), which is initialized with h/ = hyp (-00, ob 0).
Modeling the payoff function f similar to DQN (Mnih et al. 2015) yields |A x AA| separate outputs for edge { For example, each agent in StarCraft 2 map with 8 enemies has 13 actions (SMAC, (Samvelyn et al. 2019), which yields 169 outputs of f As only executed actions-part are updated during Q-learning, the parameters of many outputs remain unchanged for long stretches of time, while the underlying RNN hy keeps evolving. This can slow down training and affect message passing. To reduce the number of parameters and improve the frequency in which they are updated, propose low-rank approximation of the payoff (iv) with rank K, similar to Chen et al. (2018):
Iā(a", a² (hi h:)
Σ Eg klh, b!) fz (o, k kig h:).
(6)
The approximation can be computed one forward-pass with K(IAA) + [A'l) outputs and parame- ters ø == (ô, Ø). Note that a rank K = min (l [4'l] approximation does not restrict the output's expressiveness, while lower ranks share parameters and updates to speed up learning.
Generalization (or zero-shot transfer) of the Iearned functions onto new CGs in (iv) poses some practical design challenges. To be applicable to different graphs/topologies, DCG must be invariant to reshuffling of agent indices. This requires the payoff matrix ft), of dimensionality |A'| x [A%), to be the same as (fji) with swapped inputs. We enforce invariance by computing the function fs for both combinations and use the average between the two. Note that this retains the ability to learn asymmetric payoff matrices fü + (f") However, this paper does not evaluate (iv) and we leave the transfer of a learned DCG onto different graphs future work. The DCG Q-value function is:
5

---

Under review as a conference paper at ICLR 2020
DCG 10c
(T, a)
+
26
Σ (i,)EEE
Sala (ellhi, (1) Sā(ae, at aainn,, hi)
Moreover, some tasks allow access to privileged information like the global state s, E S during training (but not execution). We therefore propose in (v) to use this information in a privileged bias function Upp : S - IR with parameters yp, that is, DDC-- Seovi (St. Tt, a) == goov (T,, a) + (s))))
DCo
We train DCG end-to-end with the DQN loss (2) and Double Q-learning (van Hasselt et al. 2016).
Given the tensors fv E IRIV xA and f E R 1elx A = U3 AA where all unavailable actions
set to -c,, the Q-value detailed procedure of computing the tensors (Algorithm [T). the Q-value (Algorithm 2 and greedy action selection (Algorithm 3) given in the appendix. Note that no gradients flow through the message passing loop, as DQN maximizes only the bootstrapped future value.
be maximized by message passing defined in (4) and ( The
The key benefit of DCG lies in its ability to prevent relative overgeneralization during the explo- ration of agents; take the example of two hunters who have cornered their prey. The prey is danger- ous and attempting catch it alone can lead to serious injuries. From the perspective of each hunter, the expected reward for an attack depends on the actions of the other agent, who will initially behave randomly. If the punishment for attacking alone outweighs the reward for catching the prey, agents that cannot represent the value for joint actions (QMIX. VDN, IQL) cannot learn the optimal policy. However, estimating value function over the joint action space (as in QTRAN) can equally pro- hibitive, as it requires many more samples for the same prediction quality. DCG provides flexible function class between these extremes that can be tailored to the task at hand.
5 VALIDATION
In this section we compare the performance of DCG with various topologies (see Table TT to the sate--of-the-ar algorithms QTRAN (Son al. 2019). QMIX Rashid et al., 2018 VDN (Sunehag et al. 2018) and IQL. (Tan 1993). We also evaluate CG bascline similar to Castellini iet al. (2019), which conditions
DCG
1 si<ni<sssn
CYCLE
= (i modn) m1d
LINE
=
STAR
Σ: = [1,00|2sisn)
VDN
8 = Ø
shared RNN which summarizes all agents' histories. All algo- rithms implemented in the multi-agent framework PYMARL (Samvelyan et al. 2019
Table 1: Tested graph topologies for DCG.
We evaluate these methods in two complex grid-world tasks: the first formulates the relative over- generalization problem family of predator-prey tasks and the second investigates how artificial decentralization can hurt tasks that demand non-local coordination between agents. In the latter case, decentralized value functions (QMIX, VDN, IQL.) cannot learn coordinated action selection between agents that cannot see each other directly and thus converge to a sub-optimal policy. We also evaluate DCG and DCG-V StarCraft micromanagement tasks from the StarCraft Multi- Agent Challenge (SMAC, Samvelyan et al. 2019).
a) punishment p=0
b) punishment p=
c) punishment 1125
punishment 1=5
Episocie Return
40
40
40
40
20
20
20
DCG [8]
VDN
0
0.25
0.50
0.75
0.25 0.50 0.75
0.25
0.50
0.75
0.25
0.50
0.75
Environmental Steps le6
Environmental Steps 1e6
Environmental Steps 1e6
Environmental Steps 1e6
Influence of punishment p for attempts to catch prey alone on greedy test episode return (mean and shaded standard error, [number of seeds]) in a coordination task where 8 agents hunt 8 prey (dotted line denotes best possible return). Note that fully connected DCG (DCG, solid) are able to represent the value of joint actions and coordinate maximization, which leads to a better performance for larger P. where DCG without edges (VDN, dashed) has to fail eventually (p < -1).
Figure 2:

---

Under review as a conference paper at ICLR 2020
a) comparison between algorithms
comparison between topologies
40
40
Test Episode Retur
20
Test Epicode Return
30
10
20
0-
DCG [B]
-10
QTRAN [8]
DCG [8)
10
QMIX [8]
CYCLE [8]
-20
[8]
-30-
VDN [8]
0
STAR [8]
[8]
VDN
0.6
1.0
Environmental Steps
1e6
Environmental Steps
1e6
Figure 3: Greedy test episode return for the coordination task of Figure with punishment, p -2: (a) comparison to baseline algorithms; (b) comparison between DCG topologies. Note that QMTX, IQL, VDN and CG (dashed) do not solve the task (return 0) due relative overgeneralizattion and that QTRAN learns very slowly due to the large action space. The reliability of DCG depends on the CG- topology: all seeds with fully connected DCG solved the task, but the high standard error for CYCLE, LINE and STAR topologies is caused by some seeds succeeding while others fail completely.
5.1 RELATIVE OVERGENERALIZATTIO
To model the challenge of relative overgeneralization, we consider a partially observable grid-world predator-prey prey task: 8 agents have to hunt 8 prey in 10 x 10 grid. Each agent either move in one of the 4 compass directions, remain still, or try to catch any adjacent prey. Impossible actions, that is, moves into occupied target position catching when there is no adjacent prey, treated as unavailable. The prey moves by randomly selecting one available movement or remains motionless if all surrounding positions are occupied. If two adjacent agents execute the catch action, a prey is caught and both the prey and the catching agents are removed from the grid. An agent's 's observation a x sub-grit -o--grid centered around it, with one channel showing agents and another indicating prey. Removed agents and prey are no longer visible and removed agents receive special observation of all zeros. An episode ends if all agents have been removed or after 200 time steps. Capturing a prey is rewarded r 10, but unsuccessful attempts by single agents are punished by negative reward p. The task is similar to one proposed by Son et al. (2019), but significantly more complex, both in terms of the optimal policy and in the number of agents.
To demonstrate the effect of relative overgeneralization, Figure shows the average return of greedy test episodes for varying punishment p mean and standard error over 8 independent runs. Without punishment (p = 0 in Figure 22),, fully connected DCG (DCG, solid) performs as well as DCG without edges (VDN, dashed). However, for stronger punishment VDN becomes
and more unreliable, which is visible in the large standard errors in Figures 2 and until it fails completely for p < -1.5 in Figure 2 This is due to relative overgeneralization, as VDN cannot represent the values of joint actions during exploration. DCG, on the other hand, learns only slightly slower with punishment and converges otherwise reliably the optimal solution (dotted line).
Figure 3p shows how well DCG performs in comparison with the baseline algorithms in Appendix A.1 for a strong punishment of p 22. Note that CMIX, IQL and VDN completely fail learn the task (return 0) due to their restrictive value factorization. While CG could in principle learn the same policy as DCG, the lack of parameter sharing appears to slow down learning dramatically here, which yields no reward in the first million transitions. QTRAN estimates the values with a centralized function, which conditions on all agents' actions, and can therefore learn the task. However, QTRAN requires much more samples than DCG before useful policy can be learned, due to the size of the joint action space. This is in line with the findings of Son et al. (2019). which required much more samples to learn task with four agents than with two and also show the characteristic dip in performance with more agents. In comparison with both OTRAN and CG, fully connected DCG (DCG) learn near-optimal policies remarkably fast and reliable.
7

---

Under review as a conference paper at ICLR 2020
a) comparison between algorithms
b) comparison between topologies
8
8
7-
7
Test Ep-ddde Return
6
Test Episode Return
5
4-
DCG [8]
3-
QTRAN (8)
3
DCG (8)
2
QMIX [8]
2
CYCLE [8]
IQL [8]
LINE (8)
1-
VDN [8]
1-
STAR [8]
0
CG [8]
0
VDN [8]
0.0
0.5
1.0
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.5
3.0
Environmental Steps
1e6
Environmental Steps
1e6
Figure 4: Greedy test episode return (mean and shaded standard error, [number of seeds]) in
non-decentralliabble task where agents hunt prey: (a) comparison to baseline algorithms: (b) comparison between DCG topologies. The prey turns randomly into punishing ghosts, which indistinguishable from normal prey. The prey status is only visible at an indicator that is placed ran- domly each episode in one the grid's corners. QTRAN, QMTX, IQL and VDN learn decentralized policies. which are at best suboptimal in this task (around lower dotted line). Fully connected DCG and CG can learn near-optimal policy (upper dotted line denotes best possible return), but a lack of parameter sharing slows down CG and yields sub-optimal performance in comparison to DCG.
We also investigated the performance of various DCG topologies defined in Table D Figure shows that in particular the reliability of the achieved test episode return depends strongly on the graph topology. While all seeds of fully connected DCG succeed (DCG), DCG with CYCLE, LINE and STAR topologies have varying means while exhibiting large standard errors. The high devia- tions are caused by some runs finding near-optimal policies, while others fail completely (return 0). One possible explanation is that for the failed seeds the rewarded experiences, observed in the initial exploration, are only amongst agents that do not share a payoff function. Due to the relative over- generalization pathology, the learned greedy policy longer explores 'catch' actions and existing payoff functions cannot experience the reward for coordinated actions anymore. is therefore not surprising that fully connected graphs perform best, they represent the largest function class and require the fewest assumptions. The topology had also little influence on the runtime of DCG, due efficient batching on the GPU. The tested fully connected DCG only considers pairwise edges. Hyper-edges between more than two agents (Figure [T:) would yield even richer value representa- tions, but would also require more samples to sufficiently approximate the payoff functions. This effect can be seen in the much slower learning QTRAN results in Figure 34.
5.2 ARTIFICIAL DECENTRALIZATION
The choice of decentralized value functions is in most cased motivated by the huge joint action spaces and not because the task actually requires decentralized execution: it is artificial decen- tralization. While this often works surprisingly well, we want to investigate how existing algorithms deal with tasks that cannot be fully decentralized. One obvious case in which decentralization must fail is when the optimal policy cannot be represented by utility functions alone. For example, decen- tralized policies behave suboptimally in tasks where the optimal policy must condition on multiple agents' observations in order to achieve the best return. Payoff functions in DCG, on the other hand, condition on pairs of agents and can thus represent richer class of policies. Note that dependencies on more agents can be modeled as hyper-edges in the DCG (Figure [b), but this hurts the sample efficiency as discussed above.
We evaluate the advantage of a richer policy class with variation of the above predator-prey task. Inspired by the video game PACMAN, at each turn a fair coin flip decides randomly whether all prey are turned into dangerous ghosts. To disentangle the effects of relative overgeneralization, prey can be caught by only one agent (without punishment), yielding a reward of = 1. However, if the agent captures ghost, the team punished with r -1. Ghosts indistinguishable from normal prey, except for a special indicator that placed in random corner at the beginning of each episode. The indicator signals additional channel of the agents' observations whether the prey are currently
8

---

Under review as a conference paper at ICLR 2020
a) relative overgeneralization task
b) non-decentralizable task
Test Episode Return
30
40
Episode Return
25
39
DCG (full) [8]
15-
38
3-
DCG (rank 1/ (8)
DCG (rank 2] [8]
DCG (rank 3) [8]
5
0.4
0.6
0.8
1e6
1:0
1-
DCG (rank [8]
VDN [8]
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Environmental Steps
1e6
Environmental Steps
1e6
Figure 5: Low-rank payoff approximation for the tasks in (a) Figure and (b) Figure The inlay in (a) magnifies the area of the gray box. Note that in (a) all approximation ranks learn much faster than full DCG, and rank 2-4 also have better performance.
ghosts. Due the short visibility range of the agents, the indicator is only visible in one of the positions closest to its corner.
Figure 4 shows the performance of QTRAN, QMIX, IQL and VDN, all of which have decentralized policies, in comparison to fully connected DCG and CG. The baseline algorithms have to learn policy that first identifies the location of the indicator and then herds prey into that corner, where the agent is finally able to catch it without risk. By contrast, DCG and CG can learn a policy where one agent finds the indicator, allowing all agents that share an edge to condition their payoffss on that agent's s current observation. As result, this policy catch prey much more reliably, seen in the high performance of DCG compared to all baseline algorithms. Interestingly, as CG conditions all agents' histories, the baseline shows advantage in the beginning but then learns much slower and reaches a significantly lower performance. We also investigate the influence of the DCG topologies of Table [ shown in Figure 4p. Note that while other topologies do not reach the same performance as fully connected DCG, they still reach a policy that significantly outperforms all baseline algorithms, around the same performance fully connected CG.
5.3 LOW-RANK APPROXIMATION
While the above experiments already show a significant advantage of DCG with independent payoff' outputs for each action pair, we observed some serious performance issues on StarCraft maps with this urchitecture. The most likely cause is the difference in the number of actions per agent: predator-prey agents choose between [A'l actions, whereas SMAC agents on comparable maps with 8 enemies have |A'| appear reasonable to learn, 169 outputs in StarCraft would require significantly more samples to estimate the payoff of each joint-action properly.
13 actions. While payoff matrices with 36 outputs in predator-pres
Figure shows the influence of low-rank payoff approximation (Equation 6 with K f1..... 4)) on both predator-prey tasks from previous subsections. One can see in Figure 5p that any low-rank approximation (DCG (rank K) significantly improves the sample efficiency over the default architecture with independent payoff for each action pair (DCG (Eull)) ). Only rank K = 1 leads to slightly lower performance, which can be seen in the inlay plot. We conclude that rank 2 is needed to represent the true values, but rank K 1 already suffices overcome the relative overgeneralization pathology. The improvement in Figure less impressive, but shows that even rank K approximation (DCG (rank 1) yields slight performance gains over DCG (full).
5.4 STARCRAFT 2
The default architecture of DCG with independent payoff for each action pair performed poorly in StarCraft 2. We therefore tested K low-rank payoff approximation DCG with (DCG-V) and without (DCG) privileged information bias function Ug. as described Section 4 on six StarCraft 2 maps (from SMAC, (Samvelyan et al., 2019). The leaming curves for all StarCraft 2 maps

---

Under review as a conference paper at ICLR 2020
a) MMM2
b) so monn baneling
8m, vs_ 9m
1.0
1.0
1.0
Text Eghood Vin Rate
0.8
Test Cobodle Win Rate
0.0
Test Fahcdde Vin Bate
0.8
0.6
0.6
1) DCG (rank 2J [4]
QMIX [4]
0.4
0.4
(4)
0.4
0.2
0.2
0.2
0.0
0.0
0.0
Environmental Stops
Environmental Steps
Environmenall Steps
5z
3s52
f] micro focus
micro_focus
1.0
1.0
1.0
Text Ep1000 Win Rate
0.0
Test Colsade Win Rtte
0.0
Tea Fpioadd Win Rate
0.0
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
Environmental Steps
Environmental Steps
Environmental Steps
Figure 6:
Cumulative reward for test episodes on SMAC maps (mean and shaded standard error, [number of seeds]) for QMIX, VDN and fully connected DCG with rank K = payoff approximation (DCG (rank 1)) and additional -eateddeendenn bias function (DCG-V (rank 1)).
given in Figure 6 We expected DCG only yield an advantage on maps which struggle with the relative overgeneralization pathology or some related issue. In this light it is somewhat surprising that both DCG and DCG-V outperform VDN on almost all maps. DCG-V performs at least as good as DCG and clearly outperforms it some maps, which demonstrates that privileged information is clearly useful. As expected, a direct comparison with the state-of-the-art method QMIX depends strongly the StarCraft 2 map. On the one hand, DCG-V clearly outperforms QMIX on MMM2 (Figure 6l),, which is classified as super hard by SMAC. We also learn much faster on the easy map so wwaaamnn_bbaa wwaeelinnnngg (Figure(op). On the other hand, QMIX performs better on the hard map 3 3s_vs_5 (Figure 6f),, which might be due to the low number of agents. For this few agents, the added representational capacity of DCG may not improve the task much the non-linear state-dependent mixing of QMIX. However, it is hard to pin-point why state dependent mixing is an advantage here.
We conclude from these results that that some maps (like MMM2) clearly benefit from the improved coordination and value representation of DCG, while in most others DCG-V is on par with QMIX.
CONCLUSIONS & FUTURE WORK
This paper introduced the deep coordination graph (DCG), architecture for value factorization that is specified by coordination graph (CG) and can be maximized by message passing. We evaluated deep Q-learning with DCG and show that the architecture enables learning of tasks where relative overgenerulization causes all decentralized baselines to fail, whereas centralized critics are much less sample efficient than DCG. We also demonstrated that artificial decentralization can lead to suboptimal behavior in all compared methods except DCG. Our method significantly improves over existing CG methods, which we demonstrate experimentally as well. Fully connected DCG performed best in all experiments and should be preferred in the absence of prior knowledge about the task. Additionally, we introduced low-rank payoff approximation for large action spaces and a privileged bias function (DCG-V). Evaluated on StarCraft 2 micromanagement tasks, DCG-V per- forms competitive with the state-of-the-ee art QMIX. Although not evaluated in this paper, DCG should be able to transfer/generaaizee to different graphs/topoloiies and can also be defined for higher- dependencies. This would in principle allow the training of DCG on dynamically generated graphs, including hyper-edges with varying degrees. We plan to investigate this in future work.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Böhmer, W., Rashid, T., and Whiteson, S. Exploration with unreliable intrinsic reward in multi- agent reinforcement learning. CoRR, abs/1906.02135 02138, 2019. URL http::/ .rexiiivorr//.ooo abs/1900 /196. 02138 Presented at the ICML Exploration in Reinforcement Learning workshop.
Castellini, J., Oliehoek, F. A., Savani, R., and Whiteson, S. The representational capacity of action- value networks for multi-agent reinforcement learning. Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 19, pp. 1862-1864, 2019. URL httpthttp://w/tt faamas org Proceediiiii www.gggg/aaaeeeee aama pttp/pff////t //tpf//pp.......mm pdf
Chen, Y., Zhou, M., Wen, Y., Yang. Y. Su, Y., Zhang, W., Zhang, D., Wang. J., and Liu, H. Factorized q-learning for large-scale multi-agent systems. CoRR, abs/1 1as/1809.03738 2018. URL.
htttp://axiv..o wwwp:/wwwwwww....//oo/aoba 1100./.3300990088888
Chung, J., Gulcehre, C., Cho, K., and Bengio, Empirical evaluation of gated recurrent neural
networks on sequence modeling. In NIPS Workshop on Deep Learning, 2014. URL |
//axxiv.org/ab///44
3555
Crick, C. and Pfeffer, A. Loopy belief propagation as a basis for communication in sensor networks. In Proceedings of the Nineteenth conference Uncertainty in Artificial Intelligence, pp. 159- 166. Morgan Kaufmann Publishers Inc., 2002.
Foerster, J., Assael, Y., de Freitas, N., and Whiteson, S. Learning to communicate with deep multi-agent reinforcement learning. In NIPS 2016: Proceedings of the Thirtieth Annual Con- ference on Neural Information Processing Systems, 2016. URL http: htatt::/www.... wwwp///wcommmm cs ax.ac. ww/people////eeeeee shimon. wwwtesson/puii http://co/oubbbeeeeeeeeeeeeeeeee htt.://eeeseeees...ppppem
Foerster, J., Nardelli, N., Farquhar, G., Torr, P., Kohli, P., and Whiteson, S. Stabilising experience replay for deep multi-agent reinforcement learning. In ICML 20/7: Proceedings of the Thirty-
Fourth International Conference Machine Learning, 2017. URL http: http::///www.... /www ox.
ac. www.ukk/ppppeeeeee shtppleesssioo....m shimon. mmitesson/pubss
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. Counterfactual multi-agent policy gradients. In The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), pp. 2974-2982, AAAI Press, 2018. URL htLhhtts:: www.a. org/ abs/ wwwpwi.www....///////.
08926
Guestrin, C., Lagoudakis, M., and Parr, R. Coordinated reinforcement learning. In ICML, volume 2, pp. 227-234, 2002a.
Guestrin, C., Venkataraman, S., and Koller, D. Context-specific multiagent coordination and plan- ning with factored mdps. In Eighteenth National Conference on Artificial Intelligence, pp. 253- 259. 2002b.
Hausknecht, M. J. and Stone, P. Deep recurrent q-learning for partially observable mdps. In 2015 AAAI Fall Symposia. pp. 29-37, 2015. ht /twp:://www.. aaal wwwpaaa......///aaaaaaaaooooocee www.c/cc/nnnne///ieeeeeee.eeieee php/ FS5/EsS15/paper//reee//
http::/
Kok, R. and Vlassis, N. Collaborative multiagent reinforcement learning by payoff propagation. Journal of Machine Learning Research, (789p):1799-182) 2006.
Lin, L.J. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8(3):293-321, 1992.
Lowe, R., WU, Y., Tamar, A., Harb, J.. Pieter Abbeel, O., and Mordatch, I. Multi-agent actor- critic for mixed cooperative-competiiee environments. In Advances in Neural Information Processing Systems 30, pp. 6379-6390. 2017. URL http::t/pppppssaeteeese nips cc/paper////cccccccccccc for ott.aa/cc............ooooooooore wtw.:eertaateeeooooetttteeeeeeee
pdf
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg. S., and Hassabis, D. Human-level control through deep reinforcement learning. Nature, 518(7540)5529955 February 2015.

---

Under review as a conference paper at ICLR 2020
Murphy, K. P., Weiss, Y., and Jordan, M. I. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the Fifteenth conference on Uncertainty artificial intel- ligence, pp. 467-475. Morgan Kaufmann Publishers Inc., 1999.
Oliehoek, F. A. and Amato, C. A concise introduction decentralized POMDPs. Springer Publish- ing Company, Incorporated, 1st edition, 2016. ISBN 3319289276, 97833192892774
OroojlooyJadid, A. and Hajinezhad, D. review of cooperative multi-agent deep reinforcement abs 1908 03963
learning. CoRR, abs/1908.00396. 2019. URL httttt//a/axxiv.oo
Panait, L., Luke, S., and Wiegand, R. P. Biasing coevolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation, 10(6):629-666 645, 2006.
Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. ISBN 0-934613-73-7.
Rashid, T., Samvelyan, M., Witt, C. S., Farquhar, G., Foerster, J. N., and Whiteson, S. QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning (ICML), pp. 4292-4301, 2018.
Rogers, A. C., Farinelli, A., Stranders, R., and Jennings, R. Bounded approximate de- centralised coordination via the max-sum algorithm. Artificial Intelligence, 175(2):730- 759, 2011. ISSN 0004-3702. URL
Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G. Hung, C.- M., Torr, H. S., Foerster, J., and Whiteson, S. The StarCraft Multi-Agent Challenge. CoRR, abs/1902.04043, 2019.
Schröder de Witt, C. A., Förster, J. N., Farquhar, G., Torr, H., Böhmer, W., and Whiteson, S. Multi-agent common knowledge reinforcement learning. In To appear in NeurIPS 2019, 2019. URL / wttp:vv.rrgabbb//lll1
11702
Son. K., Kim, D., Kang, W. J., Hostallero, D. E., and Yi, Y. QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 5887-5896, 2019. URL http: http://proceeedngg mlr. son 9a html
Sunchag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T. Value-decomposition networks for operative multi-agent learning based on team reward. In Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems (AAMAS), pp. 2085-2087 2018.
Tan, M. Multi-agent reinforcement learning: Independent cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
van Hasselt, H., Guez, A., and Silver, D. Deep reinforcement learning with double q-learning. In Proceedings of the 13th AAAI Conference on Artificial Intelligence, pp. 2094 2100, 2016. URL https://axxi org/ / pdf 116.//166..66...... pdf
06461.
Wainwright, M., Jaakkola, T., and Willsky, A. Tree consistency and bounds on the performance of the max- max-prodes product algorithm and its generalizations. Statistics and Computing, 14(2):143-18) 166, 2004.
Watkins, C. and Dayan, P. Q-learning Machine Learning, 8:279-292. 1992.
Wei, E., Wicke, D., Freelan, D., and Luke, S. Multiagent q In AAAI Spring Symposium Series, 2018, URL https:: /tttps://www... aaai, www.oo//////ooo.eeeeeeeeo http:///ww.aaaaa.oo////////aeee. php/ SSS/ http://wpppppess//////pa/a/eee
view/17508 15482
Yang, Y., Luo, R., Li, M., Zhou, M., Zhang, W. and Wang. J. Mean field multi-agent reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 5571-5580, 2018. URL httt:tttppoooeee///////// ngs h 8d. html
12

---

Under review as a conference paper at ICLR 2020
Yedidia, J. S., Freeman, W. T., and Weiss, Y. Understanding belief propagation and its generaliza- tions. Exploring artificial intelligence the new millennium, 8:236-239, 239, 2003.
Yedidsion, H., Zivan, R., and Farinelli, A. Applying max-sum teams of mobile sensing agents. En- gineering Applications of Artificial Intelligence, 71: 71:87-99, 2018, ISSN 0952-1976. URLhttps /tt.a//acaiiicc.....aaaaaaaaaaaa
A APPENDIX
A.1 BASELINE ALGORITIIMS
IQL Independent Q-learning TTnn 1993) straightforward approach of value decentralization that allows efficient maximization by modeling each agent as an independent DQN (a'(T))) The value functions can be trained without any knowledge of other agents, which are assumed to be part of the environment. This violates the stationarity assumption of P and can become therefore instable (see e.g. Foerster et al., (017)). IQL. is nonetheless widely used in practice, as parameter sharing between agents can make it very sample efficient.
Note that parameter sharing requires access to privileged information during training, called cen- tralized training and decentralized execution (Foerster et al. (2016). This is particularly useful for actor-critic methods like MADDPG (Lowe et al. (2177). Multi-agent soft Q-learning (Wei et al.) 2018). COMA (Foerster et al.] 2018) and MACKRL (Schröder de Witt et al. 2019). where the centralized critic can condition on the underlying state st and the joint action a, E A.
VDN Another way to exploit centralized training is value function factorization. For example, value decomposition networks (VDN, SSunehag et al. (018)) perform centralized deep Q-learning on a joint Q-value function that factors as the sum of independent utility functions f", for each agent i:
VDN (Te, a)
q
This value function NDN can be maximized by maximizing each agent's utility få independently.
QMIX
(Rashid et al. 2018) improves upon this concept by factoring the value function as
QMIX 4o
(st, Tr,a) = 9 (st, fo (1))))))..... f0 (a (a" (T.")
Here & is monotonic mixing hypernetwork with non-negative weights that retains monotonicity in the inputs fg. Maximizing each utility f therefore also maximizes the joint value O as in VDN. The mixing parameters are generated by neural network, parameterized by o. that condition on the state s,, allowing different mixing of utilities in different states. QMIX improves performance over VDN, in particular in StarCraft micromanagement tasks (SMAC, Samvelyan et al., 2019).
QTRAN Recently Son et al. (019) introduced QTRAN, which learns the centralized critic of a greedy policy w.r.t. VDN factorized function, which in turn is distilled from the critic by regression under constraints. The algorithm defines three value functions MDN, and v, where q( (T,, u) is the centralized Q-vuuue function, as in Section 3.1 and
((T))
max ((TE,)) max q VDN (T,(
(10)
They prove that the greedy policies w.r.t. q and NDN are identical under the constraints:
q (T., u) q(
a) v(T.)
O, Va A, VT. E {(O' A'Y' O'
(11)
with strict equality if and only a arg max MDN VDN (T. QTRAN minimizes the parameters
of the centralized asymmetric value q', (a TT. a ) a := (a' (a'...., a" a ++1 ...., .²), for each agent (which is similar to Foerster et al. 2018) with the combined loss Lyp:
LTp =
E
74 1
Te+1, a.t1) - La a.
(12)
13

---

Under review as a conference paper at ICLR 2020
where a arg max 98 (T,, -), Vt, denotes what a greedy decentralized agent would have chosen. The decentralized value dø and the greedy difference Vg. with parameters and e respectively, are distilled by regression of the each o in the constraints. First the equality constraint:
Q9 (T at) Led ar") + u
COFT
IE
(13)
where the 'detach' operator 1. stops the gradient flow through g.. The inequality constraints are more complicated. In principle one would have to compute a loss for every action which has negative error in (3). Son al. (2019) suggest use only the action which minimizes grtn.
(M(d))T) (a(t))) - Lug(a Te, (,) up u ()] (14) AaEAA
LNOPT= =
EE
nT Σ
Σ
min
We use this loss, which is called QTRAN-alt, as it is reported to perform significantly better. The losses are combined to LQTRAN == Liu + Aort Lorr + ANOrt Exort with Xorr, ANOPT O.
CG To compare the effect of parameter sharing and restriction to local information in DCG, we evaluate variation of Castellini al. (2019) that solve sequential tasks. In this baseline all agents share a RNN encoder of their belief over the current global state he := h& (- h2-1, o₁, a;-1) with hg by (-10, oo, 0), introduced in Section 3.1 However, the parameters of the utility or payoff functions are not shared, that is, 0 == {0:1-1 and Φ = {
E}. Each set of parameters 0g and dig represents one linear layer from he to A and A x A outputs, respectively.
A.2 HYPER-PARE PARAMETERS
All algorithms are implemented in the PYMARL framework (Samvelyan et al. 2019). We aimed to keep the hyper-parameters close to those given in the framework and consistent for all algorithms.
All tasks used discount factor 7 = 0.99 and c-greedy exploration, which was linearly decayed from c= 1 to 0.05 within the first 50, 000 time steps. Every 2000 time steps we evaluated 20 greedy test trajectories with c = 0. Results are plotted by first applying histogram-smoothne (100 bins) to each seed, and then computing the mean and standard error between seeds.
All methods are based on agents' histories, which were individually summarized with h& by con- ditioning linear layer of 64 neurons on the current observation and previous action, followed by ReLU activation and GRU (Chung et al. 2014) of the same dimensionality. Both layers' parameters are shared amongst agents, which can identified by a one-hot encoded ID in the put. For the CG baseline, the linear layer and the GRU had 64n = 512 neurons. This allows fair comparison with DCG and also had the best final performance amongst tested dimensionalities (64, 256, 512, 1024) in the task of Figure 4 Independent value functions g (for IQL), utility func- tions f (for VDN /OA///II//////////////////II QTRAN//AAAAA DDG) and payoff functions f (for DCG) are linear layers from the GRU output to the corresponding number of actions. The hyper-network Ps of QMIX produces mixing network with two layers connected with an ELU activation function, where the weights of each mixing-layer are generated by a linear hyper-layer with 32 neurons conditioned on the global state, that is, the full grrd-world. For QTRAN, the critic d' computes the Q-value for agent by taking all agents' GRU outputs, all other agents' one-hor hot encoded actions, and the one-hot encoded agent ID as input. The critic contains four successive linear layers with 64 neurons each and ReLU activations between them. The greedy difference va also conditions uses three successive linear layers with 64 neurons each and ReLU activations between them. We took the loss parameters AOPr exploration.
all agents' GRU outputs and
ANOrt = from (Son et al. 2019) without any
All algorithms were trained with one RMSprop gradient step after each observed episode based on a batch of 32 episodes, which always contains the newest, from a replay buffer holding the last 500 episodes. The optimizer uses learning rate 0.0005, 0.99 and 0.00001. Gradients with norm 2 10 were clipped. The target network parameters were replaced by copy of the curent parameters every 200 episodes.
14

---

Under review as a conference paper at ICLR 2020
Name
Agents
Enemies
Difficulty
so.many so.many-banelle www.baneilggg ling
Zealots
32 Banelings
easy
8m_vs_9m
Marines
9 Marines
hard
38_v8_5z
Stalker
5 Zealots
hard
3s5z
Stalker and 5 Zealots
3 Stalker and 5 Zealots
hard
1 Medivac
Medivac
MMM2
2 Marauders
Marauders
super hard
7 Marines
Marines
micro focus
Hydralisks
8 Stalker
super hard
Table 2: All tested StarCraft maps for SMAC (Samvelyan et al. 2019
A.3 STARCRAFT DETAILS
We kept all hyper-parameters the same and evaluated the six maps in Table 2 SMAC (Samvelyan et al. 2019), thors. The results for DCG V. DCG, QMIX and VDN are given in Figure where both DCG variants use a rank-1 1 payoff approximation. Note that our results differ from those in Samaellyn et al. (019), due slightly different parameters and update after every episode. The latter differs from the original publication because we use the the epi sode runner instead of the pa ra lel runner of PYMARI.. These choices ended up improving the performance of QMIX significantly.
All maps are from which was provided to us by the SMAC au-
15

---

> initialize utility tensor D initialize payoff tensor i compute batch with all agents Under review as a conference paper at ICLR 2020
Algorithm Annotates CG by computing the utility and payoff tensors (rank K approximation). (E K IN)
function ANNOTATE(( h
D A U; A')
f := E
R
f :- E REEXXAXA
for i {1, [L...., n do
h; = he (h oi a)-1)
> new hidden state compute utility set unavailable actions D... to -00 b. compute batch with all edges > no low-rank approximation D symmetric payoffs low-rank approximation
JN 6 (ht)
R
for E ( A} A' do
f% t -00
for = (i,j E do
K = 0 then
f + 1 25/( [hj n2)) + 1 25 (1 (h)) ni)
E IAA
clse
[, F) == " 1hj k2))
R22XXX
[F' F' == fo( 1h hi)
2
f + 1/2 FF F
symmetric payoffs b return hidden states hi, utility tensor f" and payoff tensor fß
E IAA
return
{hi 1.
fV, f
Algorithm 2 Q-value computed from utility and payoff tensors (and potentially global state st).
function QVALUE(F'
E
IR
VIXA
f IRlEixAXA E A, (u up(())
return M
ES
2 Σ S + (x))
return the Q-value of the given actions
Algorithm 3 Greedy action selection with message passes in a coordination graph.
function GREEDY(F IR
VixA E EIEEIAX V,E, [A') k)
A= : U; A
1 p = E
RIEIXA
messages forward (μ) and backward (ji) > initialize "Q-value" without messages
9" = V PV
for t E {1..... k} do
> loop with & message passes update forward and backward messages
for (i,j) E E do
H = max { [g 1-1
[(am)) ) + [2| Jea
eB
D forward: maximize sender
aEA'
p. = max { {(03aa 1-1 (2 + T [
> backward: maximizes receiver
aE
if www.sageenoommaiee. lization then
to ensure converging messages
1 + 3¹: TP
Σ
A normalize forward message
DEAD
F² + P²:
1
Σ
normalize backward message
IA
for E V do
update "Q-value" with messages & utility plus incoming messages
q. = M J
Σn
+
Σn' pl
(EEDEEE
e=(i;)E
af arg max (G:a)
a> select greedy action of agent
return t E A .... Al
return actions that maximize the joint Q-value
16


Reviews:
[{"review_id": "rkgKE6E0FS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThis paper proposes a pairwise communication between agents using a shared neural network. The idea is to define the joint action-value function as the sum of individual agent's values + pair-wise payoff between agents, which is based on the prior work [Castellini et al.]. In particular, this paper proposes to share the parameters of the pairwise payoff function to improve efficiency. The result on a grid-world domain shows that the proposed method performs better than baselines that either do not have pairwise communication (VDN) or learn fully joint action value function (QTRAN). \n\n# Originality\nThe main novelty seems to be coming from the idea of parameter sharing between pairwise payoffs, but the overall architecture seems to be the same as [Castellini et al.]. \n\n# Quality\n- This paper is missing an important baseline which is DCG without parameter sharing. Given that parameter sharing is the main new component from [Castellini et al.], it would be important to show the benefit of parameter sharing.\n- Although the result against several baselines looks good, it would be much more convincing to show some qualitative analysis of the proposed method. For example, showing that the learned payoff captures reasonable and intuitive knowledge would strengthen the paper.\n\n# Clarity\n- The paper is well-written, and the figures are very clear. \n- It would be better to show a figure that illustrates the domain and task. \n\n# Significance\n- Although the paper presents a new idea very well, the overall idea seems a bit incremental. This paper overall looks like a straightforward extension of [Castellini et al.] by adding parameter sharing and evaluating it on a more complex domain. In addition, showing more in-depth analysis would make the paper stronger. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkxPtjf2FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces the deep coordination graph for collaborative multi-agent reinforcement learning aimed to solve predator-prey tasks by preventing relative overgeneralization during the exploration of agents. \n\nIn general, this paper gives a detailed and comprehensible depiction of the Introduction, Related work and Background section. However, I have two concerns about their method and experiments. \n\nThe presentation of the “Method” section is not clear enough to evaluate the contribution of this paper. Specifically: \n(1). In the \"Method\" section, your method incorporates three ideas: 1. restricting the payoffs; 2. sharing parameters; 3. allowing generalization; \nIn my understanding, both idea 1 and idea 2 come from VDN [4]. Idea 3 is not implemented in this work. Then, what is your contribution?\n\n(2). According to the announcement, the key benefit for your work is \"prevent relative overgeneralization during exploration of agents\". It is hard to access if the proposed method can prevent overgeneralization. Do you have some theoretical or empirical justifications?\n\n(3). I think it would be helpful if you could give a description according to your algorithm in the appendix. It would be better to draw a diagram to show what is your model.\n\nI think the experiments are too simple and not convincing. \n(1). I notice recent multi-agent reinforcement papers ([1], [2] closely related to your work) evaluate their work on the challenging set of StarCraft II micromanagement tasks and achieved the evident result. \n \n(2). In fig.2, why did you only compare your model with VDN [4]?\n\n(3). In fig.3, why does the return value of QTRAN first decrease and then increase? From [3], it seems their return curve continuously grows. \n\n(4). In fig.4, why QTRAN fail to this task?\n\n[1]. Rashid, Tabish, et al. \"QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning.\" arXiv preprint arXiv:1803.11485 (2018).\n[2]. Wang, Tonghan, et al. \"Learning Nearly Decomposable Value Functions Via Communication Minimization.\" arXiv preprint arXiv:1910.05366 (2019).\n[3]. Son, Kyunghwan, et al. \"QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning.\" arXiv preprint arXiv:1905.05408 (2019).\n[4]. Sunehag, Peter, et al. \"Value-decomposition networks for cooperative multi-agent learning.\" arXiv preprint arXiv:1706.05296 (2017).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BJe9asNRYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary\n\nTeh authors propose to learn value functions that are a sum of utility (single-agent) and payoff (2-agent) components. The weights between all function are shared (common RNN). This stands in contrast to VDNs (only uses utility functions or centralized value functions. The authors evaluate on predator-prey, where they argue that e.g. VDN fails to learn.\n\n(Note that other work has looked at reward shaping to learn *decentralized* agents for that problem.)\n\n1. Decision (accept or reject) with one or two key reasons for this choice.\n\nWeak reject.\n\n- The comparison between different topologies is nice, but implies that the structure of the graph has to be fixed manually. This seems to be a severe and unscalable constraint. It would be better if the authors would propose and evaluate a method to determine / learn what the right graph structure should be.\n- Weight sharing between the various agent components makes the problem closer to a single-agent problem. What happens if the agents are decentralized and the (shared-weight) pairwise functions are separate?\n- Authors only evaluate on a predator-prey problem.\n\n4. Supporting arguments\n\nN/A\n\n5. Additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\n6. Questions", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work extends previous work (Castellini et al) with parameter sharing and  low-rank approximations, for pairwise communication between agents. 
However the work as presented here is still considered too incremental, in particular when compared to Castellini et al.
The advances such as parameter sharing and low-rank approximation are good but not enough of a contribution. Authors' efforts to address this concern did not change reviewers' judgment.
Therefore, we recommend rejection.
Decision: Reject