Year: 2021

Abstract:
We study the performance of the gradient play algorithm for stochastic games (SGs), where each agent tries to maximize its own total discounted reward by making decisions independently based on current state information which is shared between agents. Policies are directly parameterized by the probability of choosing a certain action at a given state. We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting, and give a local convergence rate around strict NEs. Further, for a subclass of SGs called Markov potential games (which includes the cooperative setting with identical rewards among agents as an important special case), we design a sample-based reinforcement learning algorithm and give a non-asymptotic global convergence rate analysis for both exact gradient play and our sample-based learning algorithm. Our result shows that the number of iterations to reach an -NE scales linearly, instead of exponentially, with the number of agents. Local geometry and local stability are also considered, where we prove that strict NEs are local maxima of the total potential function and fully-mixed NEs are saddle points.

heading: 1 INTRODUCTION
text: Multi-agent systems find applications in a wide range of societal systems, e.g. electric grid, traffic networks, smart building and smart cities etc. Given the complexity of these systems, multi-agent reinforcement learning (MARL) has gained increasing attention in recent years (Daneshfar & Bevrani, 2010; Shalev-Shwartz et al., 2016; Vidhate & Kulkarni, 2017; Xu et al., 2020). Among MARL algorithms, policy gradient-type methods are highly popular because of their flexibility and capability to incorporate structured state and action spaces. However, while many recent works (Zhang et al., 2018; Chen et al., 2018; Wai et al., 2018; Li et al., 2019; Qu et al., 2020) have studied the sample complexity of multi-agent policy gradient algorithms, due to a lack of understanding of the optimization landscape in these multi-agent learning problems, most works can only show convergence to a first-order stationary point. Deeper understanding of the quality of these stationary points is missing even in the simple identical-reward multi-agent RL setting.
In this paper, we examine this problem from a game-theoretic perspective. We model the multi-agent system as a stochastic game (SG) where agents can have different reward functions, and study the dynamical behavior of first-order (gradient-based) learning methods. The study of SGs dates back to as early as the 1950s by Shapley (1953) with a series of followup works on developing NE-seeking algorithms, especially in the RL setting (e.g. (Littman, 1994; Bowling & Veloso, 2000; Shoham et al., 2003; Buşoniu et al., 2010; Lanctot et al., 2017; Zhang et al., 2019a) and citations within). While well-known classical algorithms for solving SGs are mostly value-based, such as Nash-Q learning (Hu & Wellman, 2003), Hyper-Q learning (Tesauro, 2003), and WoLF-PHC (Bowling & Veloso, 2001), gradient-based algorithms have also started to gain popularity in recent years due to their advantages as mentioned earlier (e.g. (Abdallah & Lesser, 2008; Zhang & Lesser, 2010; Foerster et al., 2017)). In this work, we aim to gain a deeper understanding of the structure and quality of first-order stationary points for these gradient-based methods, with a particular focus on answering the following questions: 1) How do the first-order stationary points relate to the NEs of the underlying game?, 2) Do gradient-based algorithms guarantee convergence to a NE?, 3) What is the stability of the individual NEs?, and 4) How should agents learn using local samples from the environment?.
These questions have already been widely discussed in other settings, e.g., one-shot (stateless) finiteaction games (Shapley, 1964; Crawford, 1985; Jordan, 1993; Krishna & Sjöström, 1998; Shamma &
Arslan, 2005; Kohlberg & Mertens, 1986; Van Damme, 1991), one-shot continuous games (Mazumdar et al., 2020), zero-sum linear quadratic (LQ) games Zhang et al. (2019b), etc. There are both negative and positive results depending on the settings. For one-shot continuous games, (Mazumdar et al., 2020) proved a negative result suggesting that gradient flow has stationary points (even local maxima) that are not necessarily NEs. Conversely, Zhang et al. (2019b) designed projected nested-gradient methods that provably converge to NEs in zero-sum LQ games. However, much less is known in the tabular setting of SGs with finite state-action spaces.
Contributions. In our paper, we consider the gradient play algorithm for the infinite time-discounted reward SGs where an agent’s individual policy is directly parameterized by the probability of choosing an action from the agent’s own action space at a given state. We focus on the tabular setting where state and action spaces are finite. Through generalizing the gradient domination property in (Agarwal et al., 2020) to the multi-agent setting, we first establish the equivalence of first-order stationary policies and Nash equilibria. We then show that strict NEs are locally asymptotically stable under gradient play and provide a local convergence rate analysis.
Additionally, we study the global convergence for a special class of SGs called Markov potential games (MPGs) (González-Sánchez & Hernández-Lerma, 2013; Macua et al., 2018; Leonardos et al., 2021), which includes identical reward multi-agent RL (Tan, 1993; Claus & Boutilier, 1998; Panait & Luke, 2005) as an important special case. In this setting, we first show that exact gradient play can find an -Nash equilibrium within O ( |S| ∑ i |Ai| 2 ) steps. Then, we design a sample-based gradient
play algorithm and show that it can find an -Nash equilibrium with high probability in a fullydecentralized manner using Õ ( n 6 poly ( 1 1−γ , |S|,maxi |Ai| ))
samples, where |S|, |Ai| denote the size of the state space and action space of agent i respectively. The convergence rate shows that the number of iterations to reach an -NE scales linearly with the number of agents. In the sample-based learning, agents only need to observe the state, their own actions, and their own rewards. The key enabler of the learning is the existence of an underlying averaged MDP for each agent when other agents’ policies are fixed. Our learning method can be viewed as a model-based policy evaluation method with respect to agents’ averaged MDPs. This averaged MDP concept could be applied to design many other MARL algorithms, especially policy-evaluation-based methods. We also study the local geometry around some special classes of equilibrium points, showing that strict NEs are local maxima of the total potential function and that fully mixed NEs are saddle points. Lastly, all the algorithms studied in this paper have been numerical tested and results are provided in Appendix A.
Comparison to other MARL algorithms: For MPGs with continuous state and action spaces, there are studies about learning either the open-loop (González-Sánchez & Hernández-Lerma, 2013; Zazo et al., 2016) or the closed-loop (Macua et al., 2018) NEs for MPGs. These works generally assume full model information and solve the problem via optimal control. There are two recent arXiv preprints (Mguni, 2020; Leonardos et al., 2021; Mguni et al., 2021) studying MPGs that are similar to our MPG setting. In particular, Leonardos et al. (2021) also studies gradient play for MPG. Both of our papers share similar results on MPGs but the sample-based methods are designed from different perspectives.1 In addition, our papers studies general SGs besides MPG. Moreover, our concept of “averaged” MDPs could also serve as a useful tool for the design and analysis of other MARL algorithms. Beyond these MPG works, decentralized Q-learning introduced in Arslan & Yüksel (2016) might be the closest to the setting considered in this paper. They consider the identical interest case and only show asymptotic convergence to the set of NEs. There are other recent works that also study learning for general-sum or zero-sum stochastic games. However the settings they consider are different from our setting, for example, Daskalakis et al. (2021) considers convergence to NE for two player zero-sum games, while Song et al. (2021) considers convergence to correlated equilibrium for finite time horizon general-sum games. On the other hand, Zhang et al. (2018); Li et al. (2019); Qu et al. (2019) consider slightly different MARL settings, where agents collaboratively maximize the summation of agents’ reward with either full or partial state observation. They also require communication between neighboring agents for a better global coordination.
1Leonardos et al. (2021) considers Monte Carlo, model-free gradient estimation. The sample complexity is derived under the condition that the estimation is unbiased, which is difficult to hold in general. Interestingly, both sample complexities are O( 1
6 ). It is an interesting question to study whether such dependence is fundamental
or not. We also remark that Leonardos et al. (2021) and this work are done in parallel.

heading: 2 PROBLEM SETTING AND PRELIMINARIES
text: We consider a stochastic game (SG)M = (N,S, A = A1 × · · · × An, P, r = (r1, . . . , rn), γ, ρ) with n agents (Shapley, 1953) which is specified by an agent set N = {1, 2, . . . , n}, a finite state space S, a finite action space Ai for each agent i ∈ N , a transition model P where P (s′|s, a) = P (s′|s, a1, . . . , an) is the probability of transitioning into state s′ upon taking action a := (a1, . . . , an) in state s where ai ∈ Ai is action of agent i, agent i’s reward function ri : S ×A → [0, 1], a discount factor γ ∈ [0, 1), and an initial state distribution ρ over S. A stochastic policy π : S → ∆(A) (where ∆(A) is the probability simplex over A) specifies a strategy in which agents choose their actions jointly based on the current state in a stochastic fashion, i.e. Pr(at|st) = π(at|st). A distributed stochastic policy is a special subclass of stochastic policies, with π = π1× . . .×πn, where πi : S → ∆(Ai). For distributed stochastic policies, each agent takes its action based on the current state s independently of other agents’ choices of actions, i.e.:
Pr(at|st) = π(at|st) = n∏ i=1 πi(ai,t|st), at = (a1,t, . . . , an,t).
For notational simplicity, we define: πI(aI |s) := ∏ i∈I πi(ai|s), where I ⊆ N is an index set. Further, we use the notation −i to denote the index set N\{i}. We consider direct distributed policy parameterization, where agent i’s policy is parameterized by θi:
πi,θi(ai|s) = θi,(s,ai), i = 1, 2, . . . , n. (1)
For notational simplicity, we abbreviate πi,θi(ai|s) as πθi(ai|s), and θi,(s,ai) as θs,ai . Here θi ∈ ∆(Ai)|S|, i.e. θi is subject to the constraints θs,ai ≥ 0 and ∑ ai∈Ai θs,ai = 1 for all s ∈ S.
The global joint policy is given by: πθ(a|s) = ∏n i=1 πθi(ai|s) = ∏n i=1 θs,ai . We use Xi := ∆(Ai)|S|,X := X1 × · · · × Xn to denote the feasible region of θi and θ. Agent i’s value function V θi : S → R, i ∈ N is defined as the discounted sum of future rewards starting at state s via executing πθ, i.e.
V θi (s) := E [ ∞∑ t=0 γtri(st, at) ∣∣ πθ, s0 = s] ,
where the expectation is with respect to the random trajectory τ = (st, at, ri,t)∞t=0 where at ∼ πθ(·|st), st+1 = P (·|st, at). We denote agent i’s total reward starting from initial state s0 ∼ ρ as:
Ji(θ) = Ji(θ1, . . . , θn) := Es0∼ρV θi (s0).
In the game setting, Nash equilibrium is often used to characterize the performance of agents’ policies.
Definition 1. (Nash equilibrium) A policy θ∗ = (θ∗1 , . . . , θ∗n) is called a Nash equilibrium (NE) if
Ji(θ ∗ i , θ ∗ −i) ≥ Ji(θ′i, θ∗−i), ∀θ′i ∈ Xi, i ∈ N
The equilibrium is called a strict NE if the inequality holds strictly for all θ′i ∈ Xi and i ∈ N . The equilibrium is called a pure NE if θ∗ corresponds to a deterministic policy. The equilibrium is called a mixed NE if it is not pure. Further, the equilibrium is called a fully mixed NE if every entry of θ∗ is strictly positive, i.e.: θ∗s,ai > 0, ∀ ai ∈ Ai, ∀ s ∈ S, i ∈ N
We define the discounted state visitation distribution dθ of a policy πθ given an initial state distribution ρ as:
dθ(s) := Es0∼ρ(1− γ) ∞∑ t=0 γtPrθ(st = s|s0), (2)
where Prθ(st = s|s0) is the state visitation probability that st = s when executing πθ starting at state s0. Throughout the paper, we make the following assumption on the SGs we study.
Assumption 1. The stochastic gameM satisfies: dθ(s) > 0, ∀s ∈ S, ∀θ ∈ X .
Assumption 1 requires that every state is visited with positive probability, which is a standard assumption for convergence proofs in the RL literature (e.g. (Agarwal et al., 2020; Mei et al., 2020)).
Similar to centralized RL, we define agent i’sQ-functionQθi : S×A → R and its advantage function Aθi : S ×A → R as:
Qθi (s, a) := E [ ∞∑ t=0 γtri(st, at) ∣∣ πθ, s0 = s, a0 = a] , Aθi (s, a) := Qθi (s, a)− V θi (s).
‘Averaged’ Markov decision process (MDP): We further define agent i’s ‘averaged’ Q-function Qθi : S ×Ai → R and ‘averaged’ advantage-function Aθi : S ×Ai → R as:
Qθi (s, ai) := ∑ a−i πθ−i(a−i|s)Qθi (s, ai, a−i), Aθi (s, ai) := ∑ a−i πθ−i(a−i|s)Aθi (s, ai, a−i). (3)
Similarly, we define agent i’s ‘averaged’ transition probability distribution P θi : S × S ×Ai → R, and ‘averaged’ reward rθi : S ×Ai → R as:
P θi (s ′|s, ai) := ∑ a−i πθ−i(a−i|s)P (s′|s, ai, a−i), rθi (s, ai) := ∑ a−i πθ−i(a−i|s)ri(s, ai, a−i)
From its definition, the averaged Q-function satisfies the following Bellman equation: Lemma 1. Qθi satisfies: Qθi (s, ai) = rθi (s, ai) + γ ∑ s′,a′i πθi(a ′ i|s′)P θi (s ′|s, ai)Qθi (s ′, a′i) (4)
Lemma 1 suggests that the averaged Q-function Qθi is indeed the Q-function for the MDP defined on action space Ai, with rθi , P θi as its stage reward and transition probability respectively. We define this MDP as the ‘averaged’ MDP of agent i, i.e., Mθi = (S,Ai, P θi , rθi , γ, ρ). The notion of an ‘averaged’ MDP will serve as an important intuition when designing the sample-based algorithm. Note that the ‘averaged’ MDP is only well-defined when the policies of the other agents θ−i are kept fixed. When this is indeed the case, agent i can be treated as an independent learner with respect to its own ‘averaged’ MDP. Thus, various classical policy evaluation RL algorithms can then be applied.

heading: 3 EXACT GRADIENT PLAY FOR GENERAL STOCHASTIC GAMES
text: Under direct distributed parameterization, the gradient play algorithm is given by:
Exact Gradient Play: θ(t+1)i = ProjXi(θ (t) i + η∇θiJi(θ (t) i )), η > 0. (5)
Gradient play can be viewed as a ‘better response’ strategy, where agents update their own parameters by gradient ascent with respect to their own rewards. A first-order stationary point is defined as such:
Definition 2. (First-order stationary policy) A policy θ∗ = (θ∗1 , . . . , θ∗n) is called a first-order stationary policy if (θ′i − θ∗i )>∇θiJi(θ∗) ≤ 0, ∀θ′i ∈ Xi, i ∈ N .
It is not hard to verify that θ∗ is a first-order stationary policy if and only if it is a fixed point under gradient play (Equation (5)). Comparing Definition 1 (of NE) and Definition 2, we know that NEs are first-order stationary policies, but not necessarily vice versa. For each agent i, first-order stationarity does not imply that θ∗i is optimal among all possible θi given θ ∗ −i. However, interestingly, we will show that NEs are equivalent to first-order stationary policies due to a gradient domination property that we will show later. Before that, we first calculate the explicit form of the gradient∇θiJi. Policy gradient theorem (Sutton et al., 1999) gives an efficient formula for the gradient:
∇θEs0∼ρV θi (s0) = 1
1− γ Es∼dθEa∼πθ(·|s)[∇θ log πθ(a|s)Q θ i (s, a)], i ∈ N. (6)
Applying Equation (6), the gradient∇θiJi can be written explicitly as follows: Lemma 2. (Proof in Appendix D) For direct distributed parameterization (Equation (1)),
∂Ji(θ) ∂θs,ai = 1 1− γ dθ(s)Qθi (s, ai) (7)
Gradient domination and the equivalence between NE and first-order stationary policy. Lemma 4.1 in Agarwal et al. (2020) established gradient domination for centralized tabular MDP under direct parameterization. We can show that a similar property still holds for stochastic games.
Lemma 3. (Gradient domination, proof in Appendix E.) For direct distributed parameterization (Equation (1)), we have that for any θ = (θ1, . . . , θn) ∈ X :
Ji(θ ′ i, θ−i)− Ji(θi, θ−i) ≤ ∥∥∥∥dθ′dθ ∥∥∥∥ ∞ max θi∈Xi (θi − θi)>∇θiJi(θ), ∀θ′i ∈ Xi, i ∈ N (8)
where ∥∥∥dθ′dθ ∥∥∥∞ := maxs dθ′ (s)dθ(s) , and θ′ = (θ′i, θ−i).
For the single-agent case (n = 1), Equation (8) is consistent with the result in Agarwal et al. (2020), i.e.: J(θ′) − J(θ) ≤ ∥∥∥dθ′dθ ∥∥∥∞maxθ∈X (θ − θ)>∇J(θ). However, when there are multiple agents, the condition is much weaker because the inequality requires θ−i to be fixed. When n = 1, gradient domination rules out the existence of stationary points that are not global optima. For the multi-agent case, the property can no longer guarantee the equivalence between first-order stationarity and global optimality; instead, it links the stationary points with NEs as shown in the next theorem whose proof is in Appendix E.
Theorem 1. Under Assumption 1, first-order stationary policies and NEs are equivalent. Local convergence for strict NEs Although the equivalence of NEs and stationary points under gradient play has been established, it is in fact difficult to show that gradient play converges to these stationary points. Even in the simpler static (stateless) game setup, gradient play might fail to converge (Shapley, 1964; Crawford, 1985; Jordan, 1993; Krishna & Sjöström, 1998). One major difficulty is that the vector field {∇θiJi(θ)}ni=1 is not a conservative vector field. Accordingly, its dynamics may display complicated behavior. Thus, as a preliminary study, instead of looking at global convergence, we focus on the local convergence and restrict our study to a special subset of NEs - the strict NEs. We begin by giving the following characterization of strict NEs:
Lemma 4. Given a stochastic gameM, any strict NE θ∗ is pure, meaning that for each i and s, there exist one a∗i (s) such that θ ∗ s,ai = 1{ai = a ∗ i (s)}. Additionally,
i) a∗i (s) = arg max ai Aθ ∗ i (s, ai), ii) A θ∗ i (s, a ∗ i (s)) = 0; iii) A θ∗ i (s, ai) < 0, ∀ ai 6= a ∗ i (s) (9)
Based on this lemma, we define the following for studying the local convergence of a strict NE θ∗:
∆θ ∗
i (s) := min ai 6=a∗i (s)
∣∣∣Aθ∗i (s, ai)∣∣∣ , ∆θ∗ := min i min s 1 1− γ dθ∗(s)∆ θ∗ i (s) > 0. (10)
Theorem 2. (Local finite time convergence around strict NE) Define the metric of policy parameters as: D(θ||θ′) := max1≤i≤n maxs∈S ‖θi,s − θ′i,s‖1, where ‖ · ‖1 denote the `1- norm. Suppose θ∗ is a strict Nash equilibrium, then for any θ(0) such that D(θ(0)||θ∗)≤ ∆ θ∗ (1−γ)3
8n|S|( ∑n i=1 |Ai|) , running
gradient play (Equation (5)) will guarantee D(θ(t+1)||θ∗) ≤ max { D(θ(t)||θ∗)− η∆ θ∗ 2 , 0 } , which means that gradient play is going to converge within d 2D(θ (0)||θ∗)
η∆θ∗ e steps.
Proofs of Lemma 4 and Theorem 2 are provided in Appendix F. The convergence only requires a finite number of steps and the stepsize η can be chosen arbitrarily large so that exact convergence can happen in even just one step. However, the caveat is that we need to assume that the initial policy is sufficiently close to θ∗. For numerical stability considerations, one should pick reasonable stepsizes to run the algorithm to accommodate random initializations. Theorem 2 also shows that the radius of region of attraction for strict NEs is at least ∆ θ∗ (1−γ)3
8n|S|( ∑n i=1 |Ai|) , and thus θ∗ with a larger ∆θ ∗ , i.e., a
larger value gap between the optimal action and other actions, will have a larger region of attraction. We would like to further remark that Theorem 2 only focuses on the local convergence property, the way to interpret the theorem is that, if there exists a strict NE, then it is locally asymptotic stable under gradient play. However, it does not claim to solve the global existence or convergence of the strict NEs.

heading: 4 GRADIENT PLAY FOR MARKOV POTENTIAL GAMES
text: We have discussed that the main problem for the global convergence of gradient play for general SGs is that the vector field {∇θiJi(θ)}ni=1 is not conservative. Thus, in this section, we restrict our analysis to a special subclass where the vector field is conservative, which in turn enjoys global convergence. This subclass is generally referred to as a Markov potential game (MPG) in the literature.
Definition 3. (Markov potential game (Macua et al., 2018)) A stochastic gameM is called a Markov potential game if there exists a potential function φ : S ×A1× · · · ×An→R such that for any agent i and any pair of policy parameters (θ′i, θ−i), (θi, θ−i) :
E [ ∞∑ t=0 γtri(st, at) ∣∣π = (θ′i, θ−i), s0 = s ] − E [ ∞∑ t=0 γtri(st, at) ∣∣π = (θi, θ−i), s0 = s]
=E [ ∞∑ t=0 γtφ(st, at) ∣∣π = (θ′i, θ−i), s0 = s ] − E [ ∞∑ t=0 γtφ(st, at) ∣∣π = (θi, θ−i), s0 = s] , ∀ s.
As shown in the definition, the condition of a MPG is admittedly rather strong and difficult to verify for general SGs. Macua et al. (2018); González-Sánchez & Hernández-Lerma (2013) found that continuous MPGs can model applications such as the great fish war (Levhari & Mirman, 1980), the stochastic lake game (Dechert & O’Donnell, 2006), medium access control (Macua et al., 2018) etc. There are also efforts attempting to identify conditions such that a SG is a MPG, e.g., Macua et al. (2018); Leonardos et al. (2021); Mguni (2020). In Appendix B, we provide a more detailed discussion on MPGs, including a necessary condition (Lemma 5) of MPG, counterexamples of stage-wise potential games that are not MPG, sufficient conditions for a SG to be a MPG, and application examples of MPG. Nevertheless, identifying sufficient and necessary conditions and broadening the applications of MPG are important furture directions.
Given a policy θ, we define the ‘total potential function’ Φ(θ) := Es0∼ρ(·) [∑∞ t=0 γ tφ(st, at) ∣∣ πθ] for a MPG. The following proposition guarantees a MPG has at least one NE and it is a pure NE.
Proposition 1. (Proof in Appendix G) For a Markov potential game, there is at least one global maximum θ∗ of the total potential function Φ, i.e.: θ∗ ∈ arg maxθ∈X Φ(θ) that is a pure NE.
From the definition of the total potential function we obtain the following relationship
Ji(θ ′ i, θ−i)− Ji(θi, θ−i) = Φ(θ′i, θ−i)− Φ(θi, θ−i). (11)
Thus, ∇θiJi(θ) = ∇θiΦ(θ), which means that gradient play (Equation (5)) is equivalent to running projected gradient ascent with respect to the total potential function Φ, i.e.: θ(t+1) = ProjX (θ(t) + η∇θΦ(θ(t)i )), η > 0. To measure the convergence to a NE, we define an -Nash equilibrium as follows:
Definition 4. ( -Nash equilibrium) Define the ‘NE-gap’ of a policy θ as:
NE-gapi(θ) := max θ′i∈Xi
Ji(θ ′ i, θ−i)− Ji(θi, θ−i); NE-gap(θ) := max
i NE-gapi(θ).

heading: A policy θ is an -Nash equilibrium if: NE-gap(θ) ≤ .
text: We further assume that the MPG satisfies the following assumption.
Assumption 2. For θ ∈ X , the total potential function Φ(θ) is bounded by: Φmin ≤ Φ(θ) ≤ Φmax.

heading: 4.1 EXACT GRADIENT PLAY - GLOBAL CONVERGENCE AND LOCAL GEOMETRY
text: In this section, we first focus on the global convergence for exact gradient play (5), where the gradient ∇θiJi can be calculated exactly by agent i. The convergence result is given as follows: Theorem 3. (Global convergence to Nash equilibria, proof in Appendix H.) Given a MPG with potential function φ(s, a), suppose the total potential function Φ satisfies Assumption 2. Then with
stepsize η = (1−γ) 3 2 ∑n i=1 |Ai| , θ(t) asymptotically converge to a NE under gradient play (Equation (5)), i.e., limt→∞ NE-gap(θ(t)) = 0. Further, we have:
1
T ∑ 1≤t≤T NE-gap(θ(t))2 ≤ 2, whenever T ≥ 64M2(Φmax − Φmin)|S| ∑n i=1 |Ai| (1− γ)3 2 , (12)
where M := maxθ,θ′∈X ∥∥∥ dθdθ′ ∥∥∥∞ (by Assumption 1, we know that this quantity is well-defined).
The factor M is also known as the distribution mismatch coefficient that characterizes how the state visitation varies with the policies. Given an initial state distribution ρ that has positive measure on every state, M can be at least bounded by M ≤ 11−γ maxθ ∥∥∥dθρ ∥∥∥∞≤ 11−γ 1mins ρ(s) . Also note that Inequality (12) on the average term 1T ∑ 1≤t≤T NE-gap(θ
(t))2 could be translated to a constant probability guarantee on single NE-gap(θ(t)). For instance, if we randomly pick one θ(t) from 1 ≤ t ≤ T , then it guarantees that NE-gap(θ(t))2 ≤ 3 · 2 with probability at least 23 .
2 As a comparison with centralized learning, if we parameterize the policy in a centralized way, the size of the action space will be |A| = ∏n i=1 |Ai| and the projected gradient ascent would needO ( |S| ∏n i=1 |Ai| 2 ) steps to find an -optimal policy (Agarwal et al., 2020); whereas we only needO ( |S| ∑n i=1 |Ai| 2 ) steps
to find an -NE, which scales linearly with n. However, centralized parameterization can provably find a global optimum, while distributed parameterization can only find a NE.
Though gradient play is guaranteed to converge to a NE, the exact NE which it converges to is uncertain, and depends on the initial point as well as the local geometry around the various NEs. As a preliminary study, we have the following characterization for two special types of NEs. More future investigation is needed for general NEs. Theorem 4. For Markov potential game with Φmin<Φmax (i.e., Φ is not a constant function):
• A strict NE θ∗ is equivalent to a strict local maximum of the total potential function Φ, i.e.: ∃ δ, s.t. ∀ θ 6=θ∗ that satisfies ‖θ − θ∗‖ ≤ δ, θ ∈ X , we have Φ(θ) < Φ(θ∗).
• Any fully mixed NE θ∗ is a saddle point with regard to the total potential function Φ, i.e.: ∀ δ > 0, ∃ θ, s.t. ‖θ−θ∗‖ ≤ δ and Φ(θ)>Φ(θ∗).
Theorem 4 implies that strict NEs are asymptotically stable under first-order methods such as gradient play; while the fully mixed NEs are not stable under gradient play. We remark that the conclusion about strict NE in Theorem 4 does not hold for settings other than tabular MPG; for instance, for continuous games, one can use quadratic functions to construct simple counterexamples (Mazumdar et al., 2020). Also, similar to the remark after Theorem 2, this theorem focuses on the local geometry of the NEs but does not claim the global existence or convergence of either strict NEs or fully mixed NEs.

heading: 4.2 SAMPLE-BASED LEARNING: ALGORITHM DESIGN AND SAMPLE COMPLEXITY
text: In this section, we no longer assume access to the exact gradient, but instead estimate it via samples. Throughout the section, we make the following additional assumption on MPGs: Assumption 3. ((τ, σS)-Sufficient exploration on states) There exist a positive integer τ and a σS ∈ (0, 1) such that for any policy θ and any initial state-action pair (s, ai), ∀i, we have
Pr(sτ |s0 = s, a0 = a) ≥ σS , ∀sτ . (13)
It says that every state has a positive probability of being visited after some time. This assumption is common in proving finite time convergence (e.g. (Qu et al., 2019; Srikant & Ying, 2019)).
We further introduction the state transition probability under θ P θS : S × S → R as:
P θS(s ′|s) := ∑ a πθ(a|s)P (s′|s, a).
We consider fully decentralized learning, where agent i’s observation only includes state st, its own action ai,t, and its own reward ri,t := ri(st, at) at time t. Such fully decentralized learning is
2Here 3, 2 3 could be replaced by 1 1−p , p where p ∈ (0, 1) is a probability.
plausible due to the fact that when θ−i is fixed, agent i can be treated as an independent learner with the underlying MDP being the ‘averaged’ MDP described in Section 2. With this key observation, we design a two-timescale ‘model-based’ on-policy learning algorithm, where agents perform policy evaluation in the inner loop and gradient ascent at the outer loop. The algorithm is provided in Algorithm 1. Roughly, it consists of three main steps: 1) (Inner loop) Estimate the averaged transition probability and reward using on-policy samples P θi , r θ i , P θ S . 2) (Inner loop) Calculate averaged Q-function Qθi and discounted state visitation distribution dθ, and compute the estimated gradient accordingly, 3) (Outer loop) Running projected gradient ascent with estimated gradients. Before discussing our algorithm in more detail, we highlight that the idea of using the “averaged” MDP can be used to design other learning methods including model-free methods, e.g., using the temporal difference methods to perform policy evaluation. One caveat is that the “averaged” MDP is only welldefined when all the other agents use fixed policies. This makes it difficult to extend the two-timescale framework to single-timescale settings, which is an interesting future direction.
Algorithm 1 Sample-based learning Require: learning rate η, greedy parameter α, sample trajectory length TJ , total iteration steps TG
For each agent i for k = 0, 1 . . . , TG − 1 do
for t = 0, 1, . . . , TJ do Implement policy θ(k) and collect trajectory D(k)i : D (k) i ←D
(k) i ∪{st, ai,t, ri,t}, ai,t∼πθ(k)i (·|s)
end for Estimate P̂ θi , r̂ θ i , P̂ θ S , M̂ θ i by Equation (14), Equation (15), Equation (16) respectively.
Calculate Q̂θi , d̂θ by Equation (17), Equation (18) respectively. Estimate the gradient by Equation (19): Run projected gradient ascent as in Equation (20)
end for
Step 1: empirical estimation of P θi , rθi , P θS : Given a sequence {st, ai,t, ri,t} TJ t=0 generated by a
policy θ := (θi, θ−i), the empirical estimation P̂ θi of P θ i is given by:
P̂ θi (s ′|s, ai) :=  ∑TJ−1 t=0 1{st+1=s ′,st=s,ai,t=ai}∑TJ−1 t=1 1{st=s,ai,t=ai} , ∑TJ−1 t=1 1{st = s, ai,t = ai} ≥ 1
1{s′ = s}, ∑TJ−1 t=1 1{st = s, ai,t = ai} = 0
(14)
Here we separately treat the special case where the state and action pair is not visited through the whole trajectory, i.e., ∑TJ−1 t=1 1{st = s, ai,t = ai} = 0 to make P̂ θi well-defined.
Similarly, the estimates r̂θi , P̂ θ S of r θ i , P θ S are given by:
r̂θi (s, ai) :=  ∑TJ t=0 1{st=s,ai,t=ai}ri,t∑TJ t=0 1{st=s,ai,t=ai} , ∑TJ−1 t=1 1{st = s, ai,t = ai} ≥ 1
0, ∑TJ−1 t=1 1{st = s, ai,t = ai} = 0
(15)
P̂ θS(s ′|s) :=  ∑TJ−1 t=0 1{st+1=s ′,st=s}∑TJ−1 t=1 1{st=s} , ∑TJ−1 t=1 1{st = s} ≥ 1
1{s′ = s}, ∑TJ−1 t=1 1{st = s} = 0
(16)
Step 2: estimation of Qθi , dθ: We slightly abuse notation and use Qθi , rθi ∈ R|S||Ai| to also denote the vectors corresponding to the averaged Q-function and reward function of agent i. Similarly, ρ, dθ ∈ R|S| are used to denote the vectors for ρ(s) and dθ(s). Define Mθi ∈ R|S||Ai|×|S||Ai|:
Mθi (s,ai)→(s′,a′i) := πθi(a ′ i|s′)P θi (s ′|s, ai).
Then from Lemma 1, Qθi is given by: (I − γMθi )Qθi = rθi =⇒ Qθi = (I − γMθi )−1rθi . The estimated averaged Q-function Q̂θi is given by: 3
Q̂θi = (I − γM̂θi ) −1r̂θi , where M̂ θ i (s,ai)→(s′,a′i) := πθi(a ′ i|s′)P̂ θi (s ′|s, ai) (17)
Similarly, from Equation (2), we have that dθ and d̂θ are given by (derivation see Appendix C): dθ = (1− γ) ( I − γP θS > )−1 ρ, d̂θ := (1− γ) ( I − γP̂ θS > )−1 ρ. (18)
Then accordingly, the estimated gradient is computed as:
∂̂θs,aiJi(θ (k)) =
1
1− γ d̂θ(s)Q̂θi (s, ai). (19)
Step 3: Projected gradient ascent onto the set of α-greedy policies: Let Un=[ 1n , . . . , 1 n ]∈∆(n)
denote the n dimensional uniform distribution. Define ∆α(n):={θ| ∃θ′∈∆(n), s.t. θ=(1−α)θ′+αUn}. We use Xαi :=∆α(|Ai|)|S|, Xα:=Xα1 ×Xα2 × · · ·×Xαn to denote the set of the α-greedy policies for θi and θ respectively. Every step after doing gradient ascent, the parameter θ will further be projected onto Xα, i.e.:
θ (k+1) i = ProjXαi (θ (k) i + η∇̂θiJi(θ (k))) (20) The reason of projecting ontoXα instead ofX is to make sure that every action has positive possibility of being selected in order to get a relatively accurate estimation of averaged Q-function. Intuitively, a larger α introduces a larger additional error in the NE-gap; however, a smaller α requires more samples to estimate the gradient. Thus the choice of α is the tradeoff between the two effects. Theorem 5. (Sample complexity) Assume that the MPG satisfies Assumption 3. Let M := maxθ,θ′∈X
∥∥∥ dθdθ′ ∥∥∥∞. In Algorithm 1, for η ≤ (1−γ)34∑i |Ai| , α = (1−γ) 6M , and TJ≥ 206976τnM4|S|3 maxi |Ai|3
(1− γ)8 4σ2S log
( 16τTG|S|2 ∑ i|Ai|
δ
) +τ, TG≥
648M2(Φmax−Φmin)|S| η 2
with probability at least 1− δ, we have that: 1TG ∑TG k=1 NE-gap(θ (k))2 ≤ 2
That is, the algorithm can find an -NE with probability at least 1− δ with TJTG ∼ Õ ( n
6 poly
( 1
1− γ , |S|,max i |Ai|
)) (21)
samples, where Õ hides log factors.
Comparison with centralized learning: The best known sample complexity bound for singleagent/centralized MDP is Õ
( |S||A|
(1−γ)3 2
) (Sidford et al., 2018). Compared with Equation (21), the
centralized bound scales better with respect to , |S|, |Ai|, 11−γ . However, as argued in the previous subsection, the total action space |A| = ∏n i=1 |Ai| in the centralized bound scales exponentially with the number of agent n, while our complexity bound only scales linearly. Here, we briefly state the fundamental difficulties of learning in the SG setting compared with centralized learning, which also explains why our bound scales worse with respect to the factors , |S|, |Ai|, 11−γ . 1) Firstly, the optimization landscape in the SG setting is more complicated. For centralized learning, the gradient domination property is stronger and accelerated gradient methods (e.g. via natural policy gradient or entropy regularization) can speed up the convergence of exact gradient from O( 1 2 ) to O( 1 ) (Agarwal et al., 2020), or even O(log( 1 )) (Mei et al., 2020). In contrast, for multi-agent settings, due to the more complicated optimization landscape, these methods can no longer improve the dependency on , which thus makes the outer loop complexity TG larger. 2) Secondly, the behavior of other agents makes the environment non-stationary, i.e., the averaged Q-function Qθi as well as the averaged transition probability distribution P θi depends on the policy of other agent θ−i. Thus, unlike centralized learning, where the state transition probability matrix can be estimated in an off-policy or
3From the Perron-Frobenius theorem, we know that the absolute values of the eigenvalues of M̂θi are upper bounded by 1, which guarantees that the matrix I − γM̂θi is invertible.
even offline manner, i.e. using data samples from different policies, P θi can only be estimated in a online manner, using samples generated by exactly the same policy θ, which increases the inner loop complexity TJ . 3) Thirdly, the complicated interactions amongst agents necessitate more care during the learning process. Algorithms designed for centralized learning that achieve near-optimal sample complexity are generally Q-learning type algorithms. However, in SGs, it can be shown that having each agent maximize its own averaged Q-function may actually lead to non-convergent behavior. Thus, we need to consider algorithms that update in a less aggressive manner, e.g. soft Q-learning, or policy gradient (which is considered in this paper).
Numerical Results. Due to the space limit, numerical performance for algorithms studied in this paper are deferred to Appendix A.

heading: 5 CONCLUSION AND DISCUSSION
text: This paper studies the optimization landscape and convergence of gradient play for SGs. For general SGs, we establish some local convergence results; for MPGs, we establish the global convergence and design a sample-based method. There are many future directions. Firstly, the assumption of MPGs is relatively strong compared with the notion of potential games in the one-shot setup, which might restrict its application to broader settings. More effort would be needed to come up with other special types of SGs which facilitate learning. It would also be meaningful to combine the insight from learning in stochastic games to investigate real-life applications, such as dynamic congestion and routing. Secondly, the sample-based learning algorithm proposed in this paper is only one choice. Other methods, such as actor-critic, natural policy gradient, Gauss-Newton methods, could also be considered, which might improve the sample complexity. We note in passing that it is an interesting and important question to characterize the fundamental complexity of MARL. Thirdly, this paper only considers direct policy parameterization. To broaden the application of MARL and to strengthen the results, other types of parameterization such as softmax parameterization and general nonlinear parameterization should be investigated.

heading: A NUMERICAL EXAMPLES
text: Game 1: multi-stage prisoner’s dilemma The first example — multi-stage prisoner’s dilemma model(Arslan & Yüksel, 2016) — studies exact gradient play for general SG settings. It is a 2-agent MDP, with S = A1 = A2 = {1, 2}. Assume that the reward for each agent ri(s, a1, a2), i ∈ {1, 2} is independent of state s and is given by Table 1. The state transition probability is determined by agents’ previous actions:
P (st+1 = 1|(a1,t, a2,t) = (1, 1)) = 1− , P (st+1 = 1|(a1,t, a2,t) 6= (1, 1)) =
Here action ai = 1 means that agent i choose to cooperate and ai = 2 means betray. The state s serves as a noisy indicator, with accuracy 1− , of whether both agents cooperated (st = 1) or not (st = 2) in the previous stage t− 1. The single-stage game corresponds to the famous Prisoner’s Dilemma, and it is well-known that there is a unique NE (a1, a2) = (2, 2), where both agent decide to betray. The dilemma arises from the fact that there exists a joint non-NE strategy (1, 1) such that both players obtain a higher reward than what they get under the NE. However, in the multi-stage case, the introduction of an additional state s allows agents to make decisions based on whether they have cooperated before. Intuitively, given that both agents cooperated at the previous stage, it is more beneficial to keep this cooperation rather than destroy it by betraying. It turns out that cooperation can be achieved in this manner given that the two agents are patient (i.e., γ is close to 1) and that the indicator s is accurate enough (i.e. is close to 0). Apart from the fully betray strategy, where both agents will betray regardless of s,
there is another strict NE θ∗ that is θ∗s=1,ai=1 = 1, θ ∗ s=2,ai=1 = 0, where agents will cooperate given that they have cooperated in previous stage, and betray otherwise.
We simulate gradient play for this model and mainly focus on the convergence to the cooperative equilibrium θ∗. The initial policy is set as: θ(0)s=1,ai=1 = 1−0.4δi, θ (0) s=2,ai=1
= 0, where the δi’s are uniformly sampled from [0, 1]. The initialization implies that at the beginning, both agents are willing to cooperate to some extent given that they cooperated at the previous stage. Figure 1 shows a trial converging to the NE starting from a randomly initialized policy. The size of the region of attraction for θ∗ can be reflected by the ratio of convergence ( #Trials that converge to θ ∗
#Total number of trials ) for multiple trials with different initial points. An empirical estimate of the volume of the region is the convergence ratio times the volume of the uniform sampling area; the larger the ratio, the larger the region of attraction. Table 3 demonstrates the change of the ratio with regard to different values of indicator error . Intuitively speaking, the more accurately the state s represents the cooperation situation of the agents, the less incentive agents will have for betraying when observing s = 1, that is, the larger ∆θ ∗ (s=1) will become, and thus the larger the convergence ratio will be. This intuition matches the simulation result as well as the theoretical guarantees on the local convergence around a strict NE in Theorem 2.
#Total number of trials . Here we calculate one ratio using 100 trials and the mean and standard deviation (std) are calculated by computing the ratio 10 times using different trials. ∆θ ∗ (s= 1) is calculated using Equation (10)
Game 2: coordination game Our second numerical example studies the empirical performance of exact gradient play for an identical-reward game which is a special class of Markov potential game. Consider a 2-agent identical reward coordination game problem with state space S = S1 × S2 and action space A = A1 ×A2, where S1 = S2 = A1 = A2 = {1, 2}. The state transition probability is given by:
P (si,t+1 = 1|ai,t = 1) = 1− , P (si,t+1 = 1|ai,t = 2) = , i = 1, 2.
The reward table is given by Table 2, where agents will only be rewarded if they are in the same state, and state 1 has a higher reward than state 2. Coordination games can be used to model the network effect in economics, where an agent reaps benefits from being in the same network as other agents. For this specific example, there are two networks with different utilities. Agents can observe the occupancy of each network, and take actions to join one of the networks based on the observation.
There is at least one fully-mixed NE where both agents join network 1 with probability 1−3 3(1−2 ) regardless of the current occupancy of networks, and there are 13 different strict NEs that can be verified numerically (computation of the NEs as well as detailed settings can be found in Appendix N). Figure 2 shows a gradient play trajectory whose initial point lies in a close neighborhood of the
mixed NE. As the algorithm progresses, we see that the trajectory in Figure 2 diverges from the mixed-NE, indicating that the fully-mixed NE is indeed a saddle point. This corroborates our finding in Theorem 4. Figure 3 shows the evolution of total reward J(θ(t)) for gradient play for different random initial points θ(0). Different initial points converge to one of 13 different strict NEs each with a different total reward (some strict NEs with relatively small region of attraction are omitted in the figure). We see the total reward is monotonically increasing for each initial point, which makes sense since gradient play runs projected gradient ascent on the total reward function J . While the total rewards are different, as shown in Figure 4, we see that the NE-gap of each trajectory (corresponding to same initial points in Figure 3) converges to 0. This suggests that the algorithm is indeed able to converge to a NE. Notice that the NE-gaps do not decrease monotonically.
Game 3: state-based coordination game Our third numerical example studies the empirical performance of the sample-based learning algorithm, Algorithm 1. Here we consider a generalization of coordination game (Game 2) where the two players now try to coordinate on a 2D grid. The two-player state-based coordination game on a 3 × 3 grid is defined as follows: the state space is given by S = S1 × S2, S1 = S2 = Sx × Sy = {xa, xb, xc} × {ya, yb, yc}, action space is given by A = A1 ×A2, A1 = A2 = {Stay,Left,Right,Up,Down}, i.e., agent can choose to stay at current grid or move left/right/up/down to its neighboring grids. We assume that there is random noise during the transition; for example, if agent 1 is staying at the middle grid (xb, yb), then:
P (s′1,x = xa|s1,x = xb, a1 = Stay) = P (s′1,x = xc|s1,x = xb, a1 = Stay) = , P (s′1,x = xb|s1,x = xb, a1 = Stay) = 1− 2 , P (s′1,y = ya|s1,y = xb, a1 = Stay) = P (s′1,y = yc|s1,y = xb, a1 = Stay) = , P (s′1,y = yb|s′1,y = yb, a1 = Stay) = 1− 2 .
The reward is given by:
r(s1, s2) = 1{s1 = s2 = {xa, ya} or {xc, yc}}, i.e. the two agents are only rewarded if they stay at the upper-left or lower-right corner at the same time.
For numerical simulation, we take TG = 300, TJ = 10000, α = 0.1, η = 10, = 0.1; the numerical results are as displayed in Figure 6 - 8. Figure 6 shows that total reward increases as the number of iterations increase, and Figure 8 shows that the NE-gap converges to a value close to zero. However, because we project the policy to the α-greedy set Xα, the NE-gap cannot converge to exactly zero.
Figure 7 visualizes the discounted state visitation distribution. To make the visualization more intuitive, we look at the marginalized discounted state visitation distribution dxθ , d y θ defined below: dxθ (s1,x, s2,x)= ∑
s1,y,s2,y
dθ(s1,x, s1,y, s2,x, s2,y) = Es0∼ρ(1−γ) ∞∑ t=0 γt Pr(s1,x,t=s1,x, s2,x,t=s2,x|s0, πθ)
dyθ(s1,y, s2,y)= ∑
s1,x,s2,x
dθ(s1,x, s1,y, s2,x, s2,y) = Es0∼ρ(1−γ) ∞∑ t=0 γt Pr(s1,y,t=s1,y, s2,y,t=s2,y|s0, πθ)
From Figure 7 we can see that most of the probability measure concentrates on {(xa, xa), (xc, xc)}, {(ya, ya), (yc, yc)}, indicating that the two agents are able to coordinate most of the time.

heading: B MORE ABOUT MARKOV POTENTIAL GAMES
text: This section is dedicated to a more thorough understanding of Markov potential games, which includes necessary or sufficient conditions for MPG and a few (counter)examples.
B.1. A necessary condition and counterexamples Definition 5. (Monderer & Shapley (1996)) Define the path in the parameter space as τ = (θ(0), θ(1), . . . , θ(N)), where θt, θt+1 differ only one component it, i.e. θ(t+1) = (θ (t+1) it , θ (t) −it).

heading: A closed path is a path such that θ(0) = θ(N). Define:
text: I(τ) := N∑ t=1 Jit(θ (t))− Jit(θ(t−1))
The following theorem is a direct generalization of Theorem 2.8 in Monderer & Shapley (1996) to MPG setting:
Lemma 5. For Markov potential games, I(τ) = 0 for any finite closed path τ .
Proof. The proof is quite straightforward from the definition of MPG
I(τ) = N∑ t=1 Jit(θ (t))− Jit(θ(t−1))
= N∑ t=1 Φ(θ(t))− Φ(θ(t−1))
= Φ(θ(N))− Φ(θ(0)) = 0.
Although the proof of Lemma 5 is straightforward, it serves as a useful tool in proving that a game is not a MPG. For example, applying the theorem we can get that the following conditions are not sufficient conditions for MPG.
Proposition 2. None of the following conditions on a SG necessarily imply that it is a MPG:
(1) There exists φ(s, a) such that at each s, ri(s, a′i, a−i) − ri(s, ai, a−i) = φ(s, a′i, a−i) − φ(s, ai, a−i);
(2) There exists φ(s, a) such that for every s, ŝ, ri(s, a′i, a−i)−ri(ŝ, ai, a−i) = φ(s, a′i, a−i)− φ(ŝ, ai, a−i);
(3) Rewards ri are independent of s, and they have a potential function, i.e., ri(ai, a−i) − ri(a ′ i, a−i) = φ(ai, a−i)− φ(a′i, a−i).
Proof. (of Proposition 2) A simple counterexample showing that the conditions in Equation (2) are not sufficient is the multi-stage prisoner’s dilemma (Game 1) introduced in the numerical section (Appendix A). Since the reward table for multi-stage prisoner’s dilemma is the same as the one-shot prisoner’s dilemma (which is known to be a potential game), Game 1 satisfies condition (3) in Proposition 2, which implies condition (2), which in turn implies condition (1). In the following we are going to use Lemma 5 to show that Game 1 is not a MPG. We define the following individual policies:
θDefecti : θ Defect s=1,ai=1 = 0, θ Defect s=2,ai=1 = 0
θCoopi : θ Coop s=1,ai=1 = 1, θCoops=2,ai=1 = 0
θAlways coopi : θ Always coop s=1,ai=1 = 1, θAlways coops=2,ai=1 = 1
Let:
θ(0) = (θDefect1 , θ Coop 2 ), θ (1) = (θCoop1 , θ Coop 2 ), θ(2) = (θCoop1 , θ Always coop 2 ), θ (3) = (θDefect1 , θ Always coop 2 )
and define a path τ by:
τ = (θ(0), θ(1), θ(2), θ(3), θ(4)), θ(4) = θ(0).
For the sake of easy calculation, we set = 0 and set initial state as s0 = 1 in Game 1. In this example, it is not hard to see that Jit(θ
(t))− Jit(θ(t−1)) > 0 for each t ∈ {1, 2, 3, 4}, implying that I(τ) > 0. This indicates that although Game 1 satisfies condition (3) (as well as conditions (1) and (2)), it is still not a MPG.4
B.2. A sufficient condition
Proposition 2 suggests that MPG is a quite restrictive assumption. Even if the reward table for a SG is the same as the reward table of a one-shot potential game, the SG may still not be a MPG. Nevertheless, we can show that the following condition is sufficient for a stochastic game to be a MPG:5
Lemma 6. A stochastic game is a MPG if condition (1) in Proposition 2 is satisfied and that P (s′|s, a) = P (s′|s).
Proof. P (s′|s, a) = P (s′|s) implies that the discounted state visitation distribution dθ does not depend on θ, and thus we denote it as d(s) instead. Condition (1) implies that φ(s, ai, a−i) − ri(s, ai, a−i) only depends on s and a−i but not ai, and so we denote the difference as δi(s, a−i), i.e., φ(s, ai, a−i)− ri(s, ai, a−i) = δi(s, a−i). The total reward of agent i can be written as:
Ji(θ) = ∑ s d(s) ∑ a πθ(a|s)ri(s, a)
= ∑ s d(s) ∑ ai πθi(ai|s) ∑ a−i πθ−i(a−i|s)r(s, ai, a−i)
Similarly, total potential function can be written as: Φ(θ) = ∑ s d(s) ∑ a πθ(a|s)φ(s, a)
= ∑ s d(s) ∑ ai πθi(ai|s) ∑ a−i πθ−i(a−i|s)φ(s, ai, a−i)
4We can use this counterexample to show that some propositions (e.g., Proposition 3) in the arXiv preprint (Mguni, 2020) would need more consideration since the multi-stage prisoner’s dilemma satisfies the conditions given in (Mguni, 2020).
5The recent arXiv preprint (Leonardos et al., 2021) has a similar characterization.
Thus, Φ(θ)− Ji(θ) = ∑ s d(s) ∑ ai πθi(ai|s) ∑ a−i πθ−i(a−i|s) (φ(s, ai, a−i)− r(s, ai, a−i))
= ∑ s d(s) ∑ ai πθi(ai|s) ∑ a−i πθ−i(a−i|s)δi(s, a−i)
= ∑ s d(s) ∑ a−i πθ−i(a−i|s)δi(s, a−i),
which does not depend on parameter θi, i.e.,
Φ(θ′i, θ−i)− Ji(θ′i, θ−i) = Φ(θi, θ−i)− Ji(θi, θ−i), ∀(θ′i, θ−i), (θi, θ−i) ∈ X ,
which completes the proof.
B.3. MPG with local states and an application example
From Proposition 2, we see that it is difficult for a SG to be a MPG even if the game is a potential game at each state. Lemma 6 only presents a very special case where the action does not affect the state, meaning that this MPG is merely a collection of potential games. To provide a MPG which is beyond the identical-interest case and the case in Lemma 6, inspired by the setting in Qu et al. (2019) and Macua et al. (2018), here we consider a special multi-agent setting where S = S1 × · · · × Sn and Si is the local state space of agent i. In addition, the transition probability takes the decomposed form, P (s′|s, a) = ∏n i=1 P (s ′ i|si, ai). The rest of the SG setting is the same as the SG in Section 2. Deviating slightly from the main text, we consider the localized policy where each agent take actions based on its own state,
πθ(at|st) = n∏ i=1 πθi(ai,t|si,t)
with the localized direct parameterization:
πθi(ai,t|si,t) = θ(si,ai), θi ∈ ∆(Ai) |Si|
We use X locali := ∆(Ai)|Si| to denote the feasibility region of θi, and the feasibility region of θ is denoted as X local := X locali × · · · × X localn . Lemma 7. If there is a function φ(s, a) such that for every agent i, ri(si, s−i, ai, a−i) = φ(si, s−i, ai, a−i) + ψi(s−i, a−i) where ψi only depends on s−i, a−i, then this SG is a MPG, i.e., for any parameters (θ′i, θ−i), (θi, θ−i) ∈ X local, the equation in Definition 3 is satisfied.
The proof is straightforward given the local structure of the MDP and the localized policies. This MPG enjoys nontrivial multi-agent application examples such as medium access control (Macua et al., 2018), dynamic congestion control (Bertrand et al., 2020), etc. Below we provide medium access control as one of the examples.
Real application - medium access control. We consider the discretized version of the dynamic medium access control game introduced in (Macua et al., 2018), where each agent is a user that tries to transmit data via a single transmission medium by injecting power to the wireless network. Each user’s goal is to maximize its data rate and battery lifespan. If multiple users transmit at the same time, they will interfere with each other and decrease their data rate. Here user i’s state is si ∈ Si = {0, 1, . . . , Bi,max}, which denotes its own battery level, where Bi,max is its initial battery level. We use δi to denote its discharging factor. Its action ai ∈ Ai = {0, 1, . . . , Pi,max} denotes the power injected to the network at each time step, where Pi,max is the maximum allowed power. The state transition is deterministic, describing the discharging process of the battery proportional to the transmission power, which is given by:
si,t+1 = si,t − δiai,t.
The stage reward of user i is given by:
ri(s, a) = log
( 1 +
|hi|2ai 1 + ∑ j 6=i |hj |2aj
) + αsi,
where hi is the random fading channel coefficient for user i. By noticing that ri(s, a) = log ( 1 + ∑n i=1 |hi|2ai ) + α ∑ i si − log ( 1 + ∑ j 6=i |hj |2aj ) −
α ∑ j 6=i sj , we can apply Lemma 7 to verify that the medium access control problem is indeed a MPG and that the potential function φ is given as:
φ(s, a) = log ( 1 +
n∑ i=1 |hi|2ai
) + α
n∑ i=1 si.
C DERIVATION OF EQUATION (18) (CALCULATION OF dθ)
From the definition of dθ:
dθ(s) = Es0∼ρ(1− γ) ∞∑ t=0 γtPrθ(st = s|s0),
we have that:
dθ = (1− γ) ( ρ+ γP θS > ρ+ γ2P θS 2> ρ+ · · · )
= (1− γ)(I + γP θS + γ 2P θS
2 · · · )>ρ
= (1− γ)(I − γP θS) −>ρ

heading: D PROOF OF LEMMA 2
text: Proof. According to policy gradient theorem Equation (6):
∂Ji(θ) ∂θs,ai = 1 1− γ ∑ s′ ∑ a′ dθ(s ′)πθ(a ′|s′)∂ log πθ(a ′|s′) ∂θs,ai Qθi (s, a)
Since for direct parameterization:
∂ log πθ(a ′|s′)
∂θs,ai = ∂ log πθi(a
′ i|s′)
∂θs,ai = 1{a′i = ai, s′ = s}
1
θs,ai
= 1{a′i = ai, s′ = s} 1
πθi(ai|s) Thus we have that:
∂Ji(θ) ∂θs,ai = 1 1− γ ∑ s′ ∑ a′ dθ(s ′)πθ(a ′|s′)1{a′i = ai, s′ = s} 1 πθ(ai|s) Qθi (s, a)
= 1 1− γ ∑ a′−i dθ(s)πθi(ai|s)πθ−i(a′−i|s) 1 πθ(ai|s) Qθi (s, ai, a ′ −i)
= 1
1− γ dθ(s) ∑ a′−i πθ−i(a ′ −i|s)Qθi (s, ai, a′−i)
= 1
1− γ dθ(s)Qθi (s, ai)

heading: E PROOFS OF LEMMA 3 AND THEOREM 1
text: Before giving proofs for Lemma 3 and Theorem 1, we first introduce the well-known the performance difference lemma (Kakade & Langford, 2002) in RL literature, which is helpful throughout. A proof is also provided for completeness.
Lemma 8. (Performance difference lemma) For policies πθ, πθ′ ,
Ji(θ ′)− Ji(θ) =
1
1− γ Es∼dθ′Ea∼πθ′A θ i (s, a), i = 1, 2, . . . , n (22)
Proof. (of performance difference lemma) From Bellman’s equation we have that:
Ji(θ ′)− Ji(θ) = Es0∼ρV θ
′
i (s0)− Es0∼ρV θi (s0) = ( Es∼ρEa∼πθ′ (·|s)Q θ i (s, a)− Es∼ρV θi (s) ) + ( Es∼ρV θ ′ i (s)− Es∼ρEa∼πθ′ (·|s)Q θ i (s, a) ) = Es∼ρEa∼πθ′ (·|s)A θ i (s, a) + γEs0∼ρ,s∼Prθ′ (s1=·|s0) [ V θ ′ i (s)− V θi (s) ]
= Es∼ρEa∼πθ′ (·|s)A θ i (s, a) + γEs0∼ρ,s∼Prθ′ (s1=·|s0)Ea∼πθ′ (·|s)A θ i (s, a) + γ2Es0∼ρ,s∼Prθ′ (s2=·|s0) [ V θ ′ i (s)− V θi (s) ]
= · · ·
= ∞∑ t=0 Es0∼ρ,s∼Prθ′ (st=·|s0)Ea∼πθ′γ tAθi (s, a)
= 1
1− γ Es∼dθ′Ea∼πθ′A θ i (s, a)
Proof. (Lemma 3) According to performance difference lemma Equation (22):
Ji(θ ′ i, θ−i)− Ji(θi, θ−i) =
1 1− γ ∑ s,a dθ′(s)πθ′(a|s)Aθi (s, a)
= 1 1− γ ∑ s,ai dθ′(s)πθ′i(ai|s) ∑ a−i πθ−i(a−i|s)Aθi (s, ai, a−i)
= 1 1− γ ∑ s,ai dθ′(s)πθ′i(ai|s)A θ i (s, ai).
(23)
According to the definition of ‘averaged’ advantage function:∑ ai πθi(ai|s)Aθi (s, ai) = 0, ∀s ∈ S
which implies:
max ai∈Ai Aθi (s, ai) ≥ 0,
thus we have that:
Ji(θ ′ i, θ−i)− Ji(θi, θ−i) =
1 1− γ ∑ s,ai dθ′(s)πθ′i(ai|s)A θ i (s, ai)
≤ 1 1− γ ∑ s dθ′(s) max ai∈Ai Aθi (s, ai)
= 1 1− γ ∑ s dθ′(s) dθ(s) dθ(s) max ai∈Ai Aθi (s, ai)
≤ 1 1− γ ∥∥∥∥dθ′dθ ∥∥∥∥ ∞ ∑ s dθ(s) max ai∈Ai Aθi (s, ai).
(24)
We can rewrite 11−γ ∑ s dθ(s) maxai∈Ai A θ i (s, ai) as:
1 1− γ ∑ s dθ(s) max ai∈Ai Aθi (s, ai) = 1 1− γ max θi∈Xi ∑ s,ai dθ(s)πθi(ai|s)A θ i (s, ai)
= max θi∈Xi ∑ s,ai (πθi(ai|s)− πθi(ai|s)) 1 1− γ dθ(s)Aθi (s, ai)
= max θi∈Xi ∑ s,ai (πθi(ai|s)− πθi(ai|s)) 1 1− γ dθ(s)Qθi (s, ai)
= max θi∈Xi
(θi − θi)>∇θiJi(θ).
(25)
Substituting this into Equation (24), we may conclude that
Ji(θ ′ i, θ−i)− Ji(θi, θ−i) ≤ ∥∥∥∥dθ′dθ ∥∥∥∥ ∞ max θi∈Xi (θi − θi)>∇θiJi(θ)
and this completes the proof.
Proof. (Theorem 1) The definition of a Nash equilibrium naturally implies first-order stationarity, because for any θi ∈ Xi:
Ji((1− η)θ∗i + ηθi, θ∗−i)− Ji(θ∗i , θ∗−i) = η(θi − θ)>∇θiJi(θ∗) + o(η‖θi − θ∗i ‖) ≤ 0, ∀ η > 0
Letting η → 0 gives the first-order stationary condition:
(θi − θ)>∇θiJi(θ∗) ≤ 0, ∀θi ∈ Xi,
It remains to be shown that all first-order stationary policies are Nash equilibria. From Assumption 1 we know that for any pair of parameters θ′, θ∗, ∥∥∥ dθ′dθ∗ ∥∥∥∞<+∞. Take θ′ = (θ′i, θ ∗ −i), θ ∗ = (θ∗i , θ ∗ −i). According to Lemma 3, we have that for any first-order stationary policy θ∗,
Ji(θ ′ i, θ ∗ −i)− Ji(θ∗i , θ∗−i) ≤ ∥∥∥∥ dθ′dθ∗ ∥∥∥∥ ∞ max θi∈Xi (θi − θ∗i )>∇θiJi(θ∗) ≤ 0,
which completes the proof.

heading: F PROOF OF THEOREM 2 AND LEMMA 4
text: Proof. (Lemma 4) For a given strict NE θ∗ randomly set:
a∗i (s) ∈ arg max ai Aθ ∗ i (s, ai),
and set θi be: θs,ai = 1{ai = a∗i (s)}. And set θ := (θi, θ∗−i) From performance difference lemma Equation (22):
Ji(θi, θ ∗ −i)− Ji(θ∗i , θ∗−i) = ∑ s,ai dθ(s)πθi(s, ai)A θ∗ i (s, ai)
= ∑ s dθ(s) max ai Aθ ∗ i (s, ai) ≥ 0
Because θ∗ is a strict NE, thus the inequality above forces θ∗i = θ, and that maxai A θ∗ i (s, ai) = 0. The uniqueness of θ∗ also implies uniqueness of a∗i (s), and thus,
Aθ ∗ i (s, ai) < 0, ∀ ai 6= a ∗ i (s),
which completes the proof of the lemma.
The proof of Theorem 2 relies on the following auxiliary lemma, whose proof we defer to Appendix M.
Lemma 9. Let X denote the probability simplex of dimension n. Suppose θ ∈ X , g ∈ Rn and that there exists i∗ ∈ {1, 2, . . . , n} and ∆ > 0 such that:
θi∗ ≥ θi, ∀i 6= i∗ gi∗ ≥ gi + ∆, ∀i 6= i∗.
Let θ′ = ProjX (θ + g),
then:
θ′i∗ ≥ min{1, θi∗ + ∆
2 }
Proof. (Theorem 2) For a fixed agent i and state s, the gradient play (Equation (5)) update rule of policy θi,s is given by:
θ (t+1) i,s = Proj∆(|Ai|)(θ (t) i,s +
η
1− γ dθ(t)(s)Q
θ(t) i (s, ·)), (26)
where ∆(|Ai|) denotes the probability simplex in |Ai|-th dimension and Qθ (t) i (s, ·)) is a |Ai|-th dimensional vector with ai-th element equals to Qθ (t)
i (s, ai)). We will show that this update rule satisfies the conditions in Lemma 9, which will then allow us to prove that
D(θ(t+1)||θ∗) ≤ max{0, D(θ(t)||θ∗)− η∆ θ∗
2 }.
Letting a∗i (s) be the same definition as Equation (9), we have that:
1
1− γ dθ(t)(s)Q
θ(t) i (s, a ∗ i (s))−
1
1− γ dθ(t)(s)Q
θ(t) i (s, ai)
≥ 1 1− γ dθ∗(s)Qθ ∗ i (s, a ∗ i (s))− 1 1− γ dθ∗ (s)Q θ∗ i (s, ai)
− ∣∣∣∣ 11− γ dθ∗(s)Qθ∗i (s, a∗i (s))− 11− γ dθ(t)(s)Qθ(t)i (s, a∗i (s)) ∣∣∣∣ − ∣∣∣∣ 11− γ dθ∗(s)Qθ∗i (s, ai)− 11− γ dθ(t)(s)Qθ(t)i (s, ai)
∣∣∣∣ ≥ 1
1− γ dθ∗(s)
( Aθ ∗ i (s, a ∗ i (s)−Aθ ∗ i (s, ai)) ) − 2‖∇θiJi(θ(t))−∇θiJi(θ∗)‖ (27)
≥∆θ ∗ − 4
(1− γ)3 ( n∑ i=1 |Ai| ) ‖θ(t) − θ∗‖ (28)
≥∆θ ∗ − 4
(1− γ)3 ( n∑ i=1 |Ai| ) n∑ i=1 ∑ s ‖θ(t)i,s − θ ∗ i,s)‖1
≥∆θ ∗ − 4
(1− γ)3 n|S| ( n∑ i=1 |Ai| ) D(θ(t)||θ∗),
where Equation (27) to Equation (28) uses smoothness property in Lemma 18.
We use proof of induction as supposed for ` ≤ t− 1, we have:
D(θ(`+1)||θ∗) ≤ max{D(θ(`)||θ∗)− η∆ θ∗
2 , 0},
thus
D(θ(t)||θ∗) ≤ D(θ(0)||θ∗) ≤ ∆ θ∗(1− γ)3 8n|S| ( ∑n i=1 |Ai|) .
Then we can further conclude that:
(1− γ)dθ(t)(s)Qθ (t) i (s, a ∗ i (s))− (1− γ)dθ(t)(s)Qθ (t) i (s, ai)
≥∆θ ∗ − 4
(1− γ)3 n|S| ( n∑ i=1 |Ai| ) D(θ(t)||θ∗)
≥∆ θ∗
2 , ∀ ai 6= a∗i (s)
Additionally, for D(θ(t)||θ∗) ≤ ∆ θ∗ (1−γ)3 8n|S|( ∑n i=1 |Ai|) , we may conclude:
θ (t) s,a∗i (s) ≥ 1/2 ≥ θ(t)s,ai ∀ai 6= a ∗ i (s),
then by applying Lemma 9 to Equation (26) we have:
θ (t+1) s,a∗i (s) ≥ min{1, θ(t)s,a∗i (s) + η∆θ
∗
4 }
=⇒ ‖θ(t+1)i,s − θ ∗ i,s‖1 = 2 ( 1− θ(t+1)s,a∗i (s) ) ≤ max{0, ‖θ(t)i,s − θ ∗ i,s‖1 − η∆θ ∗
2 }, ∀ s ∈ S, i = 1, 2, . . . , n
=⇒ D(θ(t+1)||θ∗) ≤ max{0, D(θ(t)||θ∗)− η∆ θ∗
2 },
which completes the proof.

heading: G PROOF OF PROPOSITION 1
text: Proof. First of all, from the definition of NE, the global maximum of the potential function is a NE. We now show that this global maximum is a deterministic policy. From classical results (e.g. (Sutton & Barto, 2018)) we know that there is an optimal deterministic centralized policy
π∗(a = (a1, . . . , an)|s) = 1{a = a∗(s) = (a∗1(s), . . . , a∗n(s))}
that maximizes:
π∗ = arg max π:S→∆(A) E [ ∞∑ t=0 γtφ(st, at) ∣∣π, s0 = s] .
We now show that this centralized policy can also be represented by direct distributed policy parameterization. Set θ∗ as:
πθ∗i (ai|s) = 1{ai = a ∗ i (s)},
then:
π∗(a|s) = n∏ i=1 πθ∗i (ai|s)
Since π∗ globally maximizes the discounted summation of potential function φ among centralized policies, which includes all possible direct distributedly parameterized policies, θ∗ also maximizes the total potential function Φ globally among all direct distributed parameterization, which completes the proof.

heading: H PROOF OF THEOREM 3
text: H.1 USEFUL OPTIMIZATION LEMMAS
Lemma 10. Let Φ(θ) be β-smooth in θ, define gradient mapping:
Gη(θ) := 1
η (ProjX (θ + η∇Φ(θ))− θ) .
The update rule for projected gradient is:
θ+ = θ + ηGη(θ) = ProjX (θ + η∇Φ(θ)). Then:
(θ′ − θ+)>∇Φ(θ+) ≤ (1 + ηβ)‖Gη(θ)‖‖θ′ − θ+‖ ∀θ′ ∈ X .
Proof. By a standard property of Euclidean projections onto a convex set, we get that
(θ + η∇Φ(θ)− θ+)>(θ′ − θ+) ≤ 0 =⇒ η∇Φ(θ)>(θ′ − θ+) + (θ − θ+)>(θ′ − θ+) ≤ 0 =⇒ η∇Φ(θ)>(θ′ − θ+)− ηGη(θ)>(θ′ − θ+) ≤ 0 =⇒ ∇Φ(θ)>(θ′ − θ+) ≤ ‖Gη(θ)‖θ′ − θ+‖ =⇒ ∇Φ(θ+)>(θ′ − θ+) ≤ ‖Gη(θ)‖θ′ − θ+‖+ (∇Φ(θ+)−∇Φ(θ))>(θ′ − θ+)‖
≤ ‖Gη(θ)‖θ′ − θ+‖+ β‖θ+ − θ‖‖θ′ − θ+‖ = (1 + ηβ)‖Gη(θ)‖θ′ − θ+‖
Lemma 11. (Sufficient ascent) Suppose Φ(θ) is β-smooth. Let θ+ = ProjX (θ + η∇Φ(θ)). Then for η ≤ 1β ,
Φ(θ+)− Φ(θ) ≥ η 2 ‖Gη(θ)‖2
Proof. From the smoothness property we have that:
Φ(θ+)− Φ(θ) ≥ ∇θΦ(θ)>(θ+ − θ)− β
2 ‖θ+ − θ‖2 (29)
Since θ+ = ProjX (θ + η∇Φ(θ)), we have that:
(θ + η∇Φ(θ)− θ+)>(θ′ − θ+) ≤ 0, ∀ θ′ ∈ X take θ′ = θ, we get:
∇Φ(θ)>(θ+ − θ) ≥ 1 η ‖θ+ − θ‖2.
Thus:
Φ(θ+)− Φ(θ) ≥ ∇θΦ(θ)>(θ+ − θ)− β
2 ‖θ+ − θ‖2
≥ ( 1 η − β 2 )‖θ+ − θ‖2
≥ 1 2η ‖θ+ − θ‖2 = η
2 ‖Gη(θ)‖2,
which completes the proof.
Lemma 12. (Corollary of Lemma 11) For Φ(θ) that is β smooth and bounded Φmin ≤ Φ(θ) ≤ Φmax, running projected gradient ascent:
θ(t+1) = ProjX (θ + η∇Φ(θ(t))) with η = 1β , will guarantee that:
lim t→+∞
‖Gη(θ(t))‖ = 0.
Further, we have that: 1
T T−1∑ t=0 ‖Gη(θ(t))‖2 ≤ 2β(Φmax − Φmin) T
(30)
Proof. From Lemma 11 we have:
Φ(θ(t+1))− Φ(θ(t)) ≥ 1 2β ‖Gη(θ(t))‖2 ≥ 0
Thus Φ(θ(t)) is non decreasing, and since it is bounded, we know that Φ(θ(t)) asymptotically convergence to some value Φ∗, and thus show that
lim t→∞
‖Gη(θ(t))‖ = 0.
Additionally, from Equation (30),
Φ(θ(T ))− Φ(θ(0)) ≥ T−1∑ t=0 1 2β ‖Gη(θ(t))‖2
=⇒ 1 T T−1∑ t=0 ‖Gη(θ(t))‖2 ≤ 2β(Φmax − Φmin) T ,
which completes the proof.
H.2 PROOF OF THEOREM 3
Proof. Recall the definition of gradient mapping:
Gη(θ) = 1
η (ProjX (θ + η∇Φ(θ))− θ) .
From gradient domination property Equation (8) we have that:
NE-gapi(θ (t+1)) = max
θ′i∈Xi Ji(θ
′ i.θ (t+1) −i )− Ji(θ (t+1) i , θ (t+1) −i )
≤ max θ′i∈Xi ∥∥∥∥∥ d(θ′i.θ(t+1)−i )d (θ
(t+1) i ,θ (t+1) −i ) ∥∥∥∥∥ ∞ max θi∈Xi ( θi − θ(t+1)i )> ∇θiJi(θ(t+1))
≤M max θi∈Xi
( θi − θ(t+1)i )> ∇θiΦ(θ(t+1))
≤M(1 + ηβ) max θi∈Xi ‖θi − θ(t+1)i ‖‖G η(θ(t))‖
≤M(1 + ηβ)2 √ |S|‖Gη(θ(t))‖
= 4M √ |S|‖Gη(θ(t))‖
where the last step follows as ‖θi − θ(t+1)i ‖ ≤ 2 √ |S|. Thus
NE-gap(θ(t+1)) ≤ 4M √ |S|‖Gη(θ(t))‖
Then from Lemma 12 we have that:
lim t→∞ ‖Gη(θ(t))‖ = 0 =⇒ lim t→∞ NE-gap(θ(t)) = 0,
and that:
1
T T−1∑ t=0 ‖Gη(θ(t))‖2 ≤ 2β(Φmax − Φmin) T
=⇒ 1 T T∑ t=1 NE-gap(θ(t))2 ≤ 32βM 2|S|(Φmax − Φmin) T
we can get our required bound of if we set:
32βM2|S|(Φmax − Φmin) T ≤ 2,
or equivalently
T ≥ 32M 2β(Φmax − Φmin)|S|
2
= 64M2(Φmax − Φmin)|S|
∑ i |Ai|
2(1− γ)3 ,
which completes the proof.

heading: I PROOF OF THEOREM 4
text: Proof. (of the first claim) The proof requires knowledge of Lemma 4 in Section 3 thus we would recommend readers to first go through Lemma 4 first. The lemma immediately leads to the conclusion that a strict NE θ∗ should be deterministic. Let a∗i (s),∆ θ∗ i (s),∆ θ∗
i be the same definition as Equation (9) Equation (10) respectively.
For any θ ∈ X , Taylor expansion suggests that:
Φ(θ)− Φ(θ∗) = (θ − θ∗)>∇Φ(θ∗) + o(‖θ − θ∗‖) = ∑ i (θi − θ∗i )>∇θiJi(θ∗) + o(‖θ − θ∗‖)
= 1 1− γ ∑ i ∑ s ∑ ai dθ∗(s)Aθ ∗ i (s, ai)(θs,ai − θ ∗ s,ai) + o(‖θ − θ ∗‖)
≤ − 1 1− γ ∑ i ∑ s dθ∗(s)∆ θ∗ i (s)  ∑ ai6=a∗i (s) (θs,ai − θ∗s,ai) + o(‖θ − θ∗‖) = − 1
1− γ ∑ i ∑ s dθ∗(s)∆ θ∗ i (s) 1 2 ‖θi,s − θ∗i,s‖1 + o(‖θ − θ∗‖)
≤ −∆ θ∗
2 ∑ i ∑ s ‖θi,s − θ∗i,s‖1 + o(‖θ − θ∗‖)
≤ −∆ θ∗
2 ‖θ − θ∗‖+ o(‖θ − θ∗‖).
Thus for ‖θ − θ∗‖ sufficiently small,
Φ(θ)− Φ(θ∗) < 0 holds,
this suggests that strict NEs are strict local maxima. We now show that this also holds vice versa.
Strict local maxima satisfy first-order stationarity by definition, and thus by Theorem 1 they are also NEs, we only need to show that they are strict. We prove by contradiction, suppose that there exists a local maximum θ∗ such that it is non-strict NE, i.e., there exists θ′i ∈ Xi, θ′i 6= θ∗i such that:
Ji(θ ′ i, θ ∗ −i) = Ji(θ ∗ i , θ ∗ −i)
According to Equation (25) and first-order stationarity of θ∗:
1 1− γ ∑ s dθ∗(s) max ai∈Ai Aθ ∗ i (s, ai) = max θi∈Xi (θi − θ∗i )>∇θiJi(θ∗) ≤ 0.
Since maxai∈Ai Aθi (s, ai) ≥ 0 for all θ, we may conclude:
max ai∈Ai
Aθ ∗ i (s, ai) = 0, ∀ s ∈ S.
We denote θ′ := (θ′i, θ−i∗), according to Equation (23)
0 = Ji(θ ′ i, θ ∗ −i)− Ji(θ∗i , θ∗−i) =
1 1− γ ∑ s,ai dθ′(s)πθ′i(ai|s)A θ∗ i (s, ai) ≤ 0.
Since dθ′(s) > 0, ∀ s, this further implies that∑ ai πθ′i(ai|s)A θ∗ i (s, ai) = 0, ∀ s ∈ S,
i.e., πθ′i(ai|s) is nonzero only if A θ∗ i (s, ai) = 0. Define θ η i := ηθ ′ i + (1− η)θ∗i , then∑
ai
πθηi (ai|s)A θ∗ i (s, ai) = 0, ∀ s ∈ S.
Thus let θη := (θηi , θ ∗ −i)
Ji(θ η i , θ ∗ −i)− Ji(θ∗i , θ∗−i) =
1 1− γ ∑ s,ai dθη (s)πθηi (ai|s)A θ∗ i (s, ai) = 0.
Since ‖θηi − θ∗i ‖ → 0 as η → 0, this contradicts the assumption that θ∗ is a strict local maximum. This suggests that all strict local maxima are strict NEs, which completes the proof.
Proof. (of the second claim) First, we define the corresponding value function, Q-function and advantage function for potential function φ.
V θφ (s) := E [ ∞∑ t=0 γtφ(st, at) ∣∣ π = θ, s0 = s]
Qθφ(s, a) := [ ∞∑ t=0 γtφ(st, at) ∣∣ π = θ, s0 = s, a0 = a]
Aθφ(s, a) := Q θ φ(s, a)− V θφ (s).
For an index set I ⊆ {1, 2, . . . , n} we define the following averaged advantage potential function of index set I as: Aθφ,I(s, aI) := ∑ a−I Aθφ(s, aI , a−I). We choose an index set I ⊆ {1, 2, . . . , n} such that there exists s∗, a∗I such that:
Aθ ∗ φ,I(s ∗, a∗I) > 0, (31)
and that for any other index set I ′ with smaller cardinality:
Aθ ∗ φ,I′(s, aI′) ≤ 0, ∀ s, aI′ , ∀ |I ′| < |I|. (32)
Because Φ is not a constant, this guarantees the existence of such an index set I. Further, since∑ aI′ πθ∗I′ (aI ′ |s)Aθ∗φ,I′(s, aI′) = 0, ∀ s,
and that θ∗ is fully-mixed, we have that:
Aθ ∗ φ,I′(s, aI′) = 0, ∀ s, aI′ , ∀ |I ′| < |I|. (33)
We set θ := (θI , θ∗−I), where θI is a convex combination of θ ∗ I , θ ′ I ∈ X :
θI = (1− η)θ∗I + ηθ′I , η > 0.
According to performance difference lemma Equation (22) we have: (1− γ) ( Φ(θI , θ ∗ −I)− Φ(θ∗I , θ∗−I) ) = ∑ s,aI dθ(s)πθI (aI |s)Aθ ∗ φ,I(s, aI)
= ∑ s,aI dθ(s) ∏ i∈I ( (1− η)πθ∗i (ai|s) + ηπθ′i(ai|s) ) Aθ ∗ φ,I(s, aI)
= ∑ s,aI dθ(s) ( (1−η)πθ∗i0 (ai0 |s) + ηπθ′i0 (ai0 |s) ) ∏ i∈I\{i0} ( (1−η)πθ∗i (ai|s) + ηπθ′i(ai|s) ) Aθ ∗ φ,I(s, aI), (∀ i0 ∈ I)
= (1− η) ∑ s,aI dθ(s) ∏ i∈I\{i0} ( (1−η)πθ∗i (ai|s) + ηπθ′i(ai|s) ) Aθ ∗ φ,I\{i0}(s, aI\{i0})
+ η ∑ s,aI dθ(s)πθ′i0 (ai0 |s) ∏ i∈I\{i0} ( (1− η)πθ∗i (ai|s) + ηπθ′i(ai|s) ) Aθ ∗ φ,I(s, aI).
According to Equation (33), we know that:
Aθ ∗
φ,I\{i0}(s, aI\{i0}) = 0,
thus (1− γ) ( Φ(θI , θ ∗ −I)− Φ(θ∗I , θ∗−I) ) =
η ∑ s,aI dθ(s)πθ′i0 (ai0 |s) ∏ i∈I\{i0} ( (1− η)πθ∗i (ai|s) + ηπθ′i(ai|s) ) Aθ ∗ φ,I(s, aI).
Applying similar procedures recursively and using the fact that:
Aθ ∗
φ,I\{i}(s, aI\{i}) = 0, ∀ i ∈ I, we get:
Φ(θI , θ ∗ −I)− Φ(θ∗I , θ∗−I) =
η|I| 1− γ ∑ s,aI dθ(s) ∏ i∈I πθ′i(ai|s)A θ∗ φ,I(s, aI).
Set πθ′i(ai|s) as:
πθ′i(ai|s ∗) =
{ 1 ai = a ∗ i
0 otherwise
πθ′i(ai|s) = πθ∗i (ai|s), s 6= s ∗,
where s∗, a∗i are defined in Equation (31). Then:
Φ(θI , θ ∗ −I)− Φ(θ∗I , θ∗−I) =
η|I|
1− γ dθ(s
∗)Aθ ∗ φ,I(s ∗, a∗I) > 0,
which completes the proof.

heading: J BOUNDING THE GRADIENT ESTIMATION ERROR OF ALGORITHM 1
text: The accuracy of gradient estimation is essential in the sample-based algorithm 1. In this section, we will give a high probability bound of the estimation error, which is stated in the following theorem: Theorem 6. (Error bound for gradient estimation) Assume that the stochastic game that satisfies Assumption 3. In Algorithm 1, for
TJ ≥ 32τ(1 + α)2|S|3
∑ i |Ai|maxi |Ai|2
(1− γ)6 2gα2σ2S log
( 16τTG|S|2 ∑ i |Ai|
δ
) + 1,
with probability at least 1− δ, we have: ‖∇̂Φ(θ(k))−∇Φ(θ(k))‖2 ≤ g, ∀ 0 ≤ k ≤ TG − 1.
The proof of the theorem includes bounding the estimation error of Qθi (J.1) and dθ (J.2). Let’s first introduce the definition of ‘sufficient exploration’ which is going to play an important role in this section.
In the main text Assumption 3 we have introduced (τ, σS)-sufficient exploration on states. In this section we introduce a similar definition (τ, σ)-sufficient exploration: Definition 6. ((τ, σ)-Sufficient Exploration) A stochastic game and a policy θ is said to satisfy (τ, σ)-sufficient exploration condition if there exists positive integer τ and σ ∈ (0, 1) such that for policy θ and any initial state-action pair (s, ai), ∀i, we have
Pr(sτ , ai,τ |s0 = s, a0 = a) ≥ σ, ∀sτ , ai,τ
Note that ‘(τ, σ)-sufficient exploration’ is a stronger condition compared with ‘(τ, σS)-sufficient exploration on states’. Additionally it is not hard to verify that for any stochastic game that satisfies (τ, σS)-sufficient exploration on states, and any θ ∈ Xα, it will also satisfy (τ, ασSmaxi |Ai| )-sufficient exploration condition.
J.1 BOUNDING THE ESTIMATION ERROR OF THE AVERAGED-Q FUNCTION
We first state the main theorem in this subsection: Theorem 7. (Estimation error of averaged Q-functions) Assume that the stochastic game with policy θ satisfies (σ, τ)-sufficient exploration condition (Definition 6), then for a fixed i, running Algorithm 1 will guarantee that:
Pr ( ‖Q̂θi −Qθi ‖∞ ≥ ) ≤ 4τ |S|2|Ai| exp ( − (1− γ)4 2σ2bTτ c 32|S|2 ) ,
further:
Pr ( ‖Q̂θi −Qθi ‖∞ ≥ , ∃ i ) ≤ 8τ |S|2 ( n∑ i=1 |Ai| ) exp ( − (1− γ)4 2σ2bTτ c 32|S|2 ) ,
i.e., when
TJ ≥ 32τ |S|2
(1− γ)4 2σ2 log
( 8τ |S|2| ∑ i |Ai|
δ
) + τ
with probability at least 1− δ, ‖Q̂θi −Qθi ‖∞ ≤ , ∀ i
In the following, we will introduce some lemmas which will play an important role in bounding the estimation error of the averaged-Q function: Lemma 13. Assume that the stochastic game with policy θ satisfies (σ, τ)-sufficient exploration condition (Definition 6), then fix s′, s, ai,for ≤ 1,
Pr (∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ ≥ ) ≤ 4τ exp ( − 2σ2bTτ c
32
)
Proof. According to the definition of P̂ θi , we have that{ P̂ θi (s ′|s, ai)− P θi (s ′|s, ai) ≥ } ⊆
{ T−1∑ t=0 ( 1{st+1 = s′, st = s, ai,t = ai} − (P θi (s ′|s, ai) + )1{st = s, ai,t = ai} ) ≥ 0 }
∪ { T−1∑ t=0 1{st = s, ai,t = ai} = 0 }
⊆ τ−1 ∪ m=0  bT−1−mτ c∑ k=0 ( 1{skτ+m+1 = s′, skτ+m = s, ai,kτ+m = ai}−(P θi (s ′|s, ai) + )1{skτ+m = s, ai,kτ+m = ai} ) ≥ 0  τ−1 ∪ m=0  bT−1−mτ c∑ k=0 1{skτ+m = s, ai,kτ+m = ai} = 0
 Let:
Am :=  bT−1−mτ c∑ k=0 ( 1{skτ+m+1 =s′, skτ+m=s, ai,kτ+m=ai} − (P θi (s ′|s, ai) + )1{skτ+m=s, ai,kτ+m=ai} ) ≥ 0  A′m :=  bT−1−mτ c∑ k=0 1{skτ+m = s, ai,kτ+m = ai} = 0
 Xk,m := 1{skτ+m+1 = s′, skτ+m = s, ai,kτ+m = ai} − (P θi (s
′|s, ai) + )1{skτ+m = s, ai,kτ+m = ai} X ′k,m := 1{skτ+m = s, ai,kτ+m = ai}
Yk,m := Xk,m − E[Xk,m|F(k−1)τ+m] Y ′k,m := X ′ k,m − E[X ′k,m|F(k−1)τ+m]
Then {Yk,m} bT−1−mτ c k=0 is a martingale difference sequence. Because ≤ 1, it is easy to verify that |Xk,m| ≤ 2, |X ′k,m| ≤ 1. We have that:
|Yk,m| ≤ |Xk,m|+ E[|Xk,m||F(k−1)τ+m] ≤ 4, |Y ′k,m| ≤ |X ′k,m|+ E[|X ′k,m||F(k−1)τ+m] ≤ 2.
Further,
E[X ′k,m|F(k−1)τ+m] = E[1{skτ+m = s, ai,kτ+m = ai}|F(k−1)τ+m] ≥ σ,
and that
E[Xk,m|F(k−1)τ+m]
= E[1{skτ+m+1 = s′, skτ+m = s, ai,kτ+m = ai} − (P θi (s ′|s, ai) + )1{skτ+m = s, ai,kτ+m = ai}|F(k−1)τ+m] (34) = − E[1{skτ+m = s, ai,kτ+m = ai}|F(k−1)τ+m] ≤ − σ. (35)
To move from equation (34) to equation (35), we used the fact that: E[1{st+1 = s′, st = s, ai,t+m = ai}|Ft−1] = P (s|st−1, at−1) ∑ a−i πθ(ai, a−i|s)P (s′|s, ai, a−i)
= P (s|st−1, at−1)πθi(ai|s) ∑ a−i πθ−i(a−i|s)P (s′|s, ai, a−i)
= P (s|st−1, at−1)πθi(ai|s)P θi (s ′|s, ai)
= E[P θi (s ′|s, ai)1{st = s, ai,t+m = ai}|Ft−1]
and the inequality in equation (35) is derived directly from Definition 6.
According to Azuma-Hoeffding inequality (Hoeffding, 1994; Azuma, 1967):
Pr(Am) = Pr bT−1−mτ c∑ k=0 Xk,m ≥ 0  = Pr
bT−1−mτ c∑ k=0 Yk,m ≥ − bT−1−mτ c∑ k=0 E[Xk,m|F(k−1)τ+m]  ≤ Pr
bT−1−mτ c∑ k=0 Yk,m ≥ ⌊ T − 1−m+ τ τ ⌋ σ  ≤ exp ( − 2σ2 ⌊ T τ ⌋ 32
) Similarly, from Azuma-Hoeffding inequality,
Pr(A′m) = Pr bT−1−mτ c∑ k=0 X ′k,m = 0  = Pr
bT−1−mτ c∑ k=0 Y ′k,m = − bT−1−mτ c∑ k=0 E[X ′k,m|F(k−1)τ+m]  ≤ Pr
bT−1−mτ c∑ k=0 Y ′k,m ≤ − ⌊ T − 1−m+ τ τ ⌋ σ 
≤ exp ( − σ2 ⌊ T τ ⌋ 8 ) (36)
Thus
Pr ( P̂ θi (s ′|s, ai)− P θi (s ′|s, ai) ≥ ) ≤ τ−1∑ m=0 Pr (Am) + Pr (A ′ m)
≤ τ exp ( − 2σ2 ⌊ T τ ⌋ 32 ) + τ exp ( − σ2 ⌊ T τ ⌋ 8 ) ≤ 2τ exp ( − 2σ2 ⌊ T τ ⌋ 32 ) Similarly
Pr ( P̂ θi (s ′|s, ai)− P θi (s ′|s, ai) ≤ − ) ≤ 2τ exp ( − 2σ2 ⌊ T τ ⌋ 32 )
=⇒ Pr (∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ ≥ ) ≤ 4τ exp ( − 2σ2 ⌊ T τ ⌋ 32 ) which completes the proof.
Lemma 14. Assume that the stochastic game with policy θ satisfies (σ, τ)-sufficient exploration condition (Definition 6), then fix s′, s, ai, for ≤ 1,
Pr (∣∣∣r̂θi (s, ai)− rθi (s, ai)∣∣∣ ≥ ) ≤ 4τ exp ( − 2σ2bTτ c
32
)
Proof. The proof is similar to Lemma 13.{ r̂θi (s, ai)− rθi (s, ai) ≥ } ⊆
{ T∑ t=0 1{st = s, ai,t = ai}ri(st, at)− (rθi (s, ai) + )1{st = s, ai,t = ai} ≥ 0 }
∪ { T−1∑ t=0 1{st = s, ai,t = ai} = 0 }
⊆ τ−1 ∪ m=0  bT−mτ c∑ k=0 1{skτ+m = s, ai,kτ+m = ai}ri(skτ+m, akτ+m)− (rθi (s, ai) + )1{skτ+m = s, ai,kτ+m = ai} ≥ 0  τ−1 ∪ m=0  bT−1−mτ c∑ k=0 1{skτ+m = s, ai,kτ+m = ai} = 0
 Let:
Am :=  bT−mτ c∑ k=0 1{skτ+m = s, ai,kτ+m = ai}ri(skτ+m, akτ+m)− (rθi (s, ai) + )1{skτ+m = s, ai,kτ+m = ai} ≥ 0  A′m :=  bT−1−mτ c∑ k=0 1{skτ+m = s, ai,kτ+m = ai} = 0
 Xk,m := 1{skτ+m = s, ai,kτ+m = ai}ri(skτ+m, akτ+m)− (rθi (s, ai) + )1{skτ+m = s, ai,kτ+m = ai} Yk,m := Xk,m − E[Xk,m|F(k−1)τ+m]
Then {Yk,m} bT−1−mτ c k=0 is a martingale difference sequence. Because ≤ 1, it is easy to verify that |Xk,m| ≤ 2. We have that: |Yk,m| ≤ |Xk,m|+ E[|Xk,m||F(k−1)τ+m] ≤ 4.
Further,
E[Xk,m|F(k−1)τ+m]
= E[1{skτ+m = s, ai,kτ+m = ai}ri(skτ+m, akτ+m)− (rθi (s, ai) + )1{skτ+m = s, ai,kτ+m = ai}|F(k−1)τ+m] = − E[1{skτ+m = s, ai,kτ+m = ai}|F(k−1)τ+m] ≤ − σ
the second line to the third line of the equation is derived by the fact that: E[1{st = s, ai,t+m = ai}ri(st, at)|Ft−1] = P (s|st−1, at−1) ∑ a−i πθ(ai, a−i|s)ri(s, ai, a−i)
= P (s|st−1, at−1)πθi(ai|s)rθi (s, ai)
= E[rθi (s, ai)1{st = s, ai,t = at}|Ft−1] and the inequality in the third line is derived directly from Definition 6.
According to Azuma-Hoeffding inequality:
Pr(Am) = Pr bT−mτ c∑ k=0 Xk,m ≥ 0  = Pr
bT−mτ c∑ k=0 Yk,m ≥ − bT−mτ c∑ k=0 E[Xk,m|F(k−1)τ+m]  ≤ Pr
bT−mτ c∑ k=0 Yk,m ≥ ⌊ T −m+ τ τ ⌋ σ  ≤ exp ( − 2σ2 ⌊ T τ ⌋ 32
) Same as Equation (36), we have that:
Pr(A′m) ≤ exp
( − σ2 ⌊ T τ ⌋ 8 ) Thus
Pr ( r̂θi (s, ai)− rθi (s, ai) ≥ ) ≤ τ−1∑ m=0 Pr (Am) + Pr (A ′ m) ≤ 2τ exp ( − 2σ2 ⌊ T τ ⌋ 32 ) Similarly
Pr ( r̂θi (s, ai)− rθi (s, ai) ≤ − ) ≤ 2τ exp ( − 2σ2 ⌊ T τ ⌋ 32 )
=⇒ Pr (∣∣∣r̂θi (s, ai)− rθi (s, ai)∣∣∣ ≥ ) ≤ 4τ exp ( − 2σ2 ⌊ T τ ⌋ 32 ) which completes the proof.
Lemma 13 and 14 lead to the following corollary: Corollary 1.
Pr(‖M̂θi −Mθi ‖∞ ≥ ) ≤ 4τ |S| 2|Ai| exp ( − 2σ2bTτ c 32|S|2 ) (37)
Pr(‖r̂θi − rθi ‖∞ ≥ ) ≤ 4τ |S||Ai| exp
( − 2σ2bTτ c
32
) (38)
Proof. We first prove Equation (37)
‖M̂θi −Mθi ‖∞ = max (s,ai) ∑ (s′,a′i) πθi(a ′ i|s′) ∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ = max
(s,ai) ∑ s′ ∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ Thus, {
‖M̂θi −Mθi ‖∞ ≥ }
= ∪ (s,ai) {∑ s′ ∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ ≥ }
⊆ ∪ (s,ai) ∪ s′ {∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ ≥ |S| }
Then according to Lemma 13, Pr ( ‖M̂θi −Mθi ‖∞ ≥ ) ≤ ∑ (s′,s,ai) Pr (∣∣∣P̂ θi (s′|s, ai)− P θi (s′|s, ai)∣∣∣ ≥ |S| )
≤ 4τ |S|2|Ai| exp ( − 2σ2bTτ c 32|S|2 ) .
Now we prove Equation (38). Since{ ‖r̂θi − rθi ‖∞ ≥ } = ∪
(s,ai) {∣∣∣r̂θi (s, ai)− rθi (s, ai)∣∣∣ ≥ } , according to Lemma 14,
Pr ( ‖r̂θi − rθi ‖∞ ≥ ) ≤ ∑
(s,ai)
Pr (∣∣∣r̂θi (s, ai)− rθi (s, ai)∣∣∣ ≥ )
≤ 4τ |S||Ai| exp ( − 2σ2 ⌊ T τ ⌋ 32 ) ,
which completes the proof of the corollary.
We are now ready to prove Theorem 7.
Proof. (of Theorem 7) From the definition of Q̂θi , Q θ i ,
Qθi = (I − γMθi ) −1rθi ,
Q̂θi = (I − γM̂θi ) −1r̂θi ,
we have that ‖Q̂θi −Qθi ‖∞ = ∥∥∥(I − γM̂θi )−1r̂θi − (I − γMθi )−1rθi ∥∥∥∞
= ∥∥∥(I − γMθi )−1(r̂θi − rθi ) + ((I − γM̂θi )−1 − (I − γMθi )−1) r̂θi ∥∥∥∞
≤ ∥∥∥(I − γMθi )−1(r̂θi − rθi )∥∥∥∞ + ∥∥∥γ(I − γMθi )−1(M̂θi −Mθi )(I − γM̂θi )−1r̂θi ∥∥∥∞ .
Because both Mθi and M̂ θ i are transition probability matrices, thus:
‖Mθi x‖∞ ≤ ‖x‖∞
‖M̂θi x‖∞ ≤ ‖x‖∞
‖(I − γMθi ) −1x‖∞ ≤
1
1− γ ‖x‖∞
‖(I − γM̂θi ) −1x‖∞ ≤
1
1− γ ‖x‖∞
Thus, ‖Q̂θi −Qθi ‖∞ ≤ ∥∥∥(I − γMθi )−1(r̂θi − rθi )∥∥∥∞ + ∥∥∥γ(I − γMθi )−1(M̂θi −Mθi )(I − γM̂θi )−1r̂θi ∥∥∥∞
≤ 1 1− γ ‖r̂θi − rθi ‖∞ + γ (1− γ)2 ‖M̂θi −Mθi ‖∞‖r̂θi ‖∞
≤ 1 1− γ ‖r̂θi − rθi ‖∞ + γ (1− γ)2 ‖M̂θi −Mθi ‖∞
Thus if
‖r̂θi − rθi ‖∞ ≤ (1− γ) 2 , ‖M̂θi −Mθi ‖∞ ≤ (1− γ) 2 ,
we have that: ‖Q̂θi −Qθi ‖∞ ≤ ,
Thus from Corollary 1, Pr ( ‖Q̂θi −Qθi ‖∞ ≥ ) ≤ Pr ( ‖r̂θi − rθi ‖∞ ≥ (1− γ) 2 ) + Pr ( ‖M̂θi −Mθi ‖∞ ≥ (1− γ) 2 )
≤ 4τ |S||Ai| exp ( −
(1− γ)4 2σ2bTτ c 32
) + 4τ |S|2|Ai| exp ( −
(1− γ)4 2σ2bTτ c 32|S|2
)
≤ 8τ |S|2|Ai| exp ( −
(1− γ)4 2σ2bTτ c 32|S|2
) ,
which completes the proof.
J.2 BOUNDING THE ESTIMATION ERROR OF dθ
We first state our main result:
Theorem 8. (Estimation error of dθ) Under Assumption 3,
Pr ( ‖d̂θ − dθ‖1 ≥ ) ≤ 4τ |S|2 exp ( − (1− γ)2 2σ2S ⌊ T τ ⌋ 32γ2|S|2 ) ,
i.e., when
T ≥ 32τ |S| 2
(1− γ)2 2σ2S log ( 4τ |S|2| δ ) + 1,
with probability at least 1− δ, ‖d̂θ − dθ‖1 ≤ .
Similar to the previous section, the proof of the theorem begins by bounding the estimation error |P̂ θS(s′|s)− P θS(s′|s)|. Lemma 15. Under Assumption 3, fix s′, s, ai,for ≤ 1,
Pr (∣∣∣P̂ θS(s′|s)− P θS(s′|s)∣∣∣ ≥ ) ≤ 4τ exp ( − 2σ2S ⌊ T τ ⌋ 32 )
Proof. According to the definition of P̂ θS , we have that{ P̂ θS(s ′|s)− P θS(s ′|s) ≥ } ⊆
{ T−1∑ t=0 ( 1{st+1 = s′, st = s} − (P θS(s ′|s) + )1{st = s} ) ≥ 0 } ∪ { T−1∑ t=0 1{st = s} = 0 }
⊆ τ−1 ∪ m=0  bT−1−mτ c∑ k=0 ( 1{skτ+m+1 = s′, skτ+m = s} − (P θS(s ′|s) + )1{skτ+m = s} ) ≥ 0  τ−1 ∪ m=0  bT−1−mτ c∑ k=0 1{skτ+m = s} = 0
 Let:
Am :=  bT−1−mτ c∑ k=0 ( 1{skτ+m+1 = s′, skτ+m = s} − (P θS(s ′|s) + )1{skτ+m = s} ) ≥ 0  A′m :=  bT−1−mτ c∑ k=0 1{skτ+m = s} = 0
 Xk,m := 1{skτ+m+1 = s′, skτ+m = s} − (P θS(s
′|s) + )1{skτ+m = s} X ′k,m := 1{skτ+m = s} Yk,m := Xk,m − E[Xk,m|F(k−1)τ+m] Y ′k,m := X ′ k,m − E[X ′k,m|F(k−1)τ+m]
Then {Yk,m} bT−1−mτ c k=0 is a martingale difference sequence. Because ≤ 1, it is easy to verify that |Xk,m| ≤ 2, |Xk,m| ≤ 1. We have that: |Yk,m| ≤ |Xk,m|+ E[|Xk,m||F(k−1)τ+m] ≤ 4, |Y ′k,m| ≤ |X ′k,m|+ E[|X ′k,m||F(k−1)τ+m] ≤ 2.
Further, E[X ′k,m|F(k−1)τ+m] = E[1{skτ+m = s}|F(k−1)τ+m] ≥ σS , and that
E[Xk,m|F(k−1)τ+m]
= E[1{skτ+m+1 = s′, skτ+m = s} − (P θS(s ′|s) + )1{skτ+m = s}|F(k−1)τ+m]
= − E[1{skτ+m = s}|F(k−1)τ+m] ≤ − σS the second line to the third line of the equation is derived by the fact that:
E[1{st+1 = s′, st = s}|Ft−1] = P (s|st−1, at−1) ∑ a πθ(a|s)P (s′|s, a)
= P (s|st−1, at−1)P θS(s ′|s)
= E[P θS(s ′|s)1{st = s}|Ft−1]
and the inequality in the third line is derived directly from Assumption 3.
According to Azuma-Hoeffding inequality:
Pr(Am) = Pr bT−1−mτ c∑ k=0 Xk,m ≥ 0  = Pr
bT−1−mτ c∑ k=0 Yk,m ≥ − bT−1−mτ c∑ k=0 E[Xk,m|F(k−1)τ+m]  ≤ Pr
bT−1−mτ c∑ k=0 Yk,m ≥ ⌊ T − 1−m+ τ τ ⌋ σS  ≤ exp ( − 2σ2S ⌊ T τ ⌋ 32 )
Similarly, from Azuma-Hoeffding inequality,
Pr(A′m) = Pr bT−1−mτ c∑ k=0 X ′k,m = 0  = Pr
bT−1−mτ c∑ k=0 Y ′k,m = − bT−1−mτ c∑ k=0 E[X ′k,m|F(k−1)τ+m]  ≤ Pr
bT−1−mτ c∑ k=0 Y ′k,m ≤ − ⌊ T − 1−m+ τ τ ⌋ σS  ≤ exp ( − σ2S ⌊ T τ ⌋ 8
) Thus
Pr ( P̂ θS(s ′|s)− P θS(s ′|s) ≥ ) ≤ τ−1∑ m=0 Pr (Am) + Pr (A ′ m)
≤ τ exp ( − 2σ2S ⌊ T τ ⌋ 32 ) + τ exp ( − σ2S ⌊ T τ ⌋ 8 ) ≤ 2τ exp ( − 2σ2S ⌊ T τ ⌋ 32 ) Similarly
Pr ( P̂ θS(s ′|s)− P θS(s ′|s) ≤ − ) ≤ 2τ exp ( − 2σ2S ⌊ T τ ⌋ 32 )
=⇒ Pr (∣∣∣P̂ θS(s′|s)− P θS(s′|s)∣∣∣ ≥ ) ≤ 4τ exp ( − 2σ2S ⌊ T τ ⌋ 32 ) which completes the proof.
Corollary 2.
Pr (∥∥∥P̂ θS − P θS∥∥∥∞ ≥ ) ≤ 4τ |S|2 exp ( − 2σ2SbTτ c 32|S|2 ) (39)
Proof. ∥∥∥P̂ θS − P θS∥∥∥∞ = maxs ∑ s′ ∣∣∣P̂ θS(s′|s)− P θS(s′|s)∣∣∣ Thus, {∥∥∥P̂ θS − P θS∥∥∥∞ ≥ } = ∪s {∑ s′ ∣∣∣P̂ θS(s′|s)− P θS(s′|s)∣∣∣ ≥ }
⊆ ∪ s ∪ s′ {∣∣∣P̂ θS(s′|s)− P θS(s′|s)∣∣∣ ≥ |S| }
Then according to Lemma 15, Pr ( ‖ ∥∥∥P̂ θS − P θS∥∥∥∞ ≥ ) ≤ ∑
(s′,s)
Pr (∣∣∣P̂ θS(s′|s)− P θS(s′|s)∣∣∣ ≥ |S| )
≤ 4τ |S|2 exp ( − 2σ2SbTτ c 32|S|2 ) .
which completes the proof of the corollary.
Proof. (Proof of Theorem 8)
‖d̂θ − dθ‖1 = (1− γ)‖ (( I − γP̂ θS > )−1 − ( I − γP θS > )−1) ρ‖1
≤ (1− γ) ∥∥∥∥∥ ( I − γP̂ θS > )−1 − ( I − γP θS > )−1∥∥∥∥∥
1
‖ρ‖1
≤ (1− γ) ∥∥∥∥(I − γP̂ θS)−1 − (I − γP θS)−1∥∥∥∥
∞ ‖ρ‖1 = γ(1− γ) ∥∥∥∥(I − γP θS)−1 (P̂ θS − P θS)(I − γP̂ θS)−1∥∥∥∥
∞
≤ γ 1− γ ∥∥∥P̂ θS − P θS∥∥∥∞ Thus
Pr ( ‖d̂θ − dθ‖1 ≥ ) ≤ Pr (∥∥∥P̂ θS − P θS∥∥∥∞ ≥ 1− γγ )
≤ 4τ |S|2 exp ( − (1− γ)2 2σ2S ⌊ T τ ⌋ 32γ2|S|2 )
J.3 PROOF OF THEOREM 6
Proof. Since the stochastic game satisfies (τ, σS)-sufficient exploration on states, then for any θ ∈ Xα, we know that it satisfies (τ, ασSmaxi |Ai| )-sufficient exploration. Substitute this into Theorem 7, we have that for
TJ ≥ 32τ(1 + α)2|S|3
∑ i |Ai|maxi |Ai|2
(1− γ)6 2gα2σ2S log
( 16τTG|S|2 ∑ i |Ai|
δ
) + 1, (40)
with probability at least 1− δ2TG ,
‖Qθ(k) − Q̂θ(k)‖∞ ≤ (1− γ) g (1 + α) √ |S| ∑ i |Ai| .
Similarly, applying Theorem 8, we have that with probability at least 1− δ2TG ,
‖dθ(k) − d̂θ(k)‖1 ≤ (1− γ)2 gα (1 + α) √ |S| ∑ i |Ai| .
Since:∣∣∣∣[∇Φ(θ)− ∇̂Φ(θ)] (s,ai) ∣∣∣∣ = ∣∣∣∣ 11− γ dθ(s)Qθi (s, ai)− 11− γ d̂θ(s)Q̂θi (s, ai) ∣∣∣∣
= ∣∣∣∣ 11− γ dθ(s)(Qθi (s, ai)− Q̂θi (s, ai)) ∣∣∣∣+ ∣∣∣∣ 11− γ Q̂θi (s, ai)(dθ(s)− d̂θ(s)) ∣∣∣∣ ≤ 1
1− γ |Qθi (s, ai)− Q̂θi (s, ai)|+
1
(1− γ)2 |dθ(s)− d̂θ(s)|
≤ g (1 + α) √ |S| ∑ j |Aj | + gα (1 + α) √ |S| ∑ j |Aj | = g√
|S| ∑ j |Aj |
Thus, with probability 1− δ ‖∇Φ(θ(k) − ∇̂Φ(θ(k))‖22 = ∑ i ∑ s ∑ ai ∣∣∣∣[∇Φ(θ)− ∇̂Φ(θ)] (s,ai) ∣∣∣∣2 ≤ 2g, ∀ 1 ≤ k ≤ TG

heading: K PROOF OF THEOREM 5
text: Notations: We define the following variables that will be useful in the analysis:
Ĝη(θ) := 1
η
( ProjX (θ + η∇̂Φ(θ))− θ ) Ĝη,α(θ) := 1
η
( ProjXα(θ + η∇̂Φ(θ))− θ ) .
K.1 OPTIMIZATION LEMMAS
Lemma 16. (Sufficient ascent) Suppose Φ(θ) is β-smooth. Let θ+ = ProjXα(θ + η∇̂Φ(θ)). Then for η ≤ 12β ,
Φ(θ+)− Φ(θ) ≥ η 4 ‖Ĝη,α(θ)‖2 − η 2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 Proof. From the smoothness property we have that:
Φ(θ+)− Φ(θ) ≥ ∇θΦ(θ)>(θ+ − θ)− β
2 ‖θ+ − θ‖2
Since θ+ = ProjXα(θ + η∇̂Φ(θ)), we have that:
(θ + η∇̂Φ(θ)− θ+)>(θ′ − θ+) ≤ 0, ∀ θ′ ∈ Xα
take θ′ = θ, we get:
∇̂Φ(θ)>(θ+ − θ) ≥ 1 η ‖θ+ − θ‖2.
Thus:
∇Φ(θ)>(θ+ − θ) = ( ∇Φ(θ)− ∇̂Φ(θ) )> (θ+ − θ) + ∇̂Φ(θ)>(θ+ − θ)
≥ −η 2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 − 1 2η ∥∥θ+ − θ∥∥2 + ∇̂Φ(θ)>(θ+ − θ) ≥ −η
2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 − 1 2η ∥∥θ+ − θ∥∥2 + 1 η ‖θ+ − θ‖2
= 1 2η ‖θ+ − θ‖2 − η 2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 Thus from equation (29):
Φ(θ+)− Φ(θ) ≥ ( 1
2η − β 2
) ‖θ+ − θ‖2 − η
2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 ≥ 1
4η ‖θ+ − θ‖2 − η 2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 = η
4 ‖Ĝη,α(θ)‖2 − η 2 ∥∥∥∇Φ(θ)− ∇̂Φ(θ)∥∥∥2 which completes the proof.
Lemma 16 immediately results in the following corollary:
Corollary 3. (of Lemma 16) In Algorithm 1, suppose ‖∇̂Φ(θ(k)) − ∇Φ(θ(k))‖∞ ≤ g holds for every 0 ≤ k ≤ TG − 1, then running algorithm 1 will guarantee that:
1
TG TG−1∑ k=0 ‖Ĝη,α(θ(k))‖2 ≤ 4(Φmax − Φmin) ηTG + 2 2g
Proof. From Lemma 16 we have that:
Φ(θ(k+1))− Φ(θ(k)) ≥ η 4 ‖Ĝη,α(θ(k))‖2 − η 2 ∥∥∥∇Φ(θ(k))− ∇̂Φ(θ(k))∥∥∥2 ≥ η
4 ‖Ĝη,α(θ(k))‖2 − η 2 2g.
Thus
1
TG TG−1∑ k=0 ‖Ĝη,α(θ(k))‖2 ≤ 4(Φ(θ (0))− Φ(θ(TG))) ηTG + 2 2g
≤ 4(Φmax − Φmin) ηTG + 2 2g
Lemma 17. (First-order stationarity and ‖Ĝη,α(θ)‖) Suppose Φ(θ) is β-smooth. Let θ+ = ProjXα(θ + η∇̂Φ(θ)). Then:
∇θΦ(θ+)>(θ′−θ+) ≤ [ (1 + ηβ)‖Ĝη,α(θ)‖+ ‖∇̂Φ(θ)−∇Φ(θ)‖ ] ‖θ′−θ+‖, ∀θ′ ∈ Xα. (41)
Further:
max θi∈Xi
∇θiΦ(θ+)>(θi− θ+i ) ≤ 2 √ |S| [ (1 + ηβ)‖Ĝη,α(θ)‖+ ‖∇̂Φ(θ)−∇Φ(θ)‖ ] + 2α
1− γ (42)
Proof. Since θ+ = ProjXα(θ + η∇̂Φ(θ)), we have:
(θ + η∇̂Φ(θ)− θ+)>(θ′ − θ+) ≤ 0 ∀ θ′ ∈ Xα
=⇒ η∇̂Φ(θ)>(θ′ − θ+) ≤ (θ − θ+)>(θ′ − θ+) =⇒ η∇Φ(θ)>(θ′ − θ+) ≤ (θ − θ+)>(θ′ − θ+) + η(∇Φ(θ)− ∇̂Φ(θ))>(θ′ − θ+)
=⇒ η∇Φ(θ+)>(θ′ − θ+) ≤ (θ − θ+)>(θ′ − θ+) + η(∇Φ(θ)− ∇̂Φ(θ))>(θ′ − θ+) + η(∇Φ(θ+)−∇Φ(θ))>(θ′ − θ+)
=⇒ η∇Φ(θ+)>(θ′ − θ+) ≤ (‖θ − θ+‖+ η‖∇Φ(θ)− ∇̂Φ(θ)‖+ η‖∇Φ(θ+)−∇Φ(θ)‖)‖θ′ − θ+‖ ≤ (‖θ − θ+‖+ η‖∇Φ(θ)− ∇̂Φ(θ)‖+ ηβ‖θ+ − θ‖)‖θ′ − θ+‖
= [ (1 + ηβ)‖θ − θ+‖+ η‖∇Φ(θ)− ∇̂Φ(θ)‖ ] ‖θ′ − θ+‖
=⇒ ∇Φ(θ+)>(θ′ − θ+) ≤ [ (1 + ηβ)‖Ĝη,α(θ)‖+ ‖∇Φ(θ)− ∇̂Φ(θ)‖ ] ‖θ′ − θ+‖,
which proves equation (41). We now prove equation (42). For any θ′i,s ∈ ∆(|Ai|), we know that (1− α)θ′i,s + αU|Ai| ∈ ∆α(|Ai|). Let Ui := [U|Ai|, . . . , U|Ai|︸ ︷︷ ︸
|S|times
], then for any θ′i ∈ Xi, (1− α)θ′i +
αUi ∈ Xαi . Thus:
∇θiΦ(θ+)>(θ′i − θ+i ) ≤ ∇θiΦ(θ +)>((1− α)θ′i + αUi − θ+i ) +∇θiΦ(θ +)>(θ′i − (1− α)θ′i − αUi) ≤ [ (1 + ηβ)‖Ĝη,α(θ)‖+ ‖∇̂Φ(θ)−∇Φ(θ)‖ ] ‖(1− α)θ′i + αUi − θ+i ‖
+∇θiΦ(θ+)>(θ′i − (1− α)θ′i − αUi) ≤ 2 √ |S| [ (1 + ηβ)‖Ĝη,α(θ)‖+ ‖∇̂Φ(θ)−∇Φ(θ)‖ ] + α∇θiΦ(θ+)>(θ′i − Ui)
Since
∇θiΦ(θ+)>(θ′i − Ui) = ∑ s dθ(s)Qθi,s > (θ′i,s − U|Ai|)
≤ ∑ s dθ(s)‖Qθi,s‖∞‖θ ′ i,s − U|Ai|‖1
≤ ∑ s dθ(s) 2 1− γ ≤ 2 1− γ ,
we have that: ∇θiΦ(θ+)>(θ′i − θi) ≤ 2 √ |S| [ (1 + ηβ)‖Ĝη,α(θ)‖+ ‖∇̂Φ(θ)−∇Φ(θ)‖ ] + 2α
1− γ
K.2 PROOF OF THEOREM 5 Proof. Recall that Φ is β-smooth with β = 2(1−γ)3 ( ∑n i=1 |Ai|). The step size η in Theorem 5 satisfies η ≤ (1−γ) 3
4 ∑n i=1 |Ai| = 12β .
Recall from gradient domination property:
NE-gapi(θ (k+1)) = max
θ′i∈Xi Ji(θ
′ i, θ (k+1) −i )− Ji(θ (k+1) i , θ (k+1) −i )
≤M max θ′i∈Xi (θ′i − θ (k+1) i ) >∇θiΦ(θ(k+1))
Suppose ‖∇̂Φ(θ(k))−∇Φ(θ(k))‖∞ ≤ g, ∀0 ≤ k ≤ TG − 1, recall from Lemma 17,
NE-gap(θ(k+1)) ≤ max i NE-gapi(θ (k+1)) ≤M max i max θ′i∈Xi (θ′i − θ (k+1) i ) >∇θiΦ(θ(k+1))
≤ 2M √ |S| [ (1 + ηβ)‖Ĝη,α(θ(k))‖+ g ] + 2αM
1− γ Thus,
1
TG TG−1∑ k=0 NE-gap(θ(k+1))2 ≤ 1 TG TG−1∑ k=0 3× [ 4M2|S|(1 + ηβ)2‖Ĝη,α(θ(k))‖2 + 4M2|S| 2g + 4α2M2 (1− γ)2 ]
= 12M2|S| 2g + 12α2M2
(1− γ)2 + 12M2|S|(1 + ηβ)2
( 1
TG TG−1∑ k=0
‖Ĝη,α(θ(k))‖2 )
From Corollary 3, we have that
1
TG TG−1∑ k=0 NE-gap(θ(k+1))2 ≤ 12M2|S| 2g + 12α2M2 (1− γ)2 + 12M2|S|(1 + ηβ)2 ( 4(Φmax − Φmin) ηTG + 2 2g ) ≤ 66M2|S| 2g + 12α2M2
(1− γ)2 + 108M2|S|(Φmax − Φmin) ηTG
(43)
Substitute
α = (1− γ)
6M , g = 2 √ 33M √ |S| and TG ≥ 648M2(Φmax − Φmin)|S| η 2
into the above inequality we get that:
1
TG TG−1∑ k=0 NE-gap(θ(k+1))2 ≤ 2 2 + 2 3 + 2 6 = 2
Substitute the value of α, g in Equation (43) into Theorem 6 will give us:
TJ ≥ 206976τnM4|S|3 maxi |Ai|3
(1− γ)8 4σ2S log
( 16τTG|S|2 ∑ i |Ai|
δ
) + 1
which completes the proof.

heading: L SMOOTHNESS
text: Lemma 18. (Smoothness for Direct Distributed Parameterization) Assume that 0 ≤ ri(s, a) ≤ 1, ∀s, a, i = 1, 2, . . . , n, then:
‖g(θ′)− g(θ)‖ ≤ 2 (1− γ)3 ( n∑ i=1 |Ai| ) ‖θ′ − θ‖, (44)
where g(θ) = {∇θiJi(θ)}.
The proof of Lemma 18 depends on the following lemma:
Lemma 19.
‖∇θiJi(θ′)−∇θiJi(θ)‖ ≤ 2 (1− γ)3 √ |Ai| n∑ j=1 √ |Aj |‖θ′j − θj‖ (45)
Lemma 18 is a simple corollary of Lemma 19.
Proof. (Proof of Lemma 18)
‖g(θ′)− g(θ)‖2 = n∑ i=1 ‖∇θiJi(θ′)−∇θiJi(θ)‖2
≤ (
2
(1− γ)3 )2∑ i |Ai|  n∑ j=1 √ |Aj |‖θ′j − θj‖ 2
≤ (
2
(1− γ)3 )2∑ i |Ai|  n∑ j=1 |Aj |  n∑ j=1 ‖θ′j − θj‖2 
=
( 2
(1− γ)3 )2( n∑ i=1 |Ai| )2 ‖θ′ − θ‖2,
which completes the proof.
Lemma 19 is equivalent to the following lemma:
Lemma 20.∣∣∣∣∂Ji(θ′i + αui, θ′−i)− ∂Ji(θi + αui, θ−i)∂α ∣∣∣α=0 ∣∣∣∣ ≤ 2(1− γ)3√|Ai| n∑ j=1 √ |Aj |‖θ′j−θj‖, ∀‖u‖ = 1
(46)
Proof. (Lemma 20) Define:
πi,α(ai|s) := πθi+αui(ai|s) = θs,ai + αuai,s π′i,α(ai|s) := π′θi+αui(ai|s) = θ ′ s,ai + αuai,s
πα(a|s) := πθi+αui(ai|s)πθ−i(a−i|s) π′α(a|s) := πθ′i+αui(ai|s)π ′ θ−i(a−i|s)
Qαi (s, a) := Q(θi+αui,θ−i)(s, a)
d′α(s) := d(θ′i+αui,θ−i)(s)
According to cost difference lemma,∣∣∣∣∂Ji(θ′i + αui, θ′−i)− ∂Ji(θi + αui, θ−i)∂α ∣∣∣α=0 ∣∣∣∣
= 1
1− γ
∣∣∣∣∂ ∑ s,a dα′(s)π ′ α(a|s)Aαi (s, a)
∂α
∣∣∣ α=0 ∣∣∣∣ = 1
1− γ
∣∣∣∣∂ ∑ s,a dα′(s) (π ′ α(a|s)− πα(a|s))Qαi (s, a)
∂α
∣∣∣ α=0 ∣∣∣∣ ≤ 1
1− γ  ∣∣∣∣∣∑ s,a d′θ(s) ∂π′α(a|s)− ∂πα(a|s) ∂α ∣∣∣ α=0 Qθi (s, a)
∣∣∣∣∣︸ ︷︷ ︸ Part A
+ ∣∣∣∣∣∑ s,a d′θ(s)(π ′ θ(a|s)− πθ(a|s)) ∂Qαi (s, a) ∂α ∣∣∣ α=0 ∣∣∣∣∣︸ ︷︷ ︸ Part B
+ ∣∣∣∣∣∑ s,a ∂d′α(s) ∂α ∣∣∣ α=0 (π′θ(a|s)− πθ(a|s))Qθi (s, a) ∣∣∣∣∣︸ ︷︷ ︸ Part C  Thus:
Part A = ∣∣∣∣∣∑ s,a d′θ(s) ∂π′α(a|s)− ∂πα(a|s) ∂α ∣∣∣ α=0 Qθi (s, a) ∣∣∣∣∣ =
∣∣∣∣∣∑ s,a d′θ(s)uai,s(πθ′−i(a−i|s)− πθ−i(a−i|s))Q θ i (s, a) ∣∣∣∣∣ (47) ≤ 1
1− γ ∣∣∣∣∣∣ ∑ s d′θ(s) ∑ ai |uai,s| ∑ a−i ∣∣∣πθ′−i(a−i|s)− πθ−i(a−i|s)∣∣∣ ∣∣∣∣∣∣ (48)
≤ 1 1− γ ( max s ∑ ai |uai,s| )∑ s d′θ(s)2dTV(πθ′−i(·|s)||πθ−i(·|s)) (49)
≤ 1 1− γ ( max s ∑ ai |uai,s| )∑ s d′θ(s) ∑ j 6=i 2dTV(πθ′j (·|s)||πθj (·|s)) (50)
= 1
1− γ ( max s ∑ ai |uai,s| )∑ s d′θ(s) ∑ j 6=i ‖θ′j,s − θj,s‖1 (51)
≤ 1 1− γ
√ |Ai| ∑ s d′θ(s) ∑ j 6=i √ |Aj |‖θ′j,s − θj,s‖ (52)
≤ 1 1− γ
√ |Ai| ∑ j 6=i √ |Aj | √∑ s dθ′(s)2 √∑ s ‖θ′j,s − θj,s‖2 (53)
= 1 1− γ √ |Ai| ∑ j 6=i √ |Aj | √∑ s dθ′(s)2‖θ′j − θj‖
≤ 1 1− γ
√ |Ai| ∑ j 6=i √ |Aj |‖θ′j − θj‖
≤ 1 1− γ
√ |Ai| n∑ j=1 √ |Aj |‖θ′j − θj‖,
where Equation (47) to Equation (48) is derived from the fact that |Qθi (s, a)| ≤ 11−γ . Equation (49) to Equation (50) relies on the property of total variation distance:
dTV(πθ′−i(·|s)||πθ−i(·|s)) ≤ ∑ j 6=i dTV(πθ′j (·|s)||πθj (·|s))
Equation (51) to Equation (52) is derived from:
max s ∑ ai |uai,s| ≤ √ |Ai|, ‖u‖ ≤ 1
‖θ′j,s − θj,s‖1 ≤ √ |Aj |‖θ′j,s − θj,s‖
which can be immediately verified by applying Cauchy-Schwarz inequality.
Before looking into Part B, we first define P̃ (α) as the state-action under πα:[ P̃ (α) ] (s,a)→(s′,a′) = πα(a ′|s′)P (s′|s, a)
Then we have that: [ ∂P̃ (α)
∂α ∣∣∣ α=0 ] (s,a)→(s′,a′) = ua′i,s′πθ−i(a ′ −i|s′)P (s′|s, a)
For an arbitrary vector x:[ ∂P̃ (α)
∂α ∣∣∣ α=0 x ] (s,a) = ∑ s′,a′ ua′i,s′πθ−i(a ′ −i|s′)P (s′|s, a)xs′,a′
≤ ‖x‖∞ ∑ s′,a′ |ua′i,s′ |πθ−i(a ′ −i|s′)P (s′|s, a)
= ‖x‖∞ ∑ s′ P (s′|s, a) ∑ a′i |ua′i,s′ | ∑ a′−i πθ−i(a ′ −i|s′)
≤ ‖x‖∞ ∑ s′ P (s′|s, a) √ |Ai| ∑ a′−i πθ−i(a ′ −i|s′)
≤ √ |Ai|‖x‖∞
Thus: ∥∥∥∥∥∥ [ ∂P̃ (α) ∂α ∣∣∣ α=0 x ] (s,a) ∥∥∥∥∥∥ ∞ ≤ √ |Ai|‖x‖∞
Similarly we can define P̃ (α)′ as the state-action under π′α, and can easily check that∥∥∥∥∥∥ [ ∂P̃ (α)′ ∂α ∣∣∣ α=0 x ] (s,a) ∥∥∥∥∥∥ ∞ ≤ √ |Ai|‖x‖∞
Define: M(α) := ( I − γP̃ (α) )−1 , M(α)′ := ( I − γP̃ (α)′ )−1 .
Because:
M(α) = ( I − γP̃ (α) )−1 = ∞∑ n=0 γnP̃ (α),
which implies that every entry of M(α) is nonnegative and M(α)1 = 11−γ1, this implies:
‖M(α)x‖∞ ≤ 1
1− γ ‖x‖∞,
and similarly
‖M(α)′x‖∞ ≤ 1
1− γ ‖x‖∞.
Now we are ready to bound Part B. Because:
Qαi (s, a) = e > (s,a)M(α)ri
=⇒ ∂Q α i (s, a)
∂α = e>(s,a)
∂M(α)
∂α ri = γe
> (s,a)M(α)
∂P̃ (α)
∂α M(α)ri =⇒ ∣∣∣∣∂Qαi (s, a)∂α ∣∣∣∣ ≤ γ ∥∥∥∥∥M(α)∂P̃ (α)∂α M(α)ri ∥∥∥∥∥ ∞
≤ γ (1− γ)2
√ |Ai|
Thus,
Part B = ∣∣∣∣∣∑ s,a d′θ(s)(π ′ θ(a|s)− πθ(a|s)) ∂Qαi (s, a) ∂α ∣∣∣ α=0 ∣∣∣∣∣ ≤ ∑ s,a d′θ(s) |π′θ(a|s)− πθ(a|s)| ∣∣∣∣∂Qαi (s, a)∂α ∣∣∣α=0
∣∣∣∣ ≤ γ (1− γ)2 √ |Ai| ∑ s d′θ(s)2dTV(πθ′(·|s)||πθ(·|s)) ≤ γ (1− γ)2 √ |Ai| ∑ s d′θ(s) ∑ j 2dTV(πθ′j (·|s)||πθj (·|s))
= γ (1− γ)2 √ |Ai| ∑ s d′θ(s) ∑ j ‖θ′j,s − θj,s‖1
≤ γ (1− γ)2
√ |Ai| ∑ s d′θ(s) n∑ j=1 √ |Aj |‖θ′j,s − θj,s‖
≤ γ (1− γ)2
√ |Ai| n∑ j=1 √ |Aj | √∑ s d′θ(s) 2 √∑ s ‖θ′j,s − θj,s‖2
≤ γ (1− γ)2
√ |Ai| n∑ j=1 √ |Aj |‖θ′j − θj‖
Now let’s look at Part C: d′α(s) = (1− γ) ∑ s′ ρ(s′) ∑ a′ π′α(a ′|s′)e>(s′,a′)M(α) ′ ∑ a′′ e(s,a′′)
=⇒ ∂d ′ α(s)
∂α = (1− γ)  ∑ s′ ρ(s′) ∑ a′ ∂π′α(a ′|s′) ∂α e>(s′,a′)︸ ︷︷ ︸
v>1
M(α)′ ∑ a′′ e(s,a′′)
+ ∑ s′ ρ(s′) ∑ a′ π′α(a ′|s′)e>(s′,a′)︸ ︷︷ ︸
v>2
∂M(α)′
∂α ∑ a′′ e(s,a′′)  = (1− γ) ( v>1 M(α) ′ + γv>2 M(α) ′ ∂P̃ (α)
∂α M(α)′ )∑ a′′ e(s,a′′)
Note that v1, v2 are constant vectors that are independent of the choice of s. Additionally:
‖v1‖1 = ∥∥∥∥∥∑ s ρ(s) ∑ a ∂π′α(a|s) ∂α e(s,a) ∥∥∥∥∥ 1
= ∑ s ρ(s) ∑ a ∣∣∣∣∂π′α(a|s)∂α ∣∣∣∣
= ∑ s ρ(s) ∑ a |uai,s|πθ′−i(a−i|s)
≤ ∑ s ρ(s) ∑ a |uai,s| ≤ √ |Ai|
‖v2‖1 = ‖ ∑ s ρ(s) ∑ a π′α(a|s)e(s,a)‖1
= ∑ s ρ(s) ∑ a π′α(a|s) = 1
Thus:
Part C = ∣∣∣∣∣∑ s,a ∂d′α(s) ∂α ∣∣∣ α=0 (π′θ(a|s)− πθ(a|s))Qθi (s, a) ∣∣∣∣∣ = (1− γ)
∣∣∣∣∣∣∣∣∣∣ ( v>1 M(0) ′ + γv>2 M(0) ′ ∂P̃ (α) ∂α ∣∣∣ α=0 M(0)′ )∑ s,a ∑ a′ e(s,a′)(π ′ θ(a|s)− πθ(a|s))Qθi (s, a)︸ ︷︷ ︸
v3 ∣∣∣∣∣∣∣∣∣∣ ≤ (1− γ) ( 1
1− γ ‖v1‖1‖v3‖∞ +
γ (1− γ)2 √ |Ai|‖v2‖1‖v3‖∞ ) ≤ √ |Ai|
1− γ ‖v3‖∞
Additionally: ∣∣[v3](s0,a0)∣∣ = ∣∣∣∣∣∑ a (πθ′(a|s0)− πθ(a|s0))Qθi (s0, a) ∣∣∣∣∣ ≤ 1
1− γ ∑ a |πθ′(a|s0)− πθ(a|s0)|
= 1
1− γ 2dTV(πθ′(·|s0)||πθ(·|s0))
≤ 1 1− γ n∑ j=1 2dTV(πθ′j (·|s0)||πθj (·|s0))
= 1
1− γ n∑ j=1 ‖θ′j,s − θj,s‖1
≤ 1 1− γ n∑ j=1 √ |Aj |‖θ′j,s − θj,s‖
≤ 1 1− γ n∑ j=1 √ |Aj |‖θ′j − θj‖
Combining the above inequalities we get: Part C ≤ √ |Ai|
1− γ ‖v3‖∞ ≤
√ |Ai|
(1− γ)2 n∑ j=1 √ |Aj |‖θ′j − θj‖
Sum up Part A-C we get:∣∣∣∣∂Ji(θ′i + αui, θ′−i)− ∂Ji(θi + αui, θ−i)∂α ∣∣∣α=0 ∣∣∣∣ ≤ 11− γ (Part A + Part B + Part C) ≤ 2 (1− γ)3 √ |Ai| n∑ j=1 √ |Aj |‖θ′j − θj‖,
which completes the proof.

heading: M AUXILIARY
text: We recall Lemma 9. Lemma 9. Let X denote the probability simplex of dimension n. Suppose θ ∈ X , g ∈ Rn and that there exists i∗ ∈ {1, 2, . . . , n} and ∆ > 0 such that:
θi∗ ≥ θi, ∀i 6= i∗
gi∗ ≥ gi + ∆, ∀i 6= i∗. Let θ′ = ProjX (θ + g), then:
θ′i∗ ≥ min{1, θi∗ + ∆
2 }
Proof. Let y = θ + g, without loss of generality, assume that i∗ = 1 and that: y1 > y2 ≥ y3 ≥ · · · ≥ yn.
Using KKT condition, one can derive an efficient algorithm for solving ProjX (y) (Wang & CarreiraPerpiñán, 2013), which consists of the following steps:
1. Find ρ := max{1 ≤ j ≤ n : yj + 1j ( 1− ∑j i=1 yi ) > 0};
2. Set λ := 1ρ (1− ∑ρ i=1 yi);
3. Set θ′i = max{yi + λ, 0}.
From the algorithm, we have that:
λ = 1
ρ
( 1−
ρ∑ i=1 yi
) = 1
ρ
( 1−
ρ∑ i=1 (θi + gi)
)
= 1
ρ
( 1−
ρ∑ i=1 θi ) − 1 ρ ρ∑ i=1 gi
≥ −1 ρ ρ∑ i=1 gi.
If ρ ≥ 2,
θ′1 = max{y1 + λ, 0} ≥ y1 + λ ≥ θ1 + g1 − 1
ρ ρ∑ i=1 gi
≥ θ1 + (1− 1
ρ )g1 −
1
ρ ρ∑ i=2 (g1 −∆) = θ1 + ρ− 1 ρ ∆ ≥ θ1 + ∆ 2 .
If ρ = 1, θ′1 = y1 + λ = y1 + (1− y1) = 1. Thus: θ′1 ≥ min{1, θ1 + ∆
2 },
which completes the proof.

heading: N NUMERICAL SIMULATION DETAILS
text: Verification of the fully mixed NE in Game 2 We now verify that joining network 1 with probability 1−3 3(1−2 ) ,i.e.:
πθi(ai = 1|s) = 1− 3
3(1− 2 ) , ∀s ∈ S, i = 1, 2,
is indeed a NE. First, observe that Prθ(si,t+1 = 1) = (
1− 3 3(1− 2 )
) P (si,t+1 = 1|ai,t = 1) + ( 1− 1− 3
3(1− 2 )
) P (si,t+1 = 1|ai,t = 2)
=
( 1− 3
3(1− 2 )
) (1− ) + ( 1− 1− 3
3(1− 2 )
) = 1
3 .
Thus,
V (s) = r(s) + ∞∑ t=1 Estγtr(st) = r(s) + 2γ 3(1− γ) ,
Qθi (s, ai) = r(s) + γ ∑ s′,a−i P (s′|ai, a−i)πθ−i(a−i|s)V (s′)
= r(s) + γ ∑
s′i∈{1,2}
(P (s′i|ai)Prθ(s−i = 1)r(si, s−i = 1) + P (s′i|ai)Prθ(s−i = 2)r(si, s−i = 2)) + 2γ2
3(1− γ)
= r(s) + γP (s′i = 1|ai) ( 1
3 r(s′i = 1, s−i = 1) +
2 3 r(s′i = 1, s−i = 2) ) + γP (s′i = 2|ai) ( 1
3 (s′i = 2, s−i = 1) +
2 3 r(s′i = 2, s−i = 2)
) + 2γ2
3(1− γ)
= r(s) + 2
3 γ +
2γ2
3(1− γ) = r(s) +
2γ
3(1− γ) = V (s),
which implies that: (θ′i − θi)>∇θiJi(θ) = 0, ∀θ′i ∈ Xi, i = 1, 2,
i.e. θ satisfies first-order stationarity. Since dθ(s) > 0 holds for any valid θ, by Theorem 1, θ is a NE.
Computation of strict NEs in Game 2 The computation of strict NEs is done numerically, using the criterion in Lemma 4. We enumerate over all 28 possible deterministic policies and check whether the conditions in Lemma 4 hold. For = 0.1, γ = 0.95, and an initial distribution set as:
ρ(s1 = i, s2 = j) = 1/4, i, j ∈ {1, 2},
the numerical calculation shows there exist 13 different strict NEs.

Review summaries:
The paper studies the global convergence of policy gradient for multiagent Markov potential games. The authors define a notion of potential markov games that seems natural and show convergence to Nash policies when the agents use gradient ascent independently on their policies (using direct parametrization). Observe that the authors assume that the agents have full knowledge of their utilities and their derivatives (their algorithm is deterministic). They also provide convergence for the stochastic variant of policy gradient (given samples). They moreover show that deterministic Nash policies always exist and show that fully mixed policies are saddle points. Saddle points might be of higher order, so first order methods might fail to avoid the fully mixed policies because you need to check third (or higher) order derivatives (so techniques from Ge et al do not help to show avoidance as claimed, the authors need to remove that comment since Ge et al argue about second order stationarity).

This paper studies the optimization landscape of first-order methods in stochastic games. In particular, it studies the connections between first-order stationary points and Nash equilibrium and its convergent property and learning stability. For general-sum SGs, local convergence results is provided. For Markov potential games, global convergence results are provided. 

The authors study independent gradient play in Stochastic Games, with multiple players/agents. They characterize the (local) stability of strict Nash in Stochastic Games. In addition they study Markov Potential Games, a subclass of Stochastic Games and show global convergence of projected gradient ascent for direct paramterization of Tabular MDPs. In addition, they also provide a sample-based RL algorithm, where the players do not use gradient information from others and estimate based on the observed trajectories. They show non-asymptotic convergence guarantees of this algorithm for Tabular MDPs which are Markov Potential Games.