Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games

Summary

This work proposes an analysis of the independent natural policy gradient algorithm for Markov Potential games. Under technical assumptions on a sub-optimality gap problem dependent quantity and supposing access to exact (averaged) advantage functions, this paper provides a novel $O(1/\epsilon)$ iteration complexity to guarantee that the average Nash gap along iterations is smaller than the accuracy \epsilon, improving over the previously known $O(1/\epsilon^2)$ iteration complexity in the same independent learning setting. After discussing the potential game setting as a warm-up and generalizing to the MPG setting, the paper provides simulations in a synthetic potential game and a congestion game.

Strengths

- The convergence analysis improves over the $O(1/\epsilon^2)$ iteration complexity in prior work under some technical assumptions. - To the best of my knowledge, the analysis provided in this paper is new and the proofs seem to be correct (I went through the appendix, please see some additional comments below). However, please see some comments below regarding related works and quantities/notations to be precised for clarifications. In my opinion, the main technical novelty is Lemma 3.2 (and Lemma B.3 relying on the technical lemma C.1) which is key to obtain the result in Theorem 3.3. This result is interesting and connects the sum of the ‘gaps’ (over agents) for a fixed temperature parameter $\eta$ and for $\eta$ going to infinity. - The paper is well-organized.

Weaknesses

**1. About the suboptimality gap \delta_K and the $O(1/K)$ convergence rate**: Theorem 3.3 provides an upper-bound on the average NE-gap which depends on the K-dependent quantity $\delta_K$ without further assumption, this provides a $O(1/K\delta_K)$ convergence rate as mentioned in the paper. I think it should be clearly stated that the $O(1/K)$ convergence rate which is claimed in the abstract and in the contributions under ‘mild assumptions’ (as it is stated) is actually “asymptotic”. Indeed, under assumption 3.2, the bound in Corollary 3.6.1 features an unknown constant (number of iterations) $K$’ that is not explicit in the problem parameters (such a constant is only guaranteed to exist under assumption 3.2). This is due to the fact that the NE gap is only controlled (independently of $\delta_k$) for a large enough number of iterations as it appears in l. 500 in the appendix (p. 17) under the chosen assumption. The results that the paper compares to in Table 1 have stronger guarantees in the sense that they are not asymptotic. This is not clear in the presentation and the comparison to prior work. **2. About Assumption 3.2**: this technical assumption guarantees that $\delta_K$ is uniformly lower bounded away from zero but it seems hard to interpret or give a meaning to this assumption although the ‘sub-optimality gap’ $\delta_k$ is a standard quantity in the bandit literature for instance. I am also not sure if this assumption is ‘mild’ as it is formulated. See the ‘Questions’ section for clarification questions regarding this assumption. **3. Discussion of related works**: Some relevant related works are missing in the discussion. **(a)** While Song et al. 2021 [27] is cited, it is not mentioned in the discussion that a $O(1/\epsilon)$ iteration complexity has been achieved in that work for MPGs with a Nash-coordinate ascent algorithm (see Section 5 Algorithm 7, note that sample complexity is given and the $O(1/\epsilon)$ iteration complexity appears in the proof when discarding the $O(1/\epsilon^2)$ sample complexity needed for policy evaluation). However, this algorithm is ‘turn-based’ and requires coordination and hence is not independent as the present work. **(b)** Fox et al. 2022 derived an asymptotic convergence result for the independent natural policy gradient algorithm considered in this work that seemed to be later used by Zhang et al. 2022 [33] but this reference does not appear in related works. This same result seems also to be used in Proposition 3.1 of the paper. **(c)** The results shown in this paper seem to have some similarities with the asymptotic convergence analysis provided by Khodadadian et al. 2022 in the single agent setting. For instance, the analysis in that paper introduces the optimal advantage function gap (see $\Delta$ as defined in Definition 2), a quantity similar to the sub-optimality gap $\delta_k$ in the present paper (up to the multi-agent setting). However, I would like to point out that this is just for the purpose of comparison and the present work has to overcome many difficulties related to the game theoretic setting and the multi-agent nature of the problem that make this work very different from Khodadadian et al. 2022. The abstract precises that the result improves over “ $O(1/\epsilon)$, that is achievable for the single-agent case”. Actually, Khodadadian et al. 2022 provide an asymptotic geometric convergence rate. Other recent related works even prove a global linear rate with increasing step sizes for the natural policy gradient algorithm (see for e.g. Xiao 2022, Section 4.2). Fox et al. Independent natural policy gradient always converges in Markov potential games, AISTATS 2022. Khodadadian et al. On linear and super-linear convergence of Natural Policy Gradient algorithm, Systems and Control letters 2022. Xiao. On the convergence rates of policy gradient methods. JMLR 2022 **(d)** minor remark: you might want to give reference to [Monderer and Shapley 1996, Potential Games, Games and Economic Behaviour 14, 124-143] which introduced this class of games in section 3.1 when you mention [12] (l. 128) which is much more recent. **4. Regarding the definition of Markov potential games** (Definition 2.1), for a fair comparison in Table 1, it might be worth mentioning that this definition differs from the one considered in [8,16] although it matches the definition used in [33, 34]. Indeed, the potential function in Definition 2.1 is supposed to have a discounted cumulative structure whereas such a structure is not available in the more general definition considered in [8,16]. As a matter of fact, the analysis becomes more challenging in [8] for instance since showing the potential function improvement is then more involved in that case, another decomposition different from the decomposition in Lemma B.2 l. 440 is then used to guarantee policy improvement (see Lemma in [8]). Also the dependence with respect to some parameters such as $(1-\gamma)$ and the state action space sizes are usually improved with this additional structure. **5. Originality of the analysis:** While Lemma 3.2 and its use is indeed new, the potential function improvement lemmas (Lemma 3.1, Lemma 3.5) and their proofs in appendix follow prior techniques used in [4, 33]. I suggest that authors mention this somewhere in the main part or in the appendix and emphasize the novelty of the analysis (Lemma 3.2). For instance Lemma A.1 was proved in [4], the proof of Lemma A.2 is almost identical to the proof in [4] while the proof of Lemma B.2 is very similar to the proofs in [33]. **6. Clarity**: Overall, writing can be substantially improved in my opinion. Few minor details below: — l. 108: what do you mean by ‘multiple stationary points for the problem’? Stationary points if the potential function? — l. 134-135: not very clear, see the ‘Questions’ section below. — l. 136-137: ‘for any two sets of policies’. I guess you mean any two joint policies (in the product of the individual simplices) when you say sets. — l. 158: ‘They are related by the following lemma’, the constants you just defined in l. 157 or the quantities defined few lines above in l. 153? — notation $f(\infty)$ is used in Lemma 3.2 and does not seem to be defined before although it is quite obvious this corresponds to $\lim_{\alpha \to \infty} f(\alpha)$ as used in l. 153. — Lemma A.4 in the appendix: the statement and the proof are not very precise. What is $\mathcal{R}_i$ (it seems only defined in the end of the proof of this lemma, or we can guess it from the title of the lemma)? I guess this is the set of reward functions which is known to have a particular structure for MPGs as you write it. $\mathcal{R}_i$ is a linear space in which ambient space? Please precise the proof even if we can guess the idea. Also, where is this result used? — Lemma C.1: if rewards are vectors, please precise somewhere in notations that inequalities hold for all the entries of the vectors. **Typos (main part and Appendix)**: 
l. 91: $V_i(s)$; do you mean $V_i^{\pi}(s)$? l. 476-477 (proof of Lemma B.2 in appendix): $\bar{A}_{f_i}^{\pi^k}$, what is $f_i$? I guess you mean $h_i$. l. 479 to l. 480: $\pi_i^{k+1}(\cdot|s)$, $s$ is missing in the first term of the last equation and in the KL divergences. l. 503 (proof of corollary 3.6.1): is there a missing $\phi_{\max}$ in front of $K’$ in the first inequality of the page (given l. 501)?

Questions

1. The assumption of ‘isolated stationary policies’ seems to be needed to guarantee that $c>0$ as stated in Theorem 3.6 (as it is also stated and used in [33]). However this assumption is not stated in the theorem. How does the theorem guarantee that $c> 0$? 2. Please clarify the definition of ‘isolated stationary policies’. What do we mean by ‘stationary’ policies in this context? Although such a terminology is used in [33], it is not clear to the reader what this means, especially that ‘stationary’ has also another meaning for policies (time-independent). The reference Fox et al. 2022 above may help with this. 3. About assumption 3.2, isn’t it possible to use the assumption that the ‘stationary policies are isolated’ instead to obtain corollary 3.6.1? According to the comments l 248-250 in the paper (a short proof in the appendix may be useful then to state this implication properly), this assumption would guarantee that Assumption 3.2 hold. Moreover, the assumption that the ‘stationary policies are isolated’ seems to be already needed in Theorem 3.6 to guarantee that $c >0$. Would this mean that only the assumption that ‘stationary policies are isolated’ would be then sufficient for Theorem 3.6 to hold without needing Assumption 3.2? 4. Could you please precise the mathematical definition of $\pi_i^{*k}$? It seems to be only defined once with words in l. 134-135. Why should it be unique (‘the optimal solution …’)? Do you mean it is an optimal policy in the sense that it maximizes the averaged advantage function w.r.t. the policy of other agents but i being fixed to $\pi_{-i}^k$ (or the averaged reward function in the potential games setting)? This is also important to clarify the limit statement in l. 153. 5. l. 153: why do we have that $f(\eta) \geq 0$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The paper mentions the MPG setting as a limitation in the conclusion. **Extension to the stochastic setting:** While the analysis in the deterministic setting is an important step towards understanding the more practical stochastic setting where exact advantage functions are not available and can only be estimated via sampled trajectories, this analysis does not seem to be easily extendable to the aforementioned stochastic setting. This seems to be related to the fact that showing that the constant c is positive in the stochastic setting seems to be much harder if not hopeless even in a single agent setting (see for e.g. Mei et al. 2021). However, this is a limitation that also applies to prior work in MPGs analyzing independent natural policy gradient such as Zhang et al. 2022 [33]. A comment on this or an additional remark in the paper would be welcome. For instance, [8] analyzes the sample complexity in the stochastic setting but their algorithm does not cover the case where the regularization in the policy mirror descent-like update rule is not euclidean, KL regularization (which leads to natural policy gradient) is not covered. 


Mei et al. ‘Understanding the effect of stochasticity in policy optimization’ (Neurips 2021)

Summary

The paper provides a new analysis for the (Markov) potential games with a $O(1/\epsilon)$ convergence rate. The new results are problem-dependent and may be a tighter guarantee for certain classes of potential games. Asymptotic guarantees are also provided to elaborate on the problem-dependent nature of the results.

Strengths

The results it presents showcase an improvement over previous results on (markov) potential games. The new rates are now unaffected by the number of actions and are at the order of $O(1/\epsilon)$. The problem-dependent nature of the results may provide a tighter guarantee on a certain class of potential games and the new analysis methods may lead to future works. The results are extensively discussed and empirical results are provided to corroborates the theoretical results.

Weaknesses

The new results do not seem to be directly comparable to the previous ones due to the use of a suboptimality gap. I encourage the authors to explicitly state this early in the paper to avoid confusion (e.g. in Table 1). I also encourage the authors to complement the work with more empirical results. For example, it would be interesting to see how the algorithm performs against previous ones when the suboptimal gap is very small. It may also be helpful to state when the suboptimality gap is very small, the results can degenerate into previous results.

Questions

1. In Table 1, the results for PG + softmax [33] also include a c in the denominator. Is the c defined as the same as this paper? 2. It seems that in [33], the c in the denominator can be alleviated by using log barrier regularization. Will log barrier regularization have the same effect on the results presented in this paper? 3. In Definition 2.1, the potential function is assumed to take a specific form with $\phi$. However, this form does not seem to be needed in previous analyses. How important is this specific form to the analysis and can it be lifted?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes, it is discussed in the conclusion part.

Summary

The article considers what the authors describe to be “natural policy gradient” learning in normal form and Markov potential games. This is the discrete time algorithm in which individual players' mixed strategies are multiplied by a softmax response to the opponent mixed strategies then normalised. Convergence rates are derived in both normal form and the Markovian potential games.

Strengths

The article is nicely written, and the claimed results are supported by the theory. The convergence rate results are nice, given the general difficulty to provide convergence rates in anything multiagent, and especially in Markovian games - of course restricting to situations in which there is a potential function for the full Markovian game makes things much less impossible, but it is still a hard problem. The paper is nicely self-contained, and a real pleasure to read.

Weaknesses

I have some doubts over the claimed results which I would like to see clarified. The authors claim that Thm3. Implies a 1/eps convergence rate. I don’t buy it I’m afraid. c and delta_K are not controlled. They could be arbitrarily small, at least without further work. I suspect c is okay, although a sudden switch in best response could easily result in a very small pi_i^k(br_i(pi_{-i}^k)) coming into c late in the process. And since delta is the optimality gap when playing a mixed strategy, I find it very difficult to see how to constrain it effectively. (I think line 158 tells us that c is the smallest ever pi_i^k(br(pi_{-i}^k)), and delta_K is the smallest optimality gap that occurs up to time K – if I have misinterpreted this then my objections may dissipate!) The synchronous form of "learning", and the tight construction of Markovian potential games with average reward, means the step up to Markovian settings is much less then in a less restrictive setting. A more philosophical point is that the article assumes players can receive oracle information about the long term payoff of any action. While it makes for a nice compact paper, I think for NeurIPS the authors need to at least posit some suggestions for where learners might be able to access the advantage functions that are required to implement the method. Furthermore, the dynamic is well known as the multiplicative weights algorithm, and I would expect the authors to compare their results with those presented under the multiplicative weights description.

Questions

1. In (5), the function f has dependence only on alpha. However there is also important dependence on k, and on pi_{-i}^k. This may seem like pedantry, but I think it’s important (see below). 2. In lines 154/155 the definition of a^k_{i_q} is clumsy, due to possible multiplicities in the argmax for a^k_{i_p}. I think that a^i_q is only needed to define the optimality gap? If this is the case, why not just define delta^k directly max_a r^i(a) – max_{a\notin \argmax} r(a), or something like that? The current formulation taking a_i_q to be the max that is not a_i_p is incorrect, is noted to be incorrect in the text, but is used anyway. 3. In (6) we begin to get bitten by the lack of care in defining what the functions depend on. In particular, since the r_I^k functions depend on mixed strategies pi_{-i}^k, so does the delta term. And so delta_k may well be extremely small. Have I missed something here? 4. On line 159, we see that c_K and delta_K are the smallest such quantities that are observed in the first K iterations of the algorithm, and indeed that c is minimum c observed in the limit. The notation means that this path-dependency is somewhat obscured. The authors try to argue, later, that these quantities are not small. But I do not think the argument has been made strongly enough. Furthermore, it seems strange to take a limit of c_K values, but not take a limit of delta_K values in the theory that follows? This is clearly very relevant to my point made in "weaknesses". 5. First inequality in the proof of Theorem 3.3, I think should be an equality? 6. Line 259, I think we cannot claim that |delta^k-delta*| is small, since we are only assuming a lim inf?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

No discussion of limitations is presented. I don't feel such a discussion would add much to the paper, but the review form asks the question!

Summary

This paper studies the convergence of Natural Policy Gradient method (NPG) in Markov Potential Game. Under stronger assumptions, the convergence result improves upon previous ones.

Strengths

Under the considered setting, NPG is shown to achieve a $1/K$ convergence rate for multi-agent Markov Potential Game, matching the convergence rate in single-agent setting. Discussion on the parameters that appear in the convergence rate is presented in detail.

Weaknesses

The convergence result only makes sense under the assumption that $c>0, \delta>0$. However, such assumption could be too strong and unnecessary (as the table 1 indicates).

Questions

Line 177: "A small value for c generally describes a policy that is stuck at some regions far from an NE, yet the policy gradient is small. It has been shown in [17] that these ill-conditioned problems could take exponential time to solve even in single-agent settings." In my opinion, this justification is not suitable. In single-agent settings, NPG has a nice convergence that does not depend on $1/c$, while [17] shows that PG can take exponential many iterations to converge. Thus, taking [17] as an excuse, it is okay to introduce certain assumptions (e.g. concentrability) to ensure better convergence, but directly assuming $c>0$ is still too strong (and possibly unnecessary).

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

post rebuttal

I confirm that I have read the authors’ rebuttal and I thank them for their response. I still think that assumption 3.2 is not a verifiable assumption under its current form. While the dependence on the suboptimality gap is natural as it appears in prior work (as I also mentioned in my original review and the authors further reconfirmed it), the suboptimality gap is usually **proved** to be a positive quantity (see for e.g. Lemma 3 in Khodadadian et al. 2022). Nevertheless, I acknowledge that this paper addresses a more challenging multi-agent setting. I raise my score to 6 following the authors’ rebuttal. Remaining limitations I see include Assumption 3.2, the asymptotic nature of the rate and the difficulty to extend the results to the stochastic setting given the dependence on the constant $c$ which positivity is difficult to guarantee in this setting (beyond assuming oracle access). I also encourage the authors to improve the writing, presentation and discussion of related works along the lines of the rebuttal. Khodadadian et al. 2022, On linear and super-linear convergence of natural policy gradient algorithm, Systems and Control Letters.