On the convergence of policy gradient methods to Nash equilibria in general stochastic games
Authors: Angeliki Giannou
Kyriakos Lotidis
Panayotis Mertikopoulos
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Venue: NeurIPS 2022 Accept (2022)
Keywords: Policy gradient methods
stochastic games
Nash equilibria
convergence

Abstract: Learning in stochastic games is a notoriously difficult problem because, in addition to each other's strategic decisions, the players must also contend with the fact that the game itself evolves over time, possibly in a very complicated manner. Because of this, the convergence properties of popular learning algorithms — like policy gradient and its variants — are poorly understood, except in specific classes of games (such as potential or two-player, zero-sum games). In view of this, we examine the long-run behavior of policy gradient methods with respect to Nash equilibrium policies that are second-order stationary (SOS) in a sense similar to the type of sufficiency conditions used in optimization. Our first result is that SOS policies are locally attracting with high probability, and we show that policy gradient trajectories with gradient estimates provided by the REINFORCE algorithm achieve an $\mathcal{O}(1/\sqrt{n})$ distance-squared convergence rate if the method's step-size is chosen appropriately. Subsequently, specializing to the class of deterministic Nash policies, we show that this rate can be improved dramatically and, in fact, policy gradient methods converge within a finite number of iterations in that case.

On the convergence of policy gradient methods to Nash equilibria in general stochastic games
Angeliki Giannou University of Misconsin-Maddsee gi aianou@wisc... sc. edu
Kyriakos Lotidis Stanford University klotidis@stanford edu
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France Critco AI Lab
fr
Emmanouil V. Vlatakii-Gkarrgkkunii
University of California, Berkeley emwllatakis@berkeleey edu
Abstract
Learning in stochastic games is notoriously difficult problem because, in addition to each other's s strategic decisions, the players must also contend with the fact that the game itself evolves Because of this, the convergence properties popular learning algorithms like policy gradient and its variants are poorly understood, except in specific classes of games (such as potential or two-player, zero-sum games). In view of this, we examine the long-run behavior of policy gradient methods with respect to Nash equilibrium policies that are second-on -oddrr stationary (SOS) in sense similar to the type of sufficiency conditions used in optimization. Our first result that SOS policies are locally attracting with high probability. and we show that policy gradient trajectories with gradient estimates provided by the REINFORCE algorithm achieve an O(1/ ( Vz) distance-sque squared convergence rate if the method's '' step-size is chosen appropriately. Subsequently, specializing to the class of deterministic Nash policies, we show that this rate can be improved dramatically and, in fact, policy gradient methods converge within a finite number of iterations in that case.
time, possibly in very complicated manner.
Introduction
Ever since they were introduced by Shapley [50] in the 1950's, stochastic games have been one of the staples of non-cooperative game theory, with range of pioneering applications to multi- agent reinforcement learning [51]. unmanned vehicles [49], general game-playing [37, 52, 57], etc. Informally, stochastic game unfolds in discrete time as follows: At each point in time, the players are at a given state which determines the rules of the game for that stage. The actions of the players in this state determine not only their instantaneous payoffs (as defined by the stage game). but also the transition probabilities towards the next state the process. In this way, each player has to balance two distinct and often competing objectives: optimizing the payoffs of today versus picking possibly suboptimal action which could yield significant benefits tomorrow (i.e., by influencing the transitions of the process towards a more favorable state for the player).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Since all players in the game are involved in similar dilemma, the decision decision-making problem for each player is a very complicated affair. In particular, in addition to their changing strategic decisions. the players of the game must also contend with the fact that the stage game itself evolves over time. Because of this, even the existence of a Nash equilibrium policy - viz. a stationary Markovian policy that is stable to unilateral deviations [16] is far more difficult to prove compared to standard, stateless normal form games; for a comprehensive survey, cf. [41, 53] and references therein.
The question we seek to address in this paper is whether an ensemble of boundedly rational players can reach an equilibrium policy in a stochastic game. Specifically, players do not have sufficient information or the computational resources required to solve a high-dimensional Bellman equation [15, 54], is not all clear if they would somehow end up playing a Nash policy in the long run. After all, the complexity of most games increases exponentially with the number of players, so the identification of game's equilibria quickly becomes prohibitively difficult [27].
Our contributions in the context of related work. This issue has sparked a vigorous literature with important ramifications for the range of applications mentioned above. Nevertheless, these efforts must grapple with a series of strong lower bounds for computing even weaker solution concepts like coarse correlated equilibria in turn-based stochastic games [12, 27]. On that account, recent line of work has focused on establishing convergence in specific subclasses of stochastic games, such min-max [7, 11, 32, 47, 48, 58] and common interest potential games [13, 31, 61]. However, despite these encouraging results, the general case remains particularly clusive.
Our paper takes complementary approach to the above and seeks to study the convergence landscape of a class of equilibrium policies not games. For concreteness, we focus on the general class of policy gradient methods as pioneered by [28, 29, 55, 59], and we examine the methods' convergence properties in general random stopping games - as opposed to ergodic stochastic games with an infinite horizon [32, 42]. Concretely, this means that the sequence of play evolves episode-by-episode within each episode, the players commit a policy and play the game, and from one episode to the next, they use an iterative gradient step to update their policy and continue playing.
Our main contributions in this general context may be summarized follows:
1. We introduce a flexible algorithmic template for the analysis of policy gradient methods which accounts for different information and update frameworks from perfect policy gradients to value- based estimates obtained on a per-episode basis, e.g., via the REINFORCE algorithm [4, 55, 59].
2. Within this framework, we show that Nash policies that satisfy a certain strategic stability condition are locally attracting with arbitrarily high probability. Moreover, to estimate the method's ' rate of convergence, we focus on Nash policies that satisfy a second-order sufficiency condition similar to the type of sufficiency conditions used in optimization, and we show that such policies enjoy an (11 vn) squared distance convergence rate.
3. Finally, we also consider the method's convergence to deterministic Nash policies a special case of SOS policies and we show that, generically, the above rate can be improved dramatically. In particular, by simple tweak to the method's projection step, the induced sequence of play converges to equilibrium in a finite number of iterations, despite all the noise and uncertainty.
It is also worth noting that our analysis focuses squarely on the actual, episode-by-ee by-epiod trajectory of play, not any "best-iterate" or time-averaged variant thereof. In regards to the latter class of guarantees, the recent work of Jin et al. [26] proposed an algorithm (called V-learning) which updates the policy of the n-th episode based on the observed rewards so far. Thanks to the algorithm's ' regret guarantees, Jin et al. [26] showed that (a) in min-max games, the time-averaged policy म. (I/n) Σx=1 ny converges to equilibrium at a rate of O(1/ vn); whereas (b) in general stochastic games, the empirical frequency of play converges to the game's s set of coarse correlated equilibria (a substantial relaxation of the notion of Nash equilibrium) at a rate of O(1/ vi).
By contrast, as we mentioned above, our paper focuses on the actual sequence of play, i.e., the policy n employed at each episode of the game. Moreover, the rates that we obtain all concern the convergence of the players' policies to a Nush equilibrium - not a correlated equilibrium or other relaxation thereof. In this regard, the best-iterate ergodic convergence rates are incomparable to our own as they concern a weaker type of convergence (time-averaged instead of the actual sequence). and to a weaker solution concept (correlated equilibria instead of Nash equilibria). This aspect of our

