Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the global convergence of policy gradient for multiagent Markov potential games. The authors define a notion of potential markov games that seems natural and show convergence to Nash policies when the agents use gradient ascent independently on their policies (using direct parametrization). Observe that the authors assume that the agents have full knowledge of their utilities and their derivatives (their algorithm is deterministic). They also provide convergence for the stochastic variant of policy gradient (given samples).
They moreover show that deterministic Nash policies always exist and show that fully mixed policies are saddle points. Saddle points might be of higher order, so first order methods might fail to avoid the fully mixed policies because you need to check third (or higher) order derivatives (so techniques from Ge et al do not help to show avoidance as claimed, the authors need to remove that comment since Ge et al argue about second order stationarity).
main_review: The main idea is to use the gradient domination property established in Agarwal et al., 2020 and argue that stationary points of the potential function are indeed approximate Nash policies. Then using techniques from non-convex optimization, it is known that Gradient Descent converges to stationary points and this is what they show about policy gradient on the potential function. The analysis of the stochastic variant is much more challenging, it needs different parametrization than direct parametrizatoin. In general, i feel the paper has made a valid contribution on multi-agent RL in potential games.
summary_of_the_review: I feel the paper has solid contributions, they address both deterministic and stochastic variant of Policy gradient. The stochastic variant is more challenging due to the limitation of the non-Lipschitz gradient.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study independent gradient play in Stochastic Games, with multiple players/agents. They characterize the (local) stability of strict Nash in Stochastic Games. In addition they study Markov Potential Games, a subclass of Stochastic Games and show global convergence of projected gradient ascent for direct paramterization of Tabular MDPs. In addition, they also provide a sample-based RL algorithm, where the players do not use gradient information from others and estimate based on the observed trajectories. They show non-asymptotic convergence guarantees of this algorithm for Tabular MDPs which are Markov Potential Games.
main_review: Strengths:

They study general Stochastic games with multiple players (more than two) and a provide a local characterization of the strict NE which is novel, as it applies for general stochastic games with no assumption. Although, here the gradient of each player does seem to depend on the information from other players.
They provide a sample-based RL algorithm with non-asymptotic guarantees for Markov Potential Games, with fully independent gradient updates for each players.


Weaknesses:
The issue is that the existence of Strict Nash for Stochastic Games maybe a strong assumption. This may be quite rare even when considering normal form games. 

Given the result of [Daskalakis et al. 2021] (which is not cited in this paper), that show that independent RL (with a two time scale approach) for two player Stochastic Zero-Sum games converges to the epsilon-Nash policy globally with a non-asmyptotic convergence rate. It would have been interesting to see more specific characterization of classes of Stochastic Games that possibly can lead to a similar convergence guarantees. For instance, it might be useful to look at separable zero-sum polymatrix games [Cai and Daskalakis 2014], a subclass of multiplayer games that accommodate efficient computation of NE through linear programs. Even in normal form games if one applies no-regret online algorithms for two-player zero-sum games, the last-iterate behavior might be complicated [Bailey and Piliouras 2018, Mertikopoulos et al. 2018]. It is possible that some of these complications may carry over to the MARL settings.

Also, it would be interesting to understand possibly other notions such as Coarse Correlated Equilibrium for general settings of Stochastic Games, instead of relying purely on the Nash equilibrium.

Finally it would be useful if the authors could differentiate between the results of [Leonardos et al 2021] for Markov Potential Games as both algorithms achieve the same sample complexity and other results are mostly similar. Maybe it would be useful if they discuss algorithmic and computational differences. 

References:

Daskalakis, Constantinos, Dylan J. Foster, and Noah Golowich. "Independent policy gradient methods for competitive reinforcement learning." arXiv preprint arXiv:2101.04233 (2021).

Cai, Yang, et al. "Zero-sum polymatrix games: A generalization of minmax." Mathematics of Operations Research 41.2 (2016): 648-655.

Leonardos, Stefanos, et al. "Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games." arXiv preprint arXiv:2106.01969 (2021).

Mertikopoulos, Panayotis, Christos Papadimitriou, and Georgios Piliouras. "Cycles in adversarial regularized learning." Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.

Bailey, James P., and Georgios Piliouras. "Multiplicative weights update in zero-sum games." Proceedings of the 2018 ACM Conference on Economics and Computation. 2018.


summary_of_the_review: The paper has some interesting results for very generic Stochastic Game settings and Markov Potential Games (very similar to [Leonardos et al. 2021]). But I think these settings are too generic to study and extract meaningful results. Given the above comments on the strengths and weaknesses, it seems that there is more investigation and characterization that might be required. 

After the response:
The authors have clarified most of the concerns and the characterization seems adequate for this work to be published.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the optimization landscape of first-order methods in stochastic games. In particular, it studies the connections between first-order stationary points and Nash equilibrium and its convergent property and learning stability. For general-sum SGs, local convergence results is provided. For Markov potential games, global convergence results are provided. 
main_review: * I really like the content in Appendix A, which provided numerical evidence to justify the effectiveness of the proposed methods. This kind of analysis offers particular value to the MARL community, unlike many existing theoretical MARL papers.



* There are existing work that set up Markov Potential Game, can the author clarify the difference to 

    **Learning in Nonzero-Sum Stochastic Games with Potentials  David Mguni et al. ICML 21**

    **When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? Song et al**


* Since this paper deals with SGs, can the author comment on the relationship between the Nash equilibrium in Definition 1 and Markov  Perfect Equilibrium? 


* Through gradient dominance assumption, the author equates NE and first-order stationary point, can the author clarify if this result contradicts with the result in 

    **On gradient-based learning in continuous games. Mazumdar 2020**



* For the linear dependency result on Markov Potential Game, can the author clarify the significane of your result versus 

    **When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? Song et al**

summary_of_the_review:   This paper is a rather long paper and certainly over-exceeding the content that a conference paper can hold. Given the number of pages, it is challenging to evaluate for the correctness of proof for a 50-page paper within such a short time period. However, I believe the result is generally correct, for example, the sample complexity on Markov Potential Games has been discovered, probably in parallel, by many other papers. My major concern is how this paper poses itself among the peer work and if the result is still significant.
review_title: null

Meta-review: This paper looks at stochastic and Markov potential games. Its different results, including the sample complexity ones, are overall interesting and relevant for the community.

This said, we had an intense discussion as several of the aforementioned results -  actually, closely related results, not the exact same one - already appeared elsewhere (in a ArXiv preprint, that has been publicly submitted at a previous conference). We do believe that there is no ethical/plagiarism issue here, however, it remained the question of "paternity" of these results.

We have decided to give the paternity of the sample complexity to the first paper (the ArXiv preprint) that proved it. We can therefore only credit to this paper the improvements in the sample complexity results (as they are not exactly similar).

However, this had an impact on the reviewers (and also mine and the SAC one) evaluation of the paper, when some substantial parts of the paper are "discarded".

Nonetheless, we think that this paper has its merits, although it does not reach the ICLR bar in its current form. We strongly encourage the authors to work on a revised version - incorporating the different comments of the reviewers - and to resubmit it at a further venue.
Decision: Reject