Weakness: Thank you for providing your insightful feedback once again. We greatly respect your opinions and appreciate your openness to various research directions. We would like to take this opportunity to provide a more detailed explanation of our ideas.

We first make use of the reference-advantage decomposition (also known as a variant of variance reduction) for Markov games to achieve sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, space complexity $O(SABH)$, computational complexity $O(T \mathrm{poly}(SAB))$, and burn-in cost $O(SAB\mathrm{poly}(H))$, which is never shown in previous works. Specifically, we design a pair of optimistic and pessimistic value functions and an early-settlement method to get such results. This is the first time to show the effectiveness of these ideas in Markov games, which is of significant importance in our opinion. We have stated these at the beginning of Section 3.1 in the revised version.

In terms of performance metrics, we have several noteworthy points to highlight. On the one hand, as per your previous suggestions, we have provided a comprehensive comparison of time complexity as shown in Table 1. It demonstrates that our algorithm achieves the best time complexity. On the other hand, the complex algorithm and proof process may not necessarily pose practical challenges for the algorithm implementation. On the contrary, we address a current research gap, which we think is more important.

Finally, we apologize for not presenting the implications of Theorem 3 in our initial submission. In the revised version, we have included additional explanations in Appendix F to address this concern.

Q1: Thank you for your comments and sorry for the confusion. We have included the algorithm and proof for multi-player general-sum games in Appendix F to address your comment in the revised version.

Q2: Thank you for your comments. In the revised version, we have included a paragraph in Section 1.2 to introduce the related works on multi-player general-sum Markov games.

Q3: Thank you for your question. The new major results compared with the NeurIPS version are indeed Theorems 2 and 3. Additionally, we have made several improvements. On the one hand, we have improved the presentation of Table 1 which compares various algorithms in terms of several performance metrics. Specifically, We have added a comparison of whether the output policy is a Markov/Nash-VI policy and a comparison of computational complexity. On the other hand, according to the feedback from the NeurIPS reviewers, we have provided a more detailed explanation of our reference-advantage decomposition and early-settlement methods in Section 3.1 on page 7.

Q4: Thank you for your question. Currently, we do not have a clear plan for achieving a sample complexity of $O(A+B)$. Algorithms such as Nash V-learning, or those based on V-learning, achieve a sample complexity of $O(A+B)$ because they do not need to store the Q-function and only require the Value function. It seems that they may help in future work. However, the policies learned by V-learning are non-Markov and history-dependent in general. It remains to study how to achieve a sample complexity of $O(A+B)$ without compromising the performance of existing metrics. We have discussed this in the conclusion of the revised version.

Weakness 1: We would like to express our sincere gratitude for your valuable comments. The fundamental distinctions between the proposed algorithm and reference algorithms (Nash-VI and V-learning) are the application of the ideas of variance reduction and the early-settlement method. Moreover, we first show the effectiveness of these ideas in TZMG by proving sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, space complexity $O(SABH)$, computational complexity $O(T \mathrm{poly}(SAB))$, and burn-in cost $O(SAB\mathrm{poly}(H))$.

Nash-VI uses the model-based idea and designs a different style of bonus term, which achieves the sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$ with burn-in cost $O(S^3ABH^4)$. However, Nash-VI needs space complexity $O(S^2ABH)$ to store the empirical transition matrix. Moreover, it computes the output policy for all states $s\in \mathcal{S}$ in each step, which leads to a computational complexity of $S$ times higher than that of our algorithm.

V-learning uses the FTRL idea (from adversarial bandit, i.e., $H = 1$), which overcomes the challenges posed by the curse of multi-agent, and achieves the sample complexity $\widetilde{O}(H^6S(A+B)/\varepsilon^2)$. However, this sample complexity depends greatly on $H$. Besides, the output policy of V-learning is neither Nash nor Markov policy due to the incremental updates of V-learning and causes the space complexity $O(S(A+B)T)$ to increase with the number of samples $T$.