---

results is especially relevant for multi-agen reinforcement learning scenarios where agents learn "on the fly", and it has important ramifications for many of the practical applications of stochastic games.
From a technical standpoint, our analysis is based on mapping the problem of multi-agent policy learning the problem of equilibrium learning in a class of continuous games characterized by the fact that first-order stationary points are necessarily Nash (itself' consequence of the so-called "gradient dominance" property of stochastic games). By means of this reframing, we able to leverage series of recent techniques for establishing local convergence in (non-monotone) continuous games and variational inequalities [3, 8, 24, 25, 33, 45]. which ultimately also yield convergence in our setting. As a result, even though the unbounded variance of the REifFORcE estimator is source of considerable complications, the resulting link between stochastic and continuous games of particular technical interest because it opens up wide array of stochastic approximation tools and techniques that can used for the analysis of multi-agent learning in stochastic games.
2 Preliminaries
2.1. Setup of the game. Throughout this work we consider N-player generic stochastic games where players repeatedly select actions in a shared Markov decision process (MDP) with the goal of maximizing their individual value functions. Formally, we study the tabular version with random stopping of general stochastic games, which is specified by a tuple G (S,N, (A, R P.S.P) with the following primitives:
A finite set of agents E N = (1,2....,N) and a finite set of states S = (l.....
For each i N, a finite space of actions (or pure strafegies) A; indexed by
A, A LAj.
We will write A = ITE A, and A-; = Ja Aj for the action space of all agents and that of all agents other than respectively. In a similar vein, we will also write a = (0;,ar.) when we want to highlight the action a, of player against the action profile a of i's opponents.
For each i E ., we will write R; S - [-1, 1] for the reward function of agent E N, i.e., R,ss, as, ar,)))))) will denote the value of the reward of agent when the game at state E S, the A. and all other agents take actions
focal agent e N plays
A-j.
The game transits from one state to another according to a Markov transition process, so that P(s' [ s. a) denotes the probability of transitioning from s to s' when E A is the action profile chosen by the agents.
Given an action profile a at state s, the process terminates with probability L.. > 0, i.e., Esp 1- --rrs P(s' s, a, for convenience, we will write & == minaa
P A(S) is the distribution for the initial state of the game.
Episodic Setting. We consider episodic setting, where in each episode a realization of the game completed. At every time step 1 2 0 of each episode, all agents observe the common state s, E S, select actions a, and receive rewards (R, ay)leNN Then, with probability Sa,a; the game terminates, and with probability
Ss,a,, it moves to the state S1+1, which is drawn according to P(|ss, az). Denoting the realized reward of player i at time Fi R,(,, a,), will write r (s,, a, Fi)isT()) to denote the trajectory of the episode, where == (ru))eN and 7(T) the time the episode terminates.
Policies and value functions. We consider stationary Markovian policies, i.e., policies that do not depend on the time-step and the history, given the current state the game. More specifically, for each agent i E N,, policy z: S - A(AA) specifies probability distribution over the actions of agent i state s S, i.e. 0; ~ TT(+ls) denotes the (random) action drawn by agent at state E S according to Ri, viewed here an element of II; == A(A)S. In addition, will also write π = (πT))N E πI := 11, II and π., = (TT) jel E II, = II I1 for the policy profile of all agents and all agents other than i, respectively.
The expected reward of agent i E N if agents follow policy æ, starting from initial state e S, defines the value function of agent denoted as Vi,(s), and is equal to
VZ)(T) == E,-MPP Σn T(r)
(,
where r ~ MDP denotes the randomness induced by the policy profile æ, and the stans-trann probabilities of the MDP. Overloading the notation, we set Vip(T) == (V,)).. Although value
3

---

