Can We Find Nash Equilibria at a Linear Rate in Markov Games?
Authors: Zhuoqing Song
Jason D. Lee
Zhuoran Yang
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Multi-Agent Reinforcement Learning
Markov Games
Linear Convergence
Policy Optimization

Abstract: We study decentralized learning in two-player zero-sum discounted Markov games where the goal is to design a policy optimization algorithm for either agent satisfying two properties. First, the player does not need to know the policy of the opponent to update its policy. Second, when both players adopt the algorithm, their joint policy converges to a Nash equilibrium of the game. To this end, we construct a meta-algorithm, dubbed as $\texttt{Homotopy-PO}$, which provably finds a Nash equilibrium at a global linear rate. In particular, $\texttt{Homotopy-PO}$ interweaves two base algorithms $\texttt{Local-Fast}$ and $\texttt{Global-Slow}$ via homotopy continuation. $\texttt{Local-Fast}$ is an algorithm that enjoys local linear convergence while $\texttt{Global-Slow}$ is an algorithm that converges globally but at a slower sublinear rate. By switching between these two base algorithms, $\texttt{Global-Slow}$ essentially serves as a ``guide'' which identifies a benign neighborhood where $\texttt{Local-Fast}$ enjoys fast convergence. However, since the exact size of such a neighborhood is unknown, we apply a doubling trick to switch between these two base algorithms. The switching scheme is delicately designed so that the aggregated performance of the algorithm is driven by $\texttt{Local-Fast}$. Furthermore, we prove that $\texttt{Local-Fast}$ and $\texttt{Global-Slow}$ can both be instantiated by variants of optimistic gradient descent/ascent (OGDA) method, which is of independent interest.

Published as a conference paper at ICLR 2023
CAN WE FIND NASH EQUILIBRIA AT A LINEAR RATE IN MARKOV GAMES?
Zhuoqing Song
Jason D. Lee
Zhuoran Yang
Fudan University
Princeton University jason aasoniee@prii se@princetton..o wnn.nnnnnnnc.m edu
Yale University zhuoran. eanoraanyanggyale.edl
zesongl 90 fudunn. edu.eduuc cn
ABSTRACT
We study decentralized learning in two-player zero-sum discounted Markov games where the goal is to design policy optimization algorithm for either agent satisfying two properties. First, the player does not need to know the policy of the opponent to update its policy. Second, when both players adopt the algorithm, their joint policy converges to a Nash equilibrium of the game. To this end, we construct meta algorithm, dubbed as Homotopy-PO, which provably finds Nash equilibrium at global linear rate. In particular, Homotopy inter- weaves two base algorithms Local-Fast and Global-Slov via homotopy continuation. Moocal-Fast is an algorithm that enjoys local linear convergence while Gl Global-Slow is an algorithm that converges globally but at slower sub- linear rate. By switching between these two base algorithms, Global-Slow es- sentially serves as a "guide" which identifies a benign neighborhood where Local-Fast enjoys fast convergence. However, since the exact size of such a neighborhood unknown, we apply a doubling trick to switch between these two base algorithms. The switching scheme is delicately designed so that the aggregated performance of the algorithm is driven by Local-Fast. Further- more, prove that Local-Fase and Global-Si -Sllow both be instantiated by variants of optimistic gradient descent/ascent (OGDA) method, which is of independent interest.
INTRODUCTION
Multi-agent reinforcement learning (MARL) which studies how group of agents interact with each other and make decisions in shared environment (Zhang et al.] (021a) has received much attention in recent years due to its wide applications in games (Lanctot et al. 2019: Silver et al.
2017 Vinyals et al. 2019), robust reinforcement learning (Pinto et al. [2017 Tessler et al. 2019 al. 2016 Matignon al.
2012), among many others. Problems in MARL are frequently formulated as Markov Games (Littman 1994 Shapley 1953). In this paper, we focus one important class of Markov games: two-player zero-sum Markov games. In such a game, the two players compete against each other an environment where state transition and reward depend on both players' actions.
Zhang et al. 2021b), robotics "Shalev-Shwarle
Our goal is to design efficient policy optimization methods to find Nash equilibria in zero-sum Markov games. This task is usually formulated a nonconvex-noncoocave minimax optimiza- tion problem. There have been works showing that Nash equilibria in matrix games, which are special kind of zero-sum Markov games with convex-concave structures, can be found linear rate (Gilpin et al. 2012) Wei et al., 2020). However, due to the www.oovvexxtyynnnncccviiiii retical understanding of zero-sum Markov games sparser. Existing methods have either sublinear rates for finding Nash equilibria, or linear rates for finding regularized Nash equiliria such as quantal response equilibria which are approximations for Nash equilibria (Alacaoglu et al. 2022 Cen et al.)
theo-
2021 Daskalakis et al., 2020; Pattathil et al. 2022; Perolat et al. 2015 Wei et al. 202 Yang & Ma 2022:22222 Zeng et al. 2022 Zhang et al. 2022 Zhao et al. 2022). A natural question is:
Q1: Can we find Nash equilibria for two-player zero-sum Markov games linear rate?

---

