Year: 2021

Abstract:
Potential games are one of the most important and widely studied classes of normalform games. They define the archetypal setting of multi-agent coordination in which all agents utilities are perfectly aligned via a common potential function. Can we embed this intuitive framework in the setting of Markov games? What are the similarities and differences between multi-agent coordination with and without state dependence? To answer these questions, we study a natural class of Markov Potential Games (MPGs) that generalizes prior attempts to capture complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over since MPGs involve Markov games with zero-sum stategames, but Markov games in which all state-games are potential games are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main result, we prove convergence of independent policy gradient and its stochastic counterpart to Nash policies at a rate that is polynomial in the approximation error by adapting single-agent gradient domination properties to multi-agent settings. This answers questions on the convergence of finite-sample, independent policy gradient methods beyond settings of pure conflicting or pure common interests.

heading: 1 INTRODUCTION
text: Multi-agent reinforcement learning (MARL) has been the fundamental driver of numerous recent advances in Artificial Intelligence (AI) and Machine Learning (ML) ranging from super-human performance in competitive game-playing (Silver et al., 2016; 2018; Brown & Sandholm, 2019; Jaderberg et al., 2019) and multi-tasking (Mnih et al., 2015; OpenAI, 2018; Vinyals et al., 2019) to robotics, autonomous-driving and cyber-physical systems (Busoniu et al., 2008; Zhang et al., 2019). However, despite the popularity of MARL algorithms to analyze these systems in practice, the theory that underpins their empirical success lags behind (Dafoe et al., 2020). Many state-of-the-art theoretical results concern single-agent RL systems, typically modelled as single-agent Markov Decision Processes (MDPs) (Bertsekas, 2000; Panait & Luke, 2005; Sutton & Barto, 2018).
The main challenge when transitioning from single to multi-agent RL settings is the computation of Nash policies. For n ≥ 2 agents, a Nash policy is defined to be a profile of policies (π∗1 , ..., π∗n) so that by fixing the policies of all agents but i, π∗i is optimal for the resulting single-agent MDP and this is true for all 1 ≤ i ≤ n 1 (Definition 1). In multi-agent settings, Nash policies may not be unique in principle and, unlike singe-agent MDPs, agents’ rewards may differ dramatically between them.
A common approach to compute Nash policies in MDPs is the use of policy gradient methods. The significant progress in the analysis of such methods (see Agarwal et al. (2020) and references therein) has mainly concerned the single-agent case or the case of pure common interests (identical agents) (Wang & Sandholm, 2002; Panait & Luke, 2005): the convergence properties of policy gradient in general MARL settings remain poorly understood. Recent steps towards a theory for multi-agent settings involve Daskalakis et al. (2020) who show convergence of independent policy gradient to the optimal policy for two-agent zero-sum stochastic games, Wei et al. (2021) who improve the result of Daskalakis et al. (2020) using optimistic policy gradient and Zhao et al. (2021) who study extensions of Natural Policy Gradient using function approximation. It is worth noting that the positive results
1Analogue of Nash equilibrium notion.
of Daskalakis et al. (2020); Wei et al. (2021) and Zhao et al. (2021) depend on the fact that two-agent stochastic zero-sum games satisfy the min-max equals max-min property (Shapley, 1953).
If we move away from the extremes of single-agent or purely competitive settings (two-agents, zero-sum), a lot of these regularities, and in particular the value-uniqueness property, cease to hold. However, building a theory to analyze problems of cooperation between two or more agents constitutes a primary open challenge for the fields of AI and ML (Dafoe et al., 2020; Dafoe et al., 2021). Based on the above, our work is motivated by the following natural question:
Can we get (provable) convergence guarantees for multi-agent RL settings in which agents have aligned incentives, i.e., in which coordination is desirable?
Model and Informal Statement of Results. To make progress in this direction, we study a class of n-agent MDPs that naturally generalize normal form potential games (Monderer & Shapley, 1996), the archetypal model of interactions between multiple agents with aligned, yet not necessarily identical interests, called Markov Potential Games (MPGs). In words, a multi-agent MDP is an MPG as long as there exists a (state-dependent) real-valued potential function Φ so that if an agent i changes their policy (and the rest of the agents keep their policy unchanged), the difference in agent i’s value/utility, V i, is captured by the difference in the value of Φ (Definition 2).
Our first task is to understand the structural properties of MPGs and their Nash policies. Rather surprisingly, many insights from normal-form potential games do not carry over as MPGs involve settings with purely competitive (zero-sum) interactions at some states. Moreover, Markov games in which every state-interaction is a potential game are not necessarily MPGs. These findings suggest that MPGs form a class of MDPs with rich structure which challenges our intuition on the nature of cooperation in state-based interactions. On the other hand, MPGs trivially include MDPs of pure common interests (MDPs in which agents have identical rewards) and showcase intuitively expected properties such as the existence of deterministic Nash policies. Our structural results are as follows. Theorem 1.1 (Structural Properties of MPGs). The following facts are true for MPGs with n-agents. (a) There always exists a deterministic Nash policy profile (see Theorem 3.1). (b) We can construct MDPs for which each state is a (normal-form) potential game but which are not MPGs. This can be true regardless of whether the whole MDP is competitive or cooperative in nature (see Examples 1 and 2, respectively). On the opposite side, we can construct MDPs that are MPGs, but which include states that are purely competitive (i.e., zero-sum games), see Figure 3. (c) We provide sufficient conditions so that an MDP is an MPG. These include cases where each state is a (normal-form) potential game and the transition probabilities are not affected by agents actions or the reward functions satisfy certain regularity conditions between different states (see conditions C1 and C2 in Proposition 3.2).
We then turn to our motivating question above and, in our main contribution, we answer it in the affirmative. We show that if every agent i independently runs (with simultaneous updates) projected gradient ascent (PGA) on their policy (using their value V i), then, after O(1/ 2) iterations, the system will reach an -approximate Nash policy. Here, independence means that (PGA) requires only local information to determine the updates, i.e., each agent’s own rewards, actions, and view of the environment. Such protocols are naturally motivated in distributed settings where all information about type of interaction and other agents’ actions is encoded in the agent’s environment. For the finite samples analogue, we show that the system will reach an -approximate Nash policy after O(1/ 6) iterations. Our main convergence results are summarized in the following (informal) Theorem. Theorem 1.2 (Convergence of Policy Gradient (Informal)). Consider an MPG with n agents and let > 0. (a) Exact Gradients: If each agent i runs independent policy gradient using direct parameterization on their policy and the updates are simultaneous, then the learning dynamics reach an -Nash policy after O(1/ 2) iterations. (b) Finite Samples: If each agent i runs stochastic policy gradient using greedy parameterization (see equation 3) on their policy and the updates are simultaneous, then the learning dynamics reach an -Nash policy after O(1/ 6) iterations.
The formal statements for cases (a) and (b) are provided in Theorems 4.2 and 4.4, respectively. The technical details are presented in Section 4. The main step in the proof of Theorem 1.2 establishes that Projected Gradient Ascent (PGA) on the potential function generates the same dynamics as each agent running independent PGA on their value function. This follows from a straightforward derivation of an agent-wise version of the single-agent gradient domination property which can be
used to show that every (approximate) stationary point (Definition 4) of the potential function is an (approximate) Nash policy (Lemma 4.1). If agents do not have access to exact gradients, the key is to get an unbiased sample for the gradient of the value functions and prove that it has bounded variance (in terms of the parameters of the MPG). This is established by requiring agents to perform stochastic PGA with α-greedy exploration (equation 3). The main idea is that this parameterization stays away from the boundary of the simplex throughout its trajectory (Daskalakis et al., 2020).
Other Related Works. Our paper contributes to the growing literature on cooperative AI and ML (Carroll et al., 2019; Dafoe et al., 2020). The results on convergence of MARL algorithms are scarce and largely restricted to purely competitive (Daskalakis et al., 2020; Wei et al., 2021; Zhao et al., 2021) or purely cooperative (Wang & Sandholm, 2002; Bard et al., 2020) settings. As Daskalakis et al. (2020) argue, the current frontier concerns the extension to settings that are not zero-sum, involve more than two agents and/or are cooperative in nature, albeit likely for weaker solution concepts. Our current paper proceeds precisely in this direction, and in fact, it does so without reverting to a weaker solution concept. Concerning the setup, our paper contributes to the rapidly growing literature on MPGs and variations thereof which is showcased by the works of Marden (2012); Valcarcel Macua et al. (2018); Mguni (2021); Mguni et al. (2021) and the partially concurrent work of Zhang et al. (2021). Marden (2012) study Markov games that are potential at every state and which satisfy a strong additional state-transitivity property. Under the same assumption, Mguni (2021) derive an analogous result to our Theorem 3.1 on the existence of deterministic Nash policies. Valcarcel Macua et al. (2018) provide an analytical way to find a closed-loop Nash policy in a class of Markov games that is more closely related to our current MPG setting (cf. Proposition 3.2). Zhang et al. (2021) study the same class of MPGs, and present additional practical applications. By introducing the notion of averaged MDPs, they derive an alternative, model-based policy evaluation method, which, interestingly, establishes the same sample-complexity (of O( −6)) as our model-free estimation. As pointed out by Zhang et al. (2021), it will be instructive to further explore this connection. Concerning the technical parts, our methods are related to Daskalakis et al. (2020); Agarwal et al. (2020); Kakade & Langford (2002) and to Davis & Drusvyatskiy (2018); Bubeck (2015); Nemirovski et al. (2009).

heading: 2 PRELIMINARIES
text: Markov Decision Processes (MDPs). We consider a setting with n agents who select actions in a shared Markov Decision Process (MDP). Formally, an MDP is a tuple G = (S,N , {Ai, Ri}i∈N , P, γ, ρ), where S is a finite state space of size S = |S|, N = {1, 2, . . . , n} is the set of agents, and Ai is a finite action space of size Ai = |Ai| for each agent i ∈ N with generic element ai ∈ Ai. We write A = ∏ i∈N Ai and A−i = ∏ j 6=iAj to denote the joint action spaces of all agents and of all agents other than i with generic elements a = (ai)i∈N and a−i = (aj)j 6=i, respectively. Ri : S × A → [−1, 1] is the reward function of agent i ∈ N , i.e., Ri(s, ai,a−i) is the instantaneous reward of agent i when they take action ai and all other agents take actions a−i at state s ∈ S. P is the transition probability function, for which P (s′ | s,a) is the probability of transitioning from s to s′ when a ∈ A is chosen by the agents. Finally, γ (same for all agents) is a discount factor for future rewards and ρ ∈ ∆(S) is a distribution for the initial state at time t = 0.2
Whenever time is relevant, we will index the above terms with t. In particular, at each time step t ≥ 0, all agents i ∈ N observe the state st ∈ S, select actions at = (ai,t,a−i,t), receive rewards ri,t := Ri(st,at), and transition to the next state st+1 ∼ P (· | st,at). We will write τ = (st,at, rt)t≥0 to denote the trajectories of the system, where rt := (ri,t), i ∈ N .
Policies and Value Functions. For each agent i ∈ N , a deterministic, stationary policy πi : S → Ai specifies the action of agent i at each state s ∈ S, i.e., πi(s) = ai ∈ Ai for each s ∈ S. A stochastic, stationary policy πi : S → ∆(Ai) specifies a probability distribution over the actions of agent i for each state s ∈ S. Accordingly, πi ∈ Πi := ∆(Ai)S . In this case, we will write ai ∼ πi(· | s) to denote the randomized action of agent i at state s ∈ S. As above, we will write π = (πi)i∈N ∈ Π := ×i∈N∆(Ai)S and π−i = (πj)i 6=j∈N ∈ Π−i := ×i6=j∈N∆(Aj)S to denote the joint policies of all agents and of all agents other than i, respectively. A joint policy π induces a distribution Prπ over trajectories τ = (st,at, rt)t≥0, where s0 is drawn from the initial state distribution ρ and ai,t is drawn from πi(· | st) for all i ∈ N .
2We will write ∆(X ) to denote the set of probability distributions over any set X .
The value function, V is : Π → R, gives the expected reward of agent i ∈ N when s0 = s and the agents draw their actions, at = (ai,t,a−i,t), at time t ≥ 0 from policy π = (πi, π−i)
V is (π) := Eπ [∑∞
t=0 γtri,t | s0 = s
] . (1)
We also write V iρ (π) = Es∼ρ [ V is (π) ] if the initial state is random and follows distribution ρ. The solution concept that we will be focusing on are the Nash Policies which are formally defined next. Definition 1 ( -Nash Policy). A joint policy π∗ = (π∗i )i∈N is an -Nash policy if there exists an ≥ 0 so that for each agent i ∈ N , V is (π∗i , π∗−i) ≥ V is (πi, π∗−i) − , for all πi ∈ ∆(Ai)S , and all s ∈ S. If = 0, then π∗ is a called a Nash policy. In this case, π∗i maximizes each agent i’s value function for each starting state s ∈ S given the policies, π∗−i = (π∗j )j 6=i, of all other agents j 6= i ∈ N . The definition of a Nash policy remains the same if s ∼ ρ (random starting state).

heading: 3 MARKOV POTENTIAL GAMES.
text: We are now ready to define the class of MDPs that we will focus on for the rest of the paper. Definition 2 (Markov Potential Game). A Markov Decision Process (MDP), G, is called a Markov Potential Game (MPG) if there exists a (state-dependent) function Φs : Π→ R, with s ∈ S, so that
V is (πi, π−i)− V is (π′i, π−i) = Φs(πi, π−i)− Φs(π′i, π−i),
for all agents i ∈ N , states s ∈ S and policies πi, π′i ∈ Πi, π−i ∈ Π−i. Linearity of expectation implies that Φρ(πi, π−i)−Φρ(π′i, π−i) = V iρ (πi, π−i)−V iρ (π′i, π−i), where Φρ(π) := Es∼ρ [Φs(π)] .
As in normal-form games, an immediate consequence of this definition is that the value function of each agent in an MPG can be written as the sum of the potential (common term) and a term that does not depend on that agent’s policy (dummy term), i.e., for each agent i ∈ N there exists a function U is : Π−i → R so that V is (π) = Φs(π) + U is(π−i), for all π ∈ Π (cf. Proposition B.1 in Appendix B). Definition 3 (Ordinal and Weighted Potential Games). Similar to normal-form games, we can define more general notions of MPGs: weighted or ordinal MPGs. If there exist positive constants wi > 0, i ∈ N so that wi [ V is (πi, π−i)− V is (π′i, π−i) ] = Φs(πi, π−i) − Φs(π′i, π−i), then G is a Weighted Markov Potential Game (WMPG). If for all agents i ∈ N , all states s ∈ S and all policies πi, π ′ i ∈ Πi, π−i ∈ Π−i, the function Φs, s ∈ S satisfies V is (πi, π−i) − V is (π′i, π−i) > 0 ⇐⇒ Φs(πi, π−i)− Φs(π′i, π−i) > 0, then G is an Ordinal Markov Potential Game (OMPG).
Such classes are naturally motivated in the setting of multi-agent MDPs. As Example 2 shows, even simple potential-like settings, i.e., settings in which coordination is desirable for all agents, may fail to be exact MPGs (but may still be ordinal or weighted MPGs). From our current perspective, ordinal and weighted MPGs remain relevant since our main convergence results on the convergence of policy gradient carry over (in an exact or asymptotic sense) also in these classes of games (Remark 1).
Existence of Deterministic Nash Policies in MPGs. Before studying the types of MDPs that are captured by Definition 2, we first show that MPGs always possess deterministic Nash policies (similar to their single-state counterparts, i.e., to normal-form potential games Monderer & Shapley (1996)). This is established in Theorem 3.1, which settles part (a) of Theorem 1.1. As with the rest of the proofs (and technical details) of Section 3, the proof of Theorem 3.1 is provided in Appendix B. Theorem 3.1 (Deterministic Nash Policy Profile). Let G be a Markov Potential Game (MPG). Then, there exists a Nash policy π∗ ∈ ∆(A)S which is deterministic, i.e., for each agent i ∈ N and each state s ∈ S, there exists an action ai ∈ Ai so that π∗i (ai | s) = 1.
The proof of Theorem 3.1 relies on the following iterative reduction process of the non-deterministic components of an arbitrary Nash policy profile that is also a global maximizer of the potential function. At each iteration, we isolate an agent i ∈ N , and find a deterministic (optimal) policy for that agent in the (single-agent) MDP in which the policies of all other agents but i remain fixed. The important observation is that the resulting profile is again a global maximizer of the potential and hence, a Nash policy profile. This argument critically relies on the MPG structure (cf. Definition 2) and does not seem to be directly generalizable to MDPs beyond this class.
Sufficient Conditions for MPGs. Based on the above, it is tempting to think that MDPs which are potential at every state (i.e., the immediate rewards at every state are captured by a potential game at that state) are trivially MPGs. As we show in Examples 1 and 2, this intuition fails in the most straightforward way: we can construct simple MDPs that are potential at every state but which are purely competitive overall (do not possess a deterministic Nash policy, see Example 1) or which are cooperative in nature overall, but which do not possess an exact potential function, see Example 2. Example 1. Consider the MDP in Figure 1. To show that G is not an MPG, it suffices to show that it cannot have a deterministic Nash policy profile as should be the case according to Theorem 3.1 (see Appendix B.1). Intuitively, competition arises in Example 1 because the two agents play a game of matching pennies in terms of the states that they prefer (which can be determined by the actions that they choose) even though immediate rewards at each state are determined by normal form potential games. Example 2 shows that a state-based potential game may fail to be an MPG even if agents have similar preferences over states. Example 2. Consider the MDP in Figure 2. In s0 the agents play a Battle of the Sexes game and hence a potential game, while in s1 they receive no reward (which is trivially a potential game). A simple calculation shows that there is not an exact potential function due to the dependence of the transitions on agents’ actions (thus, this MDP is not an MPG). However, in the case of Example 2, it is straightforward to show that the game is an ordinal potential game, cf. Appendix B.1.
The previous discussion focuses on games that consist of normal-form potential games at every state, which leaves an important question unanswered: are there games which are not potential at every state but which are captured by the current definition of MPGs? Figure 3 answers this question affirmatively. Together with Example 1, this settles the claim in Theorem 1.1, part (b). Proposition 3.2 (Sufficient Conditions for MPGs). Consider an MDP, G, in which every state s ∈ S is a potential game, i.e., the immediate rewards R(s,a) = (Ri(s,a))i∈N for each state s ∈ S are captured by the utilities of a potential game with potential function φs. If either C1 or C2 are true, then G is an MPG. C1. Agent-independent transitions: P (s′ | s,a) does not depend on a, that is, P (s′ | s,a) = P (s′ | s) is just a function of the present state for all states s, s′ ∈ S. C2. Constant gradient of dummy terms: P (s′ | s,a) is arbitrary, but for the decomposition of each agent’s immediate rewards in common and dummy terms, Ri(s, ai,a−i) = φs(ai,a−i) + uis(a−i) with uis : A−i → R, it holds that
∇πi(s) Eτ∼π [∑∞
t=0 γtuist(a−i,t) | s0 = s
′ ]
= cs1,
for all states s′, s ∈ S, where cs ∈ R,1 ∈ RAi , and πi(s) is the policy distribution of agent i at s.
Condition C1 can be viewed as a special case of condition C2; nevertheless, it is more practical to state it separately. Condition C2 (or variations) have been studied in Marden (2012); Valcarcel Macua et al. (2018). However, Example 2 demonstrates that such conditions are restrictive, in the sense that they do not capture very simple MDPs in which agents have aligned incentives (cooperative in nature). Condition C2 is (trivially) satisfied when uis does not depend on the state s nor on the actions of other agents, i.e., uis(a−i) ≡ ci for some constant ci ∈ R for all a−i ∈ A−i and all s ∈ S. A special case is provided by MDPs in which the instantaneous rewards of all agents are the same at each state, i.e., such that Ri(s, ai,a−i) = φs(ai,a−i) for all agents i ∈ N , all actions ai ∈ Ai and all states s ∈ S . MDPs that satisfy this condition form a subclass of the current definition and have been studied under
the name Team Markov Games in Wang & Sandholm (2002). These observations motivate the study of ordinal or weighted MPGs (cf. Definition 3) as more glasses classes of cooperative MDPs.

heading: 4 CONVERGENCE OF POLICY GRADIENT IN MARKOV POTENTIAL GAMES
text: In the current section, we present the main results regarding convergence of (projected) policy gradient to approximate Nash policies in Markov Potential Games (MPGs). We analyze the cases of both infinite and finite samples using direct and α-greedy parameterizations, respectively. All proofs and auxiliary materials are deferred to Appendix D.
Independent Policy Gradient and Direct Parameterization. We assume that all agents update their policies independently according to the projected gradient ascent (PGA) or policy gradient algorithm.3 The PGA algorithm is given by
π (t+1) i := P∆(Ai)S
( π
(t) i + η∇πiV i ρ (π
(t)) ) , (PGA)
for each agent i ∈ N , where P∆(Ai)S is the projection onto ∆(Ai)S in the Euclidean norm. Here, the additional argument t ≥ 0 denotes time. We also assume that all players i ∈ N use direct policy parameterizations, i.e., πi(a | s) = xi,s,a, with xi,s,a ≥ 0 for all s ∈ S, a ∈ Ai and∑ a∈Ai xi,s,a = 1 for all s ∈ S. This parameterization is complete in the sense that any stochastic policy can be represented in this class Agarwal et al. (2020).
In practice, agents use projected stochastic gradient ascent (PSGA), according to which, the actual gradient,∇πiV iρ (π(t)), is replaced by an estimate thereof that is calculated from a randomly selected (yet finite) sample of trajectories of the MDP. This estimate, ∇̂(t)πi may be derived from a single or a batch of observations which in expectation behave as the actual gradient. We choose the estimator of the gradient of V iρ to be
∇̂(t)πi = R (T,t) i ∑T k=0 ∇ log πi(a(t)k | s (t) k ), (2)
where st0 ∼ ρ, and R (T,t) i = ∑T k=0 r k i,t is the sum of rewards of agent i for a batch of time horizon T along the trajectory generated by the stochastic gradient ascent algorithm at its t-th iterate.
The direct parameterization is not sufficient to ensure that the variance of the gradient estimator is bounded (as policies approach the boundary). In this case, we will require that each agent i ∈ N uses instead direct parameterization with α-greedy exploration as follows
πi(a | s) = (1− α)xi,s,a + α/Ai, (3) where α is the exploration parameter for all agents. For α-greedy exploration, it can be shown that (2) is unbiased and has bounded variance. In this case, 1− γ captures the probability that the MDP terminates after each round which ensures that the (finite) length of the trajectory is sampled from a geometric distribution. This is necessary for unbiasedness, see Zhang et al. (2020); Paternain et al. (2021) and Lemma 4.3. (PSGA) is given by
π (t+1) i := P∆(Ai)S
( π
(t) i + η∇̂ (t) πi
) . (PSGA)
3In practice, even though each agent treats their environment as fixed, the environment changes as other agents update their policies. This makes the analysis of such protocols particularly challenging in general and highlights the importance of studying classes of MDPs in which convergence can be obtained.
Main Technical Tools. The first step is to observe that, in MPGs, the (partial) derivatives of the value functions and the potential function are equal, i.e., ∇πiV is (π) = ∇πiΦ(π) for all i ∈ N (Proposition B.1). Together with the separability of the projection operator, i.e., the fact that projecting independently for each agent i on ∆(Ai)S is the same as jointly projecting on ∆(A)S (Lemma D.1), this establishes that running PGA or PSGA on each agent’s value function is equivalent to running PGA or PSGA on the potential function Φ. The next step is to study the stationary points of Φ. Definition 4 ( -Stationary Point of Φ). A policy profile π := (π1, ..., πn) ∈ ∆(A)S is called - stationary for Φ w.r.t distribution µ as long as max ∑ i∈N δ > i ∇πiΦµ(π) ≤ , where the max is taken
over all δ = (δ1, . . . , δn) such that (π1 + δ1, . . . , πn + δn) ∈ ∆(A)S , ∑ i∈N ‖δi‖ 2 2 ≤ 1. In words, the function Φ(π) cannot increase in value by more than along every possible local direction δ that is feasible (namely π + δ is also a policy profile).
To state our main result, we will also need the notion of distribution mismatch coefficient (Kakade & Langford, 2002) applied to our setting. For any distribution µ ∈ ∆(S) and any policy π ∈ Π, we call D := maxπ∈Π ∥∥∥dπµµ ∥∥∥∞ the distribution mismatch coefficient, where dπµ is the discounted state distribution (7). Lemma 4.1 suggests that as long as policy gradient reaches a point π(t) with small gradient along the directions in ∆(A)S , it must be the case that π(t) is an approximate Nash policy. Lemma 4.1 (Stationarity of Φ implies Nash). Let ≥ 0, and let π be an -stationary point of Φ (see Definition 4). Then, it holds that π is a √ SD (1− γ)−1-Nash policy.
Lemma 4.1 will be one of two mains ingredients to establish convergence of PGA and PSGA. To prove Lemma 4.1, we will use an agent-wise version of the gradient domination property of singleagent MDPs (cf. Lemma D.3 and Lemma 4.1 in Agarwal et al. (2020)). An important difference in the gradient domination property between (multi-agent) MPGs and single agent MDPs is that the value of each agent at different Nash policies may not be unique4 which implies that the gradient domination property will only be enough to guarantee convergence to one of the optimal (stationary) points of Φ (and not necessarily to the absolute maximum of Φ).
The second main ingredient will be fact that Φ is a β-smooth function (its gradient is Lipschitz) with parameter β = 2nγAmax(1 − γ)−3, where Amax := maxi∈N |Ai|, i.e., the maximum number of actions for some agent. Importantly, this implies that β scales linearly in the number of agents.
Exact Gradients Case. Theorem 1.2 (restated formally below) about rates of convergence of PGA can now be proved following a standard ascent property of gradient descent algorithms to approximate stationary points in non-convex optimization Ghadimi & Lan (2013). The Ascent Lemma (Lemma C.1) suggests that for any β-smooth function, f , it holds that f(x′)− f(x) ≥ 12β ‖x
′ − x‖22, where x′ is the next iterate of equation PGA. Thus, having shown in our context that Φ is a β-smooth function, this implies that
Φµ(π (t+1))− Φµ(π(t)) ≥
(1− γ)3
4nγAmax
∥∥∥π(t+1) − π(t)∥∥∥2 2 . (4)
Putting everything together, we can show the following result. Theorem 4.2 (Formal Theorem 1.2, part (a)). Let G be an MPG and let Amax = maxi |Ai|. For any initial state and any initial policies, if all agents run independent projected gradient ascent (PGA) on their policies with learning rate (step-size) η = (1−γ) 3
2nγAmax for at least T = 16nγD 2SAmaxΦmax (1−γ)5 2
iterations, then there exists a t ∈ {1, . . . , T} such that π(t) is an -approximate Nash policy.
Finite Sample Case. In the case of finite samples, we analyze (PSGA) on the value V i of each agent i which (as was the case for PGA) can be shown to be the same as applying projected gradient ascent on Φ. The key is to get an estimate of the gradient of Φ (2) at every iterate. Note that 1− γ now captures the probability for the MDP to terminate after each round (and it does not play the role of a discounted factor since we consider finite length trajectories). Lemma 4.3 argues that the estimator of equation equation 2 is both unbiased and bounded.
4This is in contrast to single-agent MDPs for which the agent has a unique optimal value even though their optimal policy may not necessarily be unique.
Lemma 4.3 (Unbiased estimator with bounded variance). It holds that ∇̂(t)πi is an unbiased estimator of ∇πiΦ for all i ∈ N , that is Eπ(t)∇̂ (t) πi = ∇πiΦµ(π(t)), for all i ∈ N . Moreover, for all agents
i ∈ N , it holds that Eπ(t) ∥∥∥∇̂(t)πi ∥∥∥2
2 ≤ 24A
2 max
(1−γ)4 , for all i ∈ N .
Using the above, we can now state part (b) of Theorem 1.2. Together with Lemma 4.3 and the stationarity Lemma (Lemma 4.1), the proof of this part uses the smoothness of Φ and existing tools from the analysis of stochastic gradient descent for non-convex functions.
Theorem 4.4 (Formal Theorem 1.2, part (b)). Let G be an MPG. For any initial state and any initial policies, if all agents run projected stochastic gradient ascent (PSGA) on their policies using α-greedy parameterization with α = 2 and learning rate (step-size) η =
4(1−γ)3γ 48nD2A2maxS for at least
T = 48(1−γ)AmaxΦmaxD 4S2
6γ3 iterations, then there exists a t ∈ {1, . . . , T} such that in expectation, π(t) is an -approximate Nash policy.
Using Markov’s inequality, it is immediate to show that the statement of Theorem 4.4 also holds with high probability. Namely, if we set the number of iterations to Tδ = T/δ4 and and the learning rate to ηδ = δ2η, where δ ∈ (0, 1), then with probability 1 − δ there exists a t ∈ {1, . . . , T} such that π(t) is an -approximate Nash policy. However, this is a weaker than desired statement, since, optimally, the running time should be logarithmic (instead of polynomial) in 1/δ (Nemirovski et al., 2009). Proving such a statement requires bounds on higher moments of the gradient estimator which in turn, require sampling and averaging over multiple trajectories (per iteration). Remark 1 (Convergence in WMPGs and OMPGs). It is rather straightforward to see that our results carry over to WMPGs (cf. Definition 3). The only difference in the running time of PGA is to account for the weights (which are just multiplicative constants). By contrast, the extension to OMPGs is not immediate. The reason is that, in that case, we cannot prove any bound on the smoothness of Φ and hence, we cannot have rates of convergence of policy gradient. Nevertheless, it is quite straightforward that PGA converges asymptotically to critical points (in bounded domains) for differentiable functions. Thus, as long as Φ is differentiable, it is guaranteed that PGA will asymptotically converge to a critical point of Φ. By Lemma 4.1, this point will be a Nash policy.

heading: 5 EXPERIMENTS: CONGESTION GAMES
text: We next study the performance of policy gradient in a general class of MPGs that are congestion games at every state (cf. Roughgarden (2015); Bistritz & Bambos (2020)). As we argued such MDPs are not necessarily MPGs; however, this class of MDPs contains MPGs, e.g., under additional conditions on the transitions, or ordinal (weighted) MPGs under more general conditions.
Experimental setup. We consider an experiment (Figure 4) with N = 8 agents, Ai = 4 facilities (resources or locations) that the agents can select from and S = 2 states: a safe state and a distancing state. In both states, all agents prefer to be in the same facility with as many other agents as possible (follow the crowd). In particular, the reward of each agent for being at facility k is equal to a predefined positive weight wsafek times the number of agents at k = A,B,C,D. The weights satisfy wsafeA < wsafeB < w safe C < w safe D , i.e., facility D is the most
preferable by all agents. However, if more than 4 = N/2 agents find themselves in the same facility, then the game transitions to the distancing state. At the distancing state, the reward structure is the same for all agents, but reward of each agent is reduced by a constant amount, c, where c > 0 is a (considerably large) constant. (We also treat the case in which c is different for each facility in Appendix E). To return to the safe state, the agents need to achieve maximum distribution over the facilities, i.e., no more than 2 = N/4 agents may be in the same facility. We consider deterministic transitions; however, the results are quantitatively equivalent also when these transitions occur with some probability (see Appendix E).
Paremeters. We perform episodic updates with T = 20 steps. At each iteration, we estimate the policy gradients using the average of mini-batches of size 20. We use γ = 0.99 and a common learning rate η = 0.0001 (larger than the theoretical guarantee, η = (1−γ) 3
2γAmaxn ≈ 1e − 08, of
Theorem 4.2). Experiments with randomly generated learning rates for each agent, non-deterministic transitions between states and different weights at each facility in the distancing state (which result in non-MPG structure) produce qualitatively equivalent results and are presented in Appendix E.
Results. The left panel of Figure 5 shows that the agents learn the expected Nash profile in both states in all runs. Importantly, this (Nash) policy profile is deterministic in line with Theorem 4.2. The panels in the middle and right columns depict the L1-accuracy in the policy space at each iteration which is defined as the average distance between the current policy and the final policy of all 8 agents, i.e., L1-accuracy = 1N ∑ i∈N |πi − πfinali | = 1 N ∑ i∈N ∑ s ∑ a |πi(a | s)− πfinali (a | s)|.

heading: 6 CONCLUSIONS AND FUTURE DIRECTIONS
text: We presented positive results about the performance of independent policy gradient in Markov Potential Games (MPGs), a class of multi-agent MDPs that naturally generalize normal-form potential games (games in which agents have aligned incentives) to state-based interactions. We found that MPGs exhibit a richer structure than intuitively expected (e.g., they include MDPs that can be purely competitive at some states), but retain important regularity properties, most importantly, the existence of deterministic Nash policies. In our main result, we showed that independent policy gradient with simultaneous updates converges at a polynomial rate in the approximation error to a deterministic Nash policy profile even in the case of finite samples (using direct parameterization with greedy exploration). This result makes a leap forward in addressing the open questions (Agarwal et al., 2020; Daskalakis et al., 2020) on the performance of RL algorithms in general multi-agent settings between the extremes of pure coordination (single-agent or MDPs with identical agents) and pure competition (two-agents, zero-sum MDPs). Given these positive results, several interesting questions emerge.
Open Questions. Our examples and counter-examples of MPGs suggest that the fundamental issue of modelling state-based interactions between agents with aligned incentives is still far from understood. Shedding more light in this area is the first step for future research, and techniques from cooperative AI (Kao et al., 2021; Mao et al., 2021) or linear MDPs (Jin et al., 2020) may turn out to be particularly useful. From an algorithmic perspective, a second direction for future work involves the analysis of policy gradient with different parameterizations (Agarwal et al., 2020) or of other naturally motivated online learning algorithms (Kleinberg et al., 2009; Panageas et al., 2018; Mehta et al., 2015) and the adaptation of advanced techniques (Cohen et al., 2017; Lee et al., 2019) to reproduce convergence and equilibrium selection results from normal-form to state-based (Markov) games. Alternatively, it would be interesting to test whether complex behavior (e.g., limit cycles, periodic orbits) of learning dynamics that has been observed in restricted normal-form settings Mertikopoulos et al. (2018); Vlatakis-Gkaragkounis et al. (2020) also emerges in the context of exact, weighted, or ordinal MPGs. Finally, turning to efficiency aspects, it would be interesting to measure the losses due to lack of coordination between agents, e.g., via a Price of Anarchy type of analysis Koutsoupias & Papadimitriou (1999); Roughgarden & Tardos (2002).
REPRODUCIBILITY STATEMENT
We included additional technical materials and complete proofs of all the claims and results of the main part in the appendix. We also uploaded the code that was used to run the experiments (policy gradient algorithm) as supplementary material.

heading: A ADDITIONAL NOTATION AND DEFINITIONS: SECTION 2
text: We first provide some additional notation and definitions that will be used in the proofs.
Q-value and Advantage Functions. Recall from the main part that the value function, V is : Π→ R, gives the expected reward of agent i ∈ N when s0 = s and the agents draw their actions, at = (ai,t,a−i,t), at time t ≥ 0 from policies π = (πi, π−i) and is defined as
V is (π) := Eτ∼π [∑∞
t=0 γtri,t | s0 = s
] .
Similarly, we will write V iρ (π) := Eso∼ρ[V is (π)] to denote the expected value of agent i ∈ N under the initial state distribution ρ.
For any state s ∈ S, the Q-value function Qis : P × A → R and the advantage function Ais : P ×A → R of agent i ∈ N are defined as
Qis(π,a) := Eτ∼π [∑∞
t=0 γtri,t | s0 = s,a0 = a
] , and (5)
Ais(π,a) := Q i s(π,a)− V is (π). (6)
Discounted State Distribution. It will be useful to define the discounted state visitation distribution dπs0(s) for s ∈ S that is induced by a (joint) policy π as
dπs0(s) := (1− γ) ∑∞ t=0 γtPrπ(st = s | s0), for all s ∈ S. (7)
As for the value function, we will also write dπρ (s) = Es0∼ρ[dπs0(s)] to denote the discounted state visitation distribution when the initial state distribution is ρ.

heading: B OMITTED MATERIALS: SECTION 3
text: Proposition B.1 (Separability of Value Functions and Equality of Derivatives). Let G = (S,N ,A = {Ai}i∈N , P,R, ρ) be a Markov Potential Game (MPG) with potential Φs, for s ∈ S. Then, for the value function V is , s ∈ S of each agent i ∈ N , the following hold

heading: P1. Separability of Value Functions: there exists a function U is : ∆(A−i)S → R such that for each
text: joint policy profile π = (πi, π−i) ∈ ∆(A)S , we have V is (π) = Φs(π) + U is(π−i).

heading: P2. Equality of Derivatives: the partial derivatives of agent i’s value function V is coincide with the
text: partial derivatives of the potential Φs that correspond to agent i’s parameters, i.e., ∂xi,s,aV i s (π) = ∂xi,s,aΦs(π), for all i ∈ N and all s ∈ S.
Proof. To obtain P1, consider any 3 arbitrary policies for agent i, notated by πi, π′i, π ′′ i ∈ ∆(Ai)S . Then, by the definition of MPGs, we have that
Φs(πi, π−i)− Φs(π′i, π−i) = V is (πi, π−i)− V is (π′i, π−i), Φs(πi, π−i)− Φs(π′′i , π−i) = V is (πi, π−i)− V is (π′′i , π−i).
for every starting state s ∈ S. This implies that we can write V is (πi, π−i) as both
V is (πi, π−i) = Φs(πi, π−i)− Φs(π′i, π−i) + V is (π′i, π−i) V is (πi, π−i) = Φs(πi, π−i)− Φs(π′′i , π−i) + V is (π′′i , π−i)
Thus, we have that −Φs(π′i, π−i) + V is (π′i, π−i) = −Φs(π′′i , π−i) + V is (π′′i , π−i) for any arbitrary pair of policies π′i and π ′′ i for agent i, implying that agent i’s policy has no impact on these terms. Accordingly, we can express them as
U is(π−i) := −Φs(π′i, π−i) + V is (π′i, π−i) = −Φs(π′′i , π−i) + V is (π′′i , π−i), where U is(π−i) is a function that does not depend on the policy of agent i. Thus, we can express the utility function of any agent i in an MPG as
V is (π) = Φs(π) + U i s(π−i).
as claimed. To obtain P2, we use P1 for a vector xi parameterizing πi, and obtain that
∂xi,aV i(π) = ∂xi,aΦ(π) + 0
for any coordinate xi,a with a ∈ Ai of xi, from which we can see that our claim is true.
Note that P1 serves as a characterization of MPGs. Namely, a multi-agent MDP is an MPG if and only if the value function of each agent i ∈ N can be decomposed in a term that is common for all players (potential function) and in a term that may be different for each agent i ∈ N but which depends only on the actions of all agents other than i. This property carries over from normal form (single state) potential games. Also note that both properties, P1 and P2, hold for any (differentiable for P2) policy parameterization and not only for the direct one that we use here.
Proof of Theorem 3.1. Let Φ be the potential function of G. Since the space ∆(A)S = ∆(A1)S × ... × ∆(An)S is compact and Φ is continuous, Φ has a global maximum Φmax. Let (π∗1 , ..., π∗n) denote a global maximizer, i.e., a joint policy profile at which Φmax is attained. By the Definitions of MPGs and Nash policies, this implies, in particular, that (π∗1 , ..., π ∗ n) is a Nash policy, since
0 < Φs(π ∗ i , π ∗ −i)− Φs(πi, π∗−i) = V is (π∗i , π∗−i)− V is (πi, π∗−i), (∗)
for all i ∈ N , s ∈ S and all policies πi ∈ ∆(Ai)S . If π∗1 , ..., π∗n are all deterministic we are done. So, we may assume that there exists an i ∈ N so that π∗i is randomized and consider the MDP G′ in which the policy of all agents other than i has been fixed to π∗−i. G′ is a single agent MDP with the same states as G, the same actions and rewards for agent i and transition probabilities that are determined by the joint distribution of the environment and the joint policy of all agents other than i. As a single agent MDP, this setting has a deterministic optimal policy, say π̃i, for agent i. Thus, it holds that
V is (π̃i, π ∗ −i) ≤ V is (π∗i , π∗−i) ≤ V is (π̃i, π∗−i),
where the first inequality follows from the fact that π∗ is a Nash policy and the second from the optimality of π̃i. It follows that
V is (π̃i, π ∗ −i) = V i s (π ∗ i , π ∗ −i),
i.e., the payoff of agent i at (π̃i, π∗−i) is the same as in (π ∗ i , π ∗ −i). Hence, by the definition of the potential function, we have that
0 = V is (π̃i, π ∗ −i)− V is (π∗i , π∗−i) = Φs(π̃i, π∗−i)− Φs(π∗i , π∗−i),
which implies that Φs(π̃i, π ∗ −i) = Φs(π ∗ i , π ∗ −i) = Φmax. Thus, (π̃i, π∗−i) is also a global maximizer of Φ which implies that (π̃i, π ∗ −i) is a Nash policy by the same reasoning as in equation equation ∗. Note that the value of all players other than i may not be the same at the joint policy profile (π̃i, π∗−i) as it is in (π ∗ i , π ∗ −i). However, what we need for our purpose is that this step reduces the number of randomized policies by one and that it retains the value of the potential function invariant at its global maximum (which ensures that the ensuing policy profile is also a Nash policy). By iterating this process until π∗j becomes deterministic for all agents j ∈ N , we obtain the claim.
Proof of Proposition 3.2. The proof is constructive and proceeds by finding the potential function, Φs, s ∈ S in both cases, C1-C2. Since the individual rewards of the agents at each state s ∈ S are captured by a potential function φs, then for the reward, Ri(s,a) of each agent i at the action profile a, it holds that
Ri(s,a) = φs(a) + u i s(a−i), (8)
where uis : ∆(A−i) → R is a function that does not depend on the actions of agent i in any way. Thus, we may write the value function of each agent i ∈ N as
V is (π) = Eτ∼π [∑∞
t=0 γtRi(st,at) | s0 = s ] = Eτ∼π [∑∞ t=0 γt ( φst(at) + u i st(a−i,t) ) | s0 = s
] = Eτ∼π [∑∞ t=0 γtφst(at) | s0 = s ] + Eτ∼π [∑∞ t=0 γtuist(a−i,t) | s0 = s ] (?)
where τ ∼ π is the random trajectory generated by policy π. To show that G is an MPG, it suffices to show that the value function of each agent i ∈ N can be decomposed in a term that is common for all agents (and which may depend on the actions of agent i ∈ N ) and in a term that does not depend (in any way) in the actions of agent i (dummy term), cf. Proposition B.1. The first term in expression equation ?, i.e., Eτ∼π [ ∑∞ t=0 γ
tφst(at) | s0 = s], depends on the actions of all players and is common for all agents i ∈ N (and is thus, a good candidate for the potential function). The second term in expression equation ?, i.e., Eτ∼π [∑∞ t=0 γ tuist(a−i,t) | s0 = s ] , does not depend on player i via the payoffs uist(a−i,t), but, in general, it does depend on player i via the transitions, τ ∼ π. The two cases in the statement of Proposition 3.2 ensure precisely that this term is independent of the policy of agent i, in which case it is a dummy term for agent i or that it is also common for all players and hence, that it can be included in the potential function.
Condition C1. If the transitions do not depend on the action of the players, we have that τ ∼ P , where P is an exogenously given distribution function (state-wise). In this case, we have that
Φs(π) := Eτ∼π [ ∞∑ t=0 γtφst(at) | s0 = s ]
is a potential function and U is(π−i) := Eτ∼π [∑∞ t=0 γ tuist(a−i,t) | s0 = s ] is a dummy term that does not depend (in any way) on the policy of agent i ∈ N which proves the claim.
Condition C2. We will show again that
Φs′(π) := Eτ∼π [ ∞∑ t=0 γtφst(a) | s0 = s′ ]
is a potential function for G and that the same decomposition as in condition C1 of the value function of agent i in a common and a dummy term applies. To see this, let πi, π′i ∈ Πi be two policies of agent i and let π = (πi, π−i), π′ = (π′i, π−i) where π−i is the fixed policy of all agents other than i. Then, using equation ?, we have that
V is′(π)− V is′(π′) =
=Φs′(π)− Φs′(π′) + Eτ∼π [ ∞∑ t=0 γtuist(a−i,t) | s0 = s ′ ] − Eτ∼π′ [ ∞∑ t=0 γtuist(a−i,t) | s0 = s ′ ] .
The intermediate value theorem implies that there exists a policy ξi which is a convex combination of πi, π ′ i such that
Eτ∼π [ ∞∑ t=0 γtuist(a−i,t) | s0 = s ′ ] − Eτ∼π′ [ ∞∑ t=0 γtuist(a−i,t) | s0 = s ′ ]
= (πi − π′i)>∇πi Eτ∼(ξi,π−i) [ ∞∑ t=0 γtuist(a−i,t) | s0 = s ′ ] The displayed condition in C2 implies that
∇πi Eτ∼(ξi,π−i) [ ∞∑ t=0 γtuist(a−i,t) | s0 = s ′ ] = (cs1)s∈S ,
which is enough to ensure that the dot product in the previous equation is equal to 0 since πi, π′i correspond to probability distributions at every state s ∈ S, and the sum of their component-wise differences is equal to 0. This proves the claim.
Summing up, in both cases, C1-C2, G is an MPG as claimed.
Note that the proof of the (trivial) case in which the instantaneous rewards of all agents i ∈ N are equal at each state s ∈ S is similar. In this case, it is immediate to see that the instantaneous rewards
are precisely given by the potential function at that state, i.e., it holds that Ri(s,a) = φs(a) for all i ∈ N and all s ∈ S. In this case, it holds that uis(a−i) ≡ 0 for all i ∈ N and all s ∈ S and hence,
Φs(π) := Eτ∼π [ ∞∑ t=0 γtφst(a) | s0 = s ]
is a potential function for G, and the dummy terms are all equal to 0, i.e., U is(π−i) ≡ 0.
B.1 EXAMPLES
Example 1 (Continued). We prove the claim that G cannot have a deterministic Nash policy profile. To obtain a contradiction, assume that agent A is using a deterministic action a0A ∈ {0, 1} at state 0. Then, agent B, who prefers to move to state 1, will optimize their utility by choosing the action a0B ∈ {0, 1} that yields a0A ⊕ a0B = 1. In other words, given any deterministic action of agent A at state 0, agent B can choose an action that always moves the sequence of play to state 1. Thus, such an action cannot be optimal for agent A which implies that the MDP does not have a deterministic optimal policy profile as claimed.
Example 2 (Continued). At each state, s ∈ {0, 1}, the agents’ payoffs, (R1s, R2s), form a potential game (at that state), and are given as follows
State 0 : (R10, R 2 0) = ( 0 1 0 5, 2 −1,−2 1 −5,−4 1, 4 ) , with potential Φ0 = ( 4 0 −6 2 ) ,
State 1 : (R11, R 2 1) = (0, 0), with potential Φ1 = 0.
In this MDP, agents need only to select an action at state s0. Thus, we will denote a policy, π1, of agent 1 by π1 = (p, 1− p) where p ∈ [0, 1] is the probability with which agent A selects action 0 at state s0. Similarly, we will denote a policy, π2, of agent B by π2 = (q, 1− q) where q ∈ [0, 1] is the probability with which agent B selects action 0 at state s0. Moreover, we will slightly abuse notation and write
Ri0(π) = R i 0(π1, π2) = π > 1 R i 0π2 = [p, 1− p]Ri0[q, 1− q]>.
We also assume that the horizon is infinite and there is a discount factor γ ∈ [0, 1). Accordingly, we can calculate the value functions V i0 (π1, π2) of agents i = A,B starting from state s0 as follows,
V i0 (π) = R i 0(π) + γpqV i 0 (π)− γ(1− pq)× 0
which yields the solution
V i0 (π) = Ri0(π)
1− γpq , for i = A,B.
Next, we use the Performance Difference Lemma (Lemma 3.2 by Agarwal et al. (2020)) to determine the difference in the value between two different policies. We will do this for agent 1 (the calculation is similar for agent 2: we use here 1 for agent 1 and 2 for agent B). For a policy π = (π1, π2), we have at state s0 that
Ea∼π1(·|s0)[A 1 0(π ′,a)] = pA10(π ′, 0, a2) + (1− p)A1(π′, 1, a2)
= p [ R10(0, π2) + γqV0(π ′)− V0(π′) ] + (1− p) [ R10(1, π2) + 0− V0(π′) ] = pR10(0, π2) + (1− p)R10(0, π2)− (1− γpq)V0(π′)
= R10(π)− (1− γpq)V0(π′).
At state s1, there is only one available action for each agent which yields a payoff of 0. Thus,
Ea∼π1(·|s1)[A 1 1(π ′,a)] = 0.
Moreover, concerning the discounted visitation distribution, we have that
dπ0 (s0) = (1− γ) ∞∑ t=0 γtPrπ(st = s0 | s0) = (1− γ) [ 1 + γpq + (γpq)2 + . . . ] = 1− γ 1− γpq ,
and dπ0 (s1) = 1− dπ0 (s0) = γ(1−pq) 1−γpq . Thus, using all the above, we have that
V0(π)− V0(π′) = 1
1− γ
[ 1− γ
1− γpq · (R10(π)− (1− γpq)V0(π′)) + γ(1− pq) 1− γpq
· 0 ]
= R10(π)
1− γpq − V0(π′) = V0(π)− V0(π′).
which shows that our initial calculations conform with the outcome specified by the Performance Difference Lemma.
Finally, a direct calculation shows that Φs = φs for s = 0, 1 is a valid potential function for which the MDP is an ordinal MPG. Example 3 (Continued). At state s0, we consider the game with action sets A1(s0) = A2(s0) = {H,T} and (instantaneous) payoffs
R1(s0, a1, a2) = ( H T H 1 −1 T −1 1 ) and R2(s0, a1, a2) = ( H T H −1 1 T 1 −1 ) ,
where a1 denotes the action of agent 1 and a2 the action of agent 2 (agent 1 selects rows and agent 2 selects columns in both matrices). This is a constant sum game (equivalent to zero-sum) and hence, it is not an (ordinal) potential game. Apart from the instantaneous rewards, agents’ actions at s0 induce a deterministic transition to a state in which the only available actions to the agents are precisely the actions that they chose at state s0 and their instantaneous rewards at this state are the rewards of the other agent at s0. In particular, there are four possible transitions to states sab with a, b ∈ {H,T}, with action sets and instantaneous rewards given by
A1(sab) = {a}, A2(sab) = {b}, R1(sab, a, b) = R2(s0, b, a), R2(sab, a, b) = R1(s0, b, a), for agents 1 and 2, respectively. Note that the visitation probability of this states is equal to the visitation probability of state s0. After visiting one of these states, the MDP transitions to state s1 which is a potential game, with potential function given by
Φ1 = (L R L 4 3 R 3 0 ) As mentioned above, the game in state s0 does not admit a potential function. However, the joined rewards RJ1, RJ2 of agents 1 and 2 which result from selecting an action profile (a, b) ∈ H,T 2 at s0 and then traversing both s0 and the ensuing sab (part included in the dotted rectangle in Figure 3), do admit a potential function. The potential function in this case is the sum of agents’ rewards and is given by
Φ0ab = ( H T H 1− 1 1− 1 T 1− 1 1− 1 ) = (H T H 0 0 T 0 0 ) .
Let π1 = (x0,x1) denote a policy of agent 1. Here x0 = (x0, 1 − x0), where x0 ∈ [0, 1] is the probability with which agent 1 chooses action H at state s0. Similarly, x1 = (x1, 1 − x1) where x1 ∈ [0, 1] is the probability with which agent 1 chooses action L at state s1. At states sab, a, b ∈ {H,T}2, agents only have one action to choose from, so this choice is eliminated from their policy representation. Similarly, we represent a policy of agent 2 by π2 = (y0,y1) with y0, y1 ∈ [0, 1]. Let also
p0 := p0 (π1, π2) := Pr(st+1 = s0 | st = s1, π1, π2), (9) In the general case, p0, i.e., the transition probability from s1 to s0, may depend on the actions of the agents or it may be completely exogenous (i.e., constant with respect to agents’ actions). If we write
p0(a1, a2) := Pr(st+1 = s0 | st = s1, a1, a2), for a1, a2 ∈ {L,R},
to denote the probability of transitioning from state s1 to state s0 given that the agents chose actions a1, a2 ∈ {L,R} at state s1, then we can write p0 as
p0 = E(a1,a2)∼(π1,π2)[p0(a1, a2)] = ∑
(a1,a2)∈{L,R}2 Pr(a1, a2 | π1, π2) · p0(a1, a2)
= x1y1p0(L,L) + x1(1− y1)p0(L,R) + (1− x1)y1p0(R,L) + (1− x1)(1− y1)p0(R,R). (10)
Using this notation, we can now proceed to compute the value function of each state of the MDP in Figure 3. Since the value of states sa,b, a, b ∈ H,T 2 is equal to a constant reward plus the value of state s1 (discounted by γ), it suffices to calculate the value for states s0 and s1. We have that
V 10 (π1, π2) = x0R 1 0y0 + γ ( x0 ( R20/γ ) y0 ) + γ2V 11 (π1, π2)
V 11 (π1, π2) = x1R 1 1y1 + γ [ p0V 1 0 (π1, π2) + (1− p0)V 11 (π1, π2) ] ,
which after some trivial calculations yield V 10 (π1, π2) = x0 ( R10 +R 1 0 ) y0 + γ 2V 11 (π1, π2)
V 11 (π1, π2) = 1 1− γ (1− p0) [ x1R 1 1y1 + γp0V 1 0 (π1, π2) ] .
This is a system of 2 equations in the 2 unknown quantities, V 10 (π1, π2) and V 1 1 (π1, π2). Solving for these two quantities, yields the unique solution
V 10 (π1, π2) = 1 1− γ (1− p0)− γ3p0 [ (1− γ (1− p0))x0 ( R10 +R 2 0 ) y0 + γ 2x1R 1 1y1 ] .
V 11 (π1, π2) = 1 1− γ (1− p0)− γ3p0 [ γp0x0 ( R10 +R 2 0 ) y0 + x1R 1 1y1 ] .
In the case that p0 is a constant with respect to π1, π2, then both value functions are of the form V is (π1, π2) = c1 (s) · x0 ( R10 +R 2 0 ) y0 + c2 (s) · x1Ri1y1, for s ∈ {s0, s1}, and i = {1, 2},
where c1 (s) , c2 (s) > 0 are appropriate constants that depend only the state s ∈ {s0, s1} and on agents 1, 2. Since the game at s1 is a potential game, with potential function given by a 2× 2 matrix Φ1, it is immediate to infer that
V is (π ′ 1, π2)− V is (π1, π2) = Φs (π′1, π2)− Φs (π1, π2) , for s ∈ {s0, s1},
with Φs (π1, π2) := c1 (s)x0 ( R10 +R 2 0 ) y0 + c2 (s) · x1Φ1y1, for s ∈ {s0, s1}.
However, if p0 depends on the actual policies of agents 1 and 2, cf. equation equation 9, then it is not immediate to determine a potential (or even to decide whether a (exact) potential exists or not). Remark 2. Several elements of Figure 3 have been selected in the sake of simplicity and are not necessary for the main takeaway, i.e., that there are MDP that are not potential at some states, but which are MPGs. First, the transitions from s0 to the states sab need not be deterministic. To see this, let q ∈ (0, 1) and assume that if the agents select actions H,T is s0, then the process transitions with probability q to a state sHT with rewards (−1, 1)/qγ and with probability (1 − q) to a state s′HT with rewards (1,−1)/(1 − q)γ. The rest remains the same. Accordingly, the expected reward for agent 1 after (H,T ) has been selected in s0 is the same as in the current format.
Second, the construction with states s0 and sab, (a, b) ∈ H,T 2 is not the only one that leads to such an example. Another very common instance occurs in the case of aliasing between s0 and states sab, i.e., when the agents cannot tell these states apart. The intuition which carries over from the currently presented example is that the roles of the agents are essentially reversed between the two states, but the agents do not know (from the observable features) in which state they are. Thus, any valid policy, selects the same action in both states leading to the same situation as in the presented example.
Finally, if the horizon is finite, then the instantaneous rewards in states sab still work if we eliminate the scaling factor (here γ). Thus, the construction works in both episodic and continuing settings.

heading: C AUXILIARY LEMMAS
text: Before proceeding to the omitted materials of Section 4, we first include some auxiliary results that we will use in the proofs presented there.
Recall that PX denotes the projection onto some set X . Lemma C.1 (Bubeck (2015), Lemma 3.6). Let f be a β-smooth function5 with convex domain X . Let x ∈ X , x+ = PX (x− 1β∇f(x)) and gX (x) = β(x− x +). Then the following holds true:
f(x+)− f(x) ≤ − 1 2β ‖gX (x)‖22 .
Lemma C.2 (Agarwal et al. (2020), Proposition B.1). Let f(π) be a β-smooth function in π ∈ ∆(A)S . Define the gradient mapping
G(π) = β ( P∆(A)S ( π + 1
β ∇πf(π)
) − π ) and the update rule for the projected gradient is π′ = π + 1βG(π). If ‖G(π)‖2 ≤ , then
max π+δ∈∆(A)S ,‖δ‖2≤1
δ>∇πf(π′) ≤ 2 .
Lemma C.3. Let Φµ(π) be the potential function (which is β-smooth) and assume π ∈ ∆(A)S uses α-greedy parameterization. Define the gradient mapping
G(π) = β ( P∆(A)S ( π + 1
β ∇Φµ(π)
) − π ) and the update rule for the projected gradient is π′ = π + 1βG(π). If ‖G(π)‖2 ≤ , then
max π+δ∈∆(A)S ,‖δ‖2≤1
δ>∇Φµ(π′) ≤ 2 + √ nαAmax.
Proof. It is a direct application of Lemma C.2 and the fact that Φµ is Lipschitz with parameter√ nAmax
(1−γ)2 (this is Proposition 3 in page 23 of Daskalakis et al. (2020)).
Lemma C.4 (Unbiased with bounded variance Daskalakis et al. (2020)). It holds that ∇̂(t)πi is unbiased estimator of∇πiV i for all i, that is Eπ(t)∇̂ (t) πi = ∇πiV iρ (π(t)) for all i. Moreover, for all agents i we
get that (this is what the authors actually prove), it holds that Eπ(t) ∥∥∥∇̂(t)πi ∥∥∥2
2 ≤ 24A
2 max
α(1−γ)4 .

heading: D OMITTED MATERIALS: SECTION 4
text: Before we proceed with the formal statements and proofs of this section, we recall the commonly used definition of distribution mismatch coefficient Kakade & Langford (2002) applied to our setting. Definition 5 (Distribution Mismatch coefficient). For any distribution µ ∈ ∆(S) and any policy π ∈ Π, we call D := maxπ∈Π
∥∥∥dπµµ ∥∥∥∞ the distribution mismatch coefficient, where dπµ is the discounted state distribution (7).
D.1 EXACT GRADIENTS CASE
The first auxiliary Lemma has to do with the projection operator that is used on top of the independent policy gradient, so that the policy vector π(t)i remains a probability distribution for all agents i ∈ N (see (PGA)). It is not hard to show (due to separability) that the projection operator being applied independently for each agent i on ∆(Ai)S is the same as jointly applying projection on ∆(A)S . This is the statement of Lemma D.1.
5Differentiable with ∇f to be β-Lipschitz.
Lemma D.1 (Projection Operator). Let π := (π1, ..., πn) be the policy profile for all agents and let π′ = π + η∇πΦρ(π) be a gradient step on the potential function for a step-size α > 0. Then,
P∆(A)S (π ′) = (P∆(A1)S (π ′ 1), . . . , P∆(An)S (π ′ n)).
Proof of Lemma D.1. Observe that PX (y) = arg minx∈X ‖x− y‖ 2 2 for any set X ⊆ Rn. Thus,
P∆(A)S (y) = arg min x∈∆(A)S ‖x− π′‖22 = arg min x1∈∆(A1)S ,...,xn∈∆(An)S n∑ i=1 ‖xi − π′i‖ 2 2
= n∑ i=1 arg min xi∈∆(Ai)S ‖xi − π′i‖ 2 2 = (P∆(A1)S (π ′ 1), . . . , P∆(An)S (π ′ n)).
The main implication of Lemma D.1 along with the equality of the derivatives between value functions and the potential function in MPGs, i.e., ∇πiV is (π) = ∇πiΦ(π) for all i ∈ N (see property P2 in Proposition B.1), is that running independent equation PGA on each agent’s value function is equivalent to running equation PGA on the potential function Φ. In turn, Lemma 4.1 suggests that as long as policy gradient reaches a point π(t) with small gradient along the directions in ∆(A)S , it must be the case that π(t) is an approximate Nash policy. Together with Lemma D.1, this will be sufficient to prove convergence of equation PGA.
Proof of Lemma 4.1. Fix agent i and suppose that i deviates to an optimal policy π∗i (w.r.t the corresponding single agent MDP). Since π is -stationary it holds that (Definition 4)
max π′i∈∆(Ai)S
(π′i − πi)>∇πiΦµ(π) ≤ √ S . (11)
Thus, with π∗ = (π∗i , π−i), Lemma D.3 implies that
Φρ(π ∗)− Φρ(π) ≤
1
1− γ ∥∥∥∥∥dπ ∗ ρ µ ∥∥∥∥∥ ∞ max π′=(π′i,π−i) (π′ − π)>∇πiΦµ(π) (11) ≤ D 1− γ √ S . (12)
Thus, using the definition of the potential function (cf. Definition 2), we obtain that
V iρ (π ∗)− V iρ (π) = Φρ(π∗)− Φρ(π) ≤
√ SD
1− γ .
Since the choice of i was arbitrary, we conclude that π is an √ SD
1−γ -approximate Nash policy.
To prove Lemma D.3, we will use a multi-agent version of the Performance Difference Lemma (cf. Agarwal et al. (2020) for a single agent and Daskalakis et al. (2020) for two agents).
Lemma D.2 (Multi-agent Performance Difference Lemma). Consider an n-agent MDP G and fix an agent i ∈ N . Then, for any policies π = (πi, π−i), π′ = (π′i, π−i) ∈ Π and any distribution ρ ∈ ∆(S), it holds that
V iρ (π)− V iρ (π′) = 1
1− γ Es∼dπρ Eai∼πi(·|s) Ea−i∼π−i(·|s)
[ Ais(π ′, ai,a−i) ] ,
where a−i ∼ π−i(· | s) denotes the action profile of all agents other than i that is drawn from the product distribution induced by their policies π−i = (πj)j 6=i∈N ∈ Π−i.
Proof. For any initial state s ∈ S and joint policies π = (πi, π−i), π′ = (π′i, π−i) ∈ Π, it holds that V is (π)− V is (π′) = Eτ∼π [∑∞
t=0 γtri,t | s0 = s
] − V is (π′)
= Eτ∼π [∑∞
t=0 γt (ri,t − Vst(π′) + Vst(π′)) | s0 = s
] − V is (π′)
= Eτ∼π [∑∞ t=0 γt ( ri,t − Vst(π′) + γVst+1(π′) ) | s0 = s ] = Eτ∼π [∑∞ t=0 γt ( ri,t + γ E [ Vst+1(π ′) | st, ai,t,a−i,t ] − Vst(π′) ) | s0 = s
] = Eτ∼π [∑∞ t=0 γtAist(π ′,at) | s0 = s
] = 1
1− γ Es′∼dπρ Eai∼πi(·|s′) Ea−i∼π−i(·|s′)
[ Ais′(π ′,a) ] .
Taking expectation over the states s ∈ S with respect to the distribution ρ ∈ ∆(S) yields the result.
To prove Lemma 4.1, we will need an agent-wise version of the gradient domination property of single-agent MDPs (cf. Lemma 4.1 in Agarwal et al. (2020)). This is presented in Lemma D.3. Lemma D.3 (Agent-wise Gradient Domination Property in MPGs). Let G be an MPG with potential function Φ, fix any agent i ∈ N , and let π = (πi, π−i) ∈ ∆(A)S be a policy. Let π∗i be an optimal policy for agent i in the single agent MDP in which the rest of the agents are fixed to choose π−i. Then, for the policy π∗ = (π∗i , π−i) ∈ ∆(A)S that differs from π only in the policy component of agent i, and for any distributions µ, ρ ∈ ∆(S), it holds that
Φρ(π ∗)− Φρ(π) ≤
1
1− γ ∥∥∥∥∥dπ ∗ ρ µ ∥∥∥∥∥ ∞ max π′=(π′i,π−i) (π′ − π)>∇πiΦµ(π),
Proof of Lemma D.3. Fix an agent i ∈ N and let π = (πi, π−i), π∗ = (π∗i , π−i) ∈ Π = ∆(A)S . By the definition of MPGs (cf. Definition 2), it holds that
V iρ (π ∗)− V iρ (π) = Φρ(π∗)− Φρ(π).
Thus, using the multi-agent version of the Performance Difference Lemma (cf. Lemma D.2), we have for any distribution µ ∈ ∆(S) that Φρ(π ∗)− Φρ(π) = V iρ (π∗)− V iρ (π)
= 1
1− γ Es∼dπ∗ρ Eai∼π∗i (·|s) Ea−i∼π∗−i(·|s)
[ Ais(π, ai,t,a−i,t) ] ≤ 1
1− γ max π′i∈Πi {∑ s∈S dπ ∗ ρ (s)Eai∼π′i(·|s) Ea−i∼π∗−i(·|s) [ Ais(π, ai,a−i) ]} ,
= 1
1− γ max π′i∈Πi {∑ s∈S dπ ∗ ρ (s) dπµ(s) dπµ(s)Eai∼π′i(·|s) Ea−i∼π∗−i(·|s) [ Ais(π, ai,a−i) ]} ,
≤ 1 1− γ ∥∥∥∥∥dπ ∗ ρ
dπµ ∥∥∥∥∥ ∞ max π′i∈Πi {∑ s∈S dπµ(s)Eai∼π′i(·|s) Ea−i∼π∗−i(·|s) [ Ais(π, ai,a−i) ]} .
To proceed, observe that Eai∼πi(·|s) Ea−i∼π∗−i(·|s) [ Ais(π, ai,a−i) ] = 0. Thus, for any π′i ∈ Πi and any state s ∈ S, it holds that Eai∼π′i(·|s) Ea−i∼π∗−i(·|s) [ Ais(π, ai,a−i) ] =
= ∑ ai∈Ai (π′i(ai | s)− πi(ai | s))Ea−i∼π∗−i(·|s) [ Ais(π, ai,a−i) ] = ∑ ai∈Ai (π′i(ai | s)− πi(ai | s))Ea−i∼π∗−i(·|s) [ Qis(π, ai,a−i) ]
since V is (π) does not depend on ai. Substituting back in the last inequality of the previous calculations, we obtain that
Φρ(π ∗)− Φρ(π) ≤
≤ ∥∥∥∥∥dπ ∗ ρ
dπµ ∥∥∥∥∥ ∞ max π′i∈Πi {∑ s,ai dπµ(s) 1− γ (π′i(ai | s)− πi(ai | s))Ea−i∼π∗−i(·|s) [ Qis(π, ai,a−i) ]}
= ∥∥∥∥∥dπ ∗ ρ
dπµ ∥∥∥∥∥ ∞ max π′i∈Πi (π′i − πi)>∇πiV iµ(π),
where we used the policy gradient theorem (Agarwal et al. (2020); Sutton & Barto (2018)) under the assumption of direct policy parameterization. We can further upper bound the last expression by using that dπµ(s) ≥ (1 − γ)µ(s) which follows immediately from the definition of the discounted visitation distribution dπµ(s) for any initial state distribution µ. Finally, property P2 of Proposition B.1, implies that∇πiV iρ (π) = ∇πiΦρ(π) (making crucial use of the MPG structure). Putting these together, we have that
Φρ(π ∗)− Φρ(π) ≤
1
1− γ ∥∥∥∥∥dπ ∗ ρ µ ∥∥∥∥∥ ∞ max π′=(π′i,π ∗ −i) (π′ − π)>∇πiV iµ(π)
= 1
1− γ ∥∥∥∥∥dπ ∗ ρ µ ∥∥∥∥∥ ∞ max π′=(π′i,π ∗ −i) (π′ − π)>∇πiΦµ(π),
as claimed.
Remark 3. Intuitively, Lemma D.3 implies that there is a best response structure in the agents’ updates that we can exploit to show convergence of (projected) policy gradient to a Nash policy profile. In particular, given a fixed policy profile of all agents other than i, the decision of agent i is equivalent to the decision of that agent in a single MDP. Thus, the following inequality
V is (π ∗)− V is (π) ≤
1
1− γ ∥∥∥∥dπ∗sµ ∥∥∥∥ ∞ max π′=(π′i,π−i) (π′ − π)>∇πiV iµ(π)
(which stems directly from the gradient domination property in the single MDP) implies that any stationary point of V is (w.r.t the variables xi,s,a of agent’s i policy with the rest of the variables being fixed) is an optimal policy for i, i.e., a best response given the policies of all other agents.
Lemma D.3 also suggests that there is an important difference in the gradient domination property between (multi-agent) MPGs and single agent MDPs. Specifically, for MPGs, the value of each agent at different Nash policies may not be unique6 which implies that the gradient domination property, as stated in Lemma D.3, will only be enough to guarantee convergence to one of the optimal (stationary) points of Φ (and not necessarily to the absolute maximum of Φ).
The last critical step before the formal statement and proof of Theorem 1.2 is to show that the potential function Φ is smooth. Importantly, the smoothness parameter, involves Amax := maxi∈N |Ai|, i.e., the maximum number of actions for some agent, which scales linearly in the number of agents. Lemma D.4 (Smoothness of Φ). Let Amax := maxi∈N |Ai| (the maximum number of actions for some agent). Then, for any initial state s0 ∈ S (and hence for every distribution µ ∈ ∆(S) on states), Φµ(π) is 2nγAmax(1−γ)3 -smooth, i.e., it holds that
‖∇πΦs0(π)−∇πΦs0(π′)‖2 ≤ 2nγAmax (1− γ)3 ‖π − π′‖2 (13)
Proof of Lemma D.4. It suffices to show that the maximum eigenvalue in absolute value of the Hessian of Φ is at most 2nγAmax(1−γ)3 , i.e., that∥∥∇2Φµ∥∥2 ≤ 2nγAmax(1− γ)3 .
6This is in contrast to single-agent MDPs for which the agent has a unique optimal value even though their optimal policy may not necessarily be unique.
We first prove the following intermediate claim.
Claim D.5. Consider the symmetric block matrix C with n× n matrices so that ‖Cij‖2 ≤ L. Then, it holds that ‖C‖2 ≤ nL, i.e., if all block submatrices have spectral norm at most L, then C has spectral norm at most nL.
Proof. We will prove the claim by induction on n. For n = 2 we need to show that ‖C‖2 := ∥∥∥∥( C11 C12C21 C22 )∥∥∥∥ 2 ≤ 2L
if ‖C11‖2 , ‖C12‖2 , ‖C21‖2 , ‖C22‖2 ≤ L. Define matrix W to be W := 2L · I − C = (
2L · I − C11 −C12 −C21 2L · I − C22
) ,
where I is the identity matrix (of appropriate size). If we show that W is positive semi-definite, then it follows that W has only non-negative eigenvalues, which, in turn, implies that the spectral norm of C is at most 2L. To see this, set
W1 :=
( L · I − C11 0
0 L · I − C22
) ,W2 := ( L · I −C12 −C21 L · I ) .
W1 is positive semi-definite as a block diagonal matrix with diagonal blocks positive semi-definite matrices. Moreover, by Schur complement we get that W2 is positive semi-definite as long as L · I is positive semi-definite and L · I − 1L · C12C21 is positive semidefinite. By assumption, we have that
1 L ‖C12C21‖2 ≤ 1 L ‖C12‖2 ‖C12‖2 ≤ L,
which implies that L·I− 1L ·C12C21 has non-negative eigenvalues. Thus,W2 is positive semi-definite. We conclude thatW1 +W2 is positive semi-definite (sum of positive semi-definite matrices is positive semi-definite) and the claim follows.
For the induction step, suppose that the claim holds for an n = k − 1 ≥ 2. To establish that it also holds for k, we need to show that
‖C‖2 := ∥∥∥∥∥∥∥∥  C11 C12 . . . C1k C21 C22 . . . C2k ... ... ... ...
Ck1 Ck2 . . . Ckk
 ∥∥∥∥∥∥∥∥
2
≤ kL
as long as ‖Cij‖2 ≤ L for all i, j. Let W = kL · I − C. To show that W is positive semi-definite consider
W1 :=  kL · I − C11 −C12 −C13 . . . −C1k −C21 L · I 0 . . . 0
... ...
... ...
−Ck1 0 0 . . . L · I  ,W2 := W −W1. By induction, it follows that W2 is positive semi-definite. We need to show that the same holds for W1. By Schur complement we obtain that W1 is positive semi-definite if and only if kL · I − C11 − 1 L
∑k i=2 C1iCi1 is positive semi-definite. It follows that∥∥∥∥∥C11 − 1L∑
i
C1iCi1 ∥∥∥∥∥ 2 ≤ ‖C11‖2 + 1 L k∑ i=2 ‖C1i‖2 ‖Ci1‖2 ≤ L+ (k − 1)L = kL.
Hence W1 is positive semi-definite and the induction is complete.
Returning to the statement of Lemma D.4, we will show that∥∥∥∇2πjπiV jµ∥∥∥ 2 ≤ C, (14)
for all i, j ∈ N with C chosen to be 2γAmax(1−γ)3 . Assuming we have shown (14), we conclude from Claim D.5 that ∥∥∇2Φµ∥∥2 ≤ nC, and hence Φ will be nC-smooth (the proof of Lemma D.4 will follow).
To prove (14), we follow the same proof steps as in the proof of Agarwal et al. (2020), Lemma D.3. We will need to prove an upper bound on the largest eigenvalue (in absolute value) of the matrix
∇2πjπiV j µ = ∇2πjπiV i µ,
along the direction where only agent i is allowed to change policy.
Fix policy π = (π1, ..., πn), agents i 6= j, scalars t, s ≥ 0, state s0 and u, v be unit vectors such that πi + t · u ∈ ∆(Ai)S and πj + s · v ∈ ∆(Aj)S . Moreover, let V (t) = V is0(πi + t · u, π−i). and W (t, s) = V is0(πi + t · u, πj + s · v, π−i,−j). It suffices to show that
max ‖u‖2=1 ∣∣∣∣d2V (0)dt2 ∣∣∣∣ ≤ 2γ|Ai|(1− γ)3 and max‖u‖2=1 ∣∣∣∣d2W (0, 0)dtds ∣∣∣∣ ≤ 2γ √ |Ai||Aj | (1− γ)3 . (15)
• We first focus on V (t). It holds that V (t) = ∑ a∈Ai ∑ a∈A−i (xi,s0,a + tui,s0,a) ∏ j 6=i xj,s0,ajQ i s0((πi + tu, π−i), (a,a))
(note that ∑ a∈Ai ∑ a∈A−i(xi,s0,a + tui,s0,a) ∏ j 6=i xj,s0,aj = 1 since it is a distribution), hence taking the second derivative we have
d2V (0) dt2 = ∑ a∈Ai ∑ a∈A−i (xi,s0,a + tui,s0,a) ∏ j 6=i xj,s0,aj d2Qis0(π, (a,a)) dt2
+ 2 ∑ a∈Ai ∑ a∈A−i ui,s0,a ∏ j 6=i xj,s0,aj dQis0(π, (a,a)) dt
(16)
For the remaining of the first part of the proof, we shall show∣∣∣∣dQis0(π, (a,a))dt ∣∣∣∣ ≤ γ √ |Ai| (1− γ)2 and ∣∣∣∣d2Qis0(π, (a,a))dt2 ∣∣∣∣ ≤ 2γ2|Ai|(1− γ)3 ,
and then combining with (16) we get∣∣∣∣d2V (0)dt2 ∣∣∣∣ ≤ 2γ √ |Ai| (1− γ)2 ∑ a∈Ai |ui,s0,a|+ 2γ2|Ai| (1− γ)3 ≤ 2γ|Ai| (1− γ)2 + 2γ2|Ai| (1− γ)3 ≤ 2γAmax (1− γ)3 .
To bound the derivative of the Q-function, observe that Qis0((πi + tu, π−i), (a,a)) = e > s0,a(I − γP (t))−1r, where r(s0, a) is the expected reward of agent i (w.r.t the randomness of the remaining agents) if he chooses action a at state s0 and P (t) is state-action transition matrix of w.r.t the joint distribution of all agents but i, i.e., π−i and the environment. It is clear that d 2P dt2 = 0 (linear with respect to t due to the direct parameterization) and that∥∥dP
dt ∥∥ ∞ ≤ ∑ a∈Ai |ui,s0,a| ≤ √ Ai ≤ √ Amax. Using that ∥∥(I − γP (t))−1∥∥∞ ≤ 11−γ , we get∣∣∣∣dQis0(π, (a,a))dt ∣∣∣∣ = γ ∣∣∣∣e>s0,a(I − γP (0))−1 dP (0)dt (I − γP (0))−1r ∣∣∣∣ ≤ γ √ |Ai| (1− γ)2 ≤ γ √ Amax (1− γ)2 ,
(17)
and also∣∣∣∣d2Qis0(π, (a,a))dt2 ∣∣∣∣ = 2γ2 ∣∣∣∣e>s0,a(I − γP (0))−1 dP (0)dt (I − γP (0))−1 dP (0)dt (I − γP (0))−1r ∣∣∣∣ ≤ 2γ
2|Ai| (1− γ)3 ≤ 2γ 2Amax (1− γ)3 , (18)
Since u is arbitrary, the first part of (15) is proved.
• For the second part, we focus on W (t) which is equal to W (t, s) = ∑ a∈Ai ∑ b∈Aj ∑ a∈A−i,−j (xi,s0,a + tui,s0,a)(xj,s0,b + svj,s0,b)·
· ∏ j′ 6=i,j xj′,s0,aj′Q i s0((πi + tu, πj + sv, π−i,−j), (a, b,a))
(19)
We consider the derivative of W (19) and we get dW (0, 0) dtds = ∑ a∈Ai ∑ b∈Aj ∑ a∈A−i,−j ui,s0,avj,s0,b · ∏ j′ 6=i,j xj′,s0,aj′Q i s0(π, (a, b,a))
+ ∑ a∈Ai ∑ a∈A−i ui,s0,a · ∏ j′ 6=i xj′,s0,aj′ dQis0(π, (a,a)) dt
+ ∑ b∈Aj ∑ a∈A−j vj,s0,b · ∏ j′ 6=j xj′,s0,aj′ dQis0(π, (b,a)) dt + ∑ a∈A ∏ j′ xj′,s0,aj′ d2Qis0(π,a) dtds .
The first term of the sum in absolute value is at most √ |Ai||Aj | 1−γ (assuming rewards lie in [0, 1].) Moreover, using (17) the second term of the sum in absolute value is bounded by γ √ |Ai| √ |Ai|
(1−γ)2 and
the third term by γ √ |Aj | √ |Ai|
(1−γ)2 . To bound the d2Qis0 (π,a)
dtds , the same approach works that we used to prove (18) with the extra fact that the state-action transition matrix is P (t, s) and moreover, the reward r(s0, a, b) is the expected reward of agent i (w.r.t the randomness of all agents but i, j) if i chooses action a and j chooses b at state s0. Finally, for the fourth term we get that∣∣∣∣d2Qis0(π,a)dtds
∣∣∣∣ ≤ ≤ γ2 ∣∣∣∣e>s0,a(I − γP (0, 0))−1 dP (0, 0)ds (I − γP (0, 0))−1 dP (0, 0)dt (I − γP (0, 0))−1r ∣∣∣∣+
+ γ2 ∣∣∣∣e>s0,a(I − γP (0, 0))−1 dP (0, 0)dt (I − γP (0, 0))−1 dP (0, 0)ds (I − γP (0, 0))−1r ∣∣∣∣+ + γ ∣∣∣∣e>s0,a(I − γP (0, 0))−1 d2P (0, 0)dt2 (I − γP (0, 0))−1r ∣∣∣∣
≤ γ2 √ |Ai||Aj | (1− γ)3 + γ2 √ |Ai||Aj | (1− γ)3 + γ √ |Ai||Aj | (1− γ)2 ≤ 2γ √ |Ai||Aj | (1− γ)3 ≤ 2γAmax (1− γ)3 .
Proof of Theorem 4.2. The first step is to show that Φ is a β-smooth function, in particular, that∇πΦ is β-Lipschitz with β = 2nγAmax(1−γ)3 as established in Lemma D.4. Then, a standard ascent lemma for Gradient Ascent (see Lemma C.1 from Bubeck (2015)) implies that for any β-smooth function f it holds that f(x′) − f(x) ≥ 12β ‖x
′ − x‖22 where x′ is the next iterate of equation PGA. Applied to our setting, this gives
Φµ(π (t+1))− Φµ(π(t)) ≥
(1− γ)3
4nγAmax
∥∥∥π(t+1) − π(t)∥∥∥2 2
(20)
Thus, if the number of iterates, T , is 16nγD 2SAmax (1−γ)5 2 , then there must exist a 1 ≤ t ≤ T so that∥∥π(t+1) − π(t)∥∥ 2 ≤ (1−γ) 2D √ S . Using a standard approximation property (see Lemma C.2), we then conclude that π(t+1) will be a (1−γ) D √ S -stationary point for the potential function Φ. Hence, by Lemma 4.1, it follows that π(t+1) is an -Nash policy and the proof is complete.
D.2 FINITE SAMPLE CASE
Proof of Lemma 4.3. It is straightforward from Lemma C.4 and the equality of the partial derivatives between the value functions and the potential, i.e.,∇πiΦµ = ∇πiV iµ for all i ∈ N (see property P2 in Proposition B.1).
Proof of Theorem 4.4. Let δt = ∇̂(t)π −∇πΦµ(π(t)) and set λ = (1−γ) 3
2nγAmax (the inverse of the smooth
parameter in D.4). Moreover, we set y(t+1) = P∆(A)S (π(t) + η∇πΦ(π(t))) (y(t+1) captures the next iterate of the projected (deterministic) gradient ascent). We follow the analysis of Projected Stochastic Gradient Ascent for non-convex smooth-functions (see Davis & Drusvyatskiy (2018), Theorem 2.1) that makes use of the Moreau envelope. Let
φλ(x) = arg min y∈∆(A)S
{ −Φµ(y) + 1
λ ‖x− y‖22
} ,
(definition of Moreau envelope for our objective Φ). From the definition of φ and a standard property of projection we get
φλ(π (t+1)) ≤ −Φµ(y(t+1)) +
1
λ ∥∥∥π(t+1) − y(t+1)∥∥∥2 2
≤ −Φµ(y(t+1)) + 1
λ ∥∥∥π(t) + η∇̂(t)π − y(t+1)∥∥∥2 2
(21)
= −Φµ(y(t+1)) + 1
λ ∥∥∥π(t) − y(t+1)∥∥∥2 2 + η2 λ ∥∥∥∇̂(t)π ∥∥∥2 2 + 2η λ (π(t) − y(t+1))>∇̂(t)π
Since ∇̂(t)π is unbiased (Lemma 4.3) we have that E[δt|π(t)] = 0, therefore E [ δ>t (y (t+1) − π(t)) ] =
0. Additionally, by Lemma 4.3 (applied for all agents i) we also have E [∥∥∥∇̂(t)π ∥∥∥2
2
] ≤ 24nA 2 max
(1−γ)4 .
Hence by taking expectation on (21) we have:
E[φλ(π(t+1))] ≤ ≤ E [ −Φµ(y(t+1)) + 1
λ ∥∥∥π(t) − y(t+1)∥∥∥2 2 ] + 2η λ E[(π(t) − y(t+1))>∇πΦµ(π(t))] + 24η2nA2max λ (1− γ)4 .
Using the definition of Moreau envelope and the fact that Φ is 1λ -smooth (Lemma D.4, after the parameterization, the smoothness parameter does not increase) we conclude that
E[φλ(π(t+1))] ≤
≤ E[φλ(π(t))] + 2η
λ E[(π(t) − y(t+1))>∇πΦµ(π(t))] + 24η2nA2max λ (1− γ)4
≤ E[φλ(π(t))] + 2η λ E [ Φµ(π (t))− Φµ(y(t+1)) + 1 2λ ∥∥∥π(t) − y(t+1)∥∥∥2 2 ] + 24η2nA2max λ (1− γ)4 ,
or equivalently
E[φλ(π(t+1))]− E[φλ(π(t))] ≤ ≤ 2η λ E [ Φµ(π (t))− Φµ(y(t+1)) + 1 2λ ∥∥∥π(t) − y(t+1)∥∥∥2 2 ] + 24η2nA2max λ (1− γ)4
(22)
Adding telescopically (22), dividing by T and because w.l.o.g −Φ ∈ [−1, 0], we get that
1 T + 24η2nA2max λ (1− γ)4 ≥ 2η λT T∑ t=1 E [ Φµ(y (t+1))− Φµ(π(t)) ] − η λ2T T∑ t=1 E [∥∥∥y(t+1) − π(t)∥∥∥2 2 ] ≥ min t∈[T ] { 2η λ E [ Φµ(y (t+1))− Φµ(π(t)) ] − η λ2 E[ ∥∥∥y(t+1) − π(t)∥∥∥2 2 ]
} (23) Let t∗ be the time index that minimizes the above. We show the following inequality (which provides a lower bound on the RHS of (23):
E [ Φµ(y (t∗+1))− Φµ(π(t∗)) ] − 1 2λ E [∥∥∥y(t∗+1) − π(t∗)∥∥∥2 2 ] ≥ 1 λ E [∥∥∥y(t∗+1) − π(t∗)∥∥∥2 2 ] (24)
Observe that by 1λ -smoothness of Φµ we get that H(x) := −Φµ(x) + 1 λ ∥∥x− π(t∗)∥∥2 2
is 1λ -strong convex and moreover, y(t+1) is the minimizer of H . Therefore, we get that H(πt∗)−H(yt∗+1) ≥
1 2λ ∥∥πt∗ − yt∗+1∥∥2 2 , or equivalently
Φµ(y t∗+1)− Φµ(πt∗)−
1
λ
∥∥πt∗ − yt∗+1∥∥2 2 ≥ 1
2λ
∥∥πt∗ − yt∗+1∥∥2 2 .
By taking expectation of terms above, (24) follows. Combining (23) with (24) we conclude that
1 T + 24η2nA2max λ (1− γ)4 ≥ 2η λ2
E [∥∥πt∗ − yt∗+1∥∥2
2
] .
By Jensen’s inequality it occurs that
E [∥∥∥y(t∗+1) − π(t∗)∥∥∥
2
] ≤
√ λ2
2ηT + η 12nλA2max (1− γ)4 . (25)
To get an -Nash policy, we have to bound ∥∥y(t∗+1) − π(t∗)∥∥
2 ≤ (1−γ) 2D √ S(2+ √ nAmax) and choose
α = 2 in the greedy parameterization. This is true because of Lemma C.3 Lemma 4.1. Hence, we need to choose η, T so that√
λ2
2ηT + η 12nλA2max 2(1− γ)4 ≤ (1− γ) 2D √ S(2 + √ nAmax) .
We conclude that η can be chosen to be 4(1−γ)3γ 48nD2A2maxS and T to be 48(1−γ)AmaxD 4S2 6γ3 .

heading: E ADDITIONAL EXPERIMENTS
text: In this part, we analyze variations of the experimental setting in Section 5.
Coordination beyond MPGs. As mentioned in Remark 1, we know that policy gradient converges also in other cooperative settings (e.g., in weighted and asymptotically also in ordinal MPGs). To study such cases, we modify our experiment from Section 5. The setting remains mostly the same, except now in the distancing state the rewards are reduced by a differing (yet still sufficiently large) amount, ck, for each facility k = A,B,C,D. Despite this asymmetry, agents still have aligned incentives. In fact, if the ck’s for all k = A,B,C,D are taken to be greater than c in the MDP from Section 5, then the agents can be said to have even “stronger” incentive to cooperate. The results of running independent policy gradient on this variant are shown in Figure 6. Despite requiring more iterations compared to the symmetric setting, the algorithm still converges to the same Nash policy.
Coordination with more agents and facilities. We next test the performance of the independent policy gradient algorithm in a larger setting with N = 16 agents and Ai = 5 facilities, Ai = {A,B,C,D,E} with wA < wB < wC < wD < wE (i.e., E is the most preferable by all agents). We use a learning rate η = 0.0001 for all agents (which is again much larger than the theoretical guarantee of Theorem 4.2). All runs lead to convergence to an (optimal) Nash policy as shown in the middle and rightmost panels. The leftmost panel shows the distribution of the agents among facilities in both states, which is the same (and the optimal one) in all Nash policies that are reached by the algorithm. The results are shown in Figure 7.
Coordination with random transitions Next, we study the effect of adding randomness to the transitions on the performance of the individual policy gradient algorithm. In this case, we experiment with the same setting as in Section 5 (i.e., N = 8 agents and Ai = 4 facilities that each agent i ∈ N can choose from), but use the following stochastic transition rule instead: in addition to the existing transition rules, the sequence of play may transition from the safe to the distancing state with probability p% regardless of the distribution of the agents and may remain at the distancing state with probability q% again regardless of the distribution of the agents there.
Two sets of results are presented in Figure 8. In the first (upper panels), we use p, q = 1%, 10% and in the second p, q = 5%, 20%. In both cases, we use a learning rate η = 0.0001 (several orders of magnitude higher than what is required by Theorem 4.4). Independent policy gradient converges in both cases to deterministic Nash policies despite the randomness in the transitions. However, for higher levels of randomness (lower panels), the algorithm remains at an -Nash policy for a high number of iterations. This is in line with the theoretical predictions of Theorem 4.4.
Independent Policy Gradient in a Different Environment. A subsequent work to this paper introduced a different multi-agent MDP environment that they prove is an MPG, which they refer to as stochastic congestion games (Fox et al., 2021). This stochastic congestion or routing game was already well-studied before this paper, especially in Mguni et al. (2021), so it is valuable to see that this MPG framework captures such games. In this environment, there is an underlying directed acyclic graph G that has a source node s and a sink node t. There are N agents. The actual states
of the finite-horizon MDP are all the possible positions of the agents on the graph. When the state consisting of all agents being at t is reached, the MDP terminates. At each time step, each agent chooses an action, which in this case is an edge e to transverse, and the cost they experience is a function of the load of the edge, which is the total number of agents choosing edge e. A more complete description and proof that this environment is an MPG is provided in Fox et al. (2021).
We implemented this environment with N = 4 agents, matching the number of agents in Fox et al. (2021), but we were actually able to increase the size of the underlying graph from the 6 vertices done in that paper to 8. The game is visualized in Figure 9.
We used our implementation of the independent policy gradient algorithm with the same parameters as in our experiment from Section 5, specifically we have T = 20, γ = 0.99, and η = 0.0001. The results are shown in Figure 10.

Review summaries:
The paper introduces the Markov Potential Game (MPG), which generalizes the classical potential game. The authors then point out several properties of MPG. It proves the convergence to $\epsilon$-NE for learning agents following independent policy gradient or stochastic gradient. The paper also presents the experiment on a MPG of congestion games that verifies the theoretical results.

The paper introduces a novel class of Markov Games that generalize classical potential games in the normal-form representation. They show that such games always admit deterministic Nash policies, and that they enjoy some interesting properties that they make them a more suitable generalization of potential games than other attempts in the literature. The main result of the paper is that, in Markov Potential Games, policy gradient algorithms converge to Nash. The authors also provide an experimental analysis on congestion games. 

In this paper, the authors present a new definition of Markov Potential Games (MPG). They discuss the relationship between MPG, normal form potential game, and Markov games where every state-game is a potential game.  They study MPGs by presenting sufﬁcient conditions for MPGs and the existence of deterministic Nash policies.  They show the conference of independent-playing policy gradient to Nash policies, in both exact gradient case and finite sample case. Experiment results validate the congergence.