Multi-Agent Coordination via Multi-Level Communication

To begin with, we thank the reviewer for the carefully reviewing and insightful advice.

If the authors formulate this problem as a multi-agent sequential decision-making problem, the Markovian property required for formulating the problem as an MDP is no longer satisfied and there is a need to prove an alternative policy gradient theorem before simply inserting the Seqcomm into MAPPO.

To connect SeqComm and MAPPO while avoiding this problem, we build a new MDP $\tilde{M}$ based on the original MDP $M$. The state space of $\tilde{M}$ can be divided into multiple layers and the state transitions only occur between consecutive layers. The sequential decision-making process in the original MDP corresponds to a round of agent-by-agent decision-making process while the Markovian property of $\tilde{M}$ is preserved. We show SeqComm in original MDP equals Agent-by-agent PPO in new MDP $\tilde{M}$. More detailed discussions are included in Appendix A.

In Figure 2's caption, the authors stated that 'in the launching phase, the agents who hold the upper-level positions will make decisions prior to the lower-level agents. Besides, their actions will be shared with anyone that has not yet made decisions, then how to change the structure of the MAPPO model to make it fit this change? And how to adjust the time step based on this change?

Assume there are two agents, in the original MAPPO, the police of each agent is p(ai|s) and the value function is v(s). In our setting, the second level agent’s policy is p(a2|s, $\emptyset$) and the value function is v(s, $\emptyset$), we change the structure of the first level agent, its policy is p(a1|s, a2) and value function is v(s, a2). Other training procedures are the same. In practice, we use communication channels to achieve information sharing.

We did not change the time step, since after all the agents make decisions, they execute the actions to interact with the environment simultaneously. Note that we did not break the fundamental dynamic, p(s’|s, a1,a2).

There is no code available in this submission, the details of the models' structures could not be seen. The reproducibility remains unsure.

Many methods in communication-based MARL did not share the code, which makes the comparison very hard. We also do not like this trend, and we guarantee we will release the code as soon as this paper gets accepted. We also guarantee all the results can be reproduced.

Only comparing to TarMAC is not enough, this MARL with communication algorithm was proposed in 2019, and there are more recent MARL communication algorithms outperforming TarMAC.

We add more baselines as requested in Figure 3 (pdf in the global response). Note that many methods in communication-based MARL did not share the code, meaning many baselines cannot be compared fairly. We choose two baselines for comparison (CommFormer [1] and MAIC[2]) with two criteria, 1. Published in the recent top conference; 2. Release the code for a fair comparison.

The result shows that SeqComm still outperforms these baselines by a large margin. Surprisingly, we have tried our best to tuned the parameters under the limited timeline, but CommFormer (2024 baselines) still performs worsen than MAIC (2022 baselines).

[1]. Learning Multi-Agent Communication from Graph Modeling Perspective. ICLR 2024

[2]. Multi-Agent Incentive Communication via Decentralized Teammate Modeling. AAAI 2022

To begin with, we thank the reviewer for the carefully reviewing and insightful advice.

Computational complexity.

The computational complexity of SeqComm is mainly related to communication overhead.

For full communication, SeqComm needs more rounds, but it only transmits observation information for one time. For the rest n − 1 round communication with total (n − 1)/2 broadcasts per agent, only a single intention value and an action will be exchanged. Considering there are n! permutations of different order choices for n agents, our method has greatly reduced computation overhead since each agent needs to calculate up to n times to search for a satisfying order. Note that, in Section 3, we mentioned the cost-free communication setting. This extreme case gives us a better understanding of the benefit of communication, even if the results do not apply across all domains. Therefore, we propose a more applicable setting.

For local communication, there are only two communication rounds. One is for sharing observations and information. Another is for intention values.

Heterogeneous agent scenarios.

We would like to point out that the agents in SMACv2 can be heterogeneous. Each map has three types of agents. Three types have different functions (Ranged and melee types), and the types are randomly refreshed. It turns out our methods can be applied to heterogeneous agent scenarios. One policy can learn different strategies for different types of agents. Note that the observation contains the information of the agent type.

World model.

Theorem 1 provides a useful relationship between the compounding errors and the police update. As long as we improve the return under the true dynamic by more than the gap (mentioned in line 292), we can guarantee the policy improvement under the world model. If no such policy exists to overcome the gap, it implies the model error is too high, that is, there is a large discrepancy between the world model and true dynamics. Thus, the order sequence obtained under the world model is not reliable. Such an order sequence is almost the same as a random one. Though a random order sequence also has the theoretical guarantee of Proposition 2, we have shown in Section 5.2 that a random order sequence leads to a poor local optimum empirically but it still can converge.

The prioritization mechanism

In each step, we will recompute the order based on the current situation. The proposition 2 shows that, even the order changes each step, the monotonic improvement and convergence of the joint policy in SeqComm will not be affected.

Emergence of behavioral patterns

We have visualized some key frames to illustrate the behavioral patterns in Figure 2 (pdf in the global response). In the combat game, the unified attack on one enemy is always more effective than dispersing attacks. From frames 1-3, agents have no target until one agent (at the end of the orange arrow) is close to an enemy (the bottom right corner). In frame 4, through the negotiation phase, that agent is chosen as the highest-level agent (level 5) since it has a better position to choose one enemy to attack. After lower-level agents obtained the actions of higher-level agents (illustrated by a white dashed line), all the red units ended their random roaming and instead launched a unified attack on the blue units.

A similar behavioral pattern can also be observed in Frames 7-9.

Simpler aggregation methods.

We have done the ablation study as requested in Figure 1 (pdf in the global response). It turns out the attention mechanism performs better than a simpler aggregation method. The reason is simple aggregation the observations will expand the dimension input of the neural network. It will impair the learning process since high-dimension input may contain many irrelevant information [1]. However, the attention mechanism helps focus on more important information by learning different weights on different observations.

[1] Learning individually inferred communication for multi-agent cooperation. NIPS 2020.

Attention mechanism learns meaningful patterns.

We have observed two patterns. One is upper-level agents will be highlighted since important actions are provided. Another is the agents that are far away will be overlooked.

How does the computational cost of the attention mechanism scale with the number of agents, especially in the full communication scenario?

In full communication scenarios, the computation cost increases linearly with the number of agents.

In the local communication scenarios, due to the limitation of the communication range, the number of local communicated agents will also be limited. Therefore, the communication cost has an upper bound.

More advanced attention mechanisms (e.g., multi-head attention).

Yes, it may help to process the incoming messages from other agents. However, since the main contributions are not from the attention mechanism, we did not spend too much time investigating this. However, how the attention mechanisms or transformers architecture influences the learning process is another high-profile line of research in RL.

How is the attention mechanism modified to handle the local communication scenario effectively?

The attention mechanism is originally used in natural language processing, where they are inherently capable of processing input of different lengths, just like recurrent neural networks.

The assumptions regarding local observations and communications might not be realistic for all applications.

Thank you for pointing out the limitations. We agree that the settings cannot be applied to all the applications. However, our setting is more realistic compared to other full communication and global observation settings.

In more detail, local observations are widespread in the real world because of the limitations of distance, hardware, or other objective factors. For example, not all information can be measured and obtained by the sensors in the real world, which makes global observations unrealistic.

For communication, it is widely used in the real world. People use wireless communication to access the Internet. Also, the Internet of Vehicles and the Internet of Things aim to connect all things with communication by 5G, which means many works believe communication is necessary despite the difficulty in implementation.

To begin with, we thank the reviewer for the carefully reviewing and insightful advice.

Could you elaborate on your choice of SMACv2 as the primary benchmark for evaluating SeqComm?

In cooperative MARL, SMAC is the most popular testbed for the centralized training and decentralized execution paradigm. Other important testbeds are Google Research Football (GRF) and Multiple Particle Environment (MPE).

Comparing the SMAC and other testbeds (MPE and GRF), SMACv2 (upgraded version of SMAC) is the latest testbed and proposed in 2023. This work critiques the original benchmark for lacking stochasticity and meaningful partial observability (SMAC, MPE, and GRF) and claims they simplify the coordination. It deliberately increases the stochasticity, meaning partial observability, and conducts thorough experiments to verify it. Our method aims to address the coordination issue in MARL and this problem is mostly induced by the partial observability of the agents. Therefore, our method is possible to demonstrate the superiority on the benchmark requiring high-level coordination, otherwise, the performance gap is not obvious for the benchmark where agents do not even need to coordinate to finish the tasks.

Compared with other benchmarks, SMACv2 is more challenging from the following points. 1. Complex observation dimension (hundreds). 2. Diversity (many maps and unit types with different functions). 3. Stochasticity (different designed start positions). 4. meaningful partial observability (mask many irrelevant information). We believe the results from SMACv2 would generalize well to other MARL environments suffering from coordination issues since we chose the most challenging benchmark in this field.

Have you considered the possibility of deadlocks in your asynchronous mechanism? What measures, if any, have been implemented to prevent or resolve potential deadlocks?

Deadlock occurs when two or more agents obtain the same intention value at the same time, and then they need another rule to determine the priority. In our implementation, each agent is assigned an index, and the rule to break the deadlock is the agent with a small index to determine first.

Can you provide an analysis of the computational complexity of SeqComm compared to existing methods, especially for large-scale multi-agent systems?

The computational complexity of SeqComm mainly related to communication overhead.

For full communication, SeqComm needs more rounds, but it only transmits observation information for one time. For the rest n − 1 round communication with total (n − 1)/2 broadcasts per agent, only a single intention value and an action will be exchanged. Considering there are n! permutations of different order choices for n agents, our method has greatly reduced computation overhead since each agent needs to calculate up to n times to search for a satisfying order.

For local communication, there are only two communication rounds. One is for sharing observations information. Another is for intention values.

How sensitive is SeqComm to the choice of hyperparameters, particularly F and H? Are there any guidelines for selecting these values?

H is the length of the trajectory. Empirically, we found that 2-4 can lead to decent performance. For too long length, the error caused by the world model can be too large. Besides, since the order of each step can change, the observation after more steps is meaningless

F is the number of the future trajectories. Theoretically, the higher the number of F, the more accurate the estimation, but the computational cost also increases. Therefore, in practice, we need to seek a trade-off.

This paper aims to demonstrate SE is better than NE. In nature, under SE where agent makes decisions sequentially, parts of agents can obtain the extra information (actions of upper-level agents). Intuitively, if the agent has more valuable information, it will help make the decision.

For other potential equilibrium, if it allows the agent to get extra valuable information and does not break the fundamental dynamic of the environment, it also can benefit the performance.

Assumption issues.

1. If information asymmetry which means communication is not allowed, then the SeqComm is degraded to MAPPO.

   If only parts of the information are asymmetrical, it will degrade to the local-communication version.

2. In our view, we will recompute the decision-making order based on the current situation during the execution phase. It will ensure stability.

3. When perfect information about other agents' strategies is not available, we can do the opponent modeling, in more detail, we can train a policy that predicts the actions of other agents. Since we can get the observations of others via communication, the opponent modeling can be precise.