Context-Aware Sparse Deep Coordination Graphs
Authors: Tonghan Wang
Liang Zeng
Weijun Dong
Qianlan Yang
Yang Yu
Chongjie Zhang
Venue: ICLR 2022 Spotlight (2022)
Keywords: Multi-agent reinforcement learning
Sparse coordination graphs
Deep coordination graphs

Abstract: Learning sparse coordination graphs adaptive to the coordination dynamics among agents is a long-standing problem in cooperative multi-agent learning. This paper studies this problem and proposes a novel method using the variance of payoff functions to construct context-aware sparse coordination topologies. We theoretically consolidate our method by proving that the smaller the variance of payoff functions is, the less likely action selection will change after removing the corresponding edge. Moreover, we propose to learn action representations to effectively reduce the influence of payoff functions' estimation errors on graph construction. To empirically evaluate our method, we present the Multi-Agent COordination (MACO) benchmark by collecting classic coordination problems in the literature, increasing their difficulty, and classifying them into different types. We carry out a case study and experiments on the MACO and StarCraft II micromanagement benchmark to demonstrate the dynamics of sparse graph learning, the influence of graph sparseness, and the learning performance of our method.

Published as a conference paper at ICLR 2022
CONTEXT-AWARD SPARSE COORDINATION GRAPHS
Tonghan Wang" Liang Zeng' Weijun Dong', Qianlan Yang'. Yang Yu?, Chongjie Zhang' IInstitute for Interdisciplinary Information Sciences (IIIS). Tsinghua University NNational Key Laboratory of Novel Software Technology, Nanjing University
tonghanwang1 99999mmi1ll com
(zengl18, dwj18, ygl18) @mails tainghua edu. yuyenju.edie en, chong j jie@t s inghua. edu. en
ABSTRACT
Learning sparse coordination graphs adaptive to the coordination dynamics among agents is a long-standing problem in cooperative multi-agent learning. This paper studies this problem and proposes novel method using the variance of payoff functions to construct context-aware sparse coordination topologies. We theoret- ically consolidate our method by proving that the smaller the variance of payoff' functions is, the less likely action selection will change after removing the corre- sponding edge. Moreover, we propose learn action representations effectively reduce the influence of payoff functions' estimation errors on graph construction. To empirically evaluate our method, we present the Multi-Agen COordination (MACO) benchmark by collecting classic coordination problems in the literature, increasing their difficulty, and classifying them into different types. We carry out case study and experiments on the MACO and StarCraft II micromanagement benchmark to demonstrate the dynamics of sparse graph learning, the influence graph sparseness, and the learning performance of our method
INTRODUCTION
Many real-world problems involve the cooperation of multiple agents, such as unmanned aerial vehicles (Pham al. 2018 Xu et al., 2018) and sensor networks (Stranders al. 2009). Like in
single-agent settings, learning control policics for multi-agent teams largely relies on the estimation
of action-value functions, matter in value-based (Sunehag al. 2018 Rashid al. 2018 2020)
or policy-basce approaches (Lowe et al.) 2017]] Foerster et al.) 2018 Wang et al. 2021c). However, learning action-value functions for complex multi-agent tasks remains major challenge. Learning individual action-value functions [Tan] 1993) is scalable but suffers from learning non-stationarity because it treats other learning agents as part of its environment. Joint action -alue learning (Claus Boutilier 1998) is free from learning non-stationarity but requires access to global information that is often unavailable during execution due partial observability and communication constraints.
Factored Q-learning (Guestrin et al. 2002a) combines the advantages of these two methods. Learning the global action-value function as a combination of local utilities, factored Q functions maintain learn- ing scalability while avoiding non-stationss non-stationarity. Enjoying these advantages, fully decomposed Q func- tions significantly contribute to the recent progress of multi-agent reinforcement learning (Samvelyan) et al. 2019 Wang et al.) 1b2 However, when fully decomposed, local utility functions only depend on local observations and actions, which may lead to miscoordination problems in partially observable environments with stochastic transition functions (Wang et al. 2220 2021a) and game- theoretical pathology called relative overgeneralization (Panait et al.) 2006 Böhmer et al. 2020). Relative overgeneralization renders optimal decentralized policies unlearnable when the employed value function does not have enough representational capacity to distinguish other agents' effects on local utility functions.
Coordination graphs (Guestrin et al.) 2002bb provide a promising approach to solving these problems. Using vertices to represent agents and (hyper-) edges to represent payoff functions defined over the
Equal Contribution.
'The MACO benchmark and codes are publicly available at http:pp:/gggttbb..o.//o/aaaaaaaa
CASIC- MACO-AAA----C Sacco-benncmar2

---

Published as a conference paper at ICLR 2022
space of the connected agents, coordination graph expresses higher-order value decomposition among agents. Finding actions with the maximum value in a coordination graph can be achieved by distributed constraint optimization (DCOP) algorithms (Cheng 2012), which consists of multiple rounds of message passing along the edges. Recently, DCG (Böhmer et al. 2020) scales coordination graphs to large state-action spaces, shows its ability solve the problem of relative overgeneralization, and obtains competitive results on StarCraft II micromanagement tasks. However, DCG focuses on predefined static and dense topologies, which largely lack flexibility for dynamic environments and induce intensive and inefficient message passing.
joint
The question is how to learn dynamic and sparse coordination graphs sufficient for coordinated action selection. This is a long-standing problem in multi-agent learning. Sparse cooperative Q-learning (Kok & Vlassis 2006) learns value functions for sparse coordination graphs, but the graph topology is static and predefined by prior knowledge. [Zhang & Lesser (2013) propose to learn minimized dynamic coordination sets for each agent, but the computational complexity grows exponentially with the neighborhood size of an agent. Recently, Castellini et al. (2019) study the representational capability of several sparse graphs but focus on random topologies and stateless games. In this paper, we push these previous works further by proposing novel deep method that learns context-aware sparse coordination graphs adaptive to the dynamic coordination requirements.
For learning sparse coordination graphs, we propose to the variance of pairwise payoff functions as an indicator to select edges. Sparse graphs are used when selecting greedy joint actions for execution and the update of Q-function. We provide theoretical insight into method by proving that the probability of greedy action selection changing after an edge is removed decreases with the variance of the corresponding payoff function. Despite the advantages of sparse topologies, they raise the concern of learning instability. To solve this problem, we further equip our method with network structures based on action representations for utility and payoff learning to reduce the influence of estimation errors on sparse topologies learning. We call the overall learning framework Context-Aware SparsE: Coordination graphs (CASEC).
For evaluation, we present the Multi-Agent COordination (MACO) benchmark. This benchmark collects classic coordination problems raised in the literature of multi-agent learning, increases their difficulty, and classifies them into 6 classes. Each task in the benchmark represents type of problem. We carry out a case study on the MACO benchmark to show that CASEC can discover the coordination dependence among agents under different situations and to analyze how the graph sparsity influences action coordination. We further show that CASEC can largely reduce the communication cost (typically by 50%) and perform significantly better than dense, static graphs and several alternative methods for building sparse graphs. We then test CASEC on the StarCraft II micromanagement benchmark (Samvelyan et al. 2019) to demonstrate its scalability and effectiveness.
2 BACKGROUND
In this paper, we focus on fully cooperative multi-agent tasks that can be modelled as a Dec- POMDP Oliehock et al. 2016) consisting of a tuple G= A, P. R, Ω O, n, n, where I is the finite set n agents, 7 E i) the discount factor, and s E S is the true state of the environment. At each timestep, each agent receives an observation o, E Ω drawn according to the observation function Oss, i) and selects an action 0g E A. Individual actions form a joint action a E A", which leads to next state s' according to the transition function P(s ([s'|s, a), a reward
R(s, a) shared by all agents. Each agent has local action-observation history T, E T (Ω x A)* x Ω. Agents learn to collectively maximize the global return Qtor (s, a) E Es E 7 R(s,, as){so s, ag = a).
In coordination graph (Guestrin et al. 2002b G (V,E), each vertex is E V represents an agent i, and (hyper-) edges in E represent coordination dependencies among agents. In this paper, we consider pairwise edges, and such coordination graph induces a factorization of the global Q:
1 Qroe (T. a) = [V]
Σ ( 0z) +
Σ {WJEEE
(g(TTg aig))
(1)
E
where qi and qız is utility functions for individual agents and pairwise payoff functions, respectively. Tay (7,, Ty) and aig- (ai,ay) ag) is the joint action-observation history and action of agent i and j.
2

---

Published as a conference paper at ICLR 2022
Within coordination graph, the greedy action selection required by Q-learnig can not be completed by simply computing the maximum of individual utility and payoff functions. Instead, distributed constraint optimization (DCOP) (Cheng] 2012) techniques can be used. Max-Sum (Stranders et al., 2009) is a popular implementation of DCOP, which finds optimal actions on a coordination graph (V. E) via multi-round message passing on bipartite graph 9m (Va: Vq: Em). Each node i E V. represents an agent, and each node E Vy represents utility (Φ:) or payoff' (gt) function.
Edges in Em connect g with the corresponding agent node(s). Message passing on this bipartite graph starts with sending messages from node i E Va to node 9 E Vg:
mi-+g (a:)
Σ bEFF
mi-i (a:) + Cig
(2)
where Fi is the set of nodes connected to node in Vg. and Gig is normalizing factor preventing the value of messages from growing arbitrarily large. The message from node g to node i is:
Mg-+i (a,)
max
9 (ag)) +
Σ ma-+g (ax) NEV
ag (a
where V/ is the set of nodes connected to node g in Va. a== (a, lh Vg), ag fa E Vg {i)). and y represents utility or payoff functions conditioned on ag. After several iterations of message passing, each agent i can find its optimal action by calculating at argmax,; ΣnET Mp-i (az).
A drawback of Max-Sum or other message passing methods (e.g., max-plus (Pearl, 2014)) is that running them for each action selection through the whole system results in intensive computation and communication among agents, which is impractical for most applications with limited computational resources and communication bandwidth. In the following sections, we discuss how to solve this problem by learning sparse coordination graphs
Previous works (Naderializadeh et al., 2020 Li et al. 202T) study soft versions of fully-connected coordination graphs based on attention mechanisms. Specifically, Li et al. (2021) uses graphs whose edge weights are learned by self-attention so that agents attend to observations of other agents differently. The information is used in local actors or a centralized critic. |Naderializadeh et al. (2020) learns soft full graphs a similar way, but the graph used to mix local utilities conditioned on local action-observation history. Different from our work, these methods do not learn pairwise payoff functions, and the learned graphs are still fully-connected.
LEARNING CONTEXT-AWand SPARSE GRAPHS
In this section, introduce our methods for learning context-aware sparse graphs. We first introduce how we construct a sparse graph for effective action selection in 3.1 After that, we introduce our learning framework in Sec. 3.2 Although sparse graphs can reduce communication overhead, they raise the concern of learning instability. We discuss this problem and how to alleviate it in Sec. 3.3
3.1 CONSTRUCT SPARSE GRAPHS
Action values, especially the pairwise payoff functions, contain much information about mutual influence between agents. Let's consider two agents i and j. Intuitively, agent i needs to coordinate its action selection with agent j if agent j's action exerts significant influence on the expected utility of agent i. For fixed action a,, Vara, [9 (Tij. aij)] can measure the influence of agent on the expected payoff. This intuition motivates us to use the variance of payoff functions
C = max Var,, (T.j a:j)). max a.
(4)
as an indicator to construct sparse graphs. The maximization operator guarantees that the most affected action is considered. When (3"" large, the expected utility of agent é fluctuates dramatically with the action of agent j. and they need to coordinate their actions. Therefore, with this measurement, to construct sparse coordination graphs, we can set sparseness controlling constant À E (0, 1) and select X/V (IV) - 1) edges with the largest (2) values.
To justify this approach, we theoretically prove that, the smaller the value of che is, the more likely that the Max-Sum algorithm will select the same actions after removing the edge (i.
3

---

Published as a conference paper at ICLR 2022
Proposition 1. after removing edge eij. greedy actions of agent and j selected by the Max-Sum algorithm keep unchanged with probability larger than
For any two agents j and the edge eşj connecting them in the coordination graph,
(m mina, m(aj))(max,, m(aj) -1))
(5)
[A]
(h + 2M + 2/ M (M² - (,),0) -(.50)))
where mı(aj) = Mays - (1)), , in is the averuge of m(u)). M maxas [mnaxa (ai, (ai, az)l.
and r(a,, (g) a(04 a2) + mi-res (a,).
Detailed proof can be found Appendix A The lower bound in Proposition I increases with a decreasing C Therefore, edges with smaller Cif are less likely to influence the results of Max-Sum, justifying the way we construct sparse graphs.
3.2 LEARNING FRAMEWORK
Like conventional Q-learning, CASEC consists of two main components learning value functions and selecting greedy actions. The difference is that these two steps are now carried out on dynamic and sparse coordination graphs.
In CASEC, agents learn shared utility function qg. (-17a), parameterized by É.. and shared pairwise payoff function gE, (- (TT)) parameterized by Sp. The global Q value function is estimated as:
1 [V] Σ qs, (a:lTs)
1 |VKVV 1)
Q a)
Σ qsp (a.s)
(6)
which is updated by the TD loss:
(p): 1ED ED [1 (1+ Max-Sum(qg, (g.)) rear (T, (T,
Max-Sum(:,)) is the greedy joint action selected by Max-Sum, Qtat is target network with param- eters É.r En periodically copied from Qtoe. and the expectation estimated with uniform samples from a replay buffer D. Meanwhile, we also minimize a sparseness loss
sparse (Sp)
Vara; (Tij, aij)],
(8)
DI(V A
which regularization Ch Introducing a scaling factor Asparse (0, 1] and minimizing LTD(Su, Ep) +A Cipare (Ep)) builds in inductive biases which favor minimized coordination graphs that would not sacrifice global returns.
Actions with the maximized value are selected for Q-learning and exccution. In our framework. such action selections are finished by running Max-Sum sparse graphs induced by <3;- (while we update Q functions on the full graph). Running Max-Sum requires the message passing through each node and edge. To speed up action selections, similar to previous work (Böhmer et al. (020), multi-layer graph neural networks without parameters to process messages in a parallel manner.
3.3 STABILIZE LEARNING
One question with estimating Fy is that there are |A] x |A] action-pairs, each of which requires an output head in conventional deep Q networks. As only executed action-pairs are updated during Q-learning, parameters of many output heads remain unchanged for long stretches of time, resulting in estimation errors. Previous work (Böhmer et al. (020) uses low-rank approximation to reduce the number of output heads. However, is largely unclear how choose the best rank K for different tasks, and still only [ of the output heads are selected in one Q-learning update.
This problem of estimation errors becomes especially problematic in CASEC, where building coordination graphs relies on the estimation of qtj- A negative feedback loop is created because the built coordination graphs also affect the learning of dij- This loop renders learning unstable (Fig. 5)
4

---

Published as a conference paper at ICLR 2022
We propose to solve this question and stabilize training by 1) periodically fixing the way construct graphs via using the target payoff function to build graphs; and 2) accelerating the training of payoff function between target network updates to reduce the estimation errors via learning action representations.
Specifically, for 2), propose to condition the utility and payoff functions action representations to improve sample efficiency. We train an action encoder fe. (a), whose input is the one-hot encoding of action and output its representation Z We adopt the technique introduced by Wang et al. (20216) to train an effect-based action encoder. Specifically, action representation cas together with the current local observations, is used predict the reward and observations the next timestep. The prediction loss is minimized to update the action encoder fe. (a). For more details, we refer readers to Appendix D The action encoder trained with few samples when learning begins and remains unchanged for the rest of the training process.
Using action representations, the utility and payoff functions can now be estimated as:
95. (Ta, a1)) ltg. (T=) T Zozi
(9)
de, (Ty) aty) = hgg (Tx)) [(zo: Fayl:
where h includes GRU (Cho al.) 2014) to process sequential input and output vector with the same dimension as the corresponding action representation. [ means vector concatenation. Using Eq. 9 matter which action selected for execution, all parameters in the framework (Ev and Ep)
would be updated. The detailed network structure can be found in Appendix B
4 MULTI-AGENT COORDINATION BENCHMARK
To evaluate our sparse graph learning algorithm. we collect classic coordination problems from the cooperative multi-agent learning literature, improve their difficulty, and classify them into different types. Then, 6 representative problems are selected and presented as a new benchmark called Multi-Agent COordination (MACO) challenge (Table
At the first level, tasks are classified factored and non-factored games, where factored games present an ex- plicit decomposition of global re- wards. Factored games are further categorized according two proper- ties whether the task requires pair- wise or higher-order coordination, and whether the underlying coordination relationships change temporally. For non-factored games, we divide them into two classes by whether the task characterizes static coordination rela- tionships among agents. To better test
Table I: Multi-agent coordination benchmark.
Task
Factored
Pairwise
Dynamic
# Agents
Aloha
10
Pursuit
V
10
Hallway
V
12
Sensor
V
V
15
Gather
Disperse
the performance of different methods, we increase the difficulty of the included problems by ex- tending stateless games to temporally extended settings (Gather and Disperse), complicating the reward function (Pursuit), or increasing the number of agents (Aloha and Hallway). We now briefly describe the setting of each game. For detailed description, we refer readers to Appendix [
Aloha (Hansen et al. 2004 Oliehoek 2010) consists of 10 islands in 5 array. Each island has backlog of messages to send. They send one message or not at each timestep. When two neighboring agents send simultaneously, messages collide and have be resent. Islands start with package in the backlog. At each timestep, with a probability 0.6 (5) has not been reached. Each agent observes its position and the number packages in its backlog. Agents receive global reward of (..1 for each successful transmission, and -10 for collision.
packet arrives if the maximum backlog
Pursuit, also called Predator and Prey, is a classic coordination problem (Benda 1986 Stone & Veloso 2000; [Son al.] 2019). Ten agents (predators) roam a 10 10 map populated with 5 random walking preys for 50 environment steps. One prey is captured if two agents catch it simultancously. after which the catching agents and the prey removed from the map, resulting in team reward
5

---

Published as a conference paper at ICLR 2022
DASEC Joaeredi
CASZC boamed yelumi
DCG boamnol
CASEC We Jein Scamed) WV fave Veduri
Targee
Agosb
Actensccionged /odded by
S edges
Figure I: Left: Learning curves (return and the number of successfully scanned targets) of CASEC and DCG Sensor. Middle: The influence of graph sparseness performance (re- turn and the number of scanned targets). Here we show the case of the best seed. The plot of other seeds be found in Fig. 21 Right: An example coordination graph learned by our method.
of 1. only one agent tries to eatch the prey, the prey would not be captured and the agents will be punished. We consider a challenging version of Pursuit by setting the punishment to 1, which is the same as the reward obtained by a successful catch.
Hallway (Wang et al. 2020) is multi-chain Dec-POMDP. We increase the difficulty of Hallway by introducing more agents and grouping them (Fig. 6p. One agent randomly spawns state in each chain. Agents can observe their own position and choose to move left, move right, or keep still at each timestep. Agents win with a global reward of I they arrive at state g simultaneously with other agents in the same group. If n 1 groups attempt to move to g the same timestep, they keep motionless and agents receive a global punishment of 0..5 * Rgg-
Sensor has been extensively studied (Lesser et al. 2012 Zhang & Lesser 2011). We consider 15 sensors in a 3 x 5 matrix. Sensors can scan the eight nearby points. Each scan induces a cost of -1, and agents can do noop save the cost. Three targets wander randomly in the gird. If k: sensors scan a target simultaneously, the system gets a constant reward of 3, which is independent of the number of sensors. Agents can observe the id and position of targets nearby.
Gather is an extension of the Climb Game (Wei & Luke 2016). In Climb Game, each agent has three actions: A {ao: 01 a2). Action do yields reward (0) if only some agents choose it, but high reward (10) if all choose it. Otherwise, if no agent chooses action ag. reward 5 is obtained. We increase the difficulty of this game by making temporally extended and introducing stochasticity. Actions are no longer atomic, and agents need to learn policies to realize these actions by navigating to goals 91 92 and 93 (Fig. 7.. Moreover, for each episode, one of 91. 92 and 93 randomly selected as the optimal goal (corresponding to ag in the original game).
Disperse consists of 12 agents. At each timestep. agents can choose to work at one of 4 hospitals by selecting an action in = {ao, 41 022 03). timestep i, hospital j needs af agents for the next timestep. One hospital randomly selected and its x/ is a positive number, while the need of other hospitals is 0. If v441 < o agents go to the selected hospital, the whole team would be punished vi+ 2/. Agents observe the local hospital's id and its need for the next timestep.
5 CASE STUDY: LEARNING SPARSE GRAPHS ON Sensor
We are particularly interested in the dynamics and results of sparse graph learning. Therefore, carry out a case study on Sensor. When training CASEC on this task, we select 10% edges with largest Ci values to construct sparse graphs.
Interpretable sparse coordination graphs. In Fig. I we show a screenshot of the game with the learned coordination graph at a certain timestep. We can observe that all edges the learned graph involve agents around the targets. Let's see the case of agent 8. The action proposed by the individual utility function of agent 8 is to scan target other agents, agent changes its action selection and scans target target 2, resulting in optimal solution for the given configuration. This result is in line with our theoretical analysis in Sec. 3.1 The most important edges can be characterized by large ( value.
After coordinating its action with
Influence of graph sparseness on performance. It is worth noting that with fewer edges in the coordination graph, CASEC has better performance than DCG on Sensor (Fig. | left, where the

---

Published as a conference paper at ICLR 2022
(spunse graph L005 odges)
wo spare Joss Osparse graph 10' edges)
tsparse graph 10% edges)
Targes their
graph)
CASBC spanse tfuil grapet
graph)
Agents and their ids
actions
Figure 2: Coordination graphs learned by different methods Sensor.
CASEC (Ours)
VDN
Weighted QMIX (CW-QMIX)
DICG
DCG
QMIX
Weighted QMIX (MM))MIX)
GraphMix
Alcha
Pursult
Hallway
Transmitte
Toos Payy Cought
75
50
0.0
0.5
15
2.0
0.0
0.3
1.5
13
2.0
0.0
0.2
3.4
0.5
0.8
1.0
Disporse
Teat Scanedd
The Senuum
Wi
0.0
(mm)
((mll)
7mml
Figure Performance comparison with baselines on the MACO benchmark.
median performance and 25%-75% percentiles are shown). This observation may be counter-intuitive the first glance. To study this problem, we load the model after convergence learned by CASEC and DCG, gradually remove edges from the full graph in the ascending order of (. and check the change of scanned targets and the obtained reward. Results are shown Fig. T middle and Fig. 21
It can be observed that the performance of DCG (the number of scanned targets) does not change with the number of edges. another word, only the individual utility function contributes to scanning targets. Screenshots shown in Fig. (right column) align with this observation. With more edges, DCG makes a less optimal decision: agent 4, 5, and no longer sean target 1.
In contrast, the performance of CASEC grows with referring to Fig. (left column), we can conclude that CASEC first selects edges that help agents scan more targets, and then selects edges that can eliminate useless scan actions. These results demonstrate that our method can distinguish the most important edges on Sensor.
edges in the coordination graph. By
We also study the influence of the sparseness loss (Eq. E). As shown in Fig miiddle, CASEC without the spanseness loss consistently gets fewer rewards than CASEC. For example, target and 3 are not captured in the case shown Fig. 2 (middle column) only one agent scans them. These results highlight the function of the sparseness loss.
EXPERIMENTS
In this section, we design experiments to answer the following questions: (1) How much communi- cation be saved by method? How does communication threshold influence performance factored and non- non-factored games? (Sec. 6. (2) How does our method compare to state-of-ti of-the--rt
multi-agent learning methods? (Sec. 6.2 (3) Is method efficient in settings with larger
7

---

Published as a conference paper at ICLR 2022
oatton-observation spaces? (Sec. 6.33 For results in this section, show the median performance with random seeds as well as the 25-75% percentiles.
6.1 GRAPH SPARSENESS
An important advantage of learning sparse coordination graphs is reduced communication costs. The complexity of running Max- Sum for each action selection is O (k (VilA| [ where k is the number of iterations of message passing. Sparse graphs cut down communication costs by reducing the number of edges.
Table 2:
Percentage of commu-
nication saved for each task.
Aloha
Pursuit
Hallway
80.0%
70.0%
50.0%
We carry out grid search find the communication threshold under which sparse graphs have the best performance. We find that most implementations of dynamically sparse graphs require similar numbers of edges to prevent performance from dropping significantly. In Table we show the communication cut rates games typically require more messages than factored games, while, for most tasks, at least 50% messages be saved without sacrificing the learning performance.
Sensor
Gather
Disperse
90.0%
30.0%
60.0%
when benchmarking
method. Generally speaking. non-factored
Communication threshold vs. performance In Fig. 4 we show the performance our method under different communication thresholds which control the sparseness of edges. We can observe that, on the factored game Sensor, performance first grows then drops when more edges are in- cluded in the coordination graphs. These ob- servations are in line with the fact that sparse graphs can outperform complete graphs and fully-dccomposed value functions on this task. In contrast, for the non-factored game Gather, performance stabilizes beyond a certain thresh- old. Non-factored games usually involve com- plex coordination relationships, and denser topologies are suitable for this type of questions.
Senser Factored Game!
Fartordd Game)
Performance
20
0.8
15
0.6
20
0.0
0.25
0.50
1.00
0.00
0.25
0.50
0.75
1,00
Threshold
Threshold
Figure 4: The influence of graph sparseness (1.0 represents complete graphs) on the performance on factored games (Sensor, left) and hon-factored games (Gather, right).
6.2 MACO: MULTI-AGENT COORDINATION BENCHMARK
We compare our method with tlate-of-the-ae fully- dellopoedd value-based methods (VDN (Sunchag
et al. 2018), QMIX (Rashid et al., 2018), and Weighted QMIX (Rashid al. (0220), coordina- tion graph learning method (DCG (Böhmer et al. 2020)), and attentional graph learning methods (DICG (Li et al. 202T) and GraphMIX (Naderiali) lideeializzdeh lizddh al. (020)) on MACO (Fig. 3). Since the number of actions is not very large in MACO, we do not use action representations when estimating the utility and payoff function for CASEC.
We can see that our method significantly outperforms fully-decomposed value-based methods. The reason is that decop-eee methods suffer from the relative overgeneralization issue and miscoordination problems in partially observable environments with stochasticity. For example, on task Pursuit (Bendal 1986), if more than one agent catches one prey simultaneously, these agents will be rewarded 1. However, if only one agent catches prey, it fails and gets a punishment of -1. For an agent with limited sight range, the reward it obtains when taking the same action (catching a prey) under the same local observation depends on the actions of other agents and changes dramatically. This is the relative overgeneralization problem. Another example is Hallway (Wang al.. 2020), where several agents need to reach goal state simultaneously without knowing each other's 's location. Fullyddeoompsedd methods cannot solve this problem the initial positions of agents are stochastic.
For DCG, we use its default settings of complete graphs and no low-rank approximation. We observe that DCG is less effective on tasks characterized by sparse coordination interdependence like Sensor. We hypothesize this is because coordinating actions with all other agents requires the shared estimator to express payoff functions of most agent pairs accurately enough, which needs more samples to lear,, hurting the performance of DCG on loosely coupled tasks.
8

---

Published as a conference paper at ICLR 2022
rept)
DraphMiX
QMIX
CASEC (Ours)
CASEC (rank 1)
DICG
b) Win MMM2
MMN2
2.00
102
0.25
To Enger
0.32
0.13
T
Figure 5: Performance and TD errors compared to baselines and ablations on the SMAC benchmark.
6.3 STARCRAFT II MICROMANAGEMENT BENCHMARK
We compare our method against the state-of thrt--rr coordination graph learning method (DCG (Böh- mer et al.] 2020)) and fully decomposed value- MARL algorithms (VDN (Sunehag et al. 2018). QMIX (Rashid et al., 2018)). For CASEC, we use action representations to estimate the payoff function. We train the action encoder for 50k samples and keep action representations unchanged afterward. In Fig. 5 we show results on _an_v_______________ 6m and MMM2. Detailed hyperparameter settings of method can be found in Appendix E
For DCG, we use its default settings, including a low-rank approximation for learning the payoff function. We can see that CASEC outperforms DCG by a large margin. The result proves that sparse coordination graphs provide better scalability to large action-observation spaces than dense and static graphs. In DCG's defense, low-rank approximation still induces large estimation errors. We replace low-rank approximation with action representations and find that DCG (Full (action repr.)) achieves similar performance to CASEC after 5M steps, but CASEC is still more sample-efficient Moreover, taking advantage of higher-order value decomposition, CASEC is able to represent more complex coordination dynamics than fully decomposed value functions and thus performs better.
A Ablation study Our method is characterized by two contributions: context- aware sparse topologies and action representations for learning the utility and payoff function. In this section, we design ablations to show their contributions.
The effect of sparse topologies can be observed by comparing CASEC Full (action repr.), which the same as CASEC other than using complete coordination graphs. We observe that sparse graphs enjoy better sample efficiency than full graphs, and the advantage becomes less obvious as more samples are collected. This observation indicates that sparse graphs introduce inductive biases that can accelerate training, and their representational capacity is similar to that of full graphs.
From the comparison between CASEC to CASEC using conventional Q networks (w/o action repr.), we can see that using action representations can significantly stabilize learning. For example, learning diverges 5m 6m without action representations. As analyzed before, this is because negative feedback loop is created between the inaccurate payoff function and coordination graphs.
To further consolidate that action representations learning oscillation as discussed in Sec. 3.3 we visualize the TD errors of CASEC and ablations during training in Fig-5 We errors. For comparison. the low-rank approximation can also reduce the TD errors, but much less significantly. Smaller TD errors prove that action representations provide better estimations of the value function, and learning with sparse graphs can thus be stabilized (Fig. left).
reduce the estimation errors and thus alleviate
that action representations
dramatically reduce the TD
7 CONCLUSION
We study how to learn dynamic sparse coordination graphs, which is long-standing problem in cooperative MARL. We propose a specific implementation and theoretically justify it. Empirically, we evaluate the proposed method a new multi-agent coordination benchmark. Moreover, we equip our method with action representations to improve the sample efficiency of payoff learning and stabilize training. We show that sparse and adaptive topologies largely reduce communication overhead as well as improve the performance of coordination graphs. We expect our work to extend MARL to more realistic tasks with complex coordination dynamics.

---

Published as a conference paper at ICLR 2022
One limitation of our method is that the learned sparse graphs are not always cycle-free. Since the Max-Sum algorithm guarantees optimality only on acyclic graphs, our method may select sub-optimal actions. In Appendix F., study this problem in depth.
Another limitation is that we fix the communication threshold when training. It is an important question how automatically and accurately find the minimum threshold that guarantee the learning performance. In Appendix[[ [] we study two ways to adaptively select the threshold.
The source code for all the experiments along with README file with in- structions on how to run these experiments is attached in the supplementary material. In addition. the settings and parameters for all models and algorithms mentioned in the experiment section are detailed in Appendix
Reproducibility
REFERENCES
Miroslav Benda. On optimal cooperation of knowledge sources: empirical investigation. Technical Report, Boeing Advanced Technology Center, 1986.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Jacopo Castellini, Frans A Oliehoek, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgen Systems, pp. 1862-1864. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Shanjun Cheng. Coordinating decentralized learning and conftict resolution across agent boundaries. PhD thesis, The University of North Carolina at Charlotte, 2012.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734, 2014.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI/IAA,, 1998(746-752):2. 1998.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Advances in neural information processing systems, pp. 1523-1530, 2002a.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML, volume 2, pp. 227-234. Citeseer, 2002b.
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In AAAI, volume 4, pp. 709-715, 2004.
Jelle R Kok and Nikos Vlassis. Collaborative multiagent reinforcement learning by payoff propagation. Journal of Machine Learning Research, 1799-1:78991828 2006.
Victor Lesser, Charles L Ortiz Jr, and Milind Tambe. Distributed sensor networks: multiagent perspective, volume 9. Springer Science & Business Media, 2012.
Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit co- ordination graphs for multi-agent reinforcement learning. Proceedings of the 20th International Conference Autonomous Agents and MultiAgent Systems, pp. 764-772, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent environments. In Advances in Neural Information
actor-critic for mixed Processing Systems, pp. 6379-63390, 2017.
10

---

Published as a conference paper at ICLR 2022
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Navid Naderializadeh, Fan H Hung, Sean Soleyman, and Deepak Khosla. Graph convolutional value decomposition in auutti-agent reinforcement learning, arXiv preprint TrXiv:2010004740, 2020.
Julius Nagy. Über algebraische gleichungen mit lauter reellen wurzeln. Jahresbericht der Deutschen Setthemmaikke-Veriiiiiiieee 27:37-43, 1918.
Frans Oliehoek. Value-bused planning for teams of agents stochastic partially observable environ- ments. Amsterdam University Press, 2010.
Frans A Oliehoek, Christopher Amato, al. A concise introduction decentralized POMDPs, volume 1. Springer, 2016.
Liviu Panait, Sean Luke, and R Paul Wiegand. Biasing coevolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation, 10(6):629-66) 2006.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier, 2014.
Huy Xuan Pham, Hung Manh La. David Feil-Seifer, and Aria Nefian. Cooperative and distributed reinforcement learning of drones for field coverage, 2018.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4292-4301, 2018
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: / 1902.0403, 2019.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning factorize with transformation for cooperative multi-agent reinforcement learning. International Conference on Machine Learning, pp. 5887-5896, 2019.
Peter Stone and Manuela Veloso. Multiagent systems: A survey from a machine learning perspective. Autonomous Robots, 8()):35-333,, 2000.
Ruben Stranders, Alessandro Farinelli, Alex Rogers, and Nick Jennings, Decentralised coordination of mobile sensors using the max-sum algorithm. In Twenty-First International Joint Conference on Artificial Intelligence, 2009.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Valoe-ddcoopooiitoon networks for cooperative multi-agent learning based on team reward. Proceedings of the 17th International Conference Autonomous Agents und MultiAgent Systems, pp. 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex:
Duplex ducling multi-agent geaarnnng. International Conference Learning Representations (ICLR), 2021a
11

---

Published as a conference paper at ICLR 2022
Tonghan Wang. Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decomposable value functions with communication minimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Tonghan Wang. Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose multi-agent tasks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021b.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Dop: Off-policy
multi-agent decomposed policy gradients. In Proceedings of the International Conference Learning Representations (ICLR), 2021c.
Ermo Wei and Sean Luke. Lenient learning in independent-learner stochastic cooperative games. The
Journal of Machine Learning Research, 17(1):2114-295 2016.
Zhao Xu, Yang Lyu, Quan Pan, Jinwen Hu, Chunhui Zhao. and Shuai Liu. Multi-vehicle flocking
control with deep deterministic policy gradient method. 2018 IEEE 14th International Conference on Control and Automation (ICCA), Jun 2018. doi: 10. 1 109/icca. 8.44855.. URL http1
dxx org.oorg/0.. 1109/ICCA, 2018 8444355
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
Chongjie Zhang and Victor Lesser. Coordinating multi-agent reinforcement learning with limited communication. In Proceedings the 2013 international conference Autonomous agents and multi-agent systems, pp. 1101-1108, International Foundation for Autonomous Agents and Multiagent Systems, 2013.
12

---

Published as a conference paper at ICLR 2022
A MATHEMATICAL PROOF
In this section, we provide proof to Proposition 1
Without loss of generality, consider two agents and and the edge between them (1, We prove our idea by comparing the action selection of agent 2 before and after removing edge (1,2). In the following proof, we (i 1, 2) denote agent and to denote edge (1,
Action of agent 2 is determined by
a2 arg max
(22)((22)
(10)
02
bEF2
arg max
m Me-2 (a2) +
Σ hEF2/(e)
m ma22((2)
(11)
and we first see the influence of (e=2((2) on az. For clarity, we use m(a2) denote m
and I(22) to denote EneFe/fet (02). We are interested in whether arg maXa; ((2)
arg max,, (m(az) + [[a2)]. The probability of this event holds if the following inequality holds:
Range (m(a2)] S min (I(a)) I(a2)).
(12)
02
where (a)ge(a:) denotes the largest elements vector æ minus the smallest one and a² arg maxe, (a2). We rewrite Eq. 12 and obtain
Pr Range [m(a2) < min (I(a)) ((a2))
(13)
=Pr min m(2)) < m(a2) < min m(2)) + min (a(a)) - -((z))
(14)
02
According to the Asymmetric two-sided Chebyshev's inequality (Mitzenmacher & Uptal get a lower bound of this probability:
2017 we
m ming, m(a2)) (max,, m(a2) - -m) -
(15)
min وج (1(a)) I(a2))
where a is the variance maz), and m is the average m m(a2).
Suppose that take |A] actions independently. According to the von Szokefalvi Nagy inequal- ity (Nagy 1918), we can further get the lower bound as follows:
m mingo m(a2)) )) (maxa; m(az) - m) o²
(m min m(a2)) (o(a2))(mxx, m(02) m) o²
2|A|02
min aa (M(a)) ((a2))
(m min,, m(az)) m(az) m)
[
x²
(16)
Note that
m(a2)= max [g(a1, a2) mm)e((a)), a1
(17)
and we are interested a2).. We now study the relationship between m(az) and maxa, [q(a), az)]. For clarity, we use r(a1, 42) to denote g(a1, az) + (a1) and r(a ax) to denote max., r(a1, 02). Then we have Vara, maxa, r(a1, 02) = Vara,r
For given az have
Var var,, (01,02) 02) Varaz [r(at a2) 82]
(18)
13

---

Published as a conference paper at ICLR 2022
Here 82 O, Va1, because = arg max; 7(1,,
Since
Varaz [r(a]' a2) -52]
(19)
=Vara, [r(a]t a2)] + Var [82] - (Cov(r(aff,a)))
(20)
and
(ovrr(a),a2),533 S Varra [r[a],, az)] Var [82]:
(21)
it follows that
Varag [r(a] a2) (2)_222200 -82
(22)
/Vara, [2)] Var [s2]-
2 Varag
(23)
Thus,
S12 [r(a), max Varag (r(a1,a2) a2)] 2 Varag max [2(a - 2 Varaz [r(af. u2)l Var [82]
(24)
Observing that S12 [r(a1, az)] maxa; Varaz [r(a1, [2)] = maxa, Vara, [a(a), (2)l S12 [g(ai, (2)], we have
=
Varaa [r(a]t S (1alg(an, 2
[()) Var [s2]
(25)
(1elgeaa, a2)l + 2Vo8.
where a = Vara, max [2()),02) and Var [s2] S. According to the fixed-point theorem, the term satisfies (12 [g()), 02) +2 We can solve this quadratic form and get a = Ç12 [2))) 25 + 2/ 5 (S S12 [ a2)]) Because the term is larger than Ç12 [2)] + 25, we get
= {12 [ي(a), a2)] 2S 2/5 + C12 [g(01, a2)]). By inserting this inequality the lower
bound (Eq. 16). we get lower bound related to (()).02):
2 [
(m - min m(a ) ml(a) m)
(26)
[S12 [q(a), a2)] + 25 + 2 SS C12 (q(a),
When a vector æ is larger than 0 and the the cardinality of æ is n, we have: Var(x) = Em (I:
1 Em xx EE= x S max; x? Thus we can further get the following bound:
Var
max r (a1, 02) r (a1, az)
a
(27)
max
max r. (01, - r (a1, a2)
G1
Let M maXos [max,, (ai, (2) (ai, [2)], thus we have S S 2 We have Ç12 [g((), 2or by the definition (Eq. and can get the final lower bound:
2
(m - ming, m(az) (maxa, m(az)
m)
(28)
[
S + 2M + 2 2 (M² - 12
9ra
B MACO: MULTI-AGENT COORDINATION BENCHMARK
In this paper, we study how to learn context-aware sparse coordination graphs. For this purpose, we propose a new Multi-Agent COordination (MACO) benchmark (Table I to evaluate different implementations and benchmark method. This benchmark collects classic coordination problems in the literature of cooperative multi-agent learning, increases their difficulty, and classifies them into different types. We describe the detailed settings of tasks in the MACO benchmark.
14

---

Published as a conference paper at ICLR 2022
B.1 TASK SETTINGS
Factored Games are characterized by clear factorization of global rewards. We further classify factored games into 4 categories according to whether coordination dependency is pairwise and whether the underlying coordination graph is dynamic (Table D.
Aloha (Oliehoek (2010), also similar to the Broadcast Channel benchmark problem proposed by Hansen et al. (2004)) consists of 10 islands, each equipped with a radio tower to transmit messages to its residents. Each island has backlog of messages that it needs to send, and agents can choose to send one message or not at each timestep. Due to the proximity of islands, communications from adjacent islands interfere. This means that when two neighboring agents attempt to send simultaneously, a collision occurs and the messages have to be resent. Each island starts with 1 package in its backlog. At each timestep, with probability 0.6 new packet arrives if the maximum backlog (set to 5) has not been reached. Each agent observes its position and the number of packages in its backlog. global reward of 0.1 received by the system for each successful transmission, while punishment of - 10 is induced if the transmission leads to a collision.
Pursuit, also called Predator and Prey, is classic coordination problem (Benda 1986 Stone & Veloso 20000 [Snn et al. 2019). In this game, ten agents (predators) roam 10 X 10 map populated with 5 random walking preys for 50 environment steps. Based on the partial observation of any adjacent prey and other predators, agents choose to move in four directions, keep motionless, or catch prey (specified by its id). One prey is captured if two agents catch it simultancously, after which the catching agents and the prey are removed from the map, resulting in team reward of 1. However, if only one agent tries to catch the prey. the prey would not be captured and the agents will be punished. The difficulty of Pursuit is largely decided by the relative scale of the punishment compared to the catching reward (Böhmer et al. 2020), because a large punishment exacerbates the relative overgeneralization pathology. In the MACO benchmark,
consider challenging version of Pursuit by setting the punishment to 1, which is the same as the reward obtained by a successful catch.
Hal Away (Wang et al. 2020) is multi-chain Dec-POMDP whose stochasticity and partial observ- ability lead fulloodeco value functions learning sub-optimal strategies. the MACO bench- mark, we increase the difficulty of Hallway by introducing more agents and grouping them (Fig. ( One agent randomly spawns a state in each chain. Agents can observe its own position and choose to move left, move right, or keep still at each timestep. Agents win if they arrive at state y simultane- ously with other agents in the same group. In Fig. (6 different groups are drawn in different colors. Each winning group induces a global reward of 1. Other- wise, if any agent arrives at g earlier than others, the sys- tem receives reward and all agents in that group would be removed from the game. If ny > 1 groups attempt move to g at the same timestep, they keep motionless and agents receive a global punishment of -0.5 mlg The mar, 4 10 to avoid an infinite loop,
horizon is where 4 is the length of chain i.
Figure 6: Task Hallway WWagg et al. 2020). To increase the difficulty of the game, we consider a multi- -roup ver- sion. Different colors represent different groups.
Sensor (Fig. 3 in the main text) has been extensively studied in cooperative multi-agent learning (Lesser et al.) 2012, Zhang & Lesser 2011). We consider 15 sensors arranged in a 3 by 5 matrix. Each sensor is controlled by an agent and can sean the eight nearby points. Each scan induces a cost of -1, and agents can choose noop to save the cost. Three targets wander randomly in the gird. If k > sensors scan target simultaneously, the system gets a constant reward of 3, which is independent of the number of sensor. Agents observe the id and position of targets nearby.
non-ffctored games do not present an explicit decomposition of global rewards. We classify non- factored games according whether the game can be solved by a static (sparse) coordination graph in single episode.
Gather is an extension of the Climb Game (Wei & Luke 2016). In Climb Game, each agent has three actions: A = {an, a1 a2 ). Action ag yields no reward only some agents choose it. but a high reward if all choose it. The other two actions are sub-optimal actions but can induce positive reward
15

---

Published as a conference paper at ICLR 2022
Full
Rand.
Brox
Our
Bar
7041 TolSmhooe
40
10
0.0
0.5
1.0 (m/
1.5
2.0
0.0
0.5
125
15
2.0
0.0
3.5
1.5
135
2.0
Figure 8: Performance different implementations on Aloha. Different colors indicate different topologies. Performance of different losses is shown in different sub-figures.
without requiring precise coordination:
10
# n,
r(a)
0
< #oo n,
(29)
5
otherwise.
We increase the difficulty of this game by making it temporally extended and introducing stochasticity, We consider three actions. Actions are no longer atomic, and agents need to learn policies to realize these actions by navigating to goals 91, 92 and 93 (Fig. 7
Moreover, for each episode, one of 91, 92 and is randomly selected as the optimal goal (corresponding to ag in Eq, (9). Agents spawn randomly, and only agents initialized near the optimal goal know which goal optimal, Agents need to simultancously arrive at goal state to get any reward. If all
Q
4g
4
Qg
91
b
92
6
93
agents are at the optimal goal state, they get high reward of 10. If all of them are other goal states, they would be rewarded 5. The minimum reward would be received if only some agents gather the optimal goal. We further increase the difficulty by setting this reward to 5. It is worth noting that, for any single episode, Gather can be solved using a static and sparse coordination graph for example, agents can collectively coordinate with an agent who knows the optimal goal.
C2
C5
Figure 7: Task Gather. To increase the difficulty of this game, we con- sider temporally extended version and introduce stochasticity.
Full
Rand.
Bruse
Qur
Bar
5.0
Prrt Cought
4.5
4.0
0.9
3.0
2.0
0.5
0.0
1.0
2.0
T 1m00
To0li
(mill
Figure 9: Performance of different implementations on Pursuit. Different colors indicate different topologies. Performance of different losses is shown in different sub-figures.
Full
Rand.
Brisc
quar
Sar
100
100
100
75
75
75
50
50
50
0.2
0.4
1.0
0.0
0.5
0.6
0.4
(ml0
Tomll
T(mill
Figure 10: Performance of different implementations on Hallway. Different colors indicate different topologies. Performance of different losses is shown in different sub-figures.
16

---

Published as a conference paper at ICLR 2022
Full
Rand
Brxx
Our
Bar
30
20
Test
0.0
0.1
0.2
3.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
(m/)
Figure 11: Performance of different implementations on Sensor. Different colors indicate different topologies. Performance of different losses is shown in different figuuigures.
Full
Rand.
6reas
Our
6
100
100
75
75
75
TestWi
Test Win
50
50
0.2
1.0
[ml0
T (mii
T(mil)
Figure 12: Performance of different implementations on Gather. Different colors indicate different topologies. Performance of different losses shown in different sub-figures.
Disperse consists of 12 agents, At each timestep, agents choose to work at one of 4 hospitals by selecting action in A = {ao, a1, 02, 03). At timestep hospital j needs x/ agents for the next timestep. One hospital randomly selected and its æ/ is a positive number, while the need of other hospitals is 0. If vi+1 < of agents go to the selected hospital, the whole team would be punished v441 z/. Agents observe the local hospital's 's id and its need for the next timestep.
B.2 OTHER POSSIBLE IMPLEMENTS AND PERFORMANCE COMPARISON
With this benchmark in hand, we are now able to evaluate our method for constructing sparse graphs. We compare method with the following approaches.
Maximum utility difference (or q₁) is the expected utility agent (or j) can get without the awareness of actions of other agents. After specifying the action of agent the joint expected utility changes to Vij- Thus the measurement
max boy Tiji a:z)]
(30)
can describe the mutual influence between agent and j. Here
8Tg(Tiy,at) a.,) qu (TY any) qe(Te a.) (T,,,
(31)
the utility difference function.
We use a maximization operator here because two agents need to coordinate with each other if such coordination significantly affects the probability of selecting at least one action pair.
Variance of utility difference As discussed before, the value of utility difference dy and variance of payoff functions can measure the mutual influence between agent and j. In this way, the variance of d.j serves as a second-order measurement, and we can use
max Vara, (Tiy a,
(32)
to rank the necessity of coordination relationships between agents. Again we use the maximization operation base the measurement the most influenced action.
For these three measurements (Eq. g 30 and 32), the larger value of Çij is, the more important the maxa; Vara, (Ter(Tij aij)] is large, the expected utility of
edge (i,j) is. For example, when
17

---

Published as a conference paper at ICLR 2022
Full
Rand.
Brox
Our
Bar
TG2 Rctur
0.0
0.2
0.4
0.5
0.0
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
5.6
0.5
1.0
(mm)
(mi))
[mmil)
Figure 13: Performance different implementations on Disperse. Different colors indicate different topologies. Performance of different losses is shown in different sub-figures.
agent i fluctuates dramatically with the action of agent j. and they need coordinate their actions. Therefore, with these measurements, to learn sparse coordination graphs, we can set a sparseness controlling constant À E (0, 1) and select {|V)((V] - 1) edges with the largest Gij values. To make the measurements more accurate in edge selection, we minimize the following losses for the two measurements, respectively:
ΣΣ ai:as
(Te) aty)l;
(33)
sparse
PKIVI - 1)1412
sparse
ΣΣU Vara, (Tg) a.y)]
(34)
V 1)
We scale these losses with factor Asparse and optimize them together with the TD loss. It worth noting that these measurements and losses are not independent. For example, minimizing sparse would also reduce the variance of qiy. Thus, the next section, we consider all possible combinations between these measurements and losses.
Observation- Based Approaches In partial observable environments, agents sometimes need to coordinate with each other to share their observations and reduce their uncertainty about the true state (Wang al. 2020). We can build our coordination graphs according this intuition.
Agents use an attention model (Vaswani et al. (017) to select the information they need. Specifically, we train fully connected networks S& and I and estimate the importance of agent j's observations to agent i by:
Ozj = (TTT))Faa())))
(35)
Then calculate the global Q function
Qs,i(s, a) = IV Σ a((T..a)) + Easgs Cang)isTTi,,C aiy),
(36)
where Cij = /0 Eijg e0 Then both fs and fq can be trained end-to-end with the standard
TD loss. When building coordination graphs, given sparseness controlling factor X, we select X|VI(V>- - edges with the largest ōıj values.
B.3 WHICH METHOD IS BETTER FOR LEARNING DYNAMICALLY SPARSE COORDINATION GRAPHS?
We show the learning curves of value-based implementations Fig. 8 13 and compare our method (C). & Clprre) against the (attentional) abservation-basee method in Fig. 14 We can see that our proposed method generally performs better than the observation- based method, except for the task Disperse. Compared to other games, observations provided by Disperse can reveal all the game information. In this case, the observation-bar based method can make better use of local observations and can easily learn an accurate coordination graph.
C THE SMAC BENCHMARK
On the SMAC benchmark, we compare our method against fully decomposed value function learning methods (VDN (Sunehag al. 2018) & QMIX (Rashid et al. 2018)) and deep coordination graph
18

---

Published as a conference paper at ICLR 2022
Cier Altn.
Aloha
Pursult
Hallway
Paromkoe
50
Prst Cought
100
50
Tea
25
1.5
0.5
0.2
0.4
1.0
(m8)
Trril)
7m0m0
Sensor
Gathar
Disporse
20
Capturees
Teal Syturm
15
0.0
3.1
0.2
3.4
0.5
5.0
0.2
0.4
6.6
0.8
1.5
0.0
0.2
0.4
0.5
0.8
3.0
(m)))
T(e00)
T0ml0
Figure
Performance comparison between our method (S2) & Loparse) and the (attentional) observation-based approach on the MACO benchmark.
learning method (DCG (Böhmer al. 2020
Experiments carried out hard map 5m, 6m and a super hard map MMM2. For the baselines, we use the code provided by the authors and their default hyper-parameteer parameters settings that have been fine-tuned that both our method and all the considered baselines are implemented based on the open-sourced codebase PyMARI which further guarantees the fairness of the comparisons.
the SMAC benchmark. We also notice
D ACTION REPRESENTATION LEARNING
O
Predictions
As discussed in Sec. 3.3 of the main text, we use action repre- sentations to reduce the influence of utility difference function's estimation eтrors on graph structure learning. In this section, we describe the details of action representation learning (the related network structure is shown in Fig. 15). We use the technique proposed by Wang et al. (2021b) and learn an action encoder fe(:; 02): RIA > Rdd parameterized by te, map one-hot actions to a dd-dimensional representation space. With encoder, each action a has a latent representation zas i.e., Fa Se (a; ).). The representation =n is then used to predict the next observation of and the global reward r, given the cur- rent observation o, of an agent and the one-hot actions of other agents, a-i- This model is a forward model, which is trained by minimizing the following loss:
M
M
Action Representation
Action
M Encoder
(o., a_,)
aj One-Hot
Fully-Connected Network
Vector
Legand
(Ber E.i,,..,'')>
Σ
[|po oz, a.)) o'11
Figure 15: Framework for learning action representations, reproduced from Wang et al. (2021b).
+ Am Σ (pr,,a, Ui, a.)) - rr)3],
(37)
where Po and p. is the predictor for observations and rewards, respectively. We use to denote the parameters of p. and pr- Ar is a scaling factor, 'D is replay buffer, and the sum is carried out over all agents.
In the beginning, we collect samples and train the predictive model shown in Fig. 15 for 50K timesteps. Then policy learning begins and action representations are kept fixed during training. Since tasks in the MACO benchmark typically do not involve many actions, we do not use action representations when benchmarking our method. In contrast, StarCraft II micromanagement tasks usually have large action space. For example, the map MMM2 involves 16 actions, and a conventional deep Q-network requires 256 output heads for learning utility difference. Therefore, we equip our
19

---

Published as a conference paper at ICLR 2022
method with action representations to estimate the utility difference function when testing it on the SMAC benchmark.
E ARCHITECTURE, HYPERPARAMETERS, INFRASTRUCTURE, AND TIME COMPLEXITY
In CASEC, each agent has a neural network to estimate its local utility. The local utility network consists of three layers-a conneccon layer, 64 bit GRU, and another fully-connected layer- and outputs an estimated utility for each action. The utility difference function is also a 3-layer network, with the first two layers shared with the local utility function to process local action- observation history. The input to the third layer (a fully-connected layer) is the concatenation of the output of two agents' GRU layer. The local utilities and pairwise utility differences are summed to estimate the global action value (Eq. 11 in the paper).
For all experiments, the optimization conducted using RMSprop with a learning rate of 10-4, of 0.99, RMSProp epsilon of 0,00001, and with no momentum or weight decay. For exploration, we use e-greedy with annealed linearly from 1.0 0.05 over 50K time steps and kept constant for the rest of the training. Batches of 32 episodes are sampled from the replay buffer. The default iteration number of the Max-Sum algorithm is set number of agents and the task, and we set it to 0.3 on the map 5m_vs_ 6m and 0.35 on the map MMM2. We test the performance with different values (1e-3, 1e-4, and 5--5) of the scaling weight of the sparseness loss Cy Pursuit, and set it le-4 for both the MACO and SMAC benehmark. The whole framework is trained end-to-end on fully unrolled episodes. All experiments on StarCraft Il use the default reward and observation settings of the SMAC benchmark.
The communication threshold depends on the
All the experiments are carried out on NVIDIA Tesla P100 GPU. We show the estimated running time of our method different tasks in Table and 4 Typically, CASEC can finish 1M training steps within 8 hours on MACO tasks and in about 10 hours on SMAC tasks. In Table we compare the computational complexity of action selection for CASEC and DCG, which is the bottleneck of both algorithms. CASEC is slightly faster than DCG by virtue of graph sparsity.
Table 3: Approximate running time of CASEC tasks from the MACO benchmark.
Aloha
Pursuit
Hallway
Sensor
Gather
Disperse
13h (2M)
17h (2M)
7h (1M)
4.5h (0.5M)
6.5h (1M) 8h (IM)
Table 4: Approximate running time of CASEC on tasks from the SMAC benchmark.
5m_ 6m
MMM2
18h (2M)
21h (2M)
Table 5: Average time (millisecond) for 1000 action selection phases of CASEC/DCG. CASEC uses graph with sparseness 0.2 while DCG uses the full graph. To ensure a fair comparison, both Max-Sum/Max- algorithms pass messages for 8 iterations. The batch size set to 10.
5 actions
10 actions
15 actions
5 agents
2.90/3.11
3.15/3.39
3,42/3.67
10 agents
3.17/3.45
3.82/4.20
5.05/5.27
15 agents
3.41/3.67
5.14/5.4
7.75/8.02
F INFLUENCE OF CYCLES ON MAX-SUM
One limitation of our method is that we cannot guarantee cycle-free coordination graphs. Running Max-Sum on loopy graphs (graph that contains loops) may lead to sub-optimal actions being selected. In this section, we investigate the influence of cycles the optimality of Max-Sum algorithm.
20

---

Published as a conference paper at ICLR 2022
Specifically, we first compare the results of Max-Sum against optimal joint actions Aloha from the MACO benchmark. To this end, we sample 1000 Aloha configurations. We then run Max-Sum under different sparseness degrees (with guarantee of cycle-free graphs) and compare with optimal joint actions. Since finding the optimal action NP-hard, we use brute-force method and enumerate all possible joint actions and choose the one with the largest tot value.
Petnts 1025, stante 2. C994
nbs 1200 Ditbene 138.27
Alcha
750
1008
240
2
200
2-7
333
-55
Ouc 92tmmal
Ogl optmal
Communccaten thresho
Figure 16: Compare actions selected by Max-Sum and the optimal joint action on 1000 different configurations of Aloha. Left: On sparse graphs with 20% edges. Qioe values of the actions are shown. Middle: On full graphs. Qtor values of the actions are shown. Right: How many actions selected by Max-Sum are optimal under different sparseness degrees.
Agorta Trredhatte 22 Poatii 1003 Ditweeee 1.22
Agorowe3: Th--hed-11. di Jehtis D.ttacee 2.4)
Random
Adbins estimaatt 12
4300
8.700
200
3200 2040
644 05
07
32
10
Our optmal
Our optial
Communcation threahold
Figure 17: Compare actions selected by Max-Sum and the optimal joint action on 1000 random configurations. Left: On sparse graphs with 10% edges. Quat values of the actions are shown. Middle: On full graphs. Qtor values of the actions are shown. Right: How many actions selected by Max-Sum are optimal under different sparseness degrees.
Results are shown in Fig. 16 We can see that Max-Sum on sparse graphs selects optimal actions in around 95% of the cases. Quor values are also satisfactory, with most points falling near the line = x. In comparison, the quality of Max-Sum solutions decreases significantly on full graphs, as shown in Fig. middle and right.
We further investigate the case of random graphs. 1000 graphs are generated randomly with utility and payoff values conforming to a Gaussian distribution with a mean of and variance of 10, and we carry out experiments similar to those on Aloha. As shown in Fig. 17 we find that Max-Sum on both sparse and full graphs can select more than 95% optimal actions. The optimization objective, Qior, is also very close to the optimal value.
We can conclude that, although it can not guarantee optimality consistently, Max-Sum on sparse graphs select the optimal action with a large probability on the tested cases. In comparison, optimal actions are less likely to be selected on full graphs. This may shed light on why CASEC can outperform DCG on some tasks. For future work, we plan to investigate how to learn cycle-free sparse coordination graphs so that action optimality can be guaranteed.
G EMPIRICAL EVALUATION OF THE BOUND IN EQ. 5
To figure how loose the bound Eq. 5 is, we randomly generate 10000 graphs, select the edge between agent 0 and 1, and put them into 100 bins according to the value of Cover, In each bin, we calculate the number of graphs where the actions of agent 0 and I selected by Max-Sum keep unchanged after removing the edge between them. Also for each bin, average the bound in Equation each graph instance. Then, in Fig, [8] we compare our bound against the frequency of unchanged actions. We observe that, on average, the bound is 36.9% lower than the real frequency.
21

---

Published as a conference paper at ICLR 2022
Propesition
Unchangs
3:15
0.00
520
5.50
Figure 18: Comparison between the bound in Proposition and the probability in real cases.
CASCC
D0G
CASEC
DOG
120
40
Test Transmitzes
Test SCSSSarre ne
80
60
20
20
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.0
0.1
0.2
0.3
0.4
03
[mill
T(mmll
Figure 19: Comparison between CASEC and DCG on Aloha (Left) and Sensor (Right) with two times number of agents.
H TASKS WITH A LARGER NUMBER OF AGENTS
Intuitively, sparse graphs are expected perform better in tasks with more agents. In this section, compare CASEC with DCG on large version of Aloha and Sensor.
The new version of Aloha has 20 agents in Fig. left. We can see that DCG can no longer send any messages, but CASEC can send about 110 of them. For Sensor, there 30 sensors and targets. Results are shown in Fig. right. We can see that DCG does not learn to scan any targets, while CASEC can capture about 40 of them. The gap between sparse and full coordination graphs more significant on these tasks.
10 array. We compare CASEC against DCG in
I DECIDE SPARSENESS ADAPTIVELY
A limitation of our method is that we fix the communication threshold when training. In this section, we study how to select the threshold adaptively and investigate the following two methods.
The first method is based the observation that the performance of sparse graphs would degrade dramatically when the sparseness degree is below a certain value. To find this value, during testing, we check the performance of graphs with different sparseness degrees and select the degree below which the performance would drop. We change the threshold every 50K, 150K, and 200K training timesteps and show the performance in Fig. 20 (the first row). We see that training with such an adaptive threshold performs similarly with the original CASEC algorithm after convergence and learns slightly better during the initial learning stage. The found threshold smaller than the one that we get through grid search.
The second method is based on Proposition π The intuition is that we can cut off the edges which exert limited influence on Max-Sum. Specifically, during testing, we count the number of edges that lead to different Max-Sum results with probability smaller than 0.36 after being removed. The percentage of these edges is set as the communication threshold. Again, every 50K, 150K, and 200K training timesteps. The results are shown in Fig. 20 (the second row). This second method leads to higher final performance but learns slower initially. The adaptive threshold less stable compared to the first method, and the selected thresholds are larger than the hand-crafted one.
change the threshold
22

---

Published as a conference paper at ICLR 2022
Orginal Senzer
Sparsanca Acup: 2005
Original
Sparseness Adapt
Sparseness Adapt Interval 50K
Sparseness Adapt Interval 5KK
0.29
0.10
0.05
0.0
02
0.5
T (mil
[k]
Acape
Original
Sparseness Adapt Interve bok
Sparseness Adept interval 15
25
Text Scanned
Thresheld
0.2
0.0
0.1
0.2
0.3
300
350
400
400
500
T (mill
[k]
Figure 20: Learning curves (Left) and the changing process (Right) of the communication threshold of the two methods proposed in Appendix
For future work, it is an important question how to develop more principled methods that can find the minimum communication threshold which can guarantee learning performance.
sdges
Figure 21: Performance of DCG on Sensor with different numbers of edges in the coordination graph.
23


Reviews:
[{"review_id": "qyREzNdDgit", "reviewer": "Reviewer_Y1rR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "### Pros\n\n- The problem is relevant;\n- MACO benchmark is a valuable contribution to the community;\n- Empirical results are good.\n- Proposition 1 is an interesting addition to the paper (I did not check the proof).\n\n### Cons\n\n- The paper talks about \"intensive and inefficient\" message passing, however, it is unclear if a sparser graph leads to wall clock time reductions due to batching using GPUs.\n- The paper hypothesises why CASEC outperforms DCG, however, it would merit a deeper analysis of the question. Personally, I think that this is the most interesting/important finding of the paper that sparsifying the graph leads to such performance improvements.\n- The paper misses relevant work: Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning, AAMAS 2021 that use attention and graph networks to learn context-dependent coordination graphs doing an evaluation on SMAC as well.\n\n### Questions/Comments\n\n- Can you provide wallclock time comparison between DCG your method? It would be interesting to see how sparsifying the graph affects the real computation time.\n- Can you provide the range of the fraction in Equation 5? I'd like to get a bit more intuition on about how loose the bound is.\n- Is the result in Figure 2 consistent on different runs? Do all the seeds demonstrate this behaviour?\n- The negative space in Figure 3 is just too large.\n- \"These results prove that our method can distinguish the most important edges\". This statement is too strong, I don't think that empirical results can prove anything.\n- The second paragraph on page 7 is an interesting analysis of DCG, this is a great find!\n- Can you provide intuition on why DCG>CASEC on Pursuit?\n- Can you include DCG in the TD error plot in Fig 5c?\n- Why do you think there is a drop in performance for threshold = 0.5 in Figure 4 for Gather?", "summary_of_the_paper": "The paper proposes to use the variance of the payoffs functions to learn dynamic coordination graphs, i.e. coordination graphs that might change in structure at each time step of the rollout. The empirical evaluation is carried out on a newly proposed MACO benchmark as well as some levels from the Starcraft II SMAC benchmark.", "summary_of_the_review": "I reviewed this paper before, and the authors improved the manuscript and the paper reads much more nicely now. Empirical results are good, and the authors hypothesise on why this or that experiment went that way. \n\nHowever, I give it a 5 (marginally below the threshold) due to the fact that the authors decided not to include the related work that the reviewers suggested, e.g. Deep Implicit Coordination Graphs for Multi-agent RL by Li et al. I am willing to increase the score if:\n* authors provide a legitimate reason for not including relevant work into this submission, and\n* include the relevant work and compare to it / explain why such comparison is not meaningful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UFpva-ko5mv", "reviewer": "Reviewer_pXtp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "\n**Strengths**\n\nEarlier works incorporating coordination graphs in the function approximation case which either are limited to static coordination graphs (like DCG) or were learning a \"soft\" version of fully connected coordination graph [1] (with graph neural network based action inference). In comparison, the current work provides a novel alternative for the problem of coordination graph learning. While the paper doesn't mention it, the payoff variance based edge selection method might be an interesting case for resolving some of the future work mentioned in [2]. In a sense the MCTS setting might be a better test because it would resolve the chicken and egg problem that comes from trying to learn the payoff functions and can avoid the need for action encoders with auxiliary losses to stabilize learning. The paper has an expansive set of experiments with fair number of agents. \n\n**Weaknesses**\n\nWorks like [1] should be mentioned in related work. While there are some ablations, so it's not a big weakness, but it would be useful to know for example whether the action encoder trick helps say qmix or other value factorization methods. I would expect sparsity to help even more in larger number of agent environments and it would be great if MACO allows to quickly evaluate that.\n\n[1] Navid Naderializadeh, Fan H. Hung, Sean Soleyman, Deepak Khosla. \"Graph Convolutional Value Decomposition in Multi-Agent Reinforcement Learning\". arXiv:2010.04740\n\n[2] Shushman Choudhury, Jayesh K Gupta, Peter Morales, Mykel J Kochenderfer. \"Scalable Anytime Planning for Multi-Agent MDPs\". AAMAS 2021.", "summary_of_the_paper": "The paper focuses on the problem of cooperative multi-agent Reinforcement learning and proposes a novel way to learn the dynamic (state dependent) coordination graph for the joint action selection from factorized joint value representations. The key idea here is to use the variance in payoff function estimates can be a good indicator for whether a coordination graph edge should be present or not. However, given the deep RL goal is learn these payoff functions there is a cyclic dependency between errors from payoff estimation and coordination graph estimation. The paper therefore also proposes an alternative action representation scheme that helps mitigate some of these problems. The paper evaluates the proposed approach on many classic coordination problems as well as subset of SMAC benchmark tasks.", "summary_of_the_review": "Overall it's a very interesting paper and would recommend acceptance just for the new variance based metric for coordination edge selection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MIgRFihvlQ", "reviewer": "Reviewer_7Rh6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Overall speaking, I found the paper interesting to read and easy to follow. In comparison with existing literature on in cooperative multi-agent learning, I'm convinced that, the approach proposed this paper indeed adds valuable extensions in multiple dimensions and it would be quite beneficial to the research community in this area. As far as I know, the technique proposed in this paper is novel, and the demonstrated results of this proposed method/technique seem to be encouraging and promising. The presented MACO benchmark in this paper can also be valuable addition to the research community in this area, and the empirical evaluation of the proposed method v.s. existing SOTA methods on MACO benchmark and StarCraft II micromanagement benchmark, also provides some reasonable justification and illustration of the superior performance of the proposed new method.\n\nThe two major limitations of the proposed approach (also already pointed out by the authors in the conclusions section), especially about the first one about no guarantee of cycle-free graph and thus might select sub-optional actions, is a bit concerning, and it would be valuable if the authors could provide some more comprehensive study on this limitation and evaluate more accurately how severe this limitation is (based on the current write-up, we are not fully clear how severe this limitation would be for general scenarios) . We want to avoid the case that the good numbers and examples in the experimental section are specially hand-crafted or carefully selected in a way to minimize the impact of this limitation of no cycle-free guarantee and to favor the proposed methods to show off its advantages. If that study wold takes too much extra time and efforts, I won't object for acceptance of the paper based on the current available results, since I think these results already could be considered as significant contributions to this research area, and I'm ok for the authors to leave those study as future research work. But a comprehensive study about this limitation and some more justification/explanation about it would definitely makes the paper stronger.\n\n\n", "summary_of_the_paper": "In this paper, the authors study how to learn dynamic sparse coordination graphs, which is a long-standing problem in cooperative MARL. In particular, they propose a novel deep method that learns context-aware sparse coordination graphs adaptive to the dynamic coordination requirements, and evaluate the proposed method against existing methods on MACO benchmark, as well as StarCraft II micromanagement benchmark.", "summary_of_the_review": "The paper is well-written and seems to be of significant contribution to this research area. There are some limitations that are a bit concerning and it would be significantly better if the authors could provide more comprehensive study and explanations on those main limitations, but if not possible due to time limitation, I won't object for acceptance of the paper based on the current results and leave those potential improvements as future research work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Jxjwg5Vz7sr", "reviewer": "Reviewer_gGhv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "**POSITIVE**\n\nThe paper is well written and the presented ideas are novel and interesting. The choice of scoring function for the edges is well motivated (although the reviewer was not able to follow the entire proof). In particular in the StarCraft II tasks the method shows a clear advantage over DCG.\n\n**NEGATIVE**\n\n(1) The analysis of Sensor is nice, but the benchmark seems to use the wrong evaluation metric. As the reward is linear in the number of agents that scan a target (as long as they are more than 2), the task does not specify whether it is better to scan few targets with many agents or many targets with few agents. All evaluation graphs (except Fig.1, middle) focus on the number of scanned targets, though, which is not optimized for. The fact that CASEC scans more targets than DCG does not mean anything, the fact that it collects more reward does. Moreover the conclusion \"the gap between return and the number of scanned targets is larger without the sparseness loss\" is somewhat weird, as adding the loss increases reward, but decreases scanned targets. The authors must address this issue. The reviewer recommends to clip the reward at 3 for 2 or more agents scanning the same target to get rid of this ambiguity and ensure all algorithms optimize the right metric.\n\n(2) The authors claim \"Intuitively, agent $i$ needs to coordinate its action selection with agent $j$ if agent $j$'s action exerts significant influence on the expected utility of agent $i$.\" However, an edge may also be important if agent $i$ needs access to the joint histories $\\tau_{ij}$ to properly evaluate an action, similar to the \"non-decentralizable task\" in the DCG paper. Ideally the authors would disentangle this dependency in an additional experiment, but the possibility should at least be mentioned. \n\n(3) The flat performance of DCG in the middle plot of Figure 1 is curious, as DCG seems to outperform CASEC (in terms of reward) for very few edges. Does this hold for no edges left as well? The authors comment this with \"only the individual utility function contributes to action selection\". Does this indicate that all payoff functions learned by DCG barely contribute, and wouldn't that mean they have almost zero variance? Shouldn't CASEC learn this kind of behavior first, as it is explicitly regularized towards it? \n\n(4) There is no incentive for CASEC to use the utility functions, as only the payoffs' variances are punished. The network could therefore absorb the utilities into the payoffs. The authors could add a second regularization term that prevents this, e.g., a norm loss on the payoffs outputs with a very small regularization constant. \n\n**DETAILS**\n\n- The space of histories must be $T \\equiv (\\Omega \\times A)^* \\times \\Omega$\n- \"and $q$ represents utility or payoff functions.\": define clearer that $q$ is the (weighted) sum of all utility and payoff functions that condition on actions $a_g$.\n- Mention where to find the proof of Proposition 1 in the main text.\n- Why not use double-Q-learning in (eq.7)?\n- Use $|\\mathcal V|$ instead of $n$ in (eq.8) for consistency. \n- You should explicitly mention that you train a fully connected graph, but perform action selection on the sparse graph.\n- \"and 2) accelerating the training of payoff function between target network updates to reduce the estimation errors.\" is unclear. This is about action representation. Say so.\n- In the Sensor description of p.5: $k \\geq 2$\n- Mention in 6.2 whether you use the sparsity constants from 6.1\n- \"DCG outperforms CASEC on Hallway\" is not significant\n- CASEC reduces the representational capacity of DCG, which can explain why it learns faster, but you cannot argue that the CASEC solution is \"beyond the representational capacity of the network\" (p.8) of DCG.\n- What is a \"utility difference function\" (p.9)?\n- Mention the potential convergence issues earlier, e.g. p.3.\n\n** POST-REBUTTAL **\nThe author's rebuttal incorporated this reviewers suggestion and the results appear much cleaner thanks to this. The discussion has convinced this reviewer that the paper should be accepted. The score has therefore be raised to 8. ", "summary_of_the_paper": "The paper introduces a technique called CASEC to train deep coordination graphs with sparse connectivity and a dynamic method to remove a fixed number of edges during inference. The latter removes edges in order of smallest variance of the corresponding payoff functions, which the authors motivate with a theoretical statement on the probability of changing the optimal action after removing an edge. CASEC is evaluated on a novel benchmark suit (MACO) for coordination dilemmas and StarCraft II micromanagement tasks. The proposed methods outperforms the baseline (DCG) in 2 out of 6 MACO tasks and shows in particular a clear advantage of the used action encoding method in StarCraft II.  ", "summary_of_the_review": "The introduced method is novel and relevant. Although the reviewer was not able to follow the entire proof, the edge selection seems well motivated. Experiments are sometimes weirdly evaluated, but clear enough to say that in some cases using sparse graphs is an advantage. The reviewer would have liked to see more intuition when this is the case though.\n\nIn summary, this is a good paper that merits publication. The reviewer would consider increasing the score if the authors fix point (1) or convincingly explain why number of scanned targets is the correct evaluation metric. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers found that the paper offers interesting contributions for multi-agent RL and favour acceptance of the paper. The strengths of the paper are summarized below:
- Good algorithmic contribution
- Offers a new set of benchmark tasks for coordination in MARL settings
- Exhaustive experiments on complex tasks with a reasonable number of agents
- All the issues raised by the reviewers (missing references, missing discussion of limitations...) have been satisfactorliy addressed.

I therefore join the reviewers in the recommendation to accept the paper.
Decision: Accept (Spotlight)