Revisiting Cooperative Off-Policy Multi-Agent Reinforcement Learning

We are thankful for your time and effort in reviewing our paper, which has greatly helped us improve the quality of our paper. We were glad to hear that you found our proposed methods sensible and that our empirical results demonstrated promising improvements over baseline approaches. Below, we address the key concerns you raised.

1. Some detailed explanations or analysis are needed, for example on why RAR versions are outperforming their counterparts in Figure 4-6.

The superior performance of RAR versions can be attributed to the reduction in Target Estimation Error (TEE) when the joint action space is mapped into a lower-dimensional space. To validate this, we conducted experiments with MADDPG-RAR using different joint action dimensions and report the corresponding TEE values in the following table:

From these results, we observe that a lower action dimension leads to a smaller TEE. This occurs because reducing the joint action space mitigates extrapolation in the target Q-function. Intuitively, if the joint action is mapped into a single dimension (although suboptimal due to potential bias and increased optimality difference, as discussed in Section 3.1), the target Q-function would require no extrapolation even for unseen actions. By properly constraining the joint action dimension, we can significantly reduce extrapolation while maintaining sufficient expressiveness in the joint Q-function, ultimately improving performance.

Another key intuition is that joint Q-functions do not necessarily need to assign distinct values to every possible joint action. For example, consider two agents A and B:

• Joint action $a_1$: A moves toward B, B stays.
• Joint action $a_2$: A stays, B moves toward A.

If the task depends only on the relative distance between A and B, then $a_1$ and $a_2$ may be equivalent in terms of their Q-value. Now, assume:

• $a_1$ and $a_2$ is frequently observed in state $s_1$.
• $a_1$ is frequently observed in state $s_2$, but $a_2$ is not.

In an unrestricted joint Q-function, $Q(s_2,a_2)$ may be poorly estimated due to lack of experience. In contrast, with RAR, since the model has already learned in $s_1$ that $a_1$ and $a_2$ are equivalent, and since $Q(s_2,a_1)$ is well estimated, $Q(s_2,a_2)$ will also be well estimated. This further supports why RAR enhances performance.

2. Among the three approaches, it will be more beneficial to understand and compare the contributions of each induvial approach.

Figure 7 (left) illustrates the contributions of Annealed Multi-Step Bootstrapping and Averaged TD Target to QMIX. To further clarify their impact, we provide additional results:

These results indicate that both Annealed Multi-Step Bootstrapping and Averaged TD Target contribute to performance improvement. However, Averaged TD Target provides a greater benefit at the cost of additional network computations, whereas Annealed Multi-Step Bootstrapping is more computationally efficient.

The impact of RAR techniques on performance is shown in Figures 4 and 8, where we compare MADDPG and QPLEX with and without RAR. Overall, these results reinforce that all three approaches contribute to performance gains.

3. It seems like some of the aspects studied in the paper even applies to on-policy setting in MARL, will extrapolation error also be effectively mitigated by the proposed approaches?

While some insights from our work could extend to on-policy MARL, extrapolation error is less of a concern in such settings because on-policy methods primarily use a value function (V-function) rather than a Q-function. Specifically:

• Annealed Multi-Step Bootstrapping: The on-policy equivalent is TD($\lambda$) which is already widely used. Unlike in off-policy RL, annealing $\lambda$ in TD($\lambda$) is unnecessary because it does not introduce bias as in Q($\lambda$).

• Averaged TD Target: While applicable to on-policy RL, its effectiveness is reduced. The V-function is inherently easier to learn than the Q-function and is less affected by variance induced by the joint action space.

• Restricted Action Representation: This technique is not applicable to on-policy RL, as it specifically targets the joint action space, which is not used in V-function-based methods.

Thank you for your constructive feedback, especially for your detailed feedback on the evaluation of TEE and the impact of our proposed techniques. We were glad to hear that you found our work well-structured, clearly motivated, and systematic empirical analysis. Below, we address the key concerns you raised.

1. I would expect clear empirical evidence that averaged TD targets and restricted action representations reduce TEE.

For a good estimation of the TD target, both bias and variance play a crucial role. The estimation error of the TD target typically consists of both components. While annealed multi-step bootstrapping reduces bias introduced by extrapolation, it increases variance by assigning higher weight to trajectory returns. Therefore, averaged TD target is importantly utilized to mitigate variance of the target Q-function, and indeed reduced it as shown in Figure 9 (left).

Regarding RAR, it tackles both bias and variance of TEE by directly simplifying the joint Q-function. Intuitively, in an extreme case where the discrete action space is compressed into a single dimension, learning the joint Q-function becomes as simple as learning a V-function (though this introduces a significant optimality gap, as discussed in Section 3.1). To further demonstrate the impact of RAR on TEE, we conducted experiments on MADDPG-RAR in MPE. Please refer to point 1 of our rebuttal to reviewer Lbue for details.

2. Would the authors be able to show that AEQMIX indeed performs better than EQMIX?

Yes, AEQMIX consistently outperforms EQMIX. Please see point 2 of our rebuttal to reviewer Lbue for supporting results.

3. In MADDPG-RAR, Which joint actions are mapped to the same representation and which joint actions are separated?

Strictly speaking, all actions have different representation. This is because $g(a)$ is a multi-categorical distribution, and every joint action can have unique probability.

For example, consider the spread task with 5 agents and each has 5 actions, which maps from a 5^5 joint action space to 2^5. If we directly apply argmax on the probability, the joint actions are divided into 2^5 groups, each group contains between 64 and 127 mapped joint actions. Within each group, however, we did not find significant correlation among these joint actions.

4. The $\lambda$ values of QPLEX-RAR when applying the Sigmoid function.

