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