Value Factorization for Asynchronous Multi-Agent Reinforcement Learning

We appreciate Reviewer eKQs’ positive evaluation of our work and we thank the reviewer for the insightful questions. We believe our revised paper has significantly improved by addressing your doubts. In the following, we summarize the changes in the manuscript that answer your questions.

• We agree the background section could appear rushed as we omitted a few details to fit the page limit. We revised it, including a definition for Q, clarified the meaning of $\tau$, and further detailed the limit of QPLEX’s decomposition (discussed in the next point). We kindly ask the reviewer to point out any additional missing details in Section 2 that we will carefully incorporate.

• Regarding Adv-IGM, we agree the non-positive nature of the advantage function is an intrinsic property of it. However, considering the discussion in the dueling networks’ work [A], allowing the advantage function to assume arbitrary values typically leads to significantly higher performance. As such, Adv-IGM represents a more general condition as it will allow future factorization schemes to learn arbitrary advantage functions, inheriting the benefits of the single-agent dueling networks case. For example, the decomposition of Eq. 4 could be avoided by employing a principled version of dueling networks, where agents learn separate streams for state and advantage value functions (without any value restriction). This is an exciting direction to investigate in the future but goes beyond the scope of our paper.

• Regarding Cen-MADDRQN, we performed additional experiments (each over 20 independent runs) in the most complex domains: BP-30, WTD-T1, and CT-10 (Table 1 and Appendix E). In CT-10, Cen-MADDRQN showed poor performance due to the high number of agents employed in the task. Similarly, Cen-MADDRQN also has lower performance in WTD-T1 with respect to our best-performing solution, AVF-QPLEX. Conversely, BP-30 is characterized by a few agents and a joint observation of limited size, and the fully centralized baseline obtains higher performance than AVF methods.

• Regarding the results of different mixers, extending factorization methods to asynchronous MARL requires the asynchronous buffer and the use of temporal consistent joint information. The underlying mixing architectures of the primitive algorithms remain the same, and it makes sense the general results are the same in the primitive setting. The added value in our experiments is the ablation study conducted to support our claims on the importance of temporal consistency. Without using a joint macro-state, in fact, AVF methods fail at solving even the easiest macro-action tasks (BP-10 and WTD-S).

• Concerning the ablation study, we performed an additional set of experiments in BP-10. In particular, the new Figure 5 shows how AVF methods based on the true state fail at solving the easiest configuration of BP and WTS. The high number of independent runs we consider in all our experiments is also a strong indicator of the significance of these results. We further enhanced our ablation study by considering AVF-{QMIX, QPLEX} employing the only macro-state of the agent which terminated its macro-action (i.e., the second mechanism discussed in Section 3.2.). As expected, the noise introduced by such a method leads to significantly lower performance than the joint macro-state employed in Fig. 5, but represents a better-performing solution than using the true state.

• We agree Table 2 is confusing. We wanted to show how primitive-action methods fail in the easiest (primitive) task, BP-10, to highlight the complexity of the benchmarks employed in the macro-action literature. Conversely, when comparing with the state-of-the-art Mac-IAICC, we used the most complex scenarios to highlight the superior performance of AVF. Following our additional experiments with Cen-MADDRQN, we moved the comparison with primitive methods in Appendix D.1, and discuss the comparison with Mac-IAICC and Cen-MADDRQN in Appendix E. We believe such a revision significantly improves clarity, but we remain available to further revise our manuscript if you believe that would further improve our work.

• There has been a misunderstanding on the results of the primitive-action algorithms. We tested the primitive version of VDN, QMIX, and QPLEX in the primitive version of BP-10 presented in (Xiao et al., 2020a). These primitive methods only employ 1-step moving and pushing actions, as they cannot employ the temporally extended actions of their asynchronous counterpart. We added a description of the primitive BP in Appendix D.1. As clearly stated in Section 4, we remark such a comparison is not fair since primitive methods cannot leverage the expert knowledge of low-level policies used by macro-action-based methods. Intuitively, this is why their performance is not on par with the asynchronous versions.

[A] Z. Wang et al., “Dueling Network Architectures for Deep Reinforcement Learning,” ICML, 2016.

Thank you for your additional feedback. We tried to keep our previous responses as concise as possible, so we apologize if they were not sufficiently clear. In the following, we provide further clarifications.

2. Regarding the advantage function, by its definition $A^\pi(s, a) = Q^\pi(s, a) − V^\pi(s)$ we get that optimal advantage value functions are indeed non-positive. However, in practice (and during training), we typically use function approximators with linear outputs to learn either $A^\pi(s, a), Q^\pi(s, a)$, or $V^\pi(s)$. As such, these functions can assume positive values during training but have non-positive values when converging to the optimal functions.

We remark on two widely-applied examples in the literature that exploit positive advantage value functions, to further motivate why this could help in practice:

• In value-based algorithms, dueling networks showed how learning $V^\pi(s), A^\pi(s, a)$ separately, significantly improves sample efficiency and performance. In particular, authors show that forcing the advantage function estimator to have zero advantage at the chosen action (i.e., the locally-optimal action at that step of training), has significantly lower performance than having positive advantages as the latter increases the stability of the optimization [A].
• In policy-gradient algorithms, a step in the policy gradient direction should increase the probability of better-than-average actions and decrease the probability of worse-than-average actions. To this end, when using the advantage value function to measure whether or not the action at step $t$ is better or worse than the policy’s default behavior. We have that the gradient term $A^\pi(s_t, a_t)\nabla_\theta \pi_\theta(a_t|s_t)$ points in the direction of increased $\pi_\theta(a_t|s_t)$ if and only if $A^\pi(s_t, a_t) > 0$ [B, C].

For this reason, we formalized our advantage-based version of Mac-IGM to also consider positive advantages. While this is not relevant for applying previous factorization methods to macro-actions, it would allow future research to build on existing methods (e.g., dueling networks) to design more efficient and scalable algorithms.

3. Regarding the results, they are key to support the claims of our paper.
   • The fact that the performance "ranking" of the methods follows the primitive-action case, shows that our formalization based on MacDec-POMDPs is sound and works well in practice.
   • They demonstrate the importance of the temporal-consistency problem that has not been considered by macro-action literature before. In particular, introducing the joint macro-state is a simple yet powerful way to address such an issue.
   • These results also serve to compare previous macro-action-based works, showing that (i) it is possible to design principled value factorization methods for asynchronous Multi-Agent Reinforcement Learning (MARL), (ii) these CTDE value-based algorithms perform better than the current asynchronous MARL.
   • Considering the superior performance over existing methods, our results set a new baseline for future CTDE macro-action-based works.

5. There are still some misunderstandings about the primitive-action environments. In particular, an asynchronous task with unitary action duration is a primitive task (we never refer to such setups as an asynchronous task with unitary action, since unitary actions make agents synchronous, or primitive). As such, there is no difference between primitive environments/algorithms and their unitary asynchronous counterparts (since the latter are simply primitive environments/algorithms). The reason why we reported results for the primitive-action factorization methods is twofold:

• These results remark on the complexity of the standard benchmark scenarios employed by the macro-action literature. In particular, the original (primitive) approaches (VDN, QMIX, QPLEX) fail at solving even the easiest setups (as discussed in our response to Reviewer mc14).
• We further motivate the importance of employing macro-action-based methods as they successfully scale to higher-dimensional problems with a higher number of agents with different roles.

We hope these additional comments helped to clarify some of your doubts and again, we appreciate your engagement and comments that we believe allowed us to improve our work. We remain available to further discuss our manuscript during these last days of the discussion period.

[A] Z. Wang et al., “Dueling Network Architectures for Deep Reinforcement Learning,” ICML, 2016.

[B] J. Schulman et al., "High-dimensional continuous control using generalized advantage estimation," ICLR, 2016.

[C] J. Schulman et al., "Proximal Policy Optimization Algorithms," arXiv, 2017.

We would like to thank the reviewer for the constructive discussion that helped us improve our original submission. We will incorporate your last suggestions in the next paper revision, and remain available to clarify any other questions that might arise before the end of the discussion period.

Best Regards,

The Authors

We thank Reviewer mc14 for acknowledging the interesting nature of asynchronous MARL. However, we believe several misunderstandings hindered the evaluation of our work; we clarify these below.

• Regarding the impact of IGM on macro-actions, we believe the claim that “existing value factorization algorithms can inherently fulfill this requirement as long as state and action representations are adjusted in accordance with prior research” is severely misleading. In the following, we clarify our point of view, which also addresses the two reviewer's questions. Without Mac-IGM and MacAdv-IGM, existing value factorization algorithms with adjusted state and action representations would not satisfy the action selection consistency, since Mac-IGM and MacAdv-IGM must consider what happens at the centralized level and decentralized level, separately. For example, while the latter follows from the definition of a macro-action (i.e., agent $i$) selects a new macro-action based on the termination condition $\beta_i$ of the low-level policy of the previously executed macro-action), the former requires the conditional operator discussed in Eq. 5. Moreover, MacAdv-IGM relaxes the assumptions of Adv-IGM on the non-positive advantage values, while still guaranteeing consistency in the action selection as shown in the proof provided in Appendix A. Finally, the formalization of Mac-IGM and MacAdv-IGM also allowed us to draw conclusions about the relationships over the primitive case. In particular, we demonstrated how they represent more general classes of functions with respect to their primitive counterparts. It is worth remarking on the temporal consistency problem we discussed in Section 3.2 as naive implementations of asynchronous value factorization methods considering the actual state of the environment introduce significant noise in the training process, leading to policies that fail at solving even the most simple tasks (Fig. 5).

• Regarding the experimental scenarios, the reviewer’s claim “The experimental scenarios employed in this study are simplistic.” also deems scarce attention to our experiments and limited knowledge of the asynchronous MARL literature. We used most of the environments proposed in the latter, including a more complex version of the capture-target domain. In addition, our response (as well as previous macro-action works such as Xiao et al., 2020a) shows that previous synchronous, primitive approaches fail to solve even the most simple setup (BP-10). This is clear evidence of the complexity of these tasks that, we remark, represent the standard benchmark in the asynchronous MARL literature. The complexity arises from a high degree of partial observability, combined with strong coordination requirements; characteristics that represent a serious challenge for existing MARL methods.

As demonstrated by our responses to the other reviewers, we take all the feedback into serious consideration as they can help improve our manuscript. As such, we look forward to engaging in a fruitful discussion with Reviewer mc14 to further clarify any doubts regarding the proposed theory or methodology contributions.

We thank Reviewer JQAT for the comments about our work that helped us improve our manuscript, as shown in the updated submission. In the following, we summarize the papers’ modifications that address the reviewer’s doubts.

• Regarding Mac-IGM and MacAdv-IGM, they are novel formalizations that ensure the consistency between local and global macro-action selection. This is not straightforward since it takes into account the temporally extended nature of macro-actions that require considering the local and global cases separately. During centralized action selection, the joint value has to condition on ongoing macro-actions $m^-$ to avoid biases in the joint estimation, while decentralized action selection requires consistent macro-action selection for only $|M^i|$ agents (i.e., agents whose macro-action is over). Moreover, Mac-AdvIGM differs from the original (primitive) formalization since it does not enforce the decomposition from Q-values as in (J. Wang et al., 2021). We believe this aspect has been significantly overlooked by the MARL literature, and has the potential to allow learning the value of a state (or history) separately. Such a decomposition has been shown to significantly improve performance in single-agent setups based on dueling networks [A]. However, this goes beyond the scope of our original submission, and we intend to explore this in future work. In addition, we further extend the Mac-IGM and MacAdv-IGM contribution by drawing the relationships between the classes of functions that can be represented by the primitive and asynchronous IGM principles. Such a result is formalized in Proposition 3.5, where we show that the macro-action principles are more general versions of the primitive ones as they can represent value functions on both primitive and temporally extended action spaces. It follows that AVF implementations of existing primitive baselines represent a broader class of functions over the primitive counterpart.

• Regarding temporal consistency, the proposed method is a simple yet effective mechanism that has been successful in achieving good performance and stable learning. We discussed three different representations to deal with the temporal consistency problem and provided an ablation study showing the crucial role of the proposed mechanism (which has been significantly extended in the paper revision. Please, refer to the new Fig. 5 for further details.). Given the novelty represented by asynchronous MARL in the literature, we are not aware of any other method that raises the problem of utilizing temporally consistent states in the mixer, nor other solutions for tackling such a novel problem. Hence, we kindly ask the reviewer to provide any reference that will allow us to perform additional experiments with other methods that utilize temporally consistent states.

