Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games
Authors: Youbang Sun
Tao Liu
Ruida Zhou
Panganamala Kumar
Shahin Shahrampour
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi Agent Reinforcement Learning
Markov Potential Games
Natural Policy Gradient
Nash Equilibrium
TL;DR: This paper proves fast convergence of independent natural policy gradient algorithm for multi-agent reinforcement learning in Markov potential games.

Abstract: This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild technical assumptions and the introduction of the \textit{suboptimality gap}, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an $\epsilon$-Nash Equilibrium (NE) within $\mathcal{O}(1/\epsilon)$ iterations. This improves upon the previous best result of $\mathcal{O}(1/\epsilon^2)$ iterations and is of the same order, $\mathcal{O}(1/\epsilon)$, that is achievable for the single-agent case. Empirical results for a synthetic potential game and a congestion game are presented to verify the theoretical bounds.

Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games
Youbang Sun Northeastern University sun. hun.yyobbnnorthesterr. edu
Tao Liu" Texas A&M University tliu0tamu. edu
Ruida Zhou Texas A&M University ruida@tamu. edu
P. R. Kumar Texas A&M University
Shahin Shahrampour Northeastern University s shahr s ampourrnorttteestteeeee edu
prkStamu. edu
Abstract
This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. is shown that, under mild technical assumptions and the introduction of the suboptimality gap, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an e-Nash Equilibrium (NE) within O(1/e) iterations. This improves upon the previous best result of (1/e²) iterations and of the same order, (1//c), that is achievable for the single-agent case. Empirical results for synthetic potential game and congestion game are presented verify the theoretical bounds.
1 Introduction
Reinforcement learning (RL) is often impacted by the presence and interactions of several agents in multi-agent system. This challenge has motivated recent studies of multi-agent reinforcement learning (MARL) in stochastic games [37 3 Applications of MARL include robotics (30], modern production systems (2), economic decision making [33, and autonomous driving [31. Among the various types of stochastic games, we focus
commonly studied model for MARL, known as Markov Potential Games (MPGs). MPGs are seen as a generalization of canonical Markov Decision Processes (MDPs) in the multi-agent setting. In MPGs, there exists potential function that can track the value changes of all agents. Unlike single-agent systems, where the goal is to find the optimal policy, the objective in this paper is to find a global policy, formed by the joint product of set of local policies, that leads the system to reach a Nash equilibrium (NE) 29 which is precisely defined in Section
major challenge in the analysis of multi-agent systems is the restriction on joint policies of agents. For single-agent RL, policy updates are designed to increase the probability of selecting the action with the highest reward. However, in multi-agent systems, the global policy is constructed by taking the product of local agents' policies, which makes MARL algorithms suffer greater risk of being trapped near undesirable stationary points. Consequently. finding a NE in MARL is more challenging than finding the global optimum in the single-agent case, and it is therefore difficult for MPGs to recover the convergence rates of single-agent Markov decision processes (MDPs).
Additionally, the global action space in MPGs scales exponentially with the number of agents within the system, making crucial find algorithm that scales well for large number of agents. Recent
'The first two authors contributed equally.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Convergence rate results for policy gradient- based methods in Markov potential games. Some results have been modified to ensure better comparison.
ALGORITHM
ITERATION COMPLEXITY
LA M (1-3)
PG DIRECT
B9
amax; IA, Jad (1-9)4-222
PG + SOFTMAX 38
NPG + SOFTMAX 38
ndd (1-7)9
PG + SOFTMAX + LOG-BARRIER REG.
38
O
1 maxx; LA, PA
(1-7)²
NPG SOFTMAX LOG-BARRIER REG.
38
|A.]
(1 [--)""
PROJECTED Q ASCENT
g
n max, IA, |A.
(1 ")
OR
max, |A. (1-1) ")"
PROJECTED Q ASCENT (FULLY COOP)
g
max, IA
(1-7)0e²
(Ours) NPG + SOFTMAX
VTM [1 (1-7)"065c
studies [8 [4] addressed the issue by an approach called independent learning, where each agent performs policy update based on local information without regard to policies of the other agents. Independent learning algorithms scale only linearly with respect to the number of agents and are therefore preferred for large-scale multi-agent problems.
Using algorithms such as policy gradient (PG) and natural policy gradient (NPG), single-agent RL can provably converge to the global optimal policy [. However, extending these algorithms from single-agent to multi-agent settings presents natural challenges as discussed above. Multiple recent works have analyzed PG and NPG in multi-agent systems. However, due the unique geometry of the problem and complex relationships among the agents, the theoretical understanding of MARL is still limited, with most works showing slower convergence rates when compared to their single-agent counterparts (see Table TT.
Contributions We study the independent NPG algorithm in multi-agent systems and provide novel technical analysis that guarantees a provably fast convergence rate. We start our analysis with potential games in Section ] and then generalize the findings and provide convergence guarantee for Markov potential games in Section 3.2 We show that under mild assumptions, the ergodic (i.c., temporal average of) NE-gap converges with iteration complexity of (c//c) after finite threshold (Theorem 3.6 This result provides substantial improvement over the best known rate of O (1/e²) in [88 Our main theorem also reveals mild or improved dependence on multiple critical factors, including the number of agents n, the initialization dependent factor the distribution mismatch coefficient M, and the discount factor 7, discussed in Section 3 We dedicate Section 3.3 to discuss the impact of the asymptotic suboptimality gap 8", which is new factor in this work.
In addition our theoretical results, two numerical experiments are also conducted in Section 4 verification of the analysis. We consider synthetic potential game similar to (38 and a congestion game from 19. The omitted proofs of our theoretical results can be found in the appendix.
1.1 Related Literature
Markoy Potential Games Since many properties of single-agent RL do not hold in MARL, the analysis of MARL presents several challenges. Various settings have been addressed for MARL in recent works. A major distinction between these works stems from whether the agents are competitive cooperative [II]. In this paper consider MPGs introduced in stochastic control 77. MPGs are a generalized formulation of ddentical-rewant cooperative games. Markov cooperative games
have been studied in the early work of (34] and more recently by 23 24
32
10
The work (36
2c, and 8 formally defined in Section 3 Note that (8] has a different definition of M. For a comparison, we convert results X into current definition of M. "This iteration complexity holds after finite threshold.

---

also offered extensive empirical results for cooperative games using multi-agent proximal policy optimization. The work by [27] established polynomial convergence for MPGs under both Q-update as well as actor-critic update. [25] studied an independent Q-update in MPGs with perturbation, studied potential
which converges stationary point with probability one. Conversely, 17 13 games, a special static case of simplified MPGs with no state transition.
Policy Gradient in Games Policy gradient methods for centralized MDPs have drawn much attention thanks to recent advancements in RL theory 26]. The extension of PG methods to multi-agent settings is quite natural. [6 35| 5 studied two-player zero-sum competitive games. The general-sum linear-quadratic game was studied in [12]. 14 studied general-sum Markov games and
provided convergence of V-lcarning in two-player zero-sum games.
39 38 g which focus on the MPG setting and propose adaptations of PG and NPG-based methods from single-agent problems the MARL provides a detailed comparison between these works. The previous theoretical results in multi-agent systems have provided convergence rates dependent on different parameters of the system. However, the best-known iteration complexity to reach an c-NE in MARL is (1/²²). Therefore. there still exists a rate discrepancy between MARL methods where (1/E) complexity has been established in centralized RL algorithms [T]. Our main contribution to close this gap by establishing an iteration complexity of (L//e) in this work.
Of particular relevance to our work are the works [19
setting. Table I
2 Problem Formulation
We consider stochastic game M (n, A, (ri)e())) 7, consisting of agents denoted by a set [n] = {1, (.l,....7]] n.... The global action space = A X An is the product of individual action spaces, with the global action defined as a := (01, a.)) The global state space is represented by S, and the system transition model captured by P A + A(S). Furthermore, each agent is equipped with an individual reward function r; S x A [0, We use (0, 1) to denote the discount factor and p (SS) to denote the initial state distribution.
The system policy is denoted by π : S - (AA)) x ... x A(A,) C A(A), where ((A) is the probability simplex over the global action space. In the multi-agent setting, all agents make decisions independently given the observed state, often referred to as a decentralized stochastic policy (38). Under this setup, we have <aass) ILa (a,ls)) where n, : S (AA)) is the local policy for agent i. For the ease of notation, we denote the joint policy over the set [n] by T- [[] Ty and use the notation a_; analogously.
We define the state value function (**(s) with respect the reward ri(s. a) VT((s)
E" 1Ee5 ""ri(s", a'){s" = s], where (s', a²) denotes the global state-action pair at time t, and denote the expected value of the state value function over the initial state distribution p as (P)(p) == Exppl (x)) We can similarly define the state visitation distribution under as s)|so pl. where 1 is the indicator function. The state-action value function and advantage function are, respectively, given by
(0) 7) 2t=0
= E" Σ
(r a (s s, a = a), (s, (5, (s (s).
(I)
For the sake of analysis, we further define the marginalized Q-function and advantage function : Ai - R and A; A; R as:
(s) = Σ (77
A7 =
(2)
Definition 2.1 (339). The stochastic game M is a Markov potential game if there exists a bounded potential function : A + I. such that for any agent i, initial state and any set of policies Ti, R.., π n-zi
Mh - (5) -V (s) i.. (s) (.. (())
where 4h (s)
EE D x 605 )s s).
3

---

We assume that upper bound exists for the potential function, i.e., 0 S á(s, a) S Omax vs E
S, a E A, and consequently, (T(ss) ómaz
It is common in policy optimization to parameterize the policy for easier computations. In this paper, we focus on the widely used softmax parameterization [ [26), where global policy ((ass)
[ TT (aaaa))) s) is parameterized by set of parameters (01,... Jn E ||Six[A] in the following form
exp([0s]a.a.}
(a:ls)) = Eajea En, exp((0ils.a))
V(s,a,) Ex
2.1 Optimality Conditions
In the MPG setting, there may exist multiple stationary points, a set of policies that has zero policy gradients, for the same problem; therefore, we need to introduce notions of solutions to evaluate policies. The term Nash equilibrium is used to define measure of "stationarity" in strategic games.
Definition 2.2. A joint policy xt is called a Nush equilibrium for all i [n]. we have
(p) 2 V. ( for all n..
For any given joint policy that does not necessarily satisfy the definition of NE, we provide the definition of NE-gap follows [39]
NE- gap(()(
max iE (EEM),=EEAAA
V (p) V.TE. (p)
Furthermore, we refer to joint policy т as e-NE when its NE-gap(T)) <.. The NE-gap satisfies the following inequalities based on the performance difference lemma
NE-gap (T) S
Σ 1
di max A. (s,
In the tabular single-agent RL, most works consider the optimality gap as the difference between the expectations of the value functions of the current policy and the optimal policy, defined as v= (p) v (p). However, this notion does not extend to multi-agent systems. Even in fully cooperative MPG where all agents share the same reward, the optimal policy of one agent is dependent on the joint policies of other agents. As result,
common for the system to have multiple "best" policy combinations (or stationary points), which all constitute Nash equilibria. Additionally, it has also been addressed by previous works that any NE point an MPG is first order stable (39]. Given that this work addresses MARL problem, focus our analysis on the NE-gap.
3
Main Results
3.1 Warm-Up: Potential Games
In this section, we first consider the instructive case of static potential games, where the state does not change with time. Potential games important class of games that admit potential function
to capture differences in each agent's 's reward function caused by unilateral bias 28 [3] defined as
which is
r3 Ta(ai, a-)) ra ri(a,, a.:) :la;, a-:) p(aa)aa)) a-:;; Vas, d/s a-i-
(3)
Al Algorithm Update In the potential games setting, the policy update using natural policy gradient is
n (as) x n (a:) exp(x*((a))
where the exact independent gradient over policy mi also referred as oracle, is captured by the marginalized reward Fa(a)) Em--oo- (rr((arrr a.)].. By definition, the NE-gap for potential games

---

is calculated as maxielm] (m, - m.. Pf), where TH E arg maxx, V, v is the optimal solution for agent i when the rest of the agents use the joint policy -ř.-
The local marginalized reward (a,) is calculated based on other agents' policies; hence, for any two sets of policies, the difference in marginalized reward can be bounded using the total variation distance the two probability measures [4]. Using this property, we can also show that there is a "smooth" relationship between the marginalized rewards and their respective policies. We note that this relationship holds for stochastic games in general. It does not depend on the nature of the policy update or the potential game assumption.
We now introduce lemma that is specific to the potential game formulation and the NPG update:
Lemma 3.1. Given policy TH and marginalized reward (a:). for xh*1 generated using an NPG
update in (4 we have the following inequality for any 17
Vi
((*+t)) - <6(T) 2 (1- Vnn)
k+1
Lemma 3.1 provides lower bound on the difference of potential functions between two consec- utive steps. This implies that at each time step, the potential function value is guaranteed to be monotonically increasing, as long as the learning rate satisfies 1) <
Note that the lower bound of Lemma 3.1 involves (x, n.. F.)) which resembles the form of
NE-gap (m:* n. r.)) Assuming we can establish a lower bound for the right-hand side of Lemma 3.1 using NE-gap, the next step to show that the sum of all NE-gap iterations is upper bounded by a telescoping sum of the potential function, thus obtaining an upper bound on the NE-gap.
We start by introducing a function f IR + R defined as follows,
T
(*(0)= = Σ (Tit - * r)), where (-,a()) x n. exx((rr(())))
(5)
1=1
It is obvious that (*) = 0, (n) Ex - (t) 2 O, and 1im ox (a) -Ei(T x r!).
Without loss of generality, for agent at iteration k; define at, E arg maxa, EA, 73 (a,) =: A and
at, aarg mag (a;), where A denotes the set of the best possible actions for agent i
iteration k. Similar to 38 we define
;= min (E(m)
Σ a.EA
+f(a)) E (0,1), mi = (at,) (t (0,
(6)
iE(n)
Additionally, we denote ok := minke[k] ci;c : inf og > 0; 6k min 8+
We provide the following lemma on the relationship between f (a) and f*((o) = (a). which lays the foundation to obtain sharper results than those in the existing work.
Lemma 3.2. For function j (a) defined in (5) and any a > O, we have the following inequality.
(*(aa) 2 (00) 1 c(exp(aok) - 1) +1
We refer to ōσ as the minimal suboptimality gap of the system for the first K iterations, the effect of which will be discussed later in Section 3.3 Using the two lemmas above and the definitions 8x. we establish the following theorem on the convergence of the NPG algorithm in potential games.
and
Theorem 3.3. Consider a potential game with NPG update using For any K 2 1, choosing
1 2 we have
K
20max (1
2/n
NE- NE-gap(T"h)
K
K
cox
5

---

Proof. Choose 11 2/n
1 in Lemma 3.2
1
NE-gap(m
< lim (*)
(k) - 1 cdx
(*
c(xp((xx) -1)+1
2vn
x((xa)] = -[ - [(x+)][[1+ (
(1
Vnn)
obxn+1
Then, we have R NE-gap(T*)
K-1
210( --
)-
(1
m COK
20maz
2
K
One challenge in MARL is that the NE-gap is not monotonic, so we must seek ergodic convergence results, which characterize the behavior of the temporal average of the NE-gap. Theorem 3.3 shows that for potential games with NPG policy update, the ergodic NE-gap of the system converges to zero with rate (11/ (1))))x)) ))- When бж is uniformly lower bounded, Theorem 3.3 provides significant speed up compared to previous convergence results. Apart from the iteration complexity, the NE-gap also dependent linearly on 1/c and 1/0k. We address the effect of in the analysis here and defer the discussion of åx to Section 3.3 Under some mild assumptions, we can show that the system converges with rate of O(1/K).
The Effect of The convergence potentially be arbitrarily small. A small value for с generally describes a policy that is stuck at some regions far from NE, yet the policy gradient small. has been shown in (20) that these ill-conditioned problems could take exponential time to solve even in single-agent settings for policy gradient methods. The same issue also occurs NPG in MARL, since the local Fisher information matrix can not cancel the occupancy measure and action probability of other agents. A similar problem has also been reported in the analysis of [38 26 for the MPG setting. (38] proposed the addition of log-barrier regularization to mitigate this issue. However, that comes at the cost of an ((1/()K)) convergence rate to a X-neighborhood solution, which only reduced to the exact convergence rate (LI/V)) when À = 1/vKK. Therefore, this limitation may not effectively avoided without impacting the convergence rate.
given by Theorem 3.3 scales with 1/c, where e might
3.2 General Markov Potential Games
We now extend our analysis MPGs. The analysis mainly follows similar framework as potential games. However, the introduction of state transitions and the discount factor 7 add an additional layer
of complexity to the problem, making it far from trivial. As pointed out in [19], we can construet MDPs that are potential games for every state, yet the entire system is not MPG. Thus, the analysis of potential games does not directly apply MPGs.
We first provide the independent NPG update for MPGs.
Algorithm Update
For MPGs at iteration k; the independent NPG updates the policy as follows
38
"1p"" (s,
x *+ oc a& (a.ls) exp
1 1-7
where A, defined in (
Different agents in a MPG do not share reward functions in general, which makes difficult to compare evaluations of gradients across agents. However, with the introduction of Lemma (3.4 we find that MPGs have similar properties as fully cooperative games with a shared reward function. This enables
establish relationships between policy updates of all agents. We first define (a a) == rs(s, a) - ő(s, a), which implies V,7 (s) o=(s) V. (s).
Lemma 3.4. Define AW, (s, a;) with respect to h2 similar to 2p. We then have
(=((ar)))) ( (a(ass)) (s, 0, Es 1,). E A(Ai).

---

Lemma 3.4 shows a unique property of function hús where the expectation of the marginalized advantage function over every local policy ग. yields the same effect. This property is directly associated with the MPG problem structure and is later used in Lemma 3.5 Next, we introduce the following assumption on the state visitation distribution, which is erucial and standard for studying the Markov dynamics of the system.
Assumption 3.1 [ 38 8)..
The Markov potential game M satisfies: inf, min, (5 >
Similar to potential games, when the potential function o of a MPG is bounded, the marginalized advantage function A, for two policies can be bounded by the total variation between the policies.
Additionally, similar to Lemma 3.1 we present a lower bound in the following lemma for the potential function difference in two consecutive rounds.
Lemma 3.5. Given policy xh and marginalized advantage function A²" (s, az). for *+t1 generated using NPG update in 77. we have the following inequality,
Vnddmas!! x= x=11 (p) x-' (p) 2 1-7 (1 (1- 7)3
(1ss) A," (s.
p
Thus, using a function f adapted from (5) as a connection, we are able establish the convergence of NE-gap for MPGs in the following theorem.
Theorem 3.6. Consider a MPG with isolated stationary points and the policy update following NPG have
(1-7)²
update 7 For any K 1, choosing 7 2//7mmmas
K-1
2M 2Momax
2 2/Tidmaz
NE-gap(T
K(1 x(1-7) (1+
K
where
M = sup max (s)
c: inf
Σ x((ayls)) E (0.1),
0ES
8h = min
1F (s, (s, - A. (s, at))), and 6x = min 8t E (0, 1),
xEsS),EES
osksK-1
similar to 6
Here, isolated implies that no other stationary points exist any sufficiently small open neighborhood of any stationary point. This convergence result is similar to that provided in Theorem 3.3 for potential games. We note that our theorem also applies an alternate definition for MPGs in works such as [8], which we discuss in Appendix [ Compared to potential games, the major difference is the introduction of M, which measures the distribution mismatch the system. Generally, Assumption
3.1 implies finite value for M in the MPG setup.
Discussion and Comparison on Convergence Rate Compared the iteration complexity of previous works listed in Table the convergence rate in Theorem presents multiple improvements. Most importantly, the theorem guarantees that the averaged NE-gap reaches in O(1/c) iterations, improving the best previously known result of (1/e²) in Table [] Furthermore, this rate of convergence does not depend on the size of action space [A,], and it has milder dependence other system parameters, such as the distribution mismatch coefficient M and (1 - 7). Note that many of the parameters above could be arbitrarily large in practice (e.g., -- 0.01 in congestion game experiment). Theorem 3.6 indicates a tighter convergence bound with respect to the discussed factors in general.
3.3 The Consideration of Suboptimality Gap
In Theorems 3.3 and 3.6 we established the ergodic convergence rates of NPG in potential game and Markov potential game settings, which depend on 1/8x. In these results, 8 generally encapsulates
7

---

the difference between the gradients evaluated at the best and second best policies, and 6σ is a lower bound on 8². We refer to 8 as the suboptimality gap iteration k. our analysis, the suboptimality gap provides a vehicle to establish the improvement of the potential function in two consecutive steps. In particular, it enables to draw connection between Ø= =-= and NE-gap(#* using Lemma 3.2 and Lemma B.3 in the appendix. On the contrary, most of the existing work does not rely on this approach and generally studies the relationship between o 4 x= and the squared NE-gap(T"), which suffers slower convergence rate of OLI/VK)
[38
The analysis leveraging the suboptimality gap, though has not been adopted in the MARL studies, was considered in the single-agent scenario. Khodadadian et al. [16] proved asympiotic geometric convergence of single-agent RL with the introduction of optimal advantage function gap Á which shares similar definition as the gap 8 studied in this work. Moreover, the notion of suboptimality gap is commonly used in the multi-armas bandit literature so as to give the instance-dependent analysis.
While our convergence rate is sharper, lower bound on the suboptimality gap is generally not guaranteed, and scenarios with zero optimality gap can be constructed in MPGs. In practice, we find that even if 8 approaches zero in certain iterations, it may not converge zero, and in these scenarios the system still converges without a slowdown. We provide a numerical example in Section 4.1 (Fig. aap to support our claim. Nevertheless. in what follows, we further identify sufficient condition that allows us to alleviate this problem altogether by focusing on the asymptotic profile of the sub-optimality gap.
Theoretical Relaxation The following proposition guarantees the asymptotic results of independent NPG.
holds and that the stationary policies are isolated. Then independent NPG with 2/ndmaz guarantees that limg-+00 x² T. where x. a Nash policy.
Proposition 3.1 ((38). Suppose that Assumption
3.1
(1-2)²
Since asymptotic convergence of policy is guaranteed by Proposition 3.1 the suboptimality gap 8 is also guaranteed to converge to some 8* We make the following assumption about the asymptotic suboptimality gap, which only depends on the property of the game itself.
Assumption 3.2. Assume that lim 8* = 8" > O.
Assumption 3.2 provides relaxation in the sense that instead of requiring a lower bound inf 8* for all k, we only need 8* > 0, lower bound on the limit as the agents approach some Nash policies. This will allow us to disregard the transition behavior of the system and focus on the rate for large enough k.
By the definition of 8*, we know that there exists finite K' such that Vk K', 18
801
2 8
2. Using these results, we can rework the proofs of Theorems 3.3 and 3.6 to get the following corollary.
8"
Corollary 3.6.1. Consider a MPG that satisfies Assumption 3.2
with NPG update using algorithm
There exists K', such that for any K 1, choosing 1) 2 2//imaax
(1-7)*
have
Σ
1 NE-gap(
2M amma
4 4VTidmann
K'
(1
K
K(1
cō* (1 77)
2M
where M, are defined in Theorem 3.6
4 Experimental Results
In previous sections, we established the theoretical convergence of NPG in MPGs. In order to verify the results, we construct two experimental settings for the NPG update and compare our empirical results with existing algorithms. We consider synthetic potential game scenario with randomly generated rewards and a congestion problem studied in [9 and S. We also provide the source code for all experiments.
"http::/ggituub.oom/muuuut http:///gttbbbooommmmmmeeeeeeeed
8

---

Died Praeciss G SiAces
Dead Papyoce ii foond
3.9
25
batiia Pt) Sahmm
Setrra RPC
1.19
0.80
Foritioss
Reooaas
(a)
(b)
(C)
Figure 1: (a) The suboptimality gap; (b) Learning curve in synthetic experiments; (c) Learning curve for congestion game,
4.1 Synthetic Potential Games
We first construct potential game with a fully cooperative objective, where the reward tensor r(a) randomly generated from uniform distribution. We set the agent number n each with different action space |A1] = 3, |A22l = 4. |Agl 5. At the start of the experiment, all agents are initialized with uniform policies. We note that the experimental setting in (38) falls under this broad setting, although the experiment therein was a two-player game with carefully designed rewards.
The results are shown in Figure 1b
We compare the performance of independent NPG with other commonly studied policy updates, such as projected Q ascent [8, entropy regularized NPG [38 as well as fog-barrier regularized NPG method (38). We set the learning rate of all algorithms as 1) 0.1. We also fine-tune regularization parameters to find the entropy regularization factor
0.05 and the log-barrier regularization factor 0.005. As discussed in Section 3.1 (the effect of c), we observe in Figure that the regularized algorithms fail to reach an exact Nash policy despite exhibiting good convergence performance at the start. The empirical results here align with our theoretical findings in Section 3
Impact of e and 5 We demonstrate the impact of the initialization dependent factor c* and subopti- mality gap 8* in MPGs with the same experimental setup. Figure la depicts the change in value for ct, 8hh and the NE-gap. We can see from the figure that as the algorithm updates over iterations, the value of c increases and approaches one, while 8 approaches some non-zero constant. Figure Ia shows that although 5* could be arbitrarily small in theory if we do not impose technical assumptions, it is not the case in general. Therefore, one should not automatically assume that the suboptimality gap diminishes with respect to iteration, as the limit entirely depends the problem environment.
The effect of suboptimality gap 8* in PG is illustrated in Section B of the appendix under set of carefully constructed numerical examples. We verify that a larger gap indicates a faster convergence, which corroborates our theory.
4.2 Congestion Game
We now consider a class of MDPs where each state defines a congestion game. We borrow the specific settings for this experiment from [19 g
For the congestion game experiments, we consider the agent number n = 8 with the number of =1|=4 4, where A, = (A, B, C, D) as the corresponding individual action spaces. There are two states defined as S = {safe, distancing). In each state, all agents prefer to be taking the same action with many agents possible. The reward for agent selecting action & is defined by predefined weights w multiplied by the number of other agents taking the same action. Additionally, we set w. < w < " < w. and the reward in distancing state is reduced by some constant compared to the safe state. The state transition depends on the joint actions of all agents. If more than half of all agents take the same action, the system enters a distancing state with lower rewards. If the agents are evenly distributed over all actions, the system enters safe state with higher rewards.
facilities |A,|=
We use episodic updates with T = 20 steps and collect 20 trajectories in each mini-batch and estimate the value function and Q-functions as well as the discounted visitation distribution. We use a discount factor of y 0.99. We adopt the same step size used in [9 8 and determine optimal step-sizes of

---

softmax PG and NPG with grid-search Since regularized methods in Section 4.1 generally do not converge to Nash policies, they are excluded this experiment. To make the experiment results align with previous works, we provide the I. distance between the current-iteration policies compared to Nash policies. We plot the mean and variance of T, distance across multiple runs Figure Tc Compared to the direct parameterized algorithms, the two softmax parameterized algorithms exhibit faster convergence, and softmax parameterized NPG has the best performance across all tested algorithms.
5
Conclusion and Discussion
In this paper, studied Markov potential games in the context of multi-agent reinforcement learning. We focused on the independent natural policy gradient algorithm and studied its convergence rate to the Nash equilibrium. The main theorem of the paper shows that the convergence rate of NPG in MPGs is (1 K), which improves upon the previous results, Additionally, we provided detailed discussions on the impact of some problem factors (e.g., c and d) and compared our rate with the best known results with respect to these factors. Two empirical results were presented as a verification of our analysis.
Despite our newly proposed results, there are still many open problems that need to be addressed. One of the limitations of this work is the assumption of Markov potential games, the relaxation of which could extend our analysis to more general stochastic games. As a matter of fact, the gradient-bar based algorithm studied in this work will fail for zero-sum game simple Tic-Tac- Toe. A similar analysis could also be applied to regularized games and potentially sharper bounds could be obtained. The agents are also assumed to receive gradient information from an oracle in this paper. When such oracle is unavailable, the gradient can be estimated via trajectory samples, which we leave as a future work. Other future directions are the convergence analysis of policy gradient-based algorithms in safe MARL and robust MARL, following the recent exploration of safe single-agent RI. and robust single-agent RL 21
Acknowledgments and Disclosure of Funding
This material is based upon work partially supported by the US Army Contracting Command under W91 INF-22-1-0151 and W91 2004,, US National Science Foundation under CMMI-203866 and US Office of Naval Research under N00014-21-1-23855. The views expressed herein and conclusions contained in this document are those of the authors and should not be interpreted as representing the views or official policies, either expressed or implied, of the U.S. NSF, ONR, ARO, or the United States Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 ((1):4431-4506 45066, 2021.
[2] Jupiter Bakakeu, Schirin Baer, Hans-Henning Klos, Joern Peschke, Matthias Brossog, and Joerg Franke. Multi-agent reinforeement learning for the energy optimization of cyber-physical production systems. Artificial Intelligence in Industry 4.0: A Collection of Innovative Re- search Case-studies that are Reworking the Way We Look at Industry 4.0 Thanks to Artificial Intelligence, pages 143-163, 2021.
[3] Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multia- gent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156 172, 2008
[4] Shicong Cen, Fan Chen, and Yuejie Chi. Independent natural policy gradient methods for potential games: Finite-time global convergence with entropy regularization. 2022 IEEE 61 Conference Decision and Control (CDC), pages 2833-2838. IEEE, 2022.
10

---

[5] Shicong Cen, Yuejie Chi, Simon Shaolei Du, and Lin Xiao. Faster last- last-iterate convergence of policy optimization in zero-sum markov games. In The Eleventh International Conference on Learning Representations, 2022.
[6] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances neural information processing systems, 33:5527-554p 2020.
[7] W Davis Dechert and SI O' D'Dnnelll. The stochastic lake game: A numerical solution. Journal of Economic Dynamics and Control, 3009-10) 2006.
[8] Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Mihailo Jovanovic. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, pages 5166-
5220. PMLR, 2022.
[9] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33:8378 8390, 2020.
[10] Roy Fox, Stephen M Mcaleer, Will Overman, and Ioannis Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, pages 4414-4425 PMLR, 2022.
[11] Sven Gronauer and Klaus Diepold. Multi-agent deep reinforcement learning: survey. Artificial Intelligence Review, pages 1 1-49, 2022.
[12] Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods find the nash equilibrium in n-player general-sum linear-quadratic games. Journal of Machine Learning Research, 24(139), 2023.
[13] Amélie Heliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. Advances in Neural Information Processing Systems, 30, 2017.
[14] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. In ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022.
[15] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learming, ICML '02, page 267-274, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.
[16] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On linear and super-linear convergence of natural policy gradient algorithm. Systems & Control Letters, 164:1052 2022.
[17] Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 533-542, 2009.
[18] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[19] Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global conver- gence of multi-agent policy gradient in markov potential games. In International Conference on Learning Representations, 2022.
[20] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. In Conference on Learning Theory, pages 3107-3110. PMLR, 2021.
[21] Yan Li, Guanghui Lan, and Tuo Zhao. First-order policy optimization for robust markov decision process. arXiv preprint MxXiv:2209.10577 2022.
[22] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arX1v:2111.00552, 2021.
[23] Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competiiiee environments. Advances in neural information processing systems, 30, 2017.

---

[24] Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closed-loop policies for markov potential games. In International Conference on Learning Representations. 2018.
[25] Chinmay Maheshwari, Manxi Wu, Druv Pai, and Shankar Sastry. Independent and decentralized learning in markov potential games. arXiv preprint 220i::2200./459000 2022.
[26] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 0820-68299 PMLR, 2020.
[27] David H Mguni, Yutong Wu, Yali Du, Yaodong Yang. Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang- Learning in nonzero-sum stochastic games with potentials. In International Conference on Machine Learning, pages 7688-7699. PMLR, 2021.
[28] Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124- 143, 1996.
[29] John F Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-49) 1950.
[30] Guillaume Sartoretti, Yue Wu, William Paivine, TK Satish Kumar, Sven Koenig, and Howie Choset. Distributed reinforcement learning for multi-robot decentralized collective construction. In Distributed Autonomous Robotic Systems: The 14th International Symposium, pages 35-49. Springer, 2019.
[31] Shai learning for autonomous driving. arXiv preprint arXiv: /610.03295 2016.
Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement
[32] Ziang Song, Song Mei, and Yu Bai. When number of players sample-efficienlly? In International Conference on Learning Representations, 2022.
learn general-sum markov games with large
[33] Alexander Trott, Sunil Srinivasa, Douwe van der Wal, Sebastien Haneuse, and Stephan Zheng. Building a foundation for data-driven, interpretable, and robust policy design using the ai economist. Interpretable, and Robust Policy Design using the Al Economist (August 5, 202/), 2021.
[34] Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning to play an optimal nash equilibrium in team markov games. Advances in neural information processing systems, 15, 2002.
[35] Chen- Yu Wei, Chung- Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizen competitive markov games. In Conference on learning theory, pages 2259-4299. PMLR, 2021.
[36] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Systems, 35:24611-24624 1-24224, 2022.
[37] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of thcories and algorithms. Handbook of reinforcement learning and control,
pages 321-384, 2021.
[38] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35: 15:3-1911935 2022.
[39] Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity. 2021.
[40] Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, PR Kumar, and Chao Tian. Natural actor- critic for robust reinforcement learning with function approximation. Advances in neural information processing systems, 2023.
[41] Ruida Zhou, Tao I Liu, Dileep Kalathil, PR Kumar, and Chao Tian. Anchor-changing regular- ized natural policy gradient for multi-objective reinforcement learning. Advances in Neural Information Processing Systems, 2022.
12

---

A Proof for Potential Games in Section 3.1
We first find the upper bound on the difference in marginalizedd rewards under two policies. The following lemma establishes a "smooth" relationship between the marginalized rewards and their respective policies. For ease of notation, where these function values are taken expectation over policy
denote r(x) == (a><(r((a) and Φ(T)) -e-=(o(a
Lemma A.1. For any two sets of policies n, n' E reward of any agent is bounded by the total variation distance of policies,
the difference in marginalized
|
P. 10x 2TV (TT()
Proof. Given any n, n' E (AA), we have
(a:) o.. (a:)) = lri0;; a-:)] Ba_ Ba
s |rilloo| -+ T' S 27 (T
Next, we provide the proof of Lemma 3.1 which demonstrates the lower bound of the potential function difference.
Lemma A.2 (Restatement of Lemma
3.1
Given policy a and marginalized reward rit (a:), for have the following inequality for any dl VT
k+1 generated using the NPG update
o(ab+1) - <6(TT) (1 vnn)
71)
Proof of Lemma 3.1 We introduce
# (a = II x jZt
(a,)
k+1 (at) # II E>1
to denote the mixed strategy where any agent with index i follows TH and any agent with index follows n.. k+1 instead. Let PK be the associated marginalized reward function, i.e.,
p) EE Ea [r](a]]= = E
(at, (0ii,a=i)
II
(az)
II
m A+1
(at).
;eA
121
follows that
k+1 Φ ( + (mf,... m 7 m
x Φ
mi+1 ((+11)
k+1 #
We now decompose @=+1 - 0t as follows:
((* - (((*)) = e (T k-1 * - Φ (T #
(m k+1 x - & ( _
=
ri (T: k+1 a ri (क *b,))
Σ
p/. m
k+1 m + Σ (s/.m k+ m)))
The third equality follows from the definition Since
k+1
<
Σ
TV
(T
111
k+1
13

---

2
TV 2 + vn
||
k+1 x. 1
E=
i=1
KL + n
L
KL |=]]]
vT
( b+1
# log म. k+1 - log n.
n/n Σ (m k+ mt. +/))
we have
(( <6(T**
2 (1 - vnn)
k+1
xt)
Additionally, we provide the proof of Lemma 3.2 which builds the relationship between potential function difference and NE-gap.
Lemma A.3 (Restatement of Lemma 3.2p have the following inequality.
For function (a) defined in 5 and any a >> we
(a 2 (00) 1 c(exp(aδk) - 1) +1
Proof. Recall that we define of E arg maX F! (a,) =: A and df
arg max Ei (az), where A denotes the set of the best possible actions for agent i. For any E [n], we have
(Tia r()
Ea, (a.) (a))) E't(a)ttinn
E., (xx))))xxpp(((())
Enjedt (ta) (a,) exp + Eajeanay ((y)) (Ttt(attt)))
Σ (a))(((())))
Eajeat, t5 expt + E Eajeding *T(a,) exp (a)
(att) (Eaees {((1a)) exp (7+ (at,) - * ) + EmgEArAA (aa))
Σ (a.))
Emgest, Tे ((())) exp (F) )aa + +nJEAAAA ((,(a)
p/ (aft) ) Eajest, (T((a)) exp
(F (ott) ( } + EnjeAris ((aa))))(a))
Eajeat, nt(1))) exp ( )a} + EajeAAn *((a))
EaAEAi (+((at))+(a))) (a;)) (a,)
Σ att(ai)t(a))
Eojest *t(a)) exp( (att,) r(t(tt } EasEARAA *b(as)
En, (++ - P (as))
-P (ott)) Σ (ar))()))))) (Emjeat, at(a,)) (ospl (F+ (at,)) ) - p/ (at )a - 1) +1
- >Σ (+) - +( [1- (Eoyesy *+(a)) (exp( (F+ (att) p7 (at -1 +1
-
1
14

---

2(m²" xf.
c(exp(8taa} 1) +
where the first inequality holds due Lemma D.I
By taking sum over all agents E [n]] we get
(* = Σ
iia n1 r
EE|n]
[1-
1
2 (
k (.)
c(exp(ota) -
1E/m]
2 (0o)
clexpláka- - 11)
We next provide the following lemma on the structure of potential games. This lemma is not directly used in the analysis of this paper but instead provides discussion on the function class of potential games, which could be of separate interest.
Lemma A.4 (Structure potential game reward function class). For any agent i, the set of reward functions for potential games, Ri, has the following structure within the ambient space of OfRI, IA,
(aaaaa))) gc(aa))) (((a))) Vg. A CRTTIA
R₂
(8)
5#1
Proof. The reward vector r; E IRI.. |Ail can be viewed as an I |A -dimensional linear vector. There are in total (IA:,- 1) II jyz - |A.| - II; |A, independent constraints w.r.t ry and potential function s. Since R, is linear space with dimension Il [Agl. R2 is the space of valid reward functions for potential games.
B Proof for Markov Potential Games in Section 3.2
We first introduce the following lemma to fill the gap between general MPGs and fully-cooperative MPGs. Define (s,8, a) == r= 0(8 a), which implies V (s) = <5 + (s).
Lemma B.1 (Restatement of Lemma 3.4 Define Añ (s,a.) with respect h, similar to We then have
Σ (m/(a.]s)
=0, Vs S,i [m]. T. A(A.).
Proof of Lemma 3.4 Due to the definition of Markov potential game, we have
Viltit- (u) V= - D (())
for any (a, प. and m.. It then follows that
V - (w) k. (p) Σ
G. (s) M (<((a)))) T((a:ss)) (s,
Denote [P] BaNT, x (P(s'ss, a)) the transition matrix generated by policy & m Then
1
dp t
m(1 + 7P + 7 + ....) -
where - and are row vectors and (I - P) is clearly full rank. Since the above relationship holds for any μ E As, we get Ea, (7/(a//33 T: (a. (8,0;), E
Then, analyze the lower bound of the potential value function difference.
15

---

Lemma B.2 (Restatement of Lemma 3.5). Given policy x" and marginalized advantage function
Ag" (s, for nh+1 generated using NPG update in have the following inequality,
Φr (p) - Φ- (p)
vnlman'! (1-))3
d
( k+t (-1s,, A7 (s, (s
p
8
1=1
Proof of Lemma 3.5 We introduce
- (a_;ls) =
k+ (azls) Il E>1
Th (aels)
j-l
to denote the mixed strategy where each agent with index j < i follows 7. and each agent with index & > i follows oे instead. Let A be the associated marginalized advantage value based on potential function, i.e.
A (s)
Σ a-;)); II n1 (aşls) x (aels).
(5,
a
jei
We now decompose t
n+* as follows:
(p)
$='(p (p)
Σ
do
drttl (s)
Σ
(c(s)) (s.a)
i-1
p
++1
J (ayls) II
o (arls)
II
x
x+1
(ayls) (s)
(aels)
s)
15 (s.
iml
(=#+1
5=1
E=
++ (a:ls) - (ac (s, as)
(asls) (a.ss)) A3 (s,
d
(a:ls) (a (s,
(a (1s - At a:)).
1=1
Since
1 (s, AT
i-1
n II ri+t
Σ s+1 (ayls) II
3 (az
के (aels) as,a)
Omas
- m.,((13)11,
using Lemma 3.4 we have
x= (0) x= (p)
k+l (a:l))Aa (s,a:)
i=1
Ømaz
Σ #+1
|| k+1 (-|s) - (1, - +f,(-1s)]1
7)2
16

---

Since
a (-ss - (->)| +-1(11
| - (1b)]1 n (-1s) (1,011
[I (-1s)] (-)0)))((((())))))) ( (1
(T) ++1 --16)) 1 (-1s) log क. (-1s))
mm
k+1 (11s) - (11s), A7 (s.
Tm Σ
n
m
++ (11s,, (7"((,))
we have
Vnlman'!
11
(0) - x-"² (p) 2 1- - 7)3
Σ d
k+1
(8) >9)<6
(m)
k+1 (-1s), A (s,
Next, we introduce the following lemma, which is the MPG version of Lemma 3.2
Lemma B.3. At iteration define
(a() = EE (a,aa, (s) az), where (-1s) x a, (-1s) exp (ads" (8,:)
1-7
vE[n] ai
Then, for any O,
5ta c(exp
1) +1
1-y
with and 8 defined in Theorem 3.6
Proof. For any i iE [n]], we have
Ea, AT (s, (.)T)//((a) exp
an
(s,a)) (s.as)
(²(()= = Σ
(aaa)) 1-7
1E|m)
En, mp (agls) cxps
ad; (srat)
(a (dpp"10na
exp A (s, of EEaEes क =F([o[s))
EayEann A (s, (a,ls) (a,ls) exp
l-x
1-9
2
"adp" (sratt) 1-7
aa (m,at)
vE(x]
(Eaeett * exp
EasEA ((aa))))xpp
a(d) (e
-- (srat)) 1)
A (s, of,) EEaees ({)(sss)) exp
+ EEgEAnn (s
1-n aa(As" 1-x (s,at, ))
[x
EEgest, of ({,lss) exp
Eajed (a,lls))
Eajedhan (AF (s, (s, - AF (s, (T)))))))())
Σ
AF (s, (s.ot,)
EEoeest (t(a)ls)) exp= (aiat) ) A7 (s.at,))
(c)
+ +Eo (Haals
17

---

Σ A
(f)
1
iE(N]
clexp
8ºa I-7
1)
+
2 (oc)
c(exp
6% [-7
1) +1
where the first inequality holds due to Lemma D.I
Combining the above lemmas, show the proof of Theorem 3.6
(1-7)²
Proof of Theorem 3.0 Choose a = == 2/T
in Lemma B.3
NE-gap(T*)
(s) max AT (s. 0z)
?
ae
1 d
(s) max A7" (s)
d
oj
M
d
max AT (s,
p
di
M Σ
(8)
lim (a)
7
Σ
(s)
1
p
cLexp
1)+1
1-7
k+ (a.ls)A²² (s. a2. +
2(1 7)
cōt19
2 Tilmma
($ (p) क (p))2.
c6 (1
2 2/Timmax
< (1))+) (p) ** (p))2M + cōx (1 77)
Then
K-1
2M( (p) - (p)) 2/ridmax )
2M 2Momax (1+ + 2/ti@maa
NE NE-gap(m*h)
(1 cōx(1 (1-)) K(1 (1->) 7)
cd (1 -7)
K
K
0=
Finally, we show corollary of Theorem 3.6
Corollary B.3.1 (Restatement of Corollary 3.6.1) Consider MPG that satisfies Assumption 3.2 with
NPG update using algorithm 7 There exists K", such that for any K 2 1, choosing 1) 22/00mos we have
K NT-
2M 2.ndmas
(1 +1+ 4yTidmaa +
K"
K
K(1 -7) cō c5-(1- -7) 2M
where M, are defined as in Theorem 3.6
Proof of Corollary 3.6.1
Following from the main paper, we know that there exists K' such that for
all k 2 K', 8 Z.
18

---

From the proof of Theorem 3.6 we know that for MPGs, we get the following relationship:
2v 2/n@mox
NE-gap(T*) S ($ (0) 6² (0))2M +
cd -7)
Therefore, for all k K',
NE-gap(m*) S ($-^*1 (0) $5 (p))2M(1 + 4v dynimmar c0. -17)
Then, taking summation from K" K 1, we get
K-1 NE-gap(a**)
2. AMmaa s 1 1-9
4yTi@mas
(1 c5 (1-
Additionally, we know that NE-gap( < equations above, we have
Oiess for all l: by the definition of MPG. Combining the I-
K
K'
K
NE- NE-gap(1t
(T
NE-gap +
Σ
NE-gap(T*)
K
K
k=k!
1
2M 2.Momax (1 1+ 4yTidmax ) +
Omank
< K
7)
cd- - -7)
1 7
2 2M Φmax (1 AVTipmaz +
K'
K[1
c5* (1-)) 2M
C Extension to General MPG Formulation
In this section, we extend our results more general form of potential function. Note that the detailed analysis is omitted for brevity. Proofs of lemmas and theorem this section either exist in previous works or closely follow our analysis in Section B
Definition C.1 (Alternate definition of MPG
8 ). For MPG, any state s, there exists global
function -T (s) 11 x S + R such that
V. Vi Voll (8) (.))-((s) (1.
true for any policies W., T IT,
This definition of MPG differs from Definition 2.1 and does not enforce the existence of additional structure in function Φb However, whether the definitions equivalent, similar Lemma A.4 still an open question to the best of the authors' knowledge.
and
We present the following Lemmas from (8), using which we provide a similar result Lemma 3.5
Lemma C.1 (8). For any function _ :II1 + R, and any two policies n, T' E II,
T
v - )Ta)
Σ
Σ
Then S Ten Hisponn) Tea sussoa + Ren M
Lemma C.2 (8). Consider two-player game (group of players) with common-payoff Markov
game with state spuce S and action sets Ai, Ag, with reward function r, transition function P and policy sets Th Hl be defined with respect to general MDPs. Then for any ni, n E Th, n2; n/j Tl, the for value function v (1).
19

---

(n) V=i (m) Vai
2M max; [Ai
Σ 1f (lm (100)=(((113 x(((ss)] (12((1)) - m/((1)) (1-7)*
We refer to 8 for complete proof for Lemmas C.I and C.2
By using Lemmas C.I and C.2 we can
replace Lemma 3.5 in our paper with the following lemma.
Lemma C.3. Given policy nh and marginalized advantage function Ag (8, az), for n h-1 generated using independent NPG update, we have the following inequality,
1 1-7
2M max, |Aimn
t (p) - D" (p) 2
m k+l (-1s), (s. )))
(1 (1-7) 7)3
The proof of Lemma C.3 closely follows proof of Lemma 3.5
First the potential function difference
tx ++1 (p) "= (p) is decomposed following Lemma 3.5 with each term defined as a potential
function that only differs by the local policy Different from 3.5 the decomposition is based
on Definition C. instead. Then each term can be bounded using Lemma C.I with the addition of Lemma to handle the residual terms.
get similar convergence guarantee without the explicit definition of Ø, as stated in the following theorem:
Combining Lemma CS and Lemma B.3
Theorem C.4. Consider a MPG in the sense of Definition C. with isolated stationary points, where
the policy update follows NPG update in 7). For any K 2 1, choosing InM max,
(1-7)²
we have
[A,
K
2M Φmaz
(1 8nM max; Miil
K"
NE-gap(T*)
+
K
K(1
cō -7)
2M
The proof of Theorem C.4 follows Theorem 3.6 and Corollary 3.6. and the only difference in the
process is the different choice of ry from Lemma C.3 incorporates additional terms on M (distribution mismatch coefficient) and [A, (size of action space), but the (1/e)) order is still maintained.
Compared to Corollary [36.T] Theorem C.4
D Supporting Lemmas
Lemma D.I. Given a reward vector [r1, Tn] where T1 12 > Tn with
weights Ti 2ie T2 ... The we have
Σ # Timear
rimjeam Dim 2
Ei=l meao
Ti Tiear + Li= Teaa
Proof. The above claim can be proved by induction. We first have
E eam
m + #nn
Thear
Tiaa Tar
Σ 1= ar + 1n-18n-1tha
on 14 (nn-1 + an ar
Σn- Teaar + (Tn-1 + T ear
This gives a new reward vector
Pn Tn-2 > r r/-1 In- TT + Fn
>= r/2 =
nn- + Th
with weights
TIE ari
nr
nn of (nn-1 + Jn) an-
nn
20

---

Natrual Policy Gradient: Various
Natrual Policy Grad Varieus 8
6 =00
1.2
6" 10
2.5
=0.1
1.0
6"
5" 0.01
= =0.00
5" 0.001
0.6
1.0
0.0
200
400
600
800
1000
200
400
600
800
1000
Iterationn
Iterations
(a) NE-gap of matrix game with varying 8
(b) L1 accuracy matrix game with varying 6
Define n nn nn and by similar argument above,
RHS E1 i= r + - e
n
D a + (a-jeann-
n1 3 i= T Po-2 Tn-
1ft (πn-2 m
E Tieer + n Th )ear
hn-3 T + In 2dn 2t ann itintt (Tn-2 + Tn-1 + In an
2 +t
Dn mea + (Tn-2 nn-1 + Tn ya
This gives a reward vector
Fa 2 nn Tn nT + Pn Tn
x' >= =2
T/ rn-2"
Tn-2 + nn-1 + Tn
with weights
T mh 2r2 Tn- (Tn-2 + nn- + Tn e
By induction, we have
Pi + 11 T2
RHS 2
T + 1= ar
E Additional Numerical Experiments
illustrate the impact of on the algorithm the following example. We consider 2-by-2 matrix game with the reward matrix
1
3+8
We run the NPG algorithm with the same initial policy under various values of 8 ranging from 1e to 10. The NE-gap and the L1 accuracy over number of running steps are shown in Figures 2a 2b As illustrated in the figure, 8* plays an important role in the convergence of the algorithm. Larger 8 results in faster convergence, which corroborates our theoretical findings.
21


Reviews:
[{"review_id": "AQ2xc59cZL", "reviewer": "Reviewer_gegG", "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.", "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.\"\n\nIn 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). ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback regarding the paper. Please see our responses below with respect to the specific comments. We believe that we have addressed all the concerns raised by the reviewer, and we sincerely hope that the reviewer would consider increasing the score.  \n\n**Q1.** \"$c > 0, \\delta > 0$ could be too strong and unnecessary.\"\n\n**Response:** We understand the concern on $c$ and $\\delta$ raised by the reviewer. **We refer to the above \"Authors' Response to All\" for a more detailed explanation.**\n\n**Q2.** \"... 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 ... directly assuming $c>0$ is still too strong (and possibly unnecessary).\"\n\n**Response:**\nIn single-agent RL, policy gradient depends on a product of the advantage function, the occupancy measure, and the action probability (Eqn. 10 in [1]). Therefore, it is possible for PG algorithm to make a small update although the advantage function is significant. Single-agent NPG solved this issue using the Moore-Penrose inverse of Fisher information matrix to cancel out occupancy measure as well as action probability. However, in MARL, Fisher information matrix does not fully cancel out everything, since its calculation only uses local policy. Based on this observation, we make a comparison between single-agent PG and multi-agent NPG.\n\nNote that we are not the first work to introduce $1/c$ in the analysis of multi-agent independent NPG algorithms. The same assumption is made in [33] with similar accompanying statements saying that \"Based on our analysis and numerical results, even for natural gradient play—which is known to enjoy dimension-free convergence in single agent learning we find in the multiagent setting that it can still become stuck in these undesirable regions. Such evidence suggests that preconditioning according to the Fisher information matrix is not sufficient to ensure fast convergence in multi-agent learning. \"\n\nWe will rephrase our statements accordingly in the final version.\n\n[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431–4506, 2021.\n\n[33] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35:1923–1935, 2022.\n"}, {"review_id": "Ne3X5mX8Ja", "reviewer": "Reviewer_Qt2L", "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.", "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).\n2. 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.\n3. 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?\n4. 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\".\n5. First inequality in the proof of Theorem 3.3, I think should be an equality?\n6. Line 259, I think we cannot claim that |delta^k-delta*| is small, since we are only assuming a lim inf?", "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!", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The article is nicely written, and the claimed results are supported by the theory.\n\nThe 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.\n\nThe 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.\n\nThe 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!)\n\nThe 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.\n\nA 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.\n\nFurthermore, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and support of our paper as well as the valuable suggestions. We are encouraged by the fact that the reviewer finds our paper \"nicely written\", with \"nice convergence rate results\", andthat it is \"self-contained\". Please see our response below with respect to the specific comments.\n\n**Q1.** \"$c$ and $\\delta_K$ are not controlled. They could be arbitrarily small, at least without further work.\"\n\n**Response:** We understand the concern on $c$ and $\\delta_K$ raised by the reviewer. **We refer to the above \"Authors' Response to All\" for a more detailed explanation.**\n\n\n**Q2.** \"... the step up to Markovian settings is much less than in a less restrictive setting.\"\n\n**Response:** We agree that the Markov potential game (MPG) is a restrictive setting compared to the general multi-agent RL (MARL) setting. Considering the difficulty of multi-agent settings, we believe that the convergence analysis of independent NPG in MPG will be an important step in solving the general MARL problems.\n\n**Q3.** \"A more philosophical point is that the article assumes players can receive oracle information. ... where learners might be able to access the advantage functions that are required to implement the method.\"\n\n**Response:** We follow [33] and only consider the oracle setting in our analysis. In general, an oracle can be estimated by Monte Carlo or temporal difference methods for the stochastic setting and can be analyzed similarly as [1]. However, as mentioned by the Reviewer XDXN, it is much harder to handle $c$ in the stochastic setting. We will add the above comment in our final version and leave the related analysis as future work.\n\n\n**Q4.** \"... and I would expect the authors to compare their results with those presented under the multiplicative weights description.\"\n\n\n**Response:** As pointed out by [1] (after Lemma 15), NPG with softmax parameterization is \"identical to the classical multiplicative weights updates\".\n\n\n**Q5.** \"function f ... also important dependence on k, and on $\\pi_{-i}^k$.\"\n\n\n**Response:** At iteration $k$, both $\\pi_i^k$ and $\\bar{r}_i^k$ (oracle) are known and fixed. So the only decision variable for function $f$ is $\\alpha$. For clarity, we will use $f^k(\\alpha)$ in the final version.\n\n\n**Q6.** \"the definition of $a^k_{i_q}$ is clumsy ... .\"\n\n**Response:**\nThe notations for action sets have been updated in the supplementary materials, please see **Authors’ Response to All** for the updated notations.\nFor the main paper, it is enough to only define $\\delta^k$ directly. The definitions of $a^k_{i_q}$ and $a^k_{i_p}$ were in fact used only for the proof of Lemma 3.2 in the appendix. We included them in our main paper only for consistency of analysis.\n\n\n**Q7.** \"... we begin to get bitten by the lack of care in defining what the functions depend on\"\n\n\n**Response:**\nPlease refer to the response to Q5.\n\n\n**Q8.** \"... 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\"\n\n\n**Response:**\n$c^k > 0$ and $c > 0$ are guaranteed as shown in [33], but $\\delta^k > 0$ is not necessarily true for all iterations. For a few iterations $k$, it is possible to have $\\delta^k = 0$. Therefore, we only define $\\delta^* = \\lim_{k \\to \\infty} \\delta^k$ and use $\\delta^*$ in the upper bound (cf. Table 1 and Corollary 3.6.1).\n\n\n**Q9.** \"First inequality in the proof of Theorem 3.3, I think should be an equality?\"\n\n\n**Response:**\nIt should be an inequality due to the fact that NE-gap takes the maximum over all agents, whereas the function $f$ is defined with respect to the summation.\n\n\n**Q10.** \"Line 259, I think we cannot claim that $|\\delta^k-\\delta^*|$ is small, since we are only assuming a lim inf?\"\n\n\n**Response:**\nThe reviewer is correct. In fact, asymptotic convergence for this algorithm is guaranteed in previous works [33], and a limit exists. We will replace $\\liminf$ by $\\lim$ in the final version.\n\n\n[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431–4506, 2021.\n\n\n[33] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35:1923–1935, 2022."}, {"review_id": "cqHHkwALkC", "reviewer": "Reviewer_tti4", "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.", "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?\n2. 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?\n3. 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?", "limitations": "Yes, it is discussed in the conclusion part.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and suggestions concerning our paper. Please see our response below with respect to the specific comments and we sincerely hope that the reviewer would consider increasing the score. \n\n\n**Q1.** \"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.\"\n\n\n**Response:**\nWe use Table 1 to provide a clear summary of our result and existing works, which performs the same function as Table 1 in [33]. $\\delta^*$ was included in the iteration complexity in our Table 1.\nWe will further clarify the use of the suboptimality gap in our statements in the abstract and contributions.\n\n\n**Q2.** \"I also encourage the authors to complement the work with more empirical results.\"\n\n\n**Response:**\nWe have added a purposefully constructed example to show the impact of $\\delta^*$ on the algorithm in practice.\n\nWe consider an example of a 2-by-2 matrix game with the reward matrix\n$r = \\begin{bmatrix}\n1&2\\\\\\3+\\delta^*&3\n\\end{bmatrix}$.\n\nFor the experiments, we have selected various values of $\\delta^*$ ranging from $1e^{-3}$ to 10. We run the same algorithm with the same initial policy for all experiments, and plot both the NE-gap and the L1 accuracy (L1 distance between the current-iteration policies and Nash policies) of the algorithm. It can be seen from the experiments that $\\delta^*$ indeed plays an important role in the convergence of the algorithm.\n\n**Please refer to newly attached pdf in \"Authors' Response to All\" for details.**\n\n\n**Q3.** \"It may also be helpful to state when the suboptimality gap is very small, the results can degenerate into previous results.\"\n\n\n**Response:**\nIn fact, the iteration complexity of independent NPG algorithms is the smaller of the results in this paper and those in [33]. The specific minimum value depends on $\\delta^*$, which depends on the structure of (Markov) potential games.\n\n  \n\n**Q4.** \"Is the c defined as the same as this paper?\"\n\n\n**Response:** Yes, the definition of $c$ is the same.\n\n\n**Q5.** \"Will log barrier regularization have the same effect on the results presented in this paper?\"\n\n\n**Response:** Since the log-barrier regularization repels the trajectory from regions with small policy values, we can derive a lower bound for policy value as Lemma 24 in [33]. While it is true that the log-barrier regularization can remove the dependence on $1/c$, the introduction of log-barrier parameter $\\lambda$ makes the convergence rate slower by $O(1/\\sqrt{K})$ since the upper bound of convergence rate has the form $\\frac{c_1}{\\lambda K} + c_2 \\lambda$.\n\n\n**Q6.** \"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?\"\n\n\n**Response:**\nOur formulation of MPG was originally adapted from that of [33, 34, R1, R2]. The definition of $\\phi$ provides an additional structure to the problem, which changes the way of analysis and may lead to better convergence rates. However, it should be emphasized that even under this formulation, the best-known convergence rate is $O(1/\\sqrt{K})$ [33, 34]. \n\n\n[33] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35:1923–1935, 2022.\n\n\n[34] Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in multi-agent markov stochastic games: Stationary points and convergence. arXiv preprint arXiv:2106.00198, 2021.\n\n\n[R1] Macua, Sergio Valcarcel, Javier Zazo, and Santiago Zazo. \"Learning Parametric Closed-Loop Policies for Markov Potential Games.\" International Conference on Learning Representations. 2018.\n\n\n[R2] Zazo, Santiago, et al. \"Dynamic potential games with constraints: Fundamentals and applications in communications.\" IEEE Transactions on Signal Processing 64.14 (2016): 3806-3821.\n"}, {"review_id": "IL0cN8ok1p", "reviewer": "Reviewer_XDXN", "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. \n", "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$? \n\n2. 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. \n\n3. 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? \n\n4. 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.  \n\n5. l. 153: why do we have that $f(\\eta) \\geq 0$? \n", "limitations": "The paper mentions the MPG setting as a limitation in the conclusion. \n\n**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. \n\n   Mei et al. ‘Understanding the effect of stochasticity in policy optimization’ (Neurips 2021)", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The convergence analysis improves over the $O(1/\\epsilon^2)$ iteration complexity in prior work under some technical assumptions.\n\n- 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. \n\n- The paper is well-organized. \n", "weaknesses": "**1. About the suboptimality gap \\delta_K and the $O(1/K)$ convergence rate**:  \nTheorem 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. \nI 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. \n\n**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. \n\n**3. Discussion of related works**: Some relevant related works are missing in the discussion. \n\n**(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. \n\n**(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. \n\n**(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).  \n\nFox et al. Independent natural policy gradient always converges in Markov potential games, AISTATS 2022.\n\nKhodadadian et al. On linear and super-linear convergence of Natural Policy Gradient algorithm,  Systems and Control letters 2022.  \n\nXiao. On the convergence rates of policy gradient methods. JMLR 2022\n\n**(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. \n\n**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. \n\n**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].   \n\n**6. Clarity**: Overall, writing can be substantially improved in my opinion. Few minor details below: \n\n— l. 108: what do you mean by ‘multiple stationary points for the problem’? Stationary points if the potential function?\n\n— l. 134-135: not very clear, see the ‘Questions’ section below. \n\n— 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.\n\n— 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?\n\n— 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. \n\n— 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? \n\n—  Lemma C.1: if rewards are vectors, please precise somewhere in notations that inequalities hold for all the entries of the vectors.  \n\n**Typos (main part and Appendix)**: \n l. 91: $V_i(s)$; do you mean $V_i^{\\pi}(s)$? \n\nl. 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$.\n \nl. 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.\n\nl. 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)?  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed assessment and constructive feedback on the paper, with both main paper and appendix. We are encouraged by the fact that the reviewer finds our paper \"well-organized\" with \"new and interesting analysis\". Our submission has been revised to include previously missing relevant works, fix typos and rephrase potential obscurities raised by the reviewer. We also address the reviewer's concerns and questions below and sincerely hope that the reviewer would consider increasing the score.\n\n> About $\\delta_K$ and rate... convergence is actually 'asymptotic'.\n\nA more detailed discussion on $\\delta^k, \\delta_K, \\delta^*$ is provided **in Authors' Response to All**. We will clarify the \"asymptotic\" property of results in abstract, contributions, and Table 1 in our final version.\n\n> Asm. 3.2 guarantees... hard to interpret although... standard quantity in the bandit literature....\n\nThe reviewer is correct that it is hard to guarantee a lower bound on $\\delta^k, \\forall k$. Therefore, we proposed the theoretical relaxation with Cor. 3.6.1 based on $\\delta^*$. **Please see the details in Authors' Response to All.**\n\nIn the bandit literature, the suboptimality gap indicates the structure of the environment. In the multi-agent setting, other agents can also be seen as part of environment w.r.t. a specific agent. Based on this intuition, we introduce this concept based on the marginalized reward and use Lem. 3.2 to capture the impact of $\\delta^k$.\n> Related works\n\nWe sincerely thank the reviewer for pointing out these previous works and we will include them in the final version.\n> Definition of MPGs\n\nOur formulation of MPG was originally adapted from that of [33, 34, R1, R2]. We consider this formulation to be well-known and somewhat standard in the literature. We will mention this difference in formulation with additional statements alongside Tab. 1 and Sec. 2.\n> Originality of the analysis\n\nWe thank the reviewer for acknowledgement of the novelty of our analysis in Lem. 3.2, B.3, and C.1. The proofs of Lem. A.1 and A.2 are similar to [4], but we arrive at different conclusions due to new lemmas (Lem. 3.2 and B.3) as bridges. The analysis of Lem. B.2 is related to [33] but with some key differences. Firstly, we provide a new Lem. B.1 to better explain the final equality in l. 476, which doesn't appear in [33]. Secondly, we use Young's inequality in l. 479 to save a $\\sqrt{n}$ factor compared with [33]. Nevertheless, we will make sure to mention these works while providing revised proofs of these lemmas.\n> Clarity\n- We use the definition of 'stationary point' from mathematics and optimization to denote a point with zero gradients. Incidentally, in our paper's context, the stationary point denotes a set of policies with zero policy gradients.\n- Yes, we used the 'set of policies' to denote a joint policy of product simplices. We will make sure to clarify at our first use of this specific term.\n- We meant the quantities defined in l. 153 and we will clarify it in the final version.\n- Yes, the definition of $f(\\infty)$ will be included in our updated draft.\n- Yes, $\\mathcal{R}\\_i$ is the set of reward functions with a particular structure. The ambient space is $\\mathbb{R}^{\\prod\\_{j=1}^n |\\mathcal{A}\\_j|}$. We wanted to provide a discussion over the structure of PGs in Lem. A.4 without further complicating other lemmas or theorems.\n- Here our intention was to show for a vector $\\mathbf{r} = [r_1, ..., r_n]$, where $r_1 > r_2 ... > r_n$. We will make sure to clarify this in our statements.\n\n> Typos\n\nWe thank the reviewer for the detailed evaluation of the paper. We will fix these typos in our final version.\n> 'isolated stationary policies’... as stated in Thm. 3.6 (and [33])... not stated in the theorem. How does the theorem guarantee that $c>0$?\n\nYes, this assumption is required. We will add it to the final version.\n> What do we mean by ‘stationary’ policies in this context? Although such a terminology is used in [33], it is not clear... has also another meaning for policies (time-independent).\n\nA stationary policy is what our paper describes as a 'stationary point', a set of policies that has zero policy gradients. In this sense, 'isolated stationary policy' means no other stationary points exist in an open neighborhood of any stationary point. We will add this clarification in the revision.\n> ... isn’t it possible to use the assumption to obtain corollary 3.6.1? ... would guarantee that Assumption 3.2 hold.\n\nThe mild Asm. 3.2 assumes the limit $\\delta^*$ is larger than 0, which is required by Cor. 3.6.1. It is not possible to only use \"stationary policies are isolated\" to obtain Cor. 3.6.1.\n\nA counter example would be a 2-by-2 matrix game with $r_{11} = 1, r_{12} = 1, r_{21} = 2, r_{22} = 1$, where one NE would be $\\pi_1 = (0, 1), \\pi_2 = (1, 0)$. In this example, we have an isolated stationary policy with $\\delta^* = 0.$\n> Precise definition of $\\pi_i^{*k}$?\n\nThe exact definition is that $\\pi_i^{*k} \\in \\arg\\max_{\\pi_i} V_i^{\\pi_i, \\pi_{-i}^k}(\\rho)$.\n\n> l. 153: why $f(\\eta)\\geq 0$?\n\nNPG updates $\\pi_i^{k+1}$ as follows: $\\pi_i^{k+1}(a_i|s) = \\arg\\max_{\\pi_i} \\eta \\langle \\bar{r}_i^k(\\cdot), \\pi_i(\\cdot) \\rangle - KL(\\pi_i || \\pi_i^k)$. Therefore, $f(\\eta) = \\sum_i \\langle \\bar{r}_i^k(\\cdot), \\pi_i^{k+1}(\\cdot) - \\pi_i^{k}(\\cdot) \\rangle \\geq \\sum_i KL(\\pi_i^{k+1} || \\pi_i^k) / \\eta \\geq 0$.\n> Extension to the stochastic setting:\n\nWe follow [33] and only consider the oracle setting in our analysis. In general, an oracle can be estimated by Monte Carlo or temporal difference methods for the stochastic setting and can be analyzed similarly as [1]. However, as mentioned by the reviewer, it is much harder to handle $c$ in the stochastic setting. We will add the above comment and mention the sample-based results in [8] in our final version. We leave the related analysis as future work.\n\n*For brevity, please see response to reviewers Qt2L and tti4 for referenced works.*"}]

Author rebuttal:

## Authors' Response to All (Discussion on $c$ and $\delta^*$):

We wholeheartedly thank all the reviewers for their time and their constructive feedback on our paper. The reviewers' comments provided us with great insights on how to increase clarity and reduce potential confusion about our paper. All the reviewers have raised similar concerns regarding our assumptions on $c > 0$ and $\delta^* > 0$ in the paper. Please note that reference numbers and line numbers are based on the supplementary material (MPG Main\&Appendix.pdf).

First, for simplicity, we recall the definitions of $c^k, c\_K, c$ and $\delta^k, \delta\_K, \delta^*$ in the potential game setting (Lines 154-157 in “MPG Main\&Appendix.pdf”). For agent $i$ at iteration $k$, define $a\_{i\_p}^k \in \arg\max\_{a\_j \in \mathcal{A}\_i} \bar{r}\_i^k(a\_{j}) =: \mathcal{A}\_{i\_p}^k$ and $a\_{i\_q}^k \in \arg\max\_{a\_j \in \mathcal{A}\_i\backslash \mathcal{A}\_{i\_p}^k} \bar{r}\_i^k(a\_{j})$, where $\mathcal{A}\_{i\_p}^k$ denotes the set of the best possible actions for agent $i$ in the current state and $\bar{r}\_i(a\_i) = \mathbb{E}\_{a\_{-i} \sim \pi\_{-i}}[r\_i(a\_i, a\_{-i})]$. We define

$$c^k := \min\_{i\in [n]} \sum\_{a\_j \in \mathcal{A}\_{i\_p}^k} \pi\_i^k(a\_j) \in (0, 1),\quad 
\delta^k  := \min\_{i \in [n]} [\bar{r}\_i^k(a\_{i\_p}^k) - \bar{r}\_i^k(a\_{i\_q}^k)] \in (0, 1). $$

Additionally, we denote
$c_K := \min_{ k\in[K]} c^k; c := \inf_{K \to \infty} c_K; \delta_K := \min_{k\in[K]}\delta^k, \delta^* := \lim_{k \to \infty} \delta^k$.

- The effect of $c$ was discussed in our submission at l. 175-183. Our exact definition of c is indeed the same as the $c$ defined in [33], with similar motivation and justifications. Combining Lemma 2 in [33] and Proposition 3.1 in this paper, $c^k$ asymptotically converges to 1. Since $c^k > 0$ for any softmax policy parameterization ($\pi_{i}^k(a_i|s) > 0$) and $c^k$ asymptotically converges to 1, we have $c := \inf_k c^k > 0$. This can also be observed in Fig. 1a in the original paper. Therefore, we believe our assumption on $c$ is mild and has been used within the same context in prior work.

- The introduction of the suboptimality gap $\delta^k$ enables us to draw a crucial connection between the difference in the potential function and the NE-gap using Lemma 3.2. As stated in Section 3.3, the best rate without this assumption is $O({1/\sqrt{K}})$.

	We would also like to justify our introduction of the suboptimality gap with reference to two separate lines of work. In single-agent RL, Khodadadian et al. [R1] proved asymptotic geometric convergence with the introduction of "optimal advantage function gap $\Delta^k$". $\Delta^k$ is very similar to our definition of $\delta^k$. Additionally, the notion of suboptimality gap, though different in formulation, is commonly used in the multi-armed bandit literature [R2]. In both works, the introduction of a suboptimality gap greatly benefits the analysis. It also serves a similar purpose in our work.

	We agree with the reviewers that requiring $\delta^k > 0$ to hold for all iteration $k$ is indeed restrictive. However, we found that occasional $\delta^k \approx 0$ does not affect the global convergence rate. Motivated by this observation, we have proposed a theoretical relaxation with Cor. 3.6.1. Instead of requiring the suboptimality gap to be always non-zero, we only require the limit (existence of a limit is due to asymptotic convergence guarantee in [33]) to be non-zero (Assumption 3.2), which is far from restrictive. Recalling our definition in Eq. (6), the suboptimality gap is defined as the performance gap between the best and second-best classes of actions. Having a zero suboptimality gap implies that all actions of one agent belong to one class with the exact same expected reward values, which implies a zero NE-gap for the specific client.

Moreover, we provide more experiments regarding special scenarios in MPGs in the attached pdf file as requested by Reviewer tti4.

We will revise and rephrase the related statements in order to reduce the potential confusion to readers in the final version. Additionally, we will incorporate valuable suggestions concerning other related literature, and correct the typos and notation errors pointed out by various reviewers.

[33] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35:1923–1935, 2022.

[R1] Khodadadian, Sajad, et al. "On linear and super-linear convergence of Natural Policy Gradient algorithm." Systems \& Control Letters 164 (2022): 105214.

[R2] Lattimore, T. and Szepesvári, C., 2020. Bandit algorithms. Cambridge University Press.



Meta-review: The paper established fast convergence of independent natural policy gradient for MARL in Markov potential games. The technical contribution is solid and has been unanimously acknowledged by the reviews (and I concur). Please make sure to address all the comments in preparing the final version of the paper.
Decision: Accept (poster)