Learning Multi-Agent Communication from Graph Modeling Perspective

Q1 & Q2

The proposed learned communication graph approach should be experimented and evaluated against other graph-based methods.

Is this approach specialized and designed for SMAC?

Thanks for the suggestion! We have incorporated additional experiments to enhance the generalization of our method. Taking into account the communication domains explored in previous works, we have included the following experiments. It is worth noting that in certain domains, our objective extends beyond maximizing the average success rate or cumulative rewards. We also aim to minimize the average number of steps required to complete an episode, emphasizing the ability to achieve goals in the shortest possible time.

• Another three maps in the SMAC environment: 1o10b_vs_1r and 1o2r_vs_4r, which pose challenges due to partial observability, and 5z_vs_1ul, where successful outcomes require strong coordination.
• Predator-Prey (PP) [1]: The goal is for 𝑁 predator agents with limited vision to find a stationary prey and move to its location. The agents in this domain all belong to the same class (i.e., identical state, observation and action spaces).
• Predator-Capture-Prey (PCP) [2]: We have two classes of predator and capture agents. Agents of the predator class have the goal of finding the prey with limited vision (similar to agents in PP). Agents of the capture class, have the goal of locating the prey and capturing it with an additional capture-prey action in their action-space, while not having any observation inputs (e.g., lack of scanning sensors).
• Google Research Football (GRF) [11]: We evaluate algorithms in the football academy scenario 3 vs. 2, where we have 3 attackers vs. 1 defender, and 1 goalie. The three offending agents are controlled by the MARL algorithm, and the two defending agents are controlled by a built-in AI. We find that utilizing a 3 vs. 2 scenario challenges the robustness of MARL algorithms to stochasticity and sparse rewards.

We include several state-of-the-art graph-based multi-agent communication learning approaches as additional baselines in our evaluation. These methods encompass QGNN [7], SMS [3], TarMAC [4], NDQ [5], MAGIC [6], HetNet [2], CommNet [8], I3CNet [9], and GA-Comm [10].

The performance results of these baselines are presented below. It is important to note that due to time constraints, we directly obtain the performance results from the respective papers. Our CommFormer consistently demonstrates favorable performance across the evaluated metrics.

Q2

In Table 1, the FC is a little bit confusing. Even there are no constrictions on the communication bandwidth, the win rate is still hard to be 100% as it depends how the opponents perform. Of course, 100% is the maximum value for the win rate, but it is a meaningless upper bound. Further, how the value 93.8 is obtained in FC column as the upper bound?

In our study, "FC" refers to CommFormer with a sparsity setting of 1.0. This configuration implies that there are no restrictions on the communication graph, allowing agents to freely communicate with all other agents. Effectively, this represents the upper performance limit of the CommFormer methods. By presenting results under this setting, we aim to demonstrate that with our bi-level learning process, a sparsity of 0.4 can achieve comparable results to a full sparsity of 1.0 in most scenarios.

Given the "FC" framework, the bi-level optimization problem simplifies to the following optimization formulation:

$$\min_{\theta, \phi} ~L_{val}(\phi, \theta)$$

Q3

There have been some works which learns multi-agent cooperative behaviors based on learnable graphs. It would be better to illustrate the differences of the paper compared to them.

Thanks! TWG-Q[12] primarily focuses on exploring diverse spatial-temporal information environments, necessitating the utilization of a temporal weight learning mechanism and weighted GCN to dynamically capture the intensities of cooperations. Conversely, CDC[13] dynamically adjusts the communication graph, taking into account the diffusion process perspective to capture the information flow on the graph. In contrast, our CommFormer approach learns the static communication graph through an optimization perspective, employing attention scores to automatically assign credit to received messages. We will improve the related work in the updated version.

Reference

[1] Amanpreet, Singh, et al. "Learning when to communicate at scale in multiagent cooperative and competitive tasks." arXiv preprint arXiv:1812.09755 (2018).

[2] Seraj, Esmaeil, et al. "Learning Efficient Diverse Communication for Cooperative Heterogeneous Teaming." AAMAS 2022.

[3] Xue, Di, et al. "Efficient Multi-Agent Communication via Shapley Message Value." IJCAI 2022.

[4] Das, Abhishek, et al. "Tarmac: Targeted multi-agent communication." ICML 2019.

[5] Wang, Tonghan, et al. "Learning nearly decomposable value functions via communication minimization." arXiv 2019.

[6] Niu, Yaru, et al. "Multi-Agent Graph-Attention Communication and Teaming." AAMAS 2021.

[7] Ryan Kortvelesy and Amanda Prorok. "QGNN: Value Function Factorisation with Graph Neural Networks." arXiv preprint arXiv:2205.13005, 2022.

[8] Sainbayar Sukhbaatar, et al. "Learning multiagent communication with backpropagation." NeurIPS 2016.

[9] Amanpreet Singh, et al. "Learning when to communicate at scale in multiagent cooperative and competitive tasks." arXiv preprint arXiv:1812.09755 (2018).

[10] Yong Liu et al. "Multi-Agent Game Abstraction via Graph Attention Neural Network." AAAI 2022.

[11] Karol Kurach, et al. "Google Research Football: A Novel Reinforcement Learning Environment." AAAI 2020.

[12] Liu, Yuntao, et al. "Temporal Dynamic Weighted Graph Convolution for Multi-agent Reinforcement Learning." Proceedings of the Annual Meeting of the Cognitive Science Society.

[13] Pesce, Emanuele, et al. "Learning multi‑agent coordination through connectivity‑driven communication." Machine Learning Springer 2023.

Q1

Some CTCE based MARL methods. for example, graph-based MARL methods, should be considered for the comparison in the experiment.

Thanks for the suggestion! We have incorporated additional experiments to enhance the generalization of our method. Taking into account the communication domains explored in previous works, we have included the following experiments. It is worth noting that in certain domains, our objective extends beyond maximizing the average success rate or cumulative rewards. We also aim to minimize the average number of steps required to complete an episode, emphasizing the ability to achieve goals in the shortest possible time.

• Another three maps in the SMAC environment: 1o10b_vs_1r and 1o2r_vs_4r, which pose challenges due to partial observability, and 5z_vs_1ul, where successful outcomes require strong coordination.
• Predator-Prey (PP) [1]: The goal is for 𝑁 predator agents with limited vision to find a stationary prey and move to its location. The agents in this domain all belong to the same class (i.e., identical state, observation and action spaces).
• Predator-Capture-Prey (PCP) [2]: We have two classes of predator and capture agents. Agents of the predator class have the goal of finding the prey with limited vision (similar to agents in PP). Agents of the capture class, have the goal of locating the prey and capturing it with an additional capture-prey action in their action-space, while not having any observation inputs (e.g., lack of scanning sensors).
• Google Research Football (GRF) [11]: We evaluate algorithms in the football academy scenario 3 vs. 2, where we have 3 attackers vs. 1 defender, and 1 goalie. The three offending agents are controlled by the MARL algorithm, and the two defending agents are controlled by a built-in AI. We find that utilizing a 3 vs. 2 scenario challenges the robustness of MARL algorithms to stochasticity and sparse rewards.

We include several state-of-the-art graph-based multi-agent communication learning approaches as additional baselines in our evaluation. These methods encompass QGNN [7], SMS [3], TarMAC [4], NDQ [5], MAGIC [6], HetNet [2], CommNet [8], I3CNet [9], and GA-Comm [10].

The performance results of these baselines are presented below. It is important to note that due to time constraints, we directly obtain the performance results from the respective papers. Our CommFormer consistently demonstrates favorable performance across the evaluated metrics.

Q1

Despite the authors claiming that dynamic adjustments fall outside the scope of the paper, it would be interesting to see performance comparisons.

Thanks for the suggestion.

The learning process of the communication graph in our study is conducted through bi-level optimization, which necessitates backward propagation of loss. Consequently, during inference, the communication graph remains static and cannot be updated.

To adapt our method to a dynamic version, the most straightforward approach is to adjust the communication graph based on the attention scores. We conduct tests on four maps, which involve both homogeneous and heterogeneous agents. The performance results of these experiments are presented below.

As indicated, the dynamic version exhibits a decline in performance across all scenarios. In homogeneous agent environments, the dynamic version demonstrates relatively robust performance. However, in heterogeneous settings, such as in the 3s5z map, it fails to effectively learn communication relationships. This shortfall is likely due to the instability of the training process and a self-boosting phenomenon, where the network is preferentially updated based on relations with initially high attention scores.

We also compare our method with others that specifically investigate dynamic communication adjustments, such as SMS[1], TarMAC[2], and the dynamic message-passing method QGNN[3]. These comparisons are made on three maps: 1o10b_vs_1r and 1o2r_vs_4r, which are challenging due to partial observability, and 5z_vs_1ul, where strong coordination is essential for success. As illustrated in the table below, our method consistently demonstrates exceptional performance.

Q2

Why do Dynamic adjustments fall outside the scope of the paper? It seems like this is more about considering a simplified problem setting, where the communication graph between training and execution must be similar. Did you run any experiments testing the performance of CommFormer when the nature of the communication graph changes between training and execution?

Thank you for this helpful suggestion!

(1) Dynamic adjustments, while ensuring adherence to sparsity requirement at each step, operate under the assumption that all agents require constant communication with one of the other agents. This process typically demands multiple rounds to establish the current communication graph, potentially leading to inefficient bandwidth usage and imposing practical challenges in real-world applications.

(2) The primary goal of our research is to identify the most effective communication graph for a given task. During the training phase, we explore the best possible communication graph from a total of $C(N^2, m)$ potential edge configurations ( $N$ represents the number of agents, and $m$ denotes the number of edges). Upon transition to the execution phase, this communication graph is set and remains unchanged. This fixed communication model is particularly advantageous for practical deployment scenarios.

(3) Our training methodology focuses on identifying the optimal communication graph. To prevent biases towards specific edges (self-boosting phenomenon), we employ the Gumbel-Softmax trick. This approach enables random edge selection during training, ensuring that each potential connection is considered. Consequently, deviating from the determined communication graph during inference can lead to performance degradation. However, due to the comprehensive nature of our training process, the impact on performance might not be drastic. We validate this hypothesis through tests on four maps involving both homogeneous and heterogeneous agents, with the performance outcomes detailed below:

Q1

How is the ordering of agents decided when inputting to the transformer and is there positional encoding?

Sorry for the misleading. It is important to clarify that we do not manually determine the order of the agents, nor is there any positional encoding specifically assigned to the agents. Instead, we calculate the attention between agent $i$ and its preceding agents $j$ where $j<i$ in order to ensure that the decoder generates the action sequence in an auto-regressive manner. This approach guarantees a consistent improvement in performance during training [1].

In practice, it is possible to change the order of agents at each update iteration. However, we have chosen to maintain the current representation (using $1,2, \dots n$ other than $i_1, i_2, \dots i_n$ ) primarily for the purpose of preserving the order of the adjacency matrix. Altering the order of agents would require corresponding adjustments to the adjacency matrix $\alpha$.

Q2

Compare to a recent graph-based MARL baseline called QGNN.

Thank you for your comment.

QGNN primarily leverages graph pooling to facilitate the process of value factorization within a system of agents that exhibit variable sizes. In this system, the communication graph is predetermined by a specific protocol, such as known interactions, and is employed to represent the interdependencies present within a multi-layer message-passing GNN architecture. On the other hand, our CommFormer algorithm simultaneously determines the communication graph and autonomously assigns credit to received messages through a single round of communication. The requested results have been presented in the table provided below. To consider the time constraints, we have chosen StarcraftII as the environment for testing these methods. The evaluation is conducted on three maps: 1o10b_vs_1r and 1o2r_vs_4r, which pose challenges due to partial observability, and 5z_vs_1ul, where successful outcomes require strong coordination.

To ensure a comprehensive comparison, we have also included the performance of other communication methods, such as SMS[2], TarMAC[3], NDQ[4] and MAGIC[5]. It is worth noting that in the QGNN approach, the graph is fully-connected, following their official code settings. This means that each agent can communicate information with all other agents. CommFormer consistently demonstrates strong performance across these environments.

Q3

Discuss or demonstrate what would happen if more realistic assumptions on graph communication were made, such as only communicating with agents within some specified communication range?

A possible application of this study is to create an efficient communication framework tailored for enclosed, finite environments, typical of logistics warehouses. In these settings, agent movement is limited to designated zones, and communication is facilitated through overhead wires, akin to a trolleybus system.

Our objective encompasses determining the optimal communication graph, while concurrently ensuring normal updates of architectural parameters. Upon completion of the training phase, the communication graph becomes static, forming the basis for subsequent inferences.

In contrast, open environments present unique challenges, primarily due to the potential vast distances between agents, which requires wireless communication and may hinder effective communication. To address this, a straightforward approach could be to add bidirectional edges between agents when they come within close proximity, enabling communication between them [6]. However, a more effective solution may involve a hybrid approach that considers the constraint on the available bandwidth：initially segmenting agents into groups based on proximity, followed by an internal search for an optimal communication graph within each group. If agent distances vary dynamically during testing, this process is repeated as necessary to adjust the communication graph in real-time, ensuring continuous adaptability to changing environmental conditions.