Gradient play in stochastic games: stationary points, convergence, and sample complexity
Authors: Runyu Zhang
Zhaolin Ren
Na Li
Venue: ICLR 2022 Submitted (2022)
Keywords: multiagent reinforcement learning
stochastic game
policy gradient
Nash equilibrium
sample complexity

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

Under review as a conference paper at ICLR 2022
GRADIENT PLAY IN STOCHASTIC GAMES: STATIONARY POINTS, CONVERGENCE, AND SAMPLE COMPLEXITY
Anonymous authors Paper under double-blind review
ABSTRACT
We study the performance of the gradient play algorithm for stochastic games (SGs), where each agent tries to maximize its own total discounted reward by making decisions independently based on current state information which is shared between agents. Policies are directly parameterized by the probability of choosing a certain action at a given state. We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting, and give a local convergence rate around strict NEs. Further, for a subclass of SGs called Markov potential games (which includes the cooperative setting with identical rewards among agents an important special case), we design sample-based reinforcement learning algorithm and give a non-ac non-asom -symsttmt global convergence rate analysis for both exact gradient play and our sample- based learning algorithm. Our result shows that the number of iterations to reach an e-NE scales linearly, instead of exponentially, with the number of agents. Local geometry and local stability are also considered, where we prove that strict NEs are local maxima of the total potential function and fully-mixed NEs are saddle points.
INTRODUCTION
Multi-agent systems find applications in wide range of societal systems, e.g. electric grid, traffic networks, smart building and smart cities etc. Given the complexity of these systems, multi-agent reinforcement learning (MARL) has gained increasing attention in recent years (Daneshfar & Bevrani 2010: Shalev-Shwartz et al., 2016 Vidhate & Kulkarni 2017; ; Xu et al.] 2020). Among MARL algorithms, policy gradient-type methods are highly popular because of their flexibility and capability to incorporate structured state and action spaces. However, while many recent works <Zhang
et al.] 2018) [hen et al.) 2018 Wai et al.] 2018 Li et al., 2019] Qu et al.) 2020) have studied the sample complexity of multi-agent policy gradient algorithms, due to a lack of understanding of the optimization landscape in these multi-agent learning problems, most works can only show convergence to a first-order stationary point. Deeper understanding of the quality of these stationary points is missing even in the simple deeticall-eearrd multi-agent RL setting.
In this paper, we examine this problem from a game-theoree theoretic perspective. We model the multi-agon system stochastic game (SG) where agents can have different reward functions, and study the dynamical behavior of first-order (gradient-based) learning methods. The study of SGs dates back to as early as the 1950s by [Shapley] (1953) (1953) with a series of followup works on developing NE-secking algorithms, especially in the RL setting (e.g. (Littman] 1994, BBolling & Veloso 2000 Shoham et al. 2 Zhang 20199) and citations within). While well-known classical algorithms for solving SGs are mostly value-based, such as Nash- Q learning (Hu & Wellman 2003). Hyper-Q learning (Tesauro) 2003). and WoLF-PHC (Bowling & Veloso
2003 Buşoniu et al. 2010 Lanctot et al. 2017
2001). gradient-based algorithms have also started to gain popularity in recent years due to their
advantages as mentioned earlier (e.g. (Abdallah & Lesser, 2008 Zhang & Lesser] 2010 Foerster ct al. 2017)). In this work, we aim to gain deeper understanding of the structure and quality of first-order stationary points for these gradient-based methods, with a particular focus on answering the following questions: 1) How do the first-order stationary points relate to the NEs of the underlying game?, 2) Do gradient- basdee algorithms guarantee convergence to a NE?, 3) What is the stability of the individual NEs?, and 4) How should agents learn using local samples from the environment?.
These questions have already been widely discussed in other settings, e.g., one-shot (stateless) finite- action games (Shapley 1964 Crawford 1985 Jordan
1993 Krishna & Sjöström 1998 Shamma &

---

Under review as a conference paper at ICLR 2022
Arslan 2005 Kohlberg & Mertens 1986 Van Damme 1991 ) one-shot continuous games (Mazumdar et al. 2020). zero-sum linear quadratic (LQ) games Zhang et al. (2019b), etc. There are both negative and positive results depending on the settings. For she- continuous games, (Mazumdar et al. 2020) proved a negative result suggesting that gradient flow has stationary points (even local maxima) that are not necessarily NEs. Conversely, [Zhang al. (2019b) designed projected nested-gradient methods that provably converge to NEs in zero-sum LQ games. However, much less is known in the tabular setting of SGs with finite state-action spaces.
Contributions, In our paper, we consider the gradient play algorithm for the infinite time-discounted reward SGs where an agent's 's individual policy is directly parameterized by the probability of choosing an action from the agent's 's own action space at a given state. We focus on the tabular setting where state and action spaces are finite. Through generalizing the gradient domination property (Agarwal et al. 2020) to the multi-agent setting, we first establish the equivalence of first-order stationary policies and Nash equilibria. We then show that strict NEs are locally asymptotically stable under gradient play and provide a local convergence rate analysis.
Additionally, we study the global convergence for a special class of SGs called Markov potential games (MPGs) (González-Sänchez & Hernández-Lerma 2013 Macua et al. 2018 Leonardos et al. 202I). which includes identical reward agget RL (Tan [993] Claus & Boutilier [998] Panait & Luke 2005) an important special case. In this setting, first show that exact gradient play can
find an e-Nash equilibrium within O | ( Id,)) steps. Then, we design sample- sample-based gradient play algorithm and show that it can find an c-Nash equilibrium with high probability in a fully-
decentralized manner using Ô ( poly ( (1_1.- 15), ma,, (A.l)) samples, where |8], |A, denote the size of the state space and action space of agent respectively. The convergence rate shows that the number of iterations to reach an e-NE scales linearly with the number of agents. In the sample-based learning, agents only need to observe the state, their own actions, and their own rewards. The key enabler of the learning is the existence of an underlying averaged MDP for each agent when other agents' policies are fixed. Our learning method can be viewed as model- -based policy evaluation method with respect to agents' averaged MDPs. This averaged MDP concept could be applied to design many other MARL algorithms, especially the local geometry around some special classes of cquilibrium points, showing that strict NEs are local maxima of the total potential function and that fully mixed NEs are saddle points. Lastly, all the al algorithms studied in this paper have been numerical tested and results are provided in Appendix A
reticc-vvaluation -abeed methods. We also study
Comparison to other MARL algorithms: For MPGs with continuous state and action spaces, there are studies about learning either the open-loop González-Sänchar & Hernández- 2013) Zazo et al. 2016) or the closed-loop (Macua al. 2018) NEs for MPGs. These works generally assume full model information and solve the problem via optimal control. There are two recent arXiv preprints (Mguni 2020: Leonardos al. [02T Mguni al. 202T) studying MPGs that similar to our MPG setting. In particular, Leonardos et al. (2021) also studies gradient play for MPG. Both of our papers share similar results on MPGs but the sample-based methods are designed from different perspectives lT In addition, our papers studies general SGs besides MPG. Moreover, our concept of "averagedd" MDPs could also serve as a useful tool for the design and analysis of other MARL algorithms. Beyond these MPG works, decentralized Q-learning introduced in Arslan & Yüksel (016) might be the closest to the setting considered in this paper. They consider the identical interest and only show asymptotic convergence to the set of NEs. There other recent works that also study learning for general-sume sum or zero-sum stochastic games. However the settings they consider are different from our setting, for example, Daskalakis et al. (202I) considers convergence to NE for two player zero-sum games, while Song et al. (2021) considers convergence to correlated equilibrium for finite time horizon general-sum games. On the other hand, Zhang et al. (2018); Li] iet al. (2019); : Qu et al. (2019) consider slightly different MARL settings, where agents collaboratively maximize the summation of agents' reward with either full or partial state observation. They also require communication between neighboring agents for better global coordination.
Leonardos et al. 2022 considers Monte Carlo, model- free gradient estimation. The sample complexity is derived under the condition that the estimation is unbiased, which is difficult to hold in general. Interestingly, both sample complexities are O ( ). is an interesting question to study whether such dependence is fundamental not. We also remark that Leonardos et al. (202)) and this work are done in parallel.
2

---

Under review as a conference paper at ICLR 2022
2 PROBLEM SETTING AND PRELIMINARIES
: Fn), Y: P) We consider stochastic game (SG) M (N, A = A1 x... An. p. (r1....... with n agents (Shapley 1953) which is specified by an agent set N = (1,2....,, : a finite state space S, a fimite action space A; for each agent E N, transition model P where P(s a) = P(s'|8,0 .1...., On) is the probability of transitioning into state 8' upon taking ac- tion (01..... an) in state where a, E A, is action of agent agent i's reward function [0, 1), and an initial state distribution over S.
S x A + [0, 1], a discount factor
stochastic policy т + A(A) (where A(A) is the probability simplex over A) specifies strategy in which agents choose their actions jointly based on the current state in a stochastic fashion, Lee Pr(at]s: (s) = x (t) A distributed stochastic policy a special subclass of stochastic policies, with X nn, where h. S + A(A.). For distributed stochastic policies, each agent takes its action based on the current state & independently of other agents' choices of actions, i.e.:
Pr(ay)s;) (((l))))) = II T=(a,,18e), at = (a1,s..... (p,,))
For notational simplicity, we define: Tz (a(aa))) = Ilir n. (a;ls), where I S N is an index set. Further, we use the notation -i to denote the index set (i))
We consider direct distributed policy parameterization, where agent i's policy is parameterized by 0g:
5.,0, (a. = (.,())))): i= 1,1,2....,
(1)
For notational simplicity, we abbreviate ni,0; (ails) as To, (a:1s), and O (,((a, as 0s Here 0 E ((A))ss), i.e. Og is subject to the constraints 0s.a; 2 and Ea,es, 0z.;; for all S. The global joint policy is given by: (a(a)s) = IT= To,
(a; [s) I Os,a-- We use X
A(A,) X' == X1 x ... x Xn to denote the feasible region of 0g and A.
Agent i's value function V," S + R, N is defined as the discounted sum of future rewards starting at state via executing ne, i.c.
(s) =
Σ (resss,
Tg. 80 =
where the expectation is with respect to the random trajectory T = (St, Gr ri,) where a ~ To(-(st,, 8441 = P(+Ist,a;) az). We denote agent i's total reward starting from initial state 8o ~ p as:
J.(0) = J.(O)..... 0n) == Eap-p V/ ((o).
In the game setting, Nash equilibrium often used to characterize the performance of agents' policies.
Definition 1. (Nash equilibrium) A policy 0- .O....., .0%) is called Nash equilibrium (NE) if J,(07,02)) 2 1,,0, VO Xx EEN
The equälibrium is called strict NE if the inequality holds strictly for all 6 E X: and E N. The equilibrium is called a pure NE if corresponds a deterministic policy. The equilibrium called mixed NE if it is not pure. Further, the equilibrium is called fully mixed NE if every entry of 0 is strictly positive, i.e.: 0z > 0, va E A,, V E S, E
We define the discounted state visitation distribution dg of policy we given an initial state distribution as:
do(s) = Esprp
Σ 7 PP = s|su),
(2)
where Pr = s|so) is the state visitation probability that 8, = s when executing me starting at state 80. Throughout the paper, we make the following assumption on the SGs we study.
Assumption 1. The stochastic game M satisfies: de(s) > 0, Vs E S, V0 E X.
Assumption T requires that every state is visited with positive probability, which is a standard assumption for convergence proofs in the RL literature (e.g. (Agarwal al. 2020 Mei et al. 2020
3

---

Under review as a conference paper at ICLR 2022
Similar to centralized RL, define agent i's Q-function Q : - R and its advantage function A S x A -> R as:
as : Σ )r)(s), Tg. s0 = =,,00
=- = (2)
Averaged' Markov decision process (MDP): We further define agent i's 'averaged' Q-finction
Q S A: R and 'averaged' advantage-function A : Ai + as:
(s, = [=__(a_s)))((ss,....
(s, = E no (a as, a.,a.)) (3) a-
B-
Similarly, we define agent i's 'averaged' transition probability distribution P. 5.8x A, + and 'averaged' reward r. S A R as:
(s = Σ To (1))( as) ax)) = Σ To
From its definition, the averaged Q-function satisfies the following Bellman equation:
Lemma 1. Φ satisfies: (s) = 7 ai) + Σ no. (o s',a;
(4)
Lemma suggests that the averaged Q-function Q is indeed the Q-function for the MDP defined on action space A,, with r P as its stage reward and transition probability respectively. We define this MDP as the 'averaged" MDP of agent i, i.e., M¹ = A;, P. r 7, p). The notion of an "averaged" MDP will serve as an important intuition when designing the sample-based algorithm. Note that the "averaged' MDP is only well-defined when the policies of the other agents A_, are kept fixed. When this is indeed the case, agent can treated as an independent learner with respect to its own 'averaged' MDP. Thus, various classical policy evaluation RL algorithms can then be applied.
3 EXACT GRADIENT PLAY FOR GENERAL STOCHASTIC GAMES
Under direct distributed parameterization, the gradient play algorithm is given by:
Exact Gradient Play: ((++1)_ Projx, (8!") + Vo, (.. 7>0. 0.
(5)
Gradient play can be viewed as a 'better response" strategy, where agents update their own parameters by gradient ascent with respect to their own rewards. A first-order stationary point defined as such:
Definition 2. (First-order stationary policy) A policy 0" stationary policy if (0,- 0,) V.,". O, v0, E X,, i N.
(0i....,0)) 0;)) is called a first-order
It is not hard to verify that 0* is first-order stationary policy if and only if is fixed point under gradient play (Equation (5)) Comparing Definition[[[on NE) and Definition 2 we know that NEs are first-order stationary policies, but not necessarily vice versa. For each agent first-order stationarity does not imply that 0r is optimal among all possible 0, given 0-,- However, interestingly, we will show that NEs equivalent to first-order stationary policies due gradient domination property that we will show later. Before that, we first calculate the explicit form of the gradient Ve, Ja.
Policy gradient theorem (Sutton al.
1999 gives efficient formula for the gradient:
1
Voleoro V((
E8 Ba Banto (1)) [V Ve log (al ie N.
(6)
Applying Equation the gradient Ve, Js can be written explicitly as follows:
Lemma 2. (Proof in Appendix D For direct distributed parameterization (Equation 7
0J,(0)
do(s))
(7)
00 1
4

---

Under review as a conference paper at ICLR 2022
Gradient domination and the equivalence between NE and first-order stationary policy, Lemma 4.1 in Aggaraa et al. (2020) established gradient domination for centralized tabular MDP under direct parameteriization We can show that a similar property still holds for stochastic games.
Lemma 3. (Gradient domination, proof in Appendix E For direct distributed parumeterization
(Equation 7)). we have that for any = (01....,
.......,,) 8m) E E.:
dø
O=:) Jo(Oi, 0-i) <
max (0, 0.) -.) VV, J(0), 4O, 2, iEN (8) 00 A.ENt
dg
where
dat dy
max,
der(e) and 0' (0% 0-.). do (x))
For the single-agent case 1), Equation is consistent with the result Agarwal al. 2020))
Le.: J(0") (0) S dar de
maxgex (0 (())). However, when there are multiple agents,
the condition is much weaker because the inequality requires θ_; to be fixed. When 1, gradient domination rules out the existence of stationary points that are not global optima. For the multi-an multi-agent case, the property can no longer guarantee the equivalence between first-order stationarity and global optimality; instead, it links the stationary points with NEs as shown in the next theorem whose proof is in Appendix B
Theorem 1. Under Assumption ! first-order stationary policies and NEs are equivalent.
Local convergence for strict NEs Although the equivalence of NEs and stationary points under gradient play has been established, it is in fact difficult to show that gradient play converges to these stationary points. Even in the simpler static (stateless) game setup, gradient play might fail to converge (Shapley 1964; Crawford 1985 Jordan 1993; Krishna & Sjöström 1998). One major difficulty is that the vector field {V 0: J.(0) i==1 is not a conservative vector field. Accordingly, its dynamics may display complicated behavior. Thus, as a preliminary study, instead of looking at global convergence, we focus on the local convergence and restrict our study to special subset of NEs the strict NEs. We begin by giving the following characterization of strict NEs:
Lemma 4. Given stochastic game M, any strict NE fr is pure, meaning that for each and s, there exist one (8) such that 0% s.o, 1a; = di(s) Additionally,
i) at (8) arg max A (s, i)) A (s) O; tdi) A (s, az) < 0, Va; # (s) (9)
Based this lemma, we define the following for studying the local convergence of strict NE 0":
A (8)
min
A (s, as)
A min min
_--d0- do- (s) (s) 0.
(10)
(.)))(())
Theorem 2. (Local finite time convergence around strict NE) Define the metric of policy parameters
as: D00 := maxigign max,s [|0,,, alll where || || denote the E1- norm. Suppose 0
is strict Nash equilibrium, then for any (()) such that D(000)110))
Sn| ) running
A (1-733
gradient play (Equation 5) will guarantee (00(++)1100)) < max D(O00)
2 00 which
2 1107) 74
means that gradient play is going to converge within
steps.
Proofs of Lemma and Theorem 2 are provided in Appendix F The convergence only requires a finite number of steps and the stepsize can be chosen arbitrarily large so that exact convergence can happen in even just one step. However, the caveat is that we need assume that the initial policy is sufficiently close to 0*, For numerical stability considerations, one should pick reasonable stepsizes to run the algorithm to accommodate random initializations. Theorem also shows that the radius of A 2" (1-))"
region of attraction for strict NEs is at least Sn Σ.. IA.I)* and thus 0 with a larger A i.c., a
larger value gap between the optimal action and other actions, will have a larger region of attraction. We would like to further remark that Theorem 2 only focuses way to interpret the theorem is that, if there exists a strict NE, then it is locally asymptotic stable under gradient play. However, does not claim to solve the global existence or convergence of the strict NEs.
the local convergence property, the
5

