Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
Authors: Stefanos Leonardos
Will Overman
Ioannis Panageas
Georgios Piliouras
Venue: NeurIPS 2021 Submitted (2021)
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 as all agent utilities are perfectly aligned with each other 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? We present a novel definition of Markov Potential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs can consist of 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 fast convergence of independent policy gradient to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs to multi-agent learning settings. 

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
Anonymous Author(s)
Affiliation
Address email
Abstract
Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting multi-agent coordina- tion as all agent utilities are perfectly aligned with each other via a common poten- tial function. Can this intuitive framework be transplanted the setting of Markov Games? What are the similarities and differences between multi-agent coordination with and without state dependence? We present novel definition of Markov Po- tential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form poten- tial games do not carry over as MPGs can consist of settings where Maae-games can be zero-sum games. In the opposite direction, Markov games where every state gane is potential game not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, prove fast convergence of independent policy gradient to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs multi-agent learning settings.
2
6
10
12
14
15
Introduction
17 Reinforcement learning (RL) has been a fundamental driver of numerous recent advances in Artificial Intelligence (AI) applications that range from super-human performance competitive game-playing and strategic decision-making in multiple tasks 21 23 33 to robotics, autonomous- driving and cyber-physical systems 6 37. A core ingredient for the success of single-agent RL systems, which are typically modelled as Markov Decision Processes (MDPs), is the guarantee of existence of stationary deterministic optimal policies 3 30). This allows for the design of efficient algorithms that provably converge towards the optimal policy []. However, majority of the above systems involve multi-agent interactions and despite the notable empirical advancements, there is a lack of understanding about the theoretical convergence guarantees of the existing multi-agent reinforcement learning (MARL) algorithms.
18
19
28 (29
20
21
22
23
24
25
26
The main challenge in the transition from single to multi-agent RL settings is the computation of 28 Nash policies. A Nash policy for
27
agents defined be a profile of policies (mi -x so 29 that by fixing the stationary policies of all agents but i, nu is an optimal policy for the resulting single-agent MDP and this is true for all S sis < n (see Definition 1b. Note that in multi-agent
30
31
settings, Nash policies may not be unique in principle.
32 common approach for computing Nash policies in MDPs the use of policy gradient methods. The significant progress in the analysis of such methods during the last couple of years, including (and references therein), mainly concerns the single-agent case: the convergence properties of
34
Analogue of Nash equilibrium notion.
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

35
policy gradient in MARL remain poorly understood. Existing steps towards a theory for multi-agent settings involve the papers of [T] who show convergence of independent policy gradient to the optimal policy, for two-agent zero-sum stochastic games, of [36] who improve the result of [10] using optimistic policy gradient and of [X who study extensions of Natural Policy Gradient using function approximation. It is worth noting that the positive results of [O, [6] and (38 depend on the fact that
36
37
38
39
40
two-agent stochastic zero-sum games satisfy the "min-max equals max max-minn min" property [27] (even
41
though the value-function landscape may not be convex-concave, which implies that Von Neumann's celebrated minimax theorem may not be applicable).
42
Model and Informal Statement of Results. While the previous works make progress in competi- tive interactions, i.c., interactions in which gains can only come at the expense of others, MARL in cooperative settings remains largely under-explored and constitutes one of the current frontiers in AI research 9 g Based on this, our work is motivated by the following natural question:
44
45
46
47
Can we get (provably) fast convergence guarantees for multi-agent RL settings in which cooperation is desirable?
48
49
To address this question, we define and study a class of n-agent MDPs that naturally generalize normal form potential games (22). called Markov Potential Games (MPGs). In words, a multi-agent MDP is MPG as long as there exists a (state-dependent) real-valued potential function o so that if an
50
51
52
agent& 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 4 (see Definition 2}. Weighted and ordinal MPGs are defined similar to the normal form counterparts (see Remark
59
54
55
Under our definition, we answer the above motivating question in the affirmative. In particular, we show that if every agent i independently runs (with simultaneous updates) policy gradient on his utility/value V', after (1)/e²) iterations, the system will reach an e-approximate Nash policy (see informal Theorem 1.1 and formal Theorem 4.2). Moreover, we show the finite sample analogue, that is if every agent independently runs (with simultaneous updates) stochastic policy gradient, then with high probability, the system will reach an e-approximate Nash policy after (L)e²) iterations.
57
58
59
80
61
Along the way, we prove several properties about the structure of MPGs and their Nash policies (see Theorem 1.2 and Section 3). Our results can be summarized in the following two Theorems.
Theorem 1.1 (Convergence of Policy Gradient (Informal)). Consider a MPG with agents and let 64 E > O. (a) If each agent runs independent policy gradient using direct parameterization on his policy and that the updates are simultaneous, then, the learning dynamics reach e-Nash policy after (1))2) iterations. (b) If each agent runs stochastic policy gradient using greedy parameterization
63
66
(see 3 on his policy and the updates simultaneous, then the learning dynamics reach an c-Nash policy after (ll/e) iterations.
68
69
This result holds trivially for weighted MPGs and asymptotically also for ordinal MPGs, see Remark
70
Theorem 1.2 (Structural Properties of MPGs). The following facts are true for MPGs with n-agents:
71
(a) There always exists a Nash policy profile (Ti..... xhi) so that n. is deterministic for each
72
agent i (see Theorem 3.7y.
73
(b) We can construct MDPs which each state is an underlying potential game but the MDPs not MPGs. This can be true regardless of whether the whole MDP is competitive cooperative in nature (see Examples TameesTannd Tand 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 Example 3 (c) We provide sufficient conditions so that a MDP is a MPG. These include cases where each state is an underlying potential game and the transition probabilities not affected by agents actions or
74
75
76
77
78
79 the reward functions satisfy certain regularity conditions between different states (see conditions Cl
80
and C2 in Proposition 3.2
81
Technical Overview. The first challenge in the proof of Theorem I.1 is that multi-agent settings (MPGs) do not satisfy the gradient dominance property, which is an important part in the proof of convergence of policy gradient in single-agent settings [I] In particular, there is no uniqueness of optimal policies and as a result, there is not a properly defined notion of value in MPGs (in contrast to zero-sum stochastic games (10). On the positive side, we show that agent-wise (i.e., after fixing the
82
83
84
86 policy of all agents but i), the value function, V satisfies the gradient dominance property along the direction of π. (policy of agent i). This can be leveraged to show that every (approximate) stationary

---

88
point (Definition 4) of the potential function d is an (approximate) Nash policy (Lemma 4.1 As result, convergence to an approximate Nash policy is established by showing that & is smooth and then applying Projected Grudient Ascent (PGA) on t. 'hiis step uses the rather well-known fact that (PGA) converges to e-stationary points in O(1/²)) iterations for smooth functions. As a result, by applying PGA on the potential Φ one gets an approximate Nash policy. Our convergence result then follows by showing that PGA on the potential function, 2, generates the same dynamics as if each agent i runs independent PGA on their value function, V*.
89
90
91
92
93
94
95
In the case that agents do not have access to exact gradients, we derive a similar result for finite samples. In this case, we apply Projected Stochastic Gradient Ascent (PSGA) on & which (as was the case for PGA) can be shown to be the same as when agents apply PSGA independently on their individual value functions. 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 comes from the discount factor, 7, in this case, 1 7 can be interpreted as the probability to terminate the MDP at a particular state (and y to continue). This can be used to show that a trajectory of the MDP is an unbiased sample for the gradient of the value functions. To guarantee that the estimate has bounded variance, we apply the approach of [10] which requires that agents perform PSGA with a-greedy exploration (see (3)) The main idea is that this parameterization stays away from the boundary of the simplex throughout its trajectory.
96
97
98
39
100
101
102
103
105
106
Concerning our structural results in Theorem 1.2 the main challenge is (again) the lack of a value in general multi-agen settings and the dependence of transitions (in addition to agents' rewards) on agents' actions. The proof of Theorem [31 shows that these issues can be still successfully handled within the class of MPGs by studying single-agent deviations (to deterministic optimal policies)
107
108
109
110
which keep the value of the potential constant (at its global maximum). Our examples in this part
111
show that the class of MPGs can be significantly larger than state based potential games but also that
112
even simple coordination games may fail to satisfy the (exact) MPG property.
2
Preliminaries
113
114
Markoy Decision Process (MDP). The following notation is standard and largely follows 0 and
115
10 We consider a setting with n agents who repeatedly select actions in shared Markov Decision Process (MDP). The goal of each agent is to maximize their respective value function. Formally, a
116
117
MDP is defined as a tuple G = (S,
R. P. y, p). where S is a finite state space of size S = S = {1, .,,,,...uu n is a the set of active agents in the MDP and Ae is a finite action space of
118
119
size A, = | for each agent E A with generic element a; E A,. We will write A = II
120
and A_; = II, A, to denote the joint action spaces of all agents and of all agents other than with generic elements a = (a:)iEN and a (a,))zi. respectively. R; : S x A- [-1, 1] the individual reward function of agent i E N, i.e., R,(s, di, a-:) is the instantaneous reward of agent i when agent takes action a; and all other agents take actions a-; at state E S. P the transition probability function, for which P(s' s,a) is the probability of transitioning from to s' when is the action profile chosen by the agents. Finally, 7 is a discount factor for future rewards of the MDP, shared by all agents and p E A(S) is distribution for the initial state at time t = o
121
122
123
124
125
a E is
127
Whenever time relevant, we will index the above terms with t. In particular, at each time step
128
t 2 0, all agents observe the state st E S, select actions a = (d.,,,-i..) receive rewards N and transition to the next state St+1 P(- s,,a,). We will write T (st. ag, 12) to denote the trajectories of the system, where r, := (r..).i...
129
Tse = (,,,,,
130
131
Policies and Value Functions. For each agent i E N, a deterministic, stationary policy n; S ->> A specifies the action of agent i at each state E S, i.e. (T(s) a; E A, for each 8 E S. A stochastic, stationary policy म, : S + II, where II; == ((A;),, specifies a probability distribution
132
135
over the actions of agent i for each state E S. In this case, we will write a; TT(- () to denote the randomized action of agent at state 8 E S. As above, we will write म = (T.) E := A(A)s S and π_; (Ty){TJEN II := (A)) to denote the joint policies of all agents and of all agents other than i, respectively, A joint policy л induces a distribution Pr" over trajectories 7 (st, a,, 12) where so is drawn from the initial state distribution P and ag is drawn from (. 8t) for all i E.
135
136
137
139
We will write A(X') denote the set of probability distributions over any set X.
3

---

140
The value function, V : II - R, gives the expected reward of agent E -V when So = s and the agents draw their actions, a, (ai,r, a.),),, at time - 0 from policies (TT mT-))
141
(T) = E Σ t=
r'rc s0
(1)
We also denote (T) = Eanp [T)) if the initial state is random and follows distribution p. The solution concept that we will be focusing on are the Nash Policies. Formally:
142
143
144
Definition (e-Nash Policy). joint policy π (TT) ).N is an e-Nash policy if there exists an e 2 so that for each agent i E .,, (T =" 2 (i -=1)= for all म; (AA)), and all S. Ife = O, then n" is called a Nash policy. In this case, Th maximizes each agent i's value function for each starting state S given the policies, =_; (T] ji of all other agents j A N. The
148
147
148
definition of a Nash policy remains the same if 8 ~ (random starting state).
3
Markov Potential Games
149
We now ready to define the class of MDPs that we will focus for the rest of the paper, i.e., Markov Potential Games.
151
152
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 for E S that
4 (T --1) (T --1 V (T,, T-1) V (T -)).
154 for all agents i E E,, all states E S and all policies n., T/ E [1 --; E II We should note that by linearity of expectation, it follows that ( - $ (p( m-) (TT,, (m m-1), where o (T) == Eg-p (T)
156
157 As in normal-form games, an immediate consequence of this definition is that the value function of each agent in MPG can be written sum of the potential (common term) and term that does depend on that agent's policy (dummy term), cf. Proposition B. in Appendix
158
159
B i.e., for each agent i / there exists function U II + so that (T( P. (T) U (T-(T))). for all II.
180
161
Remark (Ordinal and Weighted Potential Games). Similar to normal-form games, we may also define more general notions of MPGs, such as weighted or ordinal MPGs. Specifically, if there exist positive constants w; > 0, E N so that
163
(T m) 4, (T) w/ (V T - V (T
then G is called Weighted Markov Potential Game (WMPG). If for all agents i E all states E S 164
165
and policies ,,; n/ E 11 -- E IT the function 2,, 8 E satisfies
D (T - 4 ( (T), = (I(T, Vi m-)) 0,
186
then the MPD, G, is called an Ordinal Markov Potential Game (OMPG).
187
Similarly to normal-fome games, such classes are naturally motivated also 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 be exact MPGs (but may still be ordinal or weighted MPGs). From
188
169
170
our current perspective, ordinal and weighted MPGs remain relevant, since our main convergence results on the convergence of policy gradient carry over (in an exact or asymptotic sense) also in these classes of games (see Remark[) As with the rest of the proofs (and technical details) of Section 3 the proof of Theorem 3. provided in Appendix
171
173
174
Existence of Deterministic Nash Policies in MPGs. Before studying which types of MDPs are captured by Definition [ we first show that MPGs always possess deterministic Nash policies (similarly to their single-state counterparts, i.e., normal-form potential games (22). This established
175
176
in Theorem 3.1 which settles part (a) of Theorem 1.2
Theorem 3.1 (Deterministic Optimal Policy Profile). Let G be Markov Potential Game (MPG). Then, there exists a Nash policy n² E A(A)s which deterministic, i.e., for each agent E N and each state s S, there exists action ag E A; so that Tī (a: 8) 1.
179

---

① a
(ag. ag) = (0,0)
otherwise
80
S1
80
otherwise
81
otherwise
1
(0,0)
2.0
2,0
0.2 0,2 0.2
0.2
0.2
5. 2
-1
2.0
2,0
3.
-1 1.
Figure 1: A MDP with normal-from potential games at each state (shown in matrix form be- low each state) but which is not a MPG due to conflicting preferences over states.
Figure 2: A MDP with normal-form potential games at each state which is an ordinal MPG but not a MPG despite common preferences over states.
181
Starting from an arbitrary Nash policy profile that is also global maximizer of the potential function, the proof of Theorem 3.1 (which is deferred to Appendix B relies on an iterative reduction process of its non-deterministie components, At each iteration, we isolate an agent i E N, and find 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 global maximizer of the potential and hence, a Nash policy profile. This argument critically relies on the MPG structure and does not seem directly generalizable to MDPs that not satisfy Definition
182
183
184
185
186
187
188
Sufficient Conditions for MPGs. Based on the above, it is tempting to think that MDPs which potential at every state (meaning that the immediate rewards at every state captured by (normal-form) potential game at that state) are trivially MPGs. As we show in Examples [ndd]] this intuition fails in the most straightforward way: we can construct simple MDPs that are potential at every state but which are purely competitive (do not possess a deterministic Nash policy) overall (Example T or which are cooperative in nature overall but which do not possess an exact potential function (Example 2
190
191
192
193
194
195
Example 1. Consider the MDP in Figure ] To show that G is not MPG, it suffices show that
196 it cannot have deterministic optimal policy as should be the case according to Theorem [3.] To obtain contradiction, assume that agent A is using deterministic action a% {0, state O. Then, agent B, who prefers to move to state 1, will optimize their utility by choosing the action 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
197
198
ag {0, 1} that yields d @ ag
199
200
201
an action cannot be optimal for agent A which implies that the MDP does not have deterministic optimal policy profile claimed.
202
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) despite the fact that the immediate rewards at each state are determined by normal form potential games. Example 2 shows that a state-based potential game may fail to be a MPG even if agents have similar preferences
204
206
states.
208
Example 2. In so the agents play a Battle of the Sexes game and hence a potential game, while in $1 they receive reward (which is trivially potential game). A simple calculation shows that there is not an exact potential function due to the dependence of the transitions on agents' actions (thus, this MDP is not MPG). However, in the case of Example 2 it is straightforward show that the game is an ordinal potential game, cf. Appendix B.1
210
212
213
The previous discussion focuses on games that consist of normal-form potential games at every state, which leaves an important question unanswered: are there games which are not potential at every state but which are captured by the current definition of MPGs? Example 3 (see Figure 3) answers this question affirmatively. Together with Ex this settles the claim in Theorem 1.2, part (b). Proposition 3.2 (Sufficient Conditions for MPGs), Consider a MDP G in which every state E S a potential game, i.e.. the immediate rewards R(s, a) (s, a)) for each state E S are captured by the utilities of a potential game with potential function &g. Additionally, assume that one of the following conditions holds
214
215
216
217
218
219
220
Cl. Agent- Agent-Indepenn Independent Transitions: P(s') 8, a) does not depend on a, that is, P(8' 8, = P(s) 8) is just a function of the present state for all states s' E S.
221
5

---

(+-+) (++4)
(-+4)
(8.0))
(6.6))
Figure 3: A 2-player MDP which is not potential at every state but which is overall an MPG. While state 81 corresponds to zero-sum game, the states inside the dotted rectangle do form potential game which can be used to show the MPG property whenever po does not depend on agents' actions.
C2. Equality of Individual Dummy Terms: P(s' a, is arbitrary but the dummy terms of 223
224
each agent's 's immediate rewards are equal across all states, i.e., there exists function u' ((A.)) + R. such that Rs(s, a, a (T,, + (T(T))), for all states E S.
225
226
If either C1 or C2 are true, then G is a MPG.
227
Relation to Other Works on MPGs Condition C2 (or variations of it) is also known as state- transitivity and is present as requirement in the existing definitions of potential-like MDPs, e.g..
229
19 20] and along with some additional conditions on the transitions also in [3). Example 3 restrictive, in the sense that they do not capture simple MDPs that intuitively have a cooperative structure. Similarly, Example [ motivates the study of weighted or
16.
shows that such conditions
231
ordinal MPGs (ef. Remark []. As we show, our convergence results about independent policy gradient naturally apply to these classes as well (see Remark 2
233
Another sufficient condition for a MPD that is potential at every state to be a MPG is that the instantaneous rewards of all agents are the same at each state, i.c., that [s a, a..) = Φ o,(a,, a.:) for all agents i NN, all actions a, A, and all states E S. MDPs that satisfy this condition called Team Markov Games and their analysis trivially boils down to single agent settings. However, they constitute the only (to the best of our knowledge) cooperative multi-agent setting (covered by MPGs) that have been successfully addressed in terms of convergence of independent policy gradient
235
237
239
prior to this work, (35]
241
4
Convergence of Policy Gradient in Markov Potential Games
242
The current section presents the main lemmas and steps for the proof of convergence of (projected) policy gradient (and its stochastic variant) to approximate Nash policies in Markov Potential Games (MPGs). We analyze these cases using direct and a-greedy parameterization, respectively. All proofs and auxiliary materials are deferred to the supplementary material (full version).
244
245
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. Independence here refers to the fact that (PGA) requires only local information (each agent's 's own rewards, actions and view of the environment) to determine the updates. Such protocols naturally motivated in distributed Al settings in which all information about the interacting agents. the type of interaction and the agent's ' actions (policies) is encoded in the environment of each agent The PGA algorithm is given by
247
249
251
252
(1+1) = -PALA)S (T("+ + V Vi Vi(T
(PGA)
for each agent E NV, where PA (AA)s the projection onto ((A,) in the Euclidean norm. Here, the additional argument / > 0 denotes time. We also assume that all players i E W use direct policy parameterizations, i.e., Ta(a 8) Lt,s,a: with Fi,e,0 2 for all s S,a E A, and Σ DEAA Ti,s,a = 1 for all s S. This parameterization is complete in the sense that any stochastic policy can be represented in this class (.]
253
255
257
'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 can be obtained.

---

258 In practice agents use projected stochastic gradient ascent (PSGA), according to which, the actual gradient, n. ()) is replaced by an estimate thereof that is calculated from a randomly selected
259
(yet finite) sample of trajectories of the MDP. This estimate, v may be derived from single or a batch of observations which in expectation behave as the actual gradient. We choose the estimate of the gradient of Vi to be
260
262
V R (T.))
(9) v log (1 ( (0)).
where si P. and R(T = E
k=o 7, is the sum of rewards of agent for batch of time horizon T along the trajectory generated by the stochastic gradient ascent algorithm at its f-th iterate.
264
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 N uses instead direct parameterization with a-greedy exploration as follows
266
T. s) = (1 - a,) + a/Ac,
(3)
where is the exploration parameter for all agents. Under greedy exploration, it can be shown that
2 is unbiased and has bounded variance for a-greedy exploration (see Lemma 4.3) The form of
269
PS GA is given below:
(++1) = PA(A) T
(T. 10 + V
(PSGA)
271
Proofs of main results. The first step to observe that, in MPGs, the (partial) derivatives of the value functions and the potential function are equal, i.e., Va, (T(()) Va, (TT) for all i E /N' (property P2 in Proposition [.I). Together with the separability of the projection operator, i.e., the fact that projecting independently for each agent on ((A.) is the same as jointly projecting ((A)
273
275
(see Lemma 4.1). this establishes that running (PGA) or (PSGA) on each agent's value function is equivalent to rumning (PGA) (PSGA) on the potential function 4b
Based on the above, the next step to study the stationary points of b. Lemma 4.1 suggests that 277
as long as policy gradient reaches point (19) with small gradient along the directions in A(A)s, must be the case that x(1) is approximate Nash policy.
278
279
Lemma 4.1 (Stationarity of & implies Nash). Let 2 0, be an e-stationary point of & (see Then, holds that π a vSDc VSDe.Nash policy.
281
Definition
1-7
282
Lemma 4.1 will be the one of two mains ingredients to establish convergence of (PGA) and (SGA)).
283
To prove Lemma[4.]] we will use an agent-wiss wise version of the "Gradient Domination property" that
284
has been shown to hold in single-agent MDPs [ (see Lemma 4.3). The second main ingredient is
the fact that a 3-smooth function (its gradient is Lipschitz) with parameter / 2mu
285
(1~))*
286
Exact gradients case. Theorem I.] (restated formally below) about rates of convergence of (GAA now be proved following standard arguments (in particular ascent property, Lemma D.I. on analysis of convergence of gradient descent to approximate stationary points in non-convex optimization [1I]. The ascent lemma suggests that for any f-smooth function, it holds that
286
[xx f()) 2 2z ||x' - ==1 where x' is the next iterate of (PGA). Thus, having shown that $ is 290
291
8-smooth function, the ascent lemma implies in our setting that
i (1(()) - - (T()) 2 4-AAmaxtt
(1-7)3
((+1)) - -()) (0)
(4)
Putting everything together, we can show the following theorem.
293
Theorem 4.2 (Formal Theorem 1.I part (a)). Let G be a MPG and let 80 E S denote an arbitrary initial state. Let also Amax max; As), and set the number of iterations to be T 16 A
294
(1-"))ee"
(1>)² and the learning rate (step-size) to be n- = 2-Ammee If the agents run independent projected policy gradient (PGA) starting from arbitrarily initialized policies, then there exists l (l...., TT such
285
that n! (1) is e-approximate Nash policy.
7

---

296
Finite samples case. In the case of finite samples, we analyze (PSGA) on the value V of each agent i which (as was the case for PGA) can be shown to be the same as applying projected gradient ascent on hb In this case, we choose a-greedy parametrization with a chosen appropriately. The key is to get an estimate of the gradient of Φ (see (2)) at every iterate. Lemma 4.3 argues that the
299
301
302
estimator of equation (2 is unbiased and has bounded variance.
Lemma 4.3 (Unbiased estimator with bounded variance ). It holds that ( is an unbiased estimator
303
304
of V n. T with bounded variance for all i E EN, i.e.,
24A V,, $ (1) with Egen | 2 c( 7))-))4) for all i E E.
Egt V %1
In this case, - y captures the probability for the MDP to terminate after each round since consider finite length trajectories. Using the above, we can now state part (b) of Theorem [.] Together with Lemma 4.3 and the stationariy--Lemma (Lemma 4.Ip i.e. that stationary points of Φ are Nash policies, its proof uses the smoothness of & and existing tools for the analysis of stochastic gradient descent for non-convex functions.
306
308
310
Theorem 4.4 (Formal Theorem
L.1 part (b)). Let G be a MPG and let so ES denote an arbitrary
initial state. Let Amax max; Ail, and set the number of iterations to be T = 48(1-))AAm)) D S*x
211-2)82 the agents run projected stochastic policy
312
and the learning rate (step-size) to be = 18nD2 Almas S52. S82. gradient JSSAA) starting from from arbitrarily initialized policies and using cx-greedy purametrization with
= e,, then with probability 8 there exists a 1. (1....,T) such that (0) is an e-approximate Nash policy.
314
315
316
Remurk 2 (Weighted and ordinal MPGs). We conclude this section with a remark on Weighted and Ordinal MPGs (cf. Definition in TT. It is rather straightforward to see that our results carry over for WMPGs. The only difference in the running time of (PGA) is to account for the weights (which are just multiplicative constants).
317
318
320
By contrast, the extension to OMPGs is not immediate and the reason is that we cannot prove any bound on the smoothness of & in that case. Therefore, we cannot have rates of convergence of policy gradient. Nevertheless, it is quite straightforward that (PGA) converges asymptotically to critical points (in bounded domains) for differentiable functions. Thus, as long as & is differentiable, it is guaranteed that (PGA) will asymptotically converge to a critical point of Φ. By Lemma 4. this point will be Nash policy.
321
322
323
324
5
Experiments: Congestion Games
327
We next study the performance of policy gradient in a general class of MPGs that are congestion games at every state (cf. (4). The setting of the current experiment is illustrated in Figure
328
329
330
Ex Experimental setup. There are 8 agents, 4 facilities and 2 states: a safe state and distancing state. In both states, all agents prefer to be in the same facility with as many other agents as possible (follow the crowd) [2]. In particular, the reward of each agent for being at facility k = A, B, C, D is equal to a predefined positive weight with times the number of agents at that facility. The weights satisfy w < w < urt < w i.e., facility D is the most preferable by all agents. If more than 4 = N/2 agents find themselves in the same facility, then the game transitions to the distancing state. At that state, the reward structure remains the same, but the weights are reduced by a constant factor, i.c., w = with - c, where e > 0 is a (considerably large) constant. To return to the safe state, the agents need to achieve maximum distribution over the facilities, i.c., no more
facilities
distancing state
331
332
333
N/2
N/4
335
safe state
336
Figure 4: The 2-state MPG.
338
340
342 than 2 = N/4 agents may be in the same facility.
343
To see that this MDP is a MPG, it suffices to check that every state is potential game and that condition C2 (i.e., equality of individual dummy terms) of Proposition 3.2 is satisfied. The first claim is straightforward since at each state, the agents play congestion game 22 25 The second claim follows from the fact that the rewards of all agents in all facilities at the distancing state are shifted by the same constant amount,
344
346
8

---

Paloy Gradert, -6 -0000001
Polcy Gradent nan 10.00 000001
Grodkett Rinaa (0.00)
spunncy dedddddddddde
04
Rarsoon
Bersoona
Figure 5: Policy gradient in the 2-state MPG with 8 agents of Section [ In all runs, the agents learn one of the deterministic Nash policies that leads to the optimal distribution among states (left). Individual trajectories of the LI-accuracy and averages (with I-standard deviation error bars) show fast convergence in all cases (middle and right columns).
348
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 common learning rate 1) 0.0001 (this 17 is (several orders of magnitude) larger than the theoretical guarantee, (1->)²
Paremeters.
349
350
351
08, of Theorem 4.2 Experiments with randomly generated learning rates (different for each agent), non-deterministic transitions between states and with different weights at each facility in the distancing state (that result in non- MPG structure) produce qualitatively equivalent results and are presented in Appendix
7
2ry Amaa"
352
354
355
Results. The left panel of Figure 5hsoows that the agents learn the expected Nash profile in both states in all runs Importantly, this (Nash) policy profile is deterministic line with Theorem 4.2 The panels in the middle and right columns depict the L1-accuracy in the policy space at each iteration which is defined as the average distance between the current policy and the final policy of all agents, n, final = N EiEN Es Ea [T | - n. finll (a s)]-
356
357
358
359
i.e., L1 Lccaurryyyy = N EiEN |TT
6
Further Discussion and Conclusions
351
We presented positive results (both structural and algorithmic) about the performance of independent policy gradient in Markov Potential Games (MPGs). We showed that MPGs always possess determin- istic Nash policies and that independent policy gradient is guaranteed to converge (polynomially fast the approximation error) (deterministic) Nash policy profiles even in the case of finite samples (assuming& a direct parameterization with greedy exploration). Our definition of MPGs generalizes prior works on wate-based potential MDPs (importantly, by encompassing MDPs that are not nec- essarily potential at each state) and demonstrates the effectiveness of simultaneous policy gradient in learning Nash policies even without the need to impose additional assumptions on state-based potential functions (cf.
382
383
384
385
366
367
368
[6 32
Given these positive results, several interesting questions emerge.
370
pen questions. When it comes to online learning in normal form potential games, it is possible to prove that many naturally motivated dynamics converge to deterministic Nash equilibria with certain desirable stability properties for most initial conditions [13 24] 17]. To produce such equilibrium selection results, standard Lyapunov arguments do not suffice and one needs to apply more advanced techniques such as the Center-Stable-Maniioo theorem [5]. Studying such techniques in the context
372
374
of MPGs is fascinating direction for future work.
376 On the other hand, given the complexities of multi-agent, state-based environments, it is highly unlikely to expect that practical algorithms can always guarantee convergence to equilibrium. This is already the case even for the more restricted settings of normal-form games [34] 22. Nevertheless,
378
deriving strong theoretical guarantees in the sense of cyclic/recurrent orbits, invariant functions [18]
380
or social welfare [31] in the context of exact, weighted or ordinal MPGs is another stimulating direction for future work. As a measurement of the inefficiency due to lack of coordination between agents, it would also be interesting to perform a Price of Anarchy type of analysis [4] as has been
382
383
excessively done in the context of normal-form potential (congestion) games (e.g.. (26)..
384
Finally, other natural directions for future work involve the study of policy gradient or variations
thereof (such as Natural Policy Gradient) in MPGs under different policy parametrizations, ef. (1. or the study of settings that fruitfully combine tools from both cooperative and competitive settings (as
386
in [10 36 38) that have (up to now) produced results in orthogonal directions.

---

References
388
389 [1] A. Agarwal, M. Kakade, J. D. Lee, and G. Mahajan. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes. In J. Abernethy and S. Agarwal, editors, Proceedings of 33rd Conference on Learning Theory, volume 125 of PMLR, pages 64 66, 2020.
391
[2] Gabriel P Andrade, Rafael Frongillo, and Georgios Piliouras. Learning in matrix games can be arbitrarily complex. arXiv preprint arXiv:2103.03405, 2021.
394
395
[3] Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2nd edition, 2000.
[4] I. Bistritz and N. Bambos. Cooperative multi-playe bandit optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2016-202.7 Curran Associates, Inc., 2020.
398
[5] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885-89)) 2019.
401
402
66] Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multia- gent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172, 2008.
404
405
[7]
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 6372-6381, 2017.
406
407
408
[8] A. Dafoe, Y. Bachrach, G. Hadfield, E. Horvitz, K. Larson, and T. Graepel. Cooperative ai: machines must learn to find common ground. Nature, 7857:33-36, 2021.
409
410
[9] A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, Z. Leibo, K. Larson, and T. Graepel. Open Problems in Cooperative AI. arXiv e-prints, December 2020.
411
412
[10]
C. Daskalakis, D.J. Foster, and N. Golowich. Independent Policy Gradient Methods for Competitive Reinforcement Learning. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5527-5540. Curran Associates, Inc., 2020.
413
414
415
416
[11] Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23(4) 2013.
417
418
[12] R. Hassin and M. Haviv. To queue or not to queue: Equilibrium behavior in queueing systems. Kluwer Academic Publishers, Boston, USA, 2003.
419
420
[13] Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In ACM Symposium on Theory of Computing (STOC), 2009.
422
423
[14] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In (STACS), pages 404-413 Springer- Springer-Verlag, Verlag, 1999.
424
425
[15] Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Benjamin Recht. First-order methods almost always avoid strict saddle points. Mathematical programming, 176(1):311-33) 2019.
426
428
[16] J. R. Marden. State based potential games. Automatica,
2012.
429
[17] Ruta Mehta, Ioannis Panageas, and Georgios Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and a conjecture of haploid genetics. In Innovations in Theoretical Computer Science, 2015.
430
[18] Panayotis Mertikopoulos, Christos Papadimitrion, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717, SIAM, 2018.
433
10

---

435
[19] D. Mguni. Stochastic Potential Games. arXiv e-prints, page NtXiv:2005.3352, May 2020.
[20]
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, page arXiv:2103.09284, March 2021.
437
439
[21] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G, Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-leve control through deep reinforcement learning. Nature, 51 (788750)::52955355
440
441
442
443
Feb 2015.
444
[22] D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 14(1):124- 143, 1996.
448
[23] OpenAl. Openai five. openai.com 2018.
447
[24] Ioannis Panageas, Georgios Piliouras, and Xiao Wang. Multiplicative weights update as a distributed constrained optimization algorithm: Convergence second-order stationary points almost always. In JCML, 2018.
449
450
[25]
T. Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM, 62(5). November 2015.
[26] Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM). 49(2):236-25) 259,, 2002.
451
[7]
L. S. Shapley. Stochastic games. PNAS, 1953.
454
[28]
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam. Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):4844455 Jan 2016.
455
456
457
458
459
[29] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre. Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140-1
481
2018
463
[30] Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018.
484
[31] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS' 15, pages 2989 2997, Cambridge. MA, USA, 2015. MIT Press.
486
488
469
[32] S. Valcarcel Macua, J. Zazo, and S. Zazo. Learning Parametric Closed- Policies for Markov Potential Games. In International Conference on Learning Representations, 2018
470
471
[33] Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McK- inney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):50-3354 Nov 2019.
473
475
477
479
[34] Emmanouil- Vasileeoo Vlatakis- Gkaragkounis, Lampros Flokas, Panayotis Mertikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. In Annual Conference Neural Information Processing Systems, 2020.
481

---

483
[35]
X. Wang and T. Sandholm. Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games. In Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS 02, page 1603-1610, Cambridge, MA, USA, 2002. MIT Press.
484
486
487
[36] Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. CoRR, abs/2 045400050 2021.
489
490
[37] K. Zhang. Z. Yang. and T. Basar. Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms. arXiv e-prints, page 1tt.:::9111111..... 2019.
491
482
(38) Yulai Zhao, Yuandong Tian, Jason D. Lee, and Simon S. Du. Provably efficient policy gradient methods for two-player zero-sum markov games. CoRR, abs3200000000 2021.
493
Checklist
494
1. For all authors...
496
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
497
496
Our introduction contains an informal presentation of our main results and an
overview of our techniques to make the better accessible to a wider audience.
500
(b) Did you describe the limitations of your work? [Yes]
501
Our work is mainly methodological. Its limitations in terms of the results are clearly described throughout the paper (in the sense that the results hold within the class of
502
503
MPGs and not for general MDPs) and its limitations in terms of the techniques are described in the technical sections.
504
505
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
507
508
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
In the main paper, we have included both a high-level technical overview (Intro- duction) and a sketch of the proof of the main results (Sections 3 and 4). In the supplementary material, we provide detailed proofs.
512
513
3. If you ran experiments...
515
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
516
517
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
518
519
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
520
521
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
Our experiments
be reproduced in any conventional computer in reasonable time. The code is freely accessible on GitHub (links to the repository are provided in the supplementary materials).
524
525
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
527
(a) If your work uses existing assets, did you cite the creators? [N/A]
528
(b) Did you mention the license of the assets? [N/A]
529
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
530
531
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

538
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
534
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
537
538
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
539
540
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qGS01WGkh15", "reviewer": "Reviewer_HF6B", "summary": "The paper introduces a novel class of Markov Games that generalize classical potential games in the normal-form representation. They show that such games always admit deterministic Nash policies, and that they enjoy some interesting properties that they make them a more suitable generalization of potential games than other attempts in the literature. The main result of the paper is that, in Markov Potential Games, policy gradient algorithms converge to Nash. The authors also provide an experimental analysis on congestion games. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: I think that the problem studied by authors is interesting, and that the paper makes a significant contribution to the research area. The idea behind the definition of Markov Potential Game is novel, and I think it provides a nice and clean generalization of its normal-form counterpart. \n\nQuality: As far as I am concerned, the technical claims are correct.\n\nClarity: The paper is well written, but I think that some modifications would help clarify it. For instance, the authors could better clarify the difference between (a) and (b) in Theorem 1.1 at the beginning, since I needed to step forward to the formal result later in the paper to better figure out what was going on. Also, the technical review is quite dense and hard to follow. Maybe, it's better to do not go into technicalities in the Introduction and add some more intuitions when the technical part comes into play.\n\nSignificance: I think that the paper would have a good fit in the NeurIPS conference.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "kXrDp4fKYM9", "reviewer": "Reviewer_7dwv", "summary": "This paper considers a multi-agent coordination setting as all agent utilities are perfectly aligned with each other via a common potential function. The authors claim that they present a novel function of Markov Potential Game (MPG) and prove fast convergence of independent policy gradient to Nash policies.", "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": "Potential game is one of the key concepts in multiagent reinforcement learning, especially when the cooperative setting is assumed. The main question of this paper is fast convergence guarantees for multi-agent RL, and the reviewer believes this is an important question. Even though this paper has a well-designed direction, however, the reviewer thinks the current version of the manuscript is not ready to be published at NeurIPS. \n\n\n1. Are the findings meaningful for MARL researchers?\n\nTheorem 1.2 is an important finding but it needs more discussion whether it is meaningful results in the perspective of multi-agent reinforcement learning. First of all, Theorem 1.2(a) is trivial unless it provides uniqueness. Next, Theorem 1.2(b) is a meaningful finding so we need Theorem 1.2(c) to find conditions for an MDP to be an MPG. The conditions for it are provided in Proposition 3.2. C1 claims that the state transition function should not depend on the action. In this case, RL is not necessary since RL is the effort to find an optimal action. \nThe reviewer believes that C2 is a meaningful part, leading that we need immediate reward which only includes the potential term. However, is it easy to decouple the reward to common term and dummy term? Most cooperative MARL problems have coupled reward functions. It would be beneficial to provide examples of reward function of standard MARL benchmarks (e.g., Starcraft, Hanabi, OpenAI hide-and-seek, etc). \n\n\n2. Can the main document stand alone?\n\nThe authors simply provide a long version document (31 pages) as supplementary material where a lot of parts are overlapped with the main document. If they separate the contents into main document and supplementary material, the main paper would be easy to follow, and supplementary material will be helpful. Currently, it is hard to find a piece of proper information in supplementary material since it is another long document. \nIn addition, there are a lot of never-defined notations in the main document. In the current format, the main paper cannot stand alone without supplementary, which is not desirable. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors provide open questions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "cc7w-Hx-s4U", "reviewer": "Reviewer_4tX4", "summary": "In this paper, the authors present a new definition of Markov Potential Games (MPG). They discuss the relationship between MPG, normal form potential game, and Markov games where every state-game is a potential game.  They study MPGs by presenting sufﬁcient conditions for MPGs and the existence of deterministic Nash policies.  They show the conference of independent-playing policy gradient to Nash policies, in both exact gradient case and finite sample case. Experiment results validate the congergence.", "questions": "", "limitations": "", "rating": 7, "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": "- Significance: \nMPG serves as an important and fundamental setting towards understanding multi-agent systems. Understanding the behavior of standard methods such as policy gradient is of central interest in the relevant literature. Hence this paper provides a solid contribution. \n\n- Quality and Clarity: \nThe authors have conducted a clear theoretical analysis, which seems to be very rigorous. In the experiments, the authors conducted congestion games to validate the predicted convergence clearly. \n\n- Originality: \nThe definition of MPG in the present paper is novel to my knowledge.  The proof of convergence via gradient dominance is commonly used. To improve the originality, I believe the author could discuss more what's the difference between MPG defined in this paper and in some other papers, for example:\n\n> Macua, Sergio Valcarcel, Javier Zazo, and Santiago Zazo. \"Learning parametric closed-loop policies for markov potential games.\" arXiv preprint arXiv:1802.00899 (2018).\n\nOverall, this paper is worthy of acceptance to me. I'm glad to increase my score if the discussions are provided and more experiments on some other examples of MPGs could be conducted.\n\n- Minor points: In equation (3), should the $\\alpha_i$ be $\\alpha$? A similar typo exists in the full version too (eq (4)).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No visible negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No visible ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2oQNPLM8ijg", "reviewer": "Reviewer_GJfn", "summary": "The paper focuses on one of the game theoretic views of Reinforcement Learning: the convergence of policy gradient in games of several agents. The authors build on the existing theory by adding new definitions that support the multi-agent learning systems in order to measure the complexity of the convergence of the policy gradient to Nash policies.", "questions": "", "limitations": "", "rating": 5, "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": "The paper is written in a clear and formal manner. The conclusions seem to respect the stated theorems (as corollaries). The next section has some points about the specificity of the paper's context and its novelty results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper builds on [10] of the included literature, where the authors had introduced the first independent policy gradient algorithms for competitive reinforcement learning in zero-sum stochastic game. The main result of the current paper is the fast convergence of these algorithms to the so-called 'Nash policy'.\n\n1) This seems an interesting result but It seems to make a minor contribution to a reasonable problem. It looks like a simply developed extension of the previous paper. Its novelty and significance as far as the paper's modelling is concerned (as a whole) needs to be validated.\nFrom a first point of view, the results do not seem like a breakthrough. \n\n2) The 'novel definition of MPGs that generalizes prior attempts' is interesting from the theory point of view, but it seems that it is specially developed here so that it creates a desired context. That is, it seems like a theoretical construction which supports the result, rather than solving a core problem that had arisen in [10].\n\n3) Also, although is it a well suited result for the theory of Markov Decision Processes (MDPs) founded in [10], I am not certain of how significant it is for the readers of this conference. The focus is mainly game-theoretic and about the complexity of this game, rather than in the theory of Learning. The theorems concern the relation of Markov Potential Games to (MDPs) and conclude the convergence to an \\epsilon-Nash policy. This sounds like a Game Theory result.\n\nWhich are the learning systems that benefit from the fast convergence? \nAre there any 'common' machine learning systems that benefit from this?\n\n4) The authors list an example of an eight agent congestion game which is demonstrating the MPG property. What is the applicability of this example and their convergence result in a learning context with several agents? Have the authors tried to apply that somewhere in machine learning? Can they present this in the paper? \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The discussion of this paper raised a lot of points that, I hope, will be useful to the authors:
1. there is no concern on the mathematical derivation; this is a very good selling point, but it is not sufficient
2. while there is a strong agreement that this paper would perfectly fit with more game-theory oriented venues, there are objections that, in the current form, it fits with ML venues: in particular, the authors should strengthen the learning theory part. As remarked by some Reviewers and argued in the rebuttals by the authors, some parts of the paper should be re-organized, thus requiring a second round of reviewing. 

My suggestion to the authors is to implement the comments raised by the Reviewers carefully. The converge result is nice and a bit of effort spent to re-organize the paper will lead to a very probable acceptance in a top-rated ML conference. 
Decision: Reject