The following table presents $\lambda$ values when applying the Sigmoid function. It shows that $\lambda$ values remain stable throughout training.

5. How would AE- and RAR-extended algorithms perform in this illustration? Would the take-away still be that algorithms like MAPPO that do not rely on action-value functions are preferred for tasks with many agents or do the proposed approaches bridge that gap?

Our proposed techniques improve performance, but the gains are not sufficient to match MAPPO. For instance, in the 5-agent scenario shown in Figure 1, MADDPG’s normalized return improves from -60 to -51. However, MAPPO achieves -41, maintaining a performance gap.

This suggests that while our methods enhance Q-function learning, they do not achieve the same scalability as the V-function-based on-policy methods. But this does not mean MAPPO is better in all case, off-policy methods have their own advantages, such as higher sample efficiency.

6. Would the authors be able to compute the true proportions of extrapolated values and update the respective Figure?

We apologize for the mistake. The proportion of extrapolated values was not computed from the replay buffer. Instead, we recorded visited state-action pairs using a separate Python dictionary throughout training. As a result, Figure 2(a) reflects the true proportions.

7. The work should attempt to make space to discuss related work and literature within the main work.

Thanks for the suggestion. While we included some discussion of related work in Section 2, we acknowledge that it may not be sufficient. We will consider adding a new subsection in Section 2 to better integrate the literature discussion into the main paper.

8. The legend of Figure 10 (b) within the supplementary material is misleading.

The term "double Q-learning" in Figure 10(b) refers precisely to [1, 2]. In this figure, the x-axis represents different ensemble sizes, where a larger M leads to a more conservative (underestimated) target. All blue columns apply double Q-learning, which can also contribute to underestimation. To provide contrast, we include a case without double Q-learning when M=0 (pink), which exhibits the most overestimation. The figure demonstrates that simply reducing overestimation does not necessarily lead to better performance.

Thank you for your constructive feedback, which has greatly helped us improve the quality of our paper. We were glad to hear that you found our claims convincing and that our proposed methods make sense for addressing the problem. Below, we address the key concerns you raised.

1. The authors frequently mention the MPE environment in the introduction but do not include any experiments on it. Why was this environment omitted?

The MPE environment is included in Figure 2 (left) and Figure 4 (left). However, we did not highlight it in the experiment section because it contains only one suitable task (Spread), and is significantly less complex than SMAC and SMACv2. We will provide additional results for Spread in the appendix in the next version. For futher details, please refer to point 5 of our rebuttal to reviewer o7jb.

2. The paper should compare its approach with other research addressing overestimation in MARL, such as [1].

Thank you for the suggestion. We will add a comparison to RES. However, based on the current results, it appears that RES does not outperform the fine-tuned QMIX when evaluated within the PyMARL2 codebase. This also aligns with our argument that extrapolation error does not always lead to overestimation. As shown in Figure 10(a) (Appendix D.2), applying a more underestimated target actually degrades performance.

3. The scope of paper is framed around off-policy learning, but the key techniques seem to target algorithms using Bellman optimality equations.

Our techniques target methods that utilize Q-functions, which are fundamental to most off-policy methods. Since these methods require off-policy Q-target estimation, they inherently face target estimation error, as discussed in section 3 of our paper.

4. The section on Restricted Action Representation in MADDPG is difficult to follow. The authors could provide a more intuitive example, such as one where the number of actions differs from the number of agents, rather than using the 5^5 example, which is not clearly explained.

Thanks for this suggestion, we choose the 5^5 to 2^5 example because it directly corresponds to our experimental setup in Figure 4 (left). For another example such as 4 agents with 5 action, we can also compress the action space from 5^4 to 2^4. For a more detailed explanation of RAR, please refer to point 1 of our rebuttal to reviewer Lbue.

5. The paper references the $\lambda$ parameter in QPLEX but does not provide a clear introduction to QPLEX itself. Some background should be added.

Thank you for pointing this out. We will add a brief introduction to QPLEX to provide the necessary background for the discussion on the $\lambda$ parameter.

6. The discussion on $\lambda$ in QPLEX does not seem to align with the idea of Restricted Action Representation. Instead, it appears to be merely a constraint on the weight values rather than a true action space compression.

The concept of RAR is to limit the effect of joint actions on the joint Q-function. In QPLEX, since the joint action component is already separated by $\lambda$, directly constraining $\lambda$ can effectively restrict its influence. Applying the same technique as in MADDPG could achieve similar results but would require additional networks. We will provide corresponding experiments in the appendix.

7. The authors propose applying an additional sigmoid function to $\lambda_i$, but the original QPLEX paper already applies sigmoid before summation. While this paper applies it after summation, the practical impact of this change is unclear.

The original QPLEX paper applies a sigmoid before summation, but this does not restrict the impact of joint actions, as other weight terms can still amplify it. The full expressive power of QPLEX requires $\lambda\in[0,\infty]$, meaning that even with a pre-summation sigmoid, QPLEX retains full representation capability. By constraining $\lambda\in[0,1]$ , our approach explicitly limits action representation ability, leading to more stable results.

8. The ablation study on Restricted Action Representation is confusing. The results for MADDPG and QPLEX should be presented together in the same figure for easier comparison. Why are the ablation studies conducted in different environments for different methods? This makes it difficult to interpret the results consistently.

We understand the concern. However, our MADDPG and QPLEX use different codebases as detailed in Appendix D.1, making direct performance comparison within the same figure difficult (basically because the difference in parallelized environments). Moreover, the performance of MADDPG and QPLEX are significantly different, SMACv2 may be too hard for MADDPG and SMAC may be too easy for QPLEX, which makes the effect of RAR less noticeable. We will clarify this in the next version.