Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper focuses on two-player zero-sum Markov games and studies equilibrium finding algorithms in the infinite-horizon discounted setting and the finite-horizon episodic setting. The authors propose a novel single-loop policy optimization method with symmetric updates from both agents. They show the proposed method achieves a sublinear last-iterate convergence to the Nash equilibrium by controlling the amount of regularization in the full-information tabular setting. Their results improve upon the best-known iteration complexities.
strength_and_weaknesses: Strength: This paper presents a novel algorithm for policy optimization in zero-sum Markov games, which can lead to an improvement over the existing rate. Moreover, the proposed algorithm is single-loop and symmetric, which are good properties for an algorithm. The overall algorithm design seems to be inspired by the optimistic mirror descent algorithm. But given that the algorithm and the corresponding result are novel to the research area of policy optimization in multi-agent RL, the contribution of this paper is significant. 

I only have one question regarding this paper: is it possible to extend this algorithm to a more realistic bandit setting, where both the reward and the transition are unknown to the learner? If it is not, what is the major challenge?
clarity,_quality,_novelty_and_reproducibility: This paper is overall clear to readers. It also has significant novelty. The detailed proof in the Appendix can reproduce the main results in the paper.
summary_of_the_review: See the Strength And Weaknesses section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The work "Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games" studies two-player zero-sum Markov games, where the goals are to find the Nash Equilibrium (NE) or Quantal Response Equilibrium (QRE).

The authors proposed actor-critic methods (two similar variants, one for discounted and one for episodic settings), where the actor update is the entropy-regularized optimistic multiplicative weights update (OMWU) method in Cen2021b, and the critic update is slower (as shown in Eq. (10) in Algorithm 1). The proposed algorithms are single-loop, symmetric, with finite-time last-iterate convergence toward equilibria.

In particular, Theorem 1 shows that Algorithm 1 enjoys linear convergence toward QRE, and by setting the temperature $\tau$ for the entropy the algorithm can find $\epsilon$-NE with $\tilde{O}\left( \frac{ |\mathcal{S}| }{(1 - \gamma)^5 \epsilon} \right)$ iteration complexity.

The above results outperform existing works as summarized in Tables 1 and 2, achieving the same desirable iteration complexity of $\tilde{O}\left( \frac{1}{\epsilon} \right)$ as in PI- and VI-based methods while using only single-loop updates.
strength_and_weaknesses: **Strenghs**:

1. This work studied an important problem of finding equilibria in two-player zero-sum Markov games. The presentation is clear and easy to follow. Existing related works are also discussed well enough.

2. The results obtained are strong and promising, achieving the same iteration complexity of $\tilde{O}\left( \frac{1}{\epsilon} \right)$ as for PI- and VI-based methods while using only single-loop updates.

3. The techniques are also insightful. It shows that the existing contraction techniques used in matrix games in Cen2021b can be generalized to Markov games and can be combined with critic updates to work, which seems non-trivial and novel to my knowledge.

**Weaknesses**:

I have some questions after reading the paper.

1. If $\eta \le \frac{(1 - \gamma)^3 }{32000 |\mathcal{S}| } $, then the linear rate also seems to be very small in Eq. (12a) since $\eta$ also appears there. The authors did mention that $|\mathcal{S}|$ can be replaced with concentration coefficient in Remark 1 and Appendix A, but how smaller that replacement could be is still unclear from the paper. Could you elaborate more on what in the current analysis makes the learning rate $\eta$ have to be very small in Theorem 1? It seems to me bounding the state distribution in $V$ is the bottleneck (Theorem 2 in Appendix A).

2. It would be great to use some simulation results to verify the theoretical results.

    - It would be curious to verify and observe the linear rate itself (in terms of $t$), as well as how slow it could be (in terms of $\eta$);
    - It would be also interesting to see if in practice larger learning rates than $\eta \le \frac{(1 - \gamma)^3 }{32000 |\mathcal{S}| } $ could be used and still achieve convergence, which means the analysis has space for improvement; or larger learning rates lead to non-convergence, which means it has to be what is used in Theorem 1 (in this case, I think the authors should do better jobs in explaining the difficulties of using large learning rates here).

3. I did not find any assumption of unique NE in the draft (the authors did mention that other works require unique NE assumptions, and this seems to say that they do not need this kind of assumption). Could you comment on what is the quality of NE for the convergence results in the paragraph below Theorem 1 ("Last-iterate convergence to $\epsilon$-optimal NE")?

clarity,_quality,_novelty_and_reproducibility: **Quality**: The theoretical results are strong, and the technical lemmas seem correct to me as I checked. The quality of the work is good. A missing part could be the simulation results to verify the theory as mentioned in the weaknesses.

**Clarity**: In general, I found the presentation clear and easy to follow, including the problems and settings, related work discussions, and comparisons to existing results. The clarify is good. A missing part is the explanation for difficulties of using larger learning rates could be better presented and clarified.

**Originality**: The policy update is from entropy-regularized OMWU Cen2021b as noted, and the critic update Eq. (11) is motivated from Wei2021 as also mentioned. Generalizing from matrix games to Markov games and showing that combining these two updates can work seem non-trivial to me. The technical originality is incremental but seems enough.
summary_of_the_review: Overall, this work studies an important problem and the theoretical results are strong. The techniques are from or motivated by prior works, but extending those results from matrix games to Markov games requires non-trivial work. The only missing part is lack of empirical supports.


~~~~~after rebuttal~~~~~

Thank you for the comments. I would like to maintain my current score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies computing Nash equilibria in two-player zero-sum Markov games, by proposing a single-loop and symmetric algorithm with last-iterate convergence guarantee. The derived iteration complexity improves over previous works by a factor of $H$.
strength_and_weaknesses: # Strength

- The iteration complexity improves over the best previous results by a factor of $H$.
- The paper is mostly clearly written.


# Weakness (and questions)

- The proposed algorithm simply combines the entropy-regularized OMWU method (Cen et al., 2021b) with the V-learning style value update rule (Bai et al., 2020). The techniques used in the proofs also look quite similar to the previous ones. So it's a bit unclear to me how much algorithmic and technical novelty this submission possess beyond blending the existing ideas.

- The interaction protocol considered in this paper is very strong, which basically enables running any dynamic-programming style algorithms. In this case, why isn't it a better choice to run DP-style algorithms, which is algorithmically simpler, theoretically easier to analyze, and oftentimes have better iteration complexity.

- The results in this paper seem to highly rely on the gradient feedback being exact to guarantee the linear convergence rate on the strongly convexified problem, which makes it hard to generalize to the sample-based setting. 




clarity,_quality,_novelty_and_reproducibility: Just one minor comment:

The value-update rule used in the submission was first proposed in the following paper instead of Wei et al. (2021).

Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159–2170, 2020.
summary_of_the_review: Despite the improved iteration complexity, there is still unneglectable ambiguity regarding the rationality of the setting considered and the novelty of the algorithm design and analysis. I am willing to raise the score if the above issues are well addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper discusses policy optimization in two-player zero-sum Markov games with sharp last iterate guarantee.
strength_and_weaknesses: The paper doesn't come with an appendix and I can't verify the correctness of the paper. The discussion about the technical highlight is also very limited. The authors may want to move the episodic case to the appendix and discuss more the proof sketch and technical contribution, including the limits of the existing results. I think it would be super helpful for readers.
clarity,_quality,_novelty_and_reproducibility: The paper doesn't come with an appendix and I can't verify the correctness of the paper.
summary_of_the_review: This paper discusses policy optimization in two-player zero-sum Markov games with a sharp last iterate guarantee. The paper doesn't come with an appendix and covers very little about the proof techniques in the main text.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work studies two player zero-sum Markov games, and develops a policy mirror ascent-type algorithm. Convergence analysis is conducted, which establishes the resultant algorithm achieves a Nash equilibrium depending on the amount of regularization. 

The reviewers were nearly unanimous in confirming the merits of the work relative to prior art. 

Weaknesses of the paper include a lack of experimental validation, and an ablation study of the technical conditions required for convergence in practice. Nonetheless, I recommend this paper be accepted.
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Accept: poster