Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on two player zero-sum stochastic games. It is shown that Optimistic FTRL (together with value update step) converges to a Nash equilibrium in $O(1/T)$ improving the result of Zhang et al. 
strength_and_weaknesses: The result is important and adds value to the current growing literature. The techniques are interesting, exploiting ideas from papers by Anagnostides et al that the sum of regrets should be non-negative (in this case are not too negative) and moreover this leads to prove that second-order path length is bounded. This idea can give a log T/T bound but the authors with extra effort remove the log T dependence.

There is another work (appeared a bit later I think) that achieves 1/T convergence using Optimistic MWU and the notion QRE (quantal response) Nash. The ideas are somewhat different as in the latter the KL divergence is used as a potential. 
clarity,_quality,_novelty_and_reproducibility: I think the paper is well written, has merits technically and the result is important.
summary_of_the_review: I think the paper is above the bar for acceptance. If there was a score 7, I would put 7, between 6 and 8 I choose 6 but I am in favor of the paper getting in. The only reason I chose 6 is that there have appeared many papers of the same flavor/similar results the last year and reading this paper did not make me feel surprised. If needed, I will increase my score.

Correction: After checking thoroughly the paper by Zhang et al, there is an improved analysis that also achieves O(log T/T) regret, so the improvement is not as large as was mentioned in the paper. Can you argue about that? As far as I can see now, the result improves from \log  T/T to 1/T regret. The comment/question has been addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies solving two-player zero-sum Markov games using follow-the-regularized-leader-type algorithms. The authors propose an algorithm based on Zhang et al., 2022 and proved it has an $O(1/T)$ convergence rate to the Nash equilibrium. 
strength_and_weaknesses: Pros:
- The presentation is clear.
- The proof is correct.

Cons:
- It lacks novelty for either the algorithm design or the proof. The proposed algorithm itself actually can be regarded as a special realization of  Algorithm 1 in Zhang et al. 2022, which makes the algorithm design less important. The proof also reuses lots of statements in Zhang et al., 2022 (like the proof of Lemma 1). Finally, the proposed algorithm enjoys the nearly same order of convergence rate as Algorithm 10 in Zhang et al., and I am not convinced that the proposed algorithm is simpler than Algorithm 10 in Zhang et al. since it is already simple enough. 
clarity,_quality,_novelty_and_reproducibility: The proposed algorithms and proof are not novel given the existing work Zhang et al., 2022.
summary_of_the_review: The authors propose an algorithm for two-player zero-sum Markov Games with an $O(1/T)$ convergence rate to find the Nash equilibrium. I find the proposed algorithm and theory lack novelty and importance given Zhang et al., 2022, therefore I recommend a reject.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence of optimistic policy optimization algorithms in two-player zero-sum Markov Games. The main result of the paper is to show that the Optimistic-Follow-The-Regularized-Leader (OFTRL) algorithm achieves an $O(T^{-1})$ convergence rate to the Nash Equilibria of the game. This settles the open problem raised in the recent work of (Zhang et al. 2022), which showed an $\tilde{O}(T^{-5/6})$ convergence rate for the same algorithm.
strength_and_weaknesses: Strengths:

* The paper settles the open problem raised by Zhang et al. (2022) about $T^{-1}$ convergence rate of OFTRL in Markov Games. In particular, the same work designed a modified OFTRL algorithm achieving $\tilde{O}(T^{-1})$ rate, and also showed that empirically the original OFTRL algorithm does achieve $T^{-1}$ rate. Plus, $T^{-1}$ convergence in the easier case of zero-sum normal-form games (NFGs) is a well-established result (e.g. Rakhlin and Sridharan, 2013) and follow directly from the RVU property of OFTRL. These all seem to be urging for a positive resolution to this problem, which this paper did.

* The main technique—establishing an *approximate* non-negativity of the summed regret for zero-sum NFGs with slowly changing game matrices—seems interesting and new to this line of work. As the authors mentioned, the technique of using non-negativity of regrets to establish second-order path length bounds has been used in other contexts such as fast convergence of swap regrets. However, to my best knowledge, this is its first application in Markov Games.

* The topic of fast convergence in games should be of good interest to the RL/games community. 

Weaknesses:

* Overall, the paper sounds a bit lacking in terms of completeness as for a conference paper on this topic (only one main theorem and no extensions / additional results etc). I wonder if the authors have thought about whether the techniques (approximate non-negative regret) or settings (zero-sum NFGs with slowly changing game matrices) could be useful in other problems? (For example, any relation to “time-changing zero-sum games”? see ref below). Having some additional results about related problems or techniques could genuinely improve the paper, in my opinion.  
Zhang, M., Zhao, P., Luo, H., & Zhou, Z. H. (2022). No-Regret Learning in Time-Varying Zero-Sum Games. arXiv preprint arXiv:2201.12736.

* The claim of settling Zhang et al. (2022)’s open question needs to be discussed carefully, as that work also gives a modified OFTRL algorithm with the same $\tilde{O}(T^{-1})$ rate. Currently this is discussed only in Section 3, and I suggest also adding some discussions in the introduction/related work where appropriate. 

clarity,_quality,_novelty_and_reproducibility: I think overall the work is clearly presented. The main technique leading to the improved convergence rate is new. The proof seems correct to me upon a quick skimming. 
summary_of_the_review: The paper resolves an open question on the fast convergence in Markov Games using an interesting new technique, though the result sounds a bit thin and lacking in extensions / additional results.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents an analysis showing that optimistic FTRL combined with online averaging in the value-function updates finds an $O(T^{-1})$ Nash equilibrium in $T$ iterations for two-player zero-sum Markov games with known rewards and transition dynamics. This improves upon previous analysis of the same algorithm. Also note that the resulting bound scales worse in the horizon $H$ than the tweaked version presented in earlier work which also achieves $\tilde O(T^{-1})$ convergence.
justification_for_why_not_higher_score: The results received only mild support from the reviewers. The setting is the easiest variant of zero-sum Markov games, and the novelty and potential impact of the paper is somewhat limited.
justification_for_why_not_lower_score: All reviewers support (mildly) the acceptance of the paper, which provides an improvement compared to earlier analysis.
Decision: Accept: poster