Efficient Multi-agent Reinforcement Learning by Planning

Q8: The authors should demonstrate OS($\lambda$) and AWPO more extensively on (single-agent) decision problems with large action space

We have considered demonstrating the effectiveness of OS($\lambda$) and AWPO in single-agent decision problems with large action spaces. Specifically, we choose LunarLander environment but discretize action space into $400$ actions. Additionally, we select the Walker2D scenario in MoJoCo environment and discretize each dimension of continuous action space into 7 actions, i.e., $6^7 \approx 280,000$ legal actions. Tables 9 and 10 in Appendix D present the results, demonstrating the enhancement of both techniques in terms of learning efficiency and final performance.

• Ablation study on LunarLander.

  Env steps	MAZero	w/o OS($\lambda$) and AWPO
  250k	184.6 ± 22.8	104.0 ± 87.5
  500k	259.8 ± 12.9	227.7 ± 56.3
  1M	276.9 ± 2.9	274.1 ± 3.5

• Ablation study on Walker2D, MuJoCo.

  Env steps	MAZero	w/o OS($\lambda$) and AWPO	TD3	SAC
  300k	3424 ± 246	2302 ± 472	1101 ± 386	1989 ± 500
  500k	4507 ± 411	3859 ± 424	2878 ± 343	3381 ± 329
  1M	5189 ± 382	4266 ± 509	3946 ± 292	4314 ± 256

Q9: In very large action spaces, MCTS with a limited budget (e.g. $N=100$ MCTS simulations as considered in this work) seems very sparse and unlikely to simulate the same action multiple times from a given state. This would significantly weaken the motivation for OS($\lambda$), which relies on simulating each action many times from a given state.

Thank you for highlighting concerns regarding the application of OS($\lambda$) in large action spaces with limited MCTS simulation budgets. We recognize the importance of clarity in explaining our methods and appreciate the opportunity to elucidate further.

OS($\lambda$), as employed in our work, is built upon the framework of Sampled MCTS, wherein each node expansion is conducted exactly once. This is a crucial aspect that seems to have been misunderstood by the reviewer. When a node $u$ is expanded, its set of child nodes, typically limited to a size of $K$ (about $5$ or $10$ in our settings), is determined through an on-policy distribution $\beta$. This 'sampled' aspect ensures that each expanded node receives a unique value estimate through a forward pass of the value network, followed by backpropagation to the root. Later, when an expanded node is revisited, we recursively choose a son of it and do the same thing. Therefore, each expanded node will get its value network forwarded exactly once.

Contrary to the classical sampled MCTS, the final value of a node is the average of all estimations in its subtree (each node $x$ in its subtree constitutes an estimation in the form of $r_1+r_2+…+v(x)$), which is too pessimistic when the model is deterministic and action space is large. This motivates us to design a more optimistic value of expanded nodes.

When action space is large and the simulation budget $N$ is limited, the sampling procedure in classical sampled MCTS restricts the degree of the tree to at most $K$ ($K \ll N$). This restriction enables deeper search depth, mitigating the sparsity issues. While OS($\lambda$) performs optimistic value estimation, enhancing the search efficiency by effectively navigating the limited tree structure.

We hope this clarification underscores the suitability and efficacy of OS($\lambda$) in handling the challenges posed by large action spaces and limited simulation budgets.

Q10: Is MCTS being performed at evaluation time, or is only the learned policy used? If search is being performed at evaluation time, there should be a quantification of the search overhead compared with baselines.

As requested by the reviewer, we have conducted additional ablation study about whether or not perform MCTS in Appendix C, Table 8. Results on SMAC environments show that agents maintain comparable performance without MCTS planning during evaluation.

Q3: There is no experiment in large action space settings like 27_vs_30m.

We are sorry for mentioning 27m_vs_30m in our motivation section while remaining it unevaluated in our experiment section due to the relatively large time consumption for our algorithm in this map (MAPPO uses 10M data for this map). Because of the stress of computing power, we cannot provide another experiment for it. However, we would like to point out that there are still similar tasks like 10m_vs_11m whose action space is $17^{10}\approx 2\times 10^{12}$, which is also considerably larger than the most complex environment evaluated by Sampled Muzero (Go, $361$ actions). Therefore, while we couldn't include 27m_vs_30m, our chosen experiments still showcase the algorithm's robustness in complex environments.

We hope this clarification assures you of our algorithm's applicability to a range of scenarios, including those with large action spaces, even though not all could be directly tested due to resource constraints.

Q4: There’s a lack of experimental validation beyond the SMAC benchmark, and the same benchmarks settings are used across all results and ablations. For example, Google Research Football and Multi-agent MuJoCo would be candidates for other tasks.

We agree on the importance of validating the algorithm's performance in other tasks beyond the SMAC benchmark. It would be beneficial to validate the performance of MAZero in other tasks beyond the SMAC benchmark. We further benchmark MAZero on Google Research Football academy_pass_and_shoot_with_keeper, the result is shown below(see Appendix E, Table 11), where our method outperforms baselines in terms of sample efficiency.

• Comparisons on academy_pass_and_shoot_with_keeper, Google Research Football.

  Env steps	MAZero	CDS	RODE	QMIX
  500k	0.123 ± 0.089	0.069 ± 0.041	0	0
  1M	0.214 ± 0.072	0.148 ± 0.117	0	0
  2M	0.619 ± 0.114	0.426 ± 0.083	0.290 ± 0.104	0

Q5: The SMAC benchmark is outdated and should be replaced by the SMACv2 benchmark, as many tasks have been shown to be trivially solvable due to the lack of stochasticity in the SMAC benchmark.

We appreciate the reviewer for the suggestion. Nevertheless, we did not evaluate MAZero in SMACv2 in our paper for three reasons:

• Focus on Deterministic Environments: The primary focus of our research is deterministic environments, as opposed to stochastic ones. MAZero, building upon the legacy of MuZero, is designed for deterministic models. Our Optimistic Search Lambda technique, in particular, is tailored to leverage deterministic models. While testing on SMACv2 is possible, we believe it might detract from the clarity of our research objectives, which are centered on deterministic settings.
• Baseline Comparability: The SMAC benchmark has been widely used for evaluating numerous baseline algorithms. Some baselines like MAMBA are benchmarked on SMAC, not SMACv2. To facilitate straightforward reproduction of results and ensure fair and relevant comparisons, we opted for the SMAC benchmark. This choice ensures that our findings are directly comparable to a broad range of existing research.
• Relevance of SMAC Despite Low Stochasticity: Even though SMAC is recognized for its lower stochasticity compared to SMACv2, it still presents a meaningful and non-trivial challenge for multi-agent model learning and searching. Evaluating MAZero on SMAC effectively demonstrates our model's capabilities and the efficacy of our search techniques within this context.

We acknowledge the evolving landscape of benchmarks in this field and the potential value of including SMACv2 in future work. However, for the purposes of this paper, we believe that SMAC remains a relevant and suitable choice for demonstrating the strengths and applications of MAZero.

Q6: The baselines used are relatively few compared to other published MARL works. There should be comparison with other recent methods like MBVD, RODE, CDS, etc.

We appreciate the reviewer’s suggestion. We have added RODE and CDS as our baseline (see Figure 3) and results show that MAZero significantly outperform them, especially in terms of sample efficiency. We do not add MBVD as the baseline since we fail to find any open-source implementation of it.

Q7: It’s not clear how many seeds the work used for the main Figure 3. The work mentions 3 seeds for followup ablations, but this is too few to ensure that the performance is not due to luck. The results should be reported across at least 10 seeds.

We have considered the importance of using more seeds for the main Figure 3 to ensure robust evaluation results. We have conducted extra experiments and update Figure 3 with 10 random seeds.

