Solving Homogeneous and Heterogeneous Cooperative Tasks with Greedy Sequential Execution

Thank you for your thoughtful questions and feedback on our paper. Below, we provide detailed responses to each of your questions:

1. The algorithm is tested exclusively on specially designed tasks.

   a. Our work aims to address the challenge of learning both homogeneous and heterogeneous policies simultaneously in value decomposition methods. Therefore, it is crucial to validate our approach in tasks that require both types of policies. Unfortunately, existing environments such as SMAC, GRF, and overcooked do not meet this requirement, which necessitated the design of new scenarios.

   b. Furthermore, the tasks encompass a variety of behaviors necessary for completion, and the effectiveness of a task is influenced not just by the environment, but also by the nature of the policy required for its completion. In the environments we have utilized, agents are required to concurrently learn both homogeneous and heterogeneous policies. This dual learning requirement substantially elevates the complexity of these tasks, making them challenging and rich in diversity.

2. About a more detailed description of the ablated algorithms and a clearer explanation of the results.

   We provide the following clearer explanation of the results in our ablation study and modify the revision accordingly:

   a. Ablation of Greedy Actions: Our first ablation test involved evaluating our method without using greedy actions, meaning we relied on marginal contributions instead of greedy marginal contributions. The results indicated a significant performance degradation when greedy actions were not utilized. This finding aligns with our analysis in Section 4.2, where we discussed how using greedy actions helps overcome the relative over-generalization problem.

   b. Ablation of Marginal Contributions: The second ablation focused on evaluating our method without marginal contributions. In this scenario, we did not use the critic as proposed in Section 4.1 and directly fitted the policy value function Q_s^i to Q_{tot}. The results demonstrated the challenges of using an implicit credit assignment method to learn the policy when the sequential execution policy does not satisfy the IGM principle, underscoring the importance of our proposed critic.

   c. Effect of Number of Sampling in MC Method: We also investigated the impact of varying the number of sampling in the Monte Carlo (MC) method. The findings showed that a small number of samples could lead to suboptimal action selection, failing to identify the greedy value of actions. Conversely, a sufficiently large number of sampling (beyond 5) did not yield additional performance improvements, indicating an optimal range for the number of sampling.

   d. Performance with Increased Numbers of Agents: Lastly, we tested our method in the Lift task with double and triple the number of agents. These results affirmed our method's robustness, demonstrating effective performance management even with a larger number of agents.

   We believe these clarifications provide a comprehensive understanding of the key components and functions in our algorithm, as well as the implications of each ablation test conducted.

3. About the additional time required for training and evaluation.

   It is true that the sequential execution in GSE necessitates more time per step, as each agent calculates its action sequentially. This additional execution time can be estimated as (n-1)*t for n agents, where t is the time taken by each agent to produce its action. However, it's important to note that this sequential execution primarily impacts the execution phase and not the training phase. During training, as the transitions are collected, the sequential nature of execution does not impede the parallel processing capabilities. Therefore, the additional time required during training is mitigated. We appreciate the suggestion to focus on minimizing additional execution time. We have included a discussion about this limitation in our work, underscoring its significance. Thank you for this valuable input.

4. During training, is the execution sequence of all agents fixed, or do you shuffle the sequence?

   We employ a fixed order for the execution sequence of agents, which is determined based on the agent IDs.

5. What does 'training with a larger scale of agents' mean in Section 6.3 & Figure 6?

   We tested our method in the Lift task with double and triple the number of agents. These results affirmed our method's robustness, demonstrating effective performance management even with a larger number of agents.

Thank you once again for your constructive feedback. We believe that your insights have helped us to improve the clarity and quality of our paper.

Thank you for your thoughtful questions and feedback on our paper. Below, we provide detailed responses to each of your questions:

1. Figure 2 with the architecture is hard to read and not well explained.

   We have added a more detailed description to accompany Figure 2 in our manuscript. This includes:

• Upper (Blue): A depiction of the critic architecture that we elaborated on in Section 4.1.
• Lower (Green): An illustration of the framework used for calculating the greedy marginal contribution. This is based on $Q_c^i$ and $V_c^i$, as well as the sequential execution policy $Q_s^i$.

2. How is the number of actions of Monte Carlo method selected?

   The number of actions selected for this estimation process is treated as a hyperparameter in our method. In our ablation studies, we have evaluated the effect of different numbers of sampling on the final results. Specifically, we examined how the sample number M affects performance. The results demonstrate that a small value of M can be problematic as it may not select the greedy value of actions. However, a reasonably large value of M is sufficient as increasing M beyond 5 does not further improve performance.

3. About the size of the map in Overcooked and scenarios with a larger number of agents.

   To provide a clearer understanding of the environment's complexity, we have included more detailed information about the Overcooked scenario and schematic representations of the maps in the appendix. The sizes of the maps used in our experiments are 5x5 for easy and medium and 7x7 for hard.

   Regarding the exploration with a larger number of agents, we have conducted evaluations in the Lift task using double or triple agents. The results of these evaluations are presented in the fourth figure of Figure 6. These results demonstrate that our method effectively handles a larger number of agents, maintaining performance without significant degradation.

Thank you once again for your constructive feedback. We believe that your insights have helped us to improve the clarity and quality of our paper.

Thank you for your thoughtful questions and feedback on our paper. Below, we provide detailed responses to each of your questions:

1. Discuss more in detail in Overcooked.

   The performance in the Overcooked environment is impacted by a variety of factors. Our settings of difficulty are calibrated based on the ease of discovering rewards. In simpler scenarios, characterized by more interactive objects and smaller maps, agents have increased opportunities for interaction. This design, while lowering the barrier for exploration, potentially escalates the difficulty of policy learning as agents progress. For instance, in scenarios with multiple onions, agents may quickly learn the value of picking up an onion. However, as they develop, they might attempt to pick up different onions, leading to mis-cooperation. This issue is less likely in harder scenarios with fewer onions. These are the reasons that lead to some degree of fluctuation. However, since the primary challenge of learning is relative overgeneralization and the difficulty in discovering successful instances, our setting is appropriate. We have added a discussion about this phenomenon in our work. Thank you once again for this suggestion.

2. It is better instead to introduce the comparison methods in Section V.

   We have reorganized the content to introduce the comparison methods directly in Section V. We believe that this revised order will enhance the readability and coherence of our manuscript, making it easier for readers to follow the logic and rationale behind our comparative analysis.

3. It is worth including graphically the map for the overcooked environment.

   We have included images of the map in the appendix of our manuscript.

4. About citation.

   We have revised the citation format throughout our manuscript. We have also updated the manuscript to include the correct publication venues for referenced papers. We appreciate your guidance on these matters and believe these revisions enhance the accuracy and professionalism of our manuscript.

Thank you once again for your constructive feedback. We believe that your insights have helped us to improve the clarity and quality of our paper.

In summary, while both our method and MAT aim to improve the performance of cooperative multi-agent systems, they do so from different perspectives and using different techniques. We believe that our approach offers a novel and effective solution to the challenges of learning both homogeneous and heterogeneous policies simultaneously when using value decomposition methods in multi-agent systems. Its efficiency is further validated through comparisons with other value decomposition methods.

Thank you once again for your constructive feedback. We believe that your insights have helped us to improve the clarity and quality of our paper.

[1] Wen, Muning, et al. "Multi-agent reinforcement learning is a sequence modeling problem." Advances in Neural Information Processing Systems 35 (2022): 16509-16521.

[2] Dou Z, Kuba J G, Yang Y. Understanding value decomposition algorithms in deep cooperative multi-agent reinforcement learning[J]. arXiv preprint arXiv:2202.04868, 2022.

[3] Wang J, Ren Z, Liu T, et al. QPLEX: Duplex Dueling Multi-Agent Q-Learning[C]. International Conference on Learning Representations. 2020.

[4] Shen S, Ji M, Wu Z, et al. An optimization approach for worker selection in crowdsourcing systems[J]. Computers & Industrial Engineering, 2022, 173: 108730.

[5] Landinez-Lamadrid D C, Ramirez-Ríos D G, Neira Rodado D, et al. Shapley Value: its algorithms and application to supply chains[J]. INGE CUC, 2017, 13(1): 53-60.

1. Utility Functions Structure:

   b. Unique challenges of different paradigms: Regarding policy gradient (PG) methods, as we all know, value-based methods and PG methods represent different paradigms in MARL, each with its own features. Value decomposition approaches utilize the IGM principle to model the global maximizer of the joint state-action value function as the combination of individual agent value maximizers, providing a clear and scalable optimization strategy [2][3]. Yet, IGM may not always be applicable, such as in sequential execution scenarios. This limitation is precisely what we have addressed in our work. Conversely, PG methods typically extend single-agent actor-critic algorithms to multi-agent contexts, where the critic is trained on joint observations’ value function. While PG methods like MAPPO demonstrate empirical successes, they struggle with ensuring monotonic improvement, prompting methods like HAPPO, which specifically address this issue to enhance previous PG methods. This distinction in paradigms highlights the unique challenges and methodologies that our research brings to MARL. The table illustrates that our focus is on addressing issues pertinent to value decomposition methods, positioning our work in closer relation and comparison to other methods within this framework.

Next, we will delve into the unique aspects of credit assignment in our method, focusing on how it addresses the issue of relative over-generalization and implements explicit credit assignment techniques.

2. Credit assignment:

   a. Overcome the problem of relative over-generalization: Our method introduces a novel approach to credit assignment through the concept of greedy marginal contribution to address potential issues of mis-cooperation, often referred to as the relative over-generalization problem. This problem typically arises when agents executing earlier in the sequence lack crucial information about the subsequent actions of their counterparts. Our method of greedy marginal contribution employs optimal cooperative actions to calculate marginal contributions in collaboration with preceding agents. This approach directly addresses and compensates for information asymmetry, leading to more effective and accurate credit assignment. In contrast, MAT adopts advantage value decomposition within the structure of a transformer. This design is aimed at executing updates both monotonically and in parallel, thereby enhancing the time efficiency compared to previous methods like HAPPO. However, it does not specifically address the relative over-generalization problem of the value decomposition methods, which is a central concern in our approach. By focusing on the optimal cooperative policy and addressing potential mis-cooperation, our method’s credit assignment differentiates itself significantly from the advantage value decomposition used in MAT.

   b. Explicit credit assignment: Our method enables explicit credit assignment by utilizing the marginal contribution of Shapley values. It allows us to compute the credit value of an individual agent's action at a single timestep, which can be applied to reward distribution on recruitment [4] or for pricing [5]. In contrast, MAT cannot compute a credit value for a single observation and action pair, as the utility is based on joint observations. Therefore, our solution offers broader applicability in more realistic settings.

Next, we will discuss the proposal and contributions of using sequential execution in different methods.

3. Propose of using sequential execution:

   a. Different objectives: Our work delves into why existing value decomposition methods fail to simultaneously represent both homogeneous and heterogeneous policies. Through this analysis, we introduce the concept of greedy sequential execution as a novel solution. The core contribution of our research lies not merely in proposing a new sequential execution method, but in innovatively applying this concept within the context of value-based methods by proposing an IGM utility function as well as the greedy sequential execution to solve the relative over-generalization problem. These problems have not been analyzed and solved before and are important for the value decomposition method to be implemented in real-world scenarios. In contrast, MAT does not directly address the challenge that merely using sequential execution policies does not conform to the IGM principle and cannot solve the relative over-generalization problem. This is because MAT leverages transformer structures to achieve on-policy and monotonic performance enhancement within the framework of PG methods, without specifically addressing the challenges we focus on. Therefore, MAT is not suitable to be compared as a baseline in our setting.

Thank you for your suggestion! In the following, we use MAT to refer to your suggested work [1]. According to your suggestion, we have now explicitly discussed the relationships between our solution and MAT in the related works of our revision. This discussion also involves HAPPO, which is the base of MAT. We now summarize the differences between our work and these methods for your reference.

The contributions of our method are as follows:

1. Our proposed utility function adheres to the Individual-Global-Maximum (IGM) principle, with the policy depending solely on local observation.

2. Our method analyzes and can overcome the problem of relative over-generalization.

3. Our method achieves explicit credit assignment.

4. The policy utilizes sequential execution to learn both homogeneous and heterogeneous policies.

In the table below, we compare the characteristics of our method with MAT, HAPPO, as well as our selected baselines in the paper (QMIX, CDS, MAVEN, Shapley). It is evident that compared to baseline methods, HAPPO and MAT have less relevance to our method, as they only use sequential execution to achieve monotonic improvement.

First, we will explore the distinctions in utility function structures between value decomposition and policy gradient (PG) methods, and the unique challenges each approach presents in multi-agent reinforcement learning.

1. Utility Functions Structure:

   a. We adhere to IGM principle and only requires local observation, whereas MAT requires joint observations: In our approach, we introduce a distinctive value decomposition framework implemented by a versatile utility function. This utility function is designed to accurately represent reward function while strictly adhering to the IGM principle. This adherence is crucial as it facilitates more effective credit assignment in multi-agent settings, a key aspect of our research's contribution to value decomposition methods. By adhering to the IGM principle, our utility and policy functions depend exclusively on local observation for decision-making. In contrast, MAT adopts policy gradient (PG) approaches, utilizing the transformer's encoder as its value function and the decoder as the policy structure, necessitating joint observations to generate actions.

Thank you for the clarification, which makes the contributions of this work more clear and specific, especially the 2.a & 2.b.

Just a personal thought, the Explicit credit assignment with greedy marginal contribution is the most attractive contribution of this work in the field of value-decomposition methods for cooperative MARL. But the original writing spent too much in emphasizing handling both homogeneous and heterogeneous (actually, it is not a new topic currently), which instead led to obscuring the contribution of the explicit credit assignment as well as locating this work into an unnecessarily over-large scope. In other words, if this work mainly claims that "we propose a new framework that addresses both homogeneous and heterogeneous scenarios well", you have to compare it with other existing works that address both homogeneous and heterogeneous scenarios like the MAT to prove this work is non-trivial (since from the title of the article, the MAT can also be described similarly as "SEQUENTIAL EXECUTION: SOLVING HOMOGENEOUS AND HETEROGENEOUS COOPERATIVE TASKS WITH A UNIFIED FRAMEWORK"). Otherwise, if the main claim of this work is a novel value-decomposition method that is capable of both homogeneous and heterogeneous agents, the comparison is unnecessary but the scope of contribution in the original writing should be adjusted and explained a bit according to the rebuttal provided by authors (this rebuttal is more specific about the scope of this work then that in the original writing).

It is overall a writing issue instead of a technical issue, if authors can make sure to address my concerns in the later version, I am willing to update my score to positive.

Minor issue: Similar reason to the above discussion, the beginning sentences in the abstract "Effectively handling both homogeneous and heterogeneous tasks is crucial for the practical application of cooperative agents. However, existing solutions have not been successful in addressing both types of tasks simultaneously." are misleading without a correct specification about the scope of this paper. (Is MAT an existing solution in addressing both homogeneous and heterogeneous tasks? Is it successful? If not, why?)

Thanks for providing the revision, this revision is clearer about the scope of this paper and has addressed most of my concerns. I am delighted to increase my score.