To address the aforementioned issues, we have designed the ME-Nash-QL. First, we propose a model-free algorithm to shave the $S$ factor in space complexity compared with Nash-VI. Secondly, we have successfully obtained a lower sample complexity and a lower burn-in cost by designing a pair of optimistic and pessimistic value functions along with an early-settlement method based on the reference-advantage decomposition technique, which is a variant of variance reduction. Specifically, as detailed in Section 3.1, the standard deviation of $\widehat{P} _{h,s,a,b}\big(\overline{V} _{h+1}-\overline{V}^\mathrm{R} _{h+1}\big)$ might be $O(H)$ times smaller than the stochastic term used in Nash Q-learning. This is a key observation to weaken the dependency of the regret bound on $H$, and obtain the burn-in cost $\widetilde{O}(SABH^{10})$. Thirdly, our algorithm computes marginal policies using a CCE subroutine for a specific state in each step, which leads to a lower space complexity $(SABH)$ and a lower computational complexity $T{\rm poly}(AB)$ compared with Nash VI, and meanwhile a Markov and Nash output policy. We have clarified these in Section 1 in the revised version.

Weakness 2: Thanks for your insightful feedback. Regarding the TZMG setting, we have extended it to multi-player general-sum Markov games in Theorem 3. We have also included a detailed explanation of this in Appendix F in the revised version.

For the CCE setting, we would like to discuss it in two cases, i.e., TZMG and multi-player general-sum Markov games. In the former case, CCE, CE, and NE are equivalent, meaning that CCE in zero-sum games is guaranteed to be Nash. Thus our algorithm achieves NE in this case. For the latter case, we can achieve CCE, CE, and NE by replacing the subroutine in line 15 in Algorithm 3. However, it's important to note that NE leads to a much higher computational complexity, such as PPAD-complete (a complexity class widely believed to be computationally challenging). We have clarified these in Appendix F in the revised version.

Weakness 3: Thanks for your comments. We have reorganized Algorithm 2 in the revised version to enhance its readability.

Minor: Thanks for your comments, and we apologize for this typo. We have corrected this in the revised version.

Q1: Thank you for your question. There are many well-established computational methods to calculate CCE, as demonstrated by Xie et al. in June 2022. We have supplemented relevant explanations on page 8 in the revised version of our paper to make it self-contained.

Qiaomin Xie, et al., Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium.

Q2: Thanks for your questions. For the first question, the fact that space complexity remains independent of $T$ is attributed to the fact that the output policy is a single Markov policy.

For the second question, our decision to opt for CCE over NE is primarily motivated by the goal of reducing computational complexity, rather than space complexity. This choice is driven by the understanding that NE methods often come with high computational complexity, involving PPAD-complete problems (widely believed to be computationally challenging). In other words, we could achieve NE with the same space complexity by replacing CCE with NE in the algorithm, but the computational complexity is prohibitive.

We have clarified these at the end of Section 3.1 and Appendix F.2 in the revised version.

Weakness 1: Thank you for your feedback and concerns regarding the issue of the curse of multi-agent. We do agree that some research works focus on the curse of multi-agent, but there indeed exists a lot of attention on the dependency of long-horizon and size of state space, such as Nash Q-learning (Bai et al., 2020), OMNI-VI (Xie et al., Jun. 2022), Nash-UCRL (Chen et al., 2022), Optimistic PO (Qiu et al., 2021), VI-Explore/VI-UCLB (Bai & Jin, 2020), and Nash-VI (Liu et al., July 2021). Compared with them, we design a model-free self-play algorithm for TZMG that improves performance from three aspects simultaneously, including sample complexity ($\widetilde{O}(H^4SAB/\varepsilon^2)$), space complexity ($O(SABH)$), and computational complexity ($O(T \mathrm{poly}(SAB))$). Furthermore, our algorithm achieves a $\sqrt{T}$-regret bound with the best burn-in cost of $O(SAB\mathrm{poly}(H))$ as long as $\min\{A, B\}\ll H^2$. In addition, our algorithm produces a Markov and Nash policy as output. To the best of our knowledge, these algorithms with $O(A+B)$ sample complexity do not output Nash policies. We consider our work to be of significant research value and hope that ME-Nash-QL can inspire other researchers to achieve a $O(A+B)$ dependency in their work without compromising the performance of existing metrics. To address the reviewer's concern, we have discussed the curse of multi-agent in the conclusion of the revised version.

Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play.

Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium.

Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero-sum linear mixture Markov games.

Shuang Qiu, Xiaohan Wei, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. Provably efficient fictitious play policy optimization for zero-sum Markov games with structured transitions.

Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning.

Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play.

Weakness 2: We express our heartfelt gratitude for your feedback. The algorithmic novelty lies in two aspects. First, we apply the reference-advantage decomposition technique to the design of Markov game algorithms and achieve the $\tilde{O}(H^4SAB/\varepsilon^2)$ sample complexity. Second, we use an innovative early-settlement approach, substantially reducing burn-in costs. Notably, we are the first to integrate the reference-advantage decomposition and early-settlement technique into the domain of two-player zero-sum Markov games, and successfully prove the improvement of the performance. To make it clear, we have stated this at the beginning of Section 3.1.

Q1: Thank you for your question. While we believe that each performance metric plays a crucial role in assessing algorithm quality, if we were to choose one as the most important, we would consider sample complexity and burn-in cost to be paramount. These two metrics are closely tied to the amount of data required and have a significant impact on data-driven learning algorithms, especially in tasks that involve expensive or hazardous data collection, such as autonomous driving. Our work focuses on the context of online learning, which means that algorithms need to excel in terms of real-time adaptability to the environment or task. This underscores the significance of sample complexity and burn-in cost. In addition, we think the most important role in multi-player general-sum Markov games may output the Nash policy, which is deficient in the existing research.

Q2: Thank you for your question. As we outlined in our response to Weakness 2, our main contribution lies in the innovative adaptation and application of the reference-advantage decomposition technique and the early-settlement method to two-player zero-sum Markov games. We first show the effectiveness of these ideas by proving the $\tilde{O}(H^4SAB/\varepsilon^2)$ sample complexity and the $O(SAB\mathrm{poly}(H))$ burn-in cost for the proposed model-free TZMG algorithms. We have stated this at the beginning of Section 3.1.

We would like to express our cordial thanks to the reviewer for your precious time and feedback on our paper. However, it appears that there might be some misunderstanding regarding the reviewer guideline (https://iclr.cc/Conferences/2024/ReviewerGuide).

According to the guideline, it states: "We consider papers contemporaneous if they are published (available in online proceedings) within the last four months. That means, since our full paper deadline is September 28, if a paper was published (i.e., at a peer-reviewed venue) on or after May 28, 2023, authors are not required to compare their own work to that paper."

The work by Feng et al. was available on arXiv on August 17, 2023, which is contemporaneous with our work. We appreciate the reviewer for bringing this reference to our attention, and we will ensure to cite it in the final revised version of our paper.

Q1: Thank you for your question. Besides applying the reference-advantage decomposition and early-settlement techniques, our main technical contribution is to show their effectiveness by proving sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, space complexity $O(SABH)$, computational complexity $O(T \mathrm{poly}(SAB))$, and burn-in cost of $O(SAB\mathrm{poly}(H))$. In addition, we extend our algorithm from the TZMG setting to multi-player general-sum Markov games in Theorem 3, which is also one of our contributions. We have stated these in Section 1.1 in the revised version.

Q2: Thank you for your question. Similar conclusions can be obtained in multi-player general-sum Markov games, as stated in Theorem 3 in the main text. We have added Appendix F in the revised version to provide detailed supplements for Theorem 3.