Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a novel class of Markov Games that generalize classical potential games in the normal-form representation. They show that such games always admit deterministic Nash policies, and that they enjoy some interesting properties that they make them a more suitable generalization of potential games than other attempts in the literature. The main result of the paper is that, in Markov Potential Games, policy gradient algorithms converge to Nash. The authors also provide an experimental analysis on congestion games. 
main_review: Originality: I think that the problem studied by authors is interesting, and that the paper makes a significant contribution to the research area. The idea behind the definition of Markov Potential Game is novel, and I think it provides a nice and clean generalization of its normal-form counterpart. 

Quality: As far as I am concerned, the technical claims are correct.

Clarity: The paper is well written, but I think that some modifications would help clarify it. For instance, the authors could better clarify the difference between (a) and (b) in Theorem 1.1 at the beginning, since I needed to step forward to the formal result later in the paper to better figure out what was going on. Also, the technical review is quite dense and hard to follow. Maybe, it's better to do not go into technicalities in the Introduction and add some more intuitions when the technical part comes into play.

Significance: I think that the paper would have a good fit in the NeurIPS conference.
limitations_and_societal_impact: Adequate.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper focuses on one of the game theoretic views of Reinforcement Learning: the convergence of policy gradient in games of several agents. The authors build on the existing theory by adding new definitions that support the multi-agent learning systems in order to measure the complexity of the convergence of the policy gradient to Nash policies.
main_review: The paper is written in a clear and formal manner. The conclusions seem to respect the stated theorems (as corollaries). The next section has some points about the specificity of the paper's context and its novelty results.
limitations_and_societal_impact: The paper builds on [10] of the included literature, where the authors had introduced the first independent policy gradient algorithms for competitive reinforcement learning in zero-sum stochastic game. The main result of the current paper is the fast convergence of these algorithms to the so-called 'Nash policy'.

1) This seems an interesting result but It seems to make a minor contribution to a reasonable problem. It looks like a simply developed extension of the previous paper. Its novelty and significance as far as the paper's modelling is concerned (as a whole) needs to be validated.
From a first point of view, the results do not seem like a breakthrough. 

2) The 'novel definition of MPGs that generalizes prior attempts' is interesting from the theory point of view, but it seems that it is specially developed here so that it creates a desired context. That is, it seems like a theoretical construction which supports the result, rather than solving a core problem that had arisen in [10].

3) Also, although is it a well suited result for the theory of Markov Decision Processes (MDPs) founded in [10], I am not certain of how significant it is for the readers of this conference. The focus is mainly game-theoretic and about the complexity of this game, rather than in the theory of Learning. The theorems concern the relation of Markov Potential Games to (MDPs) and conclude the convergence to an \epsilon-Nash policy. This sounds like a Game Theory result.

Which are the learning systems that benefit from the fast convergence? 
Are there any 'common' machine learning systems that benefit from this?

4) The authors list an example of an eight agent congestion game which is demonstrating the MPG property. What is the applicability of this example and their convergence result in a learning context with several agents? Have the authors tried to apply that somewhere in machine learning? Can they present this in the paper?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors present a new definition of Markov Potential Games (MPG). They discuss the relationship between MPG, normal form potential game, and Markov games where every state-game is a potential game.  They study MPGs by presenting sufﬁcient conditions for MPGs and the existence of deterministic Nash policies.  They show the conference of independent-playing policy gradient to Nash policies, in both exact gradient case and finite sample case. Experiment results validate the congergence.
main_review: - Significance: 
MPG serves as an important and fundamental setting towards understanding multi-agent systems. Understanding the behavior of standard methods such as policy gradient is of central interest in the relevant literature. Hence this paper provides a solid contribution. 

- Quality and Clarity: 
The authors have conducted a clear theoretical analysis, which seems to be very rigorous. In the experiments, the authors conducted congestion games to validate the predicted convergence clearly. 

- Originality: 
The definition of MPG in the present paper is novel to my knowledge.  The proof of convergence via gradient dominance is commonly used. To improve the originality, I believe the author could discuss more what's the difference between MPG defined in this paper and in some other papers, for example:

> Macua, Sergio Valcarcel, Javier Zazo, and Santiago Zazo. "Learning parametric closed-loop policies for markov potential games." arXiv preprint arXiv:1802.00899 (2018).

Overall, this paper is worthy of acceptance to me. I'm glad to increase my score if the discussions are provided and more experiments on some other examples of MPGs could be conducted.

- Minor points: In equation (3), should the $\alpha_i$ be $\alpha$? A similar typo exists in the full version too (eq (4)).
limitations_and_societal_impact: No visible negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers a multi-agent coordination setting as all agent utilities are perfectly aligned with each other via a common potential function. The authors claim that they present a novel function of Markov Potential Game (MPG) and prove fast convergence of independent policy gradient to Nash policies.
main_review: Potential game is one of the key concepts in multiagent reinforcement learning, especially when the cooperative setting is assumed. The main question of this paper is fast convergence guarantees for multi-agent RL, and the reviewer believes this is an important question. Even though this paper has a well-designed direction, however, the reviewer thinks the current version of the manuscript is not ready to be published at NeurIPS. 


1. Are the findings meaningful for MARL researchers?

Theorem 1.2 is an important finding but it needs more discussion whether it is meaningful results in the perspective of multi-agent reinforcement learning. First of all, Theorem 1.2(a) is trivial unless it provides uniqueness. Next, Theorem 1.2(b) is a meaningful finding so we need Theorem 1.2(c) to find conditions for an MDP to be an MPG. The conditions for it are provided in Proposition 3.2. C1 claims that the state transition function should not depend on the action. In this case, RL is not necessary since RL is the effort to find an optimal action. 
The reviewer believes that C2 is a meaningful part, leading that we need immediate reward which only includes the potential term. However, is it easy to decouple the reward to common term and dummy term? Most cooperative MARL problems have coupled reward functions. It would be beneficial to provide examples of reward function of standard MARL benchmarks (e.g., Starcraft, Hanabi, OpenAI hide-and-seek, etc). 


2. Can the main document stand alone?

The authors simply provide a long version document (31 pages) as supplementary material where a lot of parts are overlapped with the main document. If they separate the contents into main document and supplementary material, the main paper would be easy to follow, and supplementary material will be helpful. Currently, it is hard to find a piece of proper information in supplementary material since it is another long document. 
In addition, there are a lot of never-defined notations in the main document. In the current format, the main paper cannot stand alone without supplementary, which is not desirable. 


limitations_and_societal_impact: The authors provide open questions.
review_title: null

Meta-review: The discussion of this paper raised a lot of points that, I hope, will be useful to the authors:
1. there is no concern on the mathematical derivation; this is a very good selling point, but it is not sufficient
2. while there is a strong agreement that this paper would perfectly fit with more game-theory oriented venues, there are objections that, in the current form, it fits with ML venues: in particular, the authors should strengthen the learning theory part. As remarked by some Reviewers and argued in the rebuttals by the authors, some parts of the paper should be re-organized, thus requiring a second round of reviewing. 

My suggestion to the authors is to implement the comments raised by the Reviewers carefully. The converge result is nice and a bit of effort spent to re-organize the paper will lead to a very probable acceptance in a top-rated ML conference. 
Decision: Reject