Published as a conference paper at ICLR 2023
Furthermore, in Markov games, it is desirable design decentralized algorithms. That is, when player updates its policy, it does not need to know the policy of other agents, as such information is usually unavailable especially when the game is competitive in nature. Meanwhile, other desiderata in MARL include symmetric updates and rationality. Here symmetry means that the algorithm employed by each player is the same/symmetric, and their updates differ only through using the different local information possessed by each player. Rationality means that if other players adopt stationary policy, the algorithm will converge the best-response policy (Sayin et al. 2021 Wei et al. 2021 In other words, the algorithm finds the optimal policy of the player.
In decentralized learning, each player observes dynamic local information due to the changes in other players' policy, which makes it more challenging to design efficient algorithms (Daskalakis et al.] 2020; Hernandez-Leal et al., 2017: Sayin et al. 202T). Symmetric update also poses chal- lenges for the convergence, [ondon (990)) shows multiple variants of value iteration with symmet- ric updates can cycle and fail to find NEs. Gradient descent/ascent (GDA) with symmetric update can cycle even in matrix games (Daskalakis et al. 2018: Mertikopoulos al. 2018). Thus, an even more challenging question to pose is:
Q2: Can we further answer Q1 with a decentralized algorithm that is symmetric and rational?
In this paper, we give the first affirmative answers to Q! and Q2. In specific, we propose meta algorithm
which provably converges to Nash equilibrium (NE) with two base algorithms Local-Fas and Gl cllalllSlo Homotopy-PO is a homotopy continuation style algorithm that switches between Local-Fast and Global-slow, where Global-Slow be- haves as a "guide" which identifies a benign neighborhood for Local-Fast to enjoy linear con- vergence. novel switching scheme is designed to achieve global linear convergence without knowing the size of such neighborhood. Next, propose the averaging independent optimistic gradient descent/ascent (Averaging OGDA) method and the independent optimistic policy gradient descent/ascent (OGDA) method. Then, instantiate Homotopy-Po by proving that Averag- ing OGDA and OGDA satisfy the conditions of G1 This yields the first algorithm which provably finds Nash equilibria in zero-sum Markov games at global linear rate. In addition, Homotopy-Per PO is decentralized, symmetric, rational and last-iterate convergent.
and Local -Fast, respectively.
Our contribution. Our contribution is two-fold. First, we propose a meta algorithm Homotopy-Pee which is shown to converge Nash equilibria of two-player zero-sum Markov games with global linear convergence, when the two base algorithms satisfy certain benign prop- erties. Moreover, oomotopy-PO is a decentralized algorithm and enjoys additional desiderata in MARL including symmetric update, rationality and last-iterate convergence. Second, we instantiate Homot.opy-PO by designing two base algorithms based on variants of GDA methods, which are proved to satisfy the conditions required by Homotopy-Po In particular, we prove that the ex- ample base algorithm OGDA enjoys local linear convergence to Nash equilibria, which might be of independent interest.
1.1 RELATED WORK
A more comprehensive literature review is moved to Appendix A due to the space limitation. Of particular relevance are two decentralized algorithms Daskalakis al. (2020) and Wei et al. (202T).
Daskalakis et al. (2020) consider an independent policy gradient descent/ascent algorithm which is a natural extension of kingle-agent policy gradient descent two-player zero-sum Markov games. They utilize the two-sided gradient dominance prove a sub-linear convergence rate of the gradient- descent-ascent (GDA) method. This is the first non-asymptotic convergence result of GDA for find- ing Nash equilibria in Markov games. However, their method is asymmetric, where one one-player takes much smaller steps than its opponent. And their convergence results are base on average policies with no explicit guarantee for last-iterate convergence. Wei al. (02T) propose optimistic policy gradient descent/ascent algorithm that is simultaneous decentralized, symmetric, rational and has (11vVt) last-iterate convergence rate to the Nash equilibrium set. They use a critic which averages the approximate value functions from past iterations to tame nonstationarity in ap- proximate Q-functions and get better approximations for policy gradients. classical averaging stepsize from Jin al. (018) is utilized by the critic that the errors accumulate slowly and last-
actor-critic
2

---

Published as a conference paper at ICLR 2023
iterate convergence is obtained. However, the critic using such choice of stepsizes throughout the game also destroys linear convergence since relatively large errors from past iterations cannot decay fast enough and will harm the accuracy of more recent steps.
NOTATIONS AND PRELIMINARIES
For integers n n', denote [n n') = {n, 1,... nn' and [n] (1,... ,n). We use |I-I| to denote the Fuclidean norm, and -1 denotes the f--nomm. For any vector x E IRd and closed convex set C C Rd let Pe (z) denote the unique projection point of x onto C. addition, the distance between and C denoted by dist C) æ Pc (x)]l-
Markoy game. A two-player zero-sum discounted Markov game is denoted by a tuple MG = (S, A, B, P. 7) where S [S] is the state space; AA [A] and B [B] the action spaces of the min-player and the max-playe respectively; IP S x A x B - As is the transition kernel, R [es S [0, 1|4xB the reward function, and y is the discount factor. Specifically, state when the min-player takes action and the max-player takes action b at state s, P(s'|s |s, a, b) is probability that the next state becomes s', Ra, b) is the reward received by the max-player, and the min-player receives loss R.(a, b). We assume that the rewards bounded in [0, 1] without loss of generality.
Let æ { and y {ye)ees denote the policies of the min-player and the max-player where v, E AA and y, E As. The policy spaces of the min-player and the max-player are denoted by X (Aa)² y (AB) Let Z X y denote the product policy space. The policy x E X' (y E D) is treated as an AS-dimensional (BS (3S-dimensional) vector, and the policy pair (x y) is treated
(A + B)S -i-dimensional vector where 2, (æ ys) represents (A + B) dimmensiona vector by concatenating x, and y.-
The value function under the policy pair (z. y) is defined an S-dimensional vector with its tries representing the expected cumulative rewards: (=) Ez, FEz.vIErs R. (a', b²) 0s0 = s). Define V=.l (Vi.)) as the value functions of (z) with its best response, i.c., Va.((s)
max V2.y (8), (x) = ming'x V² - (s). For state E S, define the Bellman target oper-
ator Q R > Ax such for vector v TR.S.
(v(v(aabb) ba + P(
e'ES
The Q-function -. (Q. ).es is defined as a collection of A-by-B matrices with Q
Q, [a.v]. The (state) visitation distribution is defined as d= Σ " 80
s). For any distribution p As. we abbreviate (e.((p) = P(s) d3 (8)
Evesp such that for any policy pair z (x, E Z and s E,
From Gilpin et al. 2012)), there problem-dependent constant C+ >
max x. Qiv. EEA
min x' Q.y, E,AAA
T.Q.y. 2 c+ dist(z,, Zz).
(1)
Nash equilibrium. The minimax game value of state is defined (s) millee maxyey (s) = maxyey minnax (e. A policy pair (æ, y) is called a Nash equi- libirum (NE) if and only if: for any S. (al = V (s).
Define the minimax Q-functions as Q: = Q.(v"). Define the sets X and V as
X arg min max (z',, Qi y = arg max min (a', Q'v()) viEDs x'EAA
æ E yAEAA
Then X and yr are non-empty, closed and convex. Denote 2 = X yr Let X
II ses X
y = II.S Dj. z II Z A policy pair (æ" y²) attains Nash equilirrium if and only (x+ (x*.y") E Zz, i.e. (#;, y E z for any S (Başar & Olsder 1998 Filar Vrieze 2012)
We denote the closure of the NE set's neighhorhood B(2", c) (2 2 dist dist(z, 2n) S c).
3

---

Published as a conference paper at ICLR 2023
Interaction protocol. In each iteration, each player plays a policy and observes the marginal reward function and the marginal transition kemel,, i.e. in iteration t, the min- plays x' E XX while the max moxxepayerppp plays y Y. The min-player receives the marginal reward function r :SxA - [0. 1] with r (8,a) = EeES (b) Rs (a, b) and marginal transition kernel P. : S x A + As with P. (5'1ss a) = LE y (b)) |s, a, b). while the max-player receives ry and P which are defined analogously. Each player is oblivious its opponent's policy.
3
A HOMOTOPY CONTINUATION ALGORITHM WITH GLOBAL LINEAR CONVERGENCE
We propose a decentralized algorithm with global linear convergence by (1) proposing meta algo- rithm which can achieve global linear convergence with two base algorithms, (2) providing examples for the base algorithms. The analysis for the example base algorithms are in Section and Section
3.1 A HOMOTOPY CONTINUTATION META ALGORITHM
We present homotopy continuation meta algorithm. It can achieve global linear convergence by switching between two base algorithms: Global-Slow base algorithm (Global 1-11 ow) and Local- Fast base algorithm (Local Fast). Global -lllww-lwww is globally convergent, but only attains Ö(7) rate. Local-Fast is not necessarily globally convergent but attains linear convergence rate in a neighborhood of the Nash equilibrium set.
Global-Slow base algorithm: by calling Global- Global-Slow(I)
2n") during time interval
[Zi : Ty] where ž = (z, 5) is the initial policy pair, the players play policy pair z² ===6 (x', yy)) for
each iteration / [Ti 'T2), and compute an average policy pair g(Ti-Ta] (a (Tr:Tal) y (TTi.Ta)) the
end of iteration T- such that 2², T[Ti:Ta) satisfy the following two properties:
global convergence: there is groblem-depentee constant C" > 0 such that
C' log(T2 - Ti +1
dist M1:23] Z²) <
(2)
(T2 Ti +
This property means the average policy produced by Global-Slow converges to the NE set at a sublinear ((1TT) rate.
geometric boundedness: there exists problem-dependent constant Do > (possibly Do 1) such that if of < then for any E [Ti 772) dist (2' (²) < Do-Ti dist dist (2 (T.)) 2n) S D T- dist (2,
(3)
(4)
This property ensures that the iterate z' at any intermediate time and the average policy glrr do not diverge faster than geometrically from the NE set. In Global-Slow {2') he)T, are the
policy pairs played during [Tr T2), while & (TiiT will mainly be used the initial policy in the next switch to Local-Fass in the meta algorithm Homotopy-PO (Algorithm I.
Rocal-Fast base algorithm: by calling Local Local-Past((T; T2], 2, n) during time interval [Ti Tal where = (8, ②) the initial policy pair, the players play policy pair x' = (x', y²) for each
iteration E T T22 such that z' satisfies the local linear convergence property:
local linear convergence: there exist problem-dependeed constants co E (0, 1) and 8, To > such that if dist? 2 (2, (2,2*) < 6on", then for any t E [T1 Tz)
dist? Z²) To (1 =) Ti dist (2, Z*).
(5)
In other words, if initialized a neighborhood of z with radius / 6om Local-oaaasssoo.ooo converges to I at a linear rate.
With these base algorithms, a naive and impractical approach is to run Global Slow first un- til x reaches B(Z", / ). and then, run Local-Fast to achieve linear convergence. How- ever, the problem is do not know the value of do- That is, when running the algorithm, since
4

---

Published as a conference paper at ICLR 2023
2" is unknown, it is impossible tell whether the algorithm has reached the benign neighbor- hood for Local-Fast to enjoy the linear rate Thus, we cannot decide when to switch from Global-Slow to Local-Fast.
Algorithm 1: Homotopy a meta-algorithm with global linear convergence
Input: iterations: [0: T). initial policy pair: 20 2, stepsizes: 17, n/ > 0
set k 1, - 1, - 20
while 7k-1 < do
1f
I = - -
1,
T gs
min (T+s + 2 1,,,, I
+ +1, = min + + - 1,7)
R=
during time interval [Tg. T... run Global-Slow
I
بل -4-1
, and compute an
gs
average policy 2 - [xx]
during time interval [Z] 7h,, run Local (IZ
-/] 2 2T
+ 11
end
To overcome this problem, we propose a homotopy continuation method Homotopy-Po which smartly switches between Global Mlobal-Slow Slow and Local-Fast The pscudocode is in Algorithm In Hcmotopy- PO, we split [0 7] into the segments:
[0: 7 = [T I U ZHJ U
I Ra
[
U
where IZg. I the time interval of the k-th call Global-Sl and |
I 2";
[I Zh]] is the time interval of the k-th call to Loca 1 Fast and
[ Z = 4 The switching
scheme of Homotopy-PO method can be summarized as below: starting from k =
(Step 1) during time interval [T Igal. run Global-Slow for I Th
= 2 iterations with
the initial policy 2 (for k 2 1, it is the last-iterate policy of the last call to Sical-Fastt
(Step 2) during time interval [ T run Local-Fast for | T
= 4 iterations with the
initial policy z!zt, -ipl that is the average policy of the last call to Global - Slow
(Step 3) k k + goto Step 1.
Now, we elaborate on how Homot achieves global linear convergence given Global-Slow base algorithm and Local-Fast base algorithm. Specifically, there are two hidden phases which are oblivious to the players and only used for analysis. The two phases are split by h = max(k;, ki), }. where 2 ((1/(V6pm) and 2 O o log (DD))) Ō(1/(cun²)). The value of k* is unknown the players.
Hidden Phase I. In the beginning, clobal-Sle behaves like a "guide" in the sense that its aver- age policy 2 - is getting closer to the NE set as k goes. For small dist(2", 2*) could possi- bly increase when running Mocal-Fass However, since the average policy 2 17 :igh is the initial policy of the k-th call to Llocal-Fasee by the global convergence in for kf, 214h It will reach ( / )) Thus, after kj. each time when we switch Local-Fase will exhibit linear convergence during time interval [Z]] I+]
Hidden Phase II. After k ke Local-Fast enjoys fast linear convergence and becomes the main contributor to the convergence (see segments AB, CD in Figure D. Thanks to the fast vergence of Local -Fost, in this phase, d 2*) can be much smaller than C²/l. Note that
z - the initial policy of the k-th call to Global-Slos Thus, Global-Slon could possibly cause dist(=', 2²) to increase. However, instead of bounding dist(z', by (2). now 3 can provide tighter bound for dist(z', , 2²) when calling loooallss.. during Hidden Phase II. 3 implies that dist(z*, 2 Z²) increases at most geometrically when running Global-S Slow (see segments BC, DE in Figure D After 2 Z O( log(Dol')) (k > kg)), the possi- ble increase of dist(z', 2*) caused by Global -S much less than the decrease caused by

---

Published as a conference paper at ICLR 2023
2*) converges rate of cot for |[ f 4 iterations, while in BC, dist (z', 2*) diverges at rate of Do for | + = 2 iterations. Then, since 4 4k/2k+1 = 2k-1, if one step in- crease of Global- is much smaller than 2 steps of decrease of Local -ast, i.e., then, we obtain the global linear convergence (see the line AC in Fig-
Local-Fast, and thus, be "omitted". More specifically, in AB, dist (z', dist"(z',
Po - /2)= u.
Hidden Phase I has most O steps, where O(4k)) is polynomial in C², C/.1/0,, 1/60. 1/n.1/n 1/n' and only loga- rithmic Do, To. Then, enters Hidden Phase II and linear convergence begins. This yields the global linear convergence. The formal proof is deferred to Appendix
(og(dist(=',2 22))
global linear rate Local-Fast Global-
Theorem Let
=z'=(x', y') y')
be the policy pairs played when rumning Homot Homotopy-PQ -P (Algorithm [ Then, there exists problem-dependent constant D S Oppoly(C', 1/ca, 1/8g, 1/n, 1/r/)) such that for any [0 T), we have dist 2*) S t-D
1oth call to 18++ 12-4 call to (R 13th call to Lacal -host Globnl-81am
- 2)-th call to 0loba1-S1oc
where the value of C", co. dp. l' can be found the defi- nitions of Global-Slle -Slow and Local-Fast.
2S max (o.
(1 (1- (1==2²)
Lecal-Fact
Figure 1: An illustration of upper bound for log(dist(2', 2*)) in Hidden Phase II.
As D is independent of f, Theorem D guarantees the global linear convergence of Homotopy-PO.
3.2 EXAMPLES OF BASE ALGORITTM
We introduce the averaging independent optimistic gradient descent/ascent (Averaging OGDA) method and the independent optimistic policy gradient descent/ascent (OGDA) method which will serve as examples for Clobal-S1 ow and Local-Fast respectively. Both Averaging OGDA and OGDA are symmetrie, rational and decentralized algorithms. The pseudocodes are in Appendix G
Example of Global-Slow base algorithm (Averaging OGDA), By running (#, 9). the min-player initial-
T2), 2,y)) with initial policy izes I = x = & and (=1(s) (x))(s), the max-player initializes y = y = D and
Everaging-OGnn
V (s) vātt(s) and they update for E [Ti + 1 Ty] as follows:
[-1
(s) min dEA j=Ti
Σ
+- g,(a),
Σ
4-Ti+1 O
(b())
max BEB
j=T:
x. = PAr
[--1
1/ 9 1111)
34 = PAr
h--1
V
+ 1 q. ) )
(6)
8/ PAA
x111 -144))
J. = PA
(-1-1 1/ 9
where q. = V' V / = Q. 1 æ5. and Q.H- is the Bellman target operator defined in the introduction part. The min min-player and the max max-player compute the average policies
Tz
T2
Σ
T-T++1
1-T++ 1i--i++1
(7)
t=
We use the classical averaging stepsizes {a{} from Jin et 2018
H+l of
a;
#+!
oj Ie (1-ak) (1 < j t- 1), of an, with H 14%
In Averaging OGDA, x',
y

---

Published as a conference paper at ICLR 2023
the policies played iteration L [7] T2]. and x², L' V are local auxiliary variables help to generate such sequences of x', y" The global convergence and geometric boundedness of Averaging OGDA are shown Section The RHS of 2 in the definition of Global SabbllSSlww can be directly extended to different convergence rates and more algorithms such as Wei et al. (2021) with a different initialization can serve as the generalized Global-S1es More details are in Appendix H
Example of Local-Fast base algorithm (OGDA). By running OGDA([7) T2l, with initial policy = =w. ÿ). the min-player initializes xh = x = ह, the max-player initializes y
y y. and they update for t [2] + T2] as follows:
a: PAd
11 2 y. )
y PAs T
+ (Q')))
x t
(8)
2. Par
st-1 F
17 Q'.0¹²)
y, PAU
htt-1 ys + 11 (Q.) x²!)
where we abbreviate Q' = Q. for E [71 : Tz]. OGDA, x', y² are the policies played at iteration 1. E [Ti 72], while x' y" are local auxiliary variables. OGDA can be considered as a natural extension of the classical optimistic gradient descent/ascent Markov games because when there is only one state (S = 1), it reduces to the classical OGDA method for matrix games.
The proof for local linear convergence of OGDA is of independent interest and shown in Section
3.3 GL.OBAL LINEAR CONVERGENCE.
We can instantiate the meta algorithm Homot opy-t by using OGDA (8) as Local-Fast and Averaging OGDA (6) as Global- Slow. This gives the provable global linear convergence for zero-sum discounted Markov games as in Theorem 2 In practice, Homo t topy-PO can also exhibit linear convergence. Our numerical experiments are appendix[]dus the space limitation.
Theorem (Global Linear Convergence) Let {z (x', "..''))))) y')rreoor be the policy pairs played
when rumning Homotopy-PO (Algorithm Z where Local-Fan uses OGDA with s (1-))² 32v 32 and Global -S] uses Averaging OGDA with 1// S moxxxAA Then, there exist problem-dependent constants (0, 1) and M >> 0 such that for any L [0: T].
1-y
165
log (SAB/ee4m)))
(2t," Σ 1 1-7
(1 11-m1 ==
where c S(C. A, B, 1/(1 ())) and M = A, 1/cc).
Decentralized implementation. Since both OGDA and Averaging OGDA symmetric, ratio- nal and decentralized, our instantiation of Homotopy-PO is naturally symmetric, rational and decentralized algorithm. Pseudocodes and more details be found in Appendix G
Linear rate comparison with matrix games. For the convex-concave matrix games, Gilpin et al. 2012 and Wei et al. (2020) propose centralizee//decennraaizz
methods with global linear rates of (I O ((p()))))))))))))) G) and (I O(p(G G))) respectively, where s G) is a certain condition mea- sure of matrix G. Details of sp( G) are in Lemma 22 The constant C4 in ( can be naturally defined as = min,es sp( Q.)) (see Corollary 2 Thus, the global linear convergence rate for zero-sum Markov games Theorem is comparable solving matrix games up to polynomials in
S, A, B, 1/(1 7)).
4 GLOBAL CONVERGENCE AND GEOMETRIC BOUNDEDNESS OF AVERAGING OGDA
We show that the Averaging OGDA (6) method has Olog T /T) global convergence rate and geo- metrie boundedness. Thus, Averaging OGDA can be serve as Clobal-Slow in Homotopy-PO.
Global convergence. The proof for global convergence of Averaging OGDA adapts several stan- dard techniques from Markov games (Zhang et al. 2022 Wei et al. 202T). We attach its proof in Appendix D.I for completeness.

---

Published as a conference paper at ICLR 2023
Theorem (Global Convergence) Let 2 [T..Tal (T(Ti:Ta) 8 (2))) be the average policy 7 gen-
erated by running A pagaaaiinngnGD((([ T2], n') with n/ S Tomax[A,By There is problem-
dependent constant C" = (0 (1 such that 2TTa:Tal satisfies
C' log (T2 Ti +1) 7 (T2
dist (2 ( 2*)
(10)
Ti +
This gives the O(1/T) global convergence rate of Global SabbalSSlow. Slow. This property guarantees that Global-Slow can serve "guide" in Hidden Phase as described Section 3.1
Geometric boundedness. The proof of geometric boundedness mainly relies on the stability of projected gradient descent with respect to the NE set (Appendix B). We will prove that the in- crease of dist(2z', )*) is at most geometric by providing mutual bounds among {dist (z*, Z*),,
(dist(2', ), AIV V' (max; (b) min, g (a)} inductively. The formal proof is in
Appendix D.2
Theorem (Geometric Boundedness) Let (z (T(T, 2 (Ta.Tal be the policy pairs played and the average policy pair generated by running A www.rrgiiggoooaaa (Ta,, 2,11) with vf S then there is problem-dependent constant Do = 0 (1-))) (possibly Do > 1) such that for any t EEW [Tr T2).
dist (=', 2*) S D0- D dist 2 (2,
(11)
dist dist? 2²) ( D Ti dist ( Z*).
(12)
This property is important in proof for the main theorem (Theorem It means that when running Global-Sall SSlowwlwwii in Hidden Phase II, though dist(z', (*) can possibly increase due to Do > 1, dist( 22, Z²) can only increase geometrically (see segments BC, DE in Figure
5 LOCAL LINEAR CONVERGENCE OF OGDA
We show that OGDA 8 has local linear convergence. Thus, OGDA can used as the base algo- rithm Local-Fast in Homotopy-PO To prove the local linear convergence, we provide novel analysis for OGDA which starts from the following two observations.
Observation I (Lemma saddle-point metric subregularity (SP-MS) can be generalized to Markov games, i.e., for any policy pair E 2 and 8 E S,
z.
vi (s) 2 .ist(z,, (s)
(13)
Observation guarantees the progress of projected gradient descent/ascent (PGDA) substantial.
Observation II (Appendix B Lemma I0 when running OGDA (8), the change in policy pair be-
comes smaller when z² zz are approaching the NE set, i.c.,
(+1 212
(1-1)) O(dist((z' 3z) + | - 11-)
(14)
Observation II implies the stability of state visitation distribution. Intuitively, it can help relate Markov games to matrix games in a neighborhood the NE set.
Theorem (Local Linear Convergence) Let {2 Jeerrer be the policy pairs played when running
(1-y)
OGDA([Ti T2], 2,)) with stepsize 17 S 32+B(A Then, there are problem-dependeed constants
c E (0, 1), & such that if dist? (2, Z+) & 8n then for any 2 Tí.
85 [ con" T-Ti
dist? (z' 2²)
dist (2, Z",
(15)
I I-
where co = DCC.. A, B, 1/(1 7))) and 6o 4c44/ooly(S A, B. 1/(1 (/(1-))))
8

---

Published as a conference paper at ICLR 2023
We provide proof sketch below. The formal proof is in Appendix
Proof sketch Proofk
of Theorem 5 We denote the projections by x² = Px- (x"), =
Pz- (2'). Let Pu be the uniform distribution on S. Our proof for the local linear convergence of OGDA has the following steps.
Step I: One-step analysis (Appendix C.1 The main obstacle in adopting standard analysis for nor- mal form games to Markov games lies in the fact that as Markov games are nonconvex- nonconccve,
it may happen that (x++1 x,- Q y g++1)
yy
gt (Q.+) xtt1 < O.
To overcome this problem, our strategy to consider a weighted sum of (z!+) =x"", Q. y
and (x.* - y.- (Q att1). As (x" "²") attains Nash equilibrium, Vall 3"' (po)
V nhtl (po) 2 0. Then, by applying performance difference lemma (Lemma 20 have
d (s) ( (z)t1 x at y
1+1 + d (s) V v (2x+)))) T 1+1 ) 2 0, (16)
#ES
where d'(()) d= d w' (8) and (s) = d= ()
(x) for 1 1>> T2-
Since Q¹ is smooth in z', we can adopt standard regret analysis for optimistic gradient descent in normal form games to bound ( (x++1 x Q++1 y and yx vs+ (Q'+1) x++1 This
yields the following inequality (which is equivalent to Lemma 4
=11 - Cx -C( 11 + 11 CA || 2
A SA' +
O'-
z" 12), (17)
Step stability d' di
Step II: progress PGDA
where CA = 45 O¹ =
Eses d' (s)dist
+ (s) Vo). O'
ELes d=
y a (s)dist 2 (7 X²) t (s)dist (V's VT), and A = O +C 3' z" As (s)
(s) 2 to show the local linear convergence of OGDA, it suffices to show that for A
Step II: Progress of projected gradient descent (Appendix C.2
We combine 13 from Obser-
vation and standard analysis of projected gradient descent (Lemma exists problem-dependent constant 4 O (ec/nn/poll /pol:/ollySSS. B, 7))) such that
5 to essentially show that there
CA Cal
3z' 1 + + ' 2 4 O
(18)
Step III: Stability of visitation distribution near the NE set (Appendix
Using (4) from
Observation II and the non-expansive property of projections onto convex sets, we will show || 1==+1_ =1122 + || z(t-1><112 < 0 (A'-1). Then, as d' (s), d' (s) in (16) are continuous in x' and z", we can find a problem-dependen constant 8 O(e hwlp//ollysss.. A, B, 1/(1 7))) such that if At 1 < 8, then Q. can be bounded by
aC S (1 + - O 2
(19)
Step IV: Induction (Appendix C.4 By 18) 199 from Steps I, II, III above, intuitively, we can deduce that when A
(-11
< ô, the "one-step lincar convergence" achieved
d 0
CA ||' 2²112 - 0' = - c L0' -
CA
A 1+1
-'' -212 2912
2
2
2
2
SA min {
2
1
(0'
+ CxIl=' - z' - 1P1 2119)= - )
2
2
By a coupled induction with Step III, given the initial policy 2 in the neighborhood B(z vo) of the NE set, the policy pair z' will always stay in B(Z", Vō). Then, A' converges linearly.
This yields the local linear convergence of OGDA as in Theorem 5

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
We would like to thank anonymous reviewers for their helpful comments.
REFERENCES
Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum markov games. In International Conference Machine Learning, pp. 307-366. PMLR, 2022.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national conference on machine learning, pp. 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-
optimal reinforcement learning. Journal of Machine Learning Research, ((O0et):2132333 2002.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:27952- 27964, 2021.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero- sum linear mixture markov games. In International Conference Algorithmic Learning Theory, pp. 227-261. PMLR, 2022.
Anne Condon. On algorithms for simple stochastic games. Advances in computational complexity theory, 13:51-72, 1990.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations (ICLR 2018), 201 8.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances neural information processing systems, 33: 5527-5540, 2020.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Andrew Gilpin, Javier Pena, and Tuomas Sandholm. First-order algorithm with (In(1/e)) con- vergence for e-equilibrium in two-person zero-sum games. Mathematical programming, 133(1): 279-298 2012.
Pablo Hermandez-Leal Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A sur- vey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprint arXiv:1707.09188 2017.
Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. q-learning provably effi- cient? Advances in neural information processing systems, 31, 2018.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. SIAM Journal on Optimization, 31(4):2558 2585, 2021.
Mare Lanctot, Edward Lockhart, Jean- Caan-Bapisste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint (0X.::99980094555 2019.
10

---

Published as a conference paper at ICLR 2023
Chung- Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34,14293-14305, 2021.
Gen Li, Yuejie Chi, Yuting Wei, and Yuxin Chen. Minimax-optimal multi-agent in zero-sum markov games with generative model. arXiv preprint arXiv:2208. 10458, 2022.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-come max problems. In International Conference on Machine Learning, pp. 6083-6093. PMIR, 2020a.
mini-
Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738 2779. PMLR, 2020b.
Michael L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforce- ment learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation for one-sided non-convex min-max problems: algorithms and applications. 1EEE Transactions on Signal Processing, 68:3676-3691, 2020.
Laëtitia Matignon, Laurent Jeanpierre, and Abdel-Illah Mouaddib. Coordinated multi-robot ploration under communication constraints using decentralized markov decision processes. In swehty-sixth AAAI conference artificial intelligence, 2012.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703-2717 SIAM, 2018
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020a.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o(1kk) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimizution, 30(4):3230-325), 2020b.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Sarath Pattathil, Kaiging Zhang, and Asuman Ozdaglar. Symmetric (optimistic) natural policy gra- dient for multi-agent learning with parameter convergence. arXiv preprint arXiv:2210. 128/2, 2022.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, pp- 1321-1329. PMIR, 2015.
Georgios Piliouras, Lillian Ratliff, Ryann Sim, and Stratis Skoulakis. Fast convergence of optimistic gradient ascent in network zero-sum extensive form games. In Algorithmic Game Theory: 15th International Symposium, SAGT 2022, Colchester, UK, September 12-15. 2022, Proceedings, volume 13584, pp. 383. Springer Nature, 2022.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. Advances in Neural Information Processing Systems, 26, 2013.
Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decentral- ized gelaarning in zero-sum markov games. Advances in Neural Information Processing Systems, 34:18 14:18300-18334 2021.
11

---

Published as a conference paper at ICLR 2023
Shai Shalev- Shwaev-S,wartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statisfics, pp.
PMLR, 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7666))556444-33330 2017.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regu- larized learning in games. Advances Neural Information Processing Systems, 28, 2015.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and appli- cations in continuous control. In International Conference Machine Learning, pp. 62244..
PMLR, 2019.
Kiran K Thekumparampil, Prateck Jain, Pranceth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown markov games. In International conference on machine learning, pp. 10279-10288. PMLR, 2021.
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-252 1995.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):50-3344 2019.
Chen- Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30, 2017.
Chen-Yu Yu Wei, Chung-War Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference Learning Representa- tions, 2020.
Chen-Yu Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinit--horizer competitive markov games. In Conference on learning theory, pp. 4259 4299. PMLR, 2021.
Qiaomin Xie, Yudong Chen, Zhaoran Wang. and Zhuoran Yang. Learning zero-sum simultancous- move markov games using function approximation and correlated equilibrium. In Conference learning theory, pp. 3674-3682. PMLR, 2020.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for class of nonconvex-nonconeaue minimax problems. arXiv preprint arXhv:2002.0962/ 2020.
Yuepeng Yang and Cong Ma. O(t-l) convergence of fowlisstti-ooooo--teeeo www.thh--ggulriiee--eeeeee in two-player zero-sum markov games. arXiv preprint N.XI::2209.124300 2022.
Sihan Zeng, Thinh T Doan, and Justin Romberg. Regularized gradient descent ascent for two-player zero-sum markov games. arXiv preprint arXiv:2205. 137445 2022.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi- agent rl in zero-sum markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33:1 166-116611 1178, 2020.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021a.
12

---

Published as a conference paper at ICLR 2023
Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, and Yu Bai. Policy optimization for markov games: Unified framework and faster convergence. arXiv preprint arXiv:2206.02640 2022.
Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Provably efficient actor-critic for risk-sensitive and robust adversarial rl: A linear-quadratic case. In International Conference on Artificial Intel- ligence and Staristics, pp. 2764 2772. PMLR, 2021b.
Yulai Zhao, Yuandong Tian, Jason Lee, and Simon Du. Provably efficient policy optimization for two-player zero-sum markov games. In International Conference Artificial Intelligence and Statistics, pp. 2736-2761, PMLR, 2022.
13

---

Published as a conference paper at ICLR 2023
A FURTHER RELATED WORK
camplinn-baseld two-player zero-sum Markoy games. Finding Nash equilibria of zero-sum
Markov games in sampling-basee bastinonnaad//nlieeeee setting receiving extensive studies in recent years (Zhang
et al. 2020; Liu et al. [021]] Bai et al. 2020; Bai & Jin 2020; Brafman & Tennenholtz, 2002, Sid
ford et al., 2020 Tian et al. 2021 Wei et al. 2017 Xie et al. 2020 Chen et al. 2022
al. 2022).
In this paper, we are more concerned with known model or perfect recall settings. Specifically, our
focus on how to design efficient policy optimization methods to solve the minimax optimization problem formulated by zero-sum Markov games. Therefore, these works are not directly relevant to
us
Minimax optimization. Zero-sum Markov games are usually studied as minimax optimization problems. Finding Nash equilibria/saddle points in convex-concave and nonconvex-conee prob- lems have been extensively studied (Lin al. 2020b Tseng 1995; Mokhtari et al. 22020a b
Thekumparampil et al. 2019 Lu et al. 2020 Nouiehed et al. 2019. Kong & Monteiro 2021 Lin
al. 2020aa).
of zero-sum Markov games, existing tools in convex-concave and nonconvex-concave optimization are hard be adapted here. For nonconvex-nonconean op- timization, Nouiched et al. [2019) Yang et al. (2020) study wwo-timescale/aymmmetti gradient de- scent/ascent methods under the Pt. condition, where avo-tine-scale/ssymmerii refers to that one- player chooses much smaller step than its opponent, or one-player waits until its opponent finds the best response. Daskalakis et al.] (2020) establish the two-sided gradient dominance condition for zero-sum Markov games, which can be related to the two-sided Pt. condition. And they utilize this gradient dominance property to study the finite-time performance of two-timescale gradient de- scent/ascent (GDA) algorithm in zero-sum Markov games and prove its sub- sub-linear convergence rate. Zhao et al. (2022) consider function approximation and propose another two-timescale method that finds a NE at ((1/t) rate.
Due to the
Matrix games. Matrix games are special kind of Markov games with single state. Since matrix games are naturally convex-concave global linear convergence has been achieved in finding Nash cquilibria in matrix games (Gilpin al.) 2012: Wei et al., 2020). The linear convergence of their algorithms relies on the following fact: the duality gap of one policy pair can be lower bounded by its distance to the NE set multiplied by a matrix condition measure (see Lemma 22 for more details). This property is called saddle-poin metric subregularity (SP-MS) in Wei et al. (2020). Similar techniques have been extended to extensive form games and get linear convergence (Lee et al. 2021 Piliouras et al. 2022).
Averaging techniques. Averaging techniques are usually used to tame nonstationarity in approx- imate Q functions, where the players utilize information from past iterations to obtain better ap- proximations for value functions and policy gradients. Wei et al. (202I) propose an actor-critic OGDA method which uses averaged value functions to get more accurate policy gradients, and then achieve a ((/VVl) last-iterate convergence rate to the NE set. Zhang et al. (2022) propose a mod- ified OFTRL method, where the min-player and the max-players employ a lower and upper bound for value functions separately. The lower and upper bounds are computed from approximate Q- functions in past iterations. Their method has (1/tt) convergence rate for the average policy. Yang & (2022) show that the average policy of an OFTRL method whose approximate Q-functions are also averaged from past estimates can find Nash equilibria at the rate of O(1/l) with no logarithmic factors.
Regularized Markov games. Adding regularizer can greatly refine the structures of matrix games and Markov games and is considered a powerful tool to tackle iunconvexitynooncnece zero-sum Markov games. Cen et al.] (202T) study entropy-regularized matrix games and achieve dimension- -free last-iterate linear convergence to the quantal response equilibrium which is an ap- proximation for the Nash equilibrium. They further connect value iteration with matrix games and use the contraction property of the Bellman operator to prove the linear convergence to the quantal response equilibrium of the Markov games. By choosing small regularization weights, their method can find an c-Nash equilibrium in ((1/c) iterations. Zeng et al. (202)) also consider adding entropy regularization to help find Nash equilibria in zero-sum Markov games. They prove the O(t-1/3) 1/3) convergence rate of variant of GDA by driving regularization weights dynamically zero. How-
of
14

---

Published as a conference paper at ICLR 2023
ever, obtain Nash equilibria, the regularization weights have to be reduced to zero in the learning process. The time complexities of existing regularized methods are usually inversely proportional to the regularization weights. Reducing such weights to zero could possibly lead to sub-linear rates.
B STABILITY OF PROJECTED GRADIENT DESCENT/ASCENT WITH RESPECT TO THE NASH EQUILIBRIUM SET
In this section, we show the stability of the distance the Nash equilibrium set after one step of projected gradient descent/ascent. The results in this section are important in our proofs for the local linear convergence of OGDA and the geometric boundedness of Averaging OGDA.
The following lemma shows that projected gradient descent/ascent is very "stable" on the NE set. More specifically, if the players have attained a Nash equilibirum, then, their policies will remain invariant by doing projected gradient descent/ascent.
Lemma For any Nash equilibrium z (x, y) E 2", let re+ be the variables after one step of projected policy gradient descent/ascent with stepsize >> 0, i.e., for E S
x PAA (x, 17 y. y PAs y, (Q.) z.))
Let x² = (xx " yy") then, x 2.
Proof of Lemmal 7 Let u = V.ya. By Lemma 19 x. arg minlge EAA (a's, Yyy,). Equiv- alently, supp (xx) arg min, (a(). where supp x.) is the index set of the nonzero entries in 2..
Next, we will show # w., Since #t the projection A and Slater's condition is naturally satisfied in the simplex constraint, by the KKT conditions,
# (a) (a) + (a) Ao + da 0,
Aa (a) 0, Va [A],
2 Va E [A],
x (a) 2 0, Va E [A],
Σ (a)aa= =
AE
Then, for a E [A], Aa > 0 only x (a) = 0; otherwise, x (a) = xz(a) - (7 + Ag. Thus, x (a) max (a) 17 (a) + λo 0}
If Ag = 77 min u. (a), then by combining with supp (x,) C arg min, uz we have max (a) - (a) + Au 0} = (a),
iee, E. max (a) - (a) Ao 0}
Thus, for do > 11 minae[Al (a(a) or An 1 min u (a). we will have Σ. max (a,,(a) mu (a) + λo, 0} > or
E. max (a, nu, (a) Ao 0} < 1, respectively. To meet the condition Eme(s) [[]] x (a) 1,
we have to let No min wz(a), Now,
x (a) max { x. (a) (a) + do. 0} (a), Va E A.
Analogously, y. = y. The following lemma is perturbed version of Lemma
Lemma For any z = (x, E Z, 2 (7, T) E Z and matrices
.ES S RAXB,
let x 4* be the position after step of projected policy gradient descent/ascent with stepsize n > O, i.e., for ES S
xx = =Ps ( - Q.V.), y. = Pas U. + (Q.) xg
15

---

Published as a conference paper at ICLR 2023
Let z (x*,y* yy"), then.
|| - x 2 <8dist (²,2*) 4nj
Σ
B [Q,(a,b) Qī(a,
(o.
SES
4n² Σ A
Qo(a, - (a) 2
SES (a,
4n7 max
{A, B}²
dist 2 (2, 2*)
(1 (1-
Proof of Lemma
2 Denote x = Pxx (æt), y² = Py- (y), x² = y0='
x== = -xx (3),
y = -Py (ÿ), = (#",
Let u, Q.y.. u = y.y. then
1/ u.l S B u1 uzlloo
SVB max (a.))Ex
(a, (a, 1lyall max (Q) villi)
(a.6)ExxB
B
SVB max (o,
() Q"(a, 1->
dist (y )1).
i..,
|u uzll² -2 B max (Q) (i(a,b)) + B² (a.))AA
(1 7) dist (v..
(20)
By Lemma 19 T yy" is also a Nash equilibrium. Denote क. = Pas (x, - -)Q Then, by Lemma
0
(21)
By triangle inequality, have
|
2.
s
x x2
+ x
- -2.11
|PA (Ø - -17))) - PAA o nuu))
+ + dist X²)
$ x. I1 + + u, u.
+ dist X,)
2dist (m., X,) + u, u
where the first equality is by 2T and the second inequality comes from the fact that for any a, e R-, RAA (a) PAr (b)l
bl|-
Taking square and summing over s E and combining with 20 yield that
x Φ 2 Sdiss (σ,
B²
+ 4rp
Σ NES
(e,b)
max
(Q,
(2(a,)) +
(1 7)²
dist? (3, (m)
Analogously,
1 ح|| <ddist (i.y")
A²
+ 4n²
A Σ
max
Q.(a.b) - (2 + (1 - 233 dist? (z, x2)
(ax
SES
Then, the result follows by summing up the bound for ||x x1| and 11y ~1!
16

---

Published as a conference paper at ICLR 2023
C PROOF FOR LOCAL LINEAR CONVERGENCE OF OGDA
In this section, we prove the local linear convergence of OGDA (Theorem
For notational simplicity, we assume Ti 0 in the analysis below. Recall the OGDA algorithm (T1 = 0): the min-player and max-player initialize
= 3d V. T x ã. 3"
(22)
and the min-player updates for 2 1 as follows
x². PAr
a 1 y. v:
(23a)
T.- = PAr a 1--1-11'.11 Q1
(23b)
while the max max-player updates for 2 1 as follows
y = PAi y/ + 17 (Q0 T x. xr-1)
(24a)
V. = PAr
( + 17 (Q%) x²:)
(24b)
Here, we denote
Q == vf Vt 222 0.
The policy x' and y are played by the min min-player and the max mlx-player at iteration t. And ø', y are local auxiliary variables help generate the policies x' and y'
Since we initialize x = ã, y = y. we drop the notation of ã, ÿ below and directly use x", y to denote the initial policies.
The OGDA method is a decentralized algorithm, its decentralized implementation is in Algorithm 2 (for the min-player) and Algorithm (for the max max-player) of Appendix G
To prove the local linear convergence of OGDA, we first introduce some notations and auxiliary variables.
Additional notations and auxiliary variables. We use 1,0 O to denote the all-ones and all-zeros vectors or matrices, whose dimensions are determined from the context. 1, is the i-th standard basis of the Euclidean space, i.e., the i-th entry of 1; equals one, and the others entries equal zero. The operators >, 2, <, S are overloaded for vectors and matrices in entry-wise sense.
We denote the policy pairs z² (x', v²), x' = (I' yy and denote the projections onto the Nash cquilibrium sets as T = Px; (x'), y = Pyy (v(), , = =Pz; (z+). Since ~", T. z' are treated concatenated vectors, we have from the elementary property of the 22-norm that z"x
(xt U. ) tt fo =Px (0') = [xta] ]
sEs" g = Py. y ys SES" x=" Pz- 1
( J.ES and t (a v²²))
Let Pa be the uniform distribution on S. Then, we denote the state visitation distribution under the policy pairs (a (t-1)) y²) and (x' y ())))) as
(s) d (1- " (s), (s) dz' 10 (s).
(25)
Pa
follows by definition that for any s E S,
1-
1-7 < d (s) 11
< ds(() 1.
S
S
Define weighted sums of distances
O' Σ d' (s)dist (z', + d' (s)iist (3..
S
(26)
0' Σ d ++ (s)dist? xx). d (s)dist? (z..).).
SES
17

---

Published as a conference paper at ICLR 2023
and potential functions
A dist? (z",2*) 2²) dist (2,
1 1-7 x²' z'I t t 1.
(27)
A' 0 +
48
We will show the linear convergence of A given dist? (x) dependent constant óg > 0.
S don for some problem-
C.I ONE-STEP ANALYSIS
Our proof for local linear convergence starts from the following elementary lemma, which is derived by combining standard analysis of optimistic gradient descent/ascent with the smoothness of Q. with respect to the policy pair (x, y).
Lemma Let { xx 56, y², g') be generated from OGDA
23
24 Then, for any 2 0, we have
2 Fz Q 2++ 1+1
++]
V
-ta 1
+++
++1
++1
2
4
2
2
(28)
16A (A + B) x/
1 211
+
(1 (1-
and
yーー (Q*
1+1
17 Us
2
1
Ve
++1
Vs
1")
1 ++1
y
'41
1
++1
(29)
16B (A 1/
|| 2112
(1 (1-7)*
Proof of Lemma projection onto
We abbreviate we have
x² x²" 20 x in this proof. By
23b
since x--1 is the
x
xx
-n yi-1) 2 O,
AA
Equivalently,
x"; Q.+1
1+1
1
, æz1
z x:1²
1+1
T6 11)
2
Similarly, from 23a).
*+1
xx
x
2 0. V2
i.e.,
17 ( 111
xtt1
2'v'') 5 (1 x5|
++1
++
2
18

---

Published as a conference paper at ICLR 2023
Then, have
x
zg Q²+1
y
[+1
x. Q
y 1+1
+ 17
x
1+1
x V'v!)
x (+1 17
++
y
[+1 V'v¹)
|2
|
2
2
x
x
(30)
+ 17
( (+1
x-1 2
y
[+1 Q.y())
x
1 x
x
1+1
x
2+1
_
4
2
417 a Q y.
1+1
Q. v
By Lemma 21 we have
1 ys
V'v'lloc
max (a b)
(a, b)
11 ++1
11
(a b)l y0 ++
b)]l|y/
-vill
max (a.))EAXB
(x
(31)
A + B
2t+1
B
y
2v A
120+1 z111
- 71
(1 71-
Then, 28
follows by combining 30 with
31
And 29
follows by similar arguments.
We consider weighted sum of (8 and 29
using the state visitation distribution (s),, (s)
defined in (25) the weighting coefficients.
Lemma 4 (One-Step Analysis) Let (at, x. vaa. D'} be generated from OGDA with n s
(1-)) Then, for any 1. 2 0,
32//((AB)))
*+1
- 7
111
x 1-1 |1?
4S
(32)
<
7
1 1-7
(1
24
+||2411- =1(²)
+
85
4$
Proof of Lemma 4 Recall that po the uniform distribution on S. By Lemma 20
px 5 (po) y ++ (po)
=pa't gr (pn) yatti 2- (po) Va*t","" 11 (po) V²" g (po)
d' (s) ( 1+1 3." 1 g 1 ( 1+1 V. (Qtt1) 2
(2)+1
d
SES
(33)
As 1 E X', 8 E y,, by Lemma 19 x v²
also attains Nash equilibrium. Thus, we have
Vz't1g" gr (po) - y/ (po)
(34)
=yz "r (0o) - 1#n0""
(po) + 1 8" (po) - y²"","*" (po) 2 O.
19

---

Published as a conference paper at ICLR 2023
Substituting 28
29
into 333
yields that
( 11. : (po) - -Va' g0t (po)
771
7)
1
||
d (s)
x
+ d (s)
2 468
1
2
d=+ (8) 3
+ d (8)
ys
2
SES
Σ
d (8)
x
++1
+ d
g+1
(8)
4
SES
1
1 )11)
d (8)
d
r+1 (s)
1 ++1
2 SES
16 (A
+
Σ (s)+t(s)
(s))
|| z91
7)
By combining with the facts that -
" dist ( xz.) d=(s) 2 157
Eves d=+11 (s) = 1 and their counterparts for the max- maxx-llaeer we have
11 7) (Vo'l :"' (po) - V² y
(po)
1 $ 66
1 gett 1-7 ?
x
x1+1 z'+1
2
7
2
1+1
x"
2
2
45
28
64
(A + 1²
(|24/1-2
=x0|
||
(35)
+
+
xz
(1-
0r
1 1 g
1-7
g0+1
211
2
1
x
x²1²
1
zz
2
2
4S
85
168
where the last inequality is by our condition 17.
By combining
34
with
35
and rearranging, we have
0
7
z ++1
z-11
45
1 7
12 21
1 1-7 (1 2411|? + -1 -
=9(²)
<
+
85
4S
C.2 PROGRESS OF PROJECTED GRADIENT DESCENT
The following lemma is a standard step in the analysis of projected gradient descent.
Lemma 5 Ifn max maxx/VA. VA.WA) for any t O, let po be the uniform distribution on S, then
1-y
n Σ
b ( vt.0 vt:0(ss) <
36S
(| - -2 2011 + 11|2/ (= x=1² ==1²)
(1 7)2
SES
Proof of Lemma
S Since x is projection onto A for any x' E AA.
x t+1 3.. + 1 y ++1
x²g x > 0,
i.e.,
2
t+1
x'y 2 y
++1
<
x
1+1
xt 82
x
1+1
20

---

Published as a conference paper at ICLR 2023
Then, by combining with the condition on ?7-
1) [ 4+1
xzy, 2t11 y
1+1)
- 1)
x
++1
xzy
Q ys
+
x. ++
Q yx
x + 7V A
2 ++
xy x²=
7--1
+ x -++1
<2
+ 3
1+ +++
For any 80 E S and x' X, by Lemma 20 and the fact that Exes d=' (s)=1, 1,
(aall. w2 (80) - V=' w0 (8o)
1 "
d='.v"
(8) (x==1 - yz!)
SES
d d=
(x,!+1
x" Q y )
sup
? SES
E
< y SES
max
(2 (2|la2t
x 1+1
+ 3
x [+1
(2 (2|120 12 0z
+3
x
i..,
n (ve :xtt1 (50) - V (50)
5 -- (2 2+ x² +3 x ++ - -x =+
1
(36)
Similarly,
17 (ta"t))11s)) v -0 (s0))) s 1 --9 y (2 / 3' +3 1 1+ 3 8-1ll).
(37)
By 93 and
94
we have
Vz
(pc111,ts0) - -V2'' - (1 7)2
VA
x I+1 x
(38)
vB
vt.a (so)
vtT (so)
S (1 7)2
y
[+1
Then, by combining (36).
37 38
and the condition on 17, we have
n (v (vz'+ts0)- - vt (5o)
2 I (1 7)2
36
|2 2
2 + 2 8' x²1²)
The result follows by taking sum over 8g E S.
Next, extend Lemma 4 of Gilpin et al. (2012) and Theorem of Wei et al. (2020) from matrix games to Markov games. Firstly, we prove the following auxiliary lemma, which is used in the proof of Lemma 7 This lemma is straightforward from the contraction and monotonicity of the Bellman operator, we attach its proof for completeness.
Lemma 6 For policies x E X and y E y. if there is a vector e E R such that for any s E S (x., (v)))))) 2 v(s), then, have that for any S,
V (s) 2 u(s).
Proof of Lemma 6 For any vector a E R define the mapping $ R - R$ with
(lu](s) = (F., Q.(u)y.).
21

---

Published as a conference paper at ICLR 2023
Then, for any u1, U2 R by definition,
| [((u][()) -((=>(+)) 5 Σ Σ
(10 u2(66)l
S'ES (a.8)EAAB
Y U1 u2 u2lloo
Thus, we have
[ @(ue]ll S u2ll
(39)
i.e, + is a contraction mapping.
Define 21 [v) and uk+1
+ Uk) ... Then, by 39 have
||u+1 flo0 I 7 0/ Uk 1loo 5 ||0 el1oo Then, the limit of on exists and we denote the limit v, lim UR- Obviously, v. fixed point of + because
lim = lim $(px-1]
+ lim 0x-1] =(v.).
100000
As (s) (a Q, V y v.). we have v V i.e., V is fixed point of Φ. By the contraction property of + as in (39), its fixed point is unique. Thus,
V U..
By definition, for any 11 U2 E R uf 2 u2 in entry-wise sense, then b/u,] 2 D[uu] in entry- wise sense. Since the condition (æ.., Q.(oly,) y.) v(s) for any S is equivalent Vi in entry-wise sense. By induction, we have (x(s) is non-decreasing in k. Combining with the fact that
v. limg-+o Uk, we have that for any S,
(=) v. 2 v(s).
The following lemma is an extension of Lemma 4 of Gilpin et al. (2112) and Theorem of Wei et al. (2020) for matrix games Markov games, it plays important role in lower bounding the progress of gradient descent/ascent.
Lemma There exists a problem-dependent constant C+ O such that for any z (xx y) Z and S.
- 2 c+ dist(z 2,).
Vz. viv
Proof of Lemmal 7 any s S, choose
Recall that v² (s) is the minimax game value at state and Q Q,(u*). For
y Larg (I.. Q.y(). B, E arg min (z', V.
v.AAs
Then, by Shapley's s theorem (Lemma X y is the NE set for the matrix game
ming max, x Q.y¹
x Q29.) (+), (a., V.v.) S (s).
(40)
Then, by Lemma for any $ E S, there exists constant yp( (()) > depending only on the matrix Q: such that
(x,, Q. (#.. Q.y.) ( Q:) dist 27).
(41)
Define the policies 2 ( and ÿ (Uxles: Combining 440 with Lemma 6 yields that for any E S.
V (s) 2 (*), ( < (s).
22

---

Published as a conference paper at ICLR 2023
Then, by definition, in entry-wise sense,
=
2 Q,(²"].
By combining the above equations, we have for any E S.
(s) (t) 2 (s) (s)
[1. Q 2. n. - x2. Q 2 y = 2s Q Q.(V=.310 13.) - (2.
(ā Qu 0.lvã.yy. v.
(T. Q.(0") 1000000000000000 {.) (3 Qu (1" y.) (I.: QTD.) (3 Q.ya))
2 Q3) dist x; }g},
where the second last inequality by 44). the last inequality is by (41
Then, the proof is completed by T
By combining Lemma 5 and Lemma ent descent (PGD).
provide lower bound for the progress of projected gradi-
Lemma (Progress of PGD) Let
22 z²
be generated from OGDA with rj S 1 - 7, then for
120
any 2 0, we have
(1 (1-7)? O¹
10-1-2411 1 +
|| 211
365
Proof of Lemma
8 By Lemma 5 and Lemma 7 we have
2² 1+1 2
1 2²11 2n²
V (t))tt())))))) (v+)())))
SES
(1
12
dist (z', 22) (1 11/2) 0
36S
36S
where the last inequality above comes from the fact that d' (s) S 1, d (s) S for any E S.
C.3 STABILITY OF STATE VISITATION DISTRIBUTION NEAR THE NASH EQUILIBRIUM SET
The main motivation behind the proofs in this section is Lemma which shows that projected gradient descent is very "stable" on the NE set.
The following lemma is a perturbed version of Lemma T is extensively used in the proof of Lemma TO Its proof follows by Semmapaane Lemma 21 with simplification of coefficients.
Lemma For any z = (x, y) E and = (क, 7) Z, let x+,yt of projected policy gradient descent/ascent with sepsize 0, i.e., for S
yt be the policy after one step
x PAA (#. 1 "....yy.. y.), yt = PAs (w. + (Q. a.)
Let + (xx y) then,
85 (A 7
|| -=1=
x1|² < 8dist? (²,
dist? (z, Zt).
(1 71
Proof of Lemma 9
Denote x= = Px (x), y¹ = Py. (y) and x" = (x', y²). By Lemma 19
(x", .y" attains Nash equilibrium and Q .v"
= =Q By 91 we have
A + || x²
(. O¹ b)l <
max (
(1 (1-
Then, by combining with Lemma 2 have
85 (A+ B)² n?
+ z 2 (2,2")
dist (z,2") 2*).
(1 71
23

---

Published as a conference paper at ICLR 2023
The following lemma uses Lemma 9 to show that when A is close to 0, || x² ||, x+
will be small, which implies the difference between O' and @ will also be small.
Lemma 10 Consider the sequence {x (z',2% } generated from OGDA with stepsize n S 2v/2(A+B)
(1--)²
There is a problem-dependent constant if A-1 S 7281, we have
=0 1-2))
such that for any T > Oand 2 1,
Oc 0² S T
Proof of Lemma 10 By the condition on we have 85(A+B)²v* and define the problem-dependen constant
< 1. Denote d' = 8 c" = 88
--
(1-7)*
I-7
(1 71
= 0 (1-7)²
61 = 52 B)(774 + 226c")
(42)
(3 + B)
We also denote = 76 below.
The positive constants C1, C2, .2. c7 below are all polynomials in S, B, 1/11 (1)1-)), the definition for each of them follows from the line it first occurs.
Since (s), (s) 1 c', the condition
<-0 ô implies that x²-1 - x S c00
dist? 2 12'
=1-1| 112 S 6"5.
Then,
dist? (z'=1, 2z) s 2dist (z/-1 2 +2 1 1| $ 2(c' + tc')
By applying Lemma with == أاا! 2 z² 1-1 we have
x2' 2x'-3 - x 2-1 s (&d + 2( + +c')) def ojó.
(43)
Thus,
22* + +2|12- z x/1 S (2c' + 221 del c20.
dist? (z', 2*) s 2dist
(44)
By setting ă : z'=1 2 x² in Lemma
we have
z t-1 || S (8d' + 02) 8 def c3d.
(45)
Therefore,
dist? 2 (z", 2*) < 2dist 2 (xr-1 (0- + - < (2c' + +03)) 6 del
co..
(46)
Again, utilize Lemma 9 with ā := ===,, = z we have
| x1|² 2 < (8ca + (2) 8 def oz0.
(47)
Thus,
|---1 - 21
<3 (1
(1= | - - +|13-
+ - | - =11²)
(48)
<3 (03 + C3 + c1) 0 def co0.
Now can bound
x z111 2
+ |||
2¹ < (ca + co) 5 def 678.
(49)
24

---

Published as a conference paper at ICLR 2023
att [1(-1)) 1)+
Since X2 is a convex set, the projection onto it is non-expansive, i...
x x,
Pxx; x - Px;
x
1 xz
x²z Then,
a y )/11
x (1-1)) 33') )1 1 o x (1=1)/0 | + 1 - y²1
< x' x ||
+ /18 2 8/12 $
/ z
2 1 z¹12 S 078.
Analogously,
x (1 y
x . - )1²
<1 - =
+ +|| z¹12 S c70.
By Lemma 21 and 255 for any 8 S
d (s) ds)
d v (s) d
d ./¹ (s)
VA+ B 18' y x1)
(z(1-1)= 1)r w')l
(50)
V(A+ + B) 070
x
1 1-y
1-7
Similarly, we also have for any 8 E E,
V(A+ B)
[d |dt (8) - d3) &
(51)
1-y
()+ 1-7
What remains is to bound the term have
the RHS of (00 and 51
Using 43
49
(by 43 C1
10c' + 2c"
(by (44)
C2 22c' + 4c"
(by (45)
C3 30c/ + 46"
(by (46))
C4 62c' + &c"
(by (47)
C5 518c 68c"
(by (48) C6 1674c' + 222c"
* (by (49) 1704c' + 226c"
By the definition of 6 in 42 and our notation 5= 755,, we have
7(1 (11 V (A+ B70
S
Then, by combining with (50). we have (d)(() (00))dd+1(66) ds) S r(1
By combining with the fact
that (s) 2 1-1
we have
s
ds) d (s) (s).
Analogously, for any s S,
ds,(() d', S (s).
Then, the result follows by the definition of O and @ in 26
C.4 PROOF OF THEOREM 5
By Lemma g we have
||
24tel²
2++1
+
x
zz
x²12)
2 0
(52)
48
25

---

Published as a conference paper at ICLR 2023
where
(1 (1)
(53)
C8
1445²
Then, combining 52 with Lemma 4 and the definitions of A', O², O in (26) yield that for any
t 1,
A+ <A 0 0²_
x zz)
1-7 y
(1 x²1
+ x'' 13'-x117 =11²)
88
45
(54)
1-9
WA + θ 0'
-0
88
Define
co min { (1 ?
)cs
Cs
(55)
S
2
Recall the problem-dependent constant 6, defined in Lemma 10 we define
60 c > 0.
(56)
Now, we prove A++1_ < (1 (1-co) co)" A by induction. For the case t = 0, firstly, by the definitions of
A", 09, O" in 27 266 and the fact that 1-2 < d (8) < 1, 1-3 S (s) S 1, we have
A 0 N
o 2 s
7 A
Then, by combining with Lemma 4 52 and the fact that ~0
= 20, we have
00 < [ (1-))0) ) A S (1 - cond) A s A 0
S
If we have shown A++1 < (1 co)² A for j = ,
- 1, we next prove it for t. By induction
hypothesis,
- < A < d0n (con?)
By Lemma 10
T < (1 + con²) o
Then, by combining with (54) and the fact that co S cs/2, co I 1/2 from the definition of co in 55
have
A 4+1
<A + co
z
z1| - 20
165
<A min
com
2
1
11
+
1-? ?
12 - z x1(²)
2
88
(1 (1-con)) A
By induction, we have for any 2 0,
A² < (1 - con? 2)² Ao.
Using the fact that S < 1, 1-g 5 < (s) S and the definition of A in (2 we have
dist? (x', zz) + || x zz =1²)
8S
dist? 2 (²' 2
<
A+
1
85
8S
γ (1 - 2) 1 < 1-タ (1 - com?² dist? (29,
85
(1 - (1-cor?) dist? (2, Z*),
q
26

---

Published as a conference paper at ICLR 2023
where 2 (z. 3) is the initial policy pair (22
This completes the proof for local linear convergence of OGDA.
As for the order of and 8g. by 533 and 55
co
(57)
S3
By Lemma 10 81
=0
(1-71² (A++B)
Then, by (57) and 156
do 0 ( (1 (11-)) 7) 4
(58)
(A + B)
0 (1-1) VS(A+B)
in Theorem 5 by setting // 0 ( (1-1)
Since need 7 convergence rate
VS(A+B)) )
have the linear
(1 (1-1)
1 -
S*(A+By By²
and to have linear convergence, dist(z?1, needs to satisfy
(1 (1-7)
2²) dist(2 " S -
5 (A+ B)
D PROOFS FOR GLOBAL CONVERGENCE AND GEOMETRIC BOUNDEDNESS OF AVERAGING OGDA
In this section, we prove that the Averaging OGDA method introduced in (6)
Section Dectionn.22caa can serve
can
Gl oballblssss obal-slow in the meta algorithm Homotopy-PO. The proof of global convergence (The-
orem is Appendix D.I The proof of geometric boundedness (Theorem 4 is in Appendix D.2
To begin with, let recall the Averaging OGDA method: The min min-player initializes
a = xx=" w, VT (s) (1) vi."" (s)
(59)
while the max-player initializes
Ti -===0) Ú, V (8) V2. = (t))
(60)
The min-player updates for t Ti as follows:
[-1
('(s) = min
0 1-1
T-Ti Ti+1
(a),),
(61a)
aEA
==
PAA
-1-1
n
(61b)
(xt-1
Par
(61c)
where
Q,'''''
=
(62)
and Q.1-] the Bellman target operator defined the introduction. Meanwhile, the max-player updates for t > Ti follows:
maax DEB
+- (b(
(63a)
j=h
PAB
y
---1
+ . -
(63b)
V. PAN
---
+ n9g')
(63c)
27

---

Published as a conference paper at ICLR 2023
where
Th = q. (q. x._
At the end iteration 72, the min-player and the max-player compute the following average policies respectively
T2
$
TT:TT
Σ t=
2-T T
-2=1i+1 x',
Σ
t- Ti o +1+
The min- min-player plays policy x' and the max-player plays policy y at iteration t. The variables H', V' and y', V are all local auxiliary variables to help generate the policies x' and y'.
Averaging OGDA a decentralized algorithm whose decentralized implementation in Algo- rithm (for the min-player) and Algorithm (for the max-player) of Appendix
D.1 GLOBAL CONVERGENCE RATE OF AVERAGING OGDA
Our task in this section is to prove the global convergence of Averaging OGDA (Theorem 3 To this end, need to bound dist? ( Taal, 2*) by O(log(Tz TT)/(T2 Ti)). Our roadmap can be depicted as follows:
dist? (2 (1 [Ta] Z+
Lempaa
V
Lemina
Reg
That Lemin
14
O(1/(T2 Ti))
10
The regrets above are defined as
Reg.
Ti:t (s) min
0g 2-++++1
J Ti+1 <x' - -5x, (V(V)
x. EAA j=T;
Reg.
Tx:
max
0 T1+1
T ( Q [2'l (y's y!))
V. AB
f=
Reg
Tút max SES
(Regy)
(s) Reg rittss))
More specifically, we bound the distance dist [Ta z*) in the following steps:
1. (Lemma
bounding dist (Taiall
2²) 0 n vT++1 ):
dist
2 [i:iall
2* < 002
p - TT++1
2. (Lemmaa 12 bounding 0
O T=+ 122+1
by regrets:
T2
v T2t1 Tb+1
< Reg Tr:To
+ 0
Reg
Tea + || - -v o1o0)
T2 Ti
3. (Lemmal 14p bounding the regrets:
Reg Tis < 0
n1( Ti)
The following fact about af can found in Section of Jin et al. 2018). It will be used extensively
in our proofs below.
28

---

Published as a conference paper at ICLR 2023
Fact 1 The stepsize of satisfy:
(i) Ei= of = + #. 1. 1.
(ii) Ej و= at = 1 1.
(iii) of I at and a1+1 S a 1
Firstly, we show that the local auxiliary variables (s). (s) are lower and upper bounds for
0" (s). Then, to bound V v² and | - 1011 00 it suffices to bound V²' V
Fact 2 For any t E [T1 Tyl and E.
0 s V' (s) 20
1-7¹
0 s min a
g (a) (0)
max BEB
(b(b) 1
Proof of Fact 2 By 6la have
(T) = Vl.0*) (8) S 20 (s).
By the definition of q. in 62
min q. (a) = min (a's. Q (' aEA
2fEda
Recall that by Lemma 19 v* (8) mina, maxy, (æ.; Vyy.) and Q: (v(").
Suppose V' (s) S v" (s) for any s E S and j E [T] f). then we have
min g (a) aEd
min aGEAA
(a's. Q y s min
(al, Q,(0"vv))
dEEA
<
min max (a's V'y²) = =s))..
d V.'
which leads to (x+
(+) S (s) for any 8 S.
Then, follows by induction that ('()) S v² (s), min (a) S (s)s for any t [T] T2] and s E S. Analogously, V'(s) 2 0" (s), maxber (a) 2 80 (s) for any t E [Ti Tb] and s S.
It also follows by induction directly that the value of V' (s)s,, V' (s), minae (a), maxves (a)
stays in (0, -
The following lemma shows that to bound dist. 2 (21l1:2a) 2²²) suffices to bound | V
Lemma 11 There is a problem- problem-dependent dependent constant I / 0 such that the average policy
g(Ti:Ta) (TaaT TTTi:Taa) satisfies
(3 Ti- 2n) 1 C 1 vT3-1
dist
Proof of Lemma 11 Recall that Q Q,(1*). By 62 and Fact 2
T2
min A
12 g (a) = min
T-T++1
02--1
+1 (a',, Q.(V"''"')
x EAE
1=
min
QT₃-T;
(I',, Qiy").
x EA
29

---

Published as a conference paper at ICLR 2023
Analogously,
Tp
max BEB
1-T++1 TT2-Ti
(1(
max
TT-
1-I1t1
(a'.
Q.IV v/.)
V Vee
71
t=
72
2 max WE
1-T1+1 T--
( Q,y'.)
[=
Thus,
12+1 (8) - T3++((s) (s)
T2
T2
max BEB
072 112-11 9 (b)
1-T;
min acA
012 12--1 9 (a)
T-
1=
[=T]
max
1- T +1 TT2-TT 172-T, Ti
(x's, Q.y'))
min
-T
1-Ti+1
(a's, Qiy!)
V. EAB
x EAA
t=
t=
(T:Tal Qivls)
a'', Q. !! [T:T2]
= max EEAR
2
min o EDA
By I
+ [T. Qiv.) - min { a Q.g!r.Taa) 2 dist (2!T:Ta) 23) EEEAA
max EAA
The positiveness of c+ guaranteed by Lemma
Let C /s then,
1 Tot VT++1
(T:TTaal Q.v6)
(a's, (T:())
max 8ES
max
min efEAA
VEE
TalTi:aal zz) > c dist
max
C4 dist
SES
| -T The following lemma mainly uses Fact (i) and induction show that bounded by weighted sum of the regrets.
T2+1
can be
Lemma 12 The value functions V T2+1 pl++1 satisfies
-T++1
<
TI:Ta Tr:T
+
2y (H + 1)
T2
Reg
Txi +
+|
(1 (1-7) 7) (T2 Ti
(=
Proof of Lemma 12
By Fact 2 and the definition of the operator Q.I.). we have
(Q.IV")(a.b) - Q.IV"I(a,,)) b)) S ς V² vt I.
max (x.
(64)
The following relation follows by definitions of V in 6la and q¹ in 62
('(s) min a
Σ [(
min EAA
Ti+1 a T++ (0', (vI''
j=2i
==
Analogously,
V
(s)
0 02-1++1
T-T
(b)) E
max Σ
i-Ti+1 0/-1it1
( V.V
DEB
i=
==T,
30

---

Published as a conference paper at ICLR 2023
Summing up the above two equations yields that
v (8)
(s)
max
a 7i+1
T++1
min (x). Q,(V'I1() EEAA
(a's. Qu ('!!'
==
1=
+1 4-1i+1
0 Q. | -v))
max ye
j=h
-i+1 (x', x Q. \z
min
a T1+1
E ==
i-T++1
T. Q. (Q. - Q,(K')) v!
1-Ti+1
j=N
<Reg Thit (s)
Reg Ree.Ti (s) + Σ
--Ii+1 V
a
j=
where the last inequality is by 644. Thus,
| p(+1
S &Reg
Tist
+7
af V2 - V2
(65)
j=
Taking sum on both sides of the above equation and combining with Fact T yield that
To
T2
T2
Reg
Ttst
+7
7
V
t=T
j=T
T2
T2 Ta
Reg Ttit
+7
j=Ti t=j
Reg Ttit
+7
1 | H
/
j=f
T
1 H
Reg Tist +7 1
V
j=
T2
Reg Tist +
2
|
vj
1
j=
where the last inequality is from the fact that H = 1-7 After rearranging, we have
T2
v(+1
1+7
Reg
Ttst T
+
2y
7T
(66)
1+7
100
31

---

Published as a conference paper at ICLR 2023
T- a12-11+1 Since - substituting (6). we have
Tz T1- for any E [Ti t). by setting == T2 in 65 and
#+1
V 1ott
v22+1
S Reg T1:23 +7 +7T - Ti +1
H +
T2
V
T3
==
H ++1
<Reg Tr.T2
+
T2 Ti +
1 1+
T2
Reg
Tha
+
27 V" - 1 [10)
+ | rm l00)
1 1-7
1+7
<Reg Tu: Th:T
2/ (H 1)
Reg Tist + 1| -- L -111111\71111)
Titt
(1 (1-7) (12 - Ti 1)
1=
The next lemma is used to derive Lemma 14
Lemma 13 For any t E [Ti : T2 1] and 8 E S.
1 2. 1-1 ? 8B²² (T+-
2B²
(1 71- lly1s y. 1+1 11?
(1 7)²
|1 d. 11-
8A72 (a4-Ti+1)
2A²2
| - 2r 11
7)²
(1 7)
Proof of Lemma
13 By 62
and Fact 2
we have
g 7 ++1
<2B max (A,)EAX
(oLL' b) - 2.IL (a, b)1 ||
+ +2
max (a,))AAB
Q, V. 1101 - y
(67)
2B2
<2B^² 2 |
(1 (1-7)
By Fact 2
g'
S 1
Then, by the definition of V in 6la for any E S,
1--.
(s) [((s S
Σ C Σ
g
T
Ti+1
==
1-7 (a- +1 (1 a a-+))
20q-Ti+1
1-7
where the third inequality uses the facts that Ey= of and abt1 ob of s ag for any
1 isjst.
Thus,
204-Ti+1
1 - -v
<
(68)
1 1-7
By substituting (68) into 667.
we have
2 8By² (ai-1;+1)
2B²
q' q 1
| y. ++1
(1-7)²
(1 (1-
32

---

Published as a conference paper at ICLR 2023
The bound for || 4
||
follows analogously.
We bound the regrets in the following lemma. Its proof is mainly from combining standard analysis
RVU property (see for instance Rakhlin Sridharan (2013) Syrgkanis et al. (2015)) and with
Lemma 13
Lemma 14 For any & [Ti : Tol, if S 5/2max(Aa mA we have
136 (A + B) H
Reg
Tts
77 (1- 41
Proof of Lemma 14 we have
Choose an arbitrary point x, from A Since x.th is the projection onto A
x
x1+1
x² + +gght1
2 0, vt E [Ti 72 - 1].
Then, we have
7 1
x. q
1+1
1
{| a;
x
55 1|²
2
Analogously,
1 x
2
17 (2 2.t
1+1
x
x
2
Then, by combining the above two equations, we have
x+11
7 x
3g
=1
xx
1+1
x
++1
+ 17
x3
1+1
+
x
q')
2
1+1
x
x
(+1
+
17
x
A1+1
where
A 1+1
1
x
2
(+1
1
x
+
417
g.
g
By taking sum on both sides of the above equation, we have
T2
aT,
+1
-
22)
xx g.)
t=
TT +i++
Ti 0
Tq
TTi
x.
T--1
0
TT-T++1
1-71+2
QTT,
+-
-
-.
2
T--1
+2 11
2
0 T2-T++1 4
(69)
t=T,-]
[=
T--1
7
0T2-Ti+1
1 1-1 7
+ 07
-it11
+
011-1111
t-Ti+2
+-
41-11+11 A 111
t-T++2
t=
T1-1
OT
22 -T++-
T- A++1
1 1-7
TT-Ti1+ TT
33

---

Published as a conference paper at ICLR 2023
Analogously, for any y E Ag.
T2
T2 t-7++2
+-T++1 Tr2 - (y' yo T -
On 972-7++1
+ 220T2-Ti+1 -T+11 +
4T2 -2
(70)
1-7
t=
1=
where
-
|
1+1 1
1
++1
V' + 417² 11
q'
2
Since H 1, we have aT2
-72-Ti-11
t-7++2
/
10T22T711 +1
-- Ti+1
S
2.
Then, by combining with the condition 1) and
the fact that | - x²
2
2
x #++1 /"
2 Ø
we have
1--Ti42
1-T
0/1
11+1
H+
T
x²
2
80
1- T1
max {A? 2
} 17
+
+1+1
x 2+1
x²
(71)
?1-
S
T2 +i+
t- +2
-22 t xz
x
xr
1|2
+
xx
112)
S
0.
16
Then, by combining the definitions of A++1 and A+ with Lemma 13 we have
T-
Σ
1-T++2
(A +1+
T2-Ti++1
t=
807, T1+1 max {2 1)²
(1 (122it1-20")) - x2111²=
11
2 8²
(1 ?
T-
32 (A + B) (ar-Ti+1)
1-T,42 0T2-1++1
(1 (1-
(72)
32 (A + 7² T--1
+1
220 -1++1 +
-T--Ii+1
(1-7)²
-+t-
t=
32 (A+ + B) 72 2 2+
(H 1)²
71
H
QT:-T1+1>
where the first inequality also uses
71
and the max-player's counterpart of (71). the second in-
equality by the condition on 17 and Fact
By combining
(69
70
72
1
2
3A (H +1)2
Reg
Ti T2
+6+
Orp--ii+1
77
(1 (1-
136 (A + B) H
-
17 (1 - 7))
The bound Reg" Tist for E [Ti T2] follows by similar arguments.
Now, we prove the global convergence of Averaging OGDA (Theorem 3 by combining
Lemma Lemma 12 and Lemma [4
Proof of Theorem 1 1
By Lemma
12 Lemma 14 we have
TT++
136 (A + B) QT,--Ti+1
17 (1 7)²
27 (H +
To
136 (A+ B)
n
vTi
1
(1-7) - Ti 11)
(1
7)²
Og T
+1+1
34

---

Published as a conference paper at ICLR 2023
Since 21=T, a4-Ti+1
(H+1) [og(T=-TT+1) we have To -1
T2+1 72
408(H + 1) (A B) log (T2 - Ti +1
27 (H
+
11 - (1 (T2 -
(1 (12
By Lemma
11 we have
dist [g( ,*'
408(H + -1) log 72 Ti +1)
+ (H
(1 (1- Ti -i+ +1) )
<
(T +
log(T2 - - 11)
TT2 - Ti +
where
C' 3280Č B) 3280v5(A + B) (1- c1
Remark The initialization
v
Vi.9" and V =V="),t is only used to show the geometric
boundedness in Theorem 4 When Averaging OGDA is used independently rather than called in
Homotopy-PO (Algorithm we can simply choose V (s)= 0 and V -T for any S.
The global convergence rate in Theorem Sttll holds.
D.2 GEOMETRIC BOUNDEDNESS OF AVERAGING OGDA
In this section, we prove the geometric boundedness of Averaging OGDA (Theorem
The geometric boundedness of averaging OGDA essentially relies on the stability of projected gra-
dient descent/ascent characterized in Lemma 2
Intuitively, when (z') ) are close to the Nash will be close to 2² (s). Thus, min, q (a), max, (b) will { (V' V (s) je(T
equilibrium set,
also be close to o* (s). Then, by Lemma ++1 will not be far away from the Nash equilibrium set.
Our proofs in this section can be summarized as: providing mutual bounds among {dist (z*, Z*)), dist 1 2"
-
max; (b) min, (a) by induction.
The following fact shows that |
can be bounded by dist ( 2*).
Lemma 15 The approximate value functions V T
satisfy
VT max 22A, v 2B
dist (2Th 2*)
(1 71
Proof of Lemma By Fact
VTi (s) S (s) TH (8). By Lemma vt. (s) u*()).
Since the min- initializes V (T((s) = -tta"
(s), by combining with Lemma 21 we have
/B y Ti- VBdist (yT, 2*)
0*(s) V2i = vt.²" (8) vt (s)
(1 (1-
7)²
Analogously,
VT. (8) u'))) VAdist (x
(1-7)²
35

---

Published as a conference paper at ICLR 2023
The result follows by summing the above two equations and combining with the fact that dist (2?? 2*) S " ,x*) + 3"
The following lemma follows directly by the definition of V.. V in 61a). 63a and the fact that Ej of =.
Lemma 16 For any t E [Ti : T2 - 1| and E S
()) - (s) -
max je[(ia]
max hEB
(b)
min
(a)
aeA
The following lemma bound the expansion of dist (z', 2*). Its proof mainly uses Lemma 2
Lemma 17 For any 1 E [Ti + 1: T22 11, we have
max dist? (x', (x' 218dist? 15-1,2) + 81 max {A,
V V/ ?
+ 81)² max {A, B3² diist
(1 (1-
dist? (2/41, 3*) <324dist 2 (x-11.7 .2²) + 1522) max (A, B) || D2 yz
+ 152n/ max {A, B3²
dist 2 (z', 2*)
(1 (1-
In addition,
8n7² max {A?, B²] (1 - 7)
4n max {A, B3²
dist? 12Tit1,27 (8+
dist? (2 2*)
+
(1 7)2
Proof of Lemma 17 By Fact
we have L 1// 0
V wr | I
V' V Then,
B max (A.))
(a b) - ba( +
max (a.))EAxB
Q.1V") b) (a, b)
Sn 2 max [} ||'0 + +I|V² |² - -v011
S max {A,
v
Then, by Lemma 2 we have
x1-1 <ddist? (z11.2²) + +4ns
max fA, B} {} V' 18---'' 1- 2
+ 4n) 2 max {A, B)2
dist? (z', 2*)
(1 (1-
| - x²12
8 (z',z*) + 4 S max (A, V' - -vdl
8
+ 4n2 max (A, B] dist? (z', 2²)
(1-7)²
|| Ti+ 2 2T1 <ddist (* 3z) + 4ny S max (A, B} | yTi ?
+ 2 max (A, B)² 2
(1 21- dist? (2Th.20 2²)
The bound of dist (z', 2²) follows by the fact that dist? (2'.2') < 2dist (z+ 2² +
2 1z -=--"-1 -11 The bound of (2 2²) follows by the fact that dist? (2/+1, 5
36

---

Published as a conference paper at ICLR 2023
2 + 211 z1Ip.
2dist 2
The bound of dist? 2r) follows by combining with
Lemma 15
The following lemma is straightforward from the definitions of q. and gz.
Lemma 18 For any & (Ti T2] and 8 S,
max [22 V2B
max (b)
miin q (a) S V Vcl
dist (z',. 23)
bEB
aEA
1-
Proof of Lemmal
18 For any E S, we have
0" (s)
min o (a) = min (q, (2l"" (a)
min Q, (v))(()) aEA
acA
1.110 1elo") 1y Q.(L''v'l
max Q. Q,lv")(a, b) - (.(v"'(a,b))
11 + max
Q.IV")] 11 y. y-'11
(
(a.6)EAXE
VB
v2 20
+
dist (v'.)%).
Analogously,
VA dist (x X²).
max (b) 2² - V 0- bEB
1-7
Then, the proof is completed by combining the above two equations with the facts that dist(2,, 23) S (2, + /2dist "y. (*).
Now, we can prove the geometric boundedness of Averaging OGDA (Theorem by combining Lemma [6 Lemma 17 Lemma 18 inductively.
Proof of Theorem
By Lemma
15
v Ti
VTi
C (z 2*),
(73)
where
max
V2A, /2B
C
(1 71-
By Lemma 18
max SES
max (b) BEB
min g (a) aeA
C2dist (x?² Z;),
(74)
where
max 22A, /2B
C2= =
1-7
By Lemma 17 and the fact that VA + Ag + Ag S VA + VAg VAs, we have
dist (z T+ 2²) < Dídist (zT1,²").
(75)
dist gt 2²) < Dydist (x',2*) + C3 | - v
+ Cadist
(76)
dist
222 2²) < Dadist (z',2) Cs
tt1 y(+1l
+ Cadist (2)
(77)
37

---

Published as a conference paper at ICLR 2023
where
81p2 S max {A2,B%
4172 max (A, B)
D1 V 8
(1-
(1 7)²
v8n max {A, B}
D2 v18, C3 17V 85 max (A, C4
1 1-7 7
v152n max {A, B}
D3 v324, C₁ // 1528 max (A, Co
1-7
Define
D = max + +2 Cc)
Next, we prove 78 by induction
max dist (z. 23) dist (22,
(2)
V
V
.max #E8
max
(b(b)
min
aEA g: (
bEB
(78)
< D 11 dist (z 2*)
The case of j Ti follows by Now, suppose that we have shown hypothesis 788
74 75
78 for j E [T1 : t). Then, by Lemma 16 and the induction
y
Di-Ti-1 dist (,"),%))
By combining the above equation with (74) and the induction hypothesis (8))
4. (b) - min g. (a) < V' - r + Czdist (z 2;)
max NES
max
BEB
aEA
(1++
+ (z Ti 2*).
By combining the above two equations with 76). 77 and the induction hypothesis (78).
dist ++ )z - (D2 + C3 + C4) D Ti+1 dist (2 z²),
dist (z 1+2 2²) < (D3 + C3 + Cb) Dr TI+ dist (zTi. Z*).
By the definition of D. have proved 78 for + By induction,
78 holds for any / [Ti T2].
The following relation is implied by (78) directly
dist (z',z*) zz) < - dist (2 = De-Ti
Ti dist (2,
(79)
where ă = 5) is the initial policy pair 55 (60)
Then, II follows by setting Do D
By definition, we have Do OOS((AAA + B)2 +) under the condition 1) S
By Shapley's theorem (Lemma 19). - = X- y is the set of Nash equilibria of matrix game. Thus, Z is convex, then, Z is also convex. Thus, we have
dist Σ
T-+ x Z"
T-T++ dist (z', 2*) a T
a -
As Do 2 1 in our definition, we have
T2
dist (2 Ta. 2²)) <dist
Σ
aT--T++1*
- +
2"
<
TT2-Ti+
1- +1 dist (x', z²)
+=
1=
Ti-Ti
T;-T;
(DD))
dist (2Ti, 2²) = (vDo)
dist (z, Z*).
This gives 12
38

---

Published as a conference paper at ICLR 2023
E PROOFS FOR GLOBAL LINEAR CONVERGENCE
Proof of Theorem Recall the constants co, do defined in the local linear convergence of Lecal-Fast, Do defined in the geometric boundedness of Global-Slow, C" defined in the global convergence of BLobal-Slow in Section 3.1
Define
C" log(t)
Mi min
f 2 1:
I Voort
1/'l
3
M2 max
[log 0o +11,
comp
Mī = co7 (oog max (oo 1}1 + 1)
Let M = max (M1)² M2, (Mz)²} }. Then, the order of M
Cr² Cr2 log" (66omm)))) log 2 (Do + 1)
M 20
(80)
80n
cgnt
For simplicity we denote
T 7to
Note that 2" 21 112--10 -tull
the initial policy pair the k-th call to Local Fast.
Define k* as
k = min {k E E4 2 M 44 2 M2 2 Mÿ}
Then, 2*" S Mi, -1 -1 S Mř, 2*" 2 < Mý. i.e.
4ta <4 max {(M)} MA, (Mg)²) 4M
(81)
Firstly, we provide bounds for * after k > k*
For any k 2 k", since Ik gs pair 2* satisfies
I gs
+1= 2 2 2 Mi, by
2 and the definition of Mi, the policy
C" log(2*))
dist? .²,,2")
S 80n
rf' 2h
Since 2* is the initial policy pair of Local-Feas Faast in time interval [Z] Z+.. by (5. for t E [Z] 7k1 I
dist 2 (z',2*) STo (1-cn17) 1-I dist (2*,2*)
Since 4h 2 4k" Mj.
4t-1
To (1 con?
1.
Since 2h > 2*" MM. we have
1 conp 44-1
con?
24+1 (24-112)-111)
1
<
3
max (Do 11
39

---

Published as a conference paper at ICLR 2023
Then, by combining the above three equations,
dist?
(x T Zz
S <To- (1 (1-con")
) - dist (2 22,2)
14-1 (10o 3-(1--1)
=To- (1 - (1-cu17) c
4 dist (2*,2)) STu (1- comp
dist (2t 2*)
(82)
3
1
(1-03) conz
dist?
(2" 27)
max (Do, 11
By and the fact that x is the initial policy pair of the (I: + 1)-th call to celobal-Saae
dist? (2 zz
Do
7++1
x
dist
(z a
2*) = D +1
dist
(z (z z*).
(83)
Then, by combining (82) and 83
we have
1
dist 2 (zltt, ; 2²) S $DD
1
1 11- 1--00"
con2
dist? 2 (z*,21
max (Do, 13 22111
3
(84)
44-1
s =1- con?
dist? (zt 2*)
(*²)
3
Next, we give rough bound of dist?
2*) for l E [I] I
Fort E [I] Z by (5),
dist? 2 (z', 2²)
sTo (1- (1-cor²)) dist? (z*,2*) 2* S Todist? (zt,2))
For E [
- J. since z zi is the initial policy pair of the (k + 1)-th call to
ns
it follows by 3)
that
dist (z',2) ZDz I1++ dist?
(z 21122)) S max (Do, 112 dist? (z)
(1
con?"
3 dist? (zt,2*) 2*) S dist? (zt,2²)
4--1
where the first inequality is from 33: the second inequality is from the fact that [ztt] -
2k+1; the third inequality is by 82
Thus, for any t E [Z] I.
dist (x',2%) s Todist? (x*, 2*)
(85)
Now, we are ready bound t ,²) for each E [0: : Tj.
Firstly, we fix a 1e' 2 ke* + 1 and t' E I into:
TK' +1+ Then, the time interval j0 e'] can be divided zz
10: = 10: Ige
+ u J z tJ.
By 84 we have
ΣK' (4"-1)
>k-1 (4%-1)
dist. (3* 2¹) < (1 11- c
dist? (zt* , 220) < 28 (1
co7?
3
3
By combining with 88 we have
Ekzer (1
dist? (x", 2- < (2.TT)) (1- com7
3
40

---

Published as a conference paper at ICLR 2023
By 81).
k -1
k'
Th" R8
v 2*
+ Σ
22
+
44)
4
8
4k
-
32M
(86)
3
3
k=
0=
Thus,
K--1
K'-1
(4h
1)
2
1
4
1
Σ
44
2
2 Σ
1
(4* + 2
2
4
16
k=
k=k
k=k
k=k*
k
TK'
Tk
t
IK-
32M*/3
Tk+1
T
8
2
2
16 k=
16
16
16
Then, for the time we have fixed,
Ee-t (44-1)
6-3288" 18
dist? (z", <(2STo) (1-20) c01)²
(2ST)) (1-
comD
(87)
3
Since the above arguments can be applied to any 1/ 2 and t E [T]
It'+
we have
that (7) holds for any Z +
By similar arguments to 86 we have + < 128M* /3. Then, for any E [0 +
gs
26' +1 16
(at2z",²") $2S < 28 max (To, (1-
Co37
3
2- 1-128
(1- cut)
18
<2S max (To.1}
3
Then, by combining with (87), for any [0:
1283///3
co7)
16
dist? (2¹,2") 22S max (To: 1)
3
(88)
t- 128M2
Co77
<2S max [To.1)-
1
48
Proof of Theorem 2
By Theorem 3 and Theorem 4 Averaging OGDA can serve as the base
algorithm Global-Slow in the meta algorithm Homotopy-PO By Theorem OGDA can serve as the base algorithm Local-Fass in the meta algorithm Homotopy-PO.
Then, by Theorem I we have the global linear convergence of the instantiation of Homotopy-PO with OGDA and Averaging OGDA.
More specifically, by Theorem and 57). the constant c in 9 satisfies > 0 and it is of order
Co
(
48
S3
By combining 880 with Theorem
Theorem
(57). (58).
the constant M in (9) is of order
(A+ 3) log (SAB/(c((1-)))
==O
(1 25
This completes the proof for global linear convergence of our instantiation for Homotopy-PO.
41

---

Published as a conference paper at ICLR 2023
Remark 2 Theorem 2 requires ni S Ol (1-7) (((AA))) for OGDA and n/' S 0( A for Averaging
OGDA. If we set O (1-w)²
vS(A+B) ) then the linear convergence rate is
1 ene = =1 1 (1 (1-7)
(5(A++))3
If we set n = 0( (1-7)²
(3(A+B) for OGDA and n/' = 0( 1-7 A+BB ) for Averaging OGDA, then the length of
Hidden Phase I is of order
M log l (SAB/(c4m²) =0 (A B) log (SAB/ /CAAB/(c4f (c4 )
1//1122
(1 7
F AUXILIARY LEMMAS
The following lemma gives a characterization of Nash equilibrium. Its proof can be found in Sec- tion 3.9 Filar& & Vrieze (2012).
Lemma 19 Consider Markov game g= (S,AA,, P. 7). Given the minimax game value v² (s)
mingex maxyey (s)) A policy pair (x",y") E X x y is a Nash equilibrium if and only if it holds for any s E S that (2',, vz) is a Nash equilibrium of the matrix game
min max T. E,A
T V:y.:
(89)
where Q is an A-by-B B matrix with (a, (a b) + EdES U (s')P(s''s b). In addition, the minimax game value and the Nash equilibrium set of the matrix game (89 are v (s) and 2 X V". respectively. Then, the Nash equilibrum set of Markov game is zz II.es z
The following lemma is known as "performance difference lemma" (Kakade Langford 2002).
is used extensively throughout this paper.
Lemma 20 (Performance Difference Lemma) For any policies x. x' X, y E y and state so S,
we have
v=a.v V2.3
1
d
v (s) (x0g T.. 2. y,))
SES
The following lemma is standard. We provide its proof for completeness.
Lemma 21 For any policies x' E X. y, y' E y and state E S, state distribution p As. action pair (a, b) E x B. Let z = (x. y) and z' = (x', y²), then
VA+ B || 2'1
(a ye'v (s) 1
(90)
(1 7)2
TV A + B 2z - 2'1
0 Q v (a,b)
(91)
(1 7)
( d N=' (s)) <
VA+ + B || 2'1l
(92)
1- V | x'll
(e) - ye (8))()) <
(93)
(1 71-
/B y y'll
(tt(ss viol (s)
(94)
(1 7)2
Proof of Lemma 21 By performance difference lemma (Lemma 20
(s) ya (s))
<
1
Σ
d . (s') x x' Q "
EEES
Σ
d 3 ((') | -
(1
7)²
42

---

Published as a conference paper at ICLR 2023
Similarly,
|ad (s) - vo'v(s)
1
Σ
d [(s')ly>> - -s'-111 Q Q
5
x
s'ES
1
Σ
d 2 (8') Bly. - y'rll1
11
7)²
3'ES
Then, by triangle incquality and the fact that Eves dº (s') = 1, we have
(s) - V='v w/' (s) (s)) - (1 - 71-
Σ d= (5') | - =1
K'ES
VA+ B maxx'ss |z's - 2''s1
VA + B || 1|-- =211 (1 (1-7)2
(1 7)
Then, 991 follows by combining (90) with the definition Q = Q,(Ve.v)
To bound the difference of state visitation distribution, we fix s, E S. Let P E RSS be the transition matrix of policy pair (æz, y), i.e.,
81) = ΣΣ (.(C)_,(((((sss...) aEA BEB
Similarly, define P' as the transition matrix of (x',8'). Then, d (s1) is the (s, entry of (1 - 7I P)- ; d=' v' (s1) is the (8, entry of (I - P') -1 By definition, for any $1 S.S
Σ 81 ES
- P((,,a))PP(s..a.) 81)
(a) - x'((a) (b)P a,
81 65 aE BEB
bEB
+ Σ 3ΣΣ x'((a) (b) - v. P (8)1,,0,
ES BEABEB
S1|z, 2/1111
Thus, we have P PP- S maxses || 2/2111.
By combining with the fact that ||[I - P) -) S Ei 7² Pi S T-g. we have
d (s - dz'' (81)
= (1 - 7) ( (11) p) P - P'] (I - P') -1 1s,
S (1 - 7) (I - P) 1 P PP-P'la P'll
(I - PP') -1
v A + B maxxess 124/ - -2/-
VA + B 2 - 2'1
7
1-7
Then,
)e'v(s) VA + 13 1| z'1l 1-7
(s)
dz (s) S Σ p(su) (2)
p
80
S0ES
To show 993
we choose? Φ E arg max, (s), then, by performance difference lemma
(Lemma 20
(s) - (2'0(()
Σ d= (5') (s') ||00 - ='y'l1 1e2
SES
maxxes
|| 2'ylla
VA - z'll
(1 7
(1 - -
43

---

Published as a conference paper at ICLR 2023
Analogously, (s) - (s)
VA V (1-7)²
Thus, (s)(()) - -v
v/ v'ala-sa) The
(1-3)²
inequality (94) follows similarly.
As a direct corollary of (93) 194).
bound the Nash gap max,es (olt(s) vt. by
2*).
Corollary For any (x), y) Z,
max (a. - vi.v(s) max (V2A, v2B} sES
(2,
(1-7)²
Proof of Corollary I Denote Px- (x) = x", Py (y) = y², .then x" = (x", = -az (z). By the definition of Nash equilibria,
v N¹ (8) v ((s) Vt. (s).
Then, by combining with (93).
94 for any E S,
(s) - (s) max V2.((s) V (=a,t(s)==)))) + vt. (s) vi(((s)
max
$ES
SES
V - x²1l
v B y y"ll
max { 22A, 2BB Jist(zz, 2*)
I max .ES
+
(1 71
(1 - 7)
(1 1 7)
This completes the proof.
The following lemma is paraphrased from Lemma 4 of Gilpin et al. (2012) and is also known as saddle-point metric subregularity of matrix games as in Theorem 5 of Wei et al. (2020). It essentially shows that matrix game ming max, x Gy, the suboptimality of any policy pair can be lower bounded by a certain condition measure sp( G of the matrix G' multiplied by the policy pair's s distance to the Nash equilibrium set of the matrix game.
Lemma 22 (Lemma 4 of Gilpin et al. 2012 Theorem of Wei al. 2020 For any matrix E RAXB, let (²G) = arg m EAA (max, x' Gy') and (*) =
arg max (min.'e,, x. Gy'). ). Then, it holds that for any x E AA and y AB.
max T Qy' y'EAg
min a' z'EDA
T Qu 2 (Q)) / dist (xr, X (G)) + dist (y. )m (G)),
where *p( > a certain condition measure of the matrix Q.
As direct corollary of Lemma 22 we can instantiate the value of c. in
Corollary 2 Let C+ min p(Q.), then, for any policy pair z = (x, v) E Z and E S,
max x, Q,y's min x¹, Q.y, 2 c+ dist(z,, Z?). E.A
EAAA
G DECENTRALIZED IMPLEMENTATION OF THE ALGORIHTS
Recall that in our interaction protocol, the min-player only has access to its marginal reward function ri. and marginal transition kernel Pt. while the max-player only has access to its marginal reward function ri and marginal transition kernel p
Equivalently, in each iteration, the min-player receives full information of the Markov Decision Process (MDP) M = (S, A, pd a:
r 7), the max-player receives M = (S, B, Tp
7).
The marginal rewards and transition kernels are defined
(s, a) Σ R. b), PC. (s'1s, a) Σ ())P((sss))
bEB
(95)
(s, b) Σ
( (a) R. (a. b), (s'ls, Σ
a
aEA
44

---

Published as a conference paper at ICLR 2023
The value function of the policy z in the MDP M is defined an S-dimensional vector containing the expected cumulative rewards of each state, i.e.,
Va.Ma (8) = Ez
Σ 1=0
2 (8) (s),a') 150
The q-function q MM {qs a.Mis 1eEs is defined as a collection A-dimensional vector with M' (a) = r (s, +
Σ
p
(s'ss,a) V2. (s').
s'ES
The counterparts V (s), qs M for the max-player are defined similarly.
In the pseudocodes below, for any set C, le denotes its indicator.
The decentralized implementation of OGDA 8 is in Algorithm (min-player's perspective) and Algorithm (max-player's perspective).
The decentralized implementation of Averaging OGDA (6) is in Algorithm (min-player's perspec-
tive) and Algorithm (max-'layer's perspective).
Then, our instantiation of the meta algorithm Homotopy PO which uses Averaging OGDA as Global-S and OGDA as Local-Fas Fast is naturally decentralized algorithm. The pseu- docodes are presented in Algorithm 6 (min-player's perspective) and Algorithm (max-player's perspective).
Equivalence between OGDA and Algorithm 2
3 suffices to show that qs z' .'M
To prove the equivalence between OGDA and Algorithm Q Q'y'. Actually, both Qs ==' .MMM" and Q' equals the marginal functinn of the local MDP M
{S, A, P m. r 7 observed by the min-player at iteration L.
By definition, we have for any E S, Vo
V Mi V.M w' (s). Then we have
M (a)
Σ
(s'('s s, a, b)v .. (6))
9
BEBS'SS
R. (b) + Σ
IPt (P' a, b,, (8')
1a, Q N2¹ v¹.) = (la: Q.y²))
3¹ MM (Q¹) x This gives the equivalence between
Thus, q
Q'y', Analogously, OGDA and Algorithm
Algorithm 2: X-OGDA
Input: time interval: [Ti: 72), initial policy: T X, stepsize: 1
Initialize x" t
for t Tı, ... Th do
play policy x receive r and Ip
MM, l qs
compute the funnetio
JOeS in the MDP M (S.A, 7)
optimistic gradient descent
/ [[(=TT xT + LISTI PAs W 7/. MM)
1 -aax
(x'-ng-- =' e'M
end
45

---

Published as a conference paper at ICLR 2023
Algorithm 3: Y-OGDA
Input: time interval: [Ti 72], initial policy: V stepsize: f Initialize y² y
for ( ...... T2 do
play policy y¹ receive ry and p
M qs
compute the q-function
in the MDP My = (S, B, yo r 7)
SES
optimistic gradient ascent
J. = [1==T 4. +IIST Pas V. J1-1 + 1q M
[ V1 My:0"
M
y. 1-1 Pas
end
Algorithm 4: x-Averaging--OOA
Input: time interval: [Ti T2], initial policy क X, stepsize: !) Initialize x = ē .T22
for ( Ti.... ,T. do
play policy x² receive r and Ipr. if == Ti then
solve the MDP M = AS , .ri .)) to compute
(TT((s) = min V .M (s) for any E
end
compute for (s, a) S x A. (a) (s, a) + Eves Pt (8'1s,) V' (8))
optimistic gradient descent
_ [(t=TT) IT + +[ITTT) PAi (-t-1 (----gg')
1+1 Pas 33/ )g.
update value function ((+1(s) = minae Ej Ti 0, (a(a)
Ti+1
end
Compute the average policy 2 [T. Σi=,, +++
- x
46

---

Published as a conference paper at ICLR 2023
Algorithm y- y-gveragiiin--OGA
Input: time interval: [Ti 72], initial policy y E V stepsize: r Initialize y²
y
for 1, = T1." ... T2 do
play policy y¹ receive ry and p
if't == Ti then
solve the MDP My (y , to compute
v*) ey VM . (s) for any E S
end
compute for (s, b) S B, q. (b) r (s. Eves (s (s) optimistic gradient ascent
T. - |1=TT 3. + +((()))) . PAs (v.-1 + n
y = Pas V. + t
3-T: update value function (s) maxtEB Ej=r, at-Ti+1 (b))
(s)
end Compute the average policy y [T:: Li=T, OT-
t-
Equivalence between Averaging OGDA (6) and Algorithm 4
Firstly, it follows by definition that via min EX
V M. (8), y (())
max V (s).
(96)
E"
Thus, the initiation steps Averaging OGDA 6 and Algorithm are equivalent. Thus, yTi in Averaging OGDA (6) equals that in Algorithm Consider the variable (a) defined in Algorithm
(a r (s, +
Σ pe v' (s).
(97)
S'ES
By substituting 195 into 977 and combining the definition of the Bellman target operator in the introduction, we have
(a)a) Σ ()
Σ (s'))P(ssssss (b) = (1.. Q.(''
(98)
BEB
BEB
The RHS of (98) is exactly our definition for g' in Averaging OGDA 6 in Section 3.2
Analo-
gously, the definition for q' equals (6) and Algorithm
Then, induction, g q: V (s). (s)
( has the same value in Averaging OGDA
6) and Algorithm This gives the equivalence Averaging OGDA (6) and Algorithm 4
Decentralized implementation of Homotopy-PO
Recall that we have shown in Section 4 and Section that Averaging OGDA (6) and OGDA X
serve the base algorithm Global-Slon and Local-Fase in the meta algorithm opyotopyyPO. respectively. Thus, we can interpolate Averaging OGDA as Global-Siow and OGDA as Local-Fast in the meta algorithm Hometopy-PQ to obtain globally linearly vergence algorithm.
We have shown that Averaging OGDA can be implemented in decentralized manner (Algo- rithm 4 (). and OGDA is also a decentralized algorithm (Algorithmp2) 2 In addition, the inputs of Algorithm and Algorithm 4 Jolly need local information (the min-player only needs x ?i the
47

---

Published as a conference paper at ICLR 2023
max-player only needs () with requirement for knowledge of its opponent's policies. Thus, the algorithm constructed by interpolating Averaging OGDA and OGDA into Homot is naturally decentralized algorithm. The pseudocodes in the min-player's and the max-player's per- spectives are illustrated in Algorithm and Algorithm 7 respectively.
We make final remarks that instantiation for Homot.opy-FO is symmetric and rational. Since the min-player and the max-player use equal stepsize li for OGDA and equal stepsize v/ for Averag- ing OGDA, the players have symmetric roles in our algorithms.
Rationality means one player can converge to the best response set when its opponent chooses a stationary policy. This property is naturally possessed by decentralized and symmetric algorithms. Similar arguments for rationality can also be found in some existing decentralized algorithms. see for instance (Sayin et al. (2021); Wei et al. (202I). We attach the proof for rationality here for completeness. In addition, since our instantiation of Homotopp-PO has linear convergence, it is not only rational but also able to guarantee the linear convergence to the best response set.
Theorem 6 (Rationality) If the max-player chooses stationary policy ÿ -W.tees E y and the min-player runs the instantiation of opmotopy PO (Algorithm 6 then x' will converge to the best response set {a E X:: V= Vt (s). Vs E S} at a linear rate. Analogously, if X and the max-player runs the
the min-player chooses stationary policy instantiation of Homotopy-PO (Algorithm 7 then y¹ will converge the best response set {y y VV. (s), E E S} at a linear rate.
{
Proof of Theorem 0 Since the min-player and the max-player symmetric, without loss of gener- ality, we let the max-player chooses a stationary policy ÿ = (7a).s E E.
Then, we define new Markov game MG' AS, 7). where S. A. y have the same meaning as in the original Markov game. Now, the action set of the max-player only has one action 8 1=+11 [1). P(s'|s,, a, 1) EoEB P(s' a, (b) represents the transition probability to state s' when the min-player takes action and the max-playe plays the stationary policy ÿ. Similarly, define (a, 1) = ELES (a, (b)) as the marginal reward function that the min-player will receive when its opponent chooses the stationary policy ÿ.
Denote the one-sided NE set of the min-player in the new Markov game MG' by X'MM''). By def- inition, the minimax game values T" of MG' are T*(s) (s) = (s)) Then, for any xt E X' (MG'), V= 1 (s) = Vt. (s) for any E S. Equivalently, X (MM') is the best response set of ÿ.
By applying Theorem 2 to the new Makov game MG', we have that the policy x' played by the min- player will converge at a global linear rate to (MM')) that is the best response set of y. Similar arguments also hold for the max-player. This gives the rationality.
Algorithm 6: Instantiation of Homotopyy-PO with Averaging OGDA and OGDA (min-player's perspective)
Input: iterations: [0: : T). initial policy: x E X, stepsizes: n,
set 1: = 1, -- = =1,, x = =x
while T
do
I gg
= - 1,
7 gz
min [Tg - -, 1, I min (Z) + 4 1,
1,
during time interval [Tt. Ig.. run x-Averagiig--ODDA(2 Itll x T
77' and
compute an average policy a : I (Algorithm
during time interval [Z] 7 run x X-OGDA
Z+y, a 1 -tt n)) (Algorithm)
1: - k: +
end
48

---

Published as a conference paper at ICLR 2023
Algorithm 7: Instantiation of Homotopy-PP with Averaging OGDA and OGDA (max-player's
perspective)
Input: iterations: [0: T). initial policy: yd E y, stepsizes: 1) n > 0
set = 1, 7 = =-1, y y
while Z k < T do
Ih 8
1, T min 2 1,T),
= T
I min + 4 1,
during time interval [Tg I run y-Averaacing--ODDA((
Iggh y y .7' and
compute an average policy y -. I (Algorithm 5
during time interval [T] [ run y-OGDA(
-iil D 1 -
,n) (Algorithm
+- k +
end
H NATURAL GENERALIZATION OF GLOBAL-SLOW WITH MORE EXAMPLE
In this section, we mainly (I) show the convergence results of Homotopy- PO when Global-Slow base algorithm has different rates on the RHS of (2); (2) provide another example of Global-Slow base algorithm with generalized global convergence rates by proving the geometric boundedness of Algorithm in Wei et al. (2021) with a slightly modified initialization.
H.1 CONVERGENCE RESULT OF HOMOTOPY-PO WHEN ELLOBAL-SLLOW HAS DIFFERENT CONVERGENCE RATES
To avoid abuse of notations, we call the Global-Sh algorithm with more general global con- vergence rates by Generalized Global-Slow base algorithm.
T2], ž, .7') dur- ing time interval [Ti : T2] where ž = =(ã, ÿ) is the initial policy pair, the players play pol- icy pair z' = (x y²) for each iteration & E [2] T2]. and compute a policy pair g(Ti.Tal
Generalized Global-Slow base algorithm: by calling Gen-Global-Slow([(
( [TTTa] TT.Tal the end of iteration T2 such that 2 2 (T:) satisfy the following two proper- ties:
global convergence: there is problem-dependent constant C² 0 and real numbers pi >> 0 and P2, 2 0 such that
C¹ log Pa (T2 +1)
dist Tr.Tal 2²) < t (T2 Ti 1)m
(99)
geometric boundedness: there exists problem-dependent constant D. (possibly Do 1) such that if 1// & 1, then for any E [7i 72).
dist (x' 2z) < D Tt-T: di,t²(zz dist? ( (2 MTa
TTl Z*) s DT: Tı dist? dist?(2,,25 (2,2"). Z*).
The main difference between Gen Gen-Globall 1al--Slo and Global-oshee Slow is that (1) the RHS of (99) in the definition of -aw--Globallsss- add more flexibility in the power numbers then the con- dition (2) in the definition of Global-Sh.. -Slow (2) (Ta need not to be an average policy. In the example 104 below, we can simply set 2 TT = T2
By similar arguments with Theorem I with generalized Global-Slon
we have the following convergence rates for Homotopy-PO
Theorem Let {z" = (x", "ef.v") y') be the policy pairs played when running Homotopy-PO
(Algorithm 7 where G1 oba -51 ow is replaced by Gen-Gl 1 SSlow. Then, for any I. E [0:
49

---

Published as a conference paper at ICLR 2023
TI. we have
(1-
corp
1-8.1 /3
dist d 2S max (To.
(100)
48
where the value of C¹ cu, Su, To can be found in the definitions of Gen-Global-Slos and Local-Fass and
T7 log 1o (CO ((60m)))) 6) 202
log (Do +1)
M =0
+
(101)
Proof of Theorem 7 Let co. do be defined in the local linear convergence of Local Do de- fined in the geometric boundedness of Gen-Gl obbllllll- -sllowllw C" defined in the global convergence of Gen-Globa -Sbol-Slow.
Define
E log (1)
Mi min 12 1
v bon
(102)
of
Mž and Mğ defined the same as in the proof of Theorem in Appendix
Analogous to the proof of Theorem we also let M = max ?M M2, (M3)²) This gives the order of M in (10T).
Notice that the global linear rate only depends on the local linear rate of Local-Fast and the geometric boundedness of Global-Slon The global convergence rate of Gen-Global- Slow is only relevant to the length of Hidden Phase I, i.e., Mr will only affect the length of Hidden Phase I. Then the rest of this proof follows from Theorem directly. Analogously (88) we also have
dist dist (z',z") S 28 max (To: 1). (1-
Co77"
1-8.2 /3
48
This gives the convergence result of Homotopy-PO when equipped with Cen-Clobal-S1om and Local-Fast.
H.2 ANOTHER EXAMPLE OF GLOBAL--SOW BASE ALGORITHM
Next, show that the algorithm in Wei al. (202)) with slightly modified initialization can serve as an example of Gen-G1 oba
- ol... It is shown in Theorem 2 of Wei et al. (202T) that
ow.
Algorithm 1 therein has sub-linear last-iterate global convergence rate which satisfies the RHS of (99) with = 1. an example of Gen-Globar Globallll Sabal-Sllw it suffices to prove its geometric boundedness. We remark that geometric boundedness may not hold for the original Algorithm in Wei et al. (2021) since its
2, P3 = 0. To instantiate that Algorithm in Wei et al. 2022 can be
initialization (s)) may cause the policy gradients in the first step deviate largely. However, this problem can be fixed simply by changing the initialization to (* = V== V²)'"'(s).
When running Algorithm of Wei al. (2021) in the full-information setting (with the different initialization discussed above) during the time interval [Ti- T2], the min-player and the max-player
initialize T = x 5., Ti y ÿ and
V (
V= miy"" T
(103)
50

---

Published as a conference paper at ICLR 2023
and update for t 2 Ti and any S
x = Px
a 11 Q v...).
1
(104a)
ot41 = Px
(104b)
D,
541
Py
V. + 1) (..) 2!
(104c)
1 = Py
ys + (2:) x¹²
(104d)
((() = (1 - +T+T) (s) + B +1 (at. Q.v:).
(104e)
where Q. = Q and 3.
#o+1 with Ho Hott
Recall that Q is the Bellman target
operator defined in the introduction.
When using the algorithm (044 with initialization (03).. the output policy can be set as (Ta. y y²2
T (T-Tal x
We also denote =² = (xx ))) elaiias = (a tat 3 (irss)), x = Px (æ²), 4dr = Py- (yr",
= Pz. (2) (x'*, y the analysis below.
Next, we proceed to show the geometric boundedness of the algorithm of Wei et al. (021) with the slightly modified initialization similar way with Appendix D.2 We first provide mutual bounds among {dist(z', z²)} and (s) - v² (*(())loo) in Lemma 23 and Lemma 24 below.
Lemma 23 Let {zt, Vt be generated from 1104 with initialization 103 For any TT.
VA+ + Bdist 2²)
||v -pr--ol. o0'l S max JE[TT:]]
|| u² 11.00
+
max
1-7
1:t-1
Proof of Lemma 23 Firstly, define B 11 - 3kk for 0 S st and 8 Br. Since
(8 = 0, by (044e). for any / 2 Ti
v'(s)=
Σ
3 Ti-T
3/-7it1 (2),, d.v..
T=
By the definition of 2 have
(a b) (a(a, s,a.b
(' b) Q2 Q,, s | 1
max
max s.a
(105)
By Lemma 19 (s) (ag"", Qulu" Thus, for any t 2 Ti and E S, by combining the above equations, we have
u-)))
<
Ti+1 t +1
( (al, V.v.) - (w.", Q.1o"
--++ 1-1-1
x
max (x
Q2(u")(a, b)] 11 v1
1=
+
Ti+l
max (x.
('(a,b) Q.(0"I(a, b)) ||
+
Σ
31-I++1 I1+1
Ti+1
x -
Q. Q'
x - 2
|||
Ti+1
|ij
x² 11
-1
1-7
51

---

Published as a conference paper at ICLR 2023
Then, the proof is completed by the fact that max,es
||
=!*1|, S VA+ Bdist (2), _²)) and
Σj. - +1 1.
Lemma 24 Let {z', V be generated from 104 with initialization 103). Then, for any t 2 Tı,
dist? 2 $18dist (z' 222*) S + B) [t- 0²1
81p² max (A,, B} 2
dist 2 (z', 2*),
(1 ?)-
dist dist?(z't1, ((x(111)) 2)) <324dist 2 Pz", 2 + /52n/ (AA + B) |1-1 22 101
+ 1527) max {A, B) 2
(1 7)² dist. 2 (z', 2")
Proof of Lemma
24
By applying Lemma 2 to [04 and substituting (05) we have
1+1
<ddist?
x (x'22) + S(A+ + B) |V- v² 1
+ 417 max {A,
(1 7)- dist (z¹,2*)
2 zz z111| 11 Sdisst (z*+) .z') + 2
S(A + B) | 1²1
+ 4xp max (A, B3² dist?
(1 (1-7)²
The bound of dist? dist? 2*) follows by the fact that dist (x 2z) I 2dist (z'st??z",230 + 2 || =201 -
The bound of dist? 2*) follows by the fact that dist? (z*t1, s
2dist? (z1+1, 2-) + 2 2 - | and substituting the bound for dist (z 2*).
Next, we show the geometric boundedness of Algorithm in Wei al. 2021 with the initializa- tion (103.
Theorem (Geometric Boundedness of Algorithm in Wei et al. 2021 ) Let {2" hem ay be the
policy pairs played by running the algorithm (104) with intiialization (103) If I 1, then there is
problem-dependent constant Do ( 3(4+ By (possibly Do 1) such that for any [Ti T2),
(1 (1-7)*
dist (="t < Dz- Tı dist ? (2, z*).
(106)
Proof of Theorem g We will show (106) by proving (112) inductively.
Firstly, we define some constants which are used in the definition of Do. By Lemma 23 for t 2 Ti,
||V 1/ < max C dist (z', +2 max -1t-1-
||V v² 11
(107)
JE((1=]
where
C² 2(A+ B)
(1 71-
By Lemma 24fand and the condition 7) 7 1, for t 2 Tı,
(z ; 2²) <D dist (z", 2z) + C/2 [t-1 -
(108)
Cddist 2 (z/.2) 2")
dist? ;-, 2*) < DDydist (z', 2n) + C₁ 1
(109)
+ Cfdist (z¹,2").
52

---

Published as a conference paper at ICLR 2023
where
Dj 18, C2 8S(A B), c== 8max (A, B3²
(1 (1-
152 max {A, B)²
D/2 324, C 1525 + B), C
(1 - 7)²
For the initialization (003 by
|
0² 1 S C. dist (2 2²),
(110)
where
A+B B
C/ (1 1 7)a
Define
Do max {Cr + 2, C. Dj + +2 Cj. + Cg).
(111)
By definition, D S (1-g}+ Now. we proceed to prove
1122) by induction.
max {dist (z', 2²), dist (E*, 2*), || - v² [1( s DØ- dist (3,
(112)
The case of j = follows by (100) and the initialization = _ = 2.
Suppose we have shown 112 for j E [Ti : tj. Then, by 107). the fact Do 2 and induction hypothesis,
||V- 1 S (C+ 2)D dist dist? < D Ti dist (2,
By 108) and induction hypothesis
dist d S { + C2 C2y) Do Ti di, < Do 11-1-77 dist "2, Z²).
Analogously, by (109) and induction hypothesis
dist dist ,2* < (D'2 C2 + C.²) DT- dist D dist dist (2, Z*).
Thus, we have shown (122) for = + 1. By induction,
(122) holds for any j E [Tr T2]. which
implies (106) directly.
This completes the proof for the geometric boundedness of the algorithm 104 with the initializa- tion (103).
Remark 3 When the meta algorithm Homotopy-PP. switches between Algorithm I of Wei et al.
2027) (with the slightly modified initialization) and OGDA (8) then by Theorem 7 and (57)
(1 - 7)
O
48
53
Then, =f===11 0 (1-7) (S(A- for OGDA, the linear rate is
(1 (1- (10-00000))0 (5(A+BB B)²
con' = -1
48
the stepsize 1) therein has to satisfy 17 S (1-y1
As in Algorithm I of Wei et al. 2021
10'/5' By combining
Theorem of Wei et al. 202/) with (100.
5
58
if O (1-))
VS(A+ for OGDA and
' = O (1-2)* v5
for Algorithm in Wei et al. 2021)) 1) then the length of Hidden Phase is of order
128 /33 =
(A+
c1-
53

---

Published as a conference paper at ICLR 2023
1 NUMERICAL EXPERIMENTS
In this section, we evaluate the numerical performance of Homotopy-PO where Local -Fat and Global-Slow are instantiated with OGDA and Averaging OGDA respectively.
Markoy game model. We generate a sequence of zero-sum Markov games randomly and in- dependently in the way described below and test the performance of Homotopy-PO on each of the games. In each Markov game generated below, the number of states is S 10, the min-player and max-player have A B = 10 actions respectively, and the discount factor 0.99. The reward functions (a, ses are generated from uniform distribu- tion on [0. 1] independently. To generate the transition kemnl,, for each (s, (S.a,b), an integer is,a, uniformly at random from [S]. Then, we choose a random subset Ma,a, S S with aM = is.a.b. Then for each s' E Ma,..d we set (P , a, b) from uniform distribution Finally, we normalize P(s'|s, |s, a, b) = P(s'|s. |s, a, b)/ Esres P(s"|s, a, b) for each (s. a, b) to get the transition kernel. For the initial policies, we first generate (u,) seS with (a) chosen from uniform distribution on [o, 1] for each E S, a E A. Then, we normalize x² u.. ||u,|| I for each s E S. The initial policy {v)).es of the max-player is generated independently in the same way.
first choose
on [0, 1] independently, and for s' E &S,,a,,bb we set (ss'|s,, a, b)
Algorithm implementation. In all the experiments below, we set the stepsizes 0.1 in OGDA and also Tf 0.1 in Averaging OGDA. We find our algorithm has linear convergence in all the experiments with these stepsizes.
Performance metric. We measure the closeness of z' to the Nash equilibria set by the Nash gap maxses V (() Vt.v (s). By combining Lemma 7 and Corollary [ with the fact that dist(z, 2*) I VS max,es dist(z 2;), we have the following relation between the Nash gap max,ss Va.t(s) (s) (s) and the distance to the NE set dist z, 2"): for any (x, y) Z,
Vs 2") < max (s) - vit((s) max (axxVVAA V2B} $ES
dist(z, z*).
(113)
(1-
Thus, the linear convergence of "ist(z",2'' is equivalent to the linear convergence of the Nash gap max,es V - Viv (s) up to represents the logarithmic of the Nash gap log (max,es V=' (t() (s)- -Vi.v" (s)). x-axis represents the iteration number.
constants. In the figures below, y-axis
Remark 4 As we can see, there are discontinuities when switching from Averaging OGDA to OGDA in the figures below. This is because Averaging OGDA is an averaging style method. Recall that
the y-axis represents log maax.s V'' (s) Vt.0 (s) However, the initial policy pair of the
k-th call of OGDA is the average policy 2 t I E L1=Ig
O'2h 1-I z'. Since it is quite possible
that =o + Ih, there can be some discontinuities in the figures below when switching from Averaging OGDA to OGDA. On the other hand, our theoretical bound Figure 7 is continuous
because by setting = T2 ④3) theoretically dist. (2 To 2²) < DD TT=Ti, dist (2,2*) 2*) whose
bound equals the bound for dist?
(2sst(2!T::)) (2(Ti.Ta) 2n) on the RHS of (4 We remark that in practice, it is
predictable that =t + 1 7 in most cases.
Numerical performance. We validate the linear convergence of our instantiation of Homot.opy-PO, where Gl Global-S. aw and Local laaal-Fsstt are instantiated by Averaging OGDA and OGDA respectively.
Figure shows the performance when the min-player and max-player run Algorithm 6 and Algo- rithm respectively. We do 10 random and independent trials and the algorithm exhibits linear convergence in every trial. The plot shows the average trajectory and standard deviation of the 10 random and independent trials. The vertical dotted line is at the end of 7-th call to OGDA (iteration t = 22098). As we can see, on the RHS of the dotted line (after > 22098), the algorithm converges linearly and the Nash gap is less than 10-5 after 2 x 10 iterations. The standard deviation of the 10
54

---

Published as a conference paper at ICLR 2023
random trials is illustrated by the shadow area. Since the switching pattern is 2 iterations of Aver- aging OGDA followed by 4 iterations of OGDA, Averaging OGDA is only run for 1022 iterations in the total 2 X 10" iterations. Thus, Averaging OGDA is hardly trajectory of the 9-th call to Averaging OGDA as subfigure in Figure 2 We can find that Averag- ing OGDA increases in its 9-th call. This has been predicted in theoretical bounds (see segment BC in Figure D. The 8-th call to OGDA has 4 iterations, while the 9-th call to Averaging OGDA 128, i.c. the iterations of OGDA are hundreds of times more than those in the successive call to Averaging OGDA. Then the increase caused by Averaging OGDA can be naturally "omitted" compared with the decrease from OGDA. This aligns with our theoretical bounds in Figure | (see the relation between the segments AB and BC in Figure
in Figure 2 We magnify the
only has 2 iterations. We have 48 /
2
Averaging OGDA
logarithm of the Nash gap
OGDA
100
1
10
10
1
7.5
8.8
8.82
8.84
8
x110
0.2
0.4
0.6
0.8
1.2
1.4
1.6
1.8
2
iteration number
x10
Figure 2: The numerical performance Homotopyy-FO when G1 www.bbllllo and Local-Fast are instantiated by Averaging OGDA and OGDA. The trajectory is the average of 10 random and independent trials. The z-axis represents the iteration number, while the y-axis represents the loga- rithm of the Nash gap. The shadow area shows the standard deviations of these trials. The vertical dotted line is drawn at the end of the 7-th call to OGDA (iteration 22098). On the RHS of dotted line (equivalently, after switching pattern, 2* < 4tt when magnify the 9-th call to Averaging OGDA subfigure. Though Averaging OGDA can increase, its increase is negligible by the decrease from hundreds of times more steps of OGDA. This aligns with our theoretical guarantees (see the relation between segments AB and BC in Figure l..
22098), the algorithm exhibits fast linear convergence. In our
large. Thus, Averaging OGDA is almost "invisible". We
To avoid the problem that the iterations of Averaging OGDA is too few to be "visible", we do an- other group of trials by generalizing the switching pattern slightly. Recall that Algorithm ! the has 2 iterations while the k-th call to worth noting that the choices of 2 and 4k in Algorithm [ is only for simplicity. The proofs for linear convergence of Homotopy-PQ can be directly generalized to the case when the k-th call to Global- -llww and Local -aaralFFssttt Fast has [ and [ iterations respectively whenever u, v are real numbers satisfying > > 1. Then to see how Homotopy switches between Averag- ing OGDA and OGDA and see the performance difference between Averaging OGDA and OGDA separately, test the performance of Homotopy-Po where the k-tt call Global-St Slow and Local-Fast has 2 and [211* iterations respectively. We do another 10 random and indepen- dent trials in this switching pattern. The average trajectory and standard deviation illustrated in
k-th call to Blobal-SS1
has 4 iterations.
55

---

Published as a conference paper at ICLR 2023
102
Averaging OGDA
logarithm of the Nash gap
OGDA
100
1
10
10-6
10.8
2
4
6
8 10 12
14
16
18
iteration number
x10
The numerical performance of Homotopy-Pe PO with a slightly generalized switching scheme. In the new switching scheme, the k-th call Averaging OGDA has 2* steps and the k-th call to OGDA has [2.1a] steps. In this way, there are more iterations of Averaging OGDA so that the switches between them can be and independent trials with this switching pattern. The shadow area shows the standard deviation of these trials. The æ-axis represents the iteration number, while the y-axis represents the logarithm of the Nash gap. We show the trajectories of the first 15 calls of Averaging OGDA and OGDA (iterations S < 195592) in this figure. The discontinuity in the trajectory is because Averaging
Figure 3:
clearly. The trajectory the average of 10 random
OGDA averaging style method where 2 : : may not equal z 7hh (see Remark 4). A vertical dotted line is drawn at the end of the 12-th call to OGDA (iteration = 22237). It can be observed that on the RHS of the dotted line (iteration > 22237), the algorithm exhibits linear convergence. This aligns with our theoretical bounds illustrated in Figure where Averaging OGDA can increase but its increase can be "omitted" compared with the decrease from the more steps of OGDA that the algorithm still has linear convergence.
Figure where the iterations of Averaging OGDA are drawn in red while those of OGDA are drawn in blue. We show the trajectories of the first 15 calls of Averaging OGDA and OGDA (iterations 1 1St 195592) in Figure The discontinuity of the trajectory is because Averaging OGDA is an
averaging style method and OGDA uses the average policy 1 rather than 3 as the initial policy (see Remark 44. We draw vertical dotted line the end of the 12-th call OGDA (iteration t = 22237). It can be observed that on the RHS of the dotted line (after t > 22237), the algorithm exhibits linear convergence. On the RHS of the dotted line. the performance of Averaging OGDA is generally inferior to OGDA. Averaging OGDA can even increase in some iterations. This coincides with our theoretical bounds (see the segment BC Figure 1). Thanks the fast and efficient linear convergence of OGDA together with the fact that the iterations of Averaging OGDA take up less and less proportion in the total iterations, the algorithm can exhibit linear convergence on the RHS of the vertical dotted line. This also aligns with theoretical bounds illustrated in Figure
To see the switches between Averaging OGDA and OGDA clearly in each trial, in Figure and Figure 5 below, present the 10 random trials of the changed switching pattern (2 iterations of Averaging OGDA followed by [2.1*] iterations of OGDA). We illustrate the trajectories the first 15 calls of Averaging OGDA and OGDA (iterations
195592) in Figure 4 and Figure
56

---

Published as a conference paper at ICLR 2023
In each subplots, we draw vertical dotted line the end of the 12-th call to OGDA (iteration t = 22237). It can be observed that on the RHS of the dotted line (after t > 22237), the algorithm has linear convergence in each trial. In some of the trials. Averaging OGDA iterations. This is predicted (see segment BC in Figure 1). Since OGDA converges linearly and Averaging OGDA takes less and less proportion in the total iterations, the algorithm can still exhibit linear convergence on the RHS of the dotted line (t > 22237). This aligns with our theoretical bounds (see the relation between segments AB and BC in Figure D. Even the worst case (the 8-th trial), the Nash gap is less than 10 10-3 after 2 x 10 iterations. And in some fast cases such as the 3-rd, 4-th, 5-th, 9-th, 10-th trials, the Nash gap can be less than 10-6 or even 10 8 in about 2 x 10 iterations.
increase in some
10
10
Averaging OGDA OGDA
Averaging OGDA OGDA
logarth the DRp
10
10
logarithm of the Nash
10"4
10
10
10
12
12
Boration number
x10
Iteration number
x10
(a) Random trial
(b) Random trial
10
10
Averaging OGDA OGDA
Averaging OGDA
logarithm the Nash gap
10
10"
OGDA
2
logarihmm the Nash
10
10"1
10
10
10
10-10
10
10
12
14
16
18
10
12
14
16
18
Heration number
x10*
number
x10*
(c) Random trial
(d) Random trial
Figure 4: The first trajectories of 10 random and independent trials with the switching pattern described for Figure 3 The rest 6 trajectories are illustrated in Figure below. In these trials, the k-th call to Averaging OGDA and OGDA have 2 and [2.1 iterations respectively so that the switches between them can be seen more clearly. The rraxis represents the iteration number, while y-axis represents the logarithm Averaging OGDA and OGDA (iterations 1 < 1. S 195592) in these subfigures. The vertical dotted line is drawn at the end of the 12-th call to OGDA (iteration t = 22237). As we can see, on the RHS of the vertical dotted line (t > 22237), all trajectories have lincar convergence. The discontinuity is because Averaging OGDA is an averaging style method (see Remark 4). The trajectories coincides with theoretical bounds in Figure where although Averaging OGDA cause increase, its increase can be "omitted" by the more steps of decrease from OGDA.
the Nash gap. We show the trajectories of the first calls of
We also compare algorithm with Alg. 1 in Wei et al. 2021 We choose the stepsizes of both our opy-otopy-PO and Alg. in Wei et al. (2021 to be O.I. We choose the discount factor y = 0.5, and the rest settings the same with those in the experiments above. The switching scheme is chosen to the same with that in Figure 3 above. The comparison between comotopy-an and Alg. in Wei et al. (2021) is illustrated in Figure where the curves drawn by taking the average
57

---

Published as a conference paper at ICLR 2023
10
10
Averaging OGDA OGDA
Averaging OGDA OGDA
logarithn gap
10
10"
logarithm of the Nash
10"
10-4
10
10"6
10
10
10
Boration number
x10"
iteration number
X10"
(a) Random trial
(b) Random trial 6
Averaging OGDA OGDA
Averaging OGDA
OGDA
logarthi pep
10
10P
logarthm of Nash
10"1
10"
10-
10
10
10
10
12
14
16
10
12
Beration number
x10*
iteration number
x10f
(c) Random trial
(d) Random trial
10
10
Averaging OGDA OGDA
Averaging OGDA
OGDA
logenihhm pap
10
100
logarihhm of the Nash
10
10"4
10
1016
10
8
10
12
14
16
10
12
14
Baration number
X100
Iteration number
X10"
(e) Random trial
(1) Random trial 10
Figure 5: As complement to Figure 4 independent trials with the switching pattern described for Figure 3 The caption of this figure has been integrated into that of Figure
this figure shows the rest 6 trajectories of the 10 random and
5 random trajectories and connecting the points at the time points when Homotopy-Po switches between Averaging OGDA and OGDA. As we can see in Figure Homotopy-Pe can converge to the NE set faster than Alg. 1 in Wei et al. (202)).
58

---

Published as a conference paper at ICLR 2023
10
Homotopy-PO
Alg. in Wei et al. (2021)
logarithm of the Nash gap
10
10-4
1
1
0.5
1.5
2
2.5
3.5
4
4.5
iteration number
x10*
Figure 6: Comparison between opy PO with a slightly generalized switching scheme with Alg. 1 in Wei et al. (0221) In the new switching scheme, the k-th call to Averaging OGDA has 2 steps and the k-th call to OGDA has [2.1* k steps. The curves are computed from the average random and independent trials. The curves are the segments connecting the points the time points when Homotopy-Pe switches between Averaging OGDA and OGDA.
J DISCUSSIONS
J.1 POSSIBLE TRANSLATION TO SAMPLE-BASED ALGORITHMS
We remark that it is possible translate our algorithm into sample-based algorithms. Here, tentatively discuss the analogues of local linear convergence of OGDA under the following two cases and give an intuitive analysis for each case. The analogues of global convergence and geometric boundedness of Averaging OGDA can be discussed similarly.
Case 1: Assuming access a simulator (generative model). there is simulator (generative model) and the players can draw lots of samples in one iteration, then it is possible to get linear convergence against the iteration number. More specifically, iteration f, for each 8, N, samples drawn from the distributions IP-Iss, ( where 1 S. N, and a ~ xf. bi ~ vř. We define a very small variable ó; (coo)2 )t) Define the truncated simplex A = {a e RAA (a) > &e, Σ xa) = 1]. A is defined analogously. At iteration i, we replace the projection operator PA.(') (-) and PAs(1 (.) with PAç (.) and Pa: (.). This guarantees that each action is taken with probability at least d, Then by Hoeffding's inequality, each action is taken by the min-player for at least (N)))) times with high probability (w.h.p). Then, the empirical marginal reward ft and marginal transition kernel Pe observed by the min min-player satisfy the following relation w.h.p.,
l ro0loo SŌ (V Noo.
[PIs IP (-|s, a)ll S (V N₂O,
In this remark, Ö(-) suppresses logarithmic terms and problem parameters such S, B,1,((1111 for simplicity. Thus, we have |'''''"' V 11 S <0(v N.o. |1vt Vtw 11 S Ō( N.o.
- Ö(v R..). 12:" (a, ((,b)) Q:""" (a, Ō σC Noo. for any (s, a, b). Here,
use - overhead to indicate the empirical quantities. And the replacement of PaA (.) by Par (.)
will add eπror term whose foc -orm is at most 6,. Thus in each iteration t, emror terms of order Ö( Noo. +6,) are added. iteratioo I, let #++1 be the ideal variable computed from {ad Jise
59

---

Published as a conference paper at ICLR 2023
with exact value of the marginal information r' and P Let af+ be the real variable computed in
the learning process. 8z and y are defined similarly. Then, by Cauchy- Schwartz inequality,
dist? 2)) v (1 + connt/2) /2itst (z -*) + (1 + 1/ (2) N.o. + o)). After adding these enror terms to the proof of Theorem 5 the bounds for the potential functions A defined in (27) will be
CoTF NNo; + (N.,
u+1 - - o01 (ou +ō
Then by setting N, = -1or" ). can show by induction that A S O(11 en' /3)² This gives the local linear convergence of OGDA when the players can draw lots of samples in one iteration.
con
Case 2: Using an ergodic assumption. When no simulator is available, we consider translating our algorithm into a sample-based algorithm under an ergodic assumption. The assumption that there exists a constant Lo > O such that for any policy pair = (z, y), if the min- min-player and the max-player play policy x and y respectively in Lg successive iterations t E [Ty To + Lo- 1], then, for any initial state ST, and state E S, there exists a a E [To To + Lo - 1] such that 8y' 8. Briefly, this assumption requires that when the players choose stationary policy pair for successive To iterations, then every state must be visited at least once in these Do iterations. Under this assumption, our strategy is to regard successive Lo X Ng iterations as a virtual iteration k. In this way, we divide [1 2] into
[1 T] = [ T2) U [Ts T.] U......U. 102.-.-TTT--1111111 T2x] U.
where T2x- T2k-1 Lo x Ng-- Then, in the time interval [T2k-1 T2al. each state has been visited for at least N₂ times. This is similar to the case when we have a simulator and N₂ samples drawn for each state 8 in iteration k. In this way, by applying our algorithm and analysis for the simulator case (Case I aabove,, we can show the local linear convergence with respect to the virtual iteration number k.
J.2 DISCUSSIONS ABOUT THE INTUITIONS BEHIND AVERAGING OGDA AND OGDA
In Markoy games, the main challenge of finding an NE is to estimate the minimax game values (s)), If (u*(s) (s)} are already known, the players can use Q,(v"] and Q,(=*] x; as policy gradients to do optimistic gradient descent/ascent. Then finding an NE is reduced to solving [u'] ly, separately. Approximating (s)) is dif- ficult because (1) zero-sum Markov games are (s)( is almost as hard as our goal which is finding a NE: (2) the players only know marginal reward and marginal transition kernel, so in each player's perspective, the marginal MDP observed is dynamic. More specifically, the errors in approximations for {s)(s)} will cause inaccuracy in approximate Q-functions and policy gradients. The inaccuracy in policy gradients will make 2f far from the NE set and then induce errors in approximations for (s)). This will easily generate a vicious circle and make the errors blow up.
matrix games min max,, EAn xx Q.
nonoonnaee problems, and then, solving
Averaging OGDA and OGDA employ different ways to approximate (u*(s)) in each iteration. OGDA directly uses V w'
Vo'ws (s) to approximate v*()). Thus, the min-player uses
Ply Q. w/ "Iv", as approximate Q-functions to do optimistic gradient descent, while the max-player uses (Q!) = Q. wn '')T as approximate Q-functions to do optimistic gradi- ent ascent. On the other hand, in Averaging OGDA, the min-player and max-player use ('(ss) and V'(s (sss respectively to approximate {s)) Thus, the min-player uses g' = (s))()) as approximate Q-functions to do optimistic gradient descent, while the max-player uses o Q. (s)] 2 as approximate Q-functions to do optimistic gradient ascent. L²(s) and V (s) are computed through the averaging technique. Take the min-player as an example, where L'(s)
minge Σj=T, a/- j-T++1 (a) is step of value iteration on the average of past Q-function approx- imations. We will elaborate on the intuition of V''(s) below, but before that, we first show why the averaging step is needed to achieve global convergence (equivalently, the disadvantage of using Vz al (s) to approximate v" (s)).
111
Technical challenge in the analysis of OGDA. The main difficulty in the analysis of OGDA is the nonconvex-nonconcant essence of zero-sum Markov games. As discussed in Section 5.1
60

---

Published as a conference paper at ICLR 2023
of Daskalakis al. 2020), the failure of the Minty Variational Inequality (MVI) property in zero-sum Markov games poses challenges for the last-iterate convergence extragradient meth- ods/optimistie gradient methods. More specifically, given the objective function f(z) with (r,y) and F(z) = V=](())-VVp[( (=)(=)) the MVI property means that there exists point 2" (x" yy") such that (F(z), =") 2 for any z. Proposition of Daskalakis al. (2020) proves that when setting f(z.8/ y) = (s) for some state E S, the MVI property can fail m arbitrarily small neighborhoods of the NE set.
More specifically, for the OGDA method (8). it may happen that there exists some & E S such that 1+1 + ( y ++1 (Q:+t) 2411
1+1
y/
0,
(114)
where T= = Px. (z').
Py (y) are projections. We also denote 3z = P2- (z'). The troublesome case (14) implies that going in the directions of policy gradients may de- viate from rather than get close to the NE set. A naive bound to evaluate how worse the policy gradients can be is: (xt+1 x Q (etlyg+) + ~x" y (4.
y
x a!+1) 2
-2 (o,)) Q (a, b) (a(a,)) b)].
The troublesome error term in the naive bound is of order 2 Me Q (a. b)
Qa b) Oddist(z', 2)) On the other hand, we show in Appendix C.2 projected optimistic gradient descent/ascent can only provide progress order Oddst (2', 2²)). When x is close to the NE set, the error term can much larger than the progress, i.e., 2 max ()) Q (a, b)
(a, b) << O(dist ()). This prevents us from even showing the local convergence of OGDA.
Intuition of Averaging OGDA, Averaging OGDA tackles the problem (14) by using V V
instead of V='. 'v' to approximate v². The corresponding policy gradients Qa [ L''', Qe [1'] [ xf
good directions in the sense that we can provide a good lower bound for (x* x Q.(V +
(u v:) Q. Q. V''JT'r x/C More specifically, by Lemma 19 and Fact we have
(xt -
"Q.VV" + (y!* y T.Q.V -IIV V'llo.
As in Appendix D.1 the term IIV -V'lle LoIloo is relatively easy to control. Thus, Qa Qo Q.LL'TT
are "good" directions.
More discussions on OGDA. Although Averaging OGDA use the averaging technique achieve global convergence, the averaging technique will make the errors from past iterations fail to decrease exponentially fast. This prevents Averaging OGDA from achieving linear convergence. To get local linear convergence, OGDA a natural candidate because V= depends only on the most recent policies, thus, it avoids errors from the past steps. The problem (14) mentioned above necessitates novel analysis for OGDA. Our strategy for the local linear convergence of OGDA starts
from considering a weighted sum of x x"" Q. y and y yt (Q++1)) x
Let Po denote the uniform distribution on S. As (æ """ attains a Nash equilibrium,
pa't1 -gt (Po) v + (po) 2 0.
Thus, < Va't (Pn) V2 (po) = Vettl 5' (po) Vatth.y .y
(po) + Vz y (po)
V + (po). Then, by applying performance difference lemma (Lemma 20), we have a variant of the MVI property with time-varying coefficients which is in (T6), which can be regarded as variant of the MVI property with time-varying coefficients.
In order utilize (66 to get local linear convergence, we still need to tackle the following two problems:
whether can find a neighborhood of the NE set such that the time-varying coefficients ds),,, (s) in (16) are "stable"?
if the time-varying coefficients (s), (s) in (6) can be "stable" in a small neigh- borhood of the NE set, will the difference between Q' and Q" prevent the local linear convergence?
61

---

Published as a conference paper at ICLR 2023
To address the above questions, we mainly use the two geometric observations in Section S Ob- servation guarantees the p of projected gradient descent/ascent is substantial. This means that the difference between Q and Q: will not be troublesome in deriving the local linear conver- gence. Observation II implies the stability of state visitation distribution. Thus, the time-varying coefficients d', (s), d' (s) will be "stable" when x², z' are approaching the NE set. In other words, find problem-dependee neighborhood where the time-varying coefficients d").. d' (s) will possess some "stability". We remark that since d' (s), (s) can vary rapidly when 2 is far from the NE set, our analysis for OGDA only hold in small neighborhood of the NE set. Whether OGDA has global convergence still an open problem.
62


Reviews:
[{"review_id": "tPdp_ttRnxG", "reviewer": "Reviewer_Uzv1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a symmetric and rational algorithm for finding Nash policies for a two player zero sum Markov game that converges in linear time. Additionally the algorithm proposed does not rely on computing the equilibria of a regularized Markov game. \n\nThe key idea of this work is to combine a slow algorithm that enjoys global convergence to the Nash equilibrium and a fast algorithm whose linear convergence rate is only guaranteed close to the Nash equilibrium. The authors not only show how to instantiate the proposed components of their work but also how to combine them in a single unified algorithm. Importantly, this unification of the two components works despite the fact that the algorithm cannot detect if the iterates are in the linear convergence region of the fast algorithm.", "summary_of_the_review": "In summary, based on the strong and novel results I am recommending acceptance of this work.", "strength_and_weaknesses": "Regarding strengths, to the best of my knowledge the proposed algorithms have state of the art convergence rates for the problem of zero sum Markov games. At the same time, the algorithm remains symmetric and rational and does not rely on regularization, making the results even more surprising.\n\nRegarding the techniques used, they are also to the best of my knowledge novel. While two phase style techniques (global slow rates and local fast rates)  are pretty common even in the case of matrix games, these results are typically analyzing the performance of a single update rule that becomes faster closer to the equilibrium. Here the authors combine two distinct algorithms where one is responsible for the global convergence and the other for the fast rates. These two algorithms do not only have different rates, they are also qualitatively different as one relies on averaging and the other has last-iterate style guarantees. The instantiation of the local algorithm using OGDA may be of independent interest.\n\nRegarding the minor weaknesses of this work, it is still unclear to me why an averaging style algorithm is required for the global step is unclear to me. Since fast convergence is not required, why cannot we employ last iterate results from prior work for this step. If the authors could explain the reasoning, it would be helpful.  \n\n ", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "j6Qr0VfFq4u", "reviewer": "Reviewer_SKfD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "summary_of_the_paper": "This paper consider the problem of finding a Nash equilibrium in 2-player, zero-sum Markov games. The contributions are 1) a decentralized, meta-algorithm Homotopy-PO that converges to a Nash equilibrium at a global linear rate. It relies on two subroutines, Global-Slow and Local-Fast. 2) An instantiation of Homotopy-PO with choices for Global-Slow and Local-Fast that achieves the global linear rate of convergence. Further, the algorithms provided are symmetric and rational.", "summary_of_the_review": "Based on the above comments, the paper is a clear accept.", "strength_and_weaknesses": "# Strengths\n- Finding Nash equilibria in 2-player Markov games is an important problem. Existing methods are restricted to special classes of games (matrix games); have sublinear rates of convergence; or are approximations of Nash equilibria (such as quantal response equilibria).\n- The symmetric, decentralized setting, in which the algorithm is symmetric wrt the agents and the agents observe dynamic, local information without being aware of the policy of the opponent.\n- The methods proposed are novel; the idea of using a slow, global algorithm used to guide a fast, local algorithm that only works on a neighborhood of a Nash equilibrium is very interesting.\n- The fast, local algorithm proposed is of independent interest.\n\n# Weaknesses\n- Unclear how practical the algorithms are, as no implementation or empirical validation is provided. It would be nice if the global, linear convergence actually translates into a fast and practical algorithm.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "NFAdxlzION", "reviewer": "Reviewer_p6su", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates decentralized policy optimization algorithm for two-player zero-sum discounted Markov games. In particular, it proposes a decentralized meta-algorithm called $\\mathsf{Homotopy}$-$\\mathsf{PO}$ that has global linear convergence rate if the its two base algorithms have the desired properties. Then, it proves that Averaging OGDA and OGDA can serve as the two base algorithms for $\\mathsf{Homotopy}$-$\\mathsf{PO}$, resulting a concrete decentralized algorithm with linear convergence rate.", "summary_of_the_review": "This paper proposes the first decentralized algorithm with linear convergence rate in discounted two-player zero-sum Markov games, which is considered to be novel and significant. Meanwhile, it also contains some novel techniques may be of independent interest. Although its practicability looks limited now, it is okay to leave it as future work.", "strength_and_weaknesses": "### Strengths\nThis paper proposes the first decentralized algorithm with global linear convergence rate, which is considered to be significant. Meanwhile, the construction of the meta-algorithm is based on a very clear and novel intuition, which has potential wider application since it only requires the base algorithms to satisfy certain properties. Furthermore, proving that OGDA has local linear convergence itself is also considered to be significant and novel.\n\n### Weaknesses\nBased on the decentralized implementation of the two base algorithms OGDA and Averaging OGDA, it seems translating the current optimization algorithm to a learning algorithm contains some inherent difficulty. In particular, the initialization needs to solve the marginal MDP completely, which looks hard to approximate during the learning process. Is there any approach to relax it so that we can translate it to a learning algorithm easily? \n\nNevertheless, from my perspective, it is okay to leave this as future work for now.\n\n---\n\n**Post-rebuttal update:** concerns and questions have been well-addressed.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "AKXdh52tEd", "reviewer": "Reviewer_5eyy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies policy optimization for Markov Games to find the Nash equilibrium. The authors parameterize the policy by directly considering the probability for each state and action. The key contribution of this work is to propose a slow-fast framework with a series of conditions, and prove that any pair of slow and fast optimization algorithms that satisfy the above conditions, can enjoy a linear convergence rate to the Nash equilibrium. ", "summary_of_the_review": "In general, this paper did a good job of showing a global linear convergence to the Nash equilibrium for Markov Games. The idea to use hidden phases to analyze the convergence of slow and fast algorithms is quite interesting, and I believe this can be extended to other policy optimization problems considered in reinforcement learning. The only shortcoming of this paper is the lack of experiments, and I suggest the authors do some at least on some simulated datasets, especially to see how the large constant ($(1-c\\eta^2)^{-poly}$ in (9)) affect the final convergence behavior. ", "strength_and_weaknesses": "Pros:\n- The presentation is very clear, and the writing is also flawless. \n- The proposed framework is general, and the convergence result is important. \n\nCons:\n- No experiments. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%