Venue: NeurIPS 2022 Conference

Reviews:

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 studied the convergence of policy gradient (PG) methods with direct parameterization (Algorithm 2) to Nash equilibria in general stochastic games. The PG methods considered here apply to full gradient information, unbiased stochastic gradients with bounded variance, and REINFORCE estimator (Models 1-3). Explicit exploration ("epsilon greedy") is also used to bound the variance of PG estimators.

Theorem 1 showed that a stable Nash policy is locally attractive to PG with high probability.

Theorem 2 then showed that a second order stationary (SOS) Nash policy enjoys stronger results of last iterate convergence rates.

Theorem 3 showed that if a Nash policy is deterministic, then a lazy policy gradient (LPG) enjoys a finite convergence to exact Nash policies.
strengths_and_weaknesses: Strengths:

1. The setting of general stochastic games is general and representative for multiagent learning.

2. The PG methods studied here apply to multiple settings (full gradient, stochastic).

3. The results and techniques look novel and interesting to me. I like the idea of discussing different results conditioning on whether a Nash policy is stable, SOS, and deterministic. 

4. The presentation is organized and clear.

Weaknesses:

1. It would be better if some simulation results can be provided to verify some of the results (high probability convergence and rate of convergence).
questions: 1. Below Theorem 1 it was stated that the high probability convergence results cannot be improved further. Could you comment on what could be the possible failure cases (e.g., limiting cycles or chaotic behaviours)?

2. It seems to me SOS Nash policies enjoy convergence rates because of Eq. (C.9) has larger progress than Eq. (B.35). I am wondering for stable Nash policies, is it possible to establish a rate of convergence? If not what would be the difficulty, or any counterexample could be constructed to show the rate can be arbitrarily slow?

3. The finite convergence results in Theorem 3 is interesting. I am wondering if there is a parameterization to maintain the policy as valid probability distributions (e.g., standard softmax policies), then what is the implication of this lazy projection in that scenario and can it still provide useful insights?
limitations: This work is purely theoretical, and it has no potential negative societal impact as far as I can see.
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 consider multi-player stochastic games. They study the convergence property of policy gradient type algorithms toward Nash equilibrium policies that are second-order stationary, similar to the type of KKT sufficiency conditions. They prove that policy gradient algorithms where the gradient is estimated with the reinforce algorithm, if started close to a second-order stationary equilibrium converge to this equilibrium, in terms of squared distance, with high probability at the rate O(1/\sqrt(n)) where n is the number of steps. If the Nash equilibrium is deterministic, for a lazy version of the policy gradient algorithm, the rate of convergence improves to a constant number of steps.
strengths_and_weaknesses: Contributions:
-flexible algorithmic template for the analysis of policy gradient methods,  novelty: low, relevance: low.
-O(1/\sqrt(n)) rate of convergence of policy gradients method with reinforce gradient estimate towards second-order stationary equilibrium Nash equilibrium,  novelty: medium, relevance: medium.
-Finite-time convergence for a lazy version of the policy gradient methods toward a deterministic Nash equilibrium, novelty: medium, relevance: medium.


The paper is well-written even if some notations could be clarified, see specific comments. It could be interesting to ground the considered setting with a concrete example, see specific comments. Similarly, the claims are obtained through a cascade of hypotheses that are not exhaustively discussed and justify. The proofs seem correct at least in the part I read. The related work could be improved. For example, the author may also want to compare the obtained rate with the rate obtained by Jin et al. (V-Learning—A Simple, Efficient, Decentralized Algorithm for Multiagent RL , 2021) and reference therein since they seem to consider the same setting. It would also be interesting to discuss the results to provide lower bounds on the rate of convergence toward a Nash equilibrium. 
questions: Specific comments/questions:

-L30: By "game itself evolves" you mean the strategy of the other player or the rules of the game?

-L80: The notation $a_i$ for the action seems more natural than $\alpha_i$.

-L92: Do you have a concrete example of game that you can model with this framework? In particular, a game where after each step all players fully observe the state of the game.

 -L127: Can you elaborate on this assumption, which at first sight seems very strong in particular for deterministic policy. And do you have a non-trivial example where this assumption is true?

-L138: Can you precise what is the scalar product you consider and I assume that you see \pi as a vector of size S\times A right? 

