Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a symmetric and rational algorithm for finding Nash policies for a two player zero sum Markov game that converges in linear time. Additionally the algorithm proposed does not rely on computing the equilibria of a regularized Markov game. 

The key idea of this work is to combine a slow algorithm that enjoys global convergence to the Nash equilibrium and a fast algorithm whose linear convergence rate is only guaranteed close to the Nash equilibrium. The authors not only show how to instantiate the proposed components of their work but also how to combine them in a single unified algorithm. Importantly, this unification of the two components works despite the fact that the algorithm cannot detect if the iterates are in the linear convergence region of the fast algorithm.
strength_and_weaknesses: Regarding strengths, to the best of my knowledge the proposed algorithms have state of the art convergence rates for the problem of zero sum Markov games. At the same time, the algorithm remains symmetric and rational and does not rely on regularization, making the results even more surprising.

Regarding the techniques used, they are also to the best of my knowledge novel. While two phase style techniques (global slow rates and local fast rates)  are pretty common even in the case of matrix games, these results are typically analyzing the performance of a single update rule that becomes faster closer to the equilibrium. Here the authors combine two distinct algorithms where one is responsible for the global convergence and the other for the fast rates. These two algorithms do not only have different rates, they are also qualitatively different as one relies on averaging and the other has last-iterate style guarantees. The instantiation of the local algorithm using OGDA may be of independent interest.

Regarding the minor weaknesses of this work, it is still unclear to me why an averaging style algorithm is required for the global step is unclear to me. Since fast convergence is not required, why cannot we employ last iterate results from prior work for this step. If the authors could explain the reasoning, it would be helpful.  

 
clarity,_quality,_novelty_and_reproducibility: The writing is clear and concise and the organization of the paper is very helpful especially for non-expert readers who seek to understand the high level ideas first before going deeper into the analysis. As discussed, the approach and results are to the best of my knowledge novel. No reproducibility concerns since there is no experimental evaluation. 
summary_of_the_review: In summary, based on the strong and novel results I am recommending acceptance of this work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper consider the problem of finding a Nash equilibrium in 2-player, zero-sum Markov games. The contributions are 1) a decentralized, meta-algorithm Homotopy-PO that converges to a Nash equilibrium at a global linear rate. It relies on two subroutines, Global-Slow and Local-Fast. 2) An instantiation of Homotopy-PO with choices for Global-Slow and Local-Fast that achieves the global linear rate of convergence. Further, the algorithms provided are symmetric and rational.
strength_and_weaknesses: # Strengths
- Finding Nash equilibria in 2-player Markov games is an important problem. Existing methods are restricted to special classes of games (matrix games); have sublinear rates of convergence; or are approximations of Nash equilibria (such as quantal response equilibria).
- The symmetric, decentralized setting, in which the algorithm is symmetric wrt the agents and the agents observe dynamic, local information without being aware of the policy of the opponent.
- The methods proposed are novel; the idea of using a slow, global algorithm used to guide a fast, local algorithm that only works on a neighborhood of a Nash equilibrium is very interesting.
- The fast, local algorithm proposed is of independent interest.

# Weaknesses
- Unclear how practical the algorithms are, as no implementation or empirical validation is provided. It would be nice if the global, linear convergence actually translates into a fast and practical algorithm.
clarity,_quality,_novelty_and_reproducibility: High quality, clarity and originality.
summary_of_the_review: Based on the above comments, the paper is a clear accept.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: This paper investigates decentralized policy optimization algorithm for two-player zero-sum discounted Markov games. In particular, it proposes a decentralized meta-algorithm called $\mathsf{Homotopy}$-$\mathsf{PO}$ that has global linear convergence rate if the its two base algorithms have the desired properties. Then, it proves that Averaging OGDA and OGDA can serve as the two base algorithms for $\mathsf{Homotopy}$-$\mathsf{PO}$, resulting a concrete decentralized algorithm with linear convergence rate.
strength_and_weaknesses: ### Strengths
This paper proposes the first decentralized algorithm with global linear convergence rate, which is considered to be significant. Meanwhile, the construction of the meta-algorithm is based on a very clear and novel intuition, which has potential wider application since it only requires the base algorithms to satisfy certain properties. Furthermore, proving that OGDA has local linear convergence itself is also considered to be significant and novel.

### Weaknesses
Based on the decentralized implementation of the two base algorithms OGDA and Averaging OGDA, it seems translating the current optimization algorithm to a learning algorithm contains some inherent difficulty. In particular, the initialization needs to solve the marginal MDP completely, which looks hard to approximate during the learning process. Is there any approach to relax it so that we can translate it to a learning algorithm easily? 

Nevertheless, from my perspective, it is okay to leave this as future work for now.

---

**Post-rebuttal update:** concerns and questions have been well-addressed.
clarity,_quality,_novelty_and_reproducibility: As discussed above, this paper is well-written and contains high novelty. Meanwhile, there are also several questions as the following.

### Questions
- What is the intuition of using $\underline{\mathbf{q}}_s^{t}$ (and correspondingly $\overline{\mathbf{q}}_s^{t}$) for update in Averaging OGDA? More specifically, what is the intuitive difference between the update rules of Averaging OGDA and OGDA?
- Is that possible to extend this idea to a learning algorithm (in which we cannot compute $\mathbf{Q}$ exactly) with linear convergence?
- Why the linear convergence of $\mathsf{LOCAL}$-$\mathsf{FAST}$ requires the initialization $\hat{\mathbf{z}}$ to be close enough to $\mathcal{Z}^*$? Is this requirement fundamental?
- What is the rough magnitude of $c_+$ in terms other problem parameters?
- Is that possible to translate the convergence results in this paper to the version in terms of Nash gap (i.e. $\max_{s\in\mathcal{S}}\left(V^{\mathbf{x}^t, \dagger}(s)-V^{\dagger, \mathbf{y}^t}(s)\right)$)?

### Suggestions on Writing
- $\eta'$->$\eta$ in equation (2).
- $k\geq k^*$->$k\geq k_1^*$ after **Hidden Phase II** at the bottom of page 5.
- It may be better to also explicitly state the rationality of $\mathsf{Homotopy}$-$\mathsf{PO}$ as a theorem.
summary_of_the_review: This paper proposes the first decentralized algorithm with linear convergence rate in discounted two-player zero-sum Markov games, which is considered to be novel and significant. Meanwhile, it also contains some novel techniques may be of independent interest. Although its practicability looks limited now, it is okay to leave it as future work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies policy optimization for Markov Games to find the Nash equilibrium. The authors parameterize the policy by directly considering the probability for each state and action. The key contribution of this work is to propose a slow-fast framework with a series of conditions, and prove that any pair of slow and fast optimization algorithms that satisfy the above conditions, can enjoy a linear convergence rate to the Nash equilibrium. 
strength_and_weaknesses: Pros:
- The presentation is very clear, and the writing is also flawless. 
- The proposed framework is general, and the convergence result is important. 

Cons:
- No experiments. 
clarity,_quality,_novelty_and_reproducibility: Both the algorithm and analysis seem new to me. 
summary_of_the_review: In general, this paper did a good job of showing a global linear convergence to the Nash equilibrium for Markov Games. The idea to use hidden phases to analyze the convergence of slow and fast algorithms is quite interesting, and I believe this can be extended to other policy optimization problems considered in reinforcement learning. The only shortcoming of this paper is the lack of experiments, and I suggest the authors do some at least on some simulated datasets, especially to see how the large constant ($(1-c\eta^2)^{-poly}$ in (9)) affect the final convergence behavior.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies decentralized learning in two-player zero-sum discounted Markov games, when the players observation are the marginal reward and transition functions. An algorithm is provided to find approximate Nash-equilibrium policies exponentially fast: both players independently play an algorithm that switches back and forth between a slower global optimization algorithm and a faster local optimization algorithm (which converges locally at a linear rate) according to a doubling-like schedule. It is shown that the global and local algorithms can be instantiated with averaging optimistic gradient descent-ascent and optimistic gradient descent-ascent, respectively. All reviewers found this algorithm original and interesting, and the result is the first algorithm to find a Nash equilibrium in this setting at a linear rate, while at the same time it is also decentralized, symmetric, and rational.

Weaknesses: 
- The observation structure in the paper is somewhat unrealistic, which limits its usefulness. In the response the authors addressed this question by describing how one can obtain an actual learning algorithm with real observations -- their response should be incorporated in the final version (response to Reviewer p6su).
- In the response the authors present lots of intuition about OGDA and AOGDA, which should be incorporated in the main body of the paper (I hope an extra page will be available for this for the final version).
- During the rebuttal the authors provided interesting experiments, which demonstrate how the proposed algorithm work. It would be interesting to see how earlier algorithms in the literature behave in these example -- please include these additional experiments.
justification_for_why_not_higher_score: Limitations about the observation structure.
justification_for_why_not_lower_score: All reviewers found the idea in the paper interesting and original, and I also agree with them.
Decision: Accept: notable-top-25%