Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces the Markov Potential Game (MPG), which generalizes the classical potential game. The authors then point out several properties of MPG. It proves the convergence to $\epsilon$-NE for learning agents following independent policy gradient or stochastic gradient. The paper also presents the experiment on a MPG of congestion games that verifies the theoretical results.
main_review: Strength:

1. The paper did a great job introducing the MPG and showing us intuitions about the game with examples and observations.
2. The paper proved the convergence to $\epsilon$-NE and provided the convergence rate for learning agents following independent policy gradient or stochastic gradient in MPG.
3. The paper additionally provides the empirical results to verify the convergence.  
4. The paper describes several meaningful open questions and future directions that I find quite valuable.

Weakness:

1. I wish to see more MPG instances (e.g., with potential function of different smoothness or convexity) in the empirical evaluation and wonder how the performance of multiagent learning differs in different games. I think it is also possible to include classical RL algorithms and see how they perform compared to policy gradients.
2. The paper could have a much more profound technical contribution if it could touch upon any of the open questions mentioned in the end.

Questions:

1. Is it possible to generalize the theorem such that the algorithm does not need to know the number of iteration beforehand, in analogy to the doubling trick in bandit literature?
2. Is it possible to generalize the game setting to infinity state setting using the techniques from literature [1] of linear Markov decision process? It seems to me the MPG definition can be further generalized in this way.

[1] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on Learning Theory. PMLR, 2020.

summary_of_the_review: The paper is overall well-written and established the preliminary studies of MPG problem and multi-agent learning algorithm for convergences, though there are still many unsolved questions in MPG such as Price of Anarchy. Therefore, I recommend a weak-accept of this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper carefully studies the definition of Markov potential games, and establishes the similarities and differences from the stateless case. It also shows the global convergence of independent policy gradient methods for Markov potential games, to the Nash policies. 
main_review: Strengths:
1. The definition of Markov potential games is known to be more delicate than that in the matrix (stateless) case. The authors have done a good job defining and giving (counter)-examples, in order to demonstrate this subtlety, mainly stemming from the introduction of the transition dynamics. This part, to my knowledge, has not been discussed in the literature before.
2. Both global convergence (for both the model-based and model-free setting) and sample complexity results (for the model-free setting) have been established, for finding the Nash equilibrium of the Markov potential game.


Weakness:
1. The global convergence, especially the exact case, is more-or-less expected, given Agarwal et al., 2020. In particular, given the opponent's policy being fixed, first-order stationarity => best-response, can be derived directly from that reference, which further leads to the definition of Nash equilibrium in the game setting. Hence, the novelty of this part, regarding optimization landscape and global convergence, is relatively limited. 
2. It is claimed in the abstract that the convergence is "polynomially fast". I am not very sure about the accuracy and commonality of the wording. In fact, the $1/{\sqrt T}$ rate is not a fast one, but a standard one adapted from general nonconvex optimization.
3. Can the results in Theorem 4.4 be improved by choosing different parameters, e.g., alpha, eta, and T. It seems that $\epsilon^{-6}$ is not the standard rate in nonconvex stochastic optimization. 
4. Some typos have been spotted, and some arguments are not accurate/professional: 
1) Around Eq. (2), how the horizon length H is sampled (in fact, for unbiasdness, it should be sampled from a geometric distribution), is missed. Note that the setting in Daskalakis et al. (2020) is a finite-horizon one with random T (not an infinite horizon discounted one). So I am not sure if Lemma C.4's proof in this paper follows by just citing the results there directly. In fact, for infinite horizon discounted setting, the unbiasedness and bounded variance property of this estimator has been established before Daskalakis et al. (2020), see e.g., https://arxiv.org/pdf/1906.08383.pdf; https://arxiv.org/pdf/1807.11274.pdf. 
2) The constants in the main theorems (and their dependences on the problem parameters) may need double-check.
5. How do the results compare with the very related recent work of https://arxiv.org/pdf/2106.00198.pdf? It might be worth discussing the differences between the two (thought I suppose it might be possible that the two works are concurrent). 

