Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the so-called two-player zero-sum Markov game. They provides theoretical analysis of the convergence (to the Nash equilibrium) of practical gradient descent ascent (GDA) algorithms with some new numerical tools. In particular, they introduce an entropy regularization to the value function of the original game, and shows the linear convergence of GDA to the equilibrium point of the regularized game.

In addition, in order to derive practical algorithms to solve the original problem, they also studies a critical parameter, the weight parameter of the regularizer. Since there is a clear trade-off between improving convergence rate and minimizing the gap between the regularized game and the original one, they provide some practical schemes to adjust the regularization weight. The hope is that when the regularization weight is iteratively reduced to zero, the GDA algorithm will converge to the Nash equilibrium of the original game and hence the original game will be solved.
strengths_and_weaknesses: Strength:
1. The paper is well-written, self-contained and organized. 
2. This work extends the current research on finding the Nash equilibrium of two-player zero-sum Markov game. They provide significant contributions to convergence analysis of practical gradient-based algorithms.
3. They also derive some practical algorithms to apply their regularization technique to solve the original game.

Weakness:
1. The description of the numerical experiments part is too simplified. I would like to see more details, for example, more information about the game environment, why the current setting of the synthetic game is chosen, more analysis on the results.  Although some of the details have been provided in appendix, but I think that is not enough, and some details should be put into the main paper.
2. The role of Assumption 2 played in the main results of this work is not clear. As the paper itself mentioned, some of the experimental results show that the Algorithm 2 still converges correctly when it is applied to a Markov game that does not observe Assumption 2. 
3. In some of experimental results,  the pure GDA approach without regularization also has a last-iterate convergence and does not exhibit the oscillation behavior. Did the authors choose an appropriate game environment to valid their contributions?
4. The idea of introducing an entropy regularizer to improve the structure of the game is straightforward.

questions: The questions are listed above.
limitations: no.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper provided a new algorithm to find the Nash equilibrium for a two-player zero-sum Markov game. The new algorithm is based on a gradient descent with KL regularization. For completely mixed Markov games, the authors prove that the algorithm can find Nash equilibrium efficiently. They also conduct a simple experiment for tabular Markov games with low dimensions. The experiments support their main theoretical results and show that their algorithm may also work for the Markov games that are not completely mixed.
strengths_and_weaknesses: This paper is well organized, and the proofs seem sound to me. However, I still have several concerns about the clarity and significance of the main results. 

1. The main result of this paper only works for "completely mixed Markov games." I would recommend the authors indicate that in the title. Otherwise, it would be kind of misleading. Moreover, completely mixed Markov games seem quite strong in the applications, which may limit the significance of the theoretical result.

2. The authors conduct experiments and show that their algorithm may work for Markov games without completely mixed assumptions. However, the experiment is too simple to support their claims seems it is a tubular Markov game with dimension 2. 

3. One of the biggest advantages of using gradient descent to solve Markov games is that it can deal with complex models. However, this paper only conducted simple tubular Markov games by using a tabular softmax policy parameterization. Can the algorithm be applied to Markov games with more complex structures, such as with linear function approximation [1,2] or general function approximation [3]?

4. This paper assumes that we can access the expected value function during the training and doesn't consider the exploration problem. 


[1] Xie, Qiaomin, et al. "Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium." Conference on learning theory. PMLR, 2020.

[2] Chen, Zixiang, Dongruo Zhou, and Quanquan Gu. "Almost optimal algorithms for two-player Markov games with linear function approximation." arXiv preprint arXiv:2102.07404 (2021).

[3] Huang, Baihe, et al. "Towards general function approximation in zero-sum Markov games." arXiv preprint arXiv:2107.14702 (2021).

questions: 1. How can we access the gradient $\nabla J$?

2. Can this algorithm be applied to Markov games with more complex structures?

3. What's the advantage of the new algorithm compared with other algorithms that are designed for tabular settings such as [4]?


[4] Bai, Yu, and Chi Jin. "Provable self-play algorithms for competitive reinforcement learning." International conference on machine learning. PMLR, 2020.
limitations: The authors have addressed their work's limitations and potential negative social impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper develops policy gradient algorithms for entropy-regularized zero-sum games. Under some assumptions, the authors show that the entropy-regularized objective function obeys a Polyak-Łojasiewicz type condition, which allows linear convergence of policy-gradient-based GDA to the equilibrium point of the regularized game. Then, the authors propose two scheduling schemes for the regularization parameter and analyze their convergence and complexities. 
strengths_and_weaknesses: Strength: comprehensive theoretical result.

Weakness: It is still not clear why Assumption 2 is needed and justifiable. 
questions: Overall, the paper is well written, and the references are properly cited. I have the following questions/comments.

1. Entropy-regularized zero-sum game has been studied in the existing literature (Cen 2021), and I think this paper provides a policy-gradient-based solution and complexity analysis. 

2. The convergence metric used in this paper is different from the duality gap metric used in Cen 2021, is there a connection between these two metrics? How do your convergence rate and complexity compare with those established in Cen 2021?

3. Comparing with the analysis of Cen 2021, the authors stated that they discuss and leverage structure in the regularized Markov
game that was previously unknown. While I agree that the policy gradient approach and PL condition of the Entropy-regularized zero-sum game were not discussed in Cen 2021, their analysis actually leverages certain similar structures implicitly. Specifically, Cen 2021 follows the standard value iteration algorithm that has a linear convergence rate. In the inner loop, they need to solve an entropy-regularized bilinear matrix game, which satisfies a strongly-convex-strongly-concave type geometry due to the entropy regularization (w.r.t to the $\ell_1$ norm). In their convergence proof, this geometry helps them achieve a linear convergence. 
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper shows last iterate convergence for regularized gradient descent-ascent on markov games with finite state and action space under the assumption that the smallest coefficients of the support of the regularized markov games are uniformly (uniformly lower bounded over the regularization parameter.) Additionally, the authors assume that the initial state distribution has a full support. 
strengths_and_weaknesses: 
strengths:
- To the extent of my knowledge, the result seems novel and relevant to the community.
- This paper is well written. 

weaknesses: 
- Assumption 2 is strong and does not seem necessary.
- There is no discussion on the optimality of the rate proposed rate. 
- Algorithm is not practical since one needs access to the (full) gradient of J.
- The authors could do more experiments to investigate these questions left open. 

questions: - After (1), you mention that J is non-concave with respect to the policy of the first player. But it seems to me that J is actually linear (with respect to the policy) since we have $$V^{\lambda \pi_1 + (1-\lambda)\pi_2,\phi} = \lambda V^{\pi_1,\phi}  + (1-\lambda) V^{\pi_2,\phi}$$ (playing according to the mixed policy is equivalent to tossing a coin and playing according to either the first or the second policy). Can you comment on that point?
- What is your opinion on the optimal convergence rate? Are there lower bounds ? (since the problem is nonconcave-nonconvex in the parameters pre-softmax the standard convex-concave lower bounds do not hold) 
- It seems that Assumption 2 could be connected to the Maximum entropy Nash (MaxEnt). (the lower bound should be on the support of the MaxEnt. One way to prove such a result could be by saying that the MaxEnt is the limit of the regularized Nash. Since the Regularized Nash always has full support (the regularization goes to +\infty for non-full support solutions) and its limit (the MaxEnt for no regularization and the uniform distribution for infinite regularization) also has full support, there exists a (uniform) lower bound on the support of any regularized Nash. However, it does not show that this lower bound is the lower bound on the MaxEnt (which seems intuitively true). Any comment on that?


I will be eager to increase my score if the authors answer my questions and are able to show that Assumption 2 can be relaxed. 
limitations: - This work is limited to the full batch case which is not practical.
- The proposed rate may be suboptimal. It could be interesting to investigate experimentally different decays ($1/t$, $1/\sqrt{t}$). 
- Also a log-log scale for the plots could help to visualize the experimental convergence rate.
review_title: null

Meta-review: metareview: The paper studies the problem of finding the Nash equilibrium of a two-player zero-sum Markov game. Despite nonconvexity, this min-max optimization satisfies the PL condition and hence it is "easy" to solve. The authors rigorously studied the iteration complexity of this problem. The reviewers found the paper well organized and self-contained. The reviewers also found the contributions of the work solid. I recommend acceptance of the work. It would be great if the authors can address the reviewer's concerns and particularly the following concerns in the final version of the paper (most of which were answered in the discussion forum, but not in the paper):
- Please include discussions on various related works (such as[Cen 2021], [Perolat 2015], [Yu 2020] in the paper.) Please avoid having a "laundry list" type of citations, and do your best to discuss each of these works to the extent possible in the paper given one additional page (as done in the discussion forum). In addition, some of the references are closely related. For example, [Yang et al 2020]'s two-sided PL setting is closely related to the paper. Also, [Ostrovskii et al 2021] considers non-Euclidean geometries which is closely related to entropy regularization. 
- Please include more details on the experiments (see the individual reviews)
- Please include the discussion on Assumption 2 (see the individual reviews)

confidence: Certain
Decision: Accept