Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors present a last-iterate linear convergence result for two extra-gradient type algorithms (PU and OMWU, using the paper's terminology) when applied to regularized matrix games. The authors propose a value-iteration based algorithm for solving Makov matrix game where the soft Bellman operator is implemented using PU or OMWU.
main_review: originality and significance

There are several theoretical highlights as already emphasised in the paper, like the last-iterate convergence to saddle point of unregularized matrix games without uniqueness assumption, and the proposal of a value-iteration based algorithm to Markov game.

quality and clarity

The paper is well-written. 
limitations_and_societal_impact: Q1: Has it been established that mirror-prox (extragradient + Bregman divergence) [1]  in the strongly-convex-strongly-concave setting enjoys linear convergence? If yes, what makes this paper (and also several related works like (Wei et al. (2021b)) different?

The reason I ask this is, under the simplex setup of mirror-prox, the mirror-prox updates (and variants) are then just PU and OMWU. If such results for mirror-prox were available, then the results in this paper and several related works would be just special cases of such results. 

To me, it seems that linear convergence of extragradient in the deterministic and strongly-convex-strongly-concave setting should be an available result. However, I did google a little bit and there are no easily accessible results on this. It would be great if the authors could clarify a little bit. The authors also emphasize they handle constrained matrix games but it seems to me that this is not a significant issue under the simplex setup. Please correct me if I am wrong.

[1] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17– 58, 2011.

UPDATE: The authors address my concerns. I maintain my previous rating.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose to use mirror descent to solve classic entropy-regularized competitive games. Linear convergence rates are obtained for the proposed algorithm. In addition, the authors propose to use such an algorithm to solve the subproblem in the entropy-regularized Markov game and obtain a linear convergence rate to the regularized equilibrium.
main_review: Quality: The paper is well written in general.

Clarity: Clear for the most parts. However, I find the Markov game part misleading. The name of Algorithm 3 appears to be a policy optimization method for Markov games while the algorithm actually is a value iteration. The policy extragradient method is only used for solving a subroutine.

Originality/Significance: There are a few concerns on the originality and significance of this work:

1. The algorithms proposed seem to be mirror descent (or mirror-prox) for the saddle point problems. Based on this, if we look at the structure of the entropy-regularized two-player matrix games, it is strongly convex-concave due to the nice geometry brought by the regularization. Thus, the results presented in this paper are not surprising at all (see, e.g., [1]). This makes me wondering: what is the technical novelty of this paper's analysis? How does this paper compare to [1]?

2. The Markov game part resembles the framework of [Perolat 2015]. The difference is only replacing the policy iteration with value iteration, which is mentioned in [Perolat 2015]. For this part, I feel that the result here is only a combination of the already well-known contraction property of regularized Markov games and the results for matrix game solving derived earlier in this paper. I think the authors need to also explicitly highlight the significance here -- is the algorithm for solving Markov games novel, or are the techniques in the analysis here novel?

--------------------------------------------------------------------------------------

More comments:

Definition 2: Is this sampling oracle realistic? How can one sample population quantities?

Independence of $|\mathcal{S}|$: This is a bit counter-intuitive. What is the intuition behind such property? Is this related to the statement "for any $s \in \mathcal{S}$" in Definition 2? 



[1] Mokhtari, Aryan, Asuman Ozdaglar, and Sarath Pattathil. "A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies two standard classes of games with entropy regularization: two-player zero-sum matrix games and zero-sum Markov games. For the regularized matrix games, the authors apply the mirror descent approach (using KL distance) to the regularized objective, and propose two first-order descent/ascent algorithms using different optimistic predictions: the Predictive Update (PU) and the Optimistic Multiplicative Weights Update (OMWU). The authors prove that both algorithms converge to the unique Nash equilibrium of the regularized game with constant stepsizes, linearly. The authors characterize the linear convergence via four measures: KL distance, infinity norm, optimality gap, and duality gap. It is featured by last-iterate convergence and almost dimension-free. For the regularized Markov games, the authors apply the proposed PU and OMWU to the $Q$-value functions at each state and prove the convergence in infinite norm to the optimal $Q$-value function of the regularized game. The convergence rate is slightly worse than the linear rate, but it is also almost dimension-free. The authors also provide computational experiments to verify the usefulness of the proposed algorithms. 
main_review: The authors generalize standard two-player zero-sum matrix games and zero-sum Markov games to be regularized ones with entropy terms. Although adding regularization is not a new idea, the authors establish several benefits theoretically for solving certain regularized game problems. The proposed extragradient algorithms are more general due to an extra regularization parameter. The established convergence results can be more favorable in some aspects, e.g., not need unique Nash equilibrium, if we compare them with existing non-regularized results, e.g., [1,2]. I believe that this work is significant in exploiting the regularization technique for the first time to develop several algorithms for solving game problems with new theoretical guarantees. 

This paper is well-written. The proofs are easy to follow and the experimental results are convincing.   

I only have a few questions regarding quality. 

(1) The studied problems and proposed algorithms include the basic non-regularized cases $\tau = 0$. Your convergence proofs do not seem to work for $\tau = 0$, and they have to reply on the regularized problem structure. This is a possible limitation of your proof technique. It would be great if you could explain it in the paper. Viewing some other results, e.g., OMWU for non-regularized problems [1], could you comment on the gap/difference your proof analysis to [1]? 

(2) As remarked after Theorem 1, the accuracy $\epsilon$ has to be determined in advance to set $\tau$. In practice, this might be the other way around: we often fix some $\tau$ and run the algorithm for many steps in order to get a Nash as accurate as we can. How does your result help with this situation? Is it possible to use diminishing $\tau$?   

(3) A related question to (2) is that do you have a similar scheme for Theorem 2 to get an approximate Nash? diminishing $\tau$?   

(4) In Algorithm 3, it seems that step 5 still needs to know policies from both players. This might raise a concern about implementing it in a decentralized way.  


Here are some minor clarity questions.

(1) line 81. Does it imply both terms in $\max$? 

(2) line 169. Misposition in notation $f$.


References:

[1] Linear last-iterate convergence in constrained saddle-point optimization. ICLR 2021.  

[2] Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. COLT 2021.

============================

POST-REBUTTAL: Thank you for your response. I have read the response and other reviews. The authors have addressed my comments. I just have two final remarks.

(1) I made a few trials of running your code by tunning the regularization parameter. Too small regularization can lead to very slow convergence while it warrants a good accuracy in approximating an unregularized Nash in theory. It would be nice if you could highlight the tradeoff between the convergence speed and the accuracy of a Nash by varying $\tau$. Moreover, for reproducing the Markov game simulations, I recommend supplementing the code for Markov games.

(2) I tried to go over some proof steps I missed in the first round. I found a step in the inequality in line 170 is not straightforward. You might consider adding an explanation, e.g., by the weak duality.

Overall, I do believe this paper has a good quality. The score has been increased accordingly. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors provide an analysis of an entropy regularized extra-gradient method for zero sum games. The proposed algorithms have last iterate convergence guarantees to the equilibrium of the regularized game at rate that is dimension free (up to double logarithmic factors) regardless if the unregularized game has a unique equilibrium. The algorithms can be used to find approximate equilibria of the unregularized game and in Markov zero sum games.
main_review: To the best of my knowledge the analysis of the proposed algorithms is indeed novel. Previous results for the unregularized OMWU required the existence of a unique Nash equilibrium and provided dimension dependent linear convergence rates. The proposed algorithms from the authors resolve both these problems using an entropy regularization.

The major difficulty faced by previous techniques was that the linear rates were only possible in a small area around the equilibrium so a separate analysis was required to bound the number of iterations required to reach this area. The use of regularization by the proposed algorithms obviates this two-step approach and in the process removes most of the dimension dependence.  

This clearly separates the author's work from prior work. I would suggest to the authors to discuss this difference more in the main paper and provide any insight they have about why regularization resolves the technical issues faced by prior work.

I believe that this contribution is significant and can have further applications to other extra-gradient methods for constrained zero sum games. The extension to Markov zero sum games is also a nice addition.  

I have read the authors' response to all reviews. The edits proposed are going to improve the paper and thus I remain in favor of accepting this submission. 
limitations_and_societal_impact: Limitations and negative social impact have been adequately addressed.
review_title: null

Meta-review: The paper studies classical classes of games with entropy regularization.
The proposed algorithm appears to be novel. The paper provides a good contribution to the literature.
I recommend acceptance of the work.
There are a few comments from reviewers that can be addressed as a minor revision when preparing the camera ready version of the paper.
Decision: Accept (Poster)