{'fraction_non_alphanumeric': 0.04984872837288456, 'fraction_numerical': 0.012125366360971921, 'mean_word_length': 4.340696793738955, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games

Softmax policy gradient is a popular algorithm for policy optimization in single-agent reinforcement learning, particularly since projection is not needed for each gradient update. However, in multi-agent systems, the lack of central coordination introduces signiﬁcant additional difﬁculties in the convergence analysis. Even for a stochastic game with identical interest, there can be multiple Nash Equilibria (NEs), which disables proof techniques that rely on the existence of a unique global optimum. Moreover, the softmax parameterization introduces non-NE policies with zero gradient, making it difﬁcult for gradient-based algorithms in seeking NEs. In this paper, we study the ﬁnite time convergence of decentralized softmax gradient play in a special form of game, Markov Potential Games (MPGs), which includes the identical interest game as a special case. We investigate both gradient play and natural gradient play, with and without log -barrier regularization. The established convergence rates for the unregularized cases contain a trajectory dependent constant that can be arbitrarily large , whereas the log -barrier regularization overcomes this drawback, with the cost of slightly worse dependence on other factors such as the action set size. An empirical study on an identical interest matrix game conﬁrms the theoretical ﬁndings.


Introduction
Multi-agent systems encounter vast application in real world scenarios, such as network routing [35,8], social and economic decision making [36,30], and robotic swarms [22,14]. In these problems, a system consists of a group of agents interacting in a shared environment. Given the recent success of reinforcement learning (RL), increasing attention has been drawn to the possibility of applying RL algorithms, such as policy gradient, to multi-agent systems. However, the theoretical foundations for multi-agent reinforcement learning (MARL) remain limited. Unlike single-agent RL, the actions of other agents affect the dynamics and the decision making outcome for each individual in the system, raising additional theoretical challenges when analyzing joint performance.
The stochastic game (SG) is a classical multi-agent model that has received extensive attention in recent MARL studies. In a stochastic game, the environment is represented by a state space that evolves based on the joint actions of agents. Each agent in a stochastic game tries to maximize its own total reward by making decisions independently, based on state information shared between agents. The stochastic game model was first introduced in [31], with a series of followup works proposing NE-seeking algorithms, particularly in the RL setting (e.g. [21,5,32,6,17,38] and citations therein). Given recent progress in the underlying theory of RL, many recent works have investigated finite time iteration and sample complexity for learning NE or other general equilibria notions, such as correlated and coarse correlated equilibria (e.g. [33]).
There are different types of SGs, some with attributes that merit special attention; for example, two-player zero sum games [4,9], which are widely used to model two player competitive games such as GO. In this paper, we will focus on another type of SG, the Markov potential game (MPG) [23,27,39,18], which includes the identical interest game as a special case. The structure of a MPG enables efficient learning through the use of gradient-based algorithms such as gradient play. Recent work [39,18] has focused on the iteration and sample complexity of finding a NE in an MPG under the direct policy parameterization, which is not practical in most real world scenarios, given the cost of projecting back to the probability simplex on every iteration. This drawback has motivated consideration of the softmax parameterization, which bypasses the projection step in the gradient update, and is perhaps the most popular approach to parameterizing policies in practice. [11] have studied natural gradient play for MPG under softmax parameterization, but only address asymptotic behavior and leave finite time complexity open.
From the perspective of analysis and practical performance, the extension from the direct to the softmax parameterization in policies is nontrivial. Even in the single agent case, as shown by [2,24], there are policies in the softmax parameterization that have near-zero gradient and yet are far from being globally optimal, which creates difficulty for a gradient-based algorithm to escape suboptimal points. A similar issue exists for MPGs: due to the more complex interaction between agents, there is even a greater set of policies that obtain small gradient norm but are far from a NE. Based on our analysis and numerical results, even for natural gradient play-which is known to enjoy dimension free convergence in single agent learning [2]-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 [29,3] is not sufficient to ensure fast convergence in multi-agent learning. A stronger form of regularization is required, which motivates the introduction of log-barrier regularization to avoid undesirable regions of policy space.
Our contribution: In this paper, we provide finite time iteration complexity results for gradient play and natural gradient play under the softmax parameterization, considering both unregularized and log-barrier regularized dynamics. We summarize the convergence rates and compare them to existing results for the direct parameterization and to the corresponding single agent cases in Table 1.
These findings suggest that regularization is crucial for obtaining fast convergence to a NE under the softmax parameterization in a MPG. In Table 1, the results for the two unregularized algorithms in the multi-agent case rely on the assumption that the set of stationary policies is isolated (which is also assumed in [11] when establishing the asymptotical convergence for natural policy gradient), and the corresponding complexity bounds contain an initialization dependent factor c. By contrast, the log-barrier regularized algorithms overcome both drawbacks, but as a tradeoff, their bounds incur a slightly worse dependence on |A i | and M . We observe numerically that the log-barrier regularized algorithms are indeed more robust against becoming trapped near undesirable non-NE stationary points. To the best of our knowledge, the finite-time iteration complexity results are the first such results for MPGs under the softmax parameterization. Though the analysis for the gradient play follows their single-agent counterparts [2,24], the results for natural gradient play are highly non-trivial, requiring very different analysis tools which have their own merits to the literature (see Remark 2 and Remark 3 for more details on the technical novelty in the analysis). Our results also convey the following two messages. First, finding the NE of a multi-agent MPG is harder than finding the global optimum for the single-agent case, because multi-agent learning suffers greater risk of becoming trapped near undesirable stationary points. This is reflected in the dependence of the complexity bounds on in Table 1. Second, natural gradient play outperforms gradient play counterparts, suggesting that natural gradient play captures useful information about the geometry of the parameter space that accelerates the learning process.

Problem settings
We consider an infinite time horizon n-agent stochastic game (SG, [31]) M = (N, S, A = A 1 × . . . × A n , P, r = (r 1 ,. . . ,r n ), γ, ρ) which is specified by an agent set N = {1, 2, . . . , n}, a finite state space S, a finite action space A i for each agent i ∈ N , a transition model P (such that P (s |s, a) = P (s |s, a 1 , . . . , a n ) is the probability of transitioning into state s upon taking action a := (a 1 , . . . , a n ) in state s where a i ∈ A i is action of agent i), a reward function r i : S ×A → [0, 1] for each agent i, a discount factor γ ∈ [0, 1), and an initial state distribution ρ over S. We use s(t) ∈ S to denote the state at time step t, and a(t) = (a 1 (t), . . . , a n (t)) ∈ A to denote the total action.
A stochastic policy π : S → ∆(A) (where ∆(A) is the probability simplex over A) specifies a strategy, where agents choose their actions jointly based on the current state in a stochastic fashion; i.e. Pr(a(t)|s(t)) = π(a(t)|s(t)). A decentralized stochastic policy is a special subclass of stochastic policies with π = π 1 × . . . × π n , such that π i : S → ∆(A i ), where π i is agent i's own local policy. For decentralized stochastic policies, each agent takes its action based on the current state s independently of other agents' action choices; i.e., Pr(a(t)|s(t)) = π(a(t)|s(t)) = n i=1 π i (a i (t)|s(t)). For notation simplicity, we define π I (a I |s):= i∈I π i (a i |s), where I ⊆ N is an index set. Further, we use the notation −i to denote the index set N \{i}. In this paper we focus on tabular softmax parameterization for a policy, where policy π θ = (π θ1 , . . . , π θn ) is parameterized by a set of parameters θ = (θ 1 , . . . , θ n ), with θ i = {θ s,ai } s∈S,ai∈Ai , and where π θi (a i |s) = exp (θ s,ai ) We denote agent i's total reward starting from initial states s(0) ∼ ρ as: ) Further, we define the 'NE-gap' of a policy θ to be: A policy θ is an -Nash equilibrium if: NE-gap(θ) ≤ .
We define the value function with respect to stage cost r i as: , a(t)) π θ , s(0) = s .
We define agent i's Q-function and advantage function Q θ i , A θ i : S × A → R, Q θ i (s, a) := E We further define agent i's 'averaged' Q-function Q θ i : S × A i → R and 'averaged' advantagefunction A θ i : S × A i → R as: Finally, define the discounted state visitation distribution d θ of a policy π θ given an initial state distribution ρ as: where Pr θ (s(t) = s|s(0)) is the state visitation probability that s(t) = s when executing π θ starting at state s(0). From the policy gradient theorem [34], we have that (proof given in Appendix 9): For the remainder of the paper, we make the following assumptions on the stochastic games we study. Assumption 1. The stochastic game M satisfies: inf θ min s∈S d θ (s) > 0.
Assumption 1 requires that every state is visited with positive probability for any policy, which is a standard assumption for convergence proofs in the RL literature (e.g. [2,24]). We will use M to denote the following quantity Note that M can be viewed as a measure of exploration sufficiency in the stochastic game, which is slightly different from the "distributional mismatch coefficient" introduced in [2] defined by sup θ,θ max s d θ (s) d θ (s) ; however, both can be upper bounded by max s 1 (1−γ)ρ(s) . We primarily focus on the following subclass of stochastic games in this paper: Definition 2. A stochastic game is called a Markov potential game (MPG,[37,23,39,18,26]) if there exists a potential function φ : S × A 1 × · · · × A n → R such that for any agent i and any pair of policy parameters , a(t)) π = (θi, θ−i), s(0) = s , ∀ s. (6) Without loss of generality, we assume that φ min ≤ φ(s, a) ≤ φ max for all (s, a). The definition of MPG is a generalization of the notion potential game in the one-shot setting [28]. Note that identical reward game where agents share a same reward function naturally satisfies the above condition and serves as one important special case of MPG. For non-identical reward settings, [23,12] found that continuous MPGs can model applications such as the great fish war [19], the stochastic lake game [10], medium access control [23] etc. For tablular MPGs, [39,18] also discuss necessary/sufficient conditions that implies a MPG, as well as its application and counterexamples.
Given a MPG, we define the total potential function Φ as: Given the property in (6), it is straightforward to verify that the NE condition (2) is equivalent to Remark 1 (Differences between MPG and single-agent/centralized MDP). Because of the existence of the total potential function Φ, it is natural to ask whether MPG renders the multi-agent policy gradient similar to single agent policy gradient and thus results and analysis tools developed for single agent policy gradient in e.g., [2,24] would be easily extended to the multiagent case. Unfortunately, this is not the case. To illustrate how it differs from single-agent/centralized case, we can focus on the special type of MPGs where every agent has the same reward function, namely the identical interest case. In the single agent/centralized case, there is a unique global optimal solution which corresponds to the convergent stationary policy. However, in the multiagent case, even if the rewards are identical, because the policy is decentralized, i.e., agents taking independent policies π := π 1 × . . . × π n , we loose the connection between stationary policies and optimal policies. As we shown later, the convergent stationary policies are Nash equilibria, which are unfortunately non-unique even for the identical interest case. Moreover, a key condition that is used in establishing the convergence rate, Łojasiewicz condition (Lemma 1), is also much weaker for the multiagent case compared to single agent [24]: the left hand side is the Nash gap max i,θ * i Φ(θ * i , θ −i ) − Φ(θ) instead of the optimality gap max θ * Φ(θ * ) − Φ(θ)). Note that zero Nash gap does not imply zero optimality gap, as there exists many NEs of different values. These differences disable many proof technique used for single agent case and make the analysis harder and lead to different performance results, as demonstrated in the rest of the paper.
3 Relationship between first order stationary point and Nash equilibrium Before studying convergence performance of gradient play algorithms, it is important to first understand the relationship between the stationary points and the NEs. Unfortunately, equivalence cannot be established in this setting. Standard optimization theory guarantees that all NEs are stationary points, but unfortunately not vice versa. Under softmax parameterization, there exist non-NE stationary points. For example, from the gradient formulation (4), it can be shown that any non-NE deterministic policies are also stationary points. However, the notion of NE and stationarity are indeed closely related. This section aims to characterize some differences between NE and non-NE stationary points. This differentiation of the NE and non-NE stationary points is established by the non-uniform Łojasiewicz condition (also known as gradient domination) for stochastic games.
Then we have that The Łojasiewicz condition (gradient domination) implies that the NE-gap of a policy can be bounded by the norm of its gradient, whereas the term 'non-uniform' refers to the factor , which cannot be bounded uniformly for all θ. The counterpart of Lemma 1 for a single-agent MDP was first introduced in [24, Lemma 8]. One major difference between Lemma 1 and [24, Lemma 8] is how c(θ) is defined. In [24], c(θ) := min s π θ (a * (s)|s), where a * (s) is the optimal action on state s (i.e., a * = argmax a Q * (s, a)), whereas in MPG, because there's no globally defined Q * , the a * i in (7) is chosen as the greedy optimal action of the current averaged Q-function (i.e., a * i ∈ argmax ai Q θ i (s, a i )). Note that because c(θ) on the denominator can be zero for certain policies (e.g. one can verify that any non-NE deterministic policy have c(θ) = 0), which implies that a θ with gradient norm close to zero is not necessarily near a NE. Given this observation, we could differentiate the non-NE stationary points with NEs by whether c(θ * ) equals to zero, which is formally stated in the following lemma:

Unregularized gradient play
We first investigate the convergence to NE for gradient and natural gradient play, respectively. Under the softmax parameterization, the two schemes are given by Natural Gradient Play: θ where † denotes the Moore-Penrose inverse and F i (θ) is the Fisher information matrix for π θi : F i (θ) := E s∼d θ (·) E ai∼π θ i (·|s) ∇ θi log π θi (a i |s)∇ θi log π θ (a i |s) .
For notational simplicity, we abbreviate the variables d i and A (t) i respectively; and denote π θ (t) (a|s) and π θ (t) i (a i |s) as π (t) (a|s) and π (t) i (a i |s) respectively. For the softmax parameterization, we can establish the equivalence of natural gradient play and soft Q-learning [13], formally stated in the following lemma. Lemma 3. (Proof given in Appendix 10) Natural gradient play is equivalent to Asymptotic convergence to Nash Equilibrium. As stated in Section 3, there exist stationary points that are not NEs. It is not immediately obvious why running gradient methods can avoid converging to these points, thus before studying convergence rate to NE, it is necessary to first examine whether asymptotic convergence holds. Moreover, the asymptotic convergence result is used to establish the finite time convergence rate results later (see the subsection 4.1). Theorem 4. (Proof given in Appendix 12) Suppose Assumption 1 holds and that the stationary policies are isolated, gradient play is a NE. The same argument also holds for natural gradient play (10) with η ≤ The proof of Theorem 4 resembles the technique used in [2] for the single agent case, where the additional assumption on the isolated stationary policies is introduced due to some specific technical difficulties encountered in multi-agent learning (see more discussion in Appendix 12, which is also introduced in [11] for establishing the asymptotic convergence of NPG. We believe it is a conservative condition for ensuring the asymptotic convergence. It remains an interesting open question to establish convergence without this assumption.

Finite time convergence rate
This section considers finite time convergence rate for gradient play and natural gradient play.
Corresponding results for the single-agent setting can be found in [24] (for gradient play) and [2,16,25] (for natural gradient play). Some aspects of these analyses can be carried over to the multiagent MPG setting; however, as will be discussed later, there are several fundamental differences that make the multi-agent case more challenging.
Our convergence results rely on the observation from Section 3 and the asymptotic convergence to NE. Combining Theorem 4 and Lemma 2, we know that c(θ (t) ) asymptotically converges to 1 for (natural) gradient play, and since c(θ (t) ) > 0 for any softmax policy (because π θi (a i |s) > 0), We are now ready to give formal convergence rates for gradient and natural gradient play respectively. Theorem 5. (Gradient play and natural gradient play; proof given in 13) Suppose Assumption 1 holds and that the stationary policies are isolated, gradient play will guarantee that for all T , Natural gradient play (10) with η = 2n(φmax−φmin) will guarantee that for all T , Here O(·) hides constant factors, M and c are defined as in (5) and (11), respectively.
Remark 2 (Proof sketch and novelty). The proof for gradient play is relatively straightforward from the non-uniform Łojasiewicz inequality and standard non-convex optimization results, which we refer readers to the appendix for more details. However, the proof for natural gradient play is more involved and existing analysis on NPG cannot be generalized to this setting. For single-agent MDP, the analysis on NPG leverages the unique existence of optimal value function V * so that similar analysis for mirror-descent can also carry over to NPG analysis, and thus obtain dimension free convergence. However, in the multi-agent setting, there's no well-defined V * as NEs can be non-unique with different potential values, thus, we need to further deploy additional structures of the total potential function Φ. Our analysis rely on the sufficient ascent lemma (Lemma 20) that lower bounds the ascent amount Φ(θ (t+1) ) − Φ(θ (t) ) for each natural gradient step (we would like to further note that this sufficient ascent lemma cannot be trivially obtained by the smoothness of Φ). Then, we further lower bound the ascent amount in terms of NE-gap (Lemma 21). Lastly, the theorem follows by conducting standard telescoping techniques.
Discussion on 1 c : The complexity results in Theorem 5 both depend on 1 c . However, this term can become arbitrarily large. In fact, [20] show that c can be exponentially small in terms of the number of states |S| for a general finite MDP, even under uniform initialization, hence convergence can be very slow. This conclusion is also confirmed by numerical evidence. As pointed out by [24], even for single agent settings, policy gradient can get stuck at regions with small gradient yet far from being global optimal. Similar or even worse phenomena can be observed for multi-agent MPG, as shown in Figure 1 to find an -NE, whereas [24] show a to reach an -global optimum for policy gradient in a single agent MDP. The dependence on 1 is better in the single agent case because of the existence of a global optimal policy π * and optimal total reward V * , which justify the definition of optimality gap δ t = V (θ (t) ) − V * . This, combined with the non-uniform Łojasiewicz condition which bounds δ t by the gradient norm, allows one to use techniques from convex smooth analysis to show that δ t is on the scale of 1 t . By contrast, for multi-agent learning, there can be multiple NEs with different values, hence δ t is ill-defined. Further, note that the NE-gap is different from the optimality gap, hence gradient ascent no longer guarantees monotonic decreasing of NE-gap (Figure 1(a)), and we can only exploit non-convex optimization techniques that yield O( 1 2 ) complexities. For the same reason, the rate of convergence we obtain for natural gradient play is , which is worse than the dimension free convergence rate of O given in [2] for single-agent MDPs. (A better exponential convergence rate for natural PG has also been proved in [16,25] with the exponential factor being problem dependent.) Nevertheless, the dependence on 1 c , 1 1−γ and M is better than gradient play, suggesting that the preconditioning of natural gradient play at least partially captures the geometry of the parameter space. We also note that the quadratic dependence on (φ max − φ min ) might be a proof artifact. It remains an open question whether this can be reduced to a linear dependence.

Gradient play with log-barrier regularization
The previous section has shown that, for unregularized objectives, the convergence rate for gradient based algorithms depends on a factor 1 c that can be arbitrarily large for bad initializations. This motivates us to investigate regularization, in hopes of removing the dependence on 1 c . For this purpose, we consider log-barrier regularization: Define: It is not hard to verify that the gradient with respect to J i is: Discussion on the choice of the regularizer: Before analyzing the resulting algorithm we first discuss the motivation for this regularizer. First, note that for each agent, the additional regularizer only depends on an agent's own local policy, which is desirable for multiagent RL. As an alternative, one might impose regularization by choosing ai log π θi (a i |s); i.e., so that the regularization weight imposed on a state s depends on the state visitation probability d θ (s). However, in this case the gradient of the i-th agent ∇ θi Φ(θ) will not only depend on its own policy parameter θ i , but also on other parameters of the other agents' policies θ −i . Thus, running gradient based algorithms with such a regularization scheme can no longer be executed in a fully decentralized manner using local policy information. Therefore, we prefer regularization (14) which does not depend on d θ (s). Secondly, we adopt the log-barrier instead of entropy regularization due to technical rather than practical considerations. Although entropy regularization achieves fast exponential convergence in single agent learning [7,24], for multi-agent learning, we haven't been able to obtain results as strong as the log-barrier regularization. Intuitively, the log-barrier regularized gradient field repels the trajectory from regions with small π i (a i |s) values (where the geometry becomes close to singular) more strongly, which enables us to obtain our current analysis. However, we emphasize that our result does not imply that log-barrier is better than entropy regularization in practice. It remains future work to determine whether entropy regularization, or other methods such as trust region based methods, can achieve the same, or even better convergence rates.

Gradient play
We first consider gradient play algorithm, i.e., Fortunately, similar analysis from [2] for single-agent MDP can be generalized to MPG with slight modifications. Here we only state the result and defer the proof to Appendix 14.1. (1−γ) 4 2 will guarantee that min 0≤t≤T −1 NE-gap(θ (t) ) ≤ .
Note that compared to the unregularized case in Theorem 5, it only requires Assumption 1, while the convergence rate is accelerated by eliminating the dependence on 1 c . However, as a (worthy) tradeoff, the dependence on the action space size max i |A i | now becomes quadratic. The key reason for these differences is that log-barrier regularization assures that any policy with sufficiently small gradient norm cannot be close to the boundary of the probability simplex where the non-uniform Łojasiewicz constant is large.

Natural gradient play
In the unregularized setting, we have seen that natural gradient play enjoys a better convergence rate than gradient play, which motivates us to consider whether a similar advantage still holds for the regularized case. In this section we consider natural gradient play which is equivalent to (see the proof in Appendix 10) Theorem 7. (Proof given in Appendix 14. 2) Under Assumption 1, for , the natural gradient play (17) Figure 1: We consider a two-player identical reward matrix game as shown in the reward table. We run gradient play and natural gradient play (with and without log-barrier regularization) with initial policies being the uniform distribution (i.e., π1 (7)) and Φ(θ (t) ) change with each iteration respectively. In Figure (c), we zoom in on the log 10 c(θ) factor for natural gradient play. In Figure (d), we also zoom out the trajectory for running gradient play to iteration 2 × 10 4 . Here the step sizes were chosen to be η = 5 while the regularization weight λ was chosen to be λ = 0.003. In consideration of numerical stability issues, we truncate the update step of natural gradient play with log-barrier regularization by a maximum absolute value of 1 for each entry. For more numerical results and corresponding analysis see Appendix 8. will guarantee that Remark 3. (Proof sketch and novelty) As also stated for unregularized natural gradient play, there's no direct analysis tools we could borrow from literature for the analysis of natural gradient play. Our analysis depends on two key lemmas. The first is a sufficient ascent lemma on Φ(θ (t+1) ) − Φ(θ (t) ) for each natural gradient step (Lemma 26). Another key lemma (Lemma 24) states that the algorithm implicitly ensures that the policies never go near the boundary of the probability simplex, i.e., it can be uniformly lower-bounded by π , ∀t. Combining the two lemmas, it can be concluded that the ascent value Φ(θ (t+1) ) − Φ(θ (t) ) can be bounded by NE-gap(θ (t) ) plus a λ max i |A i |M bias term (Lemma 27 and 28), thus the proof is finished by standard telescoping technique and choosing an appropriate λ.
Compared with gradient play, natural gradient play manages to reduce the time complexity by a max i |A i | factor. Further, gradient play only guarantees the minimal NE-gap smaller than , while natural gradient play guarantees the average NE-gap along the trajectory smaller than . To the best of our knowledge, this is the best time complexity bound for the softmax parameterization in a MPG.

An Illustrative example
This section aims to gain a better understanding of the four gradient play algorithms, (8), (10), (15), and (17). To better justify our theoretical results and provide additional insights, we choose a carefully designed simple two-player game so that our theoretical results can be easily revealed from the empirical observations. However the four algorithms also works for settings with more agents. 1 Due to space limits, we defer the simulation with more agents in Appendix 8.
The reward table as well as the performance of the four algorithms are shown in Figure 1. Comparing the log-barrier regularized algorithms to the unregularized counterparts, one can see that the regularized dynamics converge faster but with a bias induced by the regularizer. This finding corroborates the analyses given in Theorem 6 and 7. By contrast, the unregularized dynamics are able to find a policy with zero NE-gap asymptotically, but tend to get stuck in regions where c(θ (t) ) is very close to zero, as illustrated in Fig 1(a)(b). Specifically unregularized natural gradient play gets stuck around iteration 100-400 in a region where the gradient norm and c(θ (t) ) are both close to zero while the NE-gap is not. This corroborates the finding in Lemma 1. Similar behavior can be observed for gradient play if we keep running the algorithm. In comparing the natural gradient play to gradient play algorithms, natural gradient play generally converges faster, which matches with our complexity analysis. However, natural gradient play with log-barrier regularization can suffer from numerical instability due to the 1/π (t) i (a i |s) term in the exponential factor. In this case, the stepsize needs to be chosen carefully. To bypass the numerical instability, we truncate the update step of natural gradient play with log-barrier regularization by a maximum absolute value of 1 for each entry.

Discussions and conclusions
We have established finite time iteration complexity bounds for gradient and natural gradient play under the softmax parameterization, considering both unregularized and log-barrier regularized dynamics, in the Markov potential game setting. To our best knowledge, these are the first finite time global convergence results for softmax gradient play for MPGs. However, our work suffers from the following limitations: firstly, the paper mainly focuses on MPG settings, which limits its application to general-sum Markov games; secondly, convergence results for the unregularized case relies on an extra assumption that the stationary points are isolated; thirdly, for the regularized case, we consider log-barrier regularization, which is admittedly a stronger regularization compared with entropy regularization which is more frequently used in practice. Some limitations are due to technical challenges, some might be caused by the fundamental difficulties of multi-agent learning. It remains interesting open questions to sharpen the analysis, derive similar or better bounds for other regularizations, and to develop more fundamental understandings of multi-agent learning.

Numerical Simulations
This section provides more material for the numerical example shown in Section 6. Figure ?? displays numerical performance for different initialization policies. All four algorithms perform well given a good initialization, i.e., initial policy close to a stable NE. However for bad initialization that is close to a non-NE stationary point, log-barrier regularized algorithms can escape bad regions and converge to NE much faster than unregularized dynamics.
To examine why multi-agent learning suffers more from getting stuck at undesirable stationary points, we plot out the trajectory for Q i (a i ) for both agents in Figure ??. We will mainly focus our attention on the two plots on the left. Note that for the first few steps, Q    a 1 = 2). Unfortunately, at this stage, most of the probability is assigned to the suboptimal action a 1 = 2 and the optimal action receives π (t) 1 (a 1 = 3) close to zero. Thus it will take more steps to bring π (t) 1 (a 1 = 2) from 1 to 0 and π (t) 1 (a 1 = 3) from 0 to 1, which reflects as the trajectory being stuck at the non-NE stationary policy with π 1 (a 1 = 3) = 1 in numerical behavior. From this simulation, we may conclude that one important reason for natural gradient play to get stuck at undesirable stationary points is due to the fact that the value of averaged Q-functions Q (t) i 's for different actions might switch order during the learning process. In contrast, for single agent bandit learning, the averaged Q-function as well as the Qfunction itself is the same as the reward value of a certain action r(a), and thus will not change order, which explains why it can achieve dimension free convergence in single agent learning. Additionally, we would like to remark that the algorithms considered in this paper also generalizes to settings with more agents, and similar phenomenon will still be observed. See Figure 2 and 3 for numerical simulations on a 3-agent example and an 8-agent example.
Running trajectories for all the four algorithms for one set of initializations takes approximately 2.04 seconds of CPU running time (Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz 1.80 GHz).

Derivation of Gradient and Performance Difference Lemma
Since for softmax parameterization: Thus we have that: We also introduce a useful lemma used throughout the proof which is derived from the performance difference lemma in MDP [15].
Proof. From performance difference lemma [15] J 10 Derivation of Natural Gradient Play Lemma 9.
Proof. Calculating the gradient using chain rule we have ∂ log π θi (a i |s) ∂θ a i ,s = 1{a i = a i } − π θi (a i |s).
Proof. Since F i (θ) is a block diagonal matrix, From Lemma 9, since F i,s only has a one-dimensional eigenspace for eigenvalue 0, and the eigenspace is the span of the all-one vector 1, we have that i.e., i.e., which completes the proof.

Proof. It is not hard to check that
thus we can apply Lemma 11 and conclude which completes the proof.
Proof. From performance difference lemma Thus we have that Proof of Lemma 1. From Lemma 13 we have that

Remark 4. A similar bound to Lemma 1 can be obtained by leveraging equation (259) in [24]
Notice that there's an additional √ S dependency on the right hand side compared with Lemma 1, while replacing the term M (θ) by D ∞ . We remark that there's no fundamental difference between these two bounds. There's no significant difference in the proof techniques and it is hard to tell which one is better. One can also easily re-derive the set of analysis in the paper using (18), with bounds that depends on D ∞ instead of M and slightly differs in the dependency on S from our current result.
Proof of Lemma 2. Firstly, it is straightforward to see that if c(θ * ) = 0, θ * is a NE by applying Lemma 1. So we only need to focus on proving that if θ * is a NE, then c(θ * ) = 1.
which proves the monotonicity of Φ(θ (t) ). Since φ is a bounded function, this gives: From Lemma 14 and that the stationary points are isolated, we know that the limit for θ (t) exists, i.e., it is valid to define θ (∞) := lim t→+∞ θ (t) .
We abbreviate the related functions with respect to θ (∞) as follows: Since θ (∞) is the limit of θ (t) , we have that: Define: From Lemma 13, it is sufficient to show that I i,s + = ∅, ∀ i, s. From the Lemma 14 and the above definitions we have the following corollaries: Corollary 15. There exists T 1 , such that ∀t > T 1 , ∀s ∈ S, ∀i ∈ {1, 2, . . . , n}, Proof. This is a direct corollary from (19) and (20).
Proof. This is a direct corollary from Lemma 14, i (a i |s) = 1 Proof. The first statement, ∀a i ∈ I i,s + , θ (t) s,ai is bounded from below, is trivial from Corollary 15. We only need to prove the second statement. The key observation is that: From Corollary 16, we have that s,ai sum up to a constant and that ∀a i ∈ I i,s s,ai is bounded from below, we have that: From Corollary 15, for s,ai is monotonically decreasing for t > T 1 , thus s,ai is either a constant or −∞. We'll prove by contradiction. Suppose θ s,ai is a constant, then for any δ > 0 there exists Let a i ∈ A i be defined as in (21), define: We will focus on the set where {t|τ (t) ≤ t}. Since lim inf t→+∞ θ For all τ (t) ≤ τ ≤ t, we have that: Since: θ is bounded from below, and that θ τ (t) s,ai is also bounded from above by θ (T1) s,ai , thus taking lim inf t→+∞ on both sides of eq (22) will give s,ai is a constant, and thus we can conclude that Proof. We will prove by induction. Suppose for a certain τ ≥ t, it holds that π i (a + i |s), then:
Proof. We will prove by contradiction. If I i,s + = ∅, select an arbitrary a + i ∈ I i,s + and define From Lemma 17, we have that for any a i ∈ I i,s − lim t→+∞ Additionally, since for any a i ∈ I i,s 0 , lim t→+∞ A (t) i (s, a i ) = 0, there exists T 3 > T 1 such that for any t ≥ T 3 , Thus, for t ≥ max{T 2 , T 3 }, from the fact that ai π i (s, a i ) = 0, we have: Thus for t ≥ max{T 2 , T 3 }, which leads to the fact that ai∈I i,s s,ai is bounded from above. Further, from Lemma 17, θ (t) s,a + i is bounded from below, thus the value i |s) is bounded from above. However from Corollary 16, which contradicts the fact that i (a + i |s), ∀a i ∈ B i,s 0 (a + i ) and finishes the proof by contradiction.
Lemma 19 directly implies asymptotic convergence for gradient play as state in Theorem 4. Remark 5. (Discussion on the isolated stationary points assumption) The proof of Theorem 4 resembles the technique used in [2] for the single agent case, which relies heavily on the fact that the sequence of Q-functions Q (t) (s, a) obtains a limit Q (∞) (s, a). The existence of such a limit in the single agent case follows from the monotonicity of the Q-functions. However, generalizing this proof to the multi-agent case requires the assumption that the sequence of averaged Q-functions Q (t) i (s, a i ) (which can be non-monotonic, see, e.g., Figure ?? in Appendix) has a limit Q (∞) i (s, a i ), which is not necessarily true in general. For instance, if the set of stationary policies SP := π : π i (a i |s)A π i (s, a i ) = 0, ∀s ∈ S, a i ∈ A, i = 1,2,. . .,n is not isolated, one cannot rule out the possibility that (natural) gradient play will not converge to a fixed point π (∞) (see e.g. [1] for counterexamples). Consequently, Q (t) i (s, a i ) might not converge to a single value. For the above reasons, we assume the stationary policies are isolated to ensure that π (t) converges to a fixed stationary policy π (∞) and thus Q (t) i (s, a i ) obtains a limit. We believe that this assumption is a conservative condition that is sufficient to imply asymptotic convergence. It remains an interesting open question to establish convergence without this assumption.

Asymptotic convergence for natural gradient play
The asymptotic convergence for natural gradient play is easier to establish compared with gradient play.
From Lemma 20 and the assumption that φ(s, a) is upper-bounded, we know for |x| ≤ 1) Similar to the proof for gradient play, from the assumption that stationary points are isolated, we can conclude that π (t) converges to some stationary policy π (∞) , and we can define Asymptotic convergence is equivalent to We prove by contradiction. Suppose there exists a + i such that A Select a 0 i such that lim t→+∞ π Thus from natural gradient play scheme (10) , which contradict the fact that lim t→+∞ = 0, and thus completes the proof.
13 Proof of Theorem 5 13.1 Proof of Theorem 5 (Gradient play part) Proof of Theorem 5, gradient play. From Lemma 29, Φ is β-smooth with β = 6n (1−γ) 3 , we have that: Summing over t we get: From Theorem 1 we have that which completes the proof.
13.2 Proof of Theorem 5 (Natural gradient play part) 2n(φmax−φmin) , running scheme (10) will guarantee that where Z i,s t is defined by Proof. From performance difference lemma we have that We define Then i,φ (s, a i ) .
From scheme (10), i (a i |s) Substitute this into Part A, we have i (a i |s) Further, we have that j,s 1 . Thus which completes the proof.
Proof. From Lemma 13 we have that NE-gap(θ) ≤ 1 1−γ max i max s,ai A θ i (s, a i ). On the other hand, We are now ready to prove the bound for natural gradient play in Theorem 5.
Proof of Theorem 5, natural gradient play. Combining Lemma 20 and 21 we have Summing over t we have which completes the proof.
14 Proof for log-barrier regularization 14.1 Proof of Theorem 6 We start with the following lemma: Lemma 22 implies that any policy with gradient norm smaller than λ is also a λM max i |A i |-NE. Thus by properly choosing λ, agents can find a -NE by running gradient play.
We now prove Theorem 6.
Proof of Theorem 6. From Lemma 30, Φ is β-smooth with β = 6n (1−γ) 3 + 2λ max i |A i |, we have that: For θ (0) = 0, summing over t we get: Thus for it can be guaranteed that Then applying Lemma 22 completes the proof.

Proof of Theorem 7
For notational simplicity, we define the following variables: Proof. From the definition of f i (a i |s) = 1 − 1 = 0 Using the fact that e x ≥ 1 + x, , θ (0) = 0, running scheme (17) will guarantee that Proof. We will prove by induction. For θ 0 = 0 apparently π (0) satisfies the lower bound. Suppose that π which leads to the fact that Thus we have that Thus, for a i such that π On the other hand, for a i such that π From inequality (25) we have that then according to the induction assumption, we have which completes the proof of the lemma.

Corollary 25.
Under the condition of Lemma 24, running (17) will guarantee that Proof. The first two inequalities are proved in the proof of Lemma 24, we only need to show In the proof of Lemma 24, we have already shown that On the other hand, which completes the proof of the corollary.
Proof. Let θ i,(t) be defined as: Then we have that i (a i |s) We will now bound each part separately. We first get a lower bound for part A:     We will now move on to bound the absolute value of Part C.
|Part C| ≤ 1 1 − γ       Lastly, we will bound the absolute value of Part D.
From Corollary 34 i,s 1 . Thus