Addressing Extrapolation Error in Multi-Agent Reinforcement Learning

8. There are no implementation details or parameter searches provided for the baseline methods. Only searching parameters for the proposed method is unfair and may lead to biased results.

The baselines are implemented using fine-tuned versions from PyMARL2 (VDN, QMIX, QPLEX) and FACMAC’s paper (FACMAC, MADDPG). We did not perform parameter searches for any methods, including ours, as $\lambda^*$ and $M$ were set heuristically.

9. Section 3 provides a detailed analysis of QPLEX to illustrate extrapolation error in MARL. However, Section 4 switches to QMIX. Is there a specific reason for this switch?

We chose QPLEX for theoretical analysis due to its explicit modeling of joint action spaces. QMIX was used in Section 4 because of its simplicity and popularity. However, the findings in Section 4 are applicable to other methods, including QPLEX.

[1] Fujimoto, Scott, David Meger, and Doina Precup. "Off-policy deep reinforcement learning without exploration." In International conference on machine learning, pp. 2052-2062. PMLR, 2019.

[2] Anschel, Oron, Nir Baram, and Nahum Shimkin. "Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning." In International conference on machine learning, pp. 176-185. PMLR, 2017.

[3] Rashid, Tabish, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. "Monotonic value function factorisation for deep multi-agent reinforcement learning." Journal of Machine Learning Research 21, no. 178 (2020): 1-51.

[4] Kozuno, Tadashi, Yunhao Tang, Mark Rowland, Rémi Munos, Steven Kapturowski, Will Dabney, Michal Valko, and David Abel. "Revisiting Peng’s Q ($\lambda$) for Modern Reinforcement Learning." In International Conference on Machine Learning, pp. 5794-5804. PMLR, 2021.

[5] Hu, Jian, et al. "Rethinking the Implementation Tricks and Monotonicity Constraint in Cooperative Multi-agent Reinforcement Learning." The Second Blogpost Track at ICLR 2023.

[6] Peng, Bei, et al. "Facmac: Factored multi-agent centralised policy gradients." Advances in Neural Information Processing Systems 34 (2021): 12208-12221.

Thanks for your review. We answer this question first, which helps with the subsequent rebuttal

How can we ensure that extrapolation error is reduced?

We approach this from both theoretical and empirical perspectives:

Theoretical Perspective: Extrapolation error arises when the target Q-function relies on values from rarely seen actions. By reducing the usage of such values, we can mitigate extrapolation error. For example: Factorized Q-functions operate in a much smaller action space compared to joint Q-functions. With the same sample size, factorized Q-functions are less likely to use extrapolated Q-values, reducing the extrapolation error. This theoretical property highlights why value factorization methods effectively mitigate extrapolation error.

Empirical Perspective: While extrapolation error cannot be directly measured due to its integration within the total neural network error, we use Target Estimation Error (TEE), as introduced in our paper, as an indirect indicator. For example, since value factorization theoretically reduces extrapolation error, its impact on TEE provides indirect evidence. As shown in figure 1(b)(c), TEE is significantly reduced. Although value factorization introduces limitations in function approximation, which should increase TEE, the observed reduction in TEE confirms that the theoretical and empirical results mutually validate each other.

1. Extrapolation error is a commonly discussed topic in single-agent RL and naturally extends to MARL.

We’d like to emphasize that it is not straightforward to consider extrapolation error in online MARL. Unlike offline single/multi-agent RL, where extrapolation error has been studied extensively, it is rarely considered in online single-agent RL and has not been addressed in online MARL prior to our work. The unique challenge in MARL is its large joint action space, which amplifies extrapolation error. This is discussed in Section 3.1 of our paper.

2. The authors do not provide new insights or discuss challenges specific to MARL.

We respectfully argue that our paper introduces several new insights and all specific to MARL:

• Online MARL suffers from exacerbated extrapolation error due to large joint action spaces.
• Value factorization methods effectively mitigate extrapolation error by addressing joint action space challenges.
• Monotonic factorization is crucial to prevent the accumulation of extrapolation error.
• Performance in existing MARL methods is heavily influenced by extrapolation error.

None of these points can be directly derived from prior works [1,2,3,4], demonstrating that our findings are novel and specific to MARL.

3. The paper claims that extrapolation error is a major issue in MARL, but the authors do not provide any evidence to support this claim.

Here, we summarize the evidence provided based on the 4 points mentioned above, respectively.

• In Figure 1(a), we conduct experiments on SMAC and find 20%-60% of the target estimation relies on extrapolated values, directly highlighting the importance of extrapolation error in MARL.
• As discussed at the beginning, value factorization reduces extrapolation error by limiting the use of extrapolated Q-values. This theoretical property is empirically supported in Figures 1(b)(c), where TEE decreases significantly.
• Section 3.2 provides theoretical analysis showing that monotonic factorization is critical to prevent extrapolation error accumulation. Although experiments specific to this are not included, prior works [5,6] on non-monotonic factorization support our claim.
• In Section 3.3, we show how extrapolation error destabilizes QPLEX. Furthermore, Section 5 and the appendix demonstrate that methods such as VDN, QMIX, QPLEX, FACMAC, and MADDPG show substantial performance improvement when extrapolation error is addressed.

4. Line 352 states, "The behavior policy typically originates from the old policy stored in the replay buffer, which may not align closely with the current policy after convergence". Does this not hold even after convergence? Why?

Sorry for this mistake. We meant “before convergence” rather than "after convergence."

We sincerely thank the reviewer for their detailed and constructive feedback. We are also grateful for the recognition of the strengths of our work, including the clarity of the paper, our novel focus on extrapolation error in online MARL, and the thorough analysis and methods we introduced to mitigate this issue.

1. The experiment section is not very detailed.

We appreciate the reviewer’s concern about the level of detail in the experimental section. The number of seeds is detailed in Figures 8, 9, and 10 in the appendix, where SMAC and SMACv2 use 3 seeds, and GRF uses 5 seeds.

The evaluation procedure follows the standard setup for SMAC: training pauses every $10^4$ steps, and the agent is evaluated for 32 episodes using greedy action selection.

Regarding the omission of standard deviations in Table 1, this decision was made to save space. However, the learning curves in Figures 8, 9, and 10 in the appendix provide a detailed view of performance, including error bar, which we believe addresses this concern.

2. It might be more informative to use a different environment to SMACv1.

Thank you for the suggestion. We are currently conducting experiments on several tasks from PettingZoo to expand the diversity of environments. Unfortunately, due to the time required for tuning and running baselines, we are unable to provide these results during the rebuttal phase. We appreciate your understanding.

3. It is unclear if parameter sharing is used in the baseline algorithms.

We confirm that all baseline algorithms (except for MADDPG) utilize parameter sharing across agents in our experiments.

4. Why using smaller ensembles (M=1,2) in Figure 5b, performance is worse than the QMIX baseline.

It is due to the annealing of $\lambda$ occurring too quickly, before convergence is achieved, and not because of the ensemble itself. As discussed in Lines 510–515, the annealing approach is designed for quicker convergence. However, as shown in Figure 5(c), smaller $\lambda$ leads to poor performance on the 3s5z_vs_3s6z task due to insufficient convergence. Premature annealing of $\lambda$ negatively impacts performance in these cases. In contrast, larger ensembles achieve convergence earlier, making $\lambda$ -annealing more effective. Additionally, Figure 5(a) demonstrates that smaller ensembles (M=2) still significantly improve performance compared to the baseline.

5. It would be important to disentangle the effect of increased capacity and extrapolation error mitigation.

Thank you for this valuable suggestion. To address this concern, we conducted experiments with larger QMIX models on SMACv2 by increasing the hidden dimensions of the individual Q-function from 64 to 128, and 256. The results (Figure 16) indicate that simply increasing model capacity does not improve performance, confirming that the observed improvements are not due to increased capacity.

6. What is the comparison of the parameter counts across the baseline and proposed modifications? How does this scale as the number of agents increase?

The primary increase in parameter count arises from the ensemble modification.

• In QMIX, the total parameter count is individual_Q_parameters + mixer_parameters. With an ensemble of size M, this scales to M*individual_Q_parameters + mixer_parameters.
• For policy-based methods like FACMAC, the baseline parameters include individual_Q_parameters + individual_policy_parameters + mixer_parameters, which scale to M×individual_Q_parameters + individual_policy_parameters + mixer_parameters with an ensemble of size M.

The parameter count depends on the size of each component and the state-action space of the task. For example, in the corridor task of SMAC, QMIX’s individual Q-parameters total 39k, while the mixer parameters are 69k. Importantly, the parameter count does not scale with the number of agents due to parameter sharing, except in methods like QPLEX and MADDPG, which take joint actions as input.

We thank the reviewer for their thoughtful feedback. We greatly appreciate the recognition of our paper’s insightful theoretical analysis, the practicality of our proposed methods, and the contribution to mitigating extrapolation errors in MARL. These strengths highlight the significance of our work in providing a deeper understanding of stable value estimation and its role in improving MARL performance and stability.

1. Fundamental Limitations of Value Factorization.

We acknowledge the fundamental limitations of value factorization in its reliance on a factorized action space. However, addressing this issue comprehensively has remained a challenge for years and is not the primary focus of our paper. Despite its potential suboptimality, value factorization consistently demonstrates superior performance compared to other baselines. Our objective is to investigate why it performs well and identify ways to further exploit this advantage.

Our findings provide insights that:

• Support Value Factorization in addressing joint action dependencies: We show that ignoring extrapolation errors during attempts to capture the full joint action space can result in significant error accumulation. For example, our modified QPLEX* improves upon QPLEX by considering joint action spaces while accounting for extrapolation errors. This enhances stability without compromising performance.

• Generalize beyond Value Factorization: The insights derived from our study can be directly applied to methods like MADDPG, which do not suffer from suboptimality issues, or inspire improvements in these methods.

2. Incremental and Limited MARL-Specific Solutions.

We emphasize that the primary goal of our paper is to build a theoretical foundation for understanding and mitigating extrapolation errors in MARL, rather than introducing purely novel methods. To this end, we deliberately use well-established techniques with clear theoretical properties to validate our insights. We believe that addressing a critical, overlooked issue using simple and effective approaches represents a meaningful contribution to the field.

While we acknowledge that our methods do not explicitly consider agent interactions, we do offer MARL-specific considerations:

• We introduced QPLEX*, which bounds QPLEX's $\lambda(s,a)$ to avoid extrapolation error accumulation and improves the stability.
• We find that starting with a large $\lambda$ in PQL, while being unusual in single-agent settings due to suboptimality, actually benefits MARL due to the extrapolation error.
• In line 406-408, we opt not to ensemble the mixing network since it is unrelated to extrapolation, as verified in Figure 11.
• In line 408-412, we avoid averaging before the mixing network to implicitly regularize it, as verified in Figure 15.

3. Addressing Suboptimality and Agent Dependencies

As noted above, our method does not directly address the suboptimality inherent in value factorization caused by its inability to fully capture joint action interactions. However, our contributions can:

• Facilitate future developments in value factorization methods: Previous attempts to address suboptimality, such as QTRAN and QPLEX, struggled with extrapolation errors, which we mitigate through our approach. Our insights can guide the development of methods that aim to overcome suboptimality while retaining stability.
• Benefit MARL methods without suboptimality issues: Since our study addresses extrapolation errors—a common challenge across MARL methods—it can directly apply to or inspire enhancements in approaches that do not rely on value factorization.

We hope these responses clarify our contributions and demonstrate how our work can drive progress in MARL research.