Learning Structured Communication for Multi-agent Reinforcement Learning
Authors: Junjie Sheng
Xiangfeng Wang
Bo Jin
Junchi Yan
Wenhao Li
Tsung-Hui Chang
Jun Wang
Hongyuan Zha
Venue:  (2020)
Keywords: Learning to communicate
Multi-agent reinforcement learning
Hierarchical communication network

Abstract: Learning to cooperate is crucial for many practical large-scale multi-agent applications. In this work, we consider an important collaborative task, in which agents learn to efﬁciently communicate with each other under a multi-agent reinforcement learning (MARL) setting. Despite the fact that there has been a number of existing works along this line, achieving global cooperation at scale is still challenging. In particular, most of the existing algorithms suffer from issues such as scalability and high communication complexity, in the sense that when the agent population is large, it can be difﬁcult to extract effective information for high-performance MARL. In contrast, the proposed algorithmic framework, termed Learning Structured Communication (LSC), is not only scalable but also communication high-qualitative (learning efﬁcient). The key idea is to allow the agents to dynamically learn a hierarchical communication structure, while under such a structure the graph neural network (GNN) is used to efﬁciently extract useful information to be exchanged between the neighboring agents. A number of new techniques are proposed to tightly integrate the communication structure learning, GNN optimization and MARL tasks. Extensive experiments are performed to demonstrate that, the proposed LSC framework enjoys high communication efﬁciency, scalability and global cooperation capability.

Under review as a conference paper at ICLR 2020
LEARNING STRUCTURED COMMUNICATION FOR MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Learning to cooperate is crucial for many practical large-scale multi- aagent applica- tions. In this work, we consider an important collaborative task, which agents learn to efficiently communicate with each other under multi-agent reinforce- ment learning (MARL) setting. Despite the fact that there has been a number of existing works along this line, achieving global cooperation at scale is still chal- lenging. In particular, most of the existing algorithms suffer from issues such as scalability and high communication complexity, in the sense that when the agent population is large, it can be difficult to extract effective information for high- performance MARL. In contrast, the proposed algorithmic framework, termed Learning Structured Communication (LSC), is not only scalable but also learns efficiently. The key idea is to allow the agents dynamically learn a hierarchical communication structure, while under such a structure the graph neural network (GNN) is used efficiently extract useful information be exchanged between the neighboring agents. A number of new techniques are proposed to tightly integrate the communication structure learning. GNN optimization and MARL tasks. Extensive experiments are performed to demonstrate that, the proposed LSC framework enjoys high communication efficiency, scalability, and global co- operation capability.
INTRODUCTION
Reinforcement learning (RL. has achieved remarkable success in solving single-agent sequential de- cision problems under interactive and complicated environments, such as games (Mnih et al. 2015] Silver et al. (016) and robotics (Lillicrap et al.) 2016). In many real world applications such as intelligent transportation systems (Adler & Blue, 2002) and unmanned systems(Semsar- Kazerooni - & Khorasani 2009), not only one, but usually large number of agents involved in the learn- ing tasks. Such a setting naturally leads to the popular multi-agent reinforcement learning (MARL) problems, where the key research challenges include how to design scalable and efficient learning schemes under an unstationary environment (caused by partial observation and/or the dynamics of other agents' policies), with large and/or dynamic problem dimension, and complicated and uncer- tain relationship between agents.
Learning to communicate among agents has been regarded an effective manner to strengthen the inter-agent collaboration and ultimately improve the quality of policies learned by MARL. Various communication-base. MARL algorithms have been devised recently, e.g., DIAL Foerster et al. 2016), CommNet (Sukhbaatar et al.) 2016). ATOC (Jiang & Lu 2018), IC3Net (Singh et al. 2019) and TarMAC (Das et al., 2019). These schemes aim to improve the inter-agent collaboration by learning communication strategy to exchange information between agents. However, there are still two bottlenecks unresolved, especially when faced a large number of agents.
One bottleneck lies in that achieving effective communication and global collaboration is difficult with limited resources, such as narrow communication bandwidth and energy. particular, DIAL and TarMAC require each agent to communicate with all the other agents, i.e., fully-connected communication network (Figure [()),, which is not feasible for large scale scenarios with geograph- ically apart agents. CommNet and IC3 assume coordinating the global collaboration of agents, which again does not allow large scale scenarios with long range communications. ATOC introduces interesting attention scheme build tree
network (Figure ((b)) with central node

---

Under review as a conference paper at ICLR 2020
Sep1
3kpp
(a) Fully-connected (h) Star
(c) Tree
(d) Hierarchical
Figure I: Topology of different communication structures and LSC falls into the hierarchical one.
While the tree network can be scaled, global collaboration has to be realized through inefficient multi-hop and sequential communications. a word, improper communication topologies will limit the cooperation ability in large scale scenarios.
communication network (Figure I(c)..
Another bottleneck is the difficulty of extracting essential information to exchange between agents for achieving reg-pperformacc MARI,, especially when the number of agents grows. Most of the existing works simply concatenate, take the mean or use the LSTM to extract information to be exchanged. First two lack in considering the inter-relationship between agents, and LSTM assumes that there is a fixed sequence of message passing between agents, that is, the relationship between agents is predefined. Recently, TarMAC utilized attention scheme to aggregate messages by considering the relationship from each agent to all others. However, the improper communication topology still hinders the information extraction. The communication structure needs to be jointly designed with the information extraction scheme to achieve further improved learning performance.
Normal Nodee
Cantral Nodee
Target
Tamm now conteer
Townrt
Keep my rolc
be cont al
communiiottoo and
(Downgrace
Intial Step
Weight Generation on
Establishing Structure
Weight Generation
Re-estab Structure
Figure 2: Procedure for dynamically establishing structured communication network. Left: Each agent determines its communication importance weight based on partial local observation. For in- stance, the agent "G" finds the target (red square), then it will be possible get a higher weight "4" and become the central. Right: The importance weight generation step and network construction step will be repeated iteratively. After communication and action procedures, agents will generate their new communication importance weights, and determine to keep or change their roles respec- tively. Further, the structured communication network will be re-established.
To address the above two issues, we propose a novel structured communication based algorithm, called learning structured communication (LSC).. Our LSC combines a structured communication network module and a communication- based policy module, which aims to establish a scalable hier- archically structured network and information exchange scheme for large scale MARL. In particular, a hierarchically structured communication network (Figure [(d) is dynamically learned based on local partial observations of agents. In the hierarchically structured network, all agents are grouped into clusters, where global collaboration can be achieved via intra-group and inter-group communi- cations. In contrast to the other three types in Figure [ the proposed hierarchical communication network is more flexible and scalable, with fewer resources needed to achieve long-range and global collaboration.
The procedure to establish such a hierarchically structured communication network is shown in Figure 2 To better utilize the relationship between agents given the hierarchically structured communication network and obtain more effective information extraction, graph neural network (GNN) (Scarselli et al. 2008 is employed. In GNN, each communication step involves informa- tion embedding and aggregation. Benefiting from the unordered aggregation power and the dynamic graph adaptability of GNN, the proposed LSC algorithm can extract valuable information effectively. The GNN-based information extraction procedure is depicted in Figure
2

---

Under review as a conference paper at ICLR 2020
Normal Nodes
Central Nodes
Local infos
Cluster infos
Intra-Group Aggregation
Inter-Group Sharing
Intra-Group Sharing
Global infos
Figure 3: GNN-based communication extraction procedure. Each node denotes an agent. The edge embedding be considered as the communication message. The network learning procedure prop- erly fits the communication procedure, and effectively learn valuable messages involving the global network structure and agents relationship. Left: Low-level normal agents transfer their local valu- able embeddings to the associated central agents. Middle: High-level central agents communicate with each other to gain sense of global perception. Right: All central agents broadcast embedding information to their normal agents to form global cooperation.
This paper is devoted to the learning of communication structure among agents. To our knowledge, this is the first work of hierarchical structured learning to communication for MARL. allows to learn communication structure adaptively instead of using predefined forms. Specifically:
i) To improve scalability for a large number of agents, a hierarchical structure is devised that divides the agents into higher-level central agents and sub-level normal ones. As such, the communication network is sparsified. While it still allows for more effective global cooperation via message passing among the central agents, compared with the star/tree structures.
ii) For effective communication and global cooperation, the message representation learning is deeply integrated into the information aggregating and permeating through the network, via graph neural network (GNN), which is a natural combination with the hierarchical communication struc- ture.
iii) Extensive experiments on both MAgent and StarCraft2 show our approach achieves state-of-the- art scalability and effectiveness on large-scale MARL problems.
RELATED WORK AND PRELIMINARIES
Many multi-agent reinforcement learning algorithms without communication in the inference pro- cedure have experienced fast development. Recent works like MADDPG (Lowe et al. 2017). QMIX (Rashid et al. 2018), COMA (Foerster et al. 2018) and MAAC (Igbal & Sha]2019) adopt centralized training and decentralized implementing framework. All agents' local observations and actions are considered to improve the learning stability. These algorithms are generally not suitable for large-scale case due to explosive growing number of agents.
Communication-basel MARI algorithms have been showed effective for large-scale agent cooper- ation. Earlier works assume that all agents need to communicate with each other. DIAL (Foerster cet al. 2016) learns to communication through back pookppropggtiing all other agents' gradients to the message generator network. Similarly, CommNet (Sukhbaatar et al, 2016) sends all agents' hidden states to the shared communication channel and further learns the message based the average of all other hidden states. MFRL (Yang et al.] 2018) approximates the influence of other agents by averaging the actions of surrounding neighbor agents, which could mitigate the dimensional disaster for large-scale cases. However, this can be considered as a predefined communication pattern, which unable to adapt to complex large-scale scenarios. Communication between all agents will lead to high communication complexity and difficulty of useful information extraction. DGN (Jiang et al.) 2018) employs graph convolution network (GCN) to extract relationships between agents which could result in better collaboration. However, it considers all agents equivalently and assumes the communication of each agent has to involve all neighbor agents which limits to adapt to more prac- environments. IC3Net (Singh et al. 2019) uses communication gate to
tical bandwidth-limine decide whether to communicate with the center, but adopt the same star structure like CommNet which requires high bandwidth and can hard to extract valuable information with only center. ATOC (Jiagg & Lu (018) and TarMAC (Das et al. 2019) introduce the attention mechanism to determine when communicate and whom communicate with, respectively. TarMAC focuses
3

---

Under review as a conference paper at ICLR 2020
more message aggregation rather than the communication structure. SchedNet (Kim al. 2019) aims to learn a weight- scheduler to determine the communication sequence and priority. From the perspective of employing GNN into MARL, MAGNet (Malysheva et al. 2018) that utilizes relevance graph representation of the environment and a message passing mechanism to help agents learning. However, it requires heuristic rules to establish the graph which is hard to achieve in com- plex environments. RFM (Tacchetti et al. 2019) use graph to represent the relationship between different entities, aiming to provide interpretable representations.
Before the main method, we introduce some preliminaries to facilitate the presentation. Partial Observable Stochastic Games. stochastic games, agents learn policies by maximizing their cumulative rewards through interacting with the environment and other agents. The partial ob- servable stochastic games (POSG) can be characterized as a tuple (I, 50 O,P.P.Pee R) where denotes the set of agents indexed from 1 to nı; S denotes the finite set of states; 6a represents the initial state distribution and A denotes the set of joint actions. A, is the action space of agent a = (a1. : an) denotes a joint action; O denotes the joint observations and O, is the observation space for agent i, distribution with P ( s, a) as the probability of state transit to 5 and result after taking action a. (o(o) is the Markovian observation emission probability function. R S x A + R" means the reward function for agents. The overall task of the MARL problem can solved by properly objective function modeling, which also indicates the relationship among agents, e.g., cooperation, competition or mixed.
(o1:">0u 0n) denotes joint observation; P denotes the Markovian transition
Graph Neural Network. Graph neural network (GNN) (Scarselli et al. 2008 is deep embedding framework to handle graph-based data on a graph 9 = E). V, denotes the node feature vector for node e E V (for N, nodes), ex denotes the edge feature vector for edge e& (for Ne edges) with Tk, be the receiver and sender of edge eg respectively. The vector u denotes the global feature. The graph network framework in (Battaglia et al. 2018) is employed, which divides computation on graph data to several blocks to gain flexible processing ability. Each block introduces the aggregation and embedding functions to handle graph data. There are many variants of GNN, like message- passing neural network (Gilmer et al. 2017) and non local neural networks (Wang et al. 2018). By treating every agent as a node and each communication message exchanging as the edge a graph, the observations and messages as the attributes of nodes and edges, respectively. The whole communication process can be formulated to a graph neural network. The relationships among agents can be effectively extracted to enable efficient communication message learning.
Independent Deep Q-Learning, Deep Q-Network (DQN) (Mnih et al.) 2015) is popular in deep reinforcement learning, which is one of the few RL algorithms applicable for large-scale MARL. In each step. each agent observes state s and takes an action a based on policy π. It receives reward r and next state 5 from environment. To maximize the cumulative reward R = E. DQN learns the action-value function Q** = BewP,anx(a [Ress 8, 8, = a) by minimizing C()) = I,,,,,, à [V - Qss, a; 0)]. where ū = r + y max; Q (s, ā; 0). The agent follows e-greedy policy, that is, selects the action that maximizes the Q-value with probability 1-c or randomly. The Independent Deep Q-Learning (IDQN) (Tampuu et al.) (017) is an extension of DQN by ignoring the influence of other agents for multi-agent case. Every agent learns a Q-function Q"(u" (s; 8*) based on its own observation and received reward.
Our algorithm employs DQN as the basic RI. algorithm based on the following two considera- tions: 1) our algorithm is dedicated to discuss the learning communication mechanism in large- scaleMARL scenarios, as a result we can choose a concise and effective basic RL algorithm like thewell-known DQN; 2) data collection in large-scale MARL environments is extremely ineffi- ciently,while DQN has excellent data efficiency as an offline RL algorithm.
LSC: LEARNING STRUCTURED COMMUNICATION
Our communication architecture has two key modules: structured communication network module and communication-busee policy module, shown in Figure 4 The first module aims to establish the dynamic hierarchical structured communication network in a distributed fashion, while the second module contains the GNN-based communication extraction and Q-network components. Without loss of generality, we use DQN as the basic reinforcement algorithm, however our approach can incorporate any value-based or actor-critic methods. The details of LSC is depicted in Algorithm
4

---

Under review as a conference paper at ICLR 2020
M/4
W/s
CGRP Aigorthm
Normall Agents
Generator
1/2
Central Agunit
Stuctardd Communactioo Networ: Nocile
Brad ent Arrew
Ippu/OOuputt
Offemeniaaile Modale
G-Net
duiing
Nar-Ciflanmnaabl Modide
CHS4 lasee Cormunaation
Figure 4: Algorithm framework of LSC with Structured Communication Network Module and Communication- based Policy Module, where &;, Oj, 0; and w; denote state (global perception), observation, action and importance weight of agent i. The former module uses partial observation to establish the communication structure. The latter employs GNN-based communication and Q- Network to extract communication content and produces collaboration policies respectively based on established communication structure.
Algorithm LSC: Learning Structured Communication
Initialization: weight generator parameters 0", Q-net parameters 02, GNN parameters 69mn target Q-net parameters 8 replay buffer R = Ø, group radius d, the number of agents n:;
2:
for Episode ..... M do
3: Reset = O, global state st and observation of for each agent i, Normal agents set n (all agents) and Vo Ø;
4:
for t = 1, 7 and s; * terminal do for each agent do With probability pick random action w else w! arg (ax Q0"(o5)
5:
6:
7:
Get current position POSs each agent i;
8:
(Ve n1 e1 8) = CBRP(( Vx-1 ) ",(", w (POSS), ... POSS d);
9:
(gi,-.. 2 HCOMMO V E);
10:
for each agent do
11:
With probability pick random action of else choose the action that has the largest value in the vector df:
12:
13:
Execute global actions and get global reward rf next state s++1 next observation ot+1;
14:
Get updated position POSs. f+1 for each agent ;; Store (s', o², (POSS ... POSS a² r", ot+1, (POSs)+1 POSS s(+1) to R;
15:
for 1, K do
17:
Sample random mini-batch transitions from R:
Update weight generator 6" by minimizing Eq. T
19:
Update communication based policy module (0 pmnn) by minimizing Eq.
20:
Update the target networks through Eq. (3)
Specifically, the CBRP function automatically and distributively establishes the structured com- munication network based on the learnt importance weights. The HCOMM function denotes the communication-based policy module, which outputs the Q-values based the GNN-based com- munication messages. Both CBRP and HCOMM are discussed in the following subsections, and the details of CBRP and HCOMM can be found in Appendix.
3.1 STRUCTURED COMMUNICATION NETWORK MODULE
The structured communication network module takes the role of establishing a hierarchical struc- tured communication network which will be employed communication-batt Two sub-modules included, i..., the weight generator and the Cluster Based Routing Protocol (CBRP). The weight generator sub-module aims to determine the importance weight for each agent automatically. It is modeled through neural network f (ug 0 w, where the weight mea-
policy module.
5

---

Under review as a conference paper at ICLR 2020
sure the confidence of agent to become center. Further, the CBRP sub-module employs the weights of all agents {w,} } to construct the hierarchical structured communication network. To em- phasize, the CBRP sub-module can be implemented in distributed fashion, result, the central agents can be elected distributedly. This advantage ensures the practicability for large-scale case.
The CBRP method (Rezaee & Yaghmaee 2009) is typical method for establishing hierarchical routing structure. The key idea for CBRP is that each agent will check whether central agent or agent that has larger weight exists in its receptive area. The agent will become a central agent if above agent is found, else it will keep its own role. With enough checking steps, each agent will either be an central agent or in some central agents' receptive. All agents can be separated into several groups with each central agent as the group leader. The overall hierarchical structured communication network further will be established by fully connecting all central agents from different groups and connecting the agents in each group to their central agent.
There is a strong connection between these two modules in LSC algorithm. Different generated weights will lead to different hierarchical structured communication network, which would cause diverse performance of the communication- firmed that the weights have great influence on the performance, which motivates us to train these two modules end-to-end. However the CBRP uub-module is not differentiable, which means the gra- dients cannot be back anok-propdgated from communication based policy module to the weight generator sub-module. Therefore, we introduce another RI. task as an auxiliary, i.e., each agent takes its weight as action by treating the communication- based policy module an extra unobservable part of the environment and receiving the same reward as the main RL task in the communication-bon -basd policy module discussed below. Moreover the weight w is constrained in the integer set {0, 1, 4). The action space becomes discrete, as a result DQN algorithm can be used again to train the weight gen- erator. At this time, the weight generator can be regarded as a Q-value function. The loss ((0") for the weight generator sub-module becomes clear as follows, with yi = + max., Qa (ō,, 20:) r, denotes the reward received for agent i from enyironment.
policy. Some experiment results also have con-
f(0%)) = Eo,w.ro
(Q (o,, w:) - -y:) 31
(I)
1=1
3.2 COMMUNICATION- POLICY MODULE
After the structured communication network topology is determined, the communication-basse pol- icy module will learn the communication content and generate the final global collaboration policy. The communication-basel policy module consists of two sub-modules, i.e., GNN-based commu- nication sub-module and the Q-Net sub-module. The first one aims to learn the communication messages and further update overall state perception, while the other sub-module learns the policy based on the new state perceptions after efficient communication. Different from many existing works (Foerster et al.) 2016 Das et al., 2019, [Singh et al., 2019), the agents play differently in the GNN-base communication sub-module. Central agents should guarantee high-level information and dominate the agents in their driven groups respectively. The hope is that such a structure can ensure the effectiveness of communication and the efficiency of intra-group and inter-group collaboration.
Recall Figure 3] the well-established hierarchical structured communication network can be repre- sented by a tuple (V,E) while the edges are directed. The node set V contains No nodes which can be divided into the central node set Ve and the normal node set Vn. For central node i E Ve, the node feature vector includes the embedding feature uf, the central role feature ef and the global feature uf:: for normal node E Vn. the node feature vector e; only includes the embedding feature o/- For each edge (i + j) E E with i.j V. the edge feature vector is denoted as eij- Functions and p denote the update embedding function and aggregate function respectively. As shown in Figure 3 the overall GNN-based communication sub-module consists of three steps, and the GNN operation is detailed in Table I and as follows:
Step 1: Intra-group aggregation. In each group, the normal agent embeds their local information and sends it to the associated central agent j Ve; the central agent aggregates the information from all associated normal agents and updates its central role feature:
Step 2: Inter-group sharing. The central agent communicates with the other central agent with cluster information, further aggregates the received and indicates the global perception:
Step 3: Intra-group sharing. The central agent communicates all its feature with the associated normal agents while the normal agent aggregates the received information from central agents. Both the embedding feature of central and normal agents will be updated.

---

Under review as a conference paper at ICLR 2020
Table 1: GNN-based Communication Architecture
Type
Edge (i E) 1 1E V..
Edge Update Schome
Node Update Schome OEE 27)
Step group aggregation
By div E, plyy (o-))
Step inter-group sharing
iEV.JEV
6 ole 6 Aleen vicel
Step intra-group sharing
VVV.V
60 OL. C. Ml (agges)
Table 2: Comparison of different MARL algorithms for communication efficiency.
Algorithm
DIAL.
CommNet
IC3
ATOC
LSC
Nmsg
((n²)
((n)
(n)
O(kb)
O kb)
Natep
O(1)
O(1)
O(1)
O(d)
O(1)
Nar
O(n)
(mm)
((n)
O(b)
O ((maax(b (b, b:)
The GNN-based communication sub-module modeled as a GNN (Soonn with parameter (gan, while the following Q-Net of agent (Qza) is parameterized by shared parameter 8 The gradient can be back propagated from Q-Net to the graph neural network, as a result the overall loss of communication based policy module is as follows:
E(BO, ggmn) = E.,a.r
Σ
as) 3)²
where y/ = Ti + 7 maxa, Qao (fooma - (ō), āz). denotes the reward received for agent from environment. Some softly updating scheme is further employed update target network, i.e.,
0 = - + (1 7 and ggün 703m + -))0sán
Here we discuss communication efficiency from three aspects: the number of message exchanging (Nmsg) among agents; the number of steps during the communication procedure (Nstep): the com- munication bandwidth and range requirements for each agent (N&.),, and n is the total number of agents. The details about communication efficiency are presented Table 2 for each stage of the MARL algorithms. For DIAL, each agent communicates with all other agents based on the fully- connected network, which results in Onn)) message exchanging complexity. DIAL need only one communication step, however the communication bandwidth and range requirement for each agent high and in the order of On)). Different from DIAL, CommNet and IC3 both employ the star communication network,
result the number of message exchanging is in the order of (()). Nstep and N are the same as DIAL.. The communication complexity of ATOC and our proposed LSC depends on the number of groups (denoted k < n, which automatically determined in the algorithms) and the maximum output degree of the communication network (denoted as 6 < n). For ATOC, the communication network tree-type, so that only need exchange Okk) mes- sages. However, the number of steps is larger for ATOC for its sequential property and is in the order of (d) (d denotes the depth of the communication network). Nr., will become much smaller to be (bb) because communication happens in groups. Furthermore for our LSC, the number of message exchanging is bit larger than ATOC due to the communication among all elected centers, i..., O + kb). However the depth of the hierarchical communication network is only two which results in (1) communication steps, while No., is in the order of O(max(b, k)). Overall, our LSC algorithm has advantage in the communication efficiency.
4 EXPERIMENTS
We compare LSC with state-of-the-art MARL methods in two large-scale battle environments, i.e., the grid world platform MAgent (Zheng et al., 2017) and StarCraft2 (Samvelyan et al.) 2019). to evaluate their performances from aspects of both network structure and communication.
4.1 LARGE SCALE BATTLE GAME IN MAGENT
Settings. In MAgent battle, agents fighting against enemies in 40 x 40 grid world. Each agent only receives its local observation, acts independently and cooperatively. and further gains its reward. The goal for each agent is attack its enemies and prevent them from being attacked. Each agent
7

---

Under review as a conference paper at ICLR 2020
Upoccs
Agam number
Massgge zom
(d) Message norm Figure 5: Reward of algorithms and message pattern visualization in the MAgent environment.
(a) Average reward (b) Total testing reward
(c) Message distribution
from both sides has a 6 x 6 visual field and can attack its 8 adjacent grids. The speed, attack power and health point for each agent are 1, and 4, which are increased to and 10 for the enemy to increase the difficulty. The reward is +5 for successfully attacking an enemy, -2 for being killed and -0.01 for attacking a blank grid.
Baselines. To evaluate the effects of communication scheme, three peer methods on learning to communicate for MARL, i.e., CommNet, IC3 and ATOC, are chosen to compete with our pro- posed LSC. Considering the weakness of mean aggregation, we replace the aggregation function of CommNet and IC3 with GNN which is same as LSC. The group radius is 6, the same as the visual field, in ATOC and LSC. All communication messages are embedded to 3-dimension vectors for cost-effectiveness. Besides, two MARL methods with no communication, i.c., IDQN and MFQ are also compared, since they are widely used in large-scale environments. In MAgent, the policy of enemy is pretrained by IDQN.
Policy performance. Figure[5(a) and Table show the overall performances of compared algorithm in a 64 vs. 64 battle. The learning curves in (igure(5(a)pprt present the average reward of different agents by epoch. LSC achieves better rewards quickly after 700 epochs and finally converges an obvious higher point (about 1.15) than baselines. Table Jndd Table 4 give quantitative comparisons of these methods. Each algorithm is given 50 trials with well-trained model. Mean-reward, Newu, Nieadd Rotioga in Table denote the mean of average final rewards of agents, the number of killed enemies and dead agents, and the ratio Naat / /Ndead, respectively. Following Figure 5(a) LSC can obtain a better mean reward stably, with a 30% performance advantage at least. New are similar, because all approaches fulfill the mission, and beat the pre-trained IDQN. It is achieved by LSC with the least casualty, i.e., the smallest Neead and the highest Ratioga. Table gives the comparisons in terms of the number of epochs to achieve the same reward value from 0.7 to 1.2 within maximal 1750 epochs in the training procedure. One can see that LSC needs fewer epochs to achieve the same reward compared with all the other algorithms, while more reward can be guaranteed within the maximal epochs. These results indicate that LSC can promote collaboration and cooperation, and produce superior policies.
Communication effectiveness. As observed from the blue and orange curves in Figure ((a) and the first and fifth columns in Table 3 that LSC outperforms IDQN greatly. Since IDQN is the special case of LSC without communication procedure, this phenomenon demonstrates the usefulness of our proposed communication solution. Meanwhile, it can be noted that LSC also surpasses other MARL. with communication algorithms, which is the consequence of its advanced structure. As mentioned in our experiments, CommNet and IC3 adopt the same message dimension and the same aggregation function as LSC, which leads to better performances than the original versions. However, the star structure makes the center node need process all agents' information in CommNet and IC3. When the agent number increases, the message extraction could be difficult. Thus, the final performances cannot be compared with the LSC. For ATOC in large scale environments, the message needs to jump multiple times between local circles, and multiple information aggregation and extraction bring in approximation error, which results in policy deterioration.
Scalability. Figure 5(b) shows the total reward curves of team by the agent number (10-99). Espe- cially when the team has 99 agents, the reward of LSC is 1.45-2.75 times of other methods. It can be seen that the structured communication of LSC confers superior performances at different scales, because it utilizes the divide-and-com -on-ouuue strategy to automatically group local agents and aggregate centers. In Figure ((b) When the agent number is less than 80, the communication between agents can help to learn policy, so the orange dashed line is almost bellow other lines. When the number is more than 80, the demand of star-style information processing exceed the ability of aggregation
8

---

Under review as a conference paper at ICLR 2020
Table 3: Performance comparisons in terms of average mean-reward, numbers and ratio of kills and
death (64 vs. 64 agents, in 50 testing trials). The bold stands for the best result in each row.
LSC
CommNet
IC3
ATOC
IDQN
MFQ
Mean-reward
1.11
0.86
0.93
0.58
0.8
0.83
Nau
62.6
61.3
62.48
61.46
62.1
62
Ndead 28.9
31.64
32.0
51.42
32.3
31.4
Rationa
2.16
1.93
1.95
1.20
1.92
1.97
Table 4: Comparisons on the used epoch number to achieve same reward of the training procedure in the MAgent environment.
Reward
LSCC
CommNet
IC3
ATOC
IDQN
MFQ
0.7
769
1199
787
933
1133
1254
828
1292
935
1151
1460
1304
0.9
1051
1525
1508
1471
1426
1.0
1271
1588
1506
1413
1619
1.2
1704
aa) Initial state
(b) Encircle
(c) Fire focusing
(d) LSC
(e) CommNet
(f) IC3
(g) ATOC
(h) IDQN
(i) MFQ
Figure 6: Behavior illustration. The first row shows two typical behavior by LSC. the second row, the top and bottom plot denote the early state and the near to final battle state, respectively.
network, thus CommNet and IC3 are inferior to IDQN. For ATOC, the jump of message becomes the bottleneck as the agent number increases, as inspected in the analysis above. To sum up, the experiments indicate LSC obviously has better scalability than the bascline.
Message visualization. To analyze the communication messages learned by GNN, we execute LSCC with its well-trained policy 50 times, and visualize the 3 dimensional vector sent by central nodes in Figure Observing Figure ((d)aadd (dd) after receiving messages, the majority of agents choose to move, and the minority choose atluck. This means that agents in LSC is very positive to adjust the team formation and then cooperate to attack. It is worthy to notice that most messages have a small norm (less than 10), and the norm of large proportion is around O. From the aspect of optimization, the redundant messages with larger norm will bring in more noise to other agents. In this way, LSC minimizes the impact of redundant messages on the final performance. This similar phenomenon that central nodes is nearly silent in many cases, is also mentioned by CommNet (Sukhbaatar et al.) 2016). Therefore, the message representation module via the GNN-based communication module can generate meaningful and efficient messages theoretically and empirically.
Behavior pattern. Here, we demonstrate the battle tactics evolved for MARL via structured com- munication. To analyzed the globally cooperation strategy of LSC, visualize the progress of the

---

Under review as a conference paper at ICLR 2020
battle. For fairness, start six algorithms from the same state in Figure ((a) The typical behavior patterns learnt by LSC are presented in the figures of the first row. Via the intra-group communi- encirelement to nearby red enemies; the team has a local numerical superiority, and focus agents' fire to wipe out enemies, denoted by the black attack arows in Figure 6(c) These show the intra-group cooperation of LSC.. Upper figures in the second row of Figure shows the situation of early stage (17 steps) after ini- tialization for six methods, and lower figures show the states after 50 steps. From these results, we may arrive conclusion that the team with our LSC can beat the opponent more quickly with more aggressive policy. By groupp and inter-group collaboration, Figure ((d) LSC has carried out encircling and fire-focusing many times, and achieves an enormous advantage within only 17 steps, and wipe out the enemies within 50 steps. For both IDQN and MFQ, agents tend to cooperate within their visual range, and once the agents get separated out of visual range, they can hardly form global cooperation, which lead to the failure result in Figure 6(h) and 6(1 Similarly, agents controlled by ATOC communicate only among group range, thus they encounter similar situations. Agents for CommNet and IC3 have global communication, however once some agents get far away from the central agents, central agents
cation and cooperation, in Figure 6[b] the blue team (LSC) organizes
hardly understand their messages, making ineffective cooperation. As Figure 6(e) and 6()) some agents get far away from the majority of agents, thus their results are not ideal. To sum up, in Figure ((d) agents controlled by LSC form a global encircle strategy by communication in both intra-group and inter-group thus LSC-based agents can wipe out enemies faster than the baselines.
4.2 LARGE SCALE BATTLE GAME STARCRAFT2
Battle game in StarCraft2 is confrontation between two marine teams shown in appendix, which much more complex than MAgent. Specifically, we use a 25 vs. 25 map, i... 25m, where the range vision is and the map size is 1920 x 1200. To evaluate the cooperation, agents one team are controlled by the individual learned policy. Here, we compare our LSC with IQDN, Commnet and IC3. The action space consists of movement
adjacent grid and shooting with the range 6. We adopt the same dense reward setting (0.44 for killing an enemy, 8.9 for winning the battle) as SMAC (Samvelyan et al. 2019). Agents of the enemy are controlled by the built-in game Al.
LSC outperforms compared algorithms, where the blue reward curve is much higher than others. Although the agent number (25) is fewer than MAgent, the observation and action space of StarCraft2 are much larger, leading to the difficulty learn policy. Therefore, the performance of IDQN and MFQ degrades notably in this complex environment, while LSC, IC3, CommNet and ATOC outperform it. This is because they entail com- munication to facilitate cooperation. Moreover, LSC out- performs IC3, CommNet and ATOC. This demonstrates that flexible hierarchical communication and expressive GNN-based message extraction make LSC more quali- fied for complex tasks than CommNet and IC3's star-style communication.
In Figure 7
Average reward
LSC
IDQN
CommNet
IC3Net
100000
20000C
302000 Epochs
400800
500930
Figure 7: Reward curves on StarCraft2
CONCLUSION AND FUTURE WORK
In this paper, a novel learning structured communication (LSC) algorithm is proposed for multi- agent reinforcement learning. The hierarchical structure is self-learned by cluster based routing protocol. The communication message representation is naturally embedded and extracted via graph neural network. Experiments in large-scale games (MAgent and StarCraft2) demonstrated that our LSCC can outperform existing leariing-tocoommmiice
algorithms with better communication efficiency, cooperation capability, and scalability. In the future, we will improve LSC by considering some practical constraints, such as communication bandwidth and delay.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jeffrey L Adler and Victor J Blue. A cooperative multi-agent transportation management and route guidance system. Transportation Research Part C: Emerging Technologies, 10(5-6):433 454, 2002.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro GonzzlzZ Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. TarMAC: Targeted multi-agent communication. In ICML, pp. 1538-1546 2019.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. NewrlPS, pp. 2137-2145, 2016.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, pp. 2974-2982, 2018.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, pp. 1263-12177 1272, 2017.
Shariq Iqbal and Fei Sha. Actor-attention-critie for multi-agent reinforcement learning. JCML, pp. 2961-2970, 2019.
Jiechuan Jiang and Zongqing Lu, Learning attentional communication for multi-agent cooperation. In NeurlPS, pp. 7254-7264, 2018.
Jiechuan Jiang, Chen Dun, and Zongqing Lu. Graph convolutional reinforcement learning for multi- agent cooperation. ArXiv, abs/1810.09202, 2018
Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning to schedule communication in multi-agent reinforcement learning. In ICLR, 2019.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In ICLR, 2016.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperatiee-compettiive environments. In NeurlPS, pp. 6379-6390, 2017.
Aleksandra Malysheva, Tegg Taekyong Sung, Chae-Bong Sohn, Daniel Kudenko, and Aleksei Sh- pilman. Deep multi-agent reinforcement learning with relevance graphs, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin A Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane I Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540))529 533, 2015.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In ICML,, pp. 4292-4301, 2018. 2018.
M Rezaee and M Yaghmaee. Cluster based routing protocol for mobile ad hoc networks. INFO- COMP, 8(1):30-36, 2009.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung. Philiph H. S. Torr, Jakob Foerster, and Shimon Whiteson. The CtafCraft Multi-Agent Challenge. CoRR, abs/1 2019.

---

Under review as a conference paper at ICLR 2020
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Elham Kazeroina and Khashayar Khorasani. Multi-agent team cooperation: A game theory approach. Automatica, 45(10):205--2133, 2009.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Joannis Antonoglou, Veda Panneershelvam,, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, January 2016.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. In ICLR, 2019.
Sainbayar Sukhbaatar, Rob Fergus, al. Learning multiagent communication with backpropaga- tion. In NeurlPS, pp. 2244-2252, 2016.
Andrea Tacchetti, H. Francis Song. Pedro A. M. Mediano, Vinicius Zambaldi, János Kramár, Neil C. Rabinowitz, Thore Graepel, Matthew Botviniek, and Peter W. Battaglia. Relational forward mod- cls for multi-agent learning. In International Conference Learning Representations, 2019.
URL Tetttp:://pperrviiee net http://ppaariieee..ee...orraaaap toJ
Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. PLOS ONE, 12(4):1-15, 2017.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In CVPR, pp. 7794-7803, 2018
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In ICML, pp. 5571-5580, 2018.
Lianmin Zheng, Jiacheng Yang. Han Cai, Ming Zhou, Weinan Zhang, and Yong Yu. MAgent: A many-agent reinforcement learning platform for artificial collective intelligence. In AAAI, pp. 8222-8223, 2017.
12

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1 CBRP ALGORITHM AND HCOMM ALGORITHM
Algorithm 2 CBRP: Cluster Based Routing Protocol
1: function CBRP(()*. ("] w², J. {POSS] POSS }. d)
2: Define neighbours are distance < d, T. is constant to control the max-waiting time, = 2
is the undecided nodes set and 3 = 2;
3: Each node broadcast its weight w to neighbours;
4: for i is in central node set V/6 do
Maintain the structure if there is central nodes in neighbours and its weight is bigger than agent then
5:
6:
Pop node i from Vi2 and append it to V":
7:
for normal nodes set V and no central node is in its neighbour do Vi;
8:
Pop node i from V and append for in Vu concurrently do
9:
Elect central nodes
10:
if does not receive larger weight for T. then append i to Va and broadcast to neighbours; else
11:
12:
13:
Wait for the signal from central node for 27:; if received signal from central node then append to V.
14:
15:
else
17:
append i to Ve:
18:
for in V do
generate communication link
19:
for j in V and j is neighbouring do append egy and ejt 0 to for j in Va do append Ety E; Return (1%, VL, E)
20:
21:
23:
A.2 DETAILS AND DISCUSSIONS OF ALL HYPERPARAMETERS
For both MAgent and StarCraft2 environments, the details of all hyperparameters used for ap- proaches are summarized in the following Table S and Table 6 All common hyperparameters of all approaches the message dimension to 64 in both enviroments. For the reason that if the dimension of messages set to be 3 as other algorithms, the necessary GRU embedding in ATOC leads to failure while 64 seems to be robust.
set to be the same in the same environments. Except for the "ATOC", change
For the neural network setting in MAgent enviroment, the node encoder part all implemented with two convolutional layers with 32 filters and kernel size 3 and a ML. with 256 units. For the Q Encoder part, they are implemented with MLP(122, 64, 13). The message generators for algorithms except for ATOC are implemented with MLP(64, 32, 3) and the aggregation functions are segment sum. While for ATOC, the message generator MLP (128,, 64) and the aggregation functin i64). As for neural network setting in Stareraft2, we only tune the input and output layer to adapt to the new environment. All these settings can ensure repeatability.
A.3 BATTLE SCENARIOS OF MAGENT AND STARCRAFT2
A.4 DISCUSSIONS ON WEIGHT GENERATOR AND GROUP RADIUS
Although LSC utilize the reward feedback to establish the weight generator, which will be various with respect to different settings. To investigate the improvement brought by our learned importance weight generator, also compare with basic random weight generator (randomly chosen the central nodes and separate normal nodes into groups). As shown in Figure (a)] our learned weight generator significantly outperforms randomly. Faster convergence of our learned weight generator
13

---

Under review as a conference paper at ICLR 2020
Algorithm 3 HCOMM: Communication based Policy Module
function HCOMM( Ve, 8)
2: IIntra-grou groopgrruppp aggregation
3: for of in Vn do for x² in V. and (i + j) in & do Gij vene (v');
4:
5:
D. Generate normal to central messages Central agents aggregate received messages Generate cluster perception
6:
for Dj in V. do Ej = pl (((fs) ((-s)))))))))))
7:
vf ((E), u
8:
Inter-group sharing for új in V. do
9:
10:
for o in V. and (i j) in & do
11:
eg = o00 uP);;
D Generate central to central messages
12:
for új in V. do
13:
ej (((e)s) (3-)))E8)
Aggregate received central to central messages Obtain global perception
of o(ej, uf);
15:
Intro-group sharing for i, in V. do
16:
for vy in Vn and (i + in do
18:
Ggg = ol0 os of ex), = pl p((es))
D. Generate central to normal
messages
19:
for új Vn U.V do
20:
for in V. and (i + j) in & do
21:
= p(ess)
b Aggregate received central to normal messages
22:
"f = uf);
Update states
23:
0j Q(f));
return
Table 5: Hyperparamaters for Magent
Parameter
LSC
IDQN
MFQ
CommNet
IC3
ATOC
Episodes
1750
1750
1750
1750
1750
1750
Estart
1.0
1.0
1.0
1.0
1.0
1.0
Cend
0.01
0.01
0.01
0.01
0.01
0.01
Learning rate
le
le-
1e
le
le
1e
Max steps
400
400
400
400
400
400
dimension of messages
3
3
64
radius of communication
6
6
Table 6: Hyperparamaters for Starcraft2
Parameter
LSC
IDQN
MFQ
CommNet
IC3
ATOC
Total stops
600k
600k
600
600k
600k
600k
1.0
1.0
1.0
1.0
1.0
1.0
Cend
0.05
0.05
0.05
0.05
0.05
0.05
Learning rate
le
le
le
le
1e
le
Max steps
10000
10000
10000
10000
10000
10000
dimension messages
3
3
64
radius of communication
6
6
shows the efficiency brought by involving the reward guided weight generator. The hierarchical structured communication network guaranteed through the learned weight generator improves the communication efficiency. The higher average reward obtained by learned weight generator also shows the necessity of selecting central nodes based on the learned weight generator rather than randomly chosen.
14

---

Under review as a conference paper at ICLR 2020
reward +5 for attcack
reward -2 being killed
(a) MAgent
(b) StarCraft2
Figure 8: Battle scenarios of MAgent and StarCraft2.
Average reward
1.3
13-
Average
Weight Generator
di:12
Randem
6m60
034
2006
Epochs
Epochs
(a) Weight generator
(b) Group radius
Figure 9: Discussions on weight generator and group radius.
To better investigate the hierarchical structure, we compare our LSC algorithm with respect differ- ent group radius d, i.e., 3, 6, 12 and 60. As shown in Figure LSC with radius 6 outperform other settings. When the radius increasing, the agents can establish inter-groups cooperation easier. How- LSC with radius 60 performs worse than all the other three cases. LSC with extremely large radius will downgrade to CommNet which is not an effective way to extract valuable information.
15


Reviews:
[{"review_id": "Skx5u5fZqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper proposes a method for improving the scalability of communication-based cooperative multi-agent reinforcement learning. While existing approaches assume a fixed underlying network topology over which agents communicate, in the proposed method, this network topology is dynamic (changes at each time step) and learnable (by assigning a weight to each node and \"rewiring\" nodes in a particular way based on these weights).\n\nAuthors highlight the importance of having a topology that is roughly similar to a collection of star-topologies. The center of stars (central nodes) further form a complete graph. They argue that such a topology can achieve global cooperation while reducing the number of messages exchanged as compared to the case where all agents can communicate with each other.\n\nTo learn a dynamically changing topology, the method assigns a weight (an integer between 0 and 4) to each agent based on its local observation. An existing method (CBRP) is then used to establish connections between agents based on weights assigned to them. \n\nA graph neural network (GNN) is used for computing the messages that are exchanged among agents. Communication uses the following 3 steps: (i) agents talk to the central agent(s) to which they are connected, (ii) central agents exchange information among themselves, and (iii) central agents transmit information to the agents that are connected to them. \n\nEach agent uses a deep Q-network - the parameters of this network are shared across agents. This Q-network receives rewards from the environment. Gradients flowing through Q-network are also used to update GNN. Since CBRP is non-differentiable, the parameters for network that computes weights for all the agents are also updated using a Q-network that gets the same reward from the environment as the first Q-network.\n\nExperiments done on MAgent environment demonstrate that: (i) communication is useful and (ii) method scales well as number of agents increases. Additional qualitative studies have also been performed to understand the content of messages and the learned strategies. Authors have also experimented with the StarCraftII environment.\n\n\nComments:\nThe paper deals with an interesting problem, however, the presentation can be significantly improved as there are multiple grammatical mistakes in the manuscript. Unfortunately, the work does not position very well with the existing literature. The motivation and the impact of the contributions are not very clear. I would rate contributions as marginal. \n\nIt is not clear what POSs* terms in Algorithm 1 mean.\n\nIt would be interesting to see which agents become central agents over time. As central agents form a complete graph, if there are many central agents then the approach will be inefficient.\n\nUnder the message visualization heading on p9, it is not clear how one decides whether a message was a \"move\" message or an \"attack\" message.\n\n\nQuestions to the Authors:\n\n1. On p2, it is written that when concatenation or mean operation is used for aggregation, then inter-relationship between agents are not captured. What does this mean? Why does this problem not apply to GNN based solution which may also use mean for aggregation?\n\n2. On p10, first line, it is written that all methods were made to react to the same initial state. How was this state chosen?\n\nA few questions are also embedded in the comments above.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SkeSTs9dqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method of learning a hierarchical communication graph for improving collaborative multi-agent reinforcement learning, particularly with large numbers of agents. The method is compared to a suitable range of baseline approaches across two complex environments. The initial results presented seem promising, but further work is needed to ensure the results are reproducible and repeatable.\n\nTo enable reproducibility, please include details of all hyperparameters used for all approaches in both domains. These should include justification of how the hyperparameters were tuned. Without understanding how these values were set I cannot support acceptance.\n\nTo ensure the results are repeatable, repeated runs of training should be completed and the variation in performance quantified in the results. These repeats may have already been performed as Table 3 and Figure 5 discuss average results, but if not they must be completed before the work can be published due to the known issues with high variance in performance that commonly occur in deep RL.\n\nI would also argue against the justification of excluding ATOC from the StarCraft II experiments as its performance in MAgent with 25 agents is comparable to the other baseline methods that were tested. However, this is lower priority than the issues above provided there is no significant change in the relative performance of methods when the variance across multiple runs is documented in all existing experiments.\n\nMinor Comments:\nThe following are suggestions for improvements if the paper is accepted or for future submissions. \n\nIn Section 2, centralised critic methods are grouped as \"communication-free\" however I don't think this is the best term to explain this approach as each agent has to communicate both its observations and actions to a centralised node (e.g. COMA) or all other agents (e.g. MADDPG). I also think this section should include coverage of other methods of utilizing graph neural networks in multi-agent reinforcement learning - e.g. \"Deep Multi-Agent Reinforcement Learning with Relevance Graphs.\" Malysheva et al. Deep RL Workshop @ NeurIPS 2018 and \"Relational Forward Models for Multi-Agent Learning\" Tacchetti et al. ICLR 2019.\n\nIn Section 3, the acronyms CBRP and HCOMM are used on page 4 before they are introduced in full on page 5 for CBRP and never for HCOMM. HCOMM is also not used in Figure 4 or in the text description of the method. I believe it is the module described in Section 3.2 but this should be made clearer.\n\nMany claims in the paper are worded too strongly and should be revised. In Section 2, it is claimed that DQN \"is one of the few RL algorithms applicable for large-scale MARL\" - However, there are now many successful applications of deep RL to multi-agent systems (some of which are cited earlier in this same section) that use a variety of algorithms other than DQN. It is also claimed in this section that \"DQN has excellent sample efficiency\" despite the sample efficiency of deep RL being a known issue, open research question and a barrier to its widespread use in practice. \n\nIn Section 3.2 the authors conclude \"Overall, our LSC algorithm has advantage in the communication efficiency\" despite in the same section noting two cases where ATOC has better efficiency (N_msg and N_b-r). I would suggest removing this sentence entirely as the paragraph above already contains a balanced account of the relative merits of each approach. \n\nOn pages 8 and 9 the authors make references to guarantees and in the Appendix to proofs that are not supported by theory only empirical results. Without supporting theory these words should be avoided.\n\nThe writing is also often informal to the detriment of presenting important information clearly. Notably, on page 3 \"due to explosive growing number of agents\" and on page 4 \"The overall task of the MARL problem can be solved by properly objective function modeling.\" The second of these, particularly the word \"solved\" is also related to the issue above of using the words guarantee and prove.\n\nFinally, the paper would benefit from a thorough grammar check. I note the following issues as simple changes that can be made to improve the readability of the paper:\n- In the abstract, the sentence \"but also communication high-qualitative\" does not parse. Perhaps this could be shortened to the brackets following? i.e. \"is not only scalable but also learns efficiently.\"\n- Page 2, \"or employing the LSTM to\" -> \"or use the LSTM to\"\n- Page 2, \"still hinder the\" -> \"still hinders the\"\n- Page 2, \"the communication structure need be jointly\" -> needs to be jointly\n- Page 6, \"policy module motioned below\" -> discussed below\n- Page 10, \"the map size are is 1920x1200\" -> the map size is 1920x1200\n- Page 10, \"We do not compare with ATOC because its poor performance in MAgent\" -> because of its\n- Page 10, \"we will to improve\" -> we will improve\n- Page 10, \"practical constrains\" -> practical constraints", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1lkU_SAtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary\n\nThe authors learn structured communication patterns between multiple RL agents. Their framework uses a Structured Communication Network Module and Communication-based Policy Module. These use a hierarchical decomposition of the multi-agent system and a graph neural network that operates over the resulting abstract agent (groups). The authors evaluate on two environments, where this approach outperforms other ways to communication protocols.\n\n2. Decision (accept or reject) with one or two key reasons for this choice.\n\nWeak accept.\n\n3. Supporting arguments\n\nScalable communication with many agents will require a (learned) trade-off between structural priors and learning representations of communicaton (protocols). This work seems like an interesting step in analyzing how to implement this. \n\n4. Additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\n5. Questions", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on large-scale multi-agent reinforcement learning and proposes Learning Structured Communication (LSC) to deal issues of scale and learn sample efficiently. Reviewers are positive about the presented ideas, but note remaining limitations. In particular, the empirical validation does not lead to sufficiently novel insights, and additional analysis is needed to round out the paper.
Decision: Reject