Venue: NeurIPS 2022 Conference

Reviews:

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 proposes a unified framework (algorithm 1) for Markov games, with symmetric updates and the simultaneous learning of the value functions and the policies. The main theorem (theorem 2) guarantees that the per-state weighted average policies converge to the $\epsilon$-NE (or CCE for the multi-player general-sum setting). The authors show some examples that can be subsumed into the unified framework. Finally, the numerical experiments demonstrate the theoretical results.
strengths_and_weaknesses: **Strengths**:

This general framework can capture many relative algorithms and the authors prove the same convergence rate. The framework consists of two main steps: (1) a policy update by a matrix game solver and (2) a (soft/smooth) value update. However, the update is symmetric and simultaneous, so obtaining the same convergence rate seems to be non-trivial and requires some adaptation. In the numerical experiments, the authors verify the theoretical results first (the results essentially match the order) and show that an eager value update can cause the oscillation issue.


**Weaknesses**:

The state-wise average of policies in Markov games is non-trivial, so the last-iterate convergence is very appealing. Although the current proof only seems to be suitable for the average case, the last-iterate convergence property can still be investigated in experiments. Besides, some variants of OFTRL (e.g., OMWU) can achieve last-iterate convergence with specific update rules, the last-iterate convergence property may be obtained with some adaption.
questions: (1) How does state-wise weight average implement? Is the average policy derived as the weighted sum (Line 7 in Algo. 1) on each state separately?

(2) Are the results of INPG the average or other form of policies?

(3) INPG appears to learn faster than FTRL on layer $h=2$ in Fig.1(b) and the NEGap is always lower than the FTRL (FRTL seems to plateau). Can you show the results with more iterations?

(4) Can the framework readily apply in extensive-form games?
limitations: The current version only establishes the convergence of the average policy, while averaging multiple or even infinite policies in Markov games is non-trivial. The results will be consolidated with the last-iterate property.
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 provides a generic framework for two-player zero-sum Markov Games in the full-information setting. The framework has a guarantee on Nash Equilibrium approximation gaps, depending on the per-state weighted regrets provided by different Matrix Game solvers chosen in the framework. Specifically, this paper instantiates the solver to be Nash V-Learning, GDA-Critic, Nash Q-Learning, and Nash-PI, then proves their detailed NE gap guarantees. Further, this paper shows that optimistic FTRL gives a $\tilde{O} (T^{-5/6})$ NE gap, which is the state-of-the-art for symmetric, policy optimization type algorithms in two-player zero-sum MGs. The results can be extended to multi-player general-sum MGs for a Coarse Correlated Equilibrium. Some simulations corroborate the results and incur interesting new problems.
strengths_and_weaknesses: Strengths:
1. The framework (Algorithm 1) and its general guarantee (Theorem 2) are useful for future works. Researchers may focus on the per-state regrets and then easily get a NE gap using the framework and guarantee.
2. The $\tilde{O} (T^{-5/6})$ NE gap for OFTRL is currently the best result.
3. The simulation results raise new open problems, which are interesting in my view.


Weaknesses:
1. Some of the concepts need to be provided in the main text. For example, full-information learning, policy optimization type/like algorithms, layer-wise learning, one/two-sided regrets, etc.
2. There lack of comparison between algorithms used in Section 3.2. There are many theoretical results, and the authors did not make it clear whether they are comparable.
3. In practice we cannot apply full information learning. So there is a need for generalization to sample-based learning.
questions: Basically, the question is about (1) and (2) in Weaknesses.
* What is the difference between policy optimization type/like algorithms?
* Are there any other taxonomic standards which create barrier or gaps in the NE convergence result?

The authors can add more details to Section 3.2, Section 4, and Section 5, like a clear summary of different algorithms and their traits, whether they are policy optimization -type or -like, etc. 
limitations: As the authors stated that it is an open question on generalization to sample-based setting, there are no other fundamental limitations.
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: The authors study a unifying meta-algorithm for two-player zero-sum Markov games in the full information setting. The proposed framework aims to generalize some specific algorithms that perform symmetric updates among agents, and the simultaneous learning of policies and their values: relying on upper bound assumptions on the regrets of the employed sub-routines, the authors give a general theoretical result on the convergence of the framework to approximated Nash Equilibria. Beyond providing some examples of how existing algorithms can fit in the proposed framework, the authors use a particular policy update scheme and obtain an overall new algorithm with an improved convergence rate.

strengths_and_weaknesses: The paper is well written, and it is mathematically sound. The required background is nicely summarized, the theoretical results are well described, and their requirements clearly stated.
The attempt to put some order in the huge body of literature on RL algorithm for Markov Games is admirable and welcome.

On the other side, the strong theoretical limitations required by this work (full-information setting, tabular representation) raise some concern about his impact and importance (either theoretical or, above all, practical).
questions: 1) On line 267, the authors make consideration of an improved rate for OFTRL which requires two-sided regret bounds.
This consideration seems important, but the authors relegate it to a quick citation.
What is the difference between one-sided and two-sided regret?
The authors say that two-sided regret does not imply one-sided regrets, but the opposite hold?
limitations: N/A
review_title: null

Meta-review: metareview: The paper makes interesting progress on issues related to multi-agent reinforcement learning providing fast convergence guarantees as well as a unified framework. This is definitely a hot topic of research and it would make for a nice NeurIPS contribution.
confidence: Certain
Decision: Accept