Title: LEARNING STRUCTURED COMMUNICATION FOR MULTI-AGENT REINFORCEMENT LEARNING

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 efficiently 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 difficult to extract effective information for highperformance 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 to dynamically learn a hierarchical communication structure, while under such a structure the graph neural network (GNN) is used to efficiently 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 efficiency, scalability, and global cooperation capability.

1. INTRODUCTION:

Reinforcement learning (RL) has achieved remarkable success in solving single-agent sequential decision problems under interactive and complicated environments, such as games (Mnih et al., 2015; Silver et al., 2016) 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 a large number of agents are involved in the learning 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 uncertain relationship between agents.

Learning to communicate among agents has been regarded as an effective manner to strengthen the inter-agent collaboration and ultimately improve the quality of policies learned by MARL. Various communication-based 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. In particular, DIAL and TarMAC require each agent to communicate with all the other agents, i.e., a fully-connected communication network (Figure 1 (a)), which is not feasible for large scale scenarios with geographically apart agents. CommNet and IC3 assume a star network (Figure 1(b )) with a central node coordinating the global collaboration of agents, which again does not allow large scale scenarios with long range communications. ATOC introduces an interesting attention scheme to build a tree (a) Fully-connected (b) Star

Step 1

Step 2

Step 3

(c) Tree (d) Hierarchical . While the tree network can be scaled, global collaboration has to be realized through inefficient multi-hop and sequential communications. In a word, improper communication topologies will limit the cooperation ability in large scale scenarios.

