Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the behavior of the gradient play when the policies are modeled via softmax surrogate.
Gradient play can be either first-order (policy gradient) or second-order (natural policy-gradient) method. 
In contrast to the previous results that aim to establish results for the direct parametrization $p(a|s)=\theta_{s,a}$, this work builds upon a series of results for Markov Potential Games and tries to establish rates of convergence to the corresponding Markov Nash equilibria.

For this setting, the authors provide three kind of results for the solution concept of Markov Nash equilibria in the generalization of identical interest RL game, known as Markov Potential Games.

1) The asymptotic convergence of gradient play with softmax regularization
2) Convergence rates which include some ``trajectory''-dependent constants
3) The impact of log-barrier regularization in gradient play in the rates
strengths_and_weaknesses: Summary of contributions. 
In this general context, the main contributions of the manuscript under review can be stated as follows:
(1a) In principle this is the first work that offers convergence rates for softmax policy gradient method.
(1b) It should be mentioned that as far as the asymptotic convergence results have been already established last two years. Therefore, for the standard gradient play via softmax, I will encounter as novelty the convergence rate part

(2a) The authors, via a manipulation of gradient dominance/ Polyak-Ljovasiewitz armamentum, guarantee fast convergence rates for the case of MPGs with Isolated equilibria. 
(2b) However, their convergence rate include a trajectory dependent constant which can be exponential worse.  It would be much more interesting if authors gives us examples where the worst case is achieved and how in practice this constants fluctuate. 

(3a) Finally, log-barrier is used for softmax regularization to get independent constant-style results.
(3b) From applicability perspective, it is unclear how much harder is the inclusion of log-barrier to achieve the necessary result.
(3c) Again I would like to notice that it is not the first work that applies log-barrier regularization in RL problems.







Evaluation and recommendation. 

I believe that the core of the authors’ results is interesting: in particular, the derivation of convergence rates for softmax has been an interesting question recent years. However the positioning of the main draft, does not explain at all which are the important non-trivial observations which meshes well with existing results in the field, and which can provide further insights in the behavior of policy gradient methods to extract the promised results. 

I would expect from the authors a much more extensive analysis of the challenges & the burdens that the current submission tackles and what was the main intuition that leads authors to the usage of log-barrier regularization. At the end of the day, the usage of such strong regularization was a natural solution due to some collection of issues or just a matter of lack?

At the same time, the paper’s writing, presentation and positioning leaves a lot to be desired: 
a fair number of results are presented in a confusing or misleading way (especially in
regard to the state of the art), the writing style obfuscates the analysis and statements, and
the authors’ prose is often inconsistent with the results actually being proven.

Ultimately, I believe that a thoroughly rewritten version of this paper could be ultimately publishable
in NeurIPS proceedings, but the submitted manuscript is not yet there. For this reason, I recommend a
majorly enlightening revision with the understanding that the paper should be rewritten from the ground
up with emphasis on clarity, readability and ease of comparison to the existing literature on
the topic.

Indeed, the line between asking for a border line acceptance and borderline rejecting the paper outright while encouraging resubmission at a later point is a blurry one. 
I am recommending a Border-Acceptance  because I find sufficient merit in the paper’s contributions; however, these should be stated in a way that is consistent with the Conference standards, an endeavor which will require a careful rewriting

questions: See the weakness section.

Additionally, I would like a clarification: Why in the single agent MDP the last row/first column does not copy automatically the result of the multi-agent case?




limitations: Non-applicable
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 focus on the analysis of various algorithms/dynamics for Markov Potential Games, using softmax parametrization. Softmax parametrization is challenging as it creates more fixed points than Nash equilibria. Also Markov Potential Games include multiple Nash equilibria as well so this adds an extra challenge. The authors provide rates for policy gradient with softmax parametrization (note that only asymptotical was known prior to this work from Agarwal et al), natural policy gradient with softmax parametrization (here only results for single agent were known and the authors use a nice trick from Mei et al) and finally policy and natural policy gradient with log-barrier functions. The log-barrier function allows the authors to get rid of some parameter $c$ that can be arbitrarily large and typically slows down policy gradient. Mathematically speaking, this constant $c$ is because of the new fixed points that are created in the boundary due to softmax. 
strengths_and_weaknesses: Pros
The results are important, the authors add an important contribution related to softmax parametrization. Note that softmax parametrization is important for function approximation.

Cons
The techniques were more or less established before this work, the authors had to do a careful merge of the existing techniques and generalize the results to Markov Potential Games.  