We would like to express our sincere gratitude for your valuable time, constructive comments, and dedication to helping improve the quality of our paper. The insightful feedback have been instrumental in identifying areas for improvement and refining our presentation. In response to your questions and concerns, we have made the following revisions and clarifications:

Q1: The search-based component of methods like MuZero are reduced and not significantly useful for many non-board game tasks.

Thank you for raising concerns about the usefulness of search-based methods like MuZero in non-board game tasks. While it is true that model-free RL has achieved remarkable success in various tasks, it is important to recognize the growing importance of search-based methods, such as MCTS, in recent years.

Although search-based methods may seem less significant compared to model-free RL, they have actually demonstrated valuable contributions across different domains. EfficientZero [1], for example, has achieved impressive results on standard RL benchmarks. According to the paper, it achieves 194.3% mean human performance on the Atari 100k benchmark with only two hours of real-time game experience. Additionally, there are extensions of MuZero in continuous control [2,3] that outperform model-free baselines in terms of data efficiency. These results strongly indicate the effectiveness of search-based methods in these benchmarks.

Moreover, search-based methods have made significant breakthroughs in application domains. For instance, AlphaTensor [4] discovered faster matrix multiplication algorithms, marking the first improvement in this area in 50 years. AlphaDev [5], its sister work, has also found faster sorting algorithms, some of which have been integrated into the standard sort function in the LLVM standard C++ library. Furthermore, these methods have been extended to NP-hard math problems, further demonstrating their potential and applicability.

In the field of AGI research, search-based methods show promise in providing reasonability for LLM-agents. Many recent works [6-8] are exploring the use of search-based methods to enhance the capabilities of large language models, indicating their potential for advancing natural language understanding and reasoning.

Overall, it is crucial to acknowledge that search-based methods have the potential to be utilized in numerous important domains. With this in mind, the objective of this paper is to contribute to the application of search-based methods in the multi-agent domain, serving as a foundation for further exploration and progress in this field.

[1] Ye, Weirui, et al. "Mastering atari games with limited data." Advances in Neural Information Processing Systems 34 (2021): 25476-25488.

[2] Hansen, Nicklas, Xiaolong Wang and Hao Su. “Temporal Difference Learning for Model Predictive Control.” International Conference on Machine Learning (2022).

[3] Hubert, Thomas, et al. "Learning and planning in complex action spaces." International Conference on Machine Learning. PMLR, 2021.

[4] Fawzi, Alhussein, et al. "Discovering faster matrix multiplication algorithms with reinforcement learning." Nature 610 (2022): 47-53.

[5] Mankowitz, Daniel J., et al. "Faster sorting algorithms discovered using deep reinforcement learning." Nature 618.7964 (2023): 257-263.

[6] Yao, Shunyu, et al. "Tree of Thoughts: Deliberate Problem Solving with Large Language Models." arXiv preprint arXiv:2305.10601 (2023).

[7] Feng, Xidong, et al. "Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training." arXiv preprint arXiv:2309.17179 (2023).

[8] Zhao, Zirui, Wee Sun Lee, and David Hsu. "Large Language Models as Commonsense Knowledge for Large-Scale Task Planning." arXiv preprint arXiv:2305.14078 (2023).

Q2: For example, while MuZero utilizes a large search depth for Go, it uses a very small search depth for Atari, which raises the questions of how much performance gain the search component contributes. This work mentions that it uses 5 unroll steps, which is still very small.

It appears there may be a misconception about its role in our model. The ”unroll step” refers to the expansion steps during the model-learning phase and is distinct from the search depth used in the search phase. In our work, we set the unroll step to 5, mirroring the configuration used by MuZero in board games like Go. This setting, while seemingly modest, allows us to maintain a balance between learning a robust model and computational efficiency. It's important to note that despite an unroll step of 5, our model can achieve a search depth exceeding 20, with a total number of simulations ($N$) being 50. This demonstrates that a smaller unroll step is effective and sufficient for learning an accurate model, as also evidenced by MuZero's performance in complex games. We chose this approach primarily for efficiency while ensuring minimal model error.

Thank you for raising the score and acknowledging our rebuttal results. We greatly appreciate your positive response to our additional experiments. Regarding your question about conducting ablation on only two SMAC maps, we specifically chose those maps because they exhibited the most apparent differences. This selection allowed us to effectively highlight the effects of the MCTS improvements. By focusing on these maps, we were able to demonstrate the impact of the ablation more clearly. Furthermore, we would like to clarify that the results presented in Table 3 were evaluated directly using the final model trained with MAZero, rather than starting from scratch. This approach enabled us to compare the performance whether or not conduct MCTS during evaluation in a more practical setting. Furthermore, we have extended the comparison between MAZero and Sampled MuZero across all the maps tested. Please note that in the supplemental experiment, Sampled MuZero uses the shared dynamic network we proposed; otherwise, the performance is very poor in SMAC.

We understand your concerns regarding the limited number of Google Research Football tasks we evaluated. Due to time constraints, we were unable to test our method on multiple tasks. However, we believe that the results we have presented lay a solid foundation for further investigation. We greatly appreciate your open-mindedness and willingness to consider discussions with other reviewers if necessary. We hope that our future work will address these concerns and provide more comprehensive results across a wider range of tasks.

Thank you very much for your thoughtful comments, which have allowed us to improve the quality of our manuscript and to post a revised version. In what follows, we address the raised questions and weaknesses point-by-point.

Q1: Show that they are just as significant in other domains with different types of action and state spaces (continuous, discrete, visual, tabular).

Thank you for highlighting the broader applicability of our work to various domains with different types of action and state spaces. You've rightly pointed out that our current focus with MAZero has been primarily on discrete environments. In an effort to extend our evaluation to continuous tasks, we employed a method of discretizing the continuous action space into a larger discrete action space. The results of this adaptation can be seen in Tables 9 and 10 of our paper, where MAZero demonstrates notable performance advantages in comparison to baseline algorithms. Due to the time limitation, we do not evaluate MAZero on visual and tabular tasks.

Q2: Use the evaluation protocol of Gorsanne et al (https://arxiv.org/abs/2209.10485)

We agree on the importance of utilizing standard evaluation protocol within the community. Because of the stress of computing resources and limitation of time, we cannot restart the whole experiments under such a standard protocol during the response period. We will reorganize the results of all experiments in the next few weeks.

Q3: No discussion is given to hyper parameter tuning, or the choice of hyper-parameters for the baselines that MAZero is being compared against.

We have discussed some crucial hyper-parameters (e.g. $\rho, \lambda$ used in OS($\lambda$)) in ablation study in Appendix C. Detailed hyper-parameters are provided in Table 1, which are common settings in Sampled MuZero and EfficientZero.

We have added the choice of hyper-parameters for the baselines in Appendix B.3.

Q4: Is Figure 1 a single seed? It looks remarkably smooth.

We appreciate the reviewer’s careful observation! Yes, only a single seed is used, and it is done intentionally. We will briefly explain the motivation here, the full experimental setting, and details were listed in Appendix B.4. The aim of this experiment is to compare the behavior of these two different loss functions, i.e., BC and AWPO. To ensure that the comparison was as controlled and unbiased as possible, we eliminated potential variables that may influence the outcome. In this way, we

• eradicate the randomness in policy evaluation by calculating the expected reward to evaluate the policies.
• choose the same parameterization (softmax policy), and the same random seed (which only affects the initialization of the policy weights), this is why these two curves have the same starting point.
• eliminate the randomness in SGD optimization, where the stochasticity comes from the randomness of sampling the subset (cf. Sampled MCTS) by calculating the expectation of the loss (the formula can be found in Appendix B.4), that is why these curves look smooth.

We hope this explanation clarifies the rationale behind our experimental setup and the resulting smoothness observed in Figure 1.

Thank you for your quick response. In response to your concerns about the experiments, we have conducted additional experiments beyond the SMAC environments. These experiments include LunarLander, MuJoCo, and Google Research Football. The results presented in Tables 9, 10, and 11 demonstrate the advantages of our algorithm across a diverse range of environments. Furthermore, we have also conducted experiments with an increased seed data. In future versions, we will prioritize considering the evaluation protocol you recommended.

• Experiments on LunarLander.

  Env steps	MAZero	w/o OS($\lambda$) and AWPO
  250k	184.6 ± 22.8	104.0 ± 87.5
  500k	259.8 ± 12.9	227.7 ± 56.3
  1M	276.9 ± 2.9	274.1 ± 3.5

• Experiments on Walker2D, MuJoCo.

  Env steps	MAZero	w/o OS($\lambda$) and AWPO	TD3	SAC
  300k	3424 ± 246	2302 ± 472	1101 ± 386	1989 ± 500
  500k	4507 ± 411	3859 ± 424	2878 ± 343	3381 ± 329
  1M	5189 ± 382	4266 ± 509	3946 ± 292	4314 ± 256

• Experiments on academy_pass_and_shoot_with_keeper, Google Research Football.

  Env steps	MAZero	CDS	RODE	QMIX
  500k	0.123 ± 0.089	0.069 ± 0.041	0	0
  1M	0.214 ± 0.072	0.148 ± 0.117	0	0
  2M	0.619 ± 0.114	0.426 ± 0.083	0.290 ± 0.104	0

Thank you very much for your strong support recognizing the novelty of our work. We additionally are grateful for your comments and questions that we aim to address point-by-point in what follows.

Q1: How does MAZero perform in stochastic environments compared to deterministic ones?

Our algorithm primarily focuses on deterministic environments, as stated in this paper. We have developed a deterministic model based on the previous work of Muzero. Our OS($\lambda$) technique is specifically designed to optimize this deterministic model. However, we have also conducted additional experiments beyond the SMAC environments, including LunarLander, MuJoCo, and Google Research Football, which exhibit more randomness compared to SMAC. The results in Tables 9, 10, and 11 demonstrate that MAZero performs well to some extent in stochastic environments.

• Ablation study on LunarLander.

  Env steps	MAZero	w/o OS($\lambda$) and AWPO
  250k	184.6 ± 22.8	104.0 ± 87.5
  500k	259.8 ± 12.9	227.7 ± 56.3
  1M	276.9 ± 2.9	274.1 ± 3.5

• Ablation study on Walker2D, MuJoCo.

  Env steps	MAZero	w/o OS($\lambda$) and AWPO	TD3	SAC
  300k	3424 ± 246	2302 ± 472	1101 ± 386	1989 ± 500
  500k	4507 ± 411	3859 ± 424	2878 ± 343	3381 ± 329
  1M	5189 ± 382	4266 ± 509	3946 ± 292	4314 ± 256

• Comparisons on academy_pass_and_shoot_with_keeper, Google Research Football.

  Env steps	MAZero	CDS	RODE	QMIX
  500k	0.123 ± 0.089	0.069 ± 0.041	0	0
  1M	0.214 ± 0.072	0.148 ± 0.117	0	0
  2M	0.619 ± 0.114	0.426 ± 0.083	0.290 ± 0.104	0

Q2: Can the proposed OS($\lambda$) and AWPO techniques be applied to other model-based MARL algorithms?

OS($\lambda$) and AWPO are specially designed for MCTS algorithms. We don’t think it can be applied to other model-based MARL algorithms like the dreamer-based MBMARL algorithms (e.g. our baseline method MAMBA).

Q3: Are there any potential drawbacks or limitations of the proposed network structure that the authors have not discussed?

We recognize the limitations of the proposed network structure and have outlined potential drawbacks. Some potential drawbacks or limitations of the proposed network structure include:

• The reliance on centralized training, which may not scale well to very large numbers of agents or highly heterogeneous environments.
• Although MAZero is more sample-efficiency than model-free MARL method, it is relatively computationally expensive.

Thank you very much for your positive recommendation of our work and your insightful comments. Following are our responses to your concerns.

Q1: It seems that the method assumes that the agents have access to the global reward at each step during inference?

The MAZero algorithm is designed under the CTDE framework, which means the global reward allows the agents to learn and optimize their policies collectively during centralized training. The predicted global reward is used in MCTS planning (inference) to search for a better policy based on the network prior. Ablation study in Appendix C, Table 8 shows that agents maintain comparable performance using the final model without global reward, communication or planning.

Q2: In Figure 6, please clarify the difference between communication and sharing.

We have provided a clearer explanation of the differences between communication and sharing in Figure 6.

• Communication: This refers to the exchange of information between agents to facilitate cooperation. In the MAZero algorithm, communication is achieved through an additional communication block using the attention mechanism. This allows agents to share their individual latent states and promote cooperation during the model unrolling process. “No communication” means the Centralized Dynamic Block in Figure 2 only contains the Shared Individual Dynamic Network g.
• Sharing: This refers to the parameter sharing among agents in the centralized-value, individual-dynamic model, which is a common technique for multi-agent reinforcement learning. By sharing parameters, the model can capture the homogenous behavior of agents and improve learning efficiency. “No sharing” means there is no parameter sharing in representation function h, dynamic function g and policy prediction function P in Equation (4), i.e., agents learn network individually.

Q3: Section 3.1, the discussion about the degree to which a homogeneous solution is a good one is interesting and certainly depends on the particular scenario, but it isn’t clear how the MAZero fits into this.

MAZero fits into the discussion of homogeneous solutions through parameter sharing, which has underscored the huge success in model-free MARL methods. More specifically, agents share representation network, policy prediction network and individual dynamic network, thus exhibit homogeneous behavior when facing the same situation or input similar observations.

Q4: Could you say more about the Shared Individual Dynamic Network $g_\theta$ ? Perhaps it is just the terminology but the idea seems confusing.

We have offered additional clarification on the Shared Individual Dynamic Network $g_\theta$ and its role in the model in the revised version. The Shared Individual Dynamic Network $g_\theta$ is responsible for deriving the subsequent local latent state $s_{t,k+1}^i$ of each agent $i$ based on its individual current latent state $s_{t,k}^i$ , individual action $a_{t,k}^i$, and communication feature $e_{t,k}^i$. The term "Shared Individual Dynamic" refers to the combination of shared parameters among agents (to capture homogenous behavior) and individual dynamic modeling for each agent (to capture local information input).

Q5: Section B.1, could you say more about how to “use positional encoding to distinguish agents in homogeneous settings”?

Positional encoding is a detailed implementation of the self-attention block in the Communication network $e$. Using positional encoding to distinguish agents in homogeneous settings means that the algorithm incorporates the relative positions of agents in the environment to differentiate between them. This helps the model to learn distinct communication features for each agent, even when their actions or observations are similar.

Q6: Appendix C, why do you think Adam is more effective than stochastic gradient descent? Isn't this well known?

While it is well-known that Adam often performs better than stochastic gradient descent (SGD) in many cases, especially for multi-agent reinforcement learning[1], muzero-based algorithms tend to use SGD optimizer[2-4]. So we provide the ablation study to demonstrate the effectiveness of Adam optimizer specifically for our MAZero algorithm. The results show that Adam leads to superior performance and more consistent stability in the experiments.

[1] Yu, Chao, et al. "The surprising effectiveness of ppo in cooperative multi-agent games." Advances in Neural Information Processing Systems 35 (2022): 24611-24624.

[2] Schrittwieser, Julian, et al. "Mastering atari, go, chess and shogi by planning with a learned model." Nature 588.7839 (2020): 604-609.

[3] Hubert, Thomas, et al. "Learning and planning in complex action spaces." International Conference on Machine Learning. PMLR, 2021.

[4] Ye, Weirui, et al. "Mastering atari games with limited data." Advances in Neural Information Processing Systems 34 (2021): 25476-25488.