summary_of_the_review: In general, the paper is well-written, and I enjoy reading it. It has made valid contribution on multi-agent RL in potential games. With the minor comments above being addressed, I believe it can be a good paper deserving publication.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies Markov potential games (MPGs) that genralizes the classical normal form potential games. They show that each agent playing individual policy gradient guarantees the convergence to Nash policies with polynomially decaying error rate. 	
main_review: Overall, this paper is well written. The theoretical analysis of this paper is presented clearly and seems to be rigorous. 

My main concern is whether the so-defined MPGs are of enough interest. Specifically, in Prop $3.2$  (C1),  for an MDP to be an MPG, the state transition cannot be affected by the action, which is unrealistic in MARL setting. Second, in (C2), it remains unclear how to check whether the immediate rewards can be decomposed into the desired form with individual dummy terms. The authors only present a trivial example where $u_s^i$ is some constant $c^i$. Third, for cases of non-trivial state transition, the authors only provide a 2-agent MDP example in Figure 3. As a result, I think the practical applications of this paper are restricted.
summary_of_the_review: Although the theoretical analysis of this paper is well-organized and seems to be rigorous, the so-defined MPGs seem unrealistic in the MARL setting and are restrictive in practical applications.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper examines the projected policy gradient method in markov potential games (MPG). The paper i) proves the existence of deterministic Nash policies in MPG, ii) analyzes the sufficient conditions for MPG, and iii) proves the convergece of projected (stochastic) gradient ascent to Nash policies in MPG.
main_review: Strength: This paper considers an important research topic --- policy gradient in markov potential games (MPG) and provides interesting new insights on this topic. The existence of deterministic Nash policies in MPG is somewhat not surprising though, I find the examples 1 and 2, which shows the potentiality at every state may not lead to MPG, illuminating. The methodology for analyzing the convergence property of the projected (stochastic) policy gradient seems to be adapted from some previous works. However, in general, the presented convergence results in MPG are novel.

Weakness: Some related works have not been discussed in the paper. For example, the paper "Stochastic Potential Games" (https://arxiv.org/pdf/2005.13527v1.pdf) also considers potential games with multiple states. I wonder how Theorem 3.1 of this paper is different from Theorem 1 of "Stochastic Potential Games." The paper is generally well-written, but some parts remain unclear:
1. For Condition C2 of Proposition 3.2,  the authors state that "the dummy terms of each agent's immediate rewards are equal across all states." Intuitively, this seems to suggest that $u_s^i(\vec{a}_{-i})$ equals some constant for all states, which is not in line with the condition formalized right after the statement. So how to interpret the formalism of C2? I think a more clear and precise interpretation is needed. 
2. The example provided in Figure 3 assumes that $p_0$ does not depend on agents' actions. Suppose there is a 2-player MDP which is not potential at every state and $p_0$ depends on agents' actions, is it possible that this 2-player MDP is an MPG?
3. Section 4 is rather dense and not easy to follow. In the meantime, Section 5 does not provide much new knowledge about congestion games. The authors may consider moving some parts of Section 5 to the Appendix and providing more explanations (such as the definitions and prior results required to derive Theorem 4.2) in Section 4. 

summary_of_the_review: This paper provides interesting, new, and important theoretical results for policy gradient in markov potential games.
review_title: null

Meta-review: This paper considers an important problem, Multi-Agent Reinforcement Learning, and looks at a subclass of problem, the Markov Potential Game.

Even though this class is not the more generic one (as pointed out by a reviewer), one must start somewhere before (and maybe the results cannot easily or at all be extended to a larger class), so I will not personally take this as a strong negative concern.

The other reviewers are rather positive about the result and the techniques, and I concur with them. 

I will therefore recommend acceptance.
Decision: Accept (Poster)