• Regarding Mac-IAICC, we performed an additional set of experiments (20 independent runs) on CT-10, confirming the challenges posed by these environments for the policy-gradient baseline. To further strengthen our claims on the superior performance of AVF methods, we also added a comparison with the fully centralized Cen-MADDRQN (Xiao et al., 2020a) in the most complex setups (i.e., BP-30, WTD-T1, CT-10). Please, refer to the revised manuscript (Appendix E and the revised Table 1) and our answer to Reviewer E8n9 for further details about these results. Finally, as requested by the reviewer, we included the learning curves for both Mac-IAICC and Cen-MADDRQN in the supplementary material.

Thanks to the reviewer’s insightful comments, we believe the additional experiments and our clarifications have provided significant added value to our original submission that we hope to see reflected in our papers’ evaluation. Nonetheless, we look forward to further clarifying any remaining doubts about our work during this discussion period.

[A] Z. Wang et al., “Dueling Network Architectures for Deep Reinforcement Learning,” ICML, 2016.

We greatly appreciate the insights provided by Reviewer E8n9, which helped us to significantly strengthen our work, as shown in our updated submission. In the following, we clarify the main modifications and answer the reviewer’s questions.

Weaknesses:

1. Regarding the baselines, we compare our best-performing algorithm (AVF-QPLEX) with additional experiments (20 independent runs as in the other tasks) considering Mac-IAICC and Cen-MADDRQN (the fully-centralized value-based method of (Xiao et al., 2020a)) in all the hardest tasks: BP-30, WTD-T1, CT-10. In CT-10, Mac-IAICC and Cen-MADDRQN perform poorly due to the higher number of agents and the use of centralized estimators. For similar reasons, Cen-MADDRQN also has lower performance than AVF-QPLEX in WTD-T1 but obtains higher results in BP-30 (due to the small size of the joint observation). Due to space limitations, we kept the CT-10 results in the main paper as Table 1, but we moved the experiments in WTD-T1 and BP-30 in Appendix E.

2. We added the general pseudo-code of AVF algorithms, along with an additional explanation, in Appendix B.

3. Regarding the primitive baselines, we used the primitive version of BP-10 presented in the original Dec-MADDRQN paper (Xiao et al., 2020a). In summary, agents can only perform 1-step movement and push actions. We included an exhaustive discussion of the primitive version in Appendix D.1.

4. Concerning the extra information in the mixer, we did not include the second mechanism (i.e., using the macro-state of the terminated agent) as it showed significantly lower performance than using the joint macro-state in our preliminary experiments (due to the introduced noise for the other agent values). Nonetheless, we significantly extended our ablation study (Figure 5), discussing the lower performance of AVF-{QPLEX, QMIX} based on the second mechanism and the real state, both in WTD-S and (newly) in BP-10. Please, refer to the new Fig. 5 for further details.

Questions:

1. Regarding the macro-observations, it is true that a change in the macro-action of any agent will influence the macro-observation of agent i. However, following the MacDec-POMDP formalization (Section 2, Amato et al., 2019), agent $i$ can only observe such influence upon the termination of its own macro-action $m^i$ when it receives its updated macro-observation. Conversely, if agents receive a new macro-observation and select a new macro action every time any agent terminates a macro-action, they will likely converge to a primitive action-based solution (this aspect has also been discussed by previous macro-action works).

2. To the best of our knowledge, there are no principled CTDE value-based algorithms in the field of macro-action-based MARL, which further motivates the contributions of our work.

3. It is correct that a macro-action can be simulated by executing a 1-step for a longer period. For example, the “push” macro-action in BP domains is simply a repeated 1-step move forward action.

4. The duration time $\tau$ of the joint macro-action is used for the joint reward accumulation and is set to the time interval between any two macro-action terminations. We clarified this in Section 2.2.

5. While it would be interesting to apply DIGM and RIGM to the asynchronous framework, we believe it is out of the scope of our work. In particular, it would also require formalizing distributional macro-action-based MARL algorithms, which have not been currently investigated by the few published works considering asynchronous MARL.

Regarding minor questions, we appreciate the attention reserved by the reviewer for our manuscript. We fixed Eq. 5 and the Dec-POMDP tuple. Moreover, Table 1 reports the average return as all the other experiments (but it can be also interpreted as an average win rate given the nature of the reward function in CT-10). We clarified this in the table’s caption.

We believe our responses and the additional experiments provide a significant added value to our original submission that we hope to see reflected in the reviewer’s evaluation. Nonetheless, we look forward to further clarifying any remaining doubts about our work during this discussion period.