Typos: Section 3.2 title: Convergence rate, not fate. 
questions: It feels that you cannot get rid of the mismatch coefficient in your rates. There are some other works though that use quantal response Nash idea and get rid of the mismatch coefficient. Is the existence of mismatch coefficient in your rates necessary even when you use log-barrier functions or you believe your analysis can be improved?  
limitations: This is theoretical work
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper analyzes the convergence of gradient play in Markov potential games where the players have softmax policies. Relying on recent advances in the analysis of policy gradients for softmax policies in single-agent RL, the authors first give asymptotic guarantees of convergence for both gradient play and natural gradient play and then subsequently provide finite-time convergence rates for both algorithms. These rates suffer due to a dependence on a non-uniform gradient-domination constant which may get arbitrarily large (as in the single agent case). To address this, the authors again continue as in the single-agent case and suggest doing gradient-play on a regularized version of the problem. When the amount of regularization is well chosen, the authors show that gradient-play from a fully random policy achieves fast convergence that is independent on the curvature constant 1/c but albeit with a worse dependence on the number of actions. They conclude with numerical experiments. 

strengths_and_weaknesses: This paper is very well written and easy to follow, though the results are not very surprising and the proof techniques and paper overall seem to follow from [1] in a very straightforward way. While results do not in general need to be surprising to be interesting, it is unclear what the contributions of this paper are beyond the explicit rates which follow from simple non-convex optimization arguments combined with the main property of the problem: namely the Łojasiewicz Inequality. Such analyses have been done before in [2],[3] albeit without the softmax structure, and the softmax structure is handled in exactly the same way as in [1]. 

Furthermore, the problem setting of Markov potential games is not very well motivated. Indeed, practical examples of when these games arise and why one might formulate the problem as a MPG as opposed to a single agent problem would greatly help. 

[1] Agarwal et al. On the theory of policy gradient methods: Optimality, approximation, and distribution shift

[2] Leonardo et al. Global convergence of multi-agent policy gradient in markov potential games

[3] Zhang et al. Gradient play in multi-agent markov stochastic games: stationary points, convergence, and sample complexity
questions: 1. Because of the Łojasiewicz Inequality it seems that all critical points of gradient-play are Nash equilibria of the game, but can there be saddle points in the potential function like those pointed out in [3] above?




limitations: Overall the paper is almost too straightforward an extension of prior works [1] and [3], and there does not seem to be anything particularly interesting about the combination. Making the exact contributions of this work clear would be helpful. Indeed the asymptotic global convergence guarantees and finite time rates are immediate from the potential structure and the Non-uniform Łojasiewicz Inequality. The idea of regularizing the problem seems to be a simple generalization of the idea in [1] to deal with the issue that 1/c might be arbitrarily large, but it is unclear if the multi-agent structure makes the derivation of the 1/c-less rate any more complex than in [1].
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper mainly analyzes the global convergence rates of decentralized Softmax policy play in MPG in detail, including both policy gradient and natural policy gradient, with and without log-barrier regularization, which numerically validates that the log-barrier regularized algorithms are indeed more robust against becoming trapped near undesirable non-NE stationary points. The theoretical results illustrates the complexity bounds of MPG, and the natural gradient play outperforms gradient play counterparts.
strengths_and_weaknesses: Strengths:
1) One major concern for this work is the innovation of the proof sketch, which is mainly based on the properties of smooth functions and inequality transformations. 
The authors should highlight the difficulties and solutions in the proof process.
2) The authors give a comprehensive analysis of the convergence rate of the policy gradient methods in MPG. The theoretical results seems correct and fills the gap of Softmax policy play in MPG.
3) The authors provide detailed descriptions of each term in the theoretical result, which are helpful for understanding.

Weaknesses:
1) Compared to entropy regularization methods, and even some trust region based methods, the authors should emphasize the necessity for log-barrier regularization. 
2) The authors should add some citations to illustrate the impact of Fisher information in line 57.
3) The theoretical analysis contains a large number of inequality derivations, but the author omits some sources of inequality derivation, such as Lemma 29, Lemma 31, etc., which are difficult to understand.
4) This article contains some notation errors and typos, such as the table in Introduction, the title of 3.2, etc.
questions: 1) What is the connection between Softmax policy and Boltzmann policy, log-barrier and entropy regularization, and how are they related to some exploration methods?
2) The log-barrier method is introduced to avoid undesirable regions of policy space. What is the difference between this and the Trust region policy optimization based methods, e.g., MATRPO, HATRPO? How to illustrate the advantages of this regularization method?
limitations: Yes, the authors detail the limitations of this work and possible future research works. It could be better if the fundamental reasons of these limitations can be explained.
review_title: null

Meta-review: metareview: The reviewers appreciate the contribution of this paper to the theory of tabular MARL in MPGs, namely convergence rates of PG and NPG with and without a log-barrier regularizer. There were some concerns regarding clarity of the writing (in particular the textual descriptions of the theory and its implications) and of the contributions (and their distinction from existing results). There were also some concerns regarding the novelty of the proof techniques. Nevertheless, there's consensus that the paper makes important contributions.

The authors have started to address some of the reviewer feedback in their revision, and are encouraged to continue to do so.
confidence: Certain
Decision: Accept