Year: 2019

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.

heading: 1 INTRODUCTION
text: 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
communication network (Figure 1(c)). 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.
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.
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. It 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 structure. iii) Extensive experiments on both MAgent and StarCraft2 show our approach achieves state-of-theart scalability and effectiveness on large-scale MARL problems.

heading: 2 RELATED WORK AND PRELIMINARIES
text: 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. The partial observable stochastic games (POSG) can be characterized as a tuple 〈 I,S, b0,A,O,P,Pe,R 〉 where I denotes the set of agents indexed from 1 to n; S denotes the finite set of states; b0 represents the initial state distribution and A denotes the set of joint actions. Ai is the action space of agent i, a = 〈a1, ·, an〉 denotes a joint action; O denotes the joint observations and Oi is the observation space for agent i, o = 〈o1, ·, on〉 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. Pe(o|s) is the Markovian observation emission probability function. R : S × A → Rn means the reward function for agents. The overall task of the MARL problem can be solved by properly objective function modeling, which also indicates the relationship among agents, e.g., cooperation, competition or mixed. Graph Neural Network. Graph neural network (GNN) (Scarselli et al., 2008) is a deep embedding framework to handle graph-based data on a graph G = (V, E). vi denotes the node feature vector for node vi ∈ V (for Nv nodes), ek denotes the edge feature vector for edge ek ∈ E (for Ne edges) with rk, sk be the receiver and sender of edge ek 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 rt, DQN learns the action-value function Qπ(s, a) = Es∼P,a∼π(s) [Rt|st = s, at = a] by minimizing L(θ) = Es,a,r,s̃ [ỹ −Q(s, a; θ)], where ỹ = r + γmaxãQ (s̃, ã; θ). The agent follows -greedy policy, that is, selects the action that maximizes the Q-value with probability 1- or 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 Qa(ua|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 largescaleMARL 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.

heading: 3 LSC: LEARNING STRUCTURED COMMUNICATION
text: 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
Algorithm 1 LSC: Learning Structured Communication 1: Initialization: weight generator parameters θw, Q-net parameters θQ, GNN parameters θgnn,
target Q-net parameters θQ̃, replay bufferR = ∅, group radius d, the number of agents n; 2: for Episode = 1, · · · ,M do 3: Reset t = 0, global state st and observation oti for each agent i, Normal agents set Vtn = {all agents} and Vtc = ∅; 4: for t = 1, · · · , T and st 6= terminal do 5: for each agent i do 6: With probability pick a random action wti else w t i = arg max{wi}Qθw(o t i); 7: Get current position POSsti of each agent i; 8: (Vtn,Vtc, E) = CBRP((Vt−1n ,Vt−1c ),{wt1, · · · , wtn}, {POSst1, · · · ,POSstn}, d); 9: {qt1, · · · , qtn} = HCOMM(Vtn, Vtc , E); 10: for each agent i do 11: With probability pick a random action ati else choose the action that has the largest 12: value in the vector qti ; 13: Execute global actions and get global reward rt , next state st+1 , next observation ot+1; 14: Get updated position POSst+1i for each agent i; 15: Store (st, ot, {POSst1, · · · ,POSstn}, at, rt, ot+1, {POSst+11 , · · · ,POSs t+1 n }, st+1) toR; 16: for k = 1, · · · ,K do 17: Sample a random mini-batch transitions fromR; 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.

heading: 3.1 STRUCTURED COMMUNICATION NETWORK MODULE
text: 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 fwg : 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 {wi} 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 weightw 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 yi = ri+γmaxw̃i Qθw(õi, w̃i). ri denotes the reward received for agent i from environment.
`(θw) = Eo,w,r,õ [ n∑ i=1 (Qθw(oi, wi)− yi)2 ] . (1)

heading: 3.2 COMMUNICATION-BASED POLICY MODULE
text: 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 Nv nodes which can be divided into the central node set Vc and the normal node set Vn. For central node i ∈ Vc, the node feature vector vi includes the embedding feature vni , the central role feature v c i and the global feature vgi ; for normal node i ∈ Vn, the node feature vector vi only includes the embedding feature vni . For each edge (i→ j) ∈ E with i, j ∈ V , the edge feature vector is denoted as eij . 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 ∈ Vc; 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.
The GNN-based communication sub-module is modeled as a GNN (fθgnn ) with parameter θgnn, while the following Q-Net of agent i (Qiθ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:
`(θQ, θgnn) := Eo,a,r,õ [ n∑ i=1 ( QiθQ(fθgnn(o), ai)− yi )2] , (2)
where yi = ri + γmaxãi Q i θQ(fθgnn(õ), ãi). ri 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 (Nmsg) among agents; the number of steps during the communication procedure (Nstep); the communication bandwidth and range requirements for each agent (Nb-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(n2) 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). Nstep and Nb-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 ofO(d) (d denotes the depth of the communication network). Nb-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(k2 + kb). However the depth of the hierarchical communication network is only two which results in O(1) communication steps, while Nb-r is in the order of O(max(b, k)). Overall, our LSC algorithm has advantage in the communication efficiency.

heading: 4 EXPERIMENTS
text: 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.

heading: 4.1 LARGE SCALE BATTLE GAME IN MAGENT
text: 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, Nkill, Ndead, Ratiokd in Table 3 denote the mean of average final rewards of agents, the number of killed enemies and dead agents, and the ratio Nkill / Ndead, respectively. Following Figure 5(a), LSC can obtain a better mean reward stably, with a 30% performance advantage at least. Nkill 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 Ndead and the highest Ratiokd. 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
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. 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(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(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 Figure 6(e) and 6(f), some agents get far away from the majority of agents, thus their results are not ideal. To sum up, in Figure 6(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.

heading: 4.2 LARGE SCALE BATTLE GAME IN STARCRAFT2
text: 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.

heading: 5 CONCLUSION AND FUTURE WORK
text: In this paper, a novel learning structured communication (LSC) algorithm is proposed for multiagent reinforcement learning. The hierarchical structure is self-learned by cluster based routing protocol. The communication message representation is naturally embedded and extracted via a graph neural network. Experiments in large-scale games (MAgent and StarCraft2) demonstrated that our LSC can outperform existing learning-to-communicate 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.

heading: A APPENDIX
text: A.1 CBRP ALGORITHM AND HCOMM ALGORITHM
Algorithm 2 CBRP: Cluster Based Routing Protocol 1: function CBRP((Vtn,Vtc),{wt1, · · · , wtn}, {POSst1, · · · ,POSstn}, d) 2: Define neighbours are distance< d, Te is a constant to control the max-waiting time,Vu = ∅
is the undecided nodes set and E = ∅; 3: Each node i broadcast its weight wti to neighbours; 4: for i is in central node set Vtc 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 Vtc and append it to Vtn; 7: for i is in normal nodes set Vtn and no central node is in its neighbour do 8: Pop node i from Vtn and append it to Vu; 9: for i is in Vu concurrently do . Elect central nodes 10: if does not receive larger weight for Te then 11: append i to Vtc and broadcast to neighbours; 12: else 13: Wait for the signal from central node for 2Te; 14: if received a signal from central node then 15: append i to Vtn; 16: else 17: append i to Vtc; 18: for i in Vtc do . generate communication link 19: for j in Vti and j is neighbouring i do 20: append eij = 0 and eji = 0 to E ; 21: for j in Vtc do 22: append eij = 0 to E ; 23: Return (Vtn,Vtc, 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(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(Vn,Vc, E) 2: ] Intra-group aggregation 3: for vi in Vn do 4: for vj in Vc and (i→ j) in E do 5: eij = φenc(vi); . Generate normal to central messages 6: for vj in Vc do ēj = ρ({eij}(i→j)∈E); . Central agents aggregate received messages 7: vcj = φ(ēj , v n j ); . Generate cluster perception
8: ] Inter-group sharing 9: for vj in Vc do
10: for vi in Vc and (i→ j) in E do 11: eij = φ(vci , v n i ); . Generate central to central messages 12: for vj in Vc do 13: ēj = ρ({eij}(i→j)∈E); . Aggregate received central to central messages 14: vgj = φ(ēj , v n j ); . Obtain global perception
15: ] Intro-group sharing 16: for vi in Vc do 17: for vj in Vn and (i→ j) in E do 18: eij = φ(v g i , v c i , v n i , eji), ēj = ρ({eij}(i→j)∈E); . Generate central to normal
messages 19: for vj in Vn ∪ Vc do 20: for vi in Vc and (i→ j) in E do 21: ēj = ρ({eij}(i→j)∈E); . Aggregate received central to normal messages 22: vnj = φ(ēj , v n j ); . Update states 23: qj = Q(vnj ); 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.
To better investigate the hierarchical structure, we compare our LSC algorithm with respect to different group radius d, i.e., 3, 6, 12 and 60. As shown in Figure 9(b), LSC with radius 6 outperform other settings. When the radius increasing, the agents can establish inter-groups cooperation easier. However, 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.

Review summaries:
The 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.

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.