-L153: What do you mean by close?

-L163: Can you detail this point?

-L167: Can you clarify "sufficiently close" and what norm do you consider?

-L198: constructed

-L210-215: 'reverse P'

-L212: Can you precise what you mean by 'game involves training over datasets' and how you estimate the gradient.

-L230, (14): for all s?

-L235: Can you provide for G the dependence in A and S?

-L244: Do all stochastic games admit a stable Nash policy?

-L250: r is already used for the rewards.

-L278: Can you provide any intuition on what is the typical size of \mathcal{U}? Indeed if this set is too small there is no hope to be able to start in it.


-L285: Can you provide an order for the constant hidden by the O in terms of the parameters of the problem? 
-L286: This part is not very clear if p=1 how do we know that q = 1/2 since 2p = q ?

-L289: Can you provide lower bounds in order to state that it is effectively the rate of convergence of PG ?

-L292: Can you explain how to 'to adapt the parameters of the learning process according to the complexity and limitations of the environment' in the light of Theorem 2?

-L332: Can you precise how n_0 depends in the parameters of the problem? Because if this constant  n_0 is very large in comparison to the one hidden in O(1/n) the relevant regime will still be the one of Corollary 2.

-L630: R is already used for the cumulative rewards.

-L634: a is not defined, is it any such that a+\sqrt{a} < r, r is the rate of \epsilon-greedy? If so not that it is only defined in Corollary 1 stated after Theorem 1.

-L656: Can you detail why the two limits are zero.

-L667: For (B16) you do not telescope the bound (B2) but just use that \pi_k is in \cB?

-L678: Can you explain why you need the indicator 1_{\cE_n} to get (B.24)?

-L700: + is missing in (B.32). And you should also detail quickly why the different sums are bounded for the choice of the parameters.
limitations: see Strengths And Weaknesses.
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 studies the convergence of the policy gradient method for a class of MDP problems. The equilibrium point investigated is the second-order stationary point, which is a popular notion in the optimization literature.

strengths_and_weaknesses: Pros: The topic studied in this paper is no doubt interesting and meanwhile challenging. Instead of adopting the first-order condition (KKT) used in most of the game papers in literature, this paper borrows the idea of a second-order stationary point from the optimization community and established the corresponding framework to understand the well-definedness and learning behavior in the stochastic game regime. The authors establish asymptotic convergence (in high probability) for a class of MDP games.

Cons:  However, I have some concerns regarding (1) the generality of the set-up (especially on the stopping time), (2) verifiability of the assumptions, and (3) key steps with missing proofs.

Detailed questions that require clarifications are listed below.
questions: (1) Most real-world applications do not have a random stopping time $T$. The authors should better motivate and justify this setting. In addition, it is well known in the stochastic control literature that a control problem with a random stopping time sampled from an exponential distribution with rate lambda corresponds to an infinite-time horizon problem with discount factor lambda. The authors should make the linkage between these two classes of problems if there are any.

(2) Lemma 2 is listed without proof. This is an important building block that later results rely on. I doubt whether the PL condition could hold (as stated in Lemma 2) without additional assumptions. It is well-known that the PL condition does not hold for the general two-player linear-quadratic zero-sum game case and some carefully constructed conditions are required [1]. General-sum game [2] and MDP games [3] are much harder problems and I am surprised to see that PL condition holds almost for free in Lemma 2.

(3) The convexity of the projection set is never discussed. When $\Pi$ does not enjoy good properties, finding the projected point can be NP-hard.

(4) In Theorem 1, the authors assume that $\pi^*$ is a stable Nash policy. However, the authors never verified under what verifiable conditions the original problem has a Nash equilibrium policy and under what conditions it is unique. Similar issue also appears in Theorem 2. The authors never discussed the sufficient conditions for $\pi^*$ to be SOS. This leads to the danger that the main results (Theorems 1 and 2) may never be applicable.

Minor comments:

(a) The $a_t$ in Eqn (1) should be replaced by $\alpha_t$ based on the definition. 

(b) Stopping time $T$ is not mathematically rigorously defined (i.e., the adaptiveness).

(c) Please be precise with what you mean by ``realized values’’ in line 217. I understand you refer to the instantaneous rewards but it is a bit vague in the statement.

[1] Zhang, Kaiqing, Zhuoran Yang, and Tamer Basar. "Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games." Advances in Neural Information Processing Systems 32 (2019)

[2] Mazumdar, Eric, et al. "Policy-gradient algorithms have no guarantees of convergence in linear-quadratic games." arXiv preprint arXiv:1907.03712 (2019)

[3] Xie, Qiaomin, et al. "Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium." Conference on learning theory. PMLR, 2020
=========
==========
I have read the reviews from other reviewers and the responses from the authors. The authors have addressed my concerns and I raised my rating to 6.
limitations: Yes.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the local stability of stationary Nash equilibria under the projected gradient (PG) algorithm in episodic finite (states and actions) stochastic games under various assumptions on the players observations --full, intermediate (stochastic gradient) or low (value based)-- Form the fact that stationary equilibria of finite stochastic games satisfies a version of Polyak-Łojasiewicz condition (a consequence of the semi-algebraicity), stationary Nash equilibria satisfy a gradient dominance property which easily implies that equilibria can be expressed as solutions of a variational inequality (VI). The rewriting of the equilibrium condition as a VI allows to classify the stability of Nash equilibria from stable, to second-order stationary (as in Mertikopoulos, Zhou Math Prog 2019). They then use the variational inequality conditions to establish their main results, namely 1) if an equilibrium is Nash stable, then if one starts closely to it, PG converges to it with high probability 2) when the equilibrium is second-order stable then the convergence time can be estimated (roughly 1/n or 1/n^1/2)...This rate can be improved to finite time convergence for pure stationary equilibria.
strengths_and_weaknesses: Strengths: this is an excellent paper. It shows the local stability of stationary Nash equilibria under the projected gradient under several observational assumptions whenever that Nash equilibrium has some additional stability properties. The fact that it uses only the variational inequality property of the Nash equilibrium implies that the result extend to a wider class of game, beyond the one studied in the paper (for example concave continuous games as studied in Mertikopoulos, Zhou 2019). The main difference with the MZ paper is that MZ studies Online Mirror Descent while this paper studies projected gradient descent. 


Some weaknesses: only local convergence results, only on a subclass of stochastic games (episodic stochastic games). Also, It seems to me that the existence of stable and second order stationary equilibria in finite stochastic games is rather hard to obtain (outside strict pure equilibria or zero sum games).
questions: - Can this result be coupled with the one (in zero-sum and potential stochastic games) where best iterate convergence results have been proved? namely, can we deduce from your analysis a convergence a global convergence is some zero-sum and potential SGs --

- Can you give some non trivial examples of finite stochastic games with a stationary equilibrium which is second order stable (or stable) without being strict or the game zero-sum?

limitations:  - Can you please discuss the classes of games, beyond the class of stochastic games, where your results apply?

- Can your results extend to ergodic stochastic games -where there is no ending, and the learning is obtained during the play-?
review_title: null

Meta-review: metareview: This paper analyzes the convergence of policy gradient algorithms in "generic" stochastic games. The authors provide local convergence guarantees for projected gradient descent with the REINFORCE gradient estimator. Reviewers were generally positive on this paper--- though I think it needs to be much better contextualized in the literature on gradient-based learning in games (of which this is a special case). 

Indeed--- while interesting in the context of MARL --- the results are not very surprising given that they seem very similar with other local analyses of (stochastic) gradient-play in games (see e.g., [1]). Furthermore the equivalence of equilibria follows from well known manipulations of the single-agent RL loss function like those performed in [2], genericity arguments for Nash equilibria [3], as well as work on variational inequality approaches to learning in games [4]. The final version of the paper should really comment on these previous results. Nevertheless, due to the positive reviews and the relevance to MARL, I recommend this paper for acceptance.

[1] Chasnov, Ratliff, Mazumdar, Burden; Convergence Analysis of Gradient-Based Learning in Continuous Games

[2] Zhang, Ren,  Li; Gradient play in stochastic games: stationary points, convergence, and sample complexity

[3] Ratliff, Burden, Sastry; Characterization and computation of local Nash equilibria in continuous games

[4] Mertikopolous and Zhou; Learning in games with continuous action sets and unknown payoff functions
confidence: Less certain
Decision: Accept