Another bottleneck is the difficulty of extracting essential information to exchange between agents for achieving high-performance MARL, 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 an 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. For instance, the agent "G" finds the target (red square), then it will be possible to 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 respectively. 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 hierarchically structured network and information exchange scheme for large scale MARL. In particular, a hierarchically structured communication network (Figure 1(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 communications. In contrast to the other three types in Figure 1 , 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 information 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 3 . 

2. RELATED WORK AND PRELIMINARIES:

Many multi-agent reinforcement learning algorithms without communication in the inference procedure have experienced fast development. Recent works like MADDPG (Lowe et al., 2017) , QMIX (Rashid et al., 2018) , COMA (Foerster et al., 2018) and MAAC (Iqbal & Sha, 2019) adopt a 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-based MARL algorithms have been showed effective for large-scale agent cooperation. Earlier works assume that all agents need to communicate with each other. DIAL (Foerster et al., 2016) learns to communication through back-propagating 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 on 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 is 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 practical bandwidth-limited environments. IC3Net (Singh et al., 2019) uses a communication gate to 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 one center. ATOC (Jiang & Lu, 2018) and TarMAC (Das et al., 2019) introduce the attention mechanism to determine when to communicate and whom to communicate with, respectively. TarMAC focuses more on message aggregation rather than the communication structure. SchedNet (Kim et al., 2019) aims to learn a weight-based scheduler to determine the communication sequence and priority. From the perspective of employing GNN into MARL, MAGNet (Malysheva et al., 2018) that utilizes a 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 complex 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. In stochastic games, agents learn policies by maximizing their cumulative rewards through interacting with the environment and other agents. (Scarselli et al., 2008) is a deep embedding framework to handle graph-based data on a graph G = (V, E). v i denotes the node feature vector for node v i ∈ V (for N v nodes), e k denotes the edge feature vector for edge e k ∈ E (for N e edges) with r k , s k be the receiver and sender of edge e k 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 messagepassing 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 in 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 s from environment. To maximize the cumulative reward R = t r t , DQN learns the action-value function

Q π (s, a) = E s∼P,a∼π(s) [R t |s t = s, a t = a] by minimizing L(θ) = E s,a,r,s [ỹ -Q(s, a; θ)],

where ỹ = r + γ max ã Q (s, ã; θ). The agent follows -greedy policy, that is, selects the action that maximizes the Q-value with probability 1or randomly. The Independent Deep Q-Learning (IDQN) (Tampuu et al., 2017) is an extension of DQN by ignoring the influence of other agents for multi-agent case. Every agent learns a Q-function Q a (u a |s; θ a ) based on its own observation and received reward.

Our algorithm employs DQN as the basic RL algorithm based on the following two considerations: 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 inefficiently,while DQN has excellent data efficiency as an offline RL algorithm. 

for t = 1, • • • , T and s t = terminal do 5:

for each agent i do

6:

With probability pick a random action w t i else

w t i = arg max {wi} Q θ w (o t i ); 7:

Get current position POSs t i of each agent i;

8:

(V t n , V t c , E) = CBRP((V t-1 n , V t-1 c ),{w t 1 , • • • , w t n }, {POSs t 1 , • • • , POSs t n }, d); 9: {q t 1 , • • • , q t n } = HCOMM(V t n , V t c , E); 10:

for each agent i do 11:

With probability pick a random action a t i else choose the action that has the largest 12:

value in the vector q t i ;

13:

Execute global actions and get global reward r t , next state s t+1 , next observation o t+1 ; 14:

Get updated position POSs t+1 i for each agent i;

15: Store (s t , o t , {POSs t 1 , • • • , POSs t n }, a t , r t , o t+1 , {POSs t+1 1 , • • • , POSs t+1 n }, s t+1 ) to R; 16: for k = 1, • • • , K do 17:

Sample a random mini-batch transitions from R;

18:

Update weight generator θ w by minimizing Eq. ( 1); 19:

Update communication based policy module (θ Q , θ gnn ) by minimizing Eq. ( 2); 20:

Update the target networks through Eq. (3).

Specifically, the CBRP function automatically and distributively establishes the structured communication network based on the learnt importance weights. The HCOMM function denotes the communication-based policy module, which outputs the Q-values based on the GNN-based communication 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 structured communication network which will be employed in communication-based policy module. Two sub-modules are included, i.e., 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 a neural network f wg : o → w, where the weight w can mea-sure the confidence of an agent to become a center. Further, the CBRP sub-module employs the weights of all agents {w i } to construct the hierarchical structured communication network. To emphasize, the CBRP sub-module can be implemented in a distributed fashion, as a result, the central agents can be elected distributedly. This advantage ensures the practicability for large-scale case.

The CBRP method (Rezaee & Yaghmaee, 2009 ) is a typical method for establishing a hierarchical routing structure. The key idea for CBRP is that each agent will check whether central agent or agent that has larger weight w exists in its receptive area. The agent will become a central agent if no 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-based policy. Some experiment results also have confirmed that the weights have a great influence on the performance, which motivates us to train these two modules end-to-end. However the CBRP sub-module is not differentiable, which means the gradients cannot be back-propagated from communication-based policy module to the weight generator sub-module. Therefore, we introduce another RL task as an auxiliary, i.e., each agent takes its weight as an action by treating the communication-based policy module as an extra unobservable part of the environment, and receiving the same reward as the main RL task in the communication-based policy module discussed below. Moreover the weight w is constrained in the integer set {0, 1, 2, 3, 4}. The action space becomes discrete, as a result DQN algorithm can be used again to train the weight generator. At this time, the weight generator can be regarded as a Q-value function. The loss (θ w ) for the weight generator sub-module becomes clear as follows, with y i = r i + γ max wi Q θ w (õ i , wi ). r i denotes the reward received for agent i from environment.

(θ w ) = E o,w,r,õ n i=1 (Q θ w (o i , w i ) -y i ) 2 .

(1)

3.2. COMMUNICATION-BASED POLICY MODULE:

After the structured communication network topology is determined, the communication-based policy module will learn the communication content and generate the final global collaboration policy.

The communication-based policy module consists of two sub-modules, i.e., GNN-based communication 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 represented by a tuple (V, E) while the edges are directed. The node set V contains N v nodes which can be divided into the central node set V c and the normal node set V n . For central node i ∈ V c , the node feature vector v i includes the embedding feature v n i , the central role feature v c i and the global feature v g i ; for normal node i ∈ V n , the node feature vector v i only includes the embedding feature v n i . For each edge (i → j) ∈ E with i, j ∈ V, the edge feature vector is denoted as e ij . Functions φ and ρ 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 1 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 ∈ V c ; 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. 

i ∈ V n , j ∈ V c e ij = φ(v n i ), ēj = ρ({e ij } (i→j)∈E ) v c j = φ(ē j , v n j ) Step 2: inter-group sharing i ∈ V c , j ∈ V c e ij = φ(v c i , v n i ), ēj = ρ({e ij } (i→j)∈E ) v g j = φ(ē j , v n j ) Step 3: intra-group sharing i ∈ V c , j ∈ V n ∪ V c e ij = φ(v g i , v c i , v n i ), ēj = ρ({e ij } (i→j)∈E ) v n i = φ(ē i , v n i ), v n j = φ(ē j , v n j )

Table 2 : Comparison of different MARL algorithms for communication efficiency.

Algorithm DIAL CommNet IC3 ATOC LSC Nmsg O(n 2 ) O(n) O(n) O(kb) O(k 2 + kb) Nstep O(1) O(1) O(1) O(d) O(1) N b-r O(n) O(n) O(n) O(b) O(max(b, k))

The GNN-based communication sub-module is modeled as a GNN (f θ gnn ) with parameter θ gnn , while the following Q-Net of agent i (Q i θ Q ) is parameterized by shared parameter θ Q . 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:

EQUATION

where

y i = r i + γ max ãi Q i θ Q (f θ gnn (õ), ãi

). r i denotes the reward received for agent i from environment. Some softly updating scheme is further employed to update target network, i.e.,

θ Q = τ θ Q + (1 -τ )θ Q, and θ gnn = τ θ gnn + (1 -τ )θ gnn .

(3)

Here we discuss communication efficiency from three aspects: the number of message exchanging (N msg ) among agents; the number of steps during the communication procedure (N step ); the communication bandwidth and range requirements for each agent (N b-r ), and n is the total number of agents. The details about communication efficiency are presented in Table 2 for each stage of the MARL algorithms. For DIAL, each agent communicates with all other agents based on the fullyconnected network, which results in O(n 2 ) message exchanging complexity. DIAL need only one communication step, however the communication bandwidth and range requirement for each agent is high and in the order of O(n). Different from DIAL, CommNet and IC3 both employ the star communication network, as a result the number of message exchanging is in the order of O(n).

N step and N b-r are the same as DIAL. The communication complexity of ATOC and our proposed LSC depends on the number of groups (denoted as k < n, which is automatically determined in the algorithms) and the maximum output degree of the communication network (denoted as b < n).

For ATOC, the communication network it tree-type, so that it only need to exchange O(kb) messages. However, the number of steps is larger for ATOC for its sequential property and is in the order of O(d) (d denotes the depth of the communication network). N b-r will become much smaller to be O(b) because communication happens in groups. Furthermore for our LSC, the number of message exchanging is a bit larger than ATOC due to the communication among all elected centers, i.e., O(k 2 + kb). However the depth of the hierarchical communication network is only two which results in O(1) communication steps, while N b-r 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 a MAgent battle, agents fighting against enemies in a 40 × 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 to attack its enemies and prevent them from being attacked. Each agent from both sides has a 6 × 6 visual field and can attack its 8 adjacent grids. The speed, attack power and health point for each agent are 1, 1 and 4, which are increased to 2, 2 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 proposed 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.e., 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 3 show the overall performances of compared algorithm in a 64 vs. 64 battle. The learning curves in Figure 5 (a) present the average reward of different agents by epoch. LSC achieves better rewards quickly after 700 epochs and finally converges to an obvious higher point (about 1.15) than baselines. Table 3 and Table 4 give quantitative comparisons of these methods. Each algorithm is given 50 trials with its well-trained model. Mean-reward, N kill , N dead , Ratio kd in Table 3 denote the mean of average final rewards of agents, the number of killed enemies and dead agents, and the ratio N kill N dead , respectively. Following Figure 5 (a), LSC can obtain a better mean reward stably, with a 30% performance advantage at least. N kill 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 N dead and the highest Ratio kd . Table 4 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 5 (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 to 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). Especially 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-conquer strategy to automatically group local agents and aggregate centers. In Figure 5 (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 Message visualization. To analyze the communication messages learned by GNN, we execute LSC with its well-trained policy 50 times, and visualize the 3 dimensional vector sent by central nodes in Figure 5 . Observing Figure 5 (c) and 5(d), after receiving messages, the majority of agents choose to move, and the minority choose to attack. 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 a large proportion is around 0. 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 communication. To analyzed the globally cooperation strategy of LSC, we visualize the progress of the battle. For fairness, we start six algorithms from the same state in Figure 6 (a). The typical behavior patterns learnt by LSC are presented in the figures of the first row. Via the intra-group communication and cooperation, in Figure 6 (b), the blue team (LSC) organizes an encirclement to nearby red enemies; the team has a local numerical superiority, and focus agents' fire to wipe out enemies, denoted by the black attack arrows in Figure 6 (c). These show the intra-group cooperation of LSC.

Upper figures in the second row of Figure 6 shows the situation of early stage (17 steps) after initialization for six methods, and lower figures show the states after 50 steps. From these results, we may arrive a conclusion that the team with our LSC can beat the opponent more quickly with a more aggressive policy. By intra-group and inter-group collaboration, Figure 6 

4.2. LARGE SCALE BATTLE GAME IN STARCRAFT2:

Battle game in StarCraft2 is a confrontation between two marine teams shown in appendix, which is much more complex than MAgent. Specifically, we use a 25 vs. 25 map, i.e., 25m, where the range vision is 9 and the map size is 1920 × 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 to an 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 AI. In Figure 7 , 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 to 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 communication to facilitate cooperation. Moreover, LSC outperforms IC3, CommNet and ATOC. This demonstrates that flexible hierarchical communication and expressive GNN-based message extraction make LSC more qualified for complex tasks than CommNet and IC3's star-style communication. 

5. CONCLUSION AND FUTURE WORK:

: function CBRP((V t n , V t c ),{w t 1 , • • • , w t n }, {POSs t 1 , • • • , POSs t n }, d) 2:

Define neighbours are distance < d, T e is a constant to control the max-waiting time,V u = ∅ is the undecided nodes set and E = ∅; 3:

Each node i broadcast its weight w t i to neighbours;

4:

for i is in central node set V t c do Maintain the structure 5:

if there is a central nodes in neighbours and its weight is bigger than agent i then 6:

Pop node i from V t c and append it to V t n ;

7:

for i is in normal nodes set V append e ij = 0 and e ji = 0 to E;

21:

for j in V t c do 22:

append e ij = 0 to E;

23::

Return (V t n , V t c , E)

A.2 DETAILS AND DISCUSSIONS OF ALL HYPERPARAMETERS:

For both MAgent and StarCraft2 environments, the details of all hyperparameters used for approaches are summarized in the following Table 5 and Table 6 . All common hyperparameters of all approaches are set to be the same in the same environments. Except for the "ATOC", we change the message dimension to 64 in both enviroments. For the reason that if the dimension of messages is set to be 3 as other algorithms, the necessary GRU embedding in ATOC leads to failure while 64 seems to be robust.

For the neural network setting in MAgent enviroment, the node encoder part are all implemented with two convolutional layers with 32 filters and kernel size 3 and a MLP with 256 units. For the Q Encoder part, they are implemented with MLP(128, 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 is MLP(128, 64) and the aggregation functin isGRU(64). As for neural network setting in Starcraft2, 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, we also compare with a basic random weight generator (randomly chosen the central nodes and separate normal nodes into groups). As shown in Figure 9 Intra-group aggregation 3:

for v i in V n do 4:

for v j in V c and (i → j) in E do 5:

e ij = φ enc (v i ); Generate normal to central messages 6:

for v j in V c do ēj = ρ({e ij } (i→j)∈E ); Central agents aggregate received messages 7:

v c j = φ(ē j , v n j ); Generate cluster perception 8:

Inter-group sharing 9:

for v j in V c do 10:

for v i in V c and (i → j) in E do

11: 

e ij = φ(v c i ,

for v j in V n ∪ V c do 20:

for v i in V c and (i → j) in E do v n j = φ(ē j , v n j ); Update states 23:

q j = Q(v n j ); return q. 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 our learned weight generator also shows the necessity of selecting central nodes based on the learned weight generator rather than randomly chosen.

:



Figures and Tables:

Figure 1: Topology of different communication structures and LSC falls into the hierarchical one.

Figure 2: Procedure for dynamically establishing structured communication network. Left: Each agent determines its communication importance weight based on partial local observation.For instance, the agent "G" finds the target (red square), then it will be possible to 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 respectively. Further, the structured communication network will be re-established.

Figure 3: GNN-based communication extraction procedure. Each node denotes an agent. The edge embedding can be considered as the communication message. The network learning procedure properly 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 valuable embeddings to the associated central agents. Middle: High-level central agents communicate with each other to gain a sense of global perception. Right: All central agents broadcast embedding information to their normal agents to form global cooperation.

LSC: LEARNING STRUCTURED COMMUNICATION Our communication architecture has two key modules: structured communication network module and communication-based 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 1

Figure 5: Reward of algorithms and message pattern visualization in the MAgent environment.

Figure 7: Reward curves on StarCraft2

(a), our learned weight generator significantly outperforms randomly. Faster convergence of our learned weight generator Algorithm 3 HCOMM: Communication based Policy Module 1: function HCOMM(V n , V c , E) 2:

({e ij } (i→j)∈E ); Aggregate received central to normal messages 22:

The partial observable stochastic games (POSG) can be characterized as a tuple I, S, b 0 , A, O, P, P e , R where I denotes the set of agents indexed from 1 to n; S denotes the finite set of states; b 0 represents the initial state distribution and A denotes the set of joint actions. A i is the action space of agent i, a = a 1 , •, a n denotes a joint action; O denotes the joint observations and O i is the observation space for agent i, o = o 1 , •, o n denotes a joint observation; P denotes the Markovian transition distribution with P s, o s, a as the probability of state s transit to s and result o after taking action a. P

Table content: <table/>

Algorithm framework of LSC with Structured Communication Network Module and Communication-based Policy Module, where s i , o i , a i and w i 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.

Table content: <table><tr><td>o 1 o 2</td><td>o 3</td><td>o 4</td><td colspan="2">Weight Generator</td><td>w 4 w 3 w 2 w 1</td><td>A</td><td colspan="2">CBRP</td><td>o 2 o 1</td><td>o 3</td><td>o 4</td><td>Central Agents Normal Agents</td></tr><tr><td/><td/><td/><td/><td colspan="5">Structured Communication Network Module</td><td/><td/><td>Gradient Arrow</td></tr><tr><td colspan="2">ENVIRONMENT</td><td/><td>a 2 a 1 a 3 a 4</td><td>Q-Net</td><td/><td>s 2 s 1</td><td>s 3</td><td>s 4</td><td>Inter-group sharing</td><td colspan="2">Inter-group sharing</td><td>Intra-group aggregation</td><td>Input/Output Arrow Differentiable Module Non-Differentiable Module</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="3">GNN-based Communication</td></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="5">Communication-based Policy Module</td></tr><tr><td colspan="12">Figure 4: Algorithm 1 LSC: Learning Structured Communication</td></tr></table>

GNN-based Communication Architecture

Table content: <table><tr><td>Type</td><td>Edge (i → j) ∈ E</td><td>Edge Update Scheme</td><td>Node Update Scheme</td></tr><tr><td>Step 1: intra-group aggregation</td><td/><td/><td/></tr></table>

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.

Table content: <table><tr><td/><td colspan="2">LSC CommNet</td><td>IC3</td><td colspan="3">ATOC IDQN MFQ</td></tr><tr><td colspan="2">M ean-reward 1.11</td><td>0.86</td><td>0.93</td><td>0.58</td><td>0.8</td><td>0.83</td></tr><tr><td>N kill</td><td>62.6</td><td>61.3</td><td colspan="2">62.48 61.46</td><td>62.1</td><td>62</td></tr><tr><td>N dead</td><td>28.9</td><td>31.64</td><td>32.0</td><td>51.42</td><td>32.3</td><td>31.4</td></tr><tr><td>Ratio kd</td><td>2.16</td><td>1.93</td><td>1.95</td><td>1.20</td><td>1.92</td><td>1.97</td></tr></table>

Comparisons on the used epoch number to achieve same reward of the training procedure in the MAgent environment. Behavior illustration. The first row shows two typical behavior by LSC. In 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 baseline.

Table content: <table><tr><td/><td>Reward</td><td>LSC</td><td colspan="2">CommNet</td><td>IC3</td><td colspan="2">ATOC IDQN MFQ</td></tr><tr><td/><td>0.7</td><td>769</td><td colspan="2">1199</td><td>787</td><td>933</td><td>1133</td><td>1254</td></tr><tr><td/><td>0.8</td><td>828</td><td colspan="2">1292</td><td>935</td><td>1151</td><td>1460</td><td>1304</td></tr><tr><td/><td>0.9</td><td>1051</td><td colspan="2">1525</td><td>1508</td><td>1471</td><td>-</td><td>1426</td></tr><tr><td/><td>1.0</td><td>1271</td><td>-</td><td/><td>1588</td><td>1506</td><td>-</td><td>-</td></tr><tr><td/><td>1.1</td><td>1413</td><td>-</td><td/><td>1619</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td>1.2</td><td>1704</td><td>-</td><td/><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td/><td colspan="2">(a) Initial state</td><td colspan="4">(b) Encircle (c) Fire focusing</td></tr><tr><td>(d) LSC</td><td colspan="2">(e) CommNet</td><td colspan="2">(f) IC3</td><td colspan="2">(g) ATOC</td><td>(h) IDQN</td><td>(i) MFQ</td></tr><tr><td>Figure 6:</td><td/><td/><td/><td/><td/><td/></tr></table>

(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 Figure6(h) and 6(i). 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 can hardly understand their messages, making ineffective cooperation. As Figure6(e) and 6(f), some agents get far away from the majority of agents, thus their results are not ideal. To sum up, in Figure6(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.

Table content: <table/>

t n and no central node is in its neighbour do

Table content: <table><tr><td>8:</td><td>Pop node i from V t n and append it to V u ;</td><td/></tr><tr><td>9:</td><td>for i is in V u concurrently do</td><td>Elect central nodes</td></tr><tr><td>10: 11:</td><td>if does not receive larger weight for T e then append i to V t c and broadcast to neighbours;</td><td/></tr><tr><td>12:</td><td>else</td><td/></tr><tr><td>13:</td><td>Wait for the signal from central node for 2T e ;</td><td/></tr><tr><td>14:</td><td>if received a signal from central node then</td><td/></tr><tr><td>15:</td><td>append i to V t n ;</td><td/></tr><tr><td>16:</td><td>else</td><td/></tr><tr><td>17:</td><td>append i to V t c ;</td><td/></tr><tr><td>18:</td><td>for i in V t c do</td><td>generate communication link</td></tr><tr><td>19:</td><td/><td/></tr></table>

for v j in V n and (i → j) in E do 18:e ij = φ(v g i , v c i , v n i , e ji ), ēj = ρ({e ij } (i→j)∈E );

Table content: <table><tr><td/><td>v n i );</td><td>Generate central to central messages</td></tr><tr><td>12:</td><td>for v j in V c do</td><td/></tr><tr><td>13: 14:</td><td>ēj = ρ({e ij } (i→j)∈E ); v g j = φ(ē j , v n j );</td><td>Aggregate received central to central messages Obtain global perception</td></tr><tr><td>15:</td><td>Intro-group sharing</td><td/></tr><tr><td>16:</td><td>for v i in V c do</td><td/></tr><tr><td>17:</td><td/><td/></tr><tr><td/><td/><td>Generate central to normal</td></tr><tr><td/><td>messages</td><td/></tr><tr><td>19:</td><td/><td/></tr></table>

Hyperparamaters for Magent

Table content: <table><tr><td>Parameter</td><td colspan="4">LSC IDQN MFQ CommNet</td><td>IC3</td><td>ATOC</td></tr><tr><td>Episodes</td><td>1750</td><td>1750</td><td>1750</td><td>1750</td><td>1750</td><td>1750</td></tr><tr><td>start</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td></tr><tr><td>end</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.01</td></tr><tr><td>Learning rate</td><td>1e -4</td><td>1e -4</td><td>1e -4</td><td>1e -4</td><td>1e -4</td><td>1e -4</td></tr><tr><td>Max env steps</td><td>400</td><td>400</td><td>400</td><td>400</td><td>400</td><td>400</td></tr><tr><td>dimension of messages</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td><td>64</td></tr><tr><td>radius of communication</td><td>6</td><td>∼</td><td>6</td><td>∼</td><td>∼</td><td>6</td></tr></table>

Hyperparamaters for Starcraft2

Table content: <table><tr><td>Parameter</td><td>LSC</td><td>IDQN</td><td>MFQ</td><td>CommNet</td><td>IC3</td><td>ATOC</td></tr><tr><td>Total steps</td><td>600k</td><td>600k</td><td>600k</td><td>600k</td><td>600k</td><td>600k</td></tr><tr><td>start</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td></tr><tr><td>end</td><td>0.05</td><td>0.05</td><td>0.05</td><td>0.05</td><td>0.05</td><td>0.05</td></tr><tr><td>Learning rate</td><td>1e -4</td><td>1e -4</td><td>1e -4</td><td>1e -4</td><td>1e -4</td><td>1e -4</td></tr><tr><td>Max env steps</td><td colspan="3">10000 10000 10000</td><td>10000</td><td colspan="2">10000 10000</td></tr><tr><td>dimension of messages</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td><td>64</td></tr><tr><td>radius of communication</td><td>6</td><td>∼</td><td>6</td><td>∼</td><td>∼</td><td>6</td></tr></table>

Peer review (iclr2020):
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. To 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. To 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. I 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. Minor Comments: The following are suggestions for improvements if the paper is accepted or for future submissions. In 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. In 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. Many 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. In 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. On 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. The 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. Finally, 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: - 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.* - Page 2, *or employing the LSTM to* -> *or use the LSTM to* - Page 2, *still hinder the* -> *still hinders the* - Page 2, *the communication structure need be jointly* -> needs to be jointly - Page 6, *policy module motioned below* -> discussed below - Page 10, *the map size are is 1920x1200* -> the map size is 1920x1200 - Page 10, *We do not compare with ATOC because its poor performance in MAgent* -> because of its - Page 10, *we will to improve* -> we will improve - Page 10, *practical constrains* -> practical constraints