---

Under review as a conference paper at ICLR 2022
4 GRADIENT PLAY FOR MARKOV POTENTIAL GAMES
We have discussed that the main problem for the global convergence of gradient play for general SGs is that the vector field ( is not conservative. Thus, in this section, we restrict our analysis special subclass where the vector field is conservative, which in turn enjoys global convergence. This subclass is generally referred to Markov potential game (MPG) in the literature.
Definition 3. (Markov potential game (Macua et al. 2018)) A stochastic game M is called a Markov potential game if there exists potential function S A1 X An + R such that for any agent i and any pair of policy parameters (0), 01), (0,, 0-1):
E
7rra az) 00 00),0
E
y rr, ae) (0,,0-i),
E
pb(( (0) (0, 00),0_)),00-
E
7o(s an) =
(0,, 0-), V
t=0
t=0
As shown in the definition, the condition of MPG is admittedly rather strong and difficult to verify for general SGs. |Mauua et al. (2018); Gonzälez-Sānchez & Hernández-Lerma, (2013) found that continuous MPGs
model applications such as the great fish war (Levhari & Mirman 1980). the
stochastic lake game (Dechert & O' Donnell 2006), medium access control (Macua et al. 2018) etc.
There are also efforts attempting to identify conditions such that a SG MPG, e.g., Macua al.) et al. (2021); Mgunn 2020). In Appendix B we provide a more detailed discussion on MPGs, including necessary condition (Lemma 5 of MPG, counterexamples of stage-wise potential games that are not MPG, sufficient conditions for SG to be a MPG, and application examples of MPG. Nevertheless, identifying sufficient and necessary conditions and broadening the applications of MPG are important furture directions.
Given a policy we define the 'total potential function' (() == Bey DS
C d'd(s, az) Te]
for MPG. The following proposition guarantees MPG has at least one NE and it is a pure NE.
Proposition 1. (Proof in Appendix G For Markov potential game, there is at least maximum Or of the total potential function 4 i.e.: 0* E arg max 4(0) that is a pure NE.
global
From the definition the total potential function we obtain the following relationship
Ja 0-3) J.(0,, 0-:) ( + 0-s).
(11)
Thus.
J. = (())
which means that gradient play (Equation (5) is equivalent to running projected gradient ascent with
respect to the total potential function Φ, i.e.: g(t-1) Projx v / (b!")) n >
To measure the convergence to NE, we define an e-Nash equilibrium as follows:
Definition 4. (c-Nash equilibrium) Define the 'NE-gap' of policy 0 as:
NE (0); = max J. J4 J,(0;, 0-);: NE- NE-gap(0)) == max NE (O);
8,EX.
A policy is an c-Nash equilibrium if: NE-gap(0) Sc.
We further assume that the MPG satisfies the following assumption. Assumption 2. For E X, the total potential function
functioonn 4 (8)) is bounded by: Pmin S < < mmax-
4.1 EXACT GRADIENT PLAY GLOBAL CONVERGENCE AND LOCAL GEOMETRY
In this section, first focus the global convergence for exact gradient play ( where the gradient JJ can be calculated exactly by agent i. The convergence result is given as tollows:
Theorem 3. (Global convergence to Nash equilibria, proof in Appendix H) Given a MPG with
potential function Φ(s, a), suppose the total potential function t satisfies Assumption 2 Then with

---

Under review as a conference paper at ICLR 2022
(2-7)a stepsize 1l = 2Σ A.]' 0 asympiotically converge to NE under gradient play (Equation 5
i.e, lim NE-gap(0(0) = Further, we have:
64M² max
minn)| Ei= IAil
E NE- (E-gap(((()) S S²,, whenever T 1SEST
(12)
(1-7)
where M maxe,0'e M'x
de de
(by Assumption we know that this quantity is well-defined)
The factor M is also known the distribution mismatch coefficient that characterizes how the state visitation varies with the policies. Given an initial state distribution that has positive measure on every state, M can at least bounded by M S - maxo de
S min, p(a) Also note that
00
Inequality 12) on the average term 1 Σ LisiSt NE-gap(0(0) could be translated to constant probability guarantee on single NE- -E-gap(( gap((()))))) (0(*)) For instance, if we randomly pick one O()) from 1 S 1. < T, then it guarantees that NE N < e2 with probability least comparison with centralized learning, if we parameterize the policy in centralized way. the size of the
As
action space will be |A| = I[= |A:] and the projected gradient ascent would need O
|A
steps to find an e-optimal policy (Agarwal et al. 2020; whereas we only need O
[S|] 14.1
Steps
to find an c-NE, which scales linearly with n. However, centralized parameterization can provably find a global optimum, while distributed parameterization can only find a NE.
Though gradient play is guaranteed to converge to a NE, the exact NE which converges to is uncertain, and depends on the initial point well as the local geometry around the various NEs. As preliminary study, we have the following characterization for two special types of NEs. More future investigation is needed for general NEs.
Theorem 4. For Markov potential game with Pmin <mmax (i.e., T is not constant function):
A strict NE 6t is equivalent
strict local maximum of the total potential function 4 iee: 3 8, s.t. V 0 4* that satisfies | 00 S 5, 0 X, we have 4 < 400)).
Any fully mixed NE 6" is a saddle point with regard to the total potential function t; s.t. 110-0" S ō and (0))>((0))
i.e.: 6 > 0,
>
Theorem/4jmplies that strict NEs asymptotically stable under first-order methods such as gradient play; while the fully mixed NEs are not stable under gradient play. We remark that the conclusion about strict NE in Theorem 4 does not hold for settings other than tabular MPG; for instance, for continuous games, one can use quadratic functions to construct simple counterexamples (Mazumdar jet al. 2020). Also, similar to the remark after Theorem 2 of the NEs but does not claim the global existence convergence of either strict NEs or fully mixed NEs.
this theorem focuses on the local geometry
4.2 SAMPLE-BASED LEARNING: ALGORITHM DESIGN AND SAMPIEF COMPLEXITY
In this section, we no longer assume access to the exact gradient, but instead estimate it via samples. Throughout the section, we make the following additional assumption on MPGs:
Assumption 3. ((T,as)-Son -SufSffiie exploration on stales) There exist a positive integer and as E (0, such that for any policy 0 and any initial state-action pair (8, (5)) Vi, we have
Pr(sz|80 = 8, ag = a) 2 0s. VsT-
(13)
It says that every state has positive probability of being visited after some time. This assumption is common in proving finite time convergence (e.g. (Qu et al. 2019, Srikant & Ying 2019)).
We further introduction the state transition probability under 0 Pg S x S IR as:
(s'ssss) Σ (((aas))(s/(s,c))
We consider fully decentralized learning, where agent observation only includes state 8,, its own action 0j,t, and its own reward ri, := ri(st, az) at time t. Such fully decentralized learning is
Here 3, 3 could be replaced by - where p E (0, 1) is probability.
7

---

Under review as a conference paper at ICLR 2022
plausible due to the fact that when 8-, is fixed, agent can be treated independent learner with the underlying MDP being the "averaged" MDP described in Section 2 With this key observation, we design two-timescale 'model-based" on-policy learning algorithm, where agents perform policy evaluation in the inner loop and gradient ascent at the outer loop. 'he algorithm is provided in Algorithm [ Roughly, it consists of three main steps: 1) (Inner loop) Estimate the averaged transition probability and reward using on-policy samples P. P...P. P'. 2) (Inner loop) Calculate averaged Q-function Of and discounted state visitation distribution dg, and compute the estimated gradient accordingly. 3) (Outer loop) Running projected gradient ascent with estimated gradients. Before discussing our algorithm in more detail, we highlight that the idea of using the "averaged" MDP can be used to design other learning methods including model-free methods, e.g.. using the temporal difference methods perform policy evaluation. One caveat is that the "averaged" MDP is only well- defined when all the other agents use fixed policies. This makes it difficult to extend the two-timescale framework singleltimescale settings, which an interesting future direction.
Algorithm 1 Sample-bass basee learning
Require: learning rate 1/. greedy parameter a, sample trajectory length T,, total iteration steps Te For each agent i
for k 0,
To do for t = 0, 1, Ty do Implement policy Q(8) and collect trajectory D D D Use, ai,t, ri,d, are o (-1s)
end for Estimate
21 0 PS. M. by Equation
14
Equation
15
Equation 16 respectively.
Calculate Q de by Equation 17
Equation
(18) respectively.
Estimate the gradient by Equation [9):
Run projected gradient ascent as in Equation
20
end for
Step 1: empirical estimation of P.". P...T. Ps: Given sequence fst, as, Teele generated by
policy 0 (0:, i),, the empirical estimation P of Pd is given by:
Ty-l Ein 1(
Ty t=1 1(s: -, = 2 (14)
Pf (s
1 = s}
2- Σ 1(8: 8, 04,1 = 0;} = 0
Here we separately treat the special case where the state and action pair is not visited through the whole trajectory, i.e., ΣT'-1 1sst = s, ai,t = a,} to make P!d well-defined.
Similarly, the estimates r P3 of r PS are given by:
El ((s==,,;==a))
E 1(s: 8, a;} 2
(s,
Iy ((
(15)
0,
T--1
1(st = = =a} = 0
1=1
Di "18801=0' m0=))
T t=1
1fst = =} 2
pg(ss(s):=
Σ 1(8==s)
(16)
1 s]
Σ 1fst = s) =0
Step estimation of Qi, ds: We slightly abuse notation and use Q P. SII-Al to also denote the vectors corresponding to the averaged Q-function and reward function of agent i. Similarly, dg E RSS are used to denote the vectors for p(s) and ds).. Define MD E IR ((1114
MP (s.0.)-(o',0)) == Fe, (a. )pp (8'18,a)).
8

---

Under review as a conference paper at ICLR 2022
Then from Lemma Of is given by: (I 11--10 yMM, (.M))( Q. =9
O (I 11
The estimated averaged Q-function Q. is given by
Q = ( ',7 where M (s,a)))) no. (d az)
(17)
Similarly, from Equation 2 we have that dg and do are given by (derivation see Appendix
de (1 11-7) 7) (I >P3 P. d= (1
(1-21) (1-)) (1 (T-PP3 ) P.
(18)
Then accordingly, the estimated gradient is computed as:
1-7 - [
0en.. ((((())
(19)
Step 3: Projected gradient ascent onto the set of a-greedy policies: Let U, ...... (m)
denote the n dimensional uniform distribution. Define [0] (0))))))))))))))...)))))))))))") We use (p(:=)((AA)))))) Og and 0 respectively. Every step after doing gradient ascent, the parameter & will further be projected onto X", i.c.:
( 8.1. 801.00 (L-a))aaa))
=p= x 22 x... X to denote the set of the a-greedy policies for
0 Projx; (0 + V.
(20)
The reason of projecting onto x instead of X' is to make sure that every action has positive possibility of being selected in order get relatively accurate estimation of averaged Q-function. Intuitively,
a larger a introduces larger additional error in the NE-gap; however, a smaller a requires more samples to estimate the gradient. Thus the choice of a is the tradeoff between the two effects.
Theorem 5. (Sample complexity) Assume that the MPG satisfies Assumption
3
Let M
de In Algorithm for S +E, de'
(1-7)²
(1-7)e and
maxe, EX
6MM
Ty 206976rnM*1 max, 1 log 16T 1,1,, +T, TOZ 648M @ max D mmin)s S|
(1 (1-7) 7
ne²
with probability at least 1 - 5, we have that:
1 E NE NE- c²
That is, the algorithm can find an e-NE with probability at least 1 - 8 with (
TyTG ~ ò n
poyy
1
|S] max (dil)
(21)
samples, where Ô hides log factors.
Comparison with centralized learning: The best known sample complexity bound for single- agent/centralized MDP is Ô SILA| (--
Sidford et al. 2018). Compared with Equation 21). the
However, argued in the previous subsection, the total action space |A| = IT= |.Ail in the centralized bound scales exponentially with the number of agent n, while complexity bound only scales linearly. Here, we briefly state the fundamental difficulties of learning in the SG setting compared with centralized learning, which also explains why our bound scales worse with respect to the factors e, (8), |Asl, rLz 1) Firstly, the optimization landscape the SG setting is more complicated. For centralized learning. the gradient domination property is stronger and accelerated gradient methods (c.g. via natural policy gradient or entropy regularization) can speed up the convergence of exact gradient from ( to O (Agarwal et al. 2020). or even ( (Mei et al., 2020 In contrast, for multi-agent settings, due the more complicated optimization landscape, these methods can longer improve the dependency on which thus makes the outer loop complexity TG larger. 2) Secondly, the hehavior of other agents makes the environment non-stationary, i.e., the averaged Q-function Q as well the averaged transition probability distribution μ depends on the policy of other agent 0_,. Thus, unlike centralized learning, where the state transition probability matrix can be estimated in an off-policy or
centralized bound scales better with respect to c, S1,
FFrom the Perron-Frobentc Frobenius thcorem, we know that the absolute values of the eigenvalues of M are upper hounded by 1, which guarantees that the matrix 1 >M invertible.

---

Under review as a conference paper at ICLR 2022
offline manner, ie. using data samples from different policies, P only be estimated in online manner, using samples generated by exactly the same policy 0, which increases the inner loop complexity Ty. 3) Thirdly, the complicated interactions amongst agents necessitate more care during the learning process. Algorithms designed for centralized learning that achieve near-optimal sample complexity are generally Q-learning type algorithms. However, in SGs, it can be shown that having each agent maximize its own averaged Q-function may actually lead to non-convergent behavior. Thus, we need to consider algorithms that update less aggressive manner, e.g. soft Q-learning or policy gradient (which is considered in this paper).
Numerical Results. Due the space limit, numerical performance for algorithms studied this paper are deferred to Appendix A
5 CONCLUSION AND DISCUSSION
This paper studies the optimization landscape and convergence of gradient play for SGs. For general SGs, establish some local convergence results; for MPGs, establish the global convergence and design a sample-based method. There are many future directions. Firstly, the assumption of MPGs relatively strong compared with the notion of potential games the one-shot setup, which might restrict its application to broader settings, More effort would be needed to come up with other special types of SGs which facilitate learning. would also be meaningful from learning in stochastic games to investigate real-life applications, such as dynamic congestion and routing. Secondly, the sample-based learning algorithm proposed in this paper only one choice. Other methods, such as actor-critic, natural policy gradient, Gauss-Newton methods, could also be considered, which might improve the sample complexity. We note in passing that is an interesting and important question to characterize the fundamental complexity of MARL. Thirdly, this paper only considers direct policy parameterization. To broaden the application of MARL and to strengthen the results, other types of parameterization such softmax parameterization and general nonlinear parameterization should be investigated.
combine the insight
REFERENCES
Sherief Abdallah and Victor Lesser. multiagent reinforcement learning algorithm with non-linear dynamics. Journal of Artificial Intelligence Research, 33:521-549, 2008.
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mabajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift, 2020.
Gürdal Arslan and Serdar Yüksel. Decentralized l-leaning for stochastic teams and games. IEEE Transactions on Automatic Control, 62(4):1545-1552 2016.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathernttiaa Journal, Second Series, 19(3):357-367, 1967.
Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan, and Ocan Sankur. Dynamic network conges- tion games. arXiv preprint arXiv:2009. 2020.
Michael Bowling and Manuela Veloso. An analysis of stochastic game theory for multiagent reinforcement learning. Technical report, Carnegie-Mellon Univ Pittsburgh Pa School of Computer Science, 2000.
Michael Bowling and Manuela Veloso. Rational and convergent learning in stochastic games. In International joint conference on artificial intelligence, volume 17, pp. 1021-1026. Citescer, 2001.
Lucian Buçoniu, Robert Babuška, and Bart De Schutter. Multi-agent reinforcement learning: An overview. Innovations in multi-agent systems and upplications-I, pp. 183-221, 2010.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Başar. Communicationnefffiiiien policy gradient methods for distributed reinforcement learning. arXiv preprint arXiv: 181.0338, 2018.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI/IAA,, 1998(746-552):, 1998.
10

---

Under review as a conference paper at ICLR 2022
Vincent P Crawford. Learning behavior and mixed mixed-strategy nash equilibria. Journal of Economic Behavior Organization, 6(1):69-78, 1985.
Fatheme Daneshfar and Hassan Bevrani. Load-frequent control: a ga-based multi-agent reinforce- ment learning. IET generation, transmission & distribution, 4(1):13-26, 2010.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. arXiv preprint 2Xii:2201.042333 2021.
W Davis Dechert and SI O'Donnell. The stochastic lake game: A numerical solution. Journal of Economic Dynamics and Control, 90(9-10):1569-1555 2006.
Jakob N Foerster, Richard Y Chen, Maruan Al-Shedivar, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learing awareness. arXiv preprint arXiv:1709.0433: 2017.
David Sonzälez-Sánchez and Onésimo Mernández-Lerma, Discrete-ting stochastic control and dynamic potential games: the Equaatin approach. Springer Science & Business Media, 2013.
Wassily Hoeffding, Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffdding, pp. 409-426. Springer, 1994.
Junling Hu and Michael P Wellman. Nash q-leariing for general-sum stochastic games. Journal of machine learning research, 1(Nov):1039-1000 2003.
James S Jordan, Three problems in learning mixed-strategy nash equilibria. Games and Economic Behavior, 5(3):368-338) 1993.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Claude Sammut and Achim G. Hoffmann (eds.), Machine Learning, Proceedings of the Nineteenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, July 8-12, 2002, pp. 267-274. Morgan Kaufmann, 2002.
Elon Kohlberg and -ran-Francois Mertens. On the strategic stability of equilibria. Econometrica: Journal of the Econometric Society, pp. 1003-1037, 1986.
Vijay Krishna and Tomas Sjöström. On the convergence of fictitious play. Mathematics of Operations Research, (3(2):479-511) 1998.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning, arXiv preprint 1rXiv:1711.0088: 2017.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient markov potential games. arXiv preprint arXiv:2 106.0/ 0/969, 2021.
David Levhari and Leonard Mirman. The great fish war: An example using dynamic cournot-nash solution. Bell Journal of Economics, 1(1):322-334, 1980.
Yingying Li, Yujie Tang, Runyu Zhang, and Na Li. Distributed reinforcement learning for decentral- ized linear quadratic control: A derivative-free policy optimization approach, 2019.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closs for markov potential games. CoRR, abs/ (bs/0999.00 2018. URL htt.ttt::/aax...o////////
1802. 00899
Eric Mazumdar, Lillian Ratliff, and S Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6820-6829. PMLR, 13-18 Jul 2020.
11

---

Under review as a conference paper at ICLR 2022
David Mguni.
Stochastic potential games. arXiv preprint arXiv:2005.13527, 2020.
David Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang. Learning in nonzero-sum stochastic games with potentials. arXiv preprint arXiv:2103.09284 2021.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-143, 1996.
Liviu Panait and Sean Luke. Cooperative multi-agent learning: The state of the art. Autonomous agents and multi-agent systems, 113):3877-33, 2005.
Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning of localized policies for multi-agent networked systems, 2019.
Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control, pp. 256-266. PMLR, 2020.
S. Shalev-Shwartz, Shaked Shammah, and A. Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. ArXiv, abs/1610.03295, 2016.
S. Shamma and G. Arslan. Dynamic fictitious play, dynamic gradient play, and distributed convergence to nash equilibria. IEEE Transactions Automutic Control, 50(3):312-327, 2005. doi: 10. 20.1109/TAC.2005000 80888888 843878.
Lloyd Shapley. Some topics in two-person games. Advances in game theory, 52:1-29, 1964.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Yoav Shoham, Rob Powers, and Trond Grenager. Multi-agent reinforcement learning: critical survey. Technical report, Technical report, Stanford University, 2003.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with generative model. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31, Curran Asso- ciates, Inc., 2018. URL /tttts::/prroceeeeeee wew.:eeeeeeddn.eeeeeeeeeeeeeeeee neurins..p.... wass.c//pee pctppappe//01///11111 2o02e11feesee22A222eea312225
pdf
Ziang Song, Song Mei. and Yu Bai. When can we learn general-sum markov games with large number of players sample-efficinntly. 2021.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. Conference on Learning Theory. pp. 2803-2830. PMLR, 2019.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. NIPs, volume 99, pp. 1057- 1063. Citeseer, 1999.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning. pp. 330-337, 1993.
Gerald Tesauro. Extending q-learning to general adaptive multi-agent systems. Advances in neural information processing systems, 16:87 1 1-878, 2003.
Eric Van Damme. Stability and perfection of Nash equilibria, volume 339. Springer, 1991.
Deepak A Vidhate and Parag Kulkarn.. Cooperative multi-agent reinforcement learning models (cmrlm) for intelligent traffic control. In 2017 1st International Conference on Intelligent Systems and Information Management (ICISIM), pp. 325-331. IEFE, 2017.
12

---

Under review as a conference paper at ICLR 2022
Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. NIPS' 18, pp. 9672-9683, Red Hook, NY, USA, 2018. Curran Associates Inc.
Weiran Wang and Miguel Á. Carreira-Perpiñar Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. CoRR, abs/ (311.119411) 2013. URL
http://arxix/: org/ /wwpr///////////////// abs /1099 1541
Xu Xu, Youwei Jia, Yan Xu, Zhao Xu, Songjian Chai, and Chun Sing Lai. A multi- renttiaagentriinfrremmmme reinforcement learning- braningg-basddd data-driven method for home energy management. IEEE Transactions on Smart Grid, 1144)33201332 -2211, 2020.
Santiago Zazo, Sergio Valcarcel Macua, Matilde
and Javier Zazo. Dynamic potential games with constraints: Fundamentals and applications in communications. IEEE Transactions on Signal Processing, 64(14):3806-382) 2016.
Chongjie Zhang and Victor Lesser. Multi-agent learning with policy prediction. In Proceedings of the AAAI Conference Artificial Intelligence, volume 24, 2010.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In International Conference on Machine Learning, pp. 5872-5881. PMLR, 2018.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi agettt reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv: 191 10665,, 2019a.
Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges to nash equilibria zero-sum linear quadratic games. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- AAucé-BBuc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., / paper/201 9/ / 4 6 622 7 950 wewee
cC/
A NUMERICAL EXAMPLES
022
0g = 2
$2 =
1
$2 =
01
(-1,-1)
(-3,0)
81
2
0
a1 2
(0.-3)
(-2,-2)
81
1
Table 1: Reward table Game
Table Reward table for Game 2
Game 1: multi-stage prisoner's dilemma The first example- - multi-stage prisoner's dilemma
Arssl(Arslan & Yüksel 2016) studies exact gradient play for general SG settings. It is 2-agent
MDP. with S A1 = A = 1, 2}. Assume that the reward for each agent (s a1 a2), E {1,2)
is independent of state and is given by Table The state transition probability is determined by agents' previous actions:
P( = 1((11,,,22)) = ()) =1 - P(s = (1(,,, a2,1) # (1,1)) =
Here action a; 1 means that agent choose to cooperate and a; means betray. The state serves as noisy indicator, with accuracy 1 of whether both agents cooperated (st = 1) or not
(s; 2) in the previous stage
The single-stage game corresponds to the famous Prisoner's Dilemma, and it is well-known that there is unique NE (01, a2) = (2, 2), where both agent decide to betray. The dilemma arises from the fact that there exists joint non-NE strategy (1, 1) such that both players obtain a higher reward than what they get under the NE. However, in the multi-stage case, the introduction an additional state allows agents to make decisions based on whether they have cooperated before. Intuitively, given that both agents cooperated at the previous stage, it is more beneficial to keep this cooperation rather than destroy it by betraying. It turns out that cooperation that the two agents are patient (i.c., y is close to 1) and that the indicator s is accurate enough (i.e. is close 0). Apart from the fully betray strategy, where both agents will betray regardless of
be achieved in this manner given
13

---

Under review as a conference paper at ICLR 2022
there is another striet NE 4" that is 0;=1,;==1 1, 22 0, where agents will cooperate given that they have cooperated in previous stage, and betray otherwise.
We simulate gradient play for this model and mainly focus the convergence to the cooperative equilibrium 0" The initial policy is set as: 0 0; = 11 0.46,, 0 0==2,0.=1 = 0, where the 5,
are uniformly sampled from [0, 1]. The initialization implies that at the beginning. both agents are willing cooperate to some extent given that they cooperated at the previous stage. Figure [ shows a trial converging to the NE starting from a randomly initialized policy. The size of the region of attraction for l can be reflected by the ratio of convergence ( #Irials that coaverge to 0" for multiple trials #Total number of Irials with different initial points. An empirical estimate of the volume of the region is the convergence ratio times the volume of the uniform sampling area; the larger the ratio, the larger the region of attraction. Table 3 demonstrates the change of the ratio with regard to different values of indicator error e. Intuitively speaking, the more accurately the state 8 represents the cooperation situation of the agents, the less incentive agents will have for betraying when observing A (s=1) will become, and thus the larger the convergence ratio will be. This intuition matches the simulation result as well as the theoretical guarantees on the local convergence around a strict NE in Theorem 2
1, that is, the larger
A (s=1)
ratio (mean + std)%
0.90
0.1
433.3
(47.81 5.1)%
0.9
0.05
979.3
(66.3+ 4.3)%
0.05
0.01
2498.6
(77.4# 2.8)%
0.8
Table 3: (Game 1:)
Relationship of convergence ratio and e.
Here we fix 7 0.95. Convergence ratio is calculated by Irials converge
Ieration steps
Here we calculate one ratio using 100 tri-
# Total member
Figure 1: (Game 1:) Convergence the cooperative NE
als and the mean and standard deviation (std) are calculated by computing the ratio 10 times using different trials. A= 1) is
calculated using Equation (10)
0.8
NE ge (agur baud)
0.0
40
15
10
20
20
32
90
Baralter atagps
alapes
Figure 2: (Game 2:) Starting from a close neighborhood of fully mixed NE
Figure 3: (Game 2:) Total reward for multiple runs
Figure 4: (Game 2:) NE-gap for multiple runs
Game 2: coordination game Our second numerical example studies the empirical performance of exact gradient play for an identical-reward game which special class of Markov potential game. Consider a 2-agent identical reward coordination game problem with state space S = S₁ S2 and action space A A1 x Az, where S₁ S2 = A A {1, 2}. The state transition probability is given by:
P( 1aa = = e, P(s = 1/ar, 2) c. i= 1,2.
The reward table given by Table where agents will only be rewarded if they are in the same state, and state has a higher reward than state 2. Coordination games can be used to model the network effect in economics, where an agent reaps benefits from being in the same network as other agents. For this specific example, there are two networks with different utilities. Agents can observe the occupancy of each network, and take actions to join one of the networks based on the observation.
1-3c There is at least one fully-mixed NE where both agents join network with probability 3(1-2e) regardless of the current occupancy of networks, and there are 13 different strict NEs that can be verified numerically (computation of the NEs as well as detailed settings can be found in Appendix Nj. Figure shows gradient play trajectory whose initial point lies in close neighborhood of the
14

---

Under review as a conference paper at ICLR 2022
mixed NE. As the algorithm progresses, mixed-NE, indicating that the fully-mixed NE is indeed saddle point. This corroborates our finding in Theorem Figure shows the evolution of total reward (( for gradient play for different random initial points (t0 Different initial points converge to one of 13 different strict NEs each with different total reward (some strict NEs with relatively small region of attraction are omitted in the figure). We see total reward is monotonically increasing for each initial point, which makes sense since gradient play runs projected gradient ascent the total reward function J. While the total rewards are different, as shown in Figure we see that the NE-gat gap each trajectory (corresponding same initial points in Figure E converges O. This suggests that the algorithm is indeed able to converge to a NE. Notice that the NE-gaps do not decrease monotonically.
that the trajectory in Figure 2 diverges from the
Figure 5: (Game 3:) State-based coordination game, rewards are nonzero if both players locate the shaded grids
Figure 6: Total reward J((())
keeps increasing
0.4
0.2435
0.0491
0.0185
3/s
0.2501
0.0465
0.0145
0.3
Plaer
0.0475
0.0303
0.0785
36
0.0457
0.0363
0.0744
0.0186
0.0798
0 4344
De
0.0143
0.0734
0.4450
0.1
24
21
Figure 8: NE NE-gap converges a value close zero. Here the NE-gap max, max, (s..))
Player
Player
measured by
Figure 7: Marginal distribution (81.2, s2.a) ) and de ($1.g; 82.2)
Game 3: state-based coordination game Our third numerical example studies the empirical performance the sample-based learning algorithm, Algorithm | Here we consider a generalization of coordination game (Game 2) where the two players now try coordinate on 2D grid. The two-player state-based coordination game on a 3 x 3 grid is defined as follows: the state space is given by S S x S2, S₁ S2- S₂ S, = (Iaa The 2 x {(a yb: Ne). action space is given by A Ai x Az, A A2 = (Stay. Left, Right, Up. Down). i.e., agent can choose to stay at current grid move left/righ/up/down
neighboring grids. We assume that there random noise during the transition; for example, if agent is staying at the middle grid (Ih, Ub), then:
P(s Fal 11, x = Hb, a1 Stay) P( Fe|31,z = Fb, a1 Stay) E,
P( Inh 81. = Jb; a1 Stay) = 12,
P(s = Yal Valsi.y = Tb. Q1 = Stay) = P(si, = Be Se.y = 2b. a1 = Stay) = E,
P(5 = yolss = yb. a1 = Stay) =1 -1-26 2c.
The reward is given by:
= 1(8 82),
82 = (Ia: Ma) or (a):
i.c. the two agents are only rewarded if they stay at the upper-left or lower-right corner at the same time.
For numerical simulation, we take To 300, T 10000, a = 0.1, = 10, e 0.1: the numerical
results are as displayed in Figure 6 g Figure 6 shows that total reward increases as the number of iterations increase, and Figure shows that the NE-gap converges to value close to zero. However, because project the policy to the a-greedy ~ the NE-gap cannot converge exactly zero.
15

---

Under review as a conference paper at ICLR 2022
Figure 7 visualizes the discounted state visitation distribution. To make the visualization more intuitive, look at the marginalized discounted state visitation distribution dg dg defined below:
(81. =2.2==
Σ
do(81.2 $1.01 82.2, 82,v) Bso~p (1
Pr(st.x.1 81, 82,,1 = $2, To)
91 $1,9.92,9
dg (81,)) 22,y)
Σ do(81.x:11, 81,9 82.2, 82,5) = Esp 11) Σ 7 Pr(st.,. f2 #2 T0)
From Figure 7 we can that most of the probability measure concentrates on ((ra: Ta); Fe)) {Was Va), (Wer ). indicating that the two agents are able to coordinate most of the time.
B MORE ABOUT MARKOV POTENTIAL GAMES
This section is dedicated to a more thorough understanding of Markov potential games, which includes necessary or sufficient conditions for MPG and few (counter)examples.
B.1. A necessary condition and counterexamples
Definition (Monderer Shapley (1996)) Define the path in the parameter space as T = (0(0), ((1), .......,.. ((N)), where of, g differ only one component in i.e. g(++1) (0(++1), g A closed path is path such that ((0) g(N), Define:
N
I(T) = (1(() - (0(1-1)))
The following theorem is direct generalization of Theorem 2.8 in Monderer & Shapley (1996) to MPG setting:
Lemma 5. For Markov potential games, [(r) = 0 for any funite closed path T.
Proof.
The proof is quite straightforward from the definition of MPG
I(T) Jr, (B(0)) J1. (o((-1))
= Σ ((((1) - (((((-11)
((0(N)) - (0(0)
0.
Although the proof of Lemma 5 is straightforward, it serves as a useful tool in proving that game a MPG. For example, applying the theorem we can get that the following conditions are not sufficient conditions for MPG.
Proposition 2. None of the following conditions SG necessurily imply that it is MPG:
(1) There exists 0(8, a) such that at each 8, ri(o, a/. a.)) - 1s, a.)) 0bs, a/. a=;) 0(8, 0j, a-i);
(2) There exists ø(s, a) such that for every s, 3, ri(s, a/ - (3,, = 66s, a/, ami) 6(3, as i)
(3) Rewards r; are independent of s, and they have a potential function, i.e. ri(a;, a.;) re(a,, ()))= ((a;,a-) Φ(a/, a):.
16

---

Under review as a conference paper at ICLR 2022
Proof. (of Proposition 2 A simple counterexample showing that the conditions in Equation not sufficient is the multi-stage prisoner's s dilemma (Game 1) introduced in the numerical section (Appendix(A) Since the reward table for multi-stage prisoner's dilemma is the same the one-shot prisoner's dilemma (which known to be a potential game), Game 1 satisfies condition (3) in Proposition 2 which implies condition (2), which in turn implies condition (1). In the following
are going to use Lemma to show that Game I is not MPG. We define the following individual policies:
gDefect
Defect
#1,a; = 0, DDefect
2=2,a;=1 = 0
Coup
Cuop
1, Cump
==1,0,=1
==2,0==1
0g Always.coop
Always_coop s=1,0;=
=1, O
22200
Let:
((0) = (oPefest (Bpoop),
0(1) (ofoop .0
((2) (oeoup Og Ollways coup))
((3) (Opelecs (bhways.ccom
and define path 5 by:
T ( g( _(2), g(3) g(4)), ((4) 8(0)
For the sake of easy calculation, we set c = and set initial state as 80 in Game 1. In this example, is not hard to see that Jr, (0(1)) Jr, (0(t-1)) > 0 for each E {1, 2, 3, 4), implying that
[(r) > O. This indicates that although Game I satisfies condition (3) (as well as conditions (1) and
(2)), still not MPG
B.2. A sufficient condition
Proposition 2 suggests that MPG is a quite restrictive assumption. Even if the reward table for
SG is the same as the reward table of a one-shot potential game, the SG may still not be a MPG. Nevertheless, we can show that the following condition is sufficient for a stochastic game to be MPG
Lemma 6. stochastic game a MPG if condition (1) in Proposition is satisfied and that P(s'|s, a))) P(s'ss).
Proof. P(s'(s,a) a) P(s'(s) implies that the discounted state visitation distribution de does not depend on 0, and thus we denote as d(s) instead. Condition (1) implies that 6(s, as, a-s) ri ai a-)) only depends on and a_; but not a, and so we denote the difference as 6,(s, a.:. ie..
Mls ais a-.) rs as a.:) (s,,a_))))
The total reward of agent can be written as:
(,(0) Σ d(s) To(als)r((ssa))
Σ d(s) Σ no, (arls)
Σ (a-
Similarly, total potential function can be written as:
x(0) Σ d(s) Σ To(cls)o(ssa))
Σ d(s) Σ To (ails) Σ (a (a-1))000)0)
WWe this counterexample to show that some propositions (c.g., Proposition in the arXiv preprint Mguni 2020) would need more consideration since the multi-stage prisoner's 's dilemma satisfies the conditions given in Mggnn 2020).
'The recent arXiv preprint Leonardos al. 2021 has similar characterization.
17

---

Under review as a conference paper at ICLR 2022
Thus,
4(0) J.(0) Σ d(ss) Σ
Te. (ails)
Σ
To (a_:|s) (d(s,,,,,)) r(s 04, a-i))
0i
a-i
Σ d(s) Σ
To. To, (asls)
Σ
To (a__)__s)))((s
01
a-1
Σ d(s) To To_ (a:l)_==)))0
which does not depend parameter 0,, i.e.,
00.) J.(0,, 0-.) 400,, 0-i) --(0;,0-i,, (0,,--),(000--)) EX
which completes the proof.
B.3. MPG with local states and application example
From Proposition 2 we see that it is difficult for a SG to be a MPG even if the game is a potential game each state. Lemma O only presents a very special case where the action does not affect the state, meaning that this MPG is merely a collection of potential games. To provide a MPG which is beyond the identical-intered case and the case in Lemma 6 inspired by the setting in Qu al. 2019) and Macua et al. (2018), here we consider a special multi-agent setting where S = S X X S and S, is the local state space of agent In addition, the transition probability takes the decomposed form, ((s'|s, a) I (( (s, az). The rest of the SG setting is the same as the SG in Section 2 Deviating slightly from the main text, we consider the localized policy where each agent take actions based on its own state,
Te(ae(s))
II Te, (an,els4.) 1=1
with the localized direct parameterization:
TA, (di,)( = 0 (er.a))
0, ((A.))
We use X/local := (AA,)s. to denote the feasibility region of 0,, and the feasibility region of is denoted Plocal := Xlocal .... Xlocaal
Lemma 7. If there is function ((8,a) such that for every agent i, ra(Bi, 8 Uz a-i) 6(s,, 8-s, as a-1) ) + (a(s.,,a-), where 8/ only depends on 8-s, a-s. then this SG is a MPG, i.e., for any parameters (0% (_.), (0,, 0-s) E Plocal, the equation in Definition 3 satisfied.
The proof is straightforward given the local structure of the MDP and the localized policies. This MPG enjoys nontrivial multi-agent application examples such as medium access control (Macua et al. 2018). dynamic congestion control (Bertrand et al. 2020). etc. Below we provide medium access control as one of the examples.
Real application medium access control. We consider the discretized version of the dynamic medium access control game introduced in (Macua al.) (018). where each agent user that tries to transmit data via single transmission medium by injecting power to the wireless network. Each user's goal is to maximize its data rate and battery lifespan. If multiple users transmit at same time, they will interfere with each other and decrease their data rate. Here user i's state is 8; E S, = {0, 1,..., B,,max),, ). which denotes its own battery level, where B,,max is its initial battery level. We
to denote its discharging factor. Its action O; Ar {0, 1,..., Pt.max) denotes the power injected to the network at each time step, where Pi,max is the maximum allowed power. The state transition is deterministic, describing the discharging process of the battery proportional the transmission power, which is given by:
S Si,t 6.a.,..
The stage reward of user is given by:
1
ri(8, a) = log
1+ 1 5p 1/512ag
+ a88;
18

---

Under review as a conference paper at ICLR 2022
where h2 is the random fading channel coefficient for user i.
By noticing that ri(8, a) - log (1 + Σi=1 [/x/Pa;) + a 3i 8, log (1+E, Et |8513a})
a E Ejzs 8j. we can apply Lemma 7 to verify that the medium access control problem indeed a MPG and that the potential function Φ given as:
(() log 1
1hg Pag
84-
C DERIVATION OF EQUATION
18
(CALCULATION OF da)
From the definition dg:
do(s) = Exo~p (1 7) Σ
7 >Ppr - s/s0),
t=0
we have that:
do = (1 - -7) p p p+ 7+ pd p+....
(1 71 7P's 2 )
= (1 - (I - PP)) TT
D PROOF OF LEMMA 2
Proof. According to policy gradient theorem Equation (6)
0J:(0)
do (oo(s))o(a''l) 8 log (a(a'ss))
0 (s)
00,.a;
00,.a,
Since for direct parameterization:
i log (a'd'ss))
1sa; ",,s'' =s} 210sa 0x.a. 2 log nØ. (a(ls))
09 20.a.
00,a.
l1a, si,s' {)
TTP (ails)
Thus we have that:
(J)
ΣΣ do(s') do(ss)=o(d'(s)) ai 5 5) To (as(s)) (s,
80..a.
Σ do(s) de(s)) (al
Q (s, as,
Ta(a:(s)
1
do(s)
[d
1-7
(s(s)
E PROOFS OF LEMMA 3 AND THEOREM 1
Before giving proofs for Lemma and Theorem first introduce the well- well-known the performance difference lemma (Kakade & Langford 2002) in RL literature, which is helpful throughout. proof is also provided for completeness.
19

---

Under review as a conference paper at ICLR 2022
Lemma 8. (Performance difference lemma) For policies no; me.
1
- - J((0)
Bandy Bo (s. i= 1=1,2....,
(22)
Proof. (of performance difference lemma) From Bellman's 's equation we have that:
J:((') J:(0) = Esgep V (so) - Exa V. (sp)
(Ee-p Barp Ban (116) 0% (8, - Esn (())) + V. - EEs (10)
Eaup (8) A (s, (s, Pr V."(s) (s) - v.((s)
BgupBan (1)) (1) (s,
+1 (0= Ba (s)
+ 7 2 8u po (02=
Vi (s)
E (er=)))) 7 A?
1=0
Bo A ())
Proof. (Lemma According to performance difference lemma Equation (2 :
Jr(6%, 0-)) - J,(0,, =
1
Σ
do (s) (cls)
8,0
do (a,(s)
Σ To_ ai a..
(23)
8,0c
Σ 8,04
(a,1s
According to the definition of 'averaged' advantage function:
Σ no. (s) =0, E
which implies:
max A7(s, 2 0, a,EA;;
thus have that:
J, 0-1) J,(0,, 0),) 1 Σ do (a))o
< γ Σ (s) max A8 a:)
a,EA,
(24)
dor(s) do(s) max A7 (s,a,) a,) agE,,
do
de
<
Σ
max A, (())a)). do(s) a.E.
dg
20

---

Under review as a conference paper at ICLR 2022
We rewrite - E. ds(s) max, E.A. (s az) as:
1 Σ (s) max (s,
E do(s)) (a]ls)
max
agEAi
1
U
s.0;
1 Ta. (ails) To, (a:(s))
max
1 do(s) A/ a,)
O,EX;
(25)
1
max O,EX,
TTg (a.l ()
To, (ails))
1- d (s.
max (0; 0.) Jo()) 0.EX.
Substituting this into Equation 14 we may conclude that
dæ
0-.) - 0.),,
max (0, - 0.) - (.))
de
0.Ex:
and this completes the proof.
Proof. (Theorem 1 The definition of a Nash equilibrium naturally implies first-order stationarity, because for any 8; E Xr:
J:((1 - n)03 + n,, 0²,)) J, 0-,) 1y(0, - 0) Vo, + o - 07 0, Vn >
Letting 0 gives the first-order stationary condition:
(0: 0) Vo S
40, E X₁
remains to be shown that all first-order stationary policies are Nash equilibria. From Assumption ! we know that for any pair of parameters ,', 0",
dar dg- 0c
<000.
Take 8' (0% "",,), (07,0) 0";). According Lemma stationary policy 8",
3
we have that for any first-order
de
J,(0', 02.) - 1,00,000) S
max (0. - -0,) Vo, $0. B.EA'
dg.
which completes the proof.
F PROOF OF THEOREM 2 AND LEMMA
Proof. (Lemma 4p For a given strict NE 0* randomly set:
ag (8) E arg max AT" a;),
and set 0; be:
0g.a: fa, = at (s))
And set 0 = (0,00-,) From performance difference lemma Equation 22
J,,0, - -J(0;; = Σ dg (T) ne. (s, a,) (s, (s)
s,a;
Σ (s(s) max A (s, a,) 20
Because 0" is a strict NE, thus the inequality above forces 0: = 0, and that maxo, AgT (s, a;) The uniqueness of 8" also implies uniqueness of (s). and thus,
(s, < 0, a, + a, (s),
which completes the proof of the lemma.
21

---

Under review as a conference paper at ICLR 2022
The proof of Theorem relies the following auxiliary lemma, whose proof we defer to Appendix M
Lemma 9. Let X denote the probability simplex of dimension nt Suppose 0 E X E IR" and that there existy i" E {1, 21.2..... ,., ,n] and A > O such that:
0: 2 Q::
vi + 1
gs- 2 9:
+ A, i
Let
0' = Projx(0 + g),
then:
0, 2 min min (1,0,- 2
Proof. (Theorem D For fixed agent i and state the gradient play (Equation 5 policy 0i,s given by:
update rule of
g(++1) Proja((A.D(0 + 1 1-y doco (s) (f) (s, )),
"
(26)
where A(IA:) denotes the probability simplex in [As|-th dimension and Q (s, )) is |A, -th
dimensional vector with a, element equals to Q (s, a.)). We will show that this update rule satisfies the conditions in Lemma 9
which will then allow to prove that
7
D(0(++1)00 (10)) max D(0 (0))
2
Letting at (s) be the same definition as Equation 9 we have that:
1 daco (s) ( (s, (s))
γ dgco (s)Q (s, (s,
1
>
1 do (s)Q²" (s, (s. (s))
? do (s)Q (s,
1
do- (s)Q (,,0(()))
1 - γ deco (s) (s) (8,
du- (s)Q² (s,0s)
doces (5) (s,
1
do (s)
AA" (T)
A (s, a.))) -2 2// ),(((() (('))(
(27)
1
4
Σ [4,
|10(0) - 0011
(28)
(1 7)3
> 0"
4
Σ |4,1
Σ
Σ
1002 ,11)
(1
7)3
1=1
0
4
S|S|
Σ
1(
7)3
where Equation (27
to Equation (28 uses smoothness property in Lemma 18
We use proof induction as supposed for < - 1, we have:
1 0*
D(0(e+1)1107) < max(D(o(0)00')
2 0}.
thus
n (1 7)3
D(0(0 < 1(
8n|Si EE (A,1)
22

---

Under review as a conference paper at ICLR 2022
Then further conclude that:
(1 7 ddgce (s)QQ²"
(s, (s,a((s)
- -(1 -1dda (s) (s,
21 0
(1 - 7=
4
Σ Aiil 1(0101100))
Va # (8)
2
Additionally, for D(0(0)10*)
M>|s((E.. (A.)) we may conclude:
4" 11-)²
2 1/2 2 s.0.
Va, + (8),
(,07())
then by applying Lemma 9 to Equation 26 we have:
7d0
(,a;(e) 2 min ( (C)
+
(s)
4
07 (1
g(++1)
(.)
7 rr
s max 110 0r,
}.
Vse S, i= = 1,2....,
2
7 0
1(0(++))100))) D(000 100)
2 }
which completes the proof.
G PROOF OF PROPOSITION
Proof. First of all, from the definition of NE, the global maximum of the potential function is NE, We now show that this global maximum is a deterministic policy. From classical results (e.g. (Sutton & Barto 2018)) know that there is optimal deterministic centralized policy
x (a (a1....,aa)1$$ 1aa = a" (8) (a) (o)()))..((..))))
that maximizes:
n arg max E =:A)((A) f=
Σ of (68 oz) 80 =
We now show that this centralized policy can also be represented by direct distributed policy parame- terization. Set 0* as:
Toz (as (s)
1 (a= = (8)}
then:
x" (a|s)
II To; (a,ls)
Since x² globally maximizes the discounted summation of potential function ó among centralized policies, which includes all possible direct distributedly parameterized policies, #* also maximizes the total potential function & globally among all direct distributed parameterization, which completes the proof.
H PROOF OF THEOREM 3
H.1 USEFUL OPTIMIZATION LEMMAS
Lemma 10. Let (8) be smooohh in 6, define gradient mapping:
1 (Projx 1)V4(6)) 0)-
GT = 7
23

---

Under review as a conference paper at ICLR 2022
The update rule for projected gradient is:
0 =
Then:
(0' (0'- 0+) - < (1 (1++) - 0+1l v0' E X.
Proof. By standard property of Euclidean projections onto a convex set, we get that
(0 + - (t) 0
VV (8- pt) 0 -0'0000'-000 V (0' - -0t) S [G* -
7V T(0 - -0t) - (0) -0 00
(T((t)T(0) 8+) [[" ot || (VD(0+)- (=(()) (0'0))))00000000)))))0 -ttI
< [G' 0+| + A|10 011|0' 0+|l
(1++ 0+1
Lemma 11. (Sufficient ascent) Suppose (0) B-smooth. Let 0+ Projx + ( ())) for n S 3.
Then
$(0+) (()) 2 [|)
Proof. From the smoothness property we have that:
((0+)= - (0) 2 (o) - 0) -110 - 0
(29)
Since 0- = Projx(O 7) we have that:
(0 (0+) - -0)) 50 4 E x
take 0' 0, get:
V2(0)) (0+ 0) 2 - 110 0112.
Thus:
((0+) - ((0) 2 (o T (o+ 0)
2 1 - 012
2 _
1
7 | 012
> 2n 10+ 011
G (8)
2
which completes the proof.
Lemma 12. (Corollary of Lemma 11 For ((0) that is 3 smooth and bounded 2min I =(() < + max
running projected gradient ascent:
g(t+1) = Projx + (
with 17 }. will guarantee that:
lim ++x
[["(((())]|| = 0.
Further, have that:
T-1
2 max min
T
Σ
T
(30)
t=0
24

---

Under review as a conference paper at ICLR 2022
Proof. From Lemma 11 we have:
1 |Gm 0
-
z 23
Thus ((((t)) is non decreasing, and since is bounded, we know that ((((0) asymptotically convergence some value t', and thus show that
lim |G"(
Additionally, from Equation 30
T-1
$(D - (
2
Σ
G (D(0)))
2
t=0
T T |G
23
4 pina)
v
max
T
which completes the proof.
H.2 PROOF OF THEOREM
3
Proof. Recall the definition of gradient mapping:
()) = (Projx(0 + (7)( - 0).
From gradient domination property Equation (8) we have that:
(E max 6'E:;
((( (,((((+1), 0((+1))
(00,00111) (1!041100077
(0: - -8(t11) T max
< max 8,EX:
B.Ed
$ M max
(0!-6((-1)
Vo, (g((+1))
8,E
< (1 + m73)
max 110 0 (
E
- M(1 + n1322 /
4M AMV/ST
where the last step follows 100 - 1 $ $2.155 Thus
NE-gaa(p((t1)) x 4M / (
Then from Lemma 12 have that:
lim ([())(()]| =0
lim NE NE- (a)((()) = 0, 100
50000
and that:
|GT(0((1))3= <
23( 1 max $ min)
T
T
t=0
32,3 (
Prax P
NE- NE-gap(((0)3
T
T
t=1
we can get our required bound of if we set:
32 ( ( max
T Puin) < 2
T
25

---

Under review as a conference paper at ICLR 2022
or equivalently
32M 3( max
4 Pmin)]
T
2²
(4 max
2 Pmin)
(aann)|SEE A4
<²(1 - 773
which completes the proof.
I PROOF OF THEOREM 4
Proof. (of the first claim) The proof requires knowledge of Lemma recommend readers to first go through Lerma The lemma immediately leads to the conclusion that strict NE 0* should be deterministic. Let (s), A!" (s). A be the same definition as Equation 99 Equation (TO) respectively.
4 in Section 3 thus we would
For any 0 X. Taylor expansion suggests that:
(0) 200))))))))))))r))) (0- -0-00) V>((0))0000))-)))00>)))))))>>))) o(100 1)
Σ (0. 07) Vo,
Vo, J( o(110 0-
do- (8)AA- (8, (0s,, - -2hag) + +oll0- 0*l))
82
do (s) (8)
Σ
(0s.a, 0% + +(l10 1*
(a)a7(s)
ΣΣ do- (s) (5) - 02 + -0110-0"1)
Σ 10 0f + o(110 0*l))
A
1 0- o(110 1')
Thus for |10 0*|l sufficiently small,
(0) ((8)) 0 holds,
this suggests that strict NEs are strict local maxima. We now show that this also holds vice versa.
Striet local maxima satisfy first-order stationarity by definition, and thus by Theorem I they also NEs, we only need to show that they are strict. We prove by contradiction, suppose that there exists local maximum 0 such that is non-strict NE, i.c., there exists 02 E Xx, 02 o 0ī such that:
(0,, 0- O",,00))
According to Equation 25 and first-order stationarity of 0":
Σ do- (s) max AT" (s, a.) = max (0: 0;) Vo, s 0. 0.EX.
e.E.
Since max (8 a.) 2 for all 0, we may conclude:
max A (s, 0, V a,EAA;
We denote 6' = (6', 0. ), according to Equation 23
0= 1,(0%, 0²,)) 1,(07,02)
Σ do (5) T) (d:
(s, S 0.
9,0s
26

---

Under review as a conference paper at ICLR 2022
Since der 0, V s, this further implies that
Σ
To (a: [s] (s,a;) =0, VsES,
ie., (a:(s) is nonzero only AT (s, a:) = 0. Define 02 == n00 + (1 - n))07 then
Σ Top (a: (s)(as))) =0, V
(s,
Thus let 8 : (";)
J.(07,02
10000001
Σ des (a)ls) (8,a;) 0.
Since 1000 - 0:11 + 0 as 17- + 0, this contradicts the assumption that 0 is strict local maximum. This suggests that all strict local maxima are strict NEs, which completes the proof.
Proof. (of the second claim) First, we define the corresponding value function, Q-function and advantage function for potential function Φ
(s) = E
y 00000
(x( = 7 (8), u+)
x == 0,80 8, 00 =
(s (2(0,a) a) (s).
For index set I C {1,2,... . n) define the following averaged advantage potential function of index set I as:
A (2, Σ (0
a
We choose an index set I C 1,....... n such that there exists s" at such that:
1 1 , 0,
(31)
and that for any other index I' with smaller cardinality:
A (s, ar) I 0, Vsar,, A II' < [Z]
(32)
Because & is not a constant, this guarantees the existence such an index set I. Further, since
Σ Toz (ar (s) A) 0. (s, (s,ar: = 0. Vs.
and that 0 is fully-mixed, we have that:
(5 (s. ar) Vs,ar, VZ' [Z].
(33)
We set = (0z, 0zz), where 0r a convex combination of 0 0/ E X::
0r (1 0) n10 r >
According to performance difference lemma Equation (2) we have:
(1 (1) (0((zz)0'z) 4007, 0 z))
Σ de(s) (az A
8,a7
dd(( II ((1 - To: (ai1s) + mo (ails)) (8, az)
8,ay
iEI
Σ do(s) ((1 ((1-1)m0;; (ai. + syTee (0:als))
II
((1 ((1-))=o (asls) nTTe(asls)) (8,((,, (Vio E
5,r
vEIifio)
27

---

Under review as a conference paper at ICLR 2022
(1 11) Σ do(s) II ((1 (11-1) ( (a=o(()))))) A 2I (z>(60))
5,42
(EI(Ba)
+ do (aigls)
II (11- (m A (3, a7).
8,02
VETV(io)
According to Equation 33 we know that:
A 2 (5, (2it1o)) 0,
thus
(1 7) (0(0r, 0)
$ Φ 0--)) =
" Σ ( (s))
II (ET)
((1 - T)) (ails) + )T (8,
9,07
Applying similar procedures recursively and using the fact that:
A (s, O, ViEZ.
we get:
Φ(0,, 0-1) 2002
Σ 8,07
de II
To; (a: ( (5, (s,az).
iEI
Set Toy (a:ls) as:
a; = ag otherwise
To (a:
T (a: = Toz
(as (s)
s s s'
where s", az are defined in Equation
31
Then:
|Z|
((0,,0"z) 4 ( 02z)
1-7 do do ( (s" ,az) > 0,
which completes the proof.
J BOUNDING THE GRADIENT ESTIMATION ERROR OF ALGORITHM
The accuracy of gradient estimation is essential in the sample-based algorithm | this section, we will give a high probability bound of the estimation error, which is stated in the following theorem: Theorem 6. (Error bound for gradient estimation) Assume that the stochastic game that satisfies Assumption 3 In Algorithm for
32-(1 + 8 E, |4 max; |Al2 log
(16TT|/S/< E, (di1) (dil) +1,
(1 202200003
8
with probability at least 1- we have:
(0(()))) ( l12 cg. VO To 1
The proof of the theorem includes bounding the estimation error of Q J.1 and de J.2 Let's first
introduce the definition of "sufficient exploration' which going to play an important role in this section.
In the main text Assumption we have introduced (T.oos)-ufffciien exploration on states. In this section we introduce similar definition (T, -sufffciie exploration:
Definition 6. ((T, a -uffficient Exploration) A stochastic game and policy is said satisfy (r, (T,o))-sa -uufficcin exploration condition if there exists positive integer and a E (0, 1) such that for policy 0 and any initial state-action pair (s, ax), Vi, we have
Pr(st, Gj 150 5, ag = a) 2 a, Vs,, ai,r
Note that "(r, -ufffiicien exploration' is stronger condition compared with '(T, -suffficcnn exploration on states'. Additionally it not hard verify that for any stochastic game that satisfies (T, -ss-sfffiicient exploration states, and any 0 E x it will also satisfy (T, max, [2, ) -sufficiiet exploration condition.
28

---

Under review as a conference paper at ICLR 2022
J.1 BOUNDING THE ESTIMATION ERROR OF THE AVERAGED Q FUNCTION
We first state the main theorem in this subsection:
Theorem 7. (Estimation error of averaged Q Q-functions) Assume that the stochastic game with policy
O satisfies (a, -ssfficccennt exploration condition (Definition O) then for fixed running Algorithm
7 will guarantee that:
(1-7))2011
Pr (10 - -o 20) <4T|5| exp
32/5/2
further:
[11-)) [
[
Pr (1Q - 2f 2e, 31) s 8T|S1
Σ [Ail exp
32/S/2
i.e., when
S
ST E, (Aiil)
Ty 2 (1 - 22 log
+
8
with probability at least 1 - 6, 10 0 00 Sc Vi
In the following, we will introduce some lemmas which will play an important role in bounding the estimation eтror of the averaged-O Q function:
Lemma 13. Assume that the stochastic game with policy 0 satisfies (suffiiiti exploration condition (Definition (), then fix s', a;for e $1, 1,
2002 I
Pr (P(5ss) Ps(ssss,a)) 2 S 4T exp
32
Proof. According to the definition of P., we have that
pl ( a:) - (5'1s,, ax) 2
11s141= = s', s =, = a.} - (P +c)1{s= = s,a,, =ait) 20
1/s: s, 8, =a] ]
88T4m =; 0. S ar) (PF +e)1(skrtm 8, 8, = =ai) 2 o
-
1fskt+m41 5
20
m=0
T-1-m
1 1s = =s, s, = aa)==0 =0
m==0
k=0
Let:
T-1-m
Am
1[8k44441 -,,
=a (P! + +c)1(Skr4H) = a,, =a;1) 2 20
T-1-m
4/m :
1 18krtm = =8,0i,h7tm = =a, =0
k=0
Xam 1sskT+m+ 5 8kr8kr = =,,0 ar} (P (ss'sss +c]1(skr+m s3 =,,0 =o.
X Xkm 1 1/skrtm 8, ai,kktmm aa;)
29

---

Under review as a conference paper at ICLR 2022
Yk,m
Xkm
B[X k.m (k- 1y
X Kmm
E[X kmm (k- 1yr+m!
[-1-
Then (Yk.m
} k==
is martingale difference sequence. Because S 1, it is easy to verify that
[x 2, X
k.m I We have that:
[Yrml [m
B || [
S 4, [ S [ + 1 1(( 2.
Further,
I = am = 20
and that
[[ F (]=-1)++m]
B[1{5kr+m41 8', 8kr4m 5, a.) (P,(('))) +e)l 58, 5, ((-
(34)
= -,0 5,, = (() S -E0.
(35)
To move from equation 34
to equation 35 we used the fact that:
[[1(1 s', St 8, am
P(s|st-1, -
P( To, (ails)
Te_ [a
a-
P(sls-11441170
(s,
E[ a: as) 8, - a:
and the inequality in equation 335
is derived directly from Definition
According to Azuma-Hoeffding inequality
(Hoefiding
1994
Azuma 1967
T-
Pr(Am) = Pr
Σ
X 2 0
k=
1-1-m
T-1-m
Pr
Yum 2
E[Xe,m F(k 1)
k=U
7-1-m
T
m
Pr
Y Yum
60
T
k=U
20² 2
T
exp
32
Similarly, from Hoeff-iggg inequality,
T-1-m
Pr(A'm) Pr
X =
7-1-m
T-1-m
Pr
Yo
E.X, k.m
F(x 1)
k=0
k=
T-I-m
m + T
Pr
km <
k=n
30

---

Under review as a conference paper at ICLR 2022
0²
S exp
(36)
Thus
r-1
Pr
P (s
(P
20) 1
Σ
Pr (Am) Pr (A
G002 [1]
o² [
[7]
Texp
Texp
2T exp
32
32
Similarly
200 1
Pr P. (5'1s, -P?(s'(s, S 50) $ 2T exp
32
2002 [
= Pr Pr (s((s,)))
s, (s 20) E 4T exp
exp
32
which completes the proof.
Lemma 14. Assume that the stochastic game with policy satisfies (a, -suffiicent exploration condition (Definition 6), then fix s' as for 1,
2021
Pr (s, (l)) -((,,aa)) 20) < 4r 4xexp
Proof. The proof is similar to Lemma 13
7 (s, (4) (8, }
1/ = s, Ui,t = a.fri(se: ar) - (s, az) +6)1(0; = 8, = =,a.=a)20f
1/s: = a, =a]== 0
1=0
C -0'
1 8, am = asJra(kkrtm akr+m) (rf()) + {e)1( 0i,krtm = az) 20
kmm
18br4m = a, aij
m0=0
Let:
Am
185rtm 8, ai (Kr (s)(), [)](skrmm -8, = =a] 20
k=O
T----
A'm
18kTtm = 8,0,,krtm = a: =0 a=)=
Xk.m = 1(8kT+m 8, di.krtm = ai.ri(shrtmm (0rr(())tmmmkrtmm)) - (r,( + ( 8, 0,0kkrm 0.3)
Yr.m = Xkm E[X F((-
Then (Ymm)) [-1-m| is martingale difference sequence. Because 1, it is easy to verify that
[ 2. We have that:
Ykml 5 [Nam E([XR, || (1-4mmm 5
31

---

Under review as a conference paper at ICLR 2022
Further,
E[X ((k-1)++m)
[ 5kr+mm 8, am.br+m = 0k:
akr )m) (r, (s, ai) +) (5kr+m ai,br+m = (1)
=-cl[1 (skrtm 0i,kr+m a;) (x-1)))m S -co
the second line to the third line the equation is derived by the fact that:
[s = ai = a, (rsr (x)l = (t-1 0t-1)
Σ
a_
P(s 11.1, 04 (a, (1
= =Elr as, = s, a, a
and the inequality in the third line is derived directly from Definition According to Azuma-Hoeffding inequality:
Pr(Am) Pr
X 2 0
I
T m1
= Pr
Ykm 2
E[Xx.m FF ((-1))mmm)
k=
k=
I
T - m +
Pr
Yum
k=
o002 T
exp
32
Same as Equation (36). we have that:
0²
T
Pr(AA)) S exp
8
Thus
2022 I
Pr - <
Σ
Pr (Am) + (A'm) s 2T exp
32
772
Similarly
20²
Pr (((s,))) -c) 5 -2)s2rexp
LT
32
200 T
Prr - (s, - 26) s 4
32
which completes the proof.
Lemma B and 14 lead to the following corollary:
Corollary 1.
2002 [
Pr[I|Mp - MM loo 2 5 441 exp
(37)
82|
202
Pr[1 - 1 2 5T exp
(38)
32
32

---

Under review as a conference paper at ICLR 2022
Proof. We first prove Equation (37
M, 30
max
To (a/1s")
-P
(e,0.) (s
( a:) Pss(ss))))))
max (e,0.)
Thus,
{ [ Mf 2 2
(G((0,) - -P(''ss))) 26
U
(v.a.)
c
C u U (e,a.) o'
2
[8]
Then according to Lemma 13
Pr (IMM - My 26) s Σ Pr (PP((1ssaa)-P((((lss
PM
2
e
[
(0',8,02)
1.021
S |41|S?|Able exp
-32/S1
Now prove Equation 38 Since
IIr - of 2) (s.0))
U {1:((s,.a) (
- (s) 20]. [
according to Lemma 14
Pr [1r? - 10 2 S Σ Pr
{
20)
(s,as)
2022
< 4r|S||Aii|ex) exp
32
which completes the proof of the corollary.
We are now ready to prove Theorem 7
Proof. (of Theorem From the definition of Q7 Q
Of (1 7M,) 170
O (I - -179.
we have that
11 - 11 = (I 7M -17 - (1 - 7MP) -17
(I M -1 (p? - - + ((I (II ( 11 - 19
< [1 - TM 1 (r? - ক + +1|2(1 - +||(11-2M13 MM) 100(-((() (M M - -M 17
Because both M and M are transition probability matrices, thus:
1l $ ||0||00
| x: 1ox0 S ||0||0c
1
I[T->M0) -2o100 S
1 1-7 ||
33

---

Under review as a conference paper at ICLR 2022
II - ( -10M)))-1111
1 1-7 100
Thus,
1 0. 1 (1 MM
(1? r
+ | [ - - - ~M -1,7
1 - 1|r 1
1
7
M -M 11 |1
+
(1 - 7)
1
||? 1
+
?
MP MoIls 1r
- 7)2
Thus if
11? :2 S (1 77, M 1 (1-
we have that:
1[ - 0. l00 Sc
Thus from Corollary 0
Pr (1@² - 2. 20) < Pr (1r? - -: 2 (1 - -))3E) + Pr (IM - M 21 (1-))
(1- (1-7))020213
(11-7))460PL)
< 4T|5||A:| exp
+4115/1A,1exp
32
32|S|2
(11 - 21=2))
I 88|()/2AA||o cxp
32/S|2
which completes the proof.
J.2 BOUNDING THE ESTIMATION ERROR OF dg
We first state our main result:
Theorem 8. (Estimation error of de) Under Assumption 3
(1 (1- 71--))2033 [
Pr (lão dell1 26) 4T|s/eexpp
32>218122
i.e., when
S2
log |T|S|/2
T> (1 2)
+ 1,
with probability at least 1 1 5, l|de d Sc
Similar to the previous section, the proof of the theorem begins by bounding the estimation error (s'(s (s)(ss))
Lemma 15. Under Assumption 3 fix 8', s,urfore S 1,
Pr Pg(dd(s) ()((s()))))))) 2() 54
32
Proof. According to the definition of PS, have that
P (S(('ls) - Ps((')s)2
st) 0 =0
T-1
Σ (1(9011 = 5' =3 -Pg + +e)1(s
U Σ
1 (lo==))-0
0=0
0=
34

---

Under review as a conference paper at ICLR 2022
18kr+m++1 88br-m =8] (P +c)1(8krTm = =0]) =0)20
C
m=0
0=
7-1
1 1 =
k=U
Let:
Am =-
18kk++++1 = 8kr4m ,86krm =s} - (PS(''ls) (shhr - =s]) 20
km
[-ll=
A'm
1fskr+m= = 53 =0
Xkm = 1(skr+m4H = 8 Skr = (Ps((s))) + {s)1( = =
X = 1(skrtm =
Yem = Xpm - 1| 11r+m)
Vk = km - E1X k. F(k-1)r+ml 1)r+ml
[---=] is martingale difference sequence. Because 1, it is easy to verify that
Then (Yr.m) kk=0
[X S 22 [x.ml S We have that:
|Yuml S X - E[ X | (1-1))++m] S 4, |Y,,ml S 1X)mml + ElIxk,m 1) S 2.
Further,
E[X mL (( (skr (( 2 20,
and that
B[X k.m F(k-1)r+m)
(s = S = = (P (5krrm = (F = - (8krtm = =}1 S -c0s
the second line to the third line of the equation is derived by the fact that:
[|1(1 8',8t = F[-]] P(s|5t11, 1) Σ P(s'ls)
P(s|st-1, 0g PS (s'1s)
([P 8) s) F
and the inequality the third line is derived directly from Assumption 3 According to Ezuma-Hoeffüde inequality:
Pr(Am) = Pr
X 2
k=U
T-1-m
T-I-m
= Pr
Yum 2
E E F(R 17
R=
k=
T l m
- m +
< Pr
Ykm
cos
k=0
2
< exp
7
32
35

---

Under review as a conference paper at ICLR 2022
Similarly, from Azuma-Hoeffding inequality,
T-1-m
Pr(A'm) = Pr
X k,m
0
k=U
7=1-m
T-
Pr
Y
B|x k.m
F( lyr+ml
k=0
k=0
T
0S m
< Pr
Kkm
T
2 I
S
S exp
Thus
Pr (s(('ss) - (s 26) S
Σ
Pr (Am) + Pr (A'))
m=0
2003 2
O'S [
200 [T]
I Teep
+ + exp
< 2T exp
32
8
32
Similarly
e03 f
Pr (P - ps((s(ss S -e) S 2T exp
32
eO'ss T
= Pr (P)((1())))) Pg(()s)) 20) s
( exep
32
which completes the proof.
Corollary 2.
20
Pr
pg
26) s 47|S|2 pg
exp
32
(39)
Proof.
ps
P5
max Σ
Po(('ls)) Pss()'ss)
Thus,
{1
pd 2 =U Σ
Pg(s'ls) - P3(61(5) 26
[S(('((s) Pg((s(ss N c
cuy 88'
[S)
Then according Lemma 13
Pr (1 pg pg
20 5 Σ Pr
p (s'1s) - (
[s]
(s),5)
203 -1
< 4T| exp
S2
which completes the proof of the corollary.
36

---

Under review as a conference paper at ICLR 2022
Proof. (Proof of Theorem 8)
I|dg - dell1 = (1 - -?>ll (11-728) T) -1 - 1 (1
)
Lll
5 7)
[ -1- Pp
Illll
- pp? (1-D "| llplla
S (1 7)
|1( (1- 7/
p p3) ( (1- -1
> 7)
PS PS
?
Thus
Pr (lāo doll2 2c) s Pr
(1188- P53
2 1 1-7 ))
7
s 4r|5/ exp (-(1
(111-))2003 +
22203
32,21012
J.3 PROOF OF THEOREM 6
Proof. Since the stochastic game satisfies (T, (r.as)) exploration on states, then for any ads
E X², we know that it satisfies (T, max; [A.
exploration............ Substitute this into Theorem 7
we have that for
2 32T(1 + + E; [4 max; |A,1
log [16710)SP2,1111
(41) + +1,
(40)
(1
200
8
with probability at least
8
22a
(1 7)
l|Q
QoCki
1x S
(1 (1+ [8] E, Aiil
Similarly, applying Theorem g we have that with probability at least
5 2Ta"
(1 22paaa
||dg0s dowws 111 S (1 (1+a)/is1 SIE,
Since:
[v) - (T(()] (s,as)
1 do (s, a.) 1
1-7 (s) a:)
1
do(s) (s, a.) 29 (s,)
+
1-7 1 (s. (d)o(s)) - -o(())
1
1
(1(s,a)) - Q (x)a:)] +
(1 (1- (du(s) - do(s)
Eg
(1 a1+ / | |4, (1 a1+ / E,,,,,4 |Ag
Cg
VIS) E, Asl
Thus, with probability 1-8
2
()((0() - (0000))113
Σ
(-00)-$000))
Se VisksTo
(s,0z)
4,
37

---

Under review as a conference paper at ICLR 2022
K
PROOF OF THEOREM 5
Notations: We define the following variables that will be useful in the analysis:
(o) = = " P - -0)
(0) = (0 0)
K.1
OPTIMIZATION LEMMAS
Lemma 16. (Sufficient ascent) Suppose (00) is 3-smooth. Let o Projx (0 10++n)0 1) Then for 1 S 2B
((0)) (0) 2 2 10)-00001----- 7 [ -
Proof.
From the smoothness property we have that:
$(0+) - (()) N
(0+ -0) 001
Since 0 = Projx (0 + (b))) we have that:
(0 (0) -+) - 50, 0 E x
take 0' we get:
F0)(0) 0)
-) 2 1 011
11
Thus:
V (o+ 0) (V)()) (Φ( (0+ 0) + (ot - 0)
" V2(0) )
1
110+ - 01l + (2) - 0)
2
2n
2 7
( 2
1
100 0l
10 011
+ "
2
2n
10+ - 01l ! (2 - 60(
2n
Thus from equation 29):
8
" [o - {
((+) +(0)= 2
10+ 011
2n 2
2
1
10+ 0|l
"/
(4(0) |
47
2
I a (0)1
-
7 V2(0) - -
which completes the proof.
Lemma 16 immediately results in the following corollary:
Corollary 3. (of Lemma 16 In Algorithm i suppose (O(K)) - V S eg holds for
every 0 < k < To 1, then running algorithm 7
will guarantee that:
Ta-1
4( pmin)
Σ
(0())))
+ 2c
TG
nTc
38

---

Under review as a conference paper at ICLR 2022
Proof. From Lemma 16 we have that:
(((k+))) 2((())
2 2 T (010)))
"
(o(k))) 2
2
4
Thus
Ta
(Q 4($() - ((((Te)))
22
TG
nTe
4( max
2 pmii)
+26
1/C
Lemma 17. (First-order stationarity and (0)))(())) Suppose ((0) is B-smooth. Let 0+
Projx- (0 ())). Then:
( s + (1+ - 10' 10'-0+11,
A0' E x2. (41)
Further:
max Vo, 1(0+)(()TT)))))) DEE
(0:-0t) s (o::((0)T(0:007)) (1
2a + +0) -
(42)
1-7
Proof.
Since 0+ = Projx ( + we have:
(0 + 7))) 0 (0' 0+) 50
(0) (0' (0'-0*) < (0-00) -0t) 0+)
())(0) -0'-=0+)=== < (0 (0-0t)
(00)) (4())) (0' 0t)
- " (0-0t)) -0000000---000 (V9(0) (D(O)) 10' - -0)
0t)
+1(4((0)) - (0'-0)
" -0 (t0 < (10-00' -000001++/0000 66(0)) + /// (0(0))) 0+1
S (l10 100-0+1+>/0000 ( + 1 - 01)) 0+
(1 11)11 0t (0) { 110 -011
vo(0t)T(0'' -0'-00)))))) 7 (1 n1n 10 (0) ( E 110 @+1|
which proves equation 41
We now prove equation 42 For any oi E A(IA.)), we know that
(1 a)0 + AUiA E (IA,)). Let U, U -.. UAA then for any 6f E X, a)
|(tttimes
aU: E X."
Thus:
Vo, (T00) -+) <
+ Vo,0(0+)T(0) -l-a0)0/---0 aUi)
< (1 [1 + - v2(01]] ||(1 a)0; +000%++0 +al; 0+
( -1-- -1)) -UU)
< 22/15) S
(1 + n1 n1)1 + (() V D(Ot) (0, U.)
Since
Ve, 0(0))) - -U,) = Σ dols) (0/.0 - U(Ai)
39

---

Under review as a conference paper at ICLR 2022
(o, 10',00 U1A,1l1
2
$ Σ ds(s)
1-7
1 1-7
we have that:
Vo, -0) 22//8| (1 + (00] -V0))
2a
+ 1-7
K.2 PROOF OF THEOREM
Proof. Recall that 4 is 3-smooth with B (1-7}3 (Ei=1 (Al)) The step size 17 in Theorem
satisfies 77 S 4 - |A 2
(1-7)s
Recall from gradient domination property:
(
max J, ((++1)) - -.(0(tt2), ol(t1) OEE;
< M max (0'; 0g )(htt) Va. (1(+t2))
EEE,
Suppose || (Q(()()) - co. 6A S To 1, recall from Lemma 17
NE-gap(O(ktt) & max NEX (f(++))))) - M max max (8, - 180-- 1) Vo. ((al+t1) 0iEX.
20.M
s 2M (1 + m/3) 16 ( + cg) + 1-7
Thus,
1 Te -1
4a2
NE (00
<
Σ
3 x
+ LM711(((++33(10000000) + +
To
To
(1 7)2
k=0
k=0
12
Te-1 To
12M2|8 +
12M/2 n13)
i (B(
(1-
k=
From Corollary
3
we have that
Tc
12
(4( pmin) 2c
NE 1E-gap(0(++1)) < 12
12M + n/9)
Ta
71-
nIaa
0=0
12a M2
108M2|S](
max miin)
< 66MMS/
(43)
(1 (1-7)2
TTC
Substitute
(1 7)
6M
fg
2/ 3333MM/1 V
c
and To 2
648
max
ne²
T Pmin) |
into the above inequality we get that:
Te-1
2
2
2
NE-
<
2
Tc O=0
2
3
6
Substitute the value of 6g in Equation
43 into Theorem 6
will give us:
20 max; 1 log
16TI' S| Σ,
|Ail]
T3
+1
(1 - 716
8
which completes the proof.
40

---

Under review as a conference paper at ICLR 2022
L SMOOTHNESS
Lemma 18. (Smoothness for Direct Distributed Parameterization) Assume that 0 S Vs, a, 1,2,.... n, then:
ri(ssa) 5
2
110(0") s(O))l <
Σ Ael 110 -01,
(44)
(1 - 7)3
where g(0) = (V,
The proof of Lemma 18 depends on the following lemma: Lemma 19.
Ve. J(0) ((0)l
A
v /Ayllo, 0y1
(45)
71-
(1
==1
Lemma 18 simple corollary Lemma
19
Proof. (Proof of Lemma
18)
l19(0)) - -(0)11²
(o.)((0) (.0]11
i=1
Σ |A
Σ
V 1 - 02ll
(1 -1-18 11-7)3
Σ |AI
|4ji
Σ 110 0,1
(1 7)3
J=1
j=1
2 (1 7)3
Σ Mil)
110' 0112
which completes the proof.
Lemma 19 is equivalent to the following lemma:
Lemma 20.
(J,(0% + ars, 0',,) (0, + cru, 0.))
< (1 (1-7)3
V A. Σ v
AA11110
-0yll.
V|uu|| =
da
(46)
Proof. (Lemma 20
Define:
(a:ls) = TB (ai(s) = 0s,a; + O'lag'
(a,(s) = Tú tar; (a, (s) 8',n; + a'llay.
(als) : na,+au, (a, (S) (a_s(s)
T', (alss) : tau, (a, (4:18)) (s) (s_s
0 (s, a) = Q(0.tau, (8, a)
d, (x) :- tam
According to cost difference lemma,
OJ, + au, 8¹,) (8, + aw;; 8_1)
da
41

---

Under review as a conference paper at ICLR 2022
1
0 E.,o do (s))) da
1 1-7
θ Enn do (s) To (1
1-7
da
1
Σ (s) On's (als) (1ls) - t (als)
Qa (s. a)
1 y
da
Part A
Σ (( mo(als)) 8Q a)
+
da
Part
(+)
(Fr((a)s) - (s(
da
a==0
5,6
C.
Thus:
iT @Ta(aas) - Ona (als)
Part
Σ
dg((s)
(s,
da
a=0
8,a
Σ (s))uas, (a_1ls) TO_ (a:ss))
(47)
8.0
1
Σ (s)
Uaaes Σ To. (a_ils) To_
(48)
1 7
1
max
|uayol Σ dlo()) (6(5))dr((Torr(1)))ll))) (15))
(49)
1
7
max
|uanss
Σ do((s)
2drv (TTO (-1s)][ (-1s)
(50)
7
a2
1
max
Σ ds(s)) Σ
110 03.
(51)
J
A
do
V 14i1110s, 0z,ell
(52)
A
V |4,
Σ dor (s)2 - 110/ 02.0
(53)
A
|4,
v
Σ do (5)2110' -051l
1
A.
A111,, 05l1
<
A;
V |Ai1110 - 111b
1=1
42

---

Under review as a conference paper at ICLR 2022
where Equation 47) to Equation 488) is derived from the fact that (s, S r- Equation (49)
to Equation (50) relies the property of total variation distance:
dIv(TTo (+ss) Te_. (+1s) S
Σ jØt
dIv(Too (=1s)ll=e, (-1s))
Equation
51
Equation
(2) is derived from:
max
|ua.s S vlAil: ||a|| S 1
16/,- 0galla S V |Ayllll',, - -8,.el
which can be immediately verified by applying Cauchy-Schwarz inequality.
Before looking into Part B, we first define P(a) as the state-action under ma:
[((a)] (s,a)+ na (a' (((
Then we have that:
aP(()
(o
da
a=0
(2,0)
For an arbitrary vector
@P((a)
Σ
On
a=0
(s,a)
e'.a'
S ||
Σ
Ma (d'
st,at
||>||>
Σ
P(s'ss,0) a) Σ |uatior Σ
To_ (a<<
S || E P(5')s,a)VIA) Σ
no (a'el')))))
S v Ailllolloo
Thus:
OP(a)
S |x
da
[s.a]
Similarly we can define P(a)) as the state-action under Tha and can easily check that
TaP(a)
S v 1
da
(8.0)
Define:
((a) = (1- (1=7P(a)) Alaa (1-
Because:
M(a) (I-)P(a))
P(()),
==
which implies that every entry of (a) is nonnegative and M(a) + 1, this implics:
1
Maax S 1-
| |01lo00
43

---

Under review as a conference paper at ICLR 2022
and similarly
[M(a)' S 1 - y 1101/00
Now we are ready to bound Part B. Because:
(s) = e (a)mi
M
(s.(0) = =[(aa) OM(a)
aP(a) M(a)r;
rs = TeTo Te
da
da
da
(s,
1 M(a) aP(a) M(a)r; da
da
? S (1 -- VlAi
Thus,
- (((())))))))m((()))))))))))))))) (5,
Part B
da
a==0
8,a
2 Σ ds(s) (als)) - [ (s.
da
0,0
7
Ac Σ (o) (1
5 (1 7)2
I (1 7)2
Ai
Ed((s) (s)s) Σ (TT
(-Is)]lme, ( (-1s)
(1 7)2 vlAi
?
Σ (s) Σ 110/ - 0g.0112
$
(1- 7)2 vI4
Σ (ssss
|Ag AAblll0y, - -ss.all
y=1
$ (1 7)2
ViAi
ViAAh, /
Σ ()())) V
Σ 110 -2
1=1
(1 7)² vTA
Σ
V1411100-- - 0,l -011
==1
Now let's look at Part C:
da(s) = (1 77) Σ m(6') Σ Te M(a) Σ ((s/ar)
a"
(8) (1 77)
Onla (a'lsa
Ep(s') Σ
da Eso M(a)' Σ ((saar))
da
aM(aY + EE((5] p(s)) Σ (a''s''')
Σ ((saa))
da
-(1- u0 M(a) + Tut M(a) M(a)) M(ay)
OP(a)
Σ ((sa"))
da
am
44

---

Under review as a conference paper at ICLR 2022
Note that 01, U2 are constant vectors that are independent of the choice of Additionally:
Ozla (als) ((x,a) da
|
Σ p(s)
On's (a((( da
Σ p(s) Σ
Ep(s)
Σ p(s)
|uacel Toy (a_sls)
$ Σ p(s) Σ
|Manell S Vldl
5
a
|122l1 Σ ((s) Σ (((a)))
=Σ p(s) Σ
T'a (als) =1
Thus:
Od
Part C =
Σ
- (o((s))))((
Ox
a=0
5,0
PP(a) M(O)
= -(1-))
17 (O0 + yoo (0y
ΣΣ (To(a))))- (
Oox
a==
3ia
1 |elllllesslo + (1 (1-3)3 v V1Aill /1lillollllllallls))
S (1 - 7)
As
$ 1-7
|103
Additionally:
[1s] (00,00)) =
Σ (also) - (s0als a)
Σ (al(s))))) [a(looo)
2d ( ((=0s]]([(-(so)))
2dTV (oTv((TO))) (Tog (+150)] (-1s0)
10' 03,011
| 14,111025 - -3,all
VIA,1110 - 0,11
Combining the above inequalities we get:
VAA
A n 7)² 1=1
Σ VIAI110 0,1
Part C <
1-7
(1
45

---

Under review as a conference paper at ICLR 2022
Sum up Part A-C get:
ÖJ. + 004, 0'-i)= (J: + 004, 8-i)
< 7
(Part A + Part B + Part C)
da
2
V VIAi A4
Σ
n
V VAill10 05ll,
(1 - 7)3
j=1
which completes the proof.
M AUXILIARY
We recall Lemma 9
Lemma 9. Let X denote the probability simplex of dimension n. Suppose 0 E X,9 E RR" and that there exists i" E (1,2....., and A > such that:
0:- 0,.
vi i
9:- 2 + A, ,i r.
Let
0' = Projx(( + gg,
then:
8,- 2 min min (1,0,- + A
Proof. Let y = +++00 g. without loss of generality, assume that 1" and that: > 1/2 2 ys 2 ... 2 yn-
Using KKT condition, can derive an efficient algorithm for solving Projx(y) (Wang & Carreira Perpiñán 2013), which consists of the following steps:
1. Find p == max sjsn: Uo (1 Ui) 0}:
2. Set A = 1, (1 - Ei= vi)):
3. Set 0g = max + 03.
From the algorithm, we have that:
8
0
1
Σ
y1
(0. + gi)
8
i=1
1=1
1
p
1
1
0
91
gs.
If 2 2,
1 p
0f max + +1,03 211 + 01 + 91
9i
P
2 01 (1
1 )91
1
Σ
P
(0)
A) 0
p
1
A
0
A 2
0 1=2
If pf 1,
0f = 11 + 31 +
91) 1
Thus:
A 2
0 > min
which completes the proof.
46

---

Under review as a conference paper at ICLR 2022
N NUMERICAL SIMULATION DETAILS
Verification of the fully mixed NE in Game
We now verify that joining network with proba-
bility 3[1-2c) 311-265..e. J.e.
1-3c
1- 3e
Tg. (a. 1|s)
4s EEE,, i= 1,2,
3(1 - 2c)
indeed NE. First, observe that
1 3c
1-3c 3c
Pr = 1) =
P(SL++1 = Naii = 1) +
1
P(s = I/ai 2)
3(1 26)
3(1
26)
1 3E
(1 (1-c)+ (1- 1 1 3E
1
3(1 2c)
3(1 22)
3
Thus,
V(s) = (+))= Σ
20
By Ba, =(()) 3(1 - 7)
27
(s, = -(()) + Σ
P(s
6'a
27 3(1 7)
-r(s) +7 Σ
P) 2)r(s;, - 2)) +
(E(112)
=r(s) + 7P(s = 1/a;))
g7(5/ -,, = 1) -- 1)+ gr((/ = 1,,- = =2)
+>P(s = 2/a:)
5 (8) = 2, = 1)+ 2 2,,,, 2)) +
1
-2)
27²
3(1 7)
2
2
r(s) + 27
r(s) 3
3(1 -7) V(s),
3(1 7)
which implies that:
(0' 0.) Vo. (10) = 0, 18, E X₁ i= 1,2,
ie. f satisfics first-order stationarity. Since ds(s) > holds for any valid 0, by Theorem 1 is NE.
Computation of strict NEs in Game 2 The computation of strict NEs is done numerically, using the criterion in Lemma We enumerate over all 2 possible deterministic policies and check whether the conditions in Lemma 4 hold. For 0.1, 7 0.95, and an initial distribution set as:
p(s1 82 j) 1/4, i,j (1,2),
the numerical calculation shows there exist 13 different strict NEs.
47


Reviews:
[{"review_id": "XDfzjFtJMnz", "reviewer": "Reviewer_oPGh", "summary": "", "questions": "", "limitations": "", "rating": 6, "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:\n\nThey study general Stochastic games with multiple players (more than two) and a provide a local characterization of the strict NE which is novel, as it applies for general stochastic games with no assumption. Although, here the gradient of each player does seem to depend on the information from other players.\nThey provide a sample-based RL algorithm with non-asymptotic guarantees for Markov Potential Games, with fully independent gradient updates for each players.\n\n\nWeaknesses:\nThe issue is that the existence of Strict Nash for Stochastic Games maybe a strong assumption. This may be quite rare even when considering normal form games. \n\nGiven the result of [Daskalakis et al. 2021] (which is not cited in this paper), that show that independent RL (with a two time scale approach) for two player Stochastic Zero-Sum games converges to the epsilon-Nash policy globally with a non-asmyptotic convergence rate. It would have been interesting to see more specific characterization of classes of Stochastic Games that possibly can lead to a similar convergence guarantees. For instance, it might be useful to look at separable zero-sum polymatrix games [Cai and Daskalakis 2014], a subclass of multiplayer games that accommodate efficient computation of NE through linear programs. Even in normal form games if one applies no-regret online algorithms for two-player zero-sum games, the last-iterate behavior might be complicated [Bailey and Piliouras 2018, Mertikopoulos et al. 2018]. It is possible that some of these complications may carry over to the MARL settings.\n\nAlso, it would be interesting to understand possibly other notions such as Coarse Correlated Equilibrium for general settings of Stochastic Games, instead of relying purely on the Nash equilibrium.\n\nFinally it would be useful if the authors could differentiate between the results of [Leonardos et al 2021] for Markov Potential Games as both algorithms achieve the same sample complexity and other results are mostly similar. Maybe it would be useful if they discuss algorithmic and computational differences. \n\nReferences:\n\nDaskalakis, Constantinos, Dylan J. Foster, and Noah Golowich. \"Independent policy gradient methods for competitive reinforcement learning.\" arXiv preprint arXiv:2101.04233 (2021).\n\nCai, Yang, et al. \"Zero-sum polymatrix games: A generalization of minmax.\" Mathematics of Operations Research 41.2 (2016): 648-655.\n\nLeonardos, Stefanos, et al. \"Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games.\" arXiv preprint arXiv:2106.01969 (2021).\n\nMertikopoulos, Panayotis, Christos Papadimitriou, and Georgios Piliouras. \"Cycles in adversarial regularized learning.\" Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.\n\nBailey, James P., and Georgios Piliouras. \"Multiplicative weights update in zero-sum games.\" Proceedings of the 2018 ACM Conference on Economics and Computation. 2018.\n\n", "summary_of_the_paper": "The authors study independent gradient play in Stochastic Games, with multiple players/agents. They characterize the (local) stability of strict Nash in Stochastic Games. In addition they study Markov Potential Games, a subclass of Stochastic Games and show global convergence of projected gradient ascent for direct paramterization of Tabular MDPs. In addition, they also provide a sample-based RL algorithm, where the players do not use gradient information from others and estimate based on the observed trajectories. They show non-asymptotic convergence guarantees of this algorithm for Tabular MDPs which are Markov Potential Games.", "summary_of_the_review": "The paper has some interesting results for very generic Stochastic Game settings and Markov Potential Games (very similar to [Leonardos et al. 2021]). But I think these settings are too generic to study and extract meaningful results. Given the above comments on the strengths and weaknesses, it seems that there is more investigation and characterization that might be required. \n\nAfter the response:\nThe authors have clarified most of the concerns and the characterization seems adequate for this work to be published.", "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": {}}, {"review_id": "F_grIsEAtxX", "reviewer": "Reviewer_ByWn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 main idea is to use the gradient domination property established in Agarwal et al., 2020 and argue that stationary points of the potential function are indeed approximate Nash policies. Then using techniques from non-convex optimization, it is known that Gradient Descent converges to stationary points and this is what they show about policy gradient on the potential function. The analysis of the stochastic variant is much more challenging, it needs different parametrization than direct parametrizatoin. In general, i feel the paper has made a valid contribution on multi-agent RL in potential games.", "summary_of_the_paper": "The paper studies the global convergence of policy gradient for multiagent Markov potential games. The authors define a notion of potential markov games that seems natural and show convergence to Nash policies when the agents use gradient ascent independently on their policies (using direct parametrization). Observe that the authors assume that the agents have full knowledge of their utilities and their derivatives (their algorithm is deterministic). They also provide convergence for the stochastic variant of policy gradient (given samples).\nThey moreover show that deterministic Nash policies always exist and show that fully mixed policies are saddle points. Saddle points might be of higher order, so first order methods might fail to avoid the fully mixed policies because you need to check third (or higher) order derivatives (so techniques from Ge et al do not help to show avoidance as claimed, the authors need to remove that comment since Ge et al argue about second order stationarity).", "summary_of_the_review": "I feel the paper has solid contributions, they address both deterministic and stochastic variant of Policy gradient. The stochastic variant is more challenging due to the limitation of the non-Lipschitz gradient. ", "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": {}}, {"review_id": "AV_BqOkqB4Z", "reviewer": "Reviewer_NPmA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "* I really like the content in Appendix A, which provided numerical evidence to justify the effectiveness of the proposed methods. This kind of analysis offers particular value to the MARL community, unlike many existing theoretical MARL papers.\n\n\n\n* There are existing work that set up Markov Potential Game, can the author clarify the difference to \n\n    **Learning in Nonzero-Sum Stochastic Games with Potentials  David Mguni et al. ICML 21**\n\n    **When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? Song et al**\n\n\n* Since this paper deals with SGs, can the author comment on the relationship between the Nash equilibrium in Definition 1 and Markov  Perfect Equilibrium? \n\n\n* Through gradient dominance assumption, the author equates NE and first-order stationary point, can the author clarify if this result contradicts with the result in \n\n    **On gradient-based learning in continuous games. Mazumdar 2020**\n\n\n\n* For the linear dependency result on Markov Potential Game, can the author clarify the significane of your result versus \n\n    **When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? Song et al**\n", "summary_of_the_paper": "This paper studies the optimization landscape of first-order methods in stochastic games. In particular, it studies the connections between first-order stationary points and Nash equilibrium and its convergent property and learning stability. For general-sum SGs, local convergence results is provided. For Markov potential games, global convergence results are provided. ", "summary_of_the_review": "  This paper is a rather long paper and certainly over-exceeding the content that a conference paper can hold. Given the number of pages, it is challenging to evaluate for the correctness of proof for a 50-page paper within such a short time period. However, I believe the result is generally correct, for example, the sample complexity on Markov Potential Games has been discovered, probably in parallel, by many other papers. My major concern is how this paper poses itself among the peer work and if the result is still significant. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper looks at stochastic and Markov potential games. Its different results, including the sample complexity ones, are overall interesting and relevant for the community.

This said, we had an intense discussion as several of the aforementioned results -  actually, closely related results, not the exact same one - already appeared elsewhere (in a ArXiv preprint, that has been publicly submitted at a previous conference). We do believe that there is no ethical/plagiarism issue here, however, it remained the question of "paternity" of these results.

We have decided to give the paternity of the sample complexity to the first paper (the ArXiv preprint) that proved it. We can therefore only credit to this paper the improvements in the sample complexity results (as they are not exactly similar).

However, this had an impact on the reviewers (and also mine and the SAC one) evaluation of the paper, when some substantial parts of the paper are "discarded".

Nonetheless, we think that this paper has its merits, although it does not reach the ICLR bar in its current form. We strongly encourage the authors to work on a revised version - incorporating the different comments of the reviewers - and to resubmit it at a further venue.
Decision: Reject