functions are, in general, non-convex, they share similar smoothness properties with the payoff functions of normal form games, namely bounded and Lipschitz gradients. For precise statements, we defer to the paper's supplement.
Visitation distribution and the mismatch coefficient. For policy profile π II and an arbitrary initial state distribution p, we define the discounted state visitation measure/dditrriuttion as Tir
Σn 1|s, s1|so - p|
(s) MDD
=z)))
In the appendix, we prove formally that the above definition is well-posed for the random stopping episodic framework described above, i.e., (5(s) < oo, so 7 == Eves dz(s) is well-defined. In our proofs, we will leverage standard property of visitation distributions, namely the equivalence of the expected value of state-action function and the expected cumulative value over a random trajectory. More precisely, we have:
Lemma 1. [Conversion Lemma] For an arbitrary state-action function f: S xxx.A - R, a policy profile æt and an initial state distribution 5o p. we have
f(s,, an) = Z, E, Ea Σn T(T)
E7-MDP
(2)
Finally, to quantify the difficulty of hard-to-reach states via a policy gradient method, we will follow the standard approach of [9, 14, 38, 39, 61] and use oppropriately-definel distribution "mismatch coefficient", generalizing the single-agent counterpart of Agarwal et al. [1]. More precisely, for a
stochastic game G, we define the mismatch coefficient as Cg == ma / Ioao or, more simply, as Cg == max 1ldf,///lo. p.loo) Similar to prior work in this direction [1, 5, 11], we will assume Cg is finite, which, equivalently, means that (s)(s) for any policy π and state s.
2.2. Solution concepts. The most widely used solution concept in game theory is that of a Nash cquilibrium i.e., a strategy profile x² II that discourages unilateral deviations. However, in stochastic games, the definition of a Nash policy is much more involved because of the existence of multiple states and steps, cf. [16, 50, 53, 56] and references therein. Formally, we have:
Definition 1 (Nash policies). A policy x² (x))EN E II is said to be Nash policy for given distribution initial states p E A(S) for every player N, we have
Vi x 2 Vin(T for all i E A and all π, E A
(NE)
In contrast general non-convex continuous games, stochastic games satsify version of the well- known Polyak-Lojasiewin condition [44] but with linear gradient growth, also known as a gradient dominance property (GDP) [I. 5]. For the multi-agent case, Zhang al. [61] and Daskalakis et al. [11] showed that similar property holds even in the episodic setting:
Lemma (Gradient dominance property). For any policy profile π (TD)N II, we have that
V (x(( x(;) S Cg max (1), xi)
(GDP)
for any unilateral deviation ,. E II, of player E. A. Remark. In the above and throughout our paper, will write V, denote the gradient of the quantity in question with respect to π; i.c., when πI; is kept fixed and only is varied. For concision, we will write uę())) (T) for the individual gradient of player i's value function, and t(x)) = (V;(T))EN for the ensemble thereof.
Thanks to (GDP), it straightforward to check that first-order stationary (FOS) points of V are Nash. Formally, as in [11,31, 61], we have the following characterization:
Lemma (First-order stationary policies are Nash). A policy = (TD) II is Nash if and only if it satisfies the first- stationary condition
(1(x"), ), π - x²) 50 for all π e II.
(FOS)
Leonardos et al. [31] and Zhang et al. [61] proved a relaxation of the above lemma to the effect that policies that satisfy (FOS) up to (i.e., in lieu of 0 in the RHS) are (as)- Going in the other direction, we will consider the following series of refinements of Nash policies which are particularly important from learning standpoint [30, 53]:

---

Definition 2. Let x² = (T,))eN E II be Nash policy, We then say that:
n' is stable if (u(x), - x²) < 0 for all π x² sufficiently close to x².
π is second-order stationary if it satisfies the sufficiency condition (π - >''''''T (TT,(T"))) (TT")""" =²) for al π (1,)')) where Jac,(Tr") = (V,0,(r)
(SOS)
(V VVV(()) denotes the Jacobian of at x².
n² is deterministic it induces a deterministic selection rule x S + A, for all i E N.
is strict it is deterministic and (FOS) holds as strict inequality whenever π #
Remark 1. In the above and what follows, "sufficiently close" means that there exists neighborhood xf in II such that the stated inequality holds for all π E U. Unless mentioned otherwise, we will measure distances on II relative the Euclidean norm, but this choice does not impact our results.
Intuitively, the condition for equilibrium stability is thme-theooetti analogue of first-order KKT sufficiency condition, while the condition for second-order stationarity is the second-order version thereof. In this regard, the distinction between first-order stationary, stable and second-order stationary points is formally analogous to the distinction between critical points, minimizers, and second-order minimum points in optimization. As for deterministic policies, we should mention that, generically, deterministic policies are also strict, so we will use the two terms interchangeably.
Importantly, as we show in ??, these refinements admit the following characterizations:
Proposition Let π- (x()ieN E II be Nash policy. Then:
a) Tf second-order stationary, there exists some μ > 0 such that (v(T), x²) - x'Il
for all sufficiently close to n².
(3a)
b) xf is strict, there exists some μ > such that (u(T), x') - I'll
for all sufficiently close to x².
(3b)
In view of all the above, we get the following string of implications for equilibria in generic games: strict/deterministic = SOS = stable
FOS Nash
(4)
' For posterity, we should elarify here that, due to the highly complicated structure of the game's
value functions, it is not trivial to construct a concrete example where (3a) holds but (3b) does not. Examples of strict Nash policies abound in the literature [30, 53], but an argument that could be used to close the gap hetween (3a) and (3b). In view this, our analysis will treat both cases concurrently (with the obvious anticipation that more refined solution concepts should enjoy stronger convergence guarantees).
not otherwise aware of
Policy gradient methods
We now proceed describe our general model for episodic learning in stochastic games. To that end, we will consider framework where agents follow a specific policy я, within each episode, and update from one episode the next with the objective of increasing their individual rewards. Formally, our approach will adhere to the following inter-episode sequence of events:
1. At the beginning of each episode " 1,2,..., every agent N chooses policy ni E II;
2. Within the n-th episode, each player executes their chosen policy Mi,, inducing in this way an intra-episode trajectory of play t, (s.") ,a
(n) (d)) )
3. Once the episode terminates, agents update their policies and the process repeats.
In terms of feedback, we will treat several models, depending on what type of information is available the agents during play. More precisely, we will focus on the generic policy gradient (PG) template
1 ( D,
(PG)
where:
'The notion of genericity is stated here in the sense of Baire, i.., the stated property holds for all but "meager" set of games (i.e.. countable union of nowhere dense sets in the space of all games).
5

---

Algorithm 1: REINFORCE
Algorithm 2: 8-GREEDY POLICY GRADIENT
1: Input: E II. = (s,, an FiDSSTC E T
1: Input: Ri. (wwlnnn. (EaheEN
2: for i= I...., N.....N. do
2: for 1,2,... do
3: (1(T) - -1=0 Thr
3: Rn - (1 En) Ei
4: ATT) - En1 v.(log (,(a))))))
4: Sample Tn ~ MDP(Rnls0))
5: 0, R(T) (T7))
5: in < REINFORCE(R Ta)
6: end for
Ap-1 f projjn + 7,0x)
7: return (0dhe
7: end for
1. n. (AE))EN II denotes the player's policy profile at each episode n 1,
2. 8, =(in))eN 11, A.X is an estimate for the agents' inidividual policy gradients.
3. proin: II, AAXS II denotes the Euclidean projection to the agents' policy space II.
4. > O is the method's step-size, for which we will assume throughout that Σn = typically,
(PG) is run with step-size of the form Yn = y/(n+ m)? for some y > O, m 2 and p
Regarding the gradient signal i. we will decompose it as
in = u(TT) + Un + bn
(5)
where
U, 8 E[ [F,] and b,
v(T,).
(6)
In the above, we treat Ry, n 1,2..... as stochastic process on some complete probability space (22 PP), and we write F, = F( nT) ( [ F for the history (adapted filtration) of nu up to and including stage n. By definition, IH(U, as random, mean error relative to u(T,,), whereas b, captures all systematic (non-zero-mean) errors. make this precise, we will further assume that b, and Un are bounded as
and b, Fmmassurablle, so Un can be intepreted
and where the sequences B, and o. n 1.2...., are to be construed as deterministic upper bounds on the bias, fluctuations, and magnitude of the gradient signal Òд-
BII|b F. s B,
EMU (F,) S of
Depending on these bounds, gradient signal with B, = will called unbiased, and an unbiased signal with o, 0 will be called perfect. More generally, we will assume that the above statistics are bounded as
B, O(/n''s and
oR =m=00
(8)
for some C, fy which depend the specific model under consideration. For concreteness, describe below three basic models that adhere to the above template for 0, in order of decreasing information requirements:
Model 1 (Full gradient information). The first model we will consider assumes that agents observe their full policy gradients, i.e.,
i = ((T,)
implying in particular that U, = b, = O. This model is fully deterministic across episodes (though intra-episode play remains stochastic). In particular, it tacitly assumes that agents know the game (and can observe their opponents' policies) sufficiently well so as to calculate the full gradients of their individual value functions Vip. cf. [2, 31, 61] and references therein.
Model 2 (I (Learning with stochastic gradients). A relaxation of the above model which is particularly relevant for applications to deep reinforcement learning concerns the case where the player have access to stochastic policy gradients [60], i.e., unbiased gradient estimates of the form
i ((x,)) + Un
(10)
with E[U, [F.] = 0 (so we can formally take l, oo and e,- 0 in Eq. (8) above).

---

Model 3 (Value-based learning). The last model we will consider concerns the case where agents only have access to their instantaneous rewards and need reconstruct their individual gradients based on this information. A widely used method to achieve this is via the REIFFOCCE subroutine, which we describe in pseudocode form in Algorithm In words, when employing REINFORCE, each agent i E i commits to a sampling policy ât E II, and executes it in an episode of the stochastic game in play. Then, at the end of the episode, players gather the total reward R₂(T) < Σne fy associated to the intra-episode trajectory of play т, and they estimate their policy gradients via the so-called flog-trick" [59] as
Σ
1=0 T V vlooog (srgss)))
R((T)
(11)
Lemma 4 below provides the vital statistics the REINFORCE estimator:
Lemma 4. Suppose that each agent E N follows stationary policy I1. Then:
a) [EIN = v(xz)
(12a)
24A:
b) E ED-M || (,(x))11
(12b)
K;L*
where K; min, MT(as)s)
Therefore, if REINFORCE exccuted at t nr at each episode n = 1,2..... we will have
24A,
B = (,
and
E. 5 min (asss))
(13)
In particular, this means that we will always have B, 0 for the bias of the estimator, but its variance could be unbounded if n, gets close to the boundary of II. To avoid this, Reifforee can be paired with explicit exploration step that modifies the sampling policy of the n-th episode
i = (1 - ET + En Unif for s E S
(14)
i.e. Ain is the mixture between Tie and the uniform distribution Unif over A. The resulting
algorithm is known as GRGEED POLICY GRADIETT; for pseudocode representation, see Algorithm 2.
Importantly, by calling REIFFOREE at ât instead of T,, &, becomes biased (because the difference between f and kn), but its variance is bounded; in particular, by invoking Lemma 4, we have
24A²
E||b [F.. S G
and
EII IF,
(15)
E
where G is constant that depends on the smoothness of V and the cardinalities of A and S.2 In this way, Algorithm 2 can seen as special case of (PG) with B, = O(e,) and of = O(1/e))
4 Convergence analysis and results
We now in position to state and discuss our main results. For convenience, we will present our results in order of increasing structure, starting with stable policies, and then moving on to second-order stationary and deterministic Nash policies. All proofs are deferred to the appendix.
4.1. Asymptotic convergence to stable Nash policies. Our first convergence result concerns Nash policies that satisfy the stability requirement (ι(π), x - π²) < of Definition In this case, we have the following guarantee:
Theorem 1. Let π² be a stable Nash policy, and let n, be the sequence of play generated by (PG) with step-size Yn y/(n + m)P p e (1/2, 1}, and policy gradient estimates such that p + Ep > I and p- lo > 1/2 as per (8). Then there exists neighborhood U of x" in Il such that, for any given ö 0, have
P(T, converges to x² | E U) 2 1-5
(16)
provided that y is small enough (or m large enough) relative
"Specifically, from ?? we know that (l,, - m((T,)l < 3 VA/z3 Σj VA, 1 RIall- Moreover, (a (a s) 6, for all s S. A,, so || Amall s A.A, Combining the above, follows that we take G 3NA V5/2".

---

Corollary 1. Suppose that Models 1-3 are run with a step-size of the form yn =y/(++ my, p> 1/2, and if applicable. an exploration parameter En, = mif such that 1 1-p p < L2 2p Then:
For Models and 2: the conclusions Theorem hold as stated.
For Model 3: the conclusions of Theorem I hold as long as p > 2/3.
We note here that Theorem 1 provides trajectory convergence guarantee which is otherwise quite difficult to obtain even in structured stochastic games. For example, we zoom in on the class of stochastic potential (or min-max) games, the existing guarantees in the literature concern the "best iterate" of the algorithm, cf. [31, 61] and references therein. Because of this, said guarantees do not apply the actual trajectory of play generated by (PG); this makes them less suitable for agent-based learning where the players involved are learning "as they go"" as opposed to simulating the game in order approximately compute an equilibrium policy offline.
We should also note that the convergence guarantees of Theorem 1 hold locally with arbitrarily high probability. Without further assumptions, it is not possible to obtain global trajectory convergence guarantees that hold with probability 1, even in single-state games that is, the case of learning in finite normal form games. The reason for this locality is twofold: First, equilibrium policies not unique in general, and gradient-basee dynamics may also admit non-equilibrium attractors, such as limit cycles and the like [23, 34-36]. As result, in the presence of multiple equilibrin/attractors, the best one can hope for is a local equilibrium convergence result, conditioned on the basin of attraction of said equilibrium (as per Theorem 1).
The second obstruction to a global, unconditional convergence result is probabilistic nature, and has to do with the randomness that enters the learning process (e.g., in the estimation of policy gradients via the REINFORCE). In this case, no matter how close one starts to an equilibrium policy, there is always a finite, non-zero probability that an unlucky realization of the noise can drive the process away from its basin, possibly never to return. This issuc can only be overcome in games where II is partitioned (up set of measure zero) into basins of attraction of equilibrium policies. However, this can only occur in games with a sufficiently strong global structure, like potential stochastic games, two-player zero-sum games and the like; in complete generality, locality cannot be lifted, even in single-state problems [17, 19].
4.2. Convergence to second-order stationary policies. Albeit valuable as an asymptotic conver- gence guarantee, Theorem does not provide an indication of how long will take players actually converge to Nash policy. Of course, in full generality, it is not plausible to expect to be able to derive such convergence rate because the stability requirement provides no indication on how fast the players' policy gradients stabilize near a solution. This kind of estimate is provided by the sccond-order sufficient condition (SOS), which allows us to establish sufficient control over the sequence of play as indicated by the following theorem.
Theorem 2. Let x" be second-order stationary policy, let B be a neighborhood xt' nt" such that (3a) holds on B, and let n, be the sequence of play generated by (PG) with step-size Yn = yi(nn + m), p E (1/2, 1], and policy gradient estimates such that + E > I and p Eo 1/2 per (8). Then:
1. There exists a neighborhood of x² II such that, for any confidence level > 0, the event
(n,, E B for all = 1,2....)
(17)
occurs with probability P(E n E (4) 2 if is large enough relative to
2. The sequence n, converges to πt with probability 1 on E; in particular, have
Plr, converges x¹ m U)) 5
(18)
if m is large relative to 6. Moreover, conditioned E and taking q min p 2l,), we have
(O(1/) (0 ( (0(1/9))
if and 2uy < q.
Bl - x 11111188=
(19)
otherwise.
Corollary Suppose that Models 1-3 are run with a step-size of the form yn y/(n + m)', p 1/2, and if applicable, exploration parameter e, E/(n m Then:
8

---

For Models I and 2: the conclusions of Theorem 2 hold with q = p; in particular, (19) gives an ((n))) rate of convergence if p = and 24y > q.
For Model 3: the conclusions of Theorem 2 hold for p 2/3 with q p/2; in particular, (19) gives an O(1/ Vn) rate of convergence if p = I and 24y > q.
Remark 2. Getting
explicit estimate for the constant in the O()) guarantee of Theorem 2 is quite involved but, up to logarithmic and subleading factors, Chung's lemma [10, 43] can be used to show that a) if 24y > q. it scales as (C, C,r)/((2py q) 6)] where C.- sup, Bn and C = sup, P: b) if 24y q. it scales as (C3 + +C + maxx(2 (1 - 6); and c) if 24r < as (C, + C,) max((2py)) 4py))/((q 24ry) ö)].
Besides providing general framework for achieving trajectory convergence, Theorem 2 gives the rates of convergence of the sequence of play to the Nash policy in question. In particular, with this result in hand, one can confidently argue about the distance of the iterates of (PG) from equilibrium in a series of different environments. More to the point, this convergence guarantee allows the algorithm designer to adapt the parameters of the learning process according to the complexity and limitations of the environment, a feature which further highlights the significance of this result.
We should also note the delicate interplay between the method's step-size and the achieved con- vergence rate. In the case of Model 1, Corollary suggests a step-size of the form y, O(1n),, leading to (L|/n) convergence rate. As we show in the appendix, this rate can be improved: in the deterministic case with perfect gradient information, (PG) with a suitably chosen constant step-size achieves a geometric convergence rate, i.c., ||T, x''l (cxp(-ppn) for some p > 0 (cf. ?? in ??). By contrast, in the case of Model 2. the O(1/n) rate we provide cannot be improved, even the quadratic minorant (3a) that characterizes SOS policies holds globally and this because the learning process is running against standard lower bounds from convex optimization [6, 40].
Perhaps the most significant guarantee from a practical point of view is the O(1/ vi) convergence rate attained in Model 3 (cf. Algorithms and 2). This guarantee amounts in terms of the (non-squared) distance to equilibrium which, mutatis mutandis, represents a notable improvement over the (6) guarantee of Leonardos et al. [31] (expressed in norm values). Of course, the latter guarantee is global - because the focus of [31] is stochastic potential games - but also concerns the "best iterate" of the process (not its "last iterate"), so the two results are not immediately comparable. However, a useful "best-of-both-workk woth-d heuristic that can be inferred by the combination of these works is that, given a budget of training episodes, Algorithm can be run with a constant step-size as per [31] for sufficient fraction of this budget, and then with O(1 /n) "cooldown" schedule for the rest. In this way, after an aggressive "exploration" phase, the algorithm's O(1/n// rate would kick in and supply faster stabilization to an SOS policy.
O(In!!/t) convergence rate
4.3. Convergence to deterministic Nash policies. Our last series of results concerns the rate of convergence to deterministic Nash policies in generic stochastic games. As we discussed in Section 2, deterministic Nash policies also satisfy (SOS), so the rate of convergence of (PG) to such policies can be harvested directly from Theorem 2. However, (SOS) can improve this rate dramatically.
show below, simple projection tweak in
The tweak in question is inspired by the geometry of II around deterministic policy: by definition, such policies are corner points of II, so any consistent drift towards them will cause n, to hit the boundary of II in finite time. Of course, under (PG), the process may rebound from the boundary and return to the interior of II if the policy gradient estimate is not particularly good at a given iteration of the algorithm. However, if we replace the projection step of (PG) with "lazy projection" in the spirit of Zinkevich [62], the aggregation of gradient steps will eventually push the process far inside the normal cone of II at x², so rebounds of this type can no longer occur.
Formally, we will consider the following lazy policy gradient (LPG) scheme:
(LPG) where y. (yia))eN E II, R-XS is an auxiliary variable that maintains aggregate of gradient steps before projecting them back to II. We then have the following convergence result:
yntl = yn + yaO, Ag-1 = projn
Theorem 3. Let n, be the sequence of play under (LPG) with step-size and policy gradient estimates such that p ly and p ly 1/2 as per (8). If is deterministic Nash policy, there exists an unbounded open set W S [1 R- A-X of initializations such that, for any 5 > O, we have
P(πT, converges to n² ly W) 1- 6.
(20)
9

---

provided that O is small enough. Moreover, conditioned on this event, Vn converges to '' at finite number of iterations, i.e., there exists some No such that n = x² for all n no.
Corollary 3. Suppose that Models 1-3 are with parameters YY, y/n". p (1/2, 1], and if applicable, E,, s/n'' with 1 - < le < 2p - Then the conclusions of Theorem 3 hold.
Remark 3. Getting an explicit bound for No is quite complicated, but the last part of the proof of Theorem 3 shows that ny scales in terms of the parameters of the game and the algorithm as no = ( MSA) ((P))) where c > 0 measures the minimum payoff difference between equilibrium and non-equilibrium strategies at æ², .M is a measure of the initial distance from x², and S and A is the number of states and pure strategies respectively.
Theorem and, by extension, Corollary are fairly unique because they provide a guarantee for convergence to an exact Nash equilibrium in a finite number of iterations. To the best of our knowledge, the only comparable result in the literature is that of [61], where the authors provide a finite-time convergence guarantee to strict equilibria with perfect policy gradients (as per Model 1). The result of Zhang et al. [61] echoes the convergence properties of deterministic first-order algorithms around sharp minima of convex functions [43], but the fact that Theorem 3 applies to models with stochastic gradient feedback of unbounded variance (Models 2 and 3 respectively) is major difference. As far as we are aware, this is the first guarantee of its kind in the literature on learning in stochastic games.
5 Concluding remarks
A key roadblock encountered by practical applications of multi-agent reinforcement learning is the lack of universal equilibrium convergence guarantees. While the impossibility results of [21, 22] imply that unconditional convergence is not reasonable aspiration without further assumptions on the game, the existence of local convergence results mitigates this deficiency as provides range of theoretically grounded stability and runtime guarantees. In this regard, deterministic policies acquire particular importance, as the convergence policy gradient methods is especially rapid and robust and this case. Of course, this leaves open the question of non-tabular settings and parametrically encoded policies, e.g., as in the case of deep reinforcement learning; we defer these investigations to future work.
Another open issue of high practical relevance concerns policy gradient methods that do not rely on Euclidean projections to II. In the single-state case (i.e., learning in finite normal form games), the use of methods relying on softmax choice exponential weights is very widely used because of its regret guarantees. Whether the use of similar softmax techniques can lead to finer convergence guarantees in the context of general stochastic games is an important and intriguing question for future research.
Acknowledgments and Disclosure of Funding
Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. P. Mertikopoulos gratefully ack acknowledges financial support by the French National Research Agency (ANR) in the framework of the "Investissements d' "'avenir" program (ANR-15- IDEX-02), the LabEx PERSYVAL P3IA-0003), and the bilateral ANR-NRE grant ALIAS 19-C-1-- (00--00010001)01 K. Lotidis and E. Vlatakis are grateful for financial support by the Onassis Foundation (F ZR 033- 233-1/2021-202 010-1/2018-21999 A. Giannou is grateful for financial support by ONR: "A Theoretically Principled Vlatakis-Gkaragkoon Gkaragkounis grateful for financial support
MIAI @ Grenoble Alpes (ANR-19-
Framework for Learning by Pruning". E. V. Vlatakis by the Google-Simons Fellowship. Pancretan Association of America and Simons Collaboration on Algorithms and Geometry. This project was completed while he was a visiting research fellow at the Simons Institute for the Theory of Computing. Additionally, he would like to acknowledge the following series of NSF-CCF grants under the numbers
References
[1] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gauray Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austriaj.
10

---

volume 125 of Proceedings of Muchine Leurning Research, pages 64-66. PMLR, 2020. URL http: //proceedings wtt.ss.ll.....r.........eeemme.. atvess/v12/aagarwalll.s htmll..
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 (98):1-76, 2021.
[3] Waiss Azizian, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. The last iistiiterate convergence rate of optimistic mirror descent in stochastic variational inequalities. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[4] Jonathan Baxter and Peter L Bartlett. infinitehhorizn policy-gradicn estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
[5] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint
arXiv: 09069900677770 2019.
[6] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-333 2015.
(7] Shicong Cen, Yuting Wei, and Yuejic Chi. Fast policy extragradient methods for competitive games with entropy regularization. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 27952-27966 2021.
[8] Benjamin Chasmov, Lillian Ratliff, Eric Mazumdar, and Samuel Burden. Convergence analysis of gradient- based learning in continuous games. UAI' 20: Proceedings of the 35th Annual Conference on Uncertainty in Artificial Intelligence, 2020.
[9] Jinglin Chen and Nan Jiang. Informition-theoreiicc considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMIR, 2019.
[10] Kuo-Liang Chung. On stochastic approximation method. The Annals of Mathematical Statistics, 25(3): 463-483, 1954.
[11] Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
[12] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilibrium in stochastic games. arXiv preprint 220,,22204. 2022.
[13] Dongsheng Ding, Chen-Yu Yu Wei, Kaiqing Zhang, and Mihailo R Jovanović. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. arXiv preprint arXiv:2202.de 029, 2022.
[14] Jaanqin Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pages 486-489. PMLR, 2020.
[15] Jerzy Filar and Koos Vrieze. Comperitive Markov Decision Processes. Springer, 1997.
[16] Arlington M Fink. Equilibrium in a stochastic n-person game. Journal of science of the hiroshima university, series ai (mathematics), 28(1 1:89933, 1964.
[17] Lampros Flokas, Emmanouil Vasileios Vlatakis- Vlatakis-Gkaragae Gkaragkounis, Thanasis Lianeas, Panayotis Mertikopoulos, and Georgios Piliouras. No-regret learning and mixed Nash equilibria: They do not mix. In NeurlPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[18] Gerald B. Folland. Real Analysis. Wiley- Enley-Interscience, 2 edition, 1999.
[19] Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkarageen Gkaragkounis, and Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT
21: Proceedings of the 34th Annual Conference Learning Theory, 2021.
[20] P. Hall and C. C. Heyde. Martingale Limit Theory and Its Application. Probability and Mathematical Statistics. Academic Press, New York, 1980
[21] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading correlated equilibrium. Econometrica. 68(5): 15500 September 2000.
[22] Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 93(5))1830-1883) 2003.
[23] Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: Convergence spurious non-critical sets. In ICML '21: Proceedings of the 38th International Conference on Machine Learning, 2021.
[24] Yu-Guan Hsich, Franck lutzeler. Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In NeurIPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 6936-6946. 2019.
[25] Yu-Guan Hsich, Franck lutzeler. Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In NeurIPS '20: Proceedings of the 34th International Conference Neural Information Processing Systems, 2020.
11

---

[26] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-Learning: A simple. efficient, decentralized algorithm for multiagent RL. https://arxiv. org/ abs/2110...1.. 14555, 2021.
[27] Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infinite -onitte-orizoon general-sum stochastic games, 2022.
[28] Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
[29] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
[30] Rida Laraki, Jérôme Renault, and Sylvain Sorin. Mathematical Foundations of Game Theory. Universitext. Springer, 2019.
[31] Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. In International Conference on Learning Representations, 2022. URL. htap:://ppece /tttp::/oppnrevieew
[32] David S. Leslie, Steven Perkins, and Zibo Xu. Best-response dynamies in zero-sum stochastic games. Journal of Economic Theory, 189:105095, 2020.
[33] Panayotis Mertikopouloss and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(1-2):465-507 January 2019.
[34] Panayotis Mertikopoulos. Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In SODA '18: Proceedings of the 29th annual ACM-SIAM Symposium Discrete Algorithms, 2018.
[35] Panayotis Mertikopoulos. Bruno Lecouat, Houssam Zenati, Chuan Shann-Sheng&aa Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile.
In ICLR '19: Proceedings of the 20/9 International Conference on Learning Representations, 2019.
[36] Panayotis Mertikopoulos, Ya-Ping Hsieh, and Volkan Cevher. Learning in games from stochastic approximation viewpoint. httpps//arxiv> http//aaavvvoggaaaaa.
03922, 2022.
[37] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-lovel artificial intelligence in heads-up nomii poker. Science, 356(6337):508 513, 2017. doi: 10.1 11////ieenc..amm66600
[38] Rémi Munos. Error bounds for approximate policy iteration. In ICML. volume 3, pages 560-567, 2003.
[39] Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press;
MIT Press; 1905,
[40] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Bosic Course. Number 87 in Applied Optimization. Kluwer Academic Publishers, 2004.
[41] Abraham Neyman and Sylvain Sorin, editors. Stochastic Games and Applications. NATO ASL Kluwer Academic Publishers, 2003.
[42] Steven Perkins. Advanced stochastic approximation frameworks and their applications. PhD thesis, University of Bristol, 2013.
[43] Boris Teodorovich Polyak. Introduction to Optimization. Optimization Software, New York, NY, USA, 1987.
[44] T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):8648878, 1963. ISSN 0041-5553.
[45] Lillian J. Ratliff, Samuel A. Burden, and S. Shankar Sastry. On the characterization of local Nash equilibria in continuous games. IEEE Trans. Autom. Control, (1):23301 -2077 August 2016.
[46] Ralph Tyrelll Rockafellar and Roger J. B. Wets. Variational Analysis, volume 317 of A Series of Compre- hensive Studies Mathematics. Springer-
Berlin, 1998
[47] Muhammed Sayin, Kaiqing Zhang. David Leslie, Tamer Basar, and Asuman Ozdaglar. Decentralized g-learning in zero-sum markov games. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and
J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages
18320 18334. Curran Associates, Inc., 2021.
[48] Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. arXiv preprint arXiv:2010.04223. 2020.
[49] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint 161.v:1610.03295 2016.
[50] Lloyd S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences of the USA, 39: 1095-1100, 1953.
[51] Yoav Shoham and Kevin Seyton-Brown. Multiagent systems: Algorittumic, game- theorethe and logical foundations. Cambridge University Press, 2008.
12

---

[52] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou. Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillierap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel. and Demis Hassabis. Mastering the game of go without human knowledge. Nat., 550(7676):354 359, 2017. doi: 10. 10180/
[53] Filon Solan and Nicolas Vieille. Stochastic games. Proceedings of the National Academy of Sciences, 112
(45):17743-37746 2015.
[54] Richard S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge.
MA, 1998.
[55] Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems,
12, 1999.
[56] Masayuki Takahashi. Stochastic games with infinitely many strategies. Journal of Science the Hiroshima University, Series Al (Mathematics)) 26(2):123- 1962.
[57] Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czameekki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang. Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexan- der Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom Le Paine, Çaglar Gülçehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring. Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap. Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft 11 using multi- reinforcement learning. Nat., 575(7782)3350 354, 2019. doi: 10.1038/s41 (155/451566--011 019- 1724-2.
[58] Chen-Y Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentral- ized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Mikhail Belkin and Samory Kpolufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4259-4229. PMLR, 15-19 Aug 2021.
[59] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning. 8(3):229-255 2566. 1992.
[60] Kaiqing Zhang. Alee Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 5866)335863361,, 2020.
[61] Runyu Zhang. Zhaolin Ren, and Na Li. Gradient play in multi-agent markov stochastic games: Stationary points and convergence. arXiv e-prints, pages arXiv-2106. 2021.
[62] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. ICML 00: Proceedings of the 20th International Conference on Machine Learning, pages 928 936, 2003.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
Did you include any
either in the supplemental material URL?? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're
using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "smqr1-UOlx8", "reviewer": "Reviewer_wkBA", "summary": "This paper studied the convergence of policy gradient (PG) methods with direct parameterization (Algorithm 2) to Nash equilibria in general stochastic games. The PG methods considered here apply to full gradient information, unbiased stochastic gradients with bounded variance, and REINFORCE estimator (Models 1-3). Explicit exploration (\"epsilon greedy\") is also used to bound the variance of PG estimators.\n\nTheorem 1 showed that a stable Nash policy is locally attractive to PG with high probability.\n\nTheorem 2 then showed that a second order stationary (SOS) Nash policy enjoys stronger results of last iterate convergence rates.\n\nTheorem 3 showed that if a Nash policy is deterministic, then a lazy policy gradient (LPG) enjoys a finite convergence to exact Nash policies.", "questions": "1. Below Theorem 1 it was stated that the high probability convergence results cannot be improved further. Could you comment on what could be the possible failure cases (e.g., limiting cycles or chaotic behaviours)?\n\n2. It seems to me SOS Nash policies enjoy convergence rates because of Eq. (C.9) has larger progress than Eq. (B.35). I am wondering for stable Nash policies, is it possible to establish a rate of convergence? If not what would be the difficulty, or any counterexample could be constructed to show the rate can be arbitrarily slow?\n\n3. The finite convergence results in Theorem 3 is interesting. I am wondering if there is a parameterization to maintain the policy as valid probability distributions (e.g., standard softmax policies), then what is the implication of this lazy projection in that scenario and can it still provide useful insights?", "limitations": "This work is purely theoretical, and it has no potential negative societal impact as far as I can see.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The setting of general stochastic games is general and representative for multiagent learning.\n\n2. The PG methods studied here apply to multiple settings (full gradient, stochastic).\n\n3. The results and techniques look novel and interesting to me. I like the idea of discussing different results conditioning on whether a Nash policy is stable, SOS, and deterministic. \n\n4. The presentation is organized and clear.\n\nWeaknesses:\n\n1. It would be better if some simulation results can be provided to verify some of the results (high probability convergence and rate of convergence).", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "k69HUOgZk_o", "reviewer": "Reviewer_oi33", "summary": "The authors consider multi-player stochastic games. They study the convergence property of policy gradient type algorithms toward Nash equilibrium policies that are second-order stationary, similar to the type of KKT sufficiency conditions. They prove that policy gradient algorithms where the gradient is estimated with the reinforce algorithm, if started close to a second-order stationary equilibrium converge to this equilibrium, in terms of squared distance, with high probability at the rate O(1/\\sqrt(n)) where n is the number of steps. If the Nash equilibrium is deterministic, for a lazy version of the policy gradient algorithm, the rate of convergence improves to a constant number of steps.", "questions": "Specific comments/questions:\n\n-L30: By \"game itself evolves\" you mean the strategy of the other player or the rules of the game?\n\n-L80: The notation $a_i$ for the action seems more natural than $\\alpha_i$.\n\n-L92: Do you have a concrete example of game that you can model with this framework? In particular, a game where after each step all players fully observe the state of the game.\n\n -L127: Can you elaborate on this assumption, which at first sight seems very strong in particular for deterministic policy. And do you have a non-trivial example where this assumption is true?\n\n-L138: Can you precise what is the scalar product you consider and I assume that you see \\pi as a vector of size S\\times A right? \n\n-L153: What do you mean by close?\n\n-L163: Can you detail this point?\n\n-L167: Can you clarify \"sufficiently close\" and what norm do you consider?\n\n-L198: constructed\n\n-L210-215: 'reverse P'\n\n-L212: Can you precise what you mean by 'game involves training over datasets' and how you estimate the gradient.\n\n-L230, (14): for all s?\n\n-L235: Can you provide for G the dependence in A and S?\n\n-L244: Do all stochastic games admit a stable Nash policy?\n\n-L250: r is already used for the rewards.\n\n-L278: Can you provide any intuition on what is the typical size of \\mathcal{U}? Indeed if this set is too small there is no hope to be able to start in it.\n\n\n-L285: Can you provide an order for the constant hidden by the O in terms of the parameters of the problem? \n-L286: This part is not very clear if p=1 how do we know that q = 1/2 since 2p = q ?\n\n-L289: Can you provide lower bounds in order to state that it is effectively the rate of convergence of PG ?\n\n-L292: Can you explain how to 'to adapt the parameters of the learning process according to the complexity and limitations of the environment' in the light of Theorem 2?\n\n-L332: Can you precise how n_0 depends in the parameters of the problem? Because if this constant  n_0 is very large in comparison to the one hidden in O(1/n) the relevant regime will still be the one of Corollary 2.\n\n-L630: R is already used for the cumulative rewards.\n\n-L634: a is not defined, is it any such that a+\\sqrt{a} < r, r is the rate of \\epsilon-greedy? If so not that it is only defined in Corollary 1 stated after Theorem 1.\n\n-L656: Can you detail why the two limits are zero.\n\n-L667: For (B16) you do not telescope the bound (B2) but just use that \\pi_k is in \\cB?\n\n-L678: Can you explain why you need the indicator 1_{\\cE_n} to get (B.24)?\n\n-L700: + is missing in (B.32). And you should also detail quickly why the different sums are bounded for the choice of the parameters.", "limitations": "see Strengths And Weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Contributions:\n-flexible algorithmic template for the analysis of policy gradient methods,  novelty: low, relevance: low.\n-O(1/\\sqrt(n)) rate of convergence of policy gradients method with reinforce gradient estimate towards second-order stationary equilibrium Nash equilibrium,  novelty: medium, relevance: medium.\n-Finite-time convergence for a lazy version of the policy gradient methods toward a deterministic Nash equilibrium, novelty: medium, relevance: medium.\n\n\nThe paper is well-written even if some notations could be clarified, see specific comments. It could be interesting to ground the considered setting with a concrete example, see specific comments. Similarly, the claims are obtained through a cascade of hypotheses that are not exhaustively discussed and justify. The proofs seem correct at least in the part I read. The related work could be improved. For example, the author may also want to compare the obtained rate with the rate obtained by Jin et al. (V-Learning—A Simple, Efficient, Decentralized Algorithm for Multiagent RL , 2021) and reference therein since they seem to consider the same setting. It would also be interesting to discuss the results to provide lower bounds on the rate of convergence toward a Nash equilibrium. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eVLDI79jYHu", "reviewer": "Reviewer_uYSS", "summary": "This paper studies the convergence of the policy gradient method for a class of MDP problems. The equilibrium point investigated is the second-order stationary point, which is a popular notion in the optimization literature.\n", "questions": "(1) Most real-world applications do not have a random stopping time $T$. The authors should better motivate and justify this setting. In addition, it is well known in the stochastic control literature that a control problem with a random stopping time sampled from an exponential distribution with rate lambda corresponds to an infinite-time horizon problem with discount factor lambda. The authors should make the linkage between these two classes of problems if there are any.\n\n(2) Lemma 2 is listed without proof. This is an important building block that later results rely on. I doubt whether the PL condition could hold (as stated in Lemma 2) without additional assumptions. It is well-known that the PL condition does not hold for the general two-player linear-quadratic zero-sum game case and some carefully constructed conditions are required [1]. General-sum game [2] and MDP games [3] are much harder problems and I am surprised to see that PL condition holds almost for free in Lemma 2.\n\n(3) The convexity of the projection set is never discussed. When $\\Pi$ does not enjoy good properties, finding the projected point can be NP-hard.\n\n(4) In Theorem 1, the authors assume that $\\pi^*$ is a stable Nash policy. However, the authors never verified under what verifiable conditions the original problem has a Nash equilibrium policy and under what conditions it is unique. Similar issue also appears in Theorem 2. The authors never discussed the sufficient conditions for $\\pi^*$ to be SOS. This leads to the danger that the main results (Theorems 1 and 2) may never be applicable.\n\nMinor comments:\n\n(a) The $a_t$ in Eqn (1) should be replaced by $\\alpha_t$ based on the definition. \n\n(b) Stopping time $T$ is not mathematically rigorously defined (i.e., the adaptiveness).\n\n(c) Please be precise with what you mean by ``realized values’’ in line 217. I understand you refer to the instantaneous rewards but it is a bit vague in the statement.\n\n[1] Zhang, Kaiqing, Zhuoran Yang, and Tamer Basar. \"Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games.\" Advances in Neural Information Processing Systems 32 (2019)\n\n[2] Mazumdar, Eric, et al. \"Policy-gradient algorithms have no guarantees of convergence in linear-quadratic games.\" arXiv preprint arXiv:1907.03712 (2019)\n\n[3] Xie, Qiaomin, et al. \"Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium.\" Conference on learning theory. PMLR, 2020\n=========\n==========\nI have read the reviews from other reviewers and the responses from the authors. The authors have addressed my concerns and I raised my rating to 6.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: The topic studied in this paper is no doubt interesting and meanwhile challenging. Instead of adopting the first-order condition (KKT) used in most of the game papers in literature, this paper borrows the idea of a second-order stationary point from the optimization community and established the corresponding framework to understand the well-definedness and learning behavior in the stochastic game regime. The authors establish asymptotic convergence (in high probability) for a class of MDP games.\n\nCons:  However, I have some concerns regarding (1) the generality of the set-up (especially on the stopping time), (2) verifiability of the assumptions, and (3) key steps with missing proofs.\n\nDetailed questions that require clarifications are listed below.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e2MeCNkI7ra", "reviewer": "Reviewer_kenS", "summary": "This paper studies the local stability of stationary Nash equilibria under the projected gradient (PG) algorithm in episodic finite (states and actions) stochastic games under various assumptions on the players observations --full, intermediate (stochastic gradient) or low (value based)-- Form the fact that stationary equilibria of finite stochastic games satisfies a version of Polyak-Łojasiewicz condition (a consequence of the semi-algebraicity), stationary Nash equilibria satisfy a gradient dominance property which easily implies that equilibria can be expressed as solutions of a variational inequality (VI). The rewriting of the equilibrium condition as a VI allows to classify the stability of Nash equilibria from stable, to second-order stationary (as in Mertikopoulos, Zhou Math Prog 2019). They then use the variational inequality conditions to establish their main results, namely 1) if an equilibrium is Nash stable, then if one starts closely to it, PG converges to it with high probability 2) when the equilibrium is second-order stable then the convergence time can be estimated (roughly 1/n or 1/n^1/2)...This rate can be improved to finite time convergence for pure stationary equilibria.", "questions": "- Can this result be coupled with the one (in zero-sum and potential stochastic games) where best iterate convergence results have been proved? namely, can we deduce from your analysis a convergence a global convergence is some zero-sum and potential SGs --\n\n- Can you give some non trivial examples of finite stochastic games with a stationary equilibrium which is second order stable (or stable) without being strict or the game zero-sum?\n", "limitations": " - Can you please discuss the classes of games, beyond the class of stochastic games, where your results apply?\n\n- Can your results extend to ergodic stochastic games -where there is no ending, and the learning is obtained during the play-?", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: this is an excellent paper. It shows the local stability of stationary Nash equilibria under the projected gradient under several observational assumptions whenever that Nash equilibrium has some additional stability properties. The fact that it uses only the variational inequality property of the Nash equilibrium implies that the result extend to a wider class of game, beyond the one studied in the paper (for example concave continuous games as studied in Mertikopoulos, Zhou 2019). The main difference with the MZ paper is that MZ studies Online Mirror Descent while this paper studies projected gradient descent. \n\n\nSome weaknesses: only local convergence results, only on a subclass of stochastic games (episodic stochastic games). Also, It seems to me that the existence of stable and second order stationary equilibria in finite stochastic games is rather hard to obtain (outside strict pure equilibria or zero sum games).", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept