Policy Optimization for Markov Games: Unified Framework and Faster Convergence
Authors: Runyu Zhang
Qinghua Liu
Huan Wang
Caiming Xiong
Na Li
Yu Bai
Venue: NeurIPS 2022 Accept (2022)
Keywords: policy optimization
multi-agent reinforcement learning
reinforcement learning theory
Markov games

Abstract: This paper studies policy optimization algorithms for multi-agent reinforcement learning. We begin by proposing an algorithm framework for two-player zero-sum Markov Games in the full-information setting, where each iteration consists of a policy update step at each state using a certain matrix game algorithm, and a value update step with a certain learning rate. This framework unifies many existing and new policy optimization algorithms. We show that the \emph{state-wise average policy} of this algorithm converges to an approximate Nash equilibrium (NE) of the game, as long as the matrix game algorithms achieve low weighted regret at each state, with respect to weights determined by the speed of the value updates. Next, we show that this framework instantiated with the Optimistic Follow-The-Regularized-Leader (OFTRL) algorithm at each state (and smooth value updates) can find an $\mathcal{\widetilde{O}}(T^{-5/6})$ approximate NE in $T$ iterations, and a similar algorithm with slightly modified value update rule achieves a faster $\mathcal{\widetilde{O}}(T^{-1})$ convergence rate. These improve over the current best $\mathcal{\widetilde{O}}(T^{-1/2})$ rate of symmetric policy optimization type algorithms. We also extend this algorithm to multi-player general-sum Markov Games and show an $\mathcal{\widetilde{O}}(T^{-3/4})$ convergence rate to Coarse Correlated Equilibria (CCE). Finally, we provide a numerical example to verify our theory and investigate the importance of smooth value updates, and find that using ''eager'' value updates instead (equivalent to the independent natural policy gradient algorithm) may significantly slow down the convergence, even on a simple game with $H=2$ layers.

Policy Optimization for Markov Games: Unified Framework and Faster Convergence
Runyu Zhang" Harvard University
Qinghua Liu" Princeton University ginghual@princeton. edu
Huan Wang Salesforce Research huan , wang@aalesforce.com
runyuzhangdfas. harvard.edu
Caiming Xiong Salesforce Research
Na Li Harvard University nal 1 @seas harvard. edu
Yu Bai
Salesforce Research yu. baiesalesforee. com
cxiong@ealeeforce.. com
Abstract
This paper studies policy optimization algorithms for multi-agent reinforcement learning. We begin by proposing an algorithm framework for two-player zero-sum Markov Games in the full-information setting, where each iteration consists of a policy update step at each state using a certain matrix game algorithm, and value update step with certain learning rate. This framework unifies many existing and new policy optimization algorithms. We show that the state-wise average policy this algorithm converges to approximate Nash equilibrium (NE) of the game, long as the matrix game algorithms achieve low weighted regret at each state, with respect to weights determined by the speed of the value updates. Next, we show that this framework instantiated with the Optimistic Follow- The--hh-RRe Haae--Rgularized--ee Leader (OFTRL) algorithm at each state (and smooth value updates) can find an 57 approximate NE in T' iterations, and a similar algorithm with slightly modified value update rule achieves a faster O(T-1) convergence rate. These improve over the current best ( 1/2) rate of symmetric policy optimization type algorithms. We also extend this algorithm multi-player general-sum Markov Games and show (3/43 convergence rate Coarse Correlated Equilibria (CCE). Finally, we provide a numerical example to verify our theory and investigate the importance of smooth value updates, and find that using "eager" value updates instead (equivalent to the independent natural policy gradient algorithm) may significantly slow down the convergence, even on a simple game with layers.
1 Introduction
Policy optimization, i.c. algorithms that learn to make sequential decisions by local search on the agent's policy directly, is a widely used class of algorithms reinforcement learning [40, 44, 45]. Policy optimization algorithms are particularly advantageous in the multi-agent reinforcement learning (MARL) setting (e.g. compared with value-based counterparts), due their typically lower representational cost and better scalability in both training and execution. A variety of policy optimization algorithms such as Independent PPO [14], MAPPO [56], QMix [42] have been proposed to solve real-world MARL problems [4, 39, 43). These algorithms share same high-level structure with iterative value updates (for certain value estimates) and policy updates (often independently with each agent) using information from the value estimates and/or true rewards.
TTee two authors contributed equally to this work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

While policy optimization for MARL has been studied theoretically in growing body of work, there are still gaps between algorithms used in practice and provably-efficiees algorithms studied in in practice generally follow two natural design principles: symmetric updates among all agents, and simultaneous learning of values and policies [59, 56]. By contrast, policy optimization algorithms studied in theory often diverge from these principles and incorporate some tweaks, such as (i) asymmetric updates, where one agent takes a much smaller learning rate than the others (two time-scale) [11] or waits until the other agents learn an approximate best response [62]; and (ii) batch-like learning, where policies are optimized to sufficient precision with respect to the current value estimate before the next value update [8]. There is so far lacking of systematic studies on the performance of the more vanilla policy optimization algorithms following the above two principles, even under the setting where full-ine cull-information feedback from the game is available.
Towards bridging these gaps, this paper studies policy optimization algorithms for Markov games, with focus on algorithms with symmetric updates and simultaneous learning of values and policies. Our contributions can be summarized as follows:
We propose an algorithm framework for two-player zero-sum Markov games in the full- information setting (Section 3). This framework unifies many existing and new policy op- timization algorithms such as Nash V-Learning, Gradient Descent/Ascent, as well as seemingly disparate algorithms such as Nash Q-Learning (Section 3.2). We prove that the state-wise average policy outputted by the above algorithm is an approximate Nash Equilibrium (NE), so long as suitable per-state weighted regrets are bounded (Section 3.1). This generic result can be instantiated in modular fashion to derive convergence guarantees for the many examples above.
We instantiate our framework to show that a new algorithm based on Optimistic Follow-The Regularized-Leader (OFTRL) and smooth value updates finds an (T7 approximate NE in T iterations (Section 4). This improves over the current best rate of ((T-1/2) achieved by symmetric policy optimization type algorithms. In addition, we also propose a slightly modified OFTRL algorithm that further improves the rate to Ö(T-1), which matches with the known best rate for all policy optimization type algorithm.
We additionally extend the above OFTRL algorithm to multi-player general-sum Markov games and show an O(T-3/4) convergence rate to Coarse Correlated Equilibria (CCE), which is also the first rate faster than (T2) for policy optimization in general-sum Markov games (Section 1)..
We perform simulations on a carefully constructed zero-sum Markov game with H = 2 layers to verify convergence guarantees. The numerical tests further suggest the importance of smooth value updates: the Independent Natural Policy Gradient algorithm (as one instantiation of our algorithm framework with "eager" value updates) appears converge much slower (Section 5).
1.1 Related work
Two-plas awo-player zero-sum MGs Markov games (MGs) [30] (also known as Stochastic Games [47]) is widely studied model for multi-agent reinforcement learning. In the most basic setting of two- player zero-sum MGs, algorithms for computing the NE have been extensively studied in both the full-information setting [31, 20, 19] and the cumple-based/onling setting [6, 52, 22, 48, 58, 2, 55, 3, 33, 25, 21, 57, 10, 34]. Our algorithm framework incorporates (the full-information version of) several algorithms in this line of work.
Policy optimization for zero-sum MGs Policy optimization for single-agent Markov Decision Processes has been extensively in a recent line of work, e.g. [1, 5, 32, 46. 37, 35, 7, 15, 54] and the many references therein. For two-player zero-sum MGs, the Nash V-Learning algorithm of Bai independent
et al. [3] (originally proposed for the sample-based online setting) can be viewed policy optimization algorithm, and can be adapted the full-information setting with ((7-1/2) convergence rate. Daskalakis et al. [1 I] prove that the independent policy gradient algorithm with an asymmetric two time-scale learning rate can learn the NE (for one player only) with polynomial iteration/sample complexity. Zhao et al. [62] show that another asymmetric algorithm that simulates a policy gradient/best response dynamics converges to NE with 0(1/T) rate. Cen et al. [8] use a symmetric optimistic (extragradient) subroutine for matrix games to learn zero-sum MGs in a layer-wise fashion (the matrix games each state are learned to sufficient precision before the

---

backup, more like a Value Iteration type algorithm), and also derive an ((1/T) convergence rate. The closest our work is Wei al. [53] which proves that Optimistic Gradient Descent/Ascent (OGDA), combined with smooth value updates at all layers simultaneously, converges to an NE with O(T-1/2) rate for both the average duality gap and the last iterate. The 5(6- rate of our OFTRL algorithm improves over [53] and is the first such faster rate for symmetric, policy optimization type algorithms. The (1/TT) rate of our modified OFTRL algorithm matches with rates in [62, 7], while still maintaining symmetric update and simultaneous learning of values and policies.
Multi-player general-sum MGs A recent line of work shows that a generalization of the V- learning algorithm to the multi-player general-sum setting can learn Coarse Correlated Equilibria (CCE) [49, 24, 36] and Correlated Equilibria (CE) [49, 24]. The algorithmic designs in these works are specially tailored to the sample-based setting, where the best possible rate is (TT-1/2). In contrast, this paper considers the full-information setting and proposes new algorithms achieving the faster ((T-3/4) for learning CCE in general-sum MGs. The complexity of computing or learning a Markovian or stationary Markovian CCE has been studied in [13, 26]. Another recent line of work considers learning NE in Markov Potential Games [60, 29, 49, 16, 61], which can be seen as a cooperative-type subclass of general-sum MGs.
Optimistic algorithms in normal-form games Technically, our accelerated rates build on the recent line of work on faster rates for optimistic no-regret algorithms in normal-form games [50, 41, 12]. Specifically, our ( rate for two-player zero-sum MGs builds upon a first-order smoothness analysis of [9], our improved O(T-1) rate in the same setting (achieved by the modified OFTRL algorithm) leverages analysis of [41, 50] on bounding the summed regret over the two players, and our (T-3/41) rate for multi-player general-sum MGs follows from the RVU-property [50, Definition 3]. Our incorporation of these techniques involves non-trivial new components such as weighted first-order smoothness bounds and handling changing game rewards.
Preliminaries
We consider the tabular episodic (finitehhoriznd wwo-player-zerosume Markov games (MGs), which can be denoted as M(H, A, P, where H is the horizon length; S is the state space with S = S; A. B are the action space of the max-player and min-player respectively, with |A| = A, B B; = [P is the transition probabilities, where each (s')ss a, b) gives the probability of / are the reward functions, such that (s, a, b) is reward of the max-player and -T% (s. a, b) is the reward of the min-player at time step h and state-action (s, a, b). In each episode, the MG starts with a deterministic initial state $1. Then at each time step 1 < h < H, both players observes the state 8h, the max-player takes an action On E A, and the min-player takes an action by B. Then, both players receive their rewards (s(sn, any bb) and r (Sh, On bn), respectively, and the system transits to the next state $6+1 ~ Px an br)-
transition to state s' from state-action (s, a, b); r = {rx)
Policies & value functions A (Markov) policy μ of the max-player is collection of policies a = (us, : S + A where each μu (+(ss) E A specifies the probability of taking action as at (h, s)). Similarly, a (Markov) policy of the min-player is defined as {2h S - As}. For any policy (H, (not necessarily Markov), we use V/t S - IR and Q S x A x B R to denote the value function and Q-function at time step h, respectively, i.c.
V. (s) = Ep,, Enew The (su an, bw) 8h =
h
(1)
Q4 (s, b) = Ep.. EH (sw aw, bwr) 8h = ag = a, by =
(2)
For notational simplicity, we use the following abbreviation: [P,, V V[(s, b) == E. P. (.1s...8) (ss') for any value function V. By definition of the value functions and Q-functions, we have the following Bellman equations
Q b) = (rh + PA PAVE")) ( a, a,6),
2 Even we specialize their algorithms to the full -all-informatin setting, the attained rates are no better than 0(2-1/2) because the bandit subroutines they deployed in V-Jearning converge no faster than 1/2 even the simplest setting of full-information matrix games. This assumes deterministic rewards; results can be generalized directly to the case of stochastic rewards.
3

---

V b) = Ba-pn ((1)), (1))))))))))))) 10a (s, b)] = 12 () ((((s))) x v(-ls)).
The goal for the max-player is to maximize the value function, whereas the goal for the min-player is to minimize the value function.
Best response & Nash equilibrium For any Markov policy je of a max-player, there exists best response for the min- player, which can be taken as Markov policy v (1) such that V/= V.u.e (() (s)
inf, (s) for all (s, h) E S x [H]. For simplicity we define V/t1l := Vi (w) By symmetry, we can also define (v) and V, is known (e.g. [17]) that there exist Markov policies (u", .²" that perform optimally against best responses. These policies are also equivalent to Nash Equilibria (NEs) of the game, where no player can gain by switching
different policy unilaterally. It can also be shown that any NE (p"vv") satisfies the following, minimax equation
sup,, inl, V.ll (s) = Vid (8) = s (s).
Thus, while the NE policy (H**, 2/*) may not be unique, all of them share the same value functions, which we denote as Vix == Vi ,20" The Q-function Q7 can be defined similarly. In this paper, our main goal is to find an approximate NE, which formally defined below.
Definition (s-approximate Nash Equilibrium), For any E 2 0, a policy (H, v) is an e-approximate Nash Equilibrium (s-NE) if NEGap((, v)= == Vt (si) V/t (81) S.
Full-information setting We consider finding approximate NE under the full-information setting, where we can guery the exact value of Tı + +P Vh+1 E 5xAx for any layer h E [H] and
V function Va+1 E RS. Further, the majority of algorithms are policy optimization algorithms that only query (Fh + PA Vh+1)) E R and (ry + P Vx+1) An E ÆSxB for policies Uh. uh- (See
Appendix I.1 for additional discussions.)
x B + R. we define shorthand [(m))] Qn)))(s) == (Qn(s,-. :, (, x (-(s) for any policy (H, v). Similarly, we let [Q& ub (8, :) == (Bseen(1))) (-1)))(nn ; RA, and [Q (s) == Bampa(11))
Additional notation For any (h, s) E [H] x S and Q function Qn S x Ax
R
We use AV B BB.
3 An algorithm framework for zero-sum Markov games
We begin by presenting an algorithm framework that unifies many existing and new algorithms for two-player zero-sum Markov Games, and its performance guarantee that could be specialized to yield concrete convergence results for many specific algorithms.
Our algorithm framework, described in Algorithm 1, consists of two main components: the policy update step computing policies (n², v²), and the value update step computing the Q estimate Q1 's.
Policy update via matrix game algorithms In the policy update step (Line 5), for each (h, s). the two players update policies (4), (1|s), v/ (+Is) at (h, using some matrix game algorithm MatrixGameAlg which takes as input all past Q matrices and all past policies of both players. The MatrixGameAlg offers a flexible interface that allows many choices such as the matrix NE subroutine over the most recent Q matrix MatrixNE(Q), (s. (s...-)), )). or any independent no-regret algorithm (for both players), such as Toelow-Thhe-Reglarr Gradient Descent-Ascent (11) considered in the examples later.
Leader (FTRL) (10) or projected
Value update with learning rate (3e} For any (h, 8, a, b), the value update step (Line 6) updates Qh. (s. a, b) by the newest value function Ta + PPlluh Qh+ whaa propagated from layer + 1, using a sequence of learning rates (.e)221 which we assume to be within [0, 1] (with B, == 1). (3.)
controls the speed of the value update, with two important special cases:
(1) Eager value updates, where we set 3r = 1 so that Q3 performs policy evaluation of the current policy (n²,, v²), that is, Q₁ =
(2) Smooth (incremental) value updates, where choose 3, + 0 as - co. In this case, the Q moves slower (resembling a critic in Actor-Critic like algorithms), and becomes a weighted average of all past updates. A standard choice that is frequently used is from [23] (and many subsequent work).
===;; == (H + (H + t).
(3)

---

Algorithm Algorithm framework for two-player zero-sum Markov Games
1: Require: Learning rate {Br)121 C [0, 1] (with 3 1); Algorithm MatrixGameAlg
2: Initialize: 0% (s, a, + 11 h + for all (h, 5, b) E x B.
3: for t 1,..,, do
4: for h = ...... do
5: Policy update: Update policies for all E S:
(((1ss) + MatrixGameAlg (10 (th()ss) (
6: Value update: Update Q-value for all (s, b) E A
(s, (1 " + 3. (r% Pal((4++) ) Qh+ (s), (4)
7: Output: State-wise average policy (Ti ".T), ( with By defined in (6):
T (+1s) Ei= (1))) (1ls) Ei (11))))))) for all (h, 8) E [A]] S. (5)
For any {Be}, the update (4) implies that
(s a, E
1 ((((r Pn(( "h+ (s. (s.a.
where Bi's are group of weights summing one (Ei- B 1) defined as
8 3:
B = IT 3,)3; for i i [t-1] 1].
(6)
Note that with smooth value updates (3, < 1), Qi is not necessarily the Q-function of any policy. Upon finishing, the algorithm outputs the state-wise average policy (fT", "TT) defined in (5), where each [iA (+Is) is the weighted average of ut, (-Is) using weights { T (and similarly for Di ), which we remark can implemented efficiently using moving averages (cf. Appendix C.I).
Symmetric & simultaneous learning, (de)centralization We remark that Algorithm 1 by defini- tion performs simultancous learning (of policies and values) all layers, and also yields symmetric (policy) updates if MatrixGameAlg is a symmetric algorithm with respect to μ and v. Also, although Algorithm 1 appears to be centralized algorithm as maintains Q values in (4), this does not preclude possibilities that the algorithm can be executed in a decentralized fashion. This can happen e.g. when the Q-update (4) can be rewritten as an equivalent V-update (cf. Example 2).
3.1 Theoretical guarantee
We are now ready to state the main theoretical guarantee of Algorithm 1, which states that the (7t", 2TT) ) is an approximate NE, as long the algorithm achieves low per-state weighted regrets w.r.t.
weights { defined as
regh,, (s) max W CA Ei Bi (ul (-1s), 10/4 (s,:)), regh, (8) == max ED Ei B (v/((1s) - ut, [(O)) (())) (s,)).
(7)
regi. = max,s max max(reg (5), regh
Theorem 2 (Main guarantee of Algorithm 1). Suppose that the per-state regrets can upper- bounded regt < feg,,for all (h,t) E [H]] [TT, where regh non-increasing in t; reg), regh
(+1
for all i 1. Then, the oulput policy (Ti" GT)) of Algorithm I satisfies
1 Σ max regi. + HH log T hE(H]
NT ,T") -
SC
max regi HE(M
(8)
for all T 222 2 and some absolute constant C > 0, where C3 is a constant depending on (Bchern
C3 = sup Σ 8 2 1.
(9)
Specifically, cg (1+ + at
H+1 and Cg if Br = 1. カ
5

---

Bound (8) is typically dominated by the second term on the right hand side, suggesting that the NEGap can be bounded by the average weighted regret Ö T Ei= max, regh, ). if c3 = O(1) Theorem 2 serves modular tool for analyzing broad class of algorithms: As long as this average regret is sublinear in ''' (including- no-regret algorithms), the output policy will be an approximate NE. We emphasize though that this result is not yet end-to-end, as each regh, is a weighted regret w.r.t. the particular set of weights {Bi) minimizing which may require careful algorithm designs and/or case-by-case analyses. We provide some concrete examples in Section 3.2 to demonstrate the usefulness of Theorem 2.
not limited to to-choosing MatrixGameAlg as uncoupled
We remark that the state-wise average policy considered in Theorem 2 is average policy that is also Markovian by definition, which is different from existing work which considers either the (Markovian) last iterate [53] or non-Markovian average policies (e.g- [3]). However, this guarantee relies on full-information feedback (so that per-state regret bounds are available), and it remains an open question how such guarantees could be generalized sample-based settings.
Proof overview The proof of Theorem 2 follows by (1) bounding NEGap("" (D7) in terms of per- state regrets w.r.t the Nash value functions Q7, 's by performance difference arguments (Lemma C.I); (2) recursively bounding the value estimation error 0% == 1 0% ooo (Lemma C.2) which yields the constant Ga; and (3) combining the above to translate the regret from Q 's to Q 's (which we assume to be bounded by regi) and obtain the theorem. The full proof can be found in Appendix C.
3.2 Examples
We now demonstrate the generality of Algorithm and Theorem 2 by showing that they subsume many existing algorithms (and yield new algorithms) for www-player-zero-sun Markov games, and provide new guarantees with the particular output policy (5).
Example 1 (Nash V-Learning [3], full-information version): The full algorithm (Algorithm 5) can be found in Appendix D.I. The algorithm is special case of Algorithm I with 3. = ar (H + 1) + (), and MatrixGameAlg chosen as the weighted FTRL algorithm
wi ( (0 (b(s)) xc. exp (- "
W0-1 Σ Wi ((1) 14 (s.))
(aaas Xa exp
w111
(10)
where w, = := at/at. Combining Theorem 2 with the standard regret bound of weighted FTRL, this algorithm achieves NFGGap(T? (TT)== S 5(H7/2 /VT) choosing 1j = 1/vT (Proposition D.2).
Additionally, although the original Nash V-learning algorithm [3] updates the V values (which makes
the algorithm implementable a decentralized fashion) instead of the Q values used in Algorithm 1, these two forms are actually equivalent in the full-inffe aull-informttin setting (Proposition D.1). O
Compared with the Ō( / S max{ A, B)/T) guarantee of (the non-Markovian output policy of) Nash V-Learning in the sample-based online setting [3. 51, 24], our rate achieves better (logarithmic) S, A, B dependence due to our full-information setting, and worse Hl dependence which happens as our output policy the (Markovian) state-wise average policies, whose guarantee (Theorem 2) follows from different analysis.
Example 2 (GDA-Critic): This algorithm is a special case of Algorithm 1 with S, a (H + 1) + I), and MatrixGameAlg as projected gradient descent/ascent (GDA), i.e.
+ (+1s) (s)), (/(++s) (1ss))n(())))(((())))))))
(11)
Similar as Nash V-Learning, GDA-Critic also admits an equivalent form with V value updates (full description in Algorithm 6). As GDA achieves weighted regret bounds with any monotone weights including { (Lemma B.)), we can invoke Theorem 2 to show that this algorithm achieves NEGap(A" ,D"T & O(H7/2 1222//T) if we choose 17 x 1/VT (Proposition D.4).
The GDA-critic algorithm is also similar to the OGDA-MG algorithm of Wei et al. [53], except that we use the (non-optimistic) vanilla version of GDA. To our best knowledge, the above algorithm and guarantee are not known. We remark that even ignoring difference between GDA and OGDA, the

---

above guarantee cannot be obtained by direct adaptation of the results of [53] which focus on either the average duality gap and/or last-iterate convergence.
Besides the above examples, Algorithm also incorporates the following algorithms which are typically not categorized as policy optimization algorithms (see Appendix 1.2 for discussion of the categorization).
Example 3 (Nash Q-Learning [20, 3]. full-information version): This algorithm is special case of Algorithm with 3; = 02 = (H + 1)/(H + t) and MatrixGameAlg as the matrix Nash subroutine
(-1s), (-1s) MatrixNE(Q), ()) = arg min max f 1h (s,:s()
(EEA WEAB
not by default no-regret small (due to the small aạ) we can show that is close to (hypothetical) -Be-The-Leader style algorithm that computes the matrix NE of the current Q matrix Q which achieves I regret (Lemma D.3). Combining this with Theorem 2 shows that this algorithm achieves NEGap(TT -²") < ((H*/TT) (Proposition D.5). O
(Full description in Algorithm 7.) Although MatrixNE(Qh
algorithm, using the fact that | - 1%=²
Example 4 (Nash Policy Iteration (Nash-PD): This classical algorithm (Algorithm 8) performs iterative policy evaluation and policy improvement (also similar to Nash Value Iteration [47, 2. 33]):
(ut (-1s)) Mat (s,
(12)
This is also special case of Algorithm 1 with B, and MatrixGameAAg as MatrixNE. It standard result that this algorithm converges exactly (achieving zero NE gap) in steps, and this fact can be obtained using our framework as well (Proposition D.6). O
Fast convergence of optimistic FTRL
In this section, instantiate Algorithm 1 by choosing MatrixGameAlg the Optimistic Follow- Thne-Regularized-Leee Leader (OFTRL) algorithm. OFTRL is also an uncoupled no-regret algorithm that is known to enjoy faster convergence than standard FTRL under additional loss smoothness assumptions [41, 50, 9, 12]. We show that, using OFTRL, Algorithm enjoys faster convergence than the (1/vVT) rate of using FTRL or GDA (cf. Example & 2).
Concretely,
the following weighted OFTRL algorithm at each (h, s,t):
11, (als) &a exp ((n/we) Σ w. wx w (2h 1/4 (s,
(13)
5 (bls) xa, exp (-(n/ws) E (;((()) (s, + ((Q) 1) MM ( (s,
where wi is the same weights as defined Example I, and we choose 3r 04 = (H 1)/ + l).
Theorem 3 (Fast convergence of OFTRL in zero-sum Markov Games). Suppose Algorithu is
instantiated with B, a = (H + 1)/(H + t) and MatrixGameAlg to be the OFTRL algorithm (13) with any 17 S 1/H (full description in Algorithm 9). Then the per-state regret can be bounded as follows for some absolute constant C' > 0:
2 log(A B) + rp HH) for all (h, E [H] [T].
regl, < rege == C
(14)
nt
Further, choosing 17 = poly (H, (A v Bog T)- T 1/6, the output (state-wise average) policy (p" DT)) achieves approximate NE guarantee
NEGap(pT ( (H log(A log T -/06)
(15)
To our best knowledge, the 5(T-5/6) rate asserted in Theorem 3 is the first rate faster than the standard Õ(L/VT) for symmetric, policy optimization type algorithms in two-player zero-sum Markov games. The closest existing result to this is of Wei et al. [53], who analyze the OGDA algorithm with smooth value updates and show ((L/VT) convergence of both the average NEGap
7

---

and the NEGap of the last-iterate. However, these only imply at most a ((1/VT) rate for the average policies, and not faster rate*. Cen al. [8], Zhao et al. [62] show (11/T) convergence of algorithms with optimistic muddient-based policy updates, which are however very different styles of algorithms that either performs layer-wise learning (the matrix games at each state are learned to sufficient precision before the backup) similar as Value Iteration (the matrix games at each state learned to sufficient precision before the backup) [8], or uses strongly asymmelric updates that simulate a policy gradient-best response dynamics [62]. By contrast, our Algorithm 9 (as well as its modified version in Algorithm 10 with Ó(T-1) rate) runs symmetric no-regret dynamics for both players, simultaneously at all layers.
Proof overview The proof of Theorem 3 (deferred to Appendix E) builds upon the recent line of work on fast convergence of optimistic algorithms [41, 50, 9], in particular the work of Chen and Peng [9] which shows an (T-55/6) convergence rate of OFTRL for two-player normal-form games. Our regret bound (14) generalizes this result non-trivially by additionally handling (1) The weighted regret, which requires bounding the weighted stability of the OFTRL iterates by new analysis of the potential functions (Lemma B.4), and (2) The errors induced by changing game matrices, as Q% ())))) changes over Plugging (14) into Theorem 2 yields the policy guarantee (15).
Modified OFTRL algorithm with O(T rate We further slightly modify Algorithm 9 to design a new OFTRL style algorithm with ((T-1) convergence rate (Algorithm 10 and Theorem F.1), which improves over the ((T-5/6) of Theorem 3 and matches the known best convergence rate for policy optimization type algorithms in two-player zero-sum Markov games. Algorithm 10 still uses OFTRL in its policy update step, and the main difference from Algorithm 9 is in its value update step: Rather than maintaining a single 2 the two players now each maintain their own value estimate
Ih Q' which are still updated in an incremental fashion similar to (though not strictly speaking an instantiation of) the update rule (4) in our main algorithm framework. Details of the algorithm as well as the proofs are deferred Appendix F.
4.1 Extension to multi-player general-sum Markov games
Our fast convergence result can be extended to the more general setting of multi-player general-sum Markov games. Concretely, we consider general-sum Markov games with 2 2 players, S states, H steps, where the i-th player has action space A; with Amax := max:e[m] |Ass] and her own reward function. The goal is to find a correlated policy over all players that is an approximate Coarse Correlated Equilibrium (CCE) of the game (see Appendix G.1 for the detailed setup).
We show that the OFTRL algorithm works for general-sum Markov games as well, with fast (3743/4) convergence CCE. The formal statement and proof is in Theorem G.I & Appendix G.4.
Theorem 4 (Fast convergence of OFTRL in general-sum Markov Games; Informal version of Theo- rem G.1). For m-player general-sum Markov Games, running the OFTRL algorithm (Algoritium 12) for T rounds, the output (correlated) policy से is an E-approximate CCE, where
E S Opoly((H, log Amax, Mmaxx,lgg7 T) (m - 1)1/2.T-33
A baseline result for this problem would be O(T-1/2), which may be obtained directly by adapting existing proofs of the V-Learning algorithm [49, 24] to the full-information setting. Our Theorem shows that a faster (3743/4) rate available by using the OFTRL algorithm, which to our best knowledge is the first such result for policy optimization in general-sum Markov games. We also remark that the output policy î above not a state-wise average policy as in the zero-sum setting, but rather mixture policy that is in general Mon-Markov (cf. Algorithm 13), which is similar as (and slightly simpler than) the "certified policies" " used in existing work [3, 49, 24]. The proof of Theorem 4 builds upon the RVU property of OFTRL [50] and additionally handles changing game rewards, similar as in Theorem 3. A proof sketch and comparison with the (5T-5/6) analysis of the zero-sum case can be found in Appendix G.2.
"See also [18] for another example where last-iterates are provably slower than averages.
8

---

5 Simulations
We perform numerical studies on the various policy optimization algorithms. Our goal is two-fold: (1) Verify the convergence guarantees in our theorems and examples; (2) Test some other important special cases of Algorithm that may not yet admit provable guarantee.
To this end, we consider three algorithms covered by the framework in Algorithm 1:
1. FTRL (Nash V-Learning) with smooth value updates Br ox, (Example & Algorithm 5). Here the output policy (f"" are the state-wise averages with weights {ai] and achieves NEGapp(TT, ,TT) S T-1/2 if we choose = T-1/2 (Proposition D.2).
2. OFTRL with smooth value updates B. a₁ (Algorithm 9). Here the output policy (p", .D") are the state- averages with weights
i-1- and achieves NEGap("" ,TT') S 6/6
we choose == T-1/6 (Theorem 3). We also consider the more aggressive choice 1] 1.
3. INPG (Independent Natural Policy Gradients). This algorithm is an instantiation of Algo- rithm 1 (cf. Appendix H.3 for formal justificationn) with eager value updates (Bt = 1), and MatrixGameAlg chosen as standard unweighted FTRL (a.k.a. Hedge) for all s,t):
p (als) Xa 1 (als) exp(1) "0
Mbs)) X6 (bbss) exp "/ (Q: (0))
For this algorithm, we choose two standard learning rates: 1j = 1, and 1j = 7- and use the vanilla (state-wise) average as the output policies (since the last-iterate is known to be eyclic):
+
of = E (11s)) for all (h, E [H] x S.
The main motivation for considering INPG is that is a natural generalization of both the widely- studied NPG algorithm for single-agent RI., and the standard Hedge algorithm for zero-sum matrix games. In both cases the algorithm admits favorable convergence guarantees: NPG converges with rate ((T-1) [1, 27, 38, 7] (in both last iterate and averaging) using 7 = 0(1); Hedge converges with rate (TT)1/2) in zero-sum matrix games (e.g. [41]) using v x T-1/2, However, to our best knowledge, the convergence of INPG for zero-sum Markov games is unclear, and it is commented by Wei al. [53, Section 5] that eager value updates (3. 1) could cause the value function of the (h + 1) 1)th layer to oscillate, which make learning unstable or even biased within the h-th layer.
A two-layer numerical example We design a simple zero-sum Markov game with two layers and small state/action spaces (H = 2, S 4, A = 2; see Appendix H.1 for the detailed description). The main feature of this game is that the reward in the first layer is much lower magnitude than that of the second layer (the scale is roughly (s) & 0.1 (2 ;,D, which may exaggerate the aforementioned unstable effect. We also choose a careful initialization (xe', .v') which non-uniform (and modify the FTRL/ / OFTRL algorithms to start at this initialization, cf. Appendix H.1) but with all entries bounded in [0.15, 0.85). We test all three algorithms above on this game, with this initialization, T E {103,3 3 x 103, 10 102...., 10"). and 1) chosen correspondingly as described above.
Results Figure 1a plots the NEGap of the final output policies, one for each {algorithm, (T. J. Observe that FTRL. converges with rate roughly 7-5570 < T-1/2, and OFTRL with = 1/6 converges with rate -835 z T-5/6 both corroborating our theory. Further, OFTRL with 1 = 1 appears to converge with rate T- showing this may be an interesting open theoretical question.
On the other hand, the INPG algorithm appears to be much slower: The r = 1 version does not seem to converge, whereas the convergence of n- = 1/2 version is not clear but at least substantially slower than 112 -308 given by the linear fit).
To further understand the behavior of INPG, we visualize its layer-wise NEGap's for E {1,2) (on our example), defined as the NEGap of the h-th layer's policies with respect to Q;
NEGap-Layer-h(yu.. max. (max,
p1 TitT (+) min,; [nT (s) h= 1,2.
Note that NEGap-Layer- is lower bound of NEGap(Jr 2) (cf. Appendix H.3) and thus needs to be minimized by any convergent algorithm. By contrast, on our example, NEGap-Layer-2 concerned with the last layer only, and can be minimized by any algorithm that works on matrix games.

---

(a) Overall NEGap
(b) NEGap layer h
(c) NEGap on layer h
(8. L.w
100 100 19
I8 o.
(8 ao 7-10)
INC ginn
Total
ons
28:2
step
Figure 1: (a) NEGap of final output policies (y-axis) against total # iterations T (x-axxs) on the two-layer example (cf. Appendix HI.I) in log-log scale. Each dot represents a different run with its own (T. The scalings of the form ~ T are obtained via best linear fits in the log space. (b,c) Layer-wise NEGaps (y-axis, log-scale) against itcration count (x-axis) for (INPG, FTRL. on a single run with 102 and ny = 7/2/2
Figure lb & Ic plot the layer-wise NEGap's of INPG against FTRL, the single run with 7 10 and = T-1/22 As expected, the NEGap-Layer-2 converges nicely for both algorithms with similar rates (Figure 1b) albeit the oscillation of INPG, whereas their behavior on NEGap-Layer-1 drastically different: FTRL still converges, whereas INPG seems to be oscillating around non-zero bias (Figure Ic). This suggests that INPG may indeed be suffer from a non-vanishing bias in the first layer caused by the second layer's learning dynamics. (See Appendix H.2 for additional illustrations.) would an interesting open question to investigate the convergence of INPG theoretically.
Conclusion
This paper provides a unified framework for analyzing a large class policy optimization algorithms for two-player zero-sum Markov games. Using our framework, prove new fast convergence rates for the OFTRL algorithm with smooth value updates: 5/0) for learning Nash Equilibria two-player zero-sum Markov games, which can be further accelerated to (T-1) by slightly modifying
the framework; and -3443/4) for learning Coarse Correlated Equilibria in multi-player general-sum Markov games. We further demonstrate the importance smooth value updates on simple numerical example. We believe our work opens up many other interesting directions, such as whether improved rates (e.g. O(T-1)) are available for the unmodified OFTRL algorithm, further investigation of policy optimization algorithms with eager value updates (such as Independent Natural Policy Gradients). Finally, limitation of this work is its focus on the full-information setting, and it is an important open question how to generalize our analyses to the sample-bas -aseed setting.
Acknowledgment
The authors would like to thank Chi Jin, Yuanhao Wang, Tiancheng Yu. Shicong Cen, and Song Mei for the valuable discussions. Runyu Zhang is supported by NSF AI institute: 21 2112085, ONR YIP: N00014-19-1-2217, NSF CNS: 2003111 and NSF CPS: 2038603.
References
[1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 198):1-76, 2021.
[2] Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
[3] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play, Advances in neural information processing systems, 33:2159-2170, 2020.
[4] N. Bard, J.N. Foerster, S. Chandar, N. Burch, M. Lanctot, H. F. Song, E. Parisotto, V. Dumoulin, Moitra, E. Hughes, et al. The hanabi challenge: new frontier for research. Artificial Intelligence, 280: 103216, 2020.
10

---

[5] J. Bhandari and D. Russo. Global optimality guarantees for policy gradient methods. arXiv preprint 1906:019000078888. 2019.
[6] R. I. Brafman and M. Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-25) 231, 2002.
[7] S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
[8] S. Cen, Y. Wei, and Y. Chi. Fast policy extragradient methods for competitive games with entropy regularization. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances Neural Information Processing Systems, volume 34, pages 27952-27964. Curran Associates, Inc., 2021.
[9] X. Chen and B. Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:1 18990-18999, 2020.
[10] Z. Chen, D. Zhou, and Q. Gu. Almost optimal algorithms for two-player zero-sum linear mixture markov games. In International Conference on Algorithmic Learning Theory, pages 227-261. PMLR, 2022.
[11] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020.
[12] C. Daskalakis, M. Fishelson, and N. Golowich. Near-optimal no-regret learning general games. Advances in Neural Information Processing Systems, 34, 2021.
[13] C. Daskalakis, N. Golowich, and K. Zhang. The complexity of markov equilibrium in stochastic games. arXiv preprint Xii:22244003991 2022.
[14] C. de Witt, Gupta, Makoviichuk, Makoviychuk, P. H. Torr, M. Sun, and S. Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.0953. 2020.
[15] D. Ding, K. Zhang, T. Basar, and M. Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33:8378-8390, 2020.
[16] D. Ding, C.-Y. Wei, Zhang, and Jovanović. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and gane-agnosti convergence. arXiv preprint arXiv:2202.04122 2022.
[17] Filar and K. Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
[18) N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory, pages 1758-1784 PMLR, 2020.
[19] T. D. Hansen, P. B. Miltersen, and U. Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1-16, 2013.
[20] J. Hu and M. P. Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 10N09):1039-1069,,0000 2003.
[21] B. Huang, J. D. Lee, Z. Wang, and Z. Yang. Towards general function approximation in zero-sum markov games. arXiv preprint 21Xiv:2107.14700. 2021.
[22] Z. Jia, L. F. Yang, and M. Wang. Feature-based q-learning for two-player stochastic games. arXiv preprint arXiv: 1 906.00423, 2019.
[23] C. Jin, Z. Allen-Zhu, Bubeck, and M. I. Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.

---

[24] C. Jin, Q. Liu, Y. Wang, and T. Yu. V-learning-a a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint drX1v:2110.14555, 2021.
[25] C. Jin, Q Liu, and T. Yu. The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint wxXv::2006.03352, 2021.
[26] Y. Jin, V. Muthukumar, and A. Sidford. The complexity of infinite-horizon general-sum stochastic games. arXiv preprint arXiv:2204.04186, 2022.
[27] S. Khodadadian, P. R. Jhunjhunwala. S. M. Varma, and S. T. Maguluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint arXiv:2105.01224 2021.
[28] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[29] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106.01963 2021.
[30] M. L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[31] M. L. Littman et al. Friend-or-foe q-learning in general-sum games. In ICML, volume 1, pages 322-328, 2001.
[32] B. Liu, Q. Cai, Z. Yang, and Z. Wang. Neural trust region/proximal policy optimization attains globally optimal policy, Advances neural information processing systems, 32, 2019.
[33] Q Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self- ullyp In International Conference Machine Learning, pages 7001-7010. PMLR, 2021.
[34] Q. Liu, Y. Wang, and C. Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. arXiv preprint arXiv:2203.068033 2022.
[35] Y. Liu, K. Zhang, T. Basar, and W. Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636, 2020.
[36] W. Mao and T. Başar. Provably efficient reinforcement learning in decentralized general-sum markov games. arXiv preprint arXiv:2 10.05682, 2021.
[37] J. Mei, C. Xiao, C. Szepesvari. and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829, PMLR, 2020.
[38] Mei, Dai, C. Xiao, C. Szepesvari, and D. Schuurmans. Understanding the effect of stochasticity in policy optimization. Advances in Neural Information Processing Systems, 34, 2021.
[39] I. Mordatch and P. Abbeel. Emergence of grounded compositional language in multi-agent populations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[40] J. Peters and S. Schaal. Policy gradient methods for robotics. In 2006 IEEE/RS International Conference Intelligent Robots and Systems, pages 2219-2225. IEEF, 2006.
[41] S. Rakhlin and K. Sridharan. Optimization, lcarning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[42] Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, Foerster, and Whiteson. Qmix: Mono- tonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295 4304. PMLR, 2018.
[43] M. Samvelyan, T. Rashid, C. S. De Witt, G. Farquhar, N. Nardelli, T. G. Rudner, C.-M. Hung, H. Torr, J. Foerster, and S. Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv:1902.04443 2019.
12

---

[44] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[45] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1.X.007777.06377 2017.
[46] I.. Shani, Y. Efroni, and S. Mannor. Adaptive trust region policy optimization: Global conver- gence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668-5675, 2020.
[47] I.. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[48] A. Sidford, M. Wang, L. Yang, and Y. Yc. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2020.
[49] Z. Song, S. Mei, and Y. Bai. When can we learn general-sum markov games with a large number of players sample-efficiente arXiv preprint arXiv:2110004184, 2021.
[50] V. Syrgkanis. A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning games. Advances in Neural Information Prucessing Systems, 28, 2015.
[51] Y. Tian, Y. Wang, T. Yu, and S. Sra. Online learning in unknown markov games. In International Conference on Machine Learning, pages 10279-10288, PMLR, 2021.
[52] C.-Y. Wei, Y.-T. Hong, and C.-J. Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems, pages 4987-4997, 2017.
[53] C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horize horizon competitive markov games. In Conference on Learning Theory, pages 4259-4299 PMLR, 2021.
[54] I.. Xiao. On the convergence rates of policy gradient methods. arXiv preprint arX1v:2201.07443, 2022.
[55] Q. Xie, Y. Chen, Z. Wang. and Yang. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. arXiv preprint arXiv:2002.07066, 2020.
[56] C. Yu, A. Velu, E. Vinitsky, Y. Wang, A. Bayen, and Y. Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01990 2021.
[57] T. Yu, Y. Tian, J. Zhang, and Sra. Provably efficient algorithms for multi-objectivve competitive rl. arXiv preprint arXiv:2102.0313 2021.
[58] K. Zhang, S. M. Kakade, T. Başar, and L. Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.07461, 2020.
[59] K. Zhang, Z. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[60] R. Zhang, Z. Ren, and N. Li. Gradient play in multi multi-agent markov stochastic games: Stationary points and convergence. CoRR, Abs/2106.00198, 2021.
[61] R. Zhang, J. Mei, B. Dai, D. Schuurmans, and N. Li. the effect of log-barrier regularization in decentralized softmax gradient play in multiagent systems, 2022.
[62] Y. Zhao, Y. Tian, J. D. Lee, and S. S. Du. Provably efficient policy gradient methods for 2021.
two-player zero-sum markov games. arXiv preprint
13

---

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


Reviews:
[{"review_id": "wYVUXJhTRg6", "reviewer": "Reviewer_S7zG", "summary": "The authors study a unifying meta-algorithm for two-player zero-sum Markov games in the full information setting. The proposed framework aims to generalize some specific algorithms that perform symmetric updates among agents, and the simultaneous learning of policies and their values: relying on upper bound assumptions on the regrets of the employed sub-routines, the authors give a general theoretical result on the convergence of the framework to approximated Nash Equilibria. Beyond providing some examples of how existing algorithms can fit in the proposed framework, the authors use a particular policy update scheme and obtain an overall new algorithm with an improved convergence rate.\n", "questions": "1) On line 267, the authors make consideration of an improved rate for OFTRL which requires two-sided regret bounds.\nThis consideration seems important, but the authors relegate it to a quick citation.\nWhat is the difference between one-sided and two-sided regret?\nThe authors say that two-sided regret does not imply one-sided regrets, but the opposite hold?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written, and it is mathematically sound. The required background is nicely summarized, the theoretical results are well described, and their requirements clearly stated.\nThe attempt to put some order in the huge body of literature on RL algorithm for Markov Games is admirable and welcome.\n\nOn the other side, the strong theoretical limitations required by this work (full-information setting, tabular representation) raise some concern about his impact and importance (either theoretical or, above all, practical).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h0XAPeIN51Z", "reviewer": "Reviewer_N8fq", "summary": "This paper provides a generic framework for two-player zero-sum Markov Games in the full-information setting. The framework has a guarantee on Nash Equilibrium approximation gaps, depending on the per-state weighted regrets provided by different Matrix Game solvers chosen in the framework. Specifically, this paper instantiates the solver to be Nash V-Learning, GDA-Critic, Nash Q-Learning, and Nash-PI, then proves their detailed NE gap guarantees. Further, this paper shows that optimistic FTRL gives a $\\tilde{O} (T^{-5/6})$ NE gap, which is the state-of-the-art for symmetric, policy optimization type algorithms in two-player zero-sum MGs. The results can be extended to multi-player general-sum MGs for a Coarse Correlated Equilibrium. Some simulations corroborate the results and incur interesting new problems.", "questions": "Basically, the question is about (1) and (2) in Weaknesses.\n* What is the difference between policy optimization type/like algorithms?\n* Are there any other taxonomic standards which create barrier or gaps in the NE convergence result?\n\nThe authors can add more details to Section 3.2, Section 4, and Section 5, like a clear summary of different algorithms and their traits, whether they are policy optimization -type or -like, etc. ", "limitations": "As the authors stated that it is an open question on generalization to sample-based setting, there are no other fundamental limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The framework (Algorithm 1) and its general guarantee (Theorem 2) are useful for future works. Researchers may focus on the per-state regrets and then easily get a NE gap using the framework and guarantee.\n2. The $\\tilde{O} (T^{-5/6})$ NE gap for OFTRL is currently the best result.\n3. The simulation results raise new open problems, which are interesting in my view.\n\n\nWeaknesses:\n1. Some of the concepts need to be provided in the main text. For example, full-information learning, policy optimization type/like algorithms, layer-wise learning, one/two-sided regrets, etc.\n2. There lack of comparison between algorithms used in Section 3.2. There are many theoretical results, and the authors did not make it clear whether they are comparable.\n3. In practice we cannot apply full information learning. So there is a need for generalization to sample-based learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TLR_HKNvnJg", "reviewer": "Reviewer_GbK4", "summary": "This paper proposes a unified framework (algorithm 1) for Markov games, with symmetric updates and the simultaneous learning of the value functions and the policies. The main theorem (theorem 2) guarantees that the per-state weighted average policies converge to the $\\epsilon$-NE (or CCE for the multi-player general-sum setting). The authors show some examples that can be subsumed into the unified framework. Finally, the numerical experiments demonstrate the theoretical results.", "questions": "(1) How does state-wise weight average implement? Is the average policy derived as the weighted sum (Line 7 in Algo. 1) on each state separately?\n\n(2) Are the results of INPG the average or other form of policies?\n\n(3) INPG appears to learn faster than FTRL on layer $h=2$ in Fig.1(b) and the NEGap is always lower than the FTRL (FRTL seems to plateau). Can you show the results with more iterations?\n\n(4) Can the framework readily apply in extensive-form games?", "limitations": "The current version only establishes the convergence of the average policy, while averaging multiple or even infinite policies in Markov games is non-trivial. The results will be consolidated with the last-iterate property.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\nThis general framework can capture many relative algorithms and the authors prove the same convergence rate. The framework consists of two main steps: (1) a policy update by a matrix game solver and (2) a (soft/smooth) value update. However, the update is symmetric and simultaneous, so obtaining the same convergence rate seems to be non-trivial and requires some adaptation. In the numerical experiments, the authors verify the theoretical results first (the results essentially match the order) and show that an eager value update can cause the oscillation issue.\n\n\n**Weaknesses**:\n\nThe state-wise average of policies in Markov games is non-trivial, so the last-iterate convergence is very appealing. Although the current proof only seems to be suitable for the average case, the last-iterate convergence property can still be investigated in experiments. Besides, some variants of OFTRL (e.g., OMWU) can achieve last-iterate convergence with specific update rules, the last-iterate convergence property may be obtained with some adaption.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept