Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
Authors: Stefanos Leonardos
Will Overman
Ioannis Panageas
Georgios Piliouras
Venue: ICLR 2022 Poster (2022)
Keywords: Multi-agent Reinforcement Learning
Markov Potential Games
Policy Gradient

Abstract: Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination in which all agents utilities are perfectly aligned via a common potential function. Can this intuitive framework be transplanted 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 generalize prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs involve settings where state-games can be zero-sum games. In the opposite direction, Markov games where every state-game is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, we prove convergence of independent policy gradient and its stochastic counterpart to Nash policies (polynomially fast in the approximation error) by adapting recent gradient dominance property arguments developed for single-agent Markov decision processes to multi-agent learning settings. 


Published as a conference paper at ICLR 2022
GLOBAL CONVERGENCE OF MULTI-AGENT POLICY GRADIENT IN MARKOV POTENTIAL GAMES
Stefanos Leonardos
William Overman University of California, Irvine overmana@uci. .du
Singapore University of Technology and Design stefanos 1 leonardos@ edu.
Ioannis Panageas
Georgios Piliouras
University of California, Irvine ipanageae ics..ic.ooo www.uci......o.................. edu
Singapore University of Technology and Design georgios@sutd. edu. sg
ABSTRACT
Potential games of the most important and widely studied classes of normal- form 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-intutiivll, insights from normal-form potential games do not carry over since MPGs involve Markov games with zero-sum state- games, but Markov games in which all state-games are potential games are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such the existence of deterministic Nash policies. In main result, we prove convergence of independent policy gradient and its stochastic counterpart to Nash policies at single-agent gradient domination properties to multi-agent settings. This answers questions on the convergence of siniee-sapple independent policy gradient methods beyond settings of pure conflicting or pure common interests.
that polynomial in the approximation error by adapting
INTRODUCTION
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) OpenAl 2018 Vinyals et al. 2019) to robotics, autonomous-driving and cyber-physical systems (Busoniu et al. 2008 Zhang al.)
2019). However, despite the popularity of MARL algorithms to analyze these systems in practice, the theory that underpins their empirical success lags behind (Datoe et al., 2020). Many state-of-the-an theoretical results concern single-agent RL systems, typically modelled as single-agent Markoy
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 2 agents, Nash policy is defined be a profile of policies (mi m/) so that by fixing the policies of all agents but i, गद is optimal for the resulting single-agent MDP and this is true for all < i < n (Definition] Ip. In multi-agent settings, Nash policies may not be unique in principle and, unlike singe-agent MDPs, agents' rewards may differ dramatically between them.
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) (Wagg& & Sandholm 2002 Panait & Luke 2005): the convergence properties of policy gradient in
Analogue of Nash equilibrium notion.

---

Published as a conference paper at ICLR 2022
general MARL settings remain poorly understood. Recent steps towards theory for multi-agent settings involve Daskalakis et al. (2020) who show convergence of independent policy gradient to the optimal policy for two-agent pero-sum stochastic games, |Wei et al. (202I) who improve the result of Daskalakis et al. (200)) using optimistic policy gradient and /Zhao et al. (202T) who study extensions of Natural Policy Gradient using function approximation. It is worth noting that the positive results of Daskalakis et al. (2020); Wei et al. (2021) and ZZao 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), lot of these regularities, and in particular the value- suttuennnque 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 Al and MI. (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 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 long there exists changes their policy (and the rest of the agents keep their policy unchanged), the difference in agent i's value/utility, V is captured by the difference in the value of & (Definition 2).
stateedependent) real-valued potential function t so that if an agent i
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 MPGs involve settings with purely competitive (zero-sum) interactions at some states. Moreover, Markov games in which every state-interaction is 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 The following facts are true for MPGs with n-agents. (a) There always exists a deterministic Nash policy profile (see Theorem 3.7.
(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 7 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 an MPG. These include cases where each potential game and the transition probubilities are not affected by agents actions or the reward functions satisfy certain regularity conditions between different states (see conditions Cl and C2 in Proposition 3.2)
state is a (normal-fore
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¹), then, after ((1/e²) iterations, the system will reach an c-approximate Nash policy. Here, independence means that (PGA) requires only local information to determine the updates, i.c., each agent's '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 e-approximate Nash policy after O(L/e5) 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 > O. (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 e-Nash policy after O(1/e) iterations. (b) Finite Samples: If each agent runs stochastic policy gradient using greedy parameterization (see equation 3 on their policy and the updates are simultaneous, then the learning dynamics reach an e-Nash policy after O(1/e)) iterations.
2

---

Published as a conference paper at ICLR 2022
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 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 agent-wise version of the single-agent gradient domination property which can be used to show that every (approximate) stationary point (Definition 3 of the potential function is an (approximate) Nash policy (Lemma 4.1). If agents do not have access 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 g-gredyy 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 scarce and largely restricted to purely competitive (Daskalakis et al., 2020 Wei et al. 2021; Zhao et al.) (00TT) or purely cooperative (Wang & Sandholm| 2002 Bard al. (0200) 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 Marden (012);; Valcarcel Macual al. (2018); Mguni (2021): p; Mguni et al. (202T) and the partially concurrent work Zhang et al.) (2021). Marden (2012) study Markov games that are potential at every state and which satisfy strong additional state-transitivtty property. Under the same assumption, Mggni] (202T) derive an analogous result to our Theorem 3.1 on the existence of deterministic Nash policies. Valcarcel Macua cct al. (2018) provide an analytical way to find a closed-loop Nash policy in class of Markov games that is more closely related to our current MPG setting (cf. Proposition 3.2). Zhang et al. (202I) study the same class of MPGs, and present additional practical applications. By introducing the notion of averaged MDPs, they derive alternative, model- -odel-based policy evaluation method, which, interestingly, establishes the same sample-complexity (of ((e as our model-free estimation. As pointed out by /Zang et al. 22021), will be instructive further explore this connection. Concerning the technical parts, our methods are related to Daskalakis et al. (2020), g A garwal et al. (2020); Kakade & Langford (2002) and to Davis & Drusvyatskiy (2018): Bubeck (2015); Nemirovski al. (2009).
2 PRELIMINARIES
Markov Decision Processes (MDPs). We consider a setting with n agents who select ac- tions in a shared Markov Decision Process (MDP). Formally, an MDP is a tuple G = (S,N, {,A,, ReN,,, P. where S is a finite state space of size S = |S = (1.2..... n is the set of agents, and A, is a finite action space of size A, = |A, for each agent i e A' with generic element a, Ai. We write A IIseN-A Ai and A-; I1i Aj denote the joint action spaces of all agents and of all agents other than with generic elements = (a:)ee, and a - (az) respectively. R, : S x A- + [-1, 1] is the reward function of agent E N, i.e. R, a, a-;) is the instantaneous reward of agent i when they take action a, and all other agents take actions a at state E S. P is the transition probability function, for which P(s' [s a, is the probability of transitioning from 8 to s' when a E A is chosen by the agents. Finally, 7 (same for all agents) is discount factor for future rewards and p A(S) is distribution for the initial state at time 1 0F
Whenever time relevant, we will index the above terms with t. In particular, at each time step t > 0, all agents i E A observe the state 8; S, select actions a, = (ai,, a.i,), receive rewards Fi == R2 (s), at), and transition to the next state 8t41 ~ P(. | 8r, at). We will write (st. a, r1)120 to denote the trajectories of the system, where re ir..)....
Policies and Value Functions. For each agent i N, a deterministic, stationary policy n; S - A specifies the action of agent i at each state s E S, i.e., (s) = a; E A, for each s E S. A stochastic, stationary policy m. S + ((A.) specifies probability distribution over the actions
We will write A(X') denote the of prohahility distributions over any set X.
3

---

Published as a conference paper at ICLR 2022
of agent i for each state S. Accordingly, n, E II, == A(A)) In this case, will write a, ~ (T(- s) to denote the randomized action of agent at state $ E S. As above, we will write II := (rev((A) and Th (Ty)izjeN
II; XisjeN((A,)* 8 to denote the joint policies of all agents and of all agents other than i, respectively. A joint policy induces distribution Pr" over trajectories т (St, a,, re)120, where so is drawn from the initial state distribution p and ai, is drawn from ..(- sz) for all i N.
(Tp)
The value function, V II - R. gives the expected reward of agent E V when su = s and the agents draw their actions, a, (ai,t, a,r,,, at time t 2 0 from policy (Ti -T-)
V (T) == E7 - T'r
80 =
We also write (T) Egnp [V] if the initial state is random and follows distribution p. The solution concept that we will be focusing on are the Nash Policies which are formally defined next.
Definition 1 (e-Nash Policy). A joint policy πT- = (m] DEE is an e-Nash policy if there exists an 2 0 so that for each agent i E .N, (2 m 2 Vi (T, - E, for all T; E ((A,)) and all S. If 0, then x² is called Nash policy, In this case, कद maximizes each agent i's value function for each starting state E S given the policies, -h = (T3 ( of all other agents j + i N. The definition of Nash policy remains the same if s p (random starting state).
3 MARKOV POTENTIAL GAMES.
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 $ : II + R, with s E S, so that
Vi (T,, क --1) ( +_+) = 1 (T,; --4 $b (T क 1));
for all agents i N, states $ E S and policies T.. oे E II, T-I E II,,. Linearity of expectation im- plies that (p --)) D (p( -) Vid (T, T-1) Vi -T),, where T pT(T) == E.-p [ ( (T)].
As in normal-form games, 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 A there exists function U.- : II -> R so that (T( = (T) + (T for all π E II (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
L m=)), then ç is Weighted Markov Potential Game (WMPG). If for all agents i E N, all states s E S and all policies TT, o.. E II, -h E II_,, the function 4 2. 8 E S satisfies Vi T-+) - (T( 0
w; > O,i E N so that w; VV (T; mi) V ( m=) & ( m_a)
&. (, (T T. π -) 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.c., 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 exact or asymptotic sense) also in these classes of games (Remark []).
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 (199)). This is established in Theorem 3. 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 B. provided in Appendix B
Theorem 3.1 (Deterministic Nash Policy Profile). Let G be Markov Potential Game (MPG). Then, there exists a Nash policy x² E A (A) which is deterministic, i.. each agent E N and each state E S, there exists action 0g A, so that x1 (a; 8) 1.
4

---

Published as a conference paper at ICLR 2022
4 O 4
① d
(a ) (0,0)
otherwise
otherwise
8i
81
otherwise
1
(0.0)
0
2,0
2,0 2,0
0
0.2
0.2
0,2)
0
5.
2
-1, -2
1
2,0
0.2
0,2
1
5,
4
1. 4
Figure an MDP with normal-from potential games at each state which is not an MPG due to games at each state which is an OMPG but not an MPG despite common preferences over states.
Figure 2: an MDP with normal-form potential
conflicting preferences over states.
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 global maximizer of the potential function. At each iteration, we isolate an agent i E N, and find a deterministic (optimal) policy for that agent in the (single-agent) MDP in which the policies of all other agents but remain fixed. The important observation is that the resulting profile is again a global maximizer of the potential and hence, Nash policy profile. This argument critically relies 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 think that MDPs which potential at every state (i.e., the immediate rewards at every state are captured by potential game that state) are trivially MPGs. As we show in Examples I 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 [ 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 T To show that G not an MPG, suffices to show that cannot have deterministic Nash policy profile as should be the case according to Theorem 3.1 (see Appendix B.T). Intuitively, competition arises in Example [ because the two agents play 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 state-based potential game may fail to be MPG even if agents have similar preferences over states.
Example 2. Consider the MDP in Figure In So the agents play Battle of the Sexes game and hence a potential game, while in 81 they receive no reward (which is trivially a potential game). A simple calculation shows that there is not an exact potential function due the dependence of the transitions on agents' actions (thus, this MDP is not an MPG). However, in the case of Example 2 it straightforward show that the game is an ordinal potential game, cf. Appendix B.
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 every state but which are captured by the current definition of MPGs? Figure 3 answers this question affirmatively. Together with Example []] this settles the claim in Theorem
part (b).
Proposition 3.2 (Sufficient Conditions for MPGs). Consider an MDP, G. in which every state E S a potential game, i.e., the immediate rewards R(s, a) (Re SEN for each state E S are captured by the utilities of a potential game with potential function &s. either CI or C2 are true, then G is an MPG.
Cl. geent-independent transitions: P(s' s, a) does not depend on a that is, P(s' ss P(s'
s) is just function of the present state for all states s, s' E ES.
C2. Constant gradient of dummy terms: P(s'] 8, a) is arbitrary, but for the decomposition of each agent's ' immediate rewards in common and dummy terms, R2(s, ai, a) = &s (a;, a.)) + u. (a
with ut A_ R. holds that
Σ 1= J'v,, (a- 80 = 8 c,l,
for all states s' E S, where Co ER,EER RA,, and (T( is the policy distribution of agent at
Condition Cl can be viewed as a special case of condition C2; nevertheless, is more practical to state it separately. Condition C2 (or variations) have been studied in Marden (2012): Valcarcel Macual
5

---

Published as a conference paper at ICLR 2022
SBT
T L-1)
R
(3-4)
(+-
(++)
(9.00 (0L9) (6.15
Figure 3: A 2-player MDP which is not potential every state but which overall an MPG. While state so corresponds to a zero-sum game, the states inside the dotted rectangle do form potential game which can be used show the MPG property whenever po does not depend on agents' actions.
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 uy does not depend on the state 8 nor on the actions of other agents, i.e., u (a_;) e² for some constant et E IR for all a A_., and all E S. A special case is provided by MDPs in which the instantaneous rewards of all agents are the same at each state, i.c. such that (s, a, a-)) = &, (a,, a-x) for all agents i N, all actions a, E A, and all states E S. MDPs that satisfy this condition form 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.
4 CONVERGENCE OF POLICY GRADIENT IN MARKOV POTENTIAL GAMES
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 a-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 The PGA algorithm is given by
((+1) n; = PALANS
+ V.
(PGA)
for each agent E N,, where Pa (AA) the projection onto (AA)) in the Euclidean norm. Here, the additional argument t 2 denotes time. We also assume that all players i / use direct policy parameterizations, i... (a 8) = Fi,s.a- with Zi,e,a 2 0 for all s E S, E A, and EeEA, Ti.s.a 1 for all E 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 which, the actual gradient, V (+)),, is replaced by estimate thereof that is calculated from randomly selected
(yet finite) sample of trajectories of the MDP. This estimate, 4 may be derived from single or batch observations which in expectation behave as the actual gradient. We choose the estimator of the gradient of V to be
(T.)) (0) = R
Σ K=
V Voog n. (a {
(2)
where si ~ p. and R(TM) E along the trajectory generated by the stochastic gradient ascent algorithm at its f-th iterate.
k= r is the sum of rewards of agent for batch of time horizon T
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 E / uses instead direct parameterization with a-greedy exploration follows
(a s) = (1 a. + a/Ai,
(3)
"In 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 be ohtained.

---

Published as a conference paper at ICLR 2022
where a is the exploration parameter for all agents. For a-greedy exploration, it can be shown that (2) is unbiased and has bounded variance. In this case, 1 - y captures the probability that the MDP terminates after each round which ensures that the (finite) length of the trajectory is sampled from geometric distribution. This is necessary for unbiasedness, see /Zhang et al. (2020); Paternain et al. (202T) and Lemma 4.3 (PSGA) is given by
(++1) = PA(A)S (T + t :
(PSGA)
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., V,, Va, (z) = V., ((TT) for all E W (Proposition [. Together with the separability of the projection operator, i.e., the fact that projecting independently for each agent on (AA,)
A is the same as jointly projecting on A(A)) (Lemma D.I this establishes that running PGA or PSGA on each agent's value function is equivalent to running or PPSAA on the potential function Φ. The next step is to study the stationary points of $
Definition 4 (c-Stationary Point of +). A policy profile π := (MI,.... Tn) E A(A) is called 6-
stationary for क w.r.t distribution j as long as max LiEN 5. V., (=) S e, where the max is taken
over all 8 = (f 5%) such that (#1 + 61,..., Tn 5n) E A(A) ExEN || < 1. In words, the function o (r) cannot increase in value by more than along every possible local direction ö that feasible (namely
8 is also 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 μ. E A(S) and any policy и E II, we the distribution mismatch coefficient, where di the discounted state
call D max
distribution 7 Lemma 4.1 suggests that as long as policy gradient reaches a point (7() with small gradient along the directions in ((4)), must be the case that (!)) is an approximate Nash policy. Lemma 4.1 (Stationarity of Φ implies Nash). Let c 2 0, and let π. be an c-stationary point of tb (see Definition Then, it holds that is VSDe(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 an agent-wise version of the gradient domination property of single- agent 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 unique") which implies that the gradient domination property will only be enough guarantee convergence one of the optimal (stationary) points of & (and not necessarily to the absolute maximum of Φ).
The second main ingredient will be fact that 4 is a 3-smooth function (its gradient is Lipschitz) with parameter 3 = 2n (1 ( where Amax == max,eN [A,]. i.c., the maximum number of actions for some agent. Importantly, this implies that /3 scales linearly 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 f-smooth function, f. it holds that f(x') f(x) 23 || 2z| 2 where x' the next iterate of equation PGA Thus, having shown in our context that +b is B-smooth function, this implies that
@ (1((((+))) T (T))
Anyy || [
(1 (1-7)3
n 100
Putting everything together, we can show the following result.
Theorem 4.2 (Formal Theorem I.2 part (a)). Let G be an MPG and let Anux max; |A,). 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) iterations, then there exists a t E [T. such that π. (1) is an e-approximate Nash policy.
Aun for at least T 16ny D2 SA Punn
(1-7)a
(1- (1-7)²²²
"This is in contrast to single-agent MDPs for which the agent has unique optimal value even though their optimal policy may necessarily be unique.
7

---

Published as a conference paper at ICLR 2022
Finite Sample Case. In the of finite samples, we analyze (PSGA) the value V of each agent which (as was the case for PGA) can be shown to be the same as applying projected gradient ascent on 4. The key is to get estimate of the gradient of & (2) at every iterate. Note that 1 - Y now captures the probability for the MDP to terminate after each round (and it does not play the role of discounted factor since we consider finite length trajectories). Lemma arguue that the estimator of equation equation 2 both unbiased and bounded.
Lemma 4.3 (Unbiased estimator with bounded variance). It holds that ((0) Ri an unbiased estimator of Vs, 2 for all E NN, that is E
Vit = vx (=(==)) for all E N. Moreover, for all agents 24 m1 <l1->)a for all e.N
Eg(
i E N, it holds that Ey0
(1)
Using the above, we can now state part (b) of Theorem 1.2 Together with Lemma 4.3 and the stationarity Lemma (Lemma(.1) 4. J. 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) their policies using a- a-greedy parameterization with a = e² and learning rate (step-size) rj 48 for at least
((117)²1
iterations, then there exists {L,..., T} such that in expectation, 48(1 48(1-7)AAux @ o D s
x() is an 6-approximate Nash policy.
Using Markov's 's inequality, 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's T and and the learning rate to 778 = d2 where E (0, 1). then with probability that (+) is an e-approximate Nash policy. However, this is weaker than desired statement, since, optimally, the rumning time should be logarithmic (instead of polynomial) in 1/8 (Nemirovski et al. 2009). Proving such a statement requires bounds on higher moments of the gradient estimator which turn, require sampling and averaging over multiple trajectories (per iteration).
å there exists a E {I...., such
Remark 1 (Convergence in WMPGs and OMPGs). It is rather straightforward carry over to WMPGs (ef. 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, is quite straightforward that converges asymptotically to critical points (in bounded domains) for differentiable functions. Thus, as long as & differentiable, it is guaranteed that PGA will asymptotically converge to critical point of Φ. By Lemma 4.1 this point will be a Nash policy.
that our results
5 EXPERIMENTS: CONGESTION GAMES
We next study the performance of policy gradient in a general class of MDPs that are congestion games at every state (cf. Roughgarden 2015): 3) 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 experiment (Figure 4 with N' = 8 agents, A; 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 & is equal to a predefined positive weight safe times the number of agents at k A, B, C, D. The weights satisfy safe < w safe wh i.e.. facility D is the most preferable by all agents. However. if more than = 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
4 facilities
distancing state
N/2
N/4
state
Figure 4: The 2-state MDP.
8

---

Published as a conference paper at ICLR 2022
same for all agents, but reward of each agent is reduced by constant amount, where 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, agents need to achieve maximum distribution over facilities; no more than 2 = N/4 agents in a facility. We consider deterministic transitions; however, the results quantitatively equivalent also when these transitions occur with some probability (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 7 = 0.99 and a common learning rate 7) 0.0001 (larger than the theoretical guarantee, 1) [1 (1->)²
1e 08, of Theorem 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]
27-Amax"i
Results. The left panel of Figure 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 Ll-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, fnnll
i.e. I.1 -.ccuuuryyy = N EiEN [T;
N ΣiEN E. Eo (T
final (a 8)|- m
35
Maxr 11 socamcy
Catteciig itre
08
03
0 0
200
200 400
0
-00
20C
202
Figure 5: Policy gradient in the 2-state MDP with 8 agents of Section learn one of the deterministic Nash policies that leads the optimal distribution among states (left). Individual trajectories of the Ll-accuracy and averages (with 1-standard deviation error bars) show fast convergence in all cases (middle and right columns).
5 In all runs, the 8 agents
CONCLUSIONS AND FUTURE DIRECTIONS
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 polynomial rate in the approximation error to a Nash policy profile even in the case of finite samples (in that case, using direct parameterization with greedy exploration). MPGs
first step cover the gap between the extremes of pure coordination (singlc-agent or MDPs with identical agents) and pure competition (two-agents, zero-sum MDPs).
Open Questions. Our examples and counter-example of MPGs suggest that multi-agent coordina- tion in state-based interactions is still far from understood and constitutes a major direction for future research in which techniques from cooperative Al (Kao et al. 2021 Mao al., 2021 or linear MDPs (Jin et al. 2020) may turn out to be particularly useful. From an al algorithmic perspective, a second direction for future work involves the analysis of policy gradient with different parameterizations
(Agarwal et al. (0200) or of other naturally motivated online learning algorithms (Kleinberg et al.
2009 Panageas et al. 2018 Mehta et al., (015) and the adaptation of advanced techniques (Cohen 2019) to reproduce convergence and equilibrium selection results from normal-
et al. 2017 Lee et al. form to state-based (Markov) games. Alternatively, would be interesting to test whether complex behavior (e.g., limit cycles, periodic orbits) of learning dynamics that has been observed in restricted normal-fome settings Mertikopoulos et al. (2018); Vlatakis-Gkarrgkoomma 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).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This research/project is supported in part by the National Research Foundation, Singapore un- der its AI Singapore Program (AISG Award No: NRF-NRFF2018-07
NRF 2018 Fellowship ALIAS grant. grant PIE-SGP-AI-2020-4 AME Pro- grammatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR), Provost's Chair Professorship grant RGEPPV2101 and by EPSRC grant EP/RO1 8472/1..
REPRODUCIBILIT 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) supplementary material.
REFERENCES
A. Agarwal, M. Kakade, D. Lee, and G. Mahajan. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes. In J. Abernethy and S. Agarwal (eds.), Proceedings of 33rd Conference on Learning Theory, volume 125 of PMLR, pp. 64-66, 2020. URL http: htt.:::/pproceeiigg.
m www..pprsssvve httpp/////aagaaaaaaaa2/
html
N. Bard, J. N. Foerster, S. Chandar, N. Burch, M. Lanctot, H. F. Song, E. Parisotto, V. Dumoulin, S. Moitra, E. Hughes, Dunning, S. Mourad, H. Larochelle, M. G. Bellemare, and M. Bowling. The Hanabi challenge: A new frontier for AI research. Artificial Intelligence, 280:103211 2020. ISSN 0004-3702. doi: 1.1011/..artint2201
D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2nd edition, 2000. ISBN 1886529094.
I. Bistritz and Bambos. Cooperative multi-player bandit optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neurul Information Processing Systems, volume 33, pp. 2016-2027. Curran Associates, Inc., 2020.
N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456):885-890 2019. ISSN 0036-8075. doi: 10. /2/////ienncceaay22000.
S. Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4): 231-357, 2015.
L. Busoniu, R. Babuska, and B. De Schutter. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-17) 2008. doi: 10. 109/TSMCCC2200.113999
M. Carroll, R. Shah, M. K. Ho, T. Griffiths, S. Seshia, Abbeel, and A. Dragan. On the Utility of Learning about Humans for Human-AI Coordination. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, 2019.
J. Cohen, A. Héliou, and P. Mertikopoulos. Learning with bandit feedback in potential games. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 63811, 2017.
A. Dafoe, F. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. 7. Leibo, K. Larson, and T. Graepel. Open Problems in Cooperative AI. arXiv e-prints, December 2020.
A. Dafoe, Y. Bachrach, G. Hadfield, E. Horvitz, K. Larson, and T. Graepel. Cooperative ai: machines 170-0.
must learn to find common ground. Nature, 7857:33-36, 2021. doi: 10.
C. Daskalakis, D.J. Foster, and N. Golowich. Independent Policy Gradient Methods for Competitive Reinforcement Learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5527-5540. Curran Associates, Inc., 2020.
10

---

Published as a conference paper at ICLR 2022
D. Davis and D. Drusvyatskiy. Stochastic subgradient method converges the rate O(k-1/4) weakly convex functions. CoRR, abss/180..02988, 2018.
R. Fox, S. McAleer, W. Overman, and I. Panageas. Independent natural policy gradient always converges in markov potential games, 2021.
S. Ghadimi and G. Lan. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. SIAM J. Optim., 23(4):2341-2368, 2013, doi: 10.1137/120880811
M. Jaderberg, W. M. Czarnecki, I. Dunning. L. Marris, G. Lever, A. Garcia Castañeda, C. Beattie, N. C. Rabinowitz, A. S. Morcos, A. Ruderman, N. Sonnerat, T. Green, L. Deason, J. Leibo, D. Silver, D. Hassabis, K. Kavukcuoglu, and T. Graepel. Human-level performance in 3D multiplayer games with population- based reinforcement learning. Science, 364(6443):859--888) 865, 2019. doi: 10.1 00.11666cieence.auu2..4
C. Jin, Z. Yang. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In J. Abernethy and S. Agarwal (eds.). Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2137-2144 PMLR, 09-12 Jul 2020. URL jin20a html.
.ml. www.s/rsssvv.. v125/
Kakade and J. Langford. Approximately Optimal Approximate Reinforcement Learning. In Proceedings of the Nineteenth International Conference Machine Learning, ICML '02, pp. 267-2744 San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. ISBN 1558608737.
H. Kao, C.-Y. Wei, and V. Subramanian. Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure, 2021.
R. Kleinberg, G. Piliouras, and E. Tardos. Multiplicative Updates Outperform Generic No- No-Regret Learning in Congestion Games. In ACM Symposium on Theory of Computing (STOC), 2009.
E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In (STACS), pp. 404 413. Springer- Verlag, 1999.
D. Lee, Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and Recht. First-order methods almost always avoid strict saddle points. Mathematical programming, 176(1)3311-33) 2019.
W. Mao, T. Başar, L. F. Y., and K. Zhang. Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration, 2021.
J. R. Marden. State based potential games. Automatica, 48(12))3075-3088 2012. ISSN 0005-1098, doi: 10.1016/j.automatti 2tt.:ommmaaaaa2222......3
R. Mehta, Panageas, and G. Piliouras. Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and Conjecture of Haploid Genetics. In Innovations in Theoretical Computer Science, 2015.
Mertikopoulos, C. Papadimitriou, and P. Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 2703-2717 SIAM, 2018
D. Mguni. Stochastic Potential Games, 2021.
D. Mguni, Y. Wu, Y. Du, Y. Yang, Z. Wang, M. Li, Y. Wen. J. Jennings, and J. Wang. Learning in Nonzero-Sum Stochastic Games with Potentials. arXiv e-prints, art. arXiv:2103.09284 March 2021.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, Fidjeland, Ostrovski, Petersen, C. Beattie, A. Sadik, Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforce- ment learning. Nature, 518(7540):29--335 Feb 2015. ISSN 1476-4687, doi: 10. 10.1038/nature 14236.
D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 14(1):124-1) 1996. ISSN 0899-8256. doi: 10. 10.1006/game. 1996.0044.

---

Published as a conference paper at ICLR 2022
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-1600) 2009. doi: 10.1137/ 070704277.
OpenAL. Openai five. openai.com 2018.
1. Panageas, G. Piliouras, and X. Wang. Multiplicative Weights Update Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always. In ICML, 2018.
L. Panait and S. Luke. Cooperative Multi-Agent Learning: The State of the Art. Autonomous Agents and Auett-Agent Systems, 133):387-434, Nov 2005. doi: 10. 10.10077/10458-000-
S. Paternain, J. A. Bazerque, A. Small, and A. Ribeiro. Stochastic Policy Gradient Ascent in Reproducing Kernel Hilbert Spaces. IEEE Transactions on Automatic Control, (568))3429-34444 2021. doi: 10. 10.1110
T. Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM, 62(5), November 2015. ISSN 0004-5411. doi: 10.1 155/2808888.
T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):
236-259) 2002.
L. S. Shapley. Stochastic Games. PNAS, 1953.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, Sutskever, T. Lillicrap. M. Leach, K. Kavukeuoglu, T. Graepel, and D. Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484-444 489, ISSN 1476-4687. doi: 10. 10.t03//ntture 16961.
(189,Jan Jan 2016.
D. Silver, T. Hubert, Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Ku- maran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi. and Go through self-play. Science, 362(6419):1140-111 1144, 2018. ISSN 0036-8075. doi: 10. 1211///eecee.aarreee a44444
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
S. Valcarcel Macua, Zazo, and Zazo. Learning Parametric Closed-Loop Policies for Markov Potential Games. In International Conference Learning Representations, 2018.
O. Vinyals, L. Babuschkin, W. M. Czarnecki. M. Mathieu, A. Dudzik, J. Chung. D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, Oh, D. Horgan, M. Kroiss, I. Danihelka, A. Huang, L. Sifre, T. Cai, J. P. Agapiou, M. Jaderberg, A. S. Vezhnevets, R. Leblond, T. Pohlen, V. Dalibard, D. Budden, Y. Sulsky, J. Molloy, T. L. Paine, C. Gulcehre, Z. Wang, T. Pfaff, Wu, R. Ring, D. Yogatama, D. Wünsch, K. McKinney, O. Smith, Schaul, T. Lillicrap, K. Kavukcuoglu, D. Hassabis, C. Apps, and D. Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)3350-355 3544, Nov 2019. ISSN 1476-4687. doi: 10.1038/s41586. -51--11--221
E.VV. VlatakisGGkarakkooma mixed nash equilibria: They do not mix. In Annual Conference on Neural Information Processing Systems, 2020.
Flokas, P. Mertikopoulos, and G. Piliouras. No-regret learning and
X. Wang and Sandholm. Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games. In Proceedings of the 15th International Conference Neural Information Processing Systems, NIPS'02, 02, pp. 1603-1610, Cambridge, MA, USA, 2002. MIT Press.
C.-Y. Wei, C.WW. Lee, M. Zhang, and Luo. Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games. CoRR, abs/2102.04544 2021.
K. Zhang, Z. Yang, and T. Bayar. Multi-Agent Reinforvement Learning A Selective Overview of Theories and Algorithms, arXiv e-prints, art. arXiv: 2019.
12

---

Published as a conference paper at ICLR 2022
K. Zhang, A. Koppel, H. Zhu, and T. Başar. Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies. SIAM Journal on Control and Optimization, 58(6):356-3312, 2020. doi: 10.1 10.1137/1M11280022
R. Zhang, Z. Ren, and N. Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity, 2021.
Y. Zhao, Y. Tian, D. Lee, and S. Du. Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games. CoRR, abs/2102.08903, 2021.
A ADDITIONAL NOTATION AND DEFINITIONS: SECTION 2
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 II and the agents draw their actions,
R. gives the expected reward of agent E A when a, (0i,e a a.,)), time 2 0 from policies ι = (m,; m-x) and is defined
(T) == Ersa Σ Mrua 80 = =
Similarly, we will write (T) == R (+r) to denote the expected value of agent i E V under the initial state distribution p.
For any state 8 E S, the Q-value function Q' P A + R and the advantage function A P x A R of agent E N are defined as
(1( == Erox
xra . 50 = 5, = a and
(5)
A)(T,a) -
Discounted State Distribution. It will be useful to define the discounted state visitation distribution d (s) for s E S that is induced by a (joint) policy π as
(s) (1- >) Σ 7 Pr (st = =s)s))
for all s e S.
As for the value function, we will also write (s) = Esoopll (s)] to denote the discounted state visitation distribution when the initial state distribution is p.
B OMITTED MATERIALS: SECTION
3
Proposition B.1 (Separability of Value Functions and Equality of Derivatives). Let G = (S,N, (A.HEN R. p) be a Markov Potential Game (MPG) with potential 4b 8. for s S. Then, for the value function V E S of each agent i E N, the following hold
PI. Separability of Value Functions: there exists a function U ((AA,) R such that for each joint policy profile π n-i) E A(A)S, we have V2 (.( (()
P2. Equality of Derivatives: the partial derivatives of agent i's value function V coincide with the partial derivatives of the potential 4, that correspond agent i's parameters, i.e., Dn,,.. Vi(Tt) dr... (T(T), for all E N and all E S.
Proof. To obtain Pl, consider any arbitrary policies for agent i, notated by ni Th. TH A(A.)
Then, by the definition of MPGs, we have that
(T; π --) $2( T-)) = Vi TT Vi m-))
(T,,, --)) Tb (TT"" m- (TT V.(,", , -
13

---

Published as a conference paper at ICLR 2022
for every starting state S. This implies that write (Ts, T-+) as both
(m,,, n--) = ( क --)) - 4 (,, m- + V/ (TT x-i)
(m,, -T- ( πl m-)) ( n + V (Tt πT-)
Thus, have that - (T, (-) (T T-1) - D ( ग --) )) + V7 (T --) for any arbitrary
pair of policies zi and ग. for agent i, implying that agent i's policy has no impact on these terms. Accordingly, we express them
(= == D. (T.
(T m-)) = (,,"", T-)) + (T",, T-1).
where (T-+)) is function that does not depend the policy of agent i. Thus, can express the utility function of any agent i in an MPG as
(T) (T) (x) (T
as claimed. To obtain P2, we use P1 for a vector x; parameterizing T. and obtain that
Dz., (T) Dz... ((T)) 0
for any coordinate Vi, with a E A; of 24, from which we can see that our claim is true.
Note that P1 serves as a characterization of MPGs. Namely, agent MDP is an MPG if and only if the value function of each agent E N can be decomposed in term that is common for all players (potential function) and in term that may be different for each agent i E 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.7 Let & be the potential function of G. Since the space =A))==A(A))) ... ((A,)) is compact and & is continuous, & has global maximum $ maxx- Let [Tī m denote global maximizer, i.c., a joint policy profile at which & max is attained. By the Definitions of MPGs and Nash policies, this implies, in particular, that (Iī mny xT) is a Nash policy, since
4 (M), xL,) (T,,, +-+) = (T m V (mT, m_,);
for all i N, E S and all policies म. E A(A.)). If TH. .... n, are all deterministic we are done. So, we may assume that there exists an i E E so that ग. is randomized and consider the MDP G' in which the policy of all agents other than i has been fixed to -- G' is 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 single agent MDP, this setting has a deterministic optimal policy, say म;, for agent i. Thus, it holds that
(T S VI(T, S (fr,
where the first inequality follows from the fact that n²" is a Nash policy and the second from the optimality of क.. follows that
Vi mi.) (ITT,
i.e., the payoff of agent i (mt, x1,) the same in (mt, mi,) Hence, by the definition of the potential function, we have that
0 V (T,, m",) Vi x-x) ( mi.) ((T(m(m)))
which implies that
( m (_) m_ max.
Thus, (#t, m) ) is also global maximizer of &b which implies that (#t, is a Nash policy by the same reasoning as in equation equation Note that the value of all players other than may not be the same at the joint policy profile (M; --n) as it is in (m;,T",) 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 πミ becomes deterministic for all agents j E N, obtain the claim.
14

---

Published as a conference paper at ICLR 2022
Proof of Proposition 3.2 The proof is constructive and proceeds by finding the potential function, Lg. 8 E S in both cases, C1-C2. Since the individual rewards of the agents at each state s are captured by potential function ox. then for the reward, (s, a) of each agent at the action profile a, it holds that
as) (.(a) + (a-:).
where u² : A(A-:) + R is a function that does not depend on the actions of agent in any way. Thus, we may write the value function of each agent E N as
(m(() = Brax
Σ
PB ac)
80 =
-TTx
(o., (ar)
+ u/z, (a_,,)) |so =
E 2'0s, (ar)
[ -= I' (a 80 8|
80 =
+ E
where I ~ i is the random trajectory generated by policy To show that 9 is an MPG, it suffices to show that the value function of each agent E / can be decomposed in a term that is common for all agents (and which may depend on the actions of agent i E W) and in a term that does not depend (in any way) in the actions of agent (dummy term), cf. Proposition B. The first term in expression equation [ i.e., E,s" [_>= 7'd,, (at) 60 =s. depends
the actions of all players and is common for all agents i E NVN(and is thus, good candidate for the potential function). The second term in expression equation i.c., Er>, |Ez= "'u,, p (a-i,) so = s]. does not depend on player via the payoffs wi, (a.i,)) but, in general. 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 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 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
$ $.(T) = E
The ( (at) 80 =
potential function and (= Eywr E >nu (a-i,) so s] is a dummy term that does not depend (in any way) on the policy of agent i E N which proves the claim.
Condition C2. We will show again that
Tet ( = ETAT
Ye (a) Σ t=
80
is a potential function for G and that the same decompasition as in condition C1 of the value function of agent in a common and dummy term applies. To see this, let ,, T/ II, be two policies of agent i and let = (m, m)= x' = (m/x R-)) where ._ is the fixed policy of all agents other than i. Then, using equation + we have that
V (TT (3')
Xc Σ r'u (a (aa=,)))
8
= ( Φ. (~') + R
ETA
Σ
2 Nuu
(a
80
&'
The intermediate value theorem implies that there exists policy & which a convex combination of Tia ni. such that
E PrOUT
Σ l'u, (a.1)
so 5'
E Eynn!
Σ Y'u,, (a.,e)
1=
-iT,, T:) T Vn E Err(S
Σ
ru (a
8o =s
1=0
15

---

Published as a conference paper at ICLR 2022
The displayed condition in C2 implies that
N, ((
yuu uu (a.,)) Σ t=0
so =
(c.1),ES,
which is enough ensure that the dot product in the previous equation is equal since my T. correspond to probability distributions at every state E S, and the sum of their component-wise differences equal O. This proves the claim.
Summing up. in both cases, C1-C2, 9 is an MPG as claimed.
Note that the proof the (trivial) case in which the instantaneous rewards of all agents i V are equal at each state E 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... it holds that Rş(s, a) = o, (a) for all i N and all S. In this case, it holds that ut (a_:) = 0 for all i M and all E S and hence,
(T( Erow
Σ t==
is a potential function for G, and the dummy terms are all equal to O, i.e., (+(T-:) = O.
B. EXAMPLES
Example 1 (Continued). We prove the claim that G cannot have a deterministic Nash policy profile. To obtain contradiction, assume that agent A is using deterministic action aa {0, 1} at state 0. Then, agent B, who prefers to move to state 1, will optimize their utility by choosing the action aB {0, }} that yields dq @ a
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 deterministic optimal policy profile as claimed.
Example 2 (Continued). At each state, E {0, }}. the agents' payoffs, (R,, RC), form a potential game (at that state), and are given as follows
1
5, 2
-1, -2
with potential 4u (-a
State 0: (R), RB)
)
-5,
-4
1,
4
State 1:
(R], R3) = (0, 0), with potential
$ =
In this MDP, agents need only select action state 8o- Thus, will denote policy, #1, of agent 1 by Ti = (p, - p) where p E [0, 1] is the probability with which agent A selects action at state sg. Similarly, we will denote a policy, т2, of agent B by nं = (q, 1 - q) where g [0, 1] the probability with which agent B selects action 0 at state 5g. Moreover, we will slightly abuse notation and write
(T)(T) = (T R2) म. Rinz [p, - p) R2 (g, 1 q)
We also assume that the horizon is infinite and there is discount factor E [0, 1). Accordingly, we can calculate the value functions Vij (M1, π2) of agents = A, B starting from state sy as follows,
(T( (T) + ( - r(1 pq) x 0
which yields the solution
R (
(T(
for i A, B.
7p
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
16

---

Published as a conference paper at ICLR 2022
is similar for agent 2: here for agent and 2 for agent B). For policy π (TI, TT), have at state 8y that
E E- (Aao)) a)] - p (2) (1 p) p) 1,',,
= =p (0, (0, T2) + 7 Vo(=)) + (1 (1-18 p) [R)(1, + Vo(TT)]
= -Rt (0, π2) + (1 p) R (0, m2) (1 -opPT)
= - - (1- Vo (T
At state 51, there is only one available action for each agent which yields payoff of 0. Thus, (4) (TT, a)] O.
(-
Moreover, concerning the discounted visitation distribution, we have that
1 -
(su) =1 10-7 7) 'Pr" (st so so) (1 7) [1 ypq + (rp9)² + +...]
7Pp
and dī (81) 1 dī (80) Vo(T) Vo(TT)
7(1 (11ppg) Thus, using all the above, have that
1 1-7
1
1 1-7
(R) (1- (1-77))V6(=7)) + 7(1 100-190 p4)
1 y
1 YPQ
1 7PQ
R (T)
Vo( = Vo( Vo
1-7pq 7P4
which shows that our initial calculations conform with the outcome specified by the Performance Difference Lemma.
Finally, a direct calculation shows that +, &, for = 0, 1 is a valid potential function for which the MDP is an ordinal MPG.
Example 3 (Continued). At state 80, we consider the game with action sets A1 = A2(su) {H,T} and (instantaneous) payoffs
H
T
H
T
H
-1 1 -1 1
and Ra(so, al u2) T 1 1
H -
Ri a1, a2)
where d denotes the action of agent and 02 the action of agent 2 (agent 1 selects rows and agent 2 selects columns both matrices). This constant sum game (equivalent to zero-sum) and hence, not (ordinal) potential game. Apart from the instantancous rewards, agents' actions so induce a deterministic transition to a state which the only available actions to the agents are precisely the actions that they chose state sg and their instantaneous rewards this state are the rewards of the other agent at sg- In particular, there are four possible transitions to states Sab with a, E ( {H, T), with action sets and instantaneous rewards given by
A1 (Sab) (2) for agents and 2, respectively. Note that the visitation probability of this states is equal to the visitation probability of state su- After visiting one these states, the MDP transitions to state $1 which is potential game, with potential function given by
{b), (sat, a, R2(so, b, a), R2(Sab, a, Rı (Sus b, a),
R
L R
3
3
0
As mentioned above, the game state Su does not admit a potential function. However, the joined rewards RJJ, RJ2 of agents and which result from selecting an action profile (a, H, T so and then traversing both So and the ensuing sub (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 given by
H
T
H
H 1
1-1
1
H
0
0
Poob
1-1
17

---

Published as a conference paper at ICLR 2022
Let X1) x1) denote policy of agent 1. Here Xo (zu, - zo). where zo E [0, is the probability with which agent chooses action at state Su- Similarly, X1 = (01, x1) where 21 [0,1] is the probability with which agent chooses action L at state 81. At states Sab: a, b E {H, 7) agents only have one action to choose from, so this choice eliminated from their policy representation. Similarly, represent policy of agent by m2 (Yo,Y1) with
yo. 91 E [0, 1J. Let also
Po = po (T,, π2) = Pr($e+1 = 80 8, 81, 31, 91,T1,722!
In the general case, Po, i.e., the transition probability from 81 to so, may depend the actions of the agents or it may be completely exogenous (i.e., constant with respect to agents' actions). we write
Po(a1. 02) == Pr(s so 8t $1, 01 02), for d1 02 R).
to denote the probability of transitioning from state $1 to state so given that the agents chose actions a1, 02 E {L, RJ at state 81, then we can write Po as
Po ((s. (a1, a2)]
Σ
Pr(a1, 02 (T. (o((a1,00) 02)
(a) (LL.)))
Eivioo L) + (1 v1 Pol,, R) + 21 21))1 RR 111-xp z1) b1) R. R).
(10)
Using this notation, can now proceed to compute the value function of each state of the MDP in Figure 3
Since the value of states Sa a, b E H, 2 is equal to constant reward plus the value of state $1 (discounted by 7), it suffices to calculate the value for states so and $1. We have that
Vo (TI, n2) XuRoyo + 7 (xo (Rg/>) yo) + V (T1 T2)
V/3 (m, m2) = x1 R|y 1 + (Po Vol (TI: T2) + (1 (1-po)) po) (m1,
which after some trivial calculations yield
Vol T2) = Xu RR + Rb) No + V (T1,
V/ (m),)) v2) = 1 (1 - Po)
[x + ypo Vol (TI, [2)]
This is a system of 2 equations in the 2 unknown quantities, Vol (T1, m2) and Vi (π1, Solving for these two quantities, yields the unique solution
Vol (TI.T) = 1 - 7/ 1 po) - 700 71 po)) xo (R) + RD) yo + 7 R[y].
V (m, m2) (2)
7 (1 po) - 22 [YPOXo (R)) RS) yo + x2 R|yy]
In the case that Po is a constant with respect to TΙ, T2. then both value functions are of the form
V (IT, m2) = e1 (s) X (RD) + R?))) yo + c2 (s) x1 for E (50, $1}, and = {1, [1,
where e₁ (s). (s) > are appropriate constants that depend only the state s E {so, $1} and on agents 1, 2. Since the game at is potential game, with potential function given by 2 x matrix 2, is immediate to infer that
V (Tis T2) V (πI, &, (T1, m2) 2, (T1, (2) for (50s s1h.
with
4 (TI, 22) = ci (s) Xo (R) + RZ) yo + 02 (s) x 41y1, E (s0,
However, if Po depends on the actual policies of agents and 2, ef. equation equation 9 then it not immediate to determine 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 so the states Sab need not be deterministic. To see this, let q E (0, 1) and assume that if the agents select actions H, T is sp, then the process transitions with probability q state SHT with rewards (-1, 1)/97 / and with probability
q) to a state s'rr
18

---

Published as a conference paper at ICLR 2022
with rewards (1,-1)/(1- 7). The rest remains the same. Accordingly, the expected reward for agent 1 after (H has been selected Su is the same as in the current format.
Second, the construction with states so and Sab: (a, b) E H, T is not the only one that leads to such an example. Another very common instance occurs in the case of aliasing between so and states Sob. ie., 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 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 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 7). Thus, the construction works in both episodic and continuing settings.
C AUXILIARY LEMMAS
Before proceeding to the omitted materials of Section 4 we first include some auxiliary results that 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 3-smooth function with convex domain X.
Let x. E X, xt (x fx()) and gx (x) 3(x x+). Then the following holds true:
1
f(x f(x)
19x (2)1
23
Lemma C.2 Agaawal et al. (2020), Proposition B.1). Let f(T) be a 3-smooth function in π E ((A)S. Define the gradient mapping
G(*) = 3 (ALA)S ( 1
(++T)=((m) -
and the update rule for the projected gradient is nt = (((T). If [[((T)] S then (A) [vf((')) S 2e.
Lemma C.3. Let 1 (T) be the potential function (which is 3-smooth) and assume A(A)S uses a- a-greedy parameterization. Define the gradient mapping
G(T) 8 (PALAJS
3
and the update rule for the projected gradient is T' = G(T). If [[((T]] S e, then
VT (=')) S 2c + v AnaAAax.
max +++EA(A)).11611
118111
Proof. It is a direct application Lemma
C.2 and the fact that D is Lipschitz with parameter vnAmug (this is Proposition 3 in page 23 of Daskalakis et al. (2020)..
(1->)²
Lemma C.4 (Unbiased with bounded variance Daskalakis et al, 2020 It holds that ( is unbiased estimator of V.,y V for all that is ( (1) V V2 for all i. Moreover, for all agents we
(0) < a(1 a11-7)4
24A2
get that (this is what the authors actually prove), it holds that Eg00
D OMITTED MATERIALS: SECTION 4
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 μ E A(S) and any policy the distribution mismatch coefficient, where oi is the π E 11, we call := max, discounted state distribution 7
Diifferentiable with V be f-piphhiizz
19

---

Published as a conference paper at ICLR 2022
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, that the policy vector m! remains probability distribution for all agents i / (see (PGA)). It is not hard to show (due to separability) that the projection operator being applied independently for each agent on ((A:) S is the same as jointly applying projection on ( This is the statement of Lemma D.I.
Lemma D.I (Projection Operator). Let ग :- (Ti,..., Rn) be the policy profile for all agents and let T' v & (T))) be a gradient step on the potential function for step-size o >> O. Then,
PA(A)S (P'(AI)) (T'). ..... PA(AA))
Proof of Lemma D.1 Observe that Px(y) = arg min sex || - yll2 for any set &' C R". Thus,
(a(())(U)) = arg min || T'112 zEA(A)S
arg min
Σ 1=1
1la; Tlll2
m.EA(A))) CA(A,))
Σ
arg min | - -; (P (PA(A.)*(TT) PA(A.))(TT))) (A()))
The main implication of Lemmal D. along with the equality of the derivatives between value functions and the potential function in MPGs, i.e., V., (T) V. ((x) for all i E . (see property P2 in Proposition B.I. is that running independent equation PGA on each agent's value function is equivalent to running equation PGA on the potential function 4. In turn, Lemma 4.1 suggests that
as long policy gradient reaches point (1) with small gradient along the directions in ((A)S, must be the that (1) 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 deviates optimal policy m. (w.rt the corresponding single agent MDP). Since π is e-stationary it holds that (Definition
max (T/) T TV. ()(()))))) S VSe. T(EA(A:)
(11)
Thus, with n² = =(m;; -)), Lemma D.3 implies that
1
dz
D
0p(TT) - (T)
max (o)
(T'' (T'
/S..
(12)
1
Thus, using the definition the potential function (cf. Definition
2
we obtain that
VSD
(²((T)) (T) 2,(=T)
(T(
1 1-7
Since the choice of was arbitrary, conclude that is VSDe 1-7
approximate Nash policy.
To prove Lemma D.3 will 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 agent N. Then, for any policies (m, T-i,, x' (m/, -i)) E II and any distribution E (SS), it holds that
1
(T((T) - V'((')) = 1-7 Eondy E, En, En por - (1b)) [A at a.)]
where a (c 8) denotes the action profile of all agents other than i that drawn from the product distribution induced by their policies m (πz))zieN I-
20

---

Published as a conference paper at ICLR 2022
Proof. For any initial state E S and joint policies π (Te,, TT)); n' (4/, T--) E II, it holds that (T( - (+(²') = E
TTrc 80 s) (x()²)
E
(ris (=) + Va, (T()) s0 = (+'
E
1=0 7¹ (Tre - VT,( + > >/V... (T') 80 =
E
(ri.e + 71R [Va.4] (T²) 81, Di,t a Vs, (T)) 800 =
1=0
E
7 AA, (TT,, a.) 30 =
t=
Byrnay E (.))); En fيm c(s5) [A (TT .)]]
Taking expectation over the states 8 E S with respect to the distribution P E ASS) yields the result.
To prove Lemma 4.1 we will need 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-wiss wise Gradient Domination Property in MPGs). Let G be an MPG with potential function T fix any agent i E N. and let π = (T,, - E ((A) be a policy. Let no be an optimal policy for agent in the single agent MDP in which the rest of the agents are fixed choose T-i- Then, for the policy x¹ = (T] - E A that differs from π only in the policy component of agent i, and for any distributions Je, P E (S)), it holds that
1
dz
pp(=T))- (T) 5
( (H(T)
max
7
1
x' x ))
Proof of Lemma D33
Fix an agent i E N and let ग = (TT T-1), T-" = (T) E I== A(A)
By the definition of MPGs (cf. Definition D it holds that
V2 ( = ( (T))
Thus, using the multi-agent version of the Performance Difference Lemma (cf. Lemma D.2 we have for any distribution j E ASS) that
& (T() - (T) = (T²) - (T)
1
1 7 E Bendy' (alomt(-1a)) Ba-ixt ((l))) [A, (IT, ai,, a
(11b) ((1b) (A ai الادة 2i:l) }.
< 1
Σ de (8) BasrT(((1))) La Ba SSS
max
1 7 EITT
1
Σ (8) (s))
C E Eay E. Ea [A] (T,, as 2للي }.
max
1 7 RlEll
1 di
(5))s) Eajw Ea [Ab(T, as aill
max MEll
di
NES
To proceed, observe that
E Eassne()l)) Ea (omm((-ls) [A, ai, a.))= =0.
Thus, for any प. E II, and any state S, it holds that
Bag-)((1))) Ea-,zt,((11) [A] (IT, a, a.)]
Σ (a/(a; (s) 1s)-map [s)- | s)) En Ea (11)) [AL ar a.)
a.E.
Σ ( (s) - ( 8)) E. Ba (11)) [Q, a; a])]
=
o,E.
21

---

Published as a conference paper at ICLR 2022
since (T) does not depend as. Substituting back in the last inequality of the previous calculations, we obtain that
pp(TT
(T)
S
d
d (s)
(as () - me(a; 8)) Ea ((1))) [Qt(t }
Σ 9,0;
max f/Ell,
d
max (T) m;) V (T)),,
dp
=(Ell,
where we used the policy gradient theorem (Agarwal al. (2020); Sutton & Barto (2018) under the assumption of direct policy parameterizatton. We can further upper bound the last expression by using that (s) visitation distribution (s) for any initial state distribution μ.. Finally, property P2 of Proposition
} 2 (1 - 7))((s) which follows immediately from the definition of the discounted
B.1 implies that v. (T) = Ve (T( (making crucial use of the MPG structure). Putting these logether, we have that
1
pp(TT) 2 (T( 5
p
max
[V-])(VVp (T' (T'- - V. (T(T)
1 ?
/
(xt 1
1
dx
max
(л' - xV) T (T),
V
1 7
11
( =
as claimed.
Remark 3. Intuitively, Lemma D.3 implies that there is best response structure in the agents' updates (projected) policy gradient to a Nash policy profile. In
that we can exploit to show convergence particular, given a fixed policy profile of all agents other than i, the decision of agent is equivalent to the decision of that agent in a single MDP. Thus, the following inequality
(²( Vi
(T' (T)
max
(which stems directly from the gradient domination property the single MDP) implies that any stationary point of V (w.r.t the variables Fi,s,a of agent's policy with the rest of the variables being fixed) is an optimal policy for i.e., best response given the policies of other agents.
Lemma D.3 also suggests that there is an important difference in the gradient domination property between anulti-agent) MPGs and single agent MDPs. Specifically, for MPGs, the value of each agent at different Nash policies may not be unique 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 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 == max4N [Ai], i.c., the maximum number of actions for some agent, which scales linearly in the number of agents.
Lemma D.4 (Smoothness of Φ). Let Amax := maX [As] (the maximum nunber of actions for some agent). Then, for any initial state E S (and hence for every distribution μt E A(S) states), C (T) is 2n smooth, i.e, it holds that
(1-7)
2nyAmax
I D2 (TT) V. (2 22)
||
n'1l2
(13)
(1 73
Proof of Lemma D.4 It suffices to show that the maximum eigenvalue in absolute value of the Hessian of d is at most Amaz i.c., that
2n7Amax (1 (1-7)3
I
This is in contrast to single-agent MDPs for which the agent has unique optimal value even though their optimal policy may necessarily be unique.
22

---

Published as a conference paper at ICLR 2022
We first prove the following intermediate claim.
Claim D.5. Consider the symmetric block matrix C' with n x n matrices so that [[Cxg]2 S L. Then, it holds that ||C||2 I nL, i.e., if all block submatrices have spectral norm most L. then C has spectral norm at most nL.
Proof. We will prove the claim by induction on n. For we need to show that
||C||2 := 1|(
Cn C21
C12
- 2L
C22
I 1Ci2ll2, ||221l22 || 222 S L. Define matrix W to be
= 2L T C- 2L.1- 1-11-G Cn C21
-C12 2L 2L.1- Oz
where I is the identity matrix (of appropriate size). If we show that W is positive semi-definite, then follows that W has only non-negative eigenvalues, which, turn, implies that the spectral norm of C. is at most 2L. To this, set
W1: = (
L (L.1.Cu L-I- ) W2 = L. CC12 L. )
0
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 long I is positive semi-definite and L. L C12C21 is positive semidefinite. By assumption, we have that
1
I 11122211122 - |Cizll 1C12ll2 s I.
which implies that L-I - C12C21 has non-negative eigenvalues. Thus, W2 is positive cemi-definite. We conclude that W, W 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 2 2. To establish that also holds for k, we need to show that
Cn
C12
C21
Oz
Cz
||0||
S KL
Ck1
Cka
Ckk
as long as ||Cipl12 S L for all i,j. Let W consider
kL 1
C. To show that W is positive semi-definite
kL 1 Cn
-C12
C13
-Cik
- C21
L
W1 =
W2 = W W1.
CRI
L
By induction, it follows that W2 is positive semi-definite. We need to show that the same holds for Wi. By Schur complement we obtain that W, is positive semi-definite if and only KL Ci
=E= Ci,Cai is positive semi-definite. follows that
- |
1.-,-Cc... < ||Cu1ll + - Σ [Caela < L + (k 1)L = KL.
1
Hence W, is positive semi-definite and the induction is complete.
Returning to the statement of Lemma D.4 we will show that
n m. V2l 5 C,
(14)
23

---

Published as a conference paper at ICLR 2022
for all i.j E N with C' chosen to be 2rAmua
(1-7)8- Assuming we have shown 14). conclude from Claim D.5 that /2 I nC, and hence & will be nC-smooth (the proof of Lemma D.4 will follow).
To prove 14h, 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
V V w
MyR: =
along the direction where only agent i is allowed to change policy.
Fix policy π = (TI.... n agents i # j. scalars t, 2 0, state so and u, be unit vectors such that T. + u ((A)) and Ty + s v A(A,).. Moreover, let (tt Vi (Ts + u, T-1). and W(t,s) = Vig (T, + u, T + -8800 v, n --,,))) It suffices to show that
( 2t2
2 Ail and max S
d0, dtds
27 27v A S
max || 1
21
|||||==1
(1 7)
(15)
We first focus on (t).. It holds that
v(t) = Σ
Σ
(It + tu)
Il
15,00,, Qi ((T) + tu, - (a. a))
aEA: AEA
jfi
(note that EGEs, EaEA, (Ii,sp.a tui,,,,a) [1 F3,,0,a taking the second derivative we have
since it is a distribution), hence
dV((0)
&Q', so (T, (a, a))
Σ
Σ
(Ni,og.n + (Ui
II 13,00,0
dia
d12
BEA: aEA_!
(16)
dQ's 8p (T,, ta,(a,)) a))
+2 Σ
Σ
Ui,so,a
dl
aEA:; A
jfi
For the remaining of the first part of the proof, we shall show
dQ's 40 (T, a))
TA and d d&Q (T,, (a, a))
< 27?|
dt
(1- 7)2
dt2
(1 7)33
and then combining with 16 we get
de (O)
27 27vlA (1 7)2
27 1r (1 21
27|A:
2/ Ay 27Amax
Σ aEA.
/ui,soval +
5
+
di2
(1 7)2
(1 - 7)3 (1-
To bound the derivative of the Q-function, observe that Q% ((T. + T-), (a, a)) = TT (1 )P(())-rr, where r(so, a) is the expected reward of agent (w.r.t the randomness of the remaining agents) if he chooses action a at state 8n and P(() is state-action transition matrix of w.r.t the joint distribution of all agents but i, i.e., T_ and the environment.
It is clear that dlp dP
(linear with respect to due the direct parameterization) and that de 1loo I E.EA, |uc.em.el I V S v Amaax. Using that [|(1 - -P())) S - we get
di
dQ' (I,, a))
= a (I ( dP(()) dt (I- (I- (1 7)2 (1 - -)-
7v TV Amaax
dt
(17)
and also
d2 d2 (TT, (a, a))
e -PP(0)) dP(()) -dP()) (1 P(0)) - dP(())
50
= 27²
dt (1-7 7
d1
dt
2> A
< 2-² Amax
(18)
(1 7)3
(1 7)33
Since is arbitrary, the first part of 11 is proved.
24

---

Published as a conference paper at ICLR 2022
For the second part, focus (t)) which is equal
E Σ
(K t2,, + sUg.sa.))
of A DEA, DEA 1,
(19)
II
so,ay 2%, (TT tu, By + sv, (i, (a,
j'
We consider the derivative of W dW (0,0) dtds
19
and we get
Σ E
ΣΣ
Σ
II Lj'' Q (a,b,a)
U1 2 J.000
acAi BEAd -EA-i,-
dQ (IT, (a. a))
Σ
II 8'
0i,30,a"
dl
ac aEA_..
dQ sn (T,, (b,
(T.
II
EII Ty so.ay
Ty' s0,ay/
dids
BEAy aEA-,
VAAlIA 1-7
The first term of the sum in absolute value at most
(assuming rewards lie in [0, 1].)
Moreover, using 17 the second term of the sum in absolute value is bounded by 3V/Aiyyi (1-7)²
and
the third term by 2v 2V/Al/AA To bound the @', (T. the same approach works that used to prove (18) with the extra fact that the state-action transition matrix is P(t, s) and moreover, the reward ((su a, b) is the expected reward of agent (w.r. the randomness of all agents but i, if i
(I-7)²
dids
chooses action a and j chooses b at state 8o- Finally, for the fourth term we get that
d² d'Q',, ( (T, a)
dtds
00.0 (1 (1-P((,,))-- dP((0.)
(1 - (l=7P()) dP(0,, 0)
$ 72
(1 -((,)())
ds
dt
e 2 (1 - 7P(0, dP((,,) 0)
(I 7P(0, 0)) dP(0, -I- (I-7P(0,0)~'' dt
+ 2
ds
+ ? a (I - 70---P(000 P((,0)) PPO,0
(1 -((,0))) -r
dta
22 A: Ag
72
I
A 21-
27V A. 1
2 (1 71-
73
7)3
7)
The first step is to show that O is a 8-smooth function, in particular, that V & is 3-Lipschitz with B = 2nyAA as established in Lemma D.4 Then, a standard ascent lemma for
Proof of Theorem 4.2
(1-r)s
Gradient Ascent (see Lemma C.I from Bubeck (2015) implies that for any 9-smooth function f it
holds that f(x') [xx) 2 23
where x' is the next iterate of equation PGA Applied to
our setting, this gives
(1 11-7) 73
b (x((+)) (1)) 2
(1++1)
(1)
(20)
4 A
Thus, if the number of iterates, T, is 16mg 123
(1->)*²² then there must exist S T so that
[[+1) (0 S <(1-7) Using standard approximation property (see Lemma C.2 we then 2DV5'
conclude that (1+11) will be <(1-))
DVS -stationary point for the potential function +. Hence, by
Lemma 4.1 it follows that ((++1) an c-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, ie., V Tb V., V for all N property P2 in Proposition B.I
25

---

Published as a conference paper at ICLR 2022
Proof of Theorem 4.4 Let = - (x())((())) and set (1-7)²
AmayAmax (the inverse of the smooth
parameter in D.4). Moreover, we set yf++1) Pacajs (T(*) + 17 V, ())))) (y((++1) captures the next iterate of the projected (deterministic) gradient ascent). We follow the analysis of Projected Stochastic Gradient Ascent for non-convex amooth-functions (see Davis & Drusvyatskiy (0018).
Theorem 2.1) that makes use of the Moreau envelope. Let
1 A 11 11l--13
xx(x)
arg min
yEA(A))
(definition of Moreau envelope for our objective @). From the definition of & and a standard property of projection we get
ex (x(T(++)) s - (1(())))))
(++1) -
S (cttt
+ ((()) + ~つ -
(21)
(t) y (++ 1| 2
2n (= y((+1))T (())
2
Since - is unbiased (Lemma 4.3 we have that [0] 0. therefore E Ho (y - [0)]
(1) [ S
24n
0. Additionally, by Lemma 4.3 (applied for all agents i) we also have E
c(1
Hence by taking expectation on 21 we have:
Bloa
(T (T(+)) S
$ (u(((tt)) + -
2n (0) - - V (T + + A
nA
S E
Ac(1 7)
Using the definition of Moreau envelope and the fact that & is I-smooth (Lemma parameterization, the smoothness parameter does not increase) we conclude that
D.4 after the
B (1x
27 Bl((T()) < [x)
+ n.. max
T V.
x
de(1 -7)1
2/ E (-(() - (1+))
(0( (c111) 2
24 Aax
+ < <1(pA(T(())
21
2
Ac(1 - 74
or cquivalently
(1 (++1)) -[(o(((7()) z
2n E
$ ( (++1)) + 1 (1) y y1++
27
24
1 (0)
+
(22)
21
Ac(1 - -7
Adding telescopically
(22g. dividing by T and because w.l.o.g - E [-1, 0J. we get that
maxx T Xe(1
1
+
2
21 XI
T
E
(1+(1))
[]]
17
T
E
-
- -(0
7)
X2T
1=1
(23)
min [E(TT]
2m
E 1 (g((t2))
- [,,((((0)] - 2
1 gltt2) -100))100011 10) -
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 1 (2((++))) - (T(((())))))))))))))))
EE
| - x((1)) [
2 1 -|
((()) -
| [
(24)
2A
Observe that by f-smoothness of T we get that (x) + | =((0))122 is -stron convex and moreover, (I++1) is the minimizer of H. Therefore, we get that H(***) H1)++ N
26

---

Published as a conference paper at ICLR 2022
2x 1 - 1 or equivalently
@ (1( (1((T())
|
y +++ 112 2 2x -
ylo+1
2
By taking expectation of terms above,
(4
follows. Combining
23 with 24
we conclude that
1 n. max
2/1
z
|
T
de - 7)
By Jensen's inequality it occurs that
E
1 [
x((x))
S
12
-1
12n max
(25)
2n7T
c(1 7)
To get e-Nash policy, we have to bound || e² in the greedy parameterization. This is true because of Lemma need to choose 17. T so that
x(10)|12
e(1-2)
and choose
2Dv/S2- v Andmas)
C.3 Lemma
4.1 Hence,
X2
12ndA max S
c(1-7)
+ 11
2t/7
22 7)² 2DV Vndmax)
2(1-))² and to be 48(1 Amss 48h A g
We conclude that 17 can be chosen to be
E ADDITIONAL EXPERIMENTS
In this part, we analyze variations of the experimental setting in Section
Coordination beyond MPGs. As mentioned in Remark [ 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 S The setting remains mostly the same, except now in the distancing state the rewards are reduced by a differing (yet still sufficiently large) amount, C₁. for each facility k = A, B, C, D. Despite this asymmetry, agents still have aligned incentives. fact, if the Cg'S 8 for all k A, C,C, D are taken to be greater than e 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,
Cradent agents care gerender
sgents
sgents
Figure 6: Figures similar Figure 3 except with c CA > CB > 60 > cD as described in the text. Independent policy gradient requires more iterations to converge compared to the symmetric shift setting, but still arrives at 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 A; = facilities, A; = {A, B, C, D, E} with w < WB < WC < wD < wE (i.e., E is the most preferable by all agents). We use 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 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
27

---

Published as a conference paper at ICLR 2022
35
Di Dilonoe 1600
150 201
300
402
807
Pusiity
Figure 7: Convergence deterministic Nash policies of independent policy gradient in variation of the MDP of Section 5
with N = 16 agents and A, = 5 facilities, AA, = {A, B, C, D, F} with WA < Wp < Wc wp we (i.e., E is the most preferable by all agents). Again, while there several (symmetric) deterministic Nash policies, all of them yield the same distribution of agents among states (leftmost panel). All runs converge successfully that outcome.
Coordination with random transitions Next, 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 in Section 5 (i.e., N agents and A; 4 facilities that each agent i E A can choose from), but use the Tollowing 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 9% 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 5%. 20%. both cases, we use learning rate 17 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 randomness in the transitions. However, for higher levels of randomness (lower panels), the algorithm remains at an e-Nash policy for a high number iterations. This is in line with the theoretical predictions of Theorem
REMES W.. D..-009001
Pean acurccy
Clllaciigg Aul:
25
20
05
50
00
101
10
101
Tecky
POBO noueer IQATE E, EL MIRERR
PORC/NBONY ADHER #1 RACE S1. *00EE
Tafe 18ts
Diranding
0.5
06
0
Figure 8: Convergence to deterministic Nash policies of independent policy gradient two variations of the MDP of Section 5 with stochastic transitions between states.
Independent Policy Gradient 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), that this MPG framework captures such games. In this environment, there is an underlying directed acyclic graph G that has source node and sink node f. There N agents. The actual states
it is valuable to
28

---

Published as a conference paper at ICLR 2022
of the finite-horizon MDP are all the possible positions of the agents the graph. When the state consisting of all agents being at t reached, the MDP terminates. At each time step, each agent chooses action, which in this case is edge transverse, and the cost they experience is a function of the load the edge, which is the total number of agents choosing edge e. more complete description and proof that this environment an MPG is provided in |Fox al. 202T).
We implemented this environment with N = agents, matching the number of agents in Fox et al. (202I), but we were actually able increase the size of the underlying graph from the vertices done in that paper to 8. The game is visualized in Figure)
Figure The stochastic congestion game with N agents and nodes. In this discrete time MPG, all agents start at and at each point in time, they move to one of the nodes of the next layer. Their goal is to reach f minimum cost (as expressed by the congestion on the the vertices). The left panel shows the starting state and the right panel shows one possible state after two transitions (with intermediate states pale colors).
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, 7 0.99, and ry 0.0001. The results are shown in Figure 10
Policy Gradiant: egents 4 R.na 10, 3.0001
Policy Gradient: agonts = runa 10, 0.0000
16
10
Mean L. H-acoraccy
1-4landard deviation
200
400
800
800
1000
1200
1400
1800
200
420
600
800
1000
1200
$400
1600
Innations
Herwinn
Figure 10: Convergence of independent policy gradient in the stochastic congestion game with N and 6 vertices between source and target (3 layers of vertices each) as shown in Figure
29


Reviews:
[{"review_id": "qDfGl1AhPaW", "reviewer": "Reviewer_43Uo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. The paper did a great job introducing the MPG and showing us intuitions about the game with examples and observations.\n2. The paper proved the convergence to $\\epsilon$-NE and provided the convergence rate for learning agents following independent policy gradient or stochastic gradient in MPG.\n3. The paper additionally provides the empirical results to verify the convergence.  \n4. The paper describes several meaningful open questions and future directions that I find quite valuable.\n\nWeakness:\n\n1. I wish to see more MPG instances (e.g., with potential function of different smoothness or convexity) in the empirical evaluation and wonder how the performance of multiagent learning differs in different games. I think it is also possible to include classical RL algorithms and see how they perform compared to policy gradients.\n2. The paper could have a much more profound technical contribution if it could touch upon any of the open questions mentioned in the end.\n\nQuestions:\n\n1. Is it possible to generalize the theorem such that the algorithm does not need to know the number of iteration beforehand, in analogy to the doubling trick in bandit literature?\n2. Is it possible to generalize the game setting to infinity state setting using the techniques from literature [1] of linear Markov decision process? It seems to me the MPG definition can be further generalized in this way.\n\n[1] Jin, Chi, et al. \"Provably efficient reinforcement learning with linear function approximation.\" Conference on Learning Theory. PMLR, 2020.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is overall well-written and established the preliminary studies of MPG problem and multi-agent learning algorithm for convergences, though there are still many unsolved questions in MPG such as Price of Anarchy. Therefore, I recommend a weak-accept of this paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lzVKBF_F0VE", "reviewer": "Reviewer_awwm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The definition of Markov potential games is known to be more delicate than that in the matrix (stateless) case. The authors have done a good job defining and giving (counter)-examples, in order to demonstrate this subtlety, mainly stemming from the introduction of the transition dynamics. This part, to my knowledge, has not been discussed in the literature before.\n2. Both global convergence (for both the model-based and model-free setting) and sample complexity results (for the model-free setting) have been established, for finding the Nash equilibrium of the Markov potential game.\n\n\nWeakness:\n1. The global convergence, especially the exact case, is more-or-less expected, given Agarwal et al., 2020. In particular, given the opponent's policy being fixed, first-order stationarity => best-response, can be derived directly from that reference, which further leads to the definition of Nash equilibrium in the game setting. Hence, the novelty of this part, regarding optimization landscape and global convergence, is relatively limited. \n2. It is claimed in the abstract that the convergence is \"polynomially fast\". I am not very sure about the accuracy and commonality of the wording. In fact, the $1/{\\sqrt T}$ rate is not a fast one, but a standard one adapted from general nonconvex optimization.\n3. Can the results in Theorem 4.4 be improved by choosing different parameters, e.g., alpha, eta, and T. It seems that $\\epsilon^{-6}$ is not the standard rate in nonconvex stochastic optimization. \n4. Some typos have been spotted, and some arguments are not accurate/professional: \n1) Around Eq. (2), how the horizon length H is sampled (in fact, for unbiasdness, it should be sampled from a geometric distribution), is missed. Note that the setting in Daskalakis et al. (2020) is a finite-horizon one with random T (not an infinite horizon discounted one). So I am not sure if Lemma C.4's proof in this paper follows by just citing the results there directly. In fact, for infinite horizon discounted setting, the unbiasedness and bounded variance property of this estimator has been established before Daskalakis et al. (2020), see e.g., https://arxiv.org/pdf/1906.08383.pdf; https://arxiv.org/pdf/1807.11274.pdf. \n2) The constants in the main theorems (and their dependences on the problem parameters) may need double-check.\n5. How do the results compare with the very related recent work of https://arxiv.org/pdf/2106.00198.pdf? It might be worth discussing the differences between the two (thought I suppose it might be possible that the two works are concurrent). \n", "summary_of_the_paper": "This paper carefully studies the definition of Markov potential games, and establishes the similarities and differences from the stateless case. It also shows the global convergence of independent policy gradient methods for Markov potential games, to the Nash policies. ", "summary_of_the_review": "In general, the paper is well-written, and I enjoy reading it. It has made valid contribution on multi-agent RL in potential games. With the minor comments above being addressed, I believe it can be a good paper deserving publication. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h_1oqYVL6A1", "reviewer": "Reviewer_5gGX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is well written. The theoretical analysis of this paper is presented clearly and seems to be rigorous. \n\nMy main concern is whether the so-defined MPGs are of enough interest. Specifically, in Prop $3.2$  (C1),  for an MDP to be an MPG, the state transition cannot be affected by the action, which is unrealistic in MARL setting. Second, in (C2), it remains unclear how to check whether the immediate rewards can be decomposed into the desired form with individual dummy terms. The authors only present a trivial example where $u_s^i$ is some constant $c^i$. Third, for cases of non-trivial state transition, the authors only provide a 2-agent MDP example in Figure 3. As a result, I think the practical applications of this paper are restricted.", "summary_of_the_paper": "This paper studies Markov potential games (MPGs) that genralizes the classical normal form potential games. They show that each agent playing individual policy gradient guarantees the convergence to Nash policies with polynomially decaying error rate. \t", "summary_of_the_review": "Although the theoretical analysis of this paper is well-organized and seems to be rigorous, the so-defined MPGs seem unrealistic in the MARL setting and are restrictive in practical applications. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GQVECbU4Fys", "reviewer": "Reviewer_idii", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: This paper considers an important research topic --- policy gradient in markov potential games (MPG) and provides interesting new insights on this topic. The existence of deterministic Nash policies in MPG is somewhat not surprising though, I find the examples 1 and 2, which shows the potentiality at every state may not lead to MPG, illuminating. The methodology for analyzing the convergence property of the projected (stochastic) policy gradient seems to be adapted from some previous works. However, in general, the presented convergence results in MPG are novel.\n\nWeakness: Some related works have not been discussed in the paper. For example, the paper \"Stochastic Potential Games\" (https://arxiv.org/pdf/2005.13527v1.pdf) also considers potential games with multiple states. I wonder how Theorem 3.1 of this paper is different from Theorem 1 of \"Stochastic Potential Games.\" The paper is generally well-written, but some parts remain unclear:\n1. For Condition C2 of Proposition 3.2,  the authors state that \"the dummy terms of each agent's immediate rewards are equal across all states.\" Intuitively, this seems to suggest that $u_s^i(\\vec{a}_{-i})$ equals some constant for all states, which is not in line with the condition formalized right after the statement. So how to interpret the formalism of C2? I think a more clear and precise interpretation is needed. \n2. The example provided in Figure 3 assumes that $p_0$ does not depend on agents' actions. Suppose there is a 2-player MDP which is not potential at every state and $p_0$ depends on agents' actions, is it possible that this 2-player MDP is an MPG?\n3. Section 4 is rather dense and not easy to follow. In the meantime, Section 5 does not provide much new knowledge about congestion games. The authors may consider moving some parts of Section 5 to the Appendix and providing more explanations (such as the definitions and prior results required to derive Theorem 4.2) in Section 4. \n", "summary_of_the_paper": "This paper examines the projected policy gradient method in markov potential games (MPG). The paper i) proves the existence of deterministic Nash policies in MPG, ii) analyzes the sufficient conditions for MPG, and iii) proves the convergece of projected (stochastic) gradient ascent to Nash policies in MPG.", "summary_of_the_review": "This paper provides interesting, new, and important theoretical results for policy gradient in markov potential games.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers an important problem, Multi-Agent Reinforcement Learning, and looks at a subclass of problem, the Markov Potential Game.

Even though this class is not the more generic one (as pointed out by a reviewer), one must start somewhere before (and maybe the results cannot easily or at all be extended to a larger class), so I will not personally take this as a strong negative concern.

The other reviewers are rather positive about the result and the techniques, and I concur with them. 

I will therefore recommend acceptance.
Decision: Accept (Poster)