Exponential Topology-enabled Scalable Communication in Multi-agent Reinforcement Learning

Thank you for your positive review. We have updated the manuscript accordingly (highlighted in blue) and provide detailed clarifications below. If you have any follow-up questions or comments, please let us know, and we will be happy to discuss further.

Q1: Communication overhead.

Q1.1:

The definition of communication overhead in this paper is rather ambiguous... Does communication overhead in this paper refer to number of messages passed? Can you provide a definition in-text?

A1.1: We apologize for the ambiguity. Yes, in our manuscript, communication overhead refers to the number of messages passed between agents. We have clarified this definition in Section 3.1.2 and reorganized the experiment setups in Section 4.1 to include a detailed explanation of the communication budget settings.

Q1.2: Does ExpoComm result in lower numbers of messages passed between agents?

A1.2: In our experimental setup, we maintain equal communication budgets (number of messages passed) across all methods except communication-free baselines. This design allows us to fairly evaluate the effectiveness of different communication strategies. Our results demonstrate that ExpoComm achieves superior performance while operating under the same communication constraints as baseline algorithms.

Q1.3:

Are there additional communciation savings that can be achieved by your method beyond its exponential graph structure?

A1.3: While our current implementation focuses on the exponential graph structure, there are promising avenues for additional communication savings. These include learning low-entropy messages [1] and exploiting temporal communication sparsity, which we discuss as future directions in Appendix C.3.

Q1.4:

Did you experiment with more K values beyond log2N and 1? If so, what did you observe and why did you believe these two values in the paper would be representative examples?

A1.4: Our choice of $K=\log_2N$ and $K=1$ was primarily motivated by theoretical considerations rather than experimental observations. These values represent logarithmic growth and constant complexity respectively, which are particularly relevant for scaling to large-scale multi-agent systems (MASs). Traditional approaches using fully-connected graphs ($K=N$) or sparse connections [2] ($K=\text{sparsity} \cdot N$, where $\text{sparsity}$ is a constant) result in quadratic overall communication costs, becoming impractical for large values of $N$ (e.g., $N=100$). By contrast, our approach deliberately explores sub-polynomial scaling through logarithmic and constant functions, offering more efficient alternatives for large-scale deployments.

Q2:

Do you have any theories why CommFormer performs so terribly in the Adversarial Pursuit 25 agent case? It performs similarly to ExpoComm in the Battle Environment 20 agent case; I would be interested to hear your theories on why it doesn’t generalize well or performs similarly to ExpoComm in that one case.

A2: Thank you for this thoughtful question. The issue might relate to the asymmetric nature of the AdversarialPursuit tasks. Agents move slower than adversaries and face penalties for failed tagging attempts, which can lead them to become inactive (choose to do nothing rather than trying to tag adversaries). Our analysis shows that CommFormer's training loss and gradients quickly stabilize at low values, indicating early overfitting [3]. This is likely because CommFormer has a larger number of parameters (3-5 times more than other methods), making it more prone to overfitting in this scenario.

Q3:

The performance of ER and ExpoComm are very smilar in the filled bar transferability cases (i.e. K=log2N). Do you have theories about why this is?

A3: Thank you for raising this insightful point! We also observed this phenomenon and included a brief discussion in Section 4.2 (lines 476–479). The strong transferability of both ER and ExpoComm shall result from the global grounding of messages, a design choice we implemented for both our proposed ExpoComm and the ER baseline.

---

References

[1] Rundong Wang, Xu He, Runsheng Yu, Wei Qiu, Bo An, and Zinovi Rabinovich. Learning efficient multi-agent communication: An information bottleneck approach. In Proceedings of the 37th International Conference on Machine Learning, pp. 9908–9918, 2020.

[2] Shengchao Hu, Li Shen, Ya Zhang, and Dacheng Tao. Learning multi-agent communication from graph modeling perspective. In Proceedings of the 12th International Conference on Learning Representations, 2024.

[3] Evgenii Nikishin, Junhyuk Oh, Georg Ostrovski, Clare Lyle, Razvan Pascanu, Will Dabney, and Andr´e Barreto. Deep reinforcement learning with plasticity injection. In Advances in Neural Information Processing Systems, volume 36, 2024.

Q4: How does the proposed method performs compared to traditional mulitcast type of multi-agent communication method such as CommNet, as it seems more global communication is beneficial for the target scenarios?

A4: Thank you for the question, and we would like to provide the following clarifications:

• Unlike ExpoComm, CommNet requires a physical communication proxy to aggregate messages from all agents during execution. This introduces additional hardware requirements for MASs, which is beyond the focus of our work. Without such a proxy, CommNet incurs $N$ (20 to 100) times more communication overhead compared to the $K=1$ case in our experiments. As a result, a direct comparison with CommNet is inherently unfair to ExpoComm and the other baseline methods.
• However, we recognize that this comparison can provide useful insights into the properties of different tasks. And we have included these comparisons in Figure 11 and Table 6 in Appendix C.2. Despite incurring significantly lower communication costs, ExpoComm outperforms CommNet in most scenarios. Interestingly, CommNet shows comparable performance to ExpoComm in AdversarialPursuit tasks, suggesting that a global perspective is crucial in this scenario. This protentially explains the larger performance gap between ExpoComm and other baselines in this scenario.
• Unlike global communication strategies that rely on physical proxies (e.g., CommNet), ExpoComm achieves global communication in decentralized MASs through a carefully designed communication topology. This emphasizes the versatility and scalability of ExpoComm, as it can achieve effective communication without the need for centralized infrastructure.

Q5: How does the proposed exponential graph compared with random selection of communication peers? (keeping the number of communication peers the same)?

A5: This corresponds to the ER baseline in our manuscript, with results presented in Figure 4 and Table 1. Overall, ExpoComm outperforms the ER method in most scenarios. Please see Section 4.2 for a more detailed discussion.

Q6: What are the limitation of this method? Based on the results in Figure 4, the benefit of the method is more obvious for AdversarialPursuit than for Battle. It seems it's only learning after for the Battle environments. Is it learning faster for Battle because there is less communication peers for each node?

A6: Thank you for your questions. We share our thoughts regarding these questions here:

• Limitations: We have updated the manuscript with a subsection discussing limitations and future work (see Appendix C.3). We acknowledge that ExpoComm may not perform well in scenarios requiring more targeted communication, network MDPs, or non-cooperative tasks. We also suggest possible paths to further improve communication performance in many-agent systems.
• Performance in AdversarialPursuit: The larger performance gap may be due to the stronger need for global information in AdversarialPursuit. This is supported by the superior performance of CommNet (see A4) and visualization results in Figure 9. In these tasks, agents move slower than adversaries, requiring more coordinated behaviors and a global perspective to trap adversaries effectively. ExpoComm provides this global perspective, making it particularly well-suited for tasks that demand strong coordination.
• We are not entirely sure we fully understand the remaining part of the question. Could reviewer 56ww clarify what "it's only learning after for the Battle environments" means and what "it" refers to in the next sentence?

We hope these responses and additional experiments address your concerns and encourage you to consider a more favorable evaluation of our paper.

---

References

[1] Kai Cui, Anam Tahir, Gizem Ekinci, Ahmed Elshamanhory, Yannick Eich, Mengguang Li, and Heinz Koeppl. A survey on large-population systems and scalable multi-agent reinforcement learning. arXiv preprint arXiv:2209.03859, 2022.

[2] Lukas M Schmidt, Johanna Brosig, Axel Plinge, Bjoern M Eskofier, and Christopher Mutschler. An introduction to multi-agent reinforcement learning and review of its application to autonomous mobility. In IEEE 25th International Conference on Intelligent Transportation Systems (ITSC), pp. 1342–1349. IEEE, 2022.

[3] Chengdong Ma, Aming Li, Yali Du, Hao Dong, and Yaodong Yang. Efficient and scalable reinforcement learning for large-scale network control. Nature Machine Intelligence, pp. 1–15, 2024.

Thank you for your constructive feedback. Regarding your questions and suggestions, we have updated the manuscripts accordingly (highlighted in blue) and would like to provide clarifications below. If you have any follow-up questions or comments, please let us know, and we will be happy to discuss further.

Q1:

It is unclear how the proposed exponential graph can be helpful for improving agent communication under target scenario. Providing some theoretically analysis or motivating example would be helpful. The toy example is helpful, but random global communication is not considered there.

A1: The proposed ExpoComm enhances agent communication by introducing an topology that propagates information among all agents effectively and at low cost. To support this:

• We analyze the exponential graph properties in Section 3.1.3 (lines 251-292). Specifically, the effective information propagation is enabled by the small-diameter property ($\text{diameter}(\mathcal{G}^t) = \lceil \log_2{(N-1)} \rceil$) and the low cost is ensured by the small-size property ($\lvert \mathcal{E}^t \rvert = N$ for one-peer exponential graph). Following suggestion from reviewer 56ww, we have supplemented the theoretical analysis in Appendix A to provide further support for these properties.
• A toy example in Figure 2 illustrates message dissemination with different graph topologies. We demonstrate a trade-off between graph diameter and size, reflecting the balance between communication performance and overhead in many-agent systems. Exponential topologies strike a balance in this trade-off, showing strong information diffusion even with a minimal communication budget of $N$.
• Extensive experimental results on benchmarks MAgent and IMP in Figure 4 and Table 1 show that ExpoComm outperforms baseline algorithms with the same communication budgets, demonstrating its effectiveness.

To better address the reviewer’s concerns and clear up any misunderstanding, could reviewer 56ww kindly clarify what "random global communication" refers to in the original review?

Q2: Beside the exponential graph, the contribution of this work seems limited. Highlighting and clarifying the contributions of this work would be helpful for better understanding.

A2: Thank you for this suggestion. This work addresses a research gap in scalable multi-agent communication, as most existing strategies are designed for and tested under small-scale systems. Many real-world applications [1,2,3] require communication strategies that scale to dozens or even hundreds of agents. To address this gap, we made the following contributions:

• We propose an exponential topology-enabled communication protocol, ExpoComm, as a scalable solution for MARL communication. It supports effective message dissemination among agents at low cost, enabled by the small-size and small-diameter properties of exponential graphs.
• To fully leverage these properties for efficient information dissemination, we employ memory-based blocks for message processing and auxiliary tasks to ground messages, ensuring they effectively reflect global information.
• Through extensive experiments across twelve scenarios on large-scale benchmarks, including MAgent and Infrastructure Management Planning (IMP), we demonstrate the superior performance and transferability of ExpoComm over existing baseline methods, handling large numbers of agents up to a hundred.

Q3: Evaluation seems incomplete. Comparing the proposed method to the traditional broadcast communication methods can help make the claim more persuasive.

A3: For comparisons with broadcast communication methods, please refer to A4 below. Regarding multicast communication, our original manuscript compares ExpoComm with traditional multicast methods, including CommFormer, ER, DGN+TarMAC, using two different communication budgets ($K = \lceil \log_2{N} \rceil$ and $K=1$). The results in Figure 4 and Table 1 demonstrate the superior performance of ExpoComm compared to these baselines. Please see Section 4.2 for a more detailed discussion.

Thank you for your thoughtful review. We have updated the manuscript accordingly (highlighted in blue) and provide clarifications below. If you have any follow-up questions or comments, please let us know, and we will be happy to discuss further.

Q1: A more explicit discussion of the limitations: tasks reqiuring more targeted communication or non-cooperative tasks.

A1: Thank you for the suggestion. We have included a subsection discussing limitations and future work (see Appendix C.3).

• We acknowledge that ExpoComm may not perform well in scenarios requiring more targeted communication, network MDPs, or non-cooperative tasks. We have identified possible paths to further improve communication performance in many-agent systems.
• Regarding the specific pairwise connectivity mentioned by reviewer 9jpX, this is indeed a very interesting question. Generally, there is a trade-off between adopting a global or local (pairwise) perspective when designing communication strategies in MASs of different scales. A local perspective, which focuses on task-oriented pairwise connectivity, can enhance task-specific performance in small-scale MASs, as shown in previous work [1]. However, it becomes extremely challenging to learn such relationships in large-scale MASs because the number of communication pairs scales quadratically with the number of agents. This observation motivates our ExpoComm, which adopts a global perspective in designing communication topology. While ExpoComm performs well in large-scale many-agent systems, it may not excel in scenarios requiring highly targeted communication. A promising direction for future work would be to design a mechanism that enables a seamless transition between global and local perspectives. Such a mechanism could potentially improve the adaptability of multi-agent communication schemes, allowing them to perform effectively across a wider range of scenarios. We leave this exploration for future work.

Q2: More details and visualization about the experimental setups.

A2: Thank you for the helpful suggestion! We have made the following updates to address this point:

• Expanded Appendix B.2 to include more descriptions of the environmental settings along with snapshots (Figures 7 and 8) to improve clarity and readability.
• Supplemented visualization results for ExpoComm and IDQN (without communication) in both AdversarialPursuit and Battle scenarios in Appendix C.1. These visualizations demonstrate that ExpoComm enhances cooperation by enabling agents to adopt a global perspective. For example, agents exhibit behaviors such as surrounding opponents and allocating more agents to the front lines, even when communication budgets are low ($K=1$). Please see Figures 9, 10, and Appendix C.1 for visualization results and more detailed discussion.

Q3:

In Figures 4 and 6, the x-axis is labeled as "test return," although it appears to show plots related to training return. Could the authors clarify this discrepancy?

A3: Thank you for pointing this out. To avoid any ambiguity, we have updated all y-axis labels to "evaluation return" or "evaluation win rate" (see Figures 4, 6, and 11). To clarify, the y-axis represents the evaluation return during the training process, which is induced by the learned policy without exploration (taking the argmax of Q functions), while the training return is induced by the learned policy with exploration (using epsilon-greedy strategies).

---

References

[1] Shengchao Hu, Li Shen, Ya Zhang, and Dacheng Tao. Learning multi-agent communication from graph modeling perspective. In Proceedings of the 12th International Conference on Learning Representations, 2024.

Thank you for your positive review. Regarding your questions and suggestions, we have updated the manuscripts accordingly (highlighted in blue) and would like to provide clarifications below. If you have any follow-up questions or comments, please let us know, and we will be happy to discuss further.

Q1:

The presentation of section 3.3 is not ideal, e.g. line 323, can you elaborate more on the prediction function f? line 354 to line 355, what is t'?

A1: Thank you for your suggestion. We have improved the readability of Section 3.3 by adding subtitles and rewording the relevant content. Please see the updated section highlighted in blue. The function $f(\cdot; \phi)$ refers to the learnable prediction function used for grounding messages. It is implemented using a two-layer MLP in our experiments (Appendix B.1, line 809). In Equation 5, $t$ and $t'$ refer to the timesteps of negative data pairs.

Q2:

In figure 4(f), why does the test win rate of ExpoComm start to drop from 4*1e6 step?

A2: We acknowledge that there is some performance fluctuation for ExpoComm throughout training in the Battle scenario. Similar fluctuations are also observed for baselines in the same scenario, such as IDQN (green solid line) at $4.5 \times 10^6$ timesteps in Battle w/ 64 agents, DGN+TarMAC (green solid line) at $2.6 \times 10^6$ timesteps in Battle w/ 20 agents and CommFormer (purple solid line) at $4.3 \times 10^6$ timesteps in Battle w/ 20 agents. We suspect this fluctuation may be due to the higher sensitivity of the win rate metric compared to return, as there were no outstanding abnormal patterns in return or loss curves for ExpoComm or the baselines.

Q3:

This algorithm should excel in large-scale multi-agent environment, so can we suppose the performance gap between the algorithm proposed and other baselines should increase when the number of agents increase? If so, why can't we see such trend in figure 4?

A3: To some extent, this is true. Such implications can be observed from the AdversarialPursuit scenario in Figure 4, Uncorrelated and Correlated scenario in Table 1. However, we refrained from explicitly making this claim in our manuscript due to the challenges in rigorously defining the performance gap across different settings. Specifically:

• Comparing returns (or their differences) directly across different settings is problematic, as the returns are defined under different conditions.
• It is unclear which baseline should be selected as the reference algorithm when calculating such a performance gap.