Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games
Authors: Shicong Cen
Yuejie Chi
Simon Shaolei Du
Lin Xiao
Venue: ICLR 2023 poster (2023)
Keywords: zero-sum Markov game
entropy regularization
policy optimization
global convergence
multiplicative updates

Abstract: Multi-Agent Reinforcement Learning (MARL)---where multiple agents learn to interact in a shared dynamic environment---permeates across a wide range of critical applications. While there has been substantial progress on understanding the global convergence of policy optimization methods in single-agent RL, designing and analysis of efficient policy optimization algorithms in the MARL setting present significant challenges and new desiderata, which unfortunately, remain highly inadequately addressed by existing theory. In this paper, we focus on the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games, and study equilibrium finding algorithms in both the infinite-horizon discounted setting and the finite-horizon episodic setting. We propose a single-loop policy optimization method with symmetric updates from both agents, where the policy is updated via the entropy-regularized optimistic multiplicative weights update (OMWU) method and the value is updated on a slower timescale. We show that, in the full-information tabular setting, the proposed method achieves a finite-time last-iterate linear convergence to the quantal response equilibrium of the regularized problem, which translates to a sublinear convergence to the Nash equilibrium by controlling the amount of regularization. Our convergence results improve upon the best known iteration complexities, and lead to a better understanding of policy optimization in competitive Markov games.

Published as a conference paper at ICLR 2023
FASTER LAST-ITERATE CONVERGENCE OF POLICY OPTIMIZATION IN ZERO-SUM MARKOV GAMES
Shicong Cen
Yuejie Chi
Carnegie Mellon University shi shicongce andrew. cmu. edu
Carnegie Mellon University yue iech @cmu. edu
Simon S. Du
Lin Xiao Meta Al Research linx fb. com
University of Washington ssduêcs, washington, edu
ABSTRACT
Multi-Agent Reinforcement Learning (MAR))where multiple agents learn interact shared dynamic ical applications. While there has been substantial progress understanding the global convergence of policy optimization methods in singlc-agent RL, design- ing and analysis of efficient policy optimization algorithms in the MARL setting present significant challenges, which unfortunately, remain highly inadequately addressed by existing theory. In this paper, focus the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games, and study equilibrium finding algorithms in both the infinite-horizon discounted ting and the finite-horizon episodic setting. We propose single-loop policy op- timization method with symmetric updates from both agents, where the policy is updated via the entropy-regularizze optimistic multiplicative weights update (OMWU) method and the value updated on slower timescale. We show that, in the full-information tabular setting, the proposed method achieves finite-time last-iterate linear convergence to the quantal response equilibrium of the regular- ized problem, which translates to sublinear last-iterate convergence to the Nash equilibrium by controlling the amount of regularization. Our convergence results improve upon the best known iteration complexities, and lead to better under- standing of policy optimization in competitive Markov games.
across wide range crit-
Keywords: zero-sum Markov game, entropy regularization, policy optimiza- tion, global convergence, multiplicative updates
INTRODUCTION
Policy optimization methods (Williams, 1992; Sutton et al., 2000; Kakade, 2002; Peters and Schaal, 2008; Konda and Tsitsiklis, 2000), which cast sequential decision making as value maximization problems with regards to (parameterized)) policies, have been instrumental in enabling recent suc- cesses of reinforcement learning (RL). See e.g., Schulman al. (2015; 2017); Silver et (2016). Despite its empirical popularity, the theoretical underpinnings of policy optimization methods re- main elusive until very recently. For single-agent RI. problems, a flurry of recent works has made substantial progress on understanding the global convergence of policy optimization methods under the framework of Markov Decision Processes (MDP) (Agarwal et al., 2020; Bhandari and Russo, 2019; Mei et al., 2020; Cen et al., 202 Lan, 2022; Bhandari and Russo, 2020; Zhan et al., 2021; Khodadadian et al., 2021; Xiao, 2022). Despite the nonconcave nature of value maximization, (nat- ural) policy gradient methods are shown achieve global convergence at sublinear rate (Agarwal et al., 2020; Mei et al., 2020) or even a linear rate in the presence of regularization (Mei et al., 2020; Cen al., 2021 a;; Lan, 2022; Zhan al., 2021) when the learning is constant.
Author sorted alphabetically.

---

Published as a conference paper at ICLR 2023
Moving beyond single-agent RL, Multi-Agent Reinforcement Learning (MARL) is the next frontier- wwheee multiple agents learn to interact in a shared dynamic environment -etnanmmttt-eeemttinnge across critical applications such as multi-agent networked systems, autonomous vehicles. roboties, and so on. Designing and analysis of efficient policy optimization algorithms in the MARL. setting present significant challenges and new desiderata, which unfortunately, remain highly inadequately addressed by existing theory.
1.1 POLICY OPTIMIZATION FOR COMPETITIVE RL
In this work, focus on of the most basic settings of competitive multi-agent RI, namely two-player zero-sum Markov games (Shapley, 1953), and study equilibrium finding algorithms in both the infinite-horizon discounted setting and the finite-horizon episodic setting. In particular, our designs gravitate around algorithms that are single-loop, symmetric, with finite-fime last- convergence the Nash Equilibrium (NE) or Quantal Response Equilibrium (QRE) under bounded rationality, two prevalent solution concepts in game theory. These design principles naturally come up as result of pursuing simple yet efficient algorithms: single-loop updates preclude sophisticated interleaving of rounds between agents; symmetric updates ensure no agent will compromise its re- wards in the learning process, which can be otherwise exploited by a faster-updating opponent; in addition, asymmetric updates typically lead one-sided convergence, i.c.. only one of the agents is guaranteed to converge to the minimax equilibrium in a non-asymptotic manner, which is less desir- able; moreover, last-iterate convergence guarantee absolves the need for agents to switch between learning and deployment; last but not least, it is desirable to converge as fast as possible, where the iteration complexities are non-asymptotic with clear dependence on salient problem parameters.
Substantial algorithmic developments have been made for finding equilibria in two-player zero-sum Markov games, where Dynamical Programming (DP) techniques have long been used as funda- mental building block, leading to prototypical iterative schemes such as Value Iteration (VI) (Shap- ley, 1953) and Policy Iteration (PI) (Van Der Wal, 1978: Patek and Bertsekas, 1999). Different from their single-agent counterparts, these methods require solving two-player zero-sum matrix game for every state per iteration. A considerable number of recent works (Zhao et al., 2022; Alacaoglu et al., 2022; Cen et al., 2021b; Chen et al., 202 la) are based on these DP iterations, by plugging in various (gradient-based) solvers two-player zero-sum matrix games. However, these methods are inherently nested-loop, which are less convenient to implement. In addition, Pl-based methods are asymmetric and come with only one-sided convergence guarantees (Patek and Bertsekas, 1999; Zhao et al., 2022; Alacaoglu et al., 2022).
Going beyond nested-loop algorithms, single-loop policy gradient methods have been proposed re- cently for solving two-player zero-sum Markov games. Here, we are interested in finding optimal NE or QRE in terms of the duality gap, i.e. the difference in the value functions when either of the agents deviates from the solution policy.
For the infinitehhorionn discounted setting, Daskalakis et al. (2020) demonstrated that the in- dependent policy gradient method, with direct parameterization and asymmetric learning rates, finds an e-optimal NE within a polynomial number of iterations. Zeng et al. (2022) improved policy gradient method with softmax parameterization
over this rate using an entropy-regularie and asymmetric learning rates. On the other end, Wei et al. (2021b) proposed an optimistic gra- dient descent ascent (OGDA) method (Rakhlin and Sridharan, 2013) with direct parameterization and symmetric learning rates, I which achieves a last-iterate convergence at a rather pessimistic iteration complexity.
For the hirieehorizonn episodic setting, Zhang et al. (2022); Yang and Ma (2022) showed that the weighted average-iteral of the optimistic Follow-The- Shth--egularize--eeaaaa (FTRL) method, when combined with slow critic updates, finds an e-optimal NE in polynomial number of iterations.
A more complete summary of prior results can be found in Table I and Table 2. In brief, while there have been encouraging progresses in developing computationally efficient policy gradient methods
'To be precise, Wei et al. (2021b) proved the average- iterate convergence of the duality gap, as well as the last-iterate convergence of the policy in terms of the Euclidean distance to the set of NEs, where it is possible to translate the latter last- last-iterate convergence to the duality gap (see Appendix. G). The resulting iteration complexity, however, is much worse than that of the average-iterate convergence in terms of the duality gap, with a problem-dependent constant that can scale pessimistically with salient prohlem parameters.
2

---

Published as a conference paper at ICLR 2023
for solving zero-sum Markov games, achieving fast finite-time last-iterate convergence with single- loop and symmetric update rules remains a challenging goal.
1.2 OUR CONTRIBUTIONS
Motivated by the positive role of entropy regularization in enabling faster convergence of policy op- timization in single-agent RL (Cen et al., 2021a; Lan, 2022) and two-player zero-sum games (Cen al., 2021b), we propose a single-loop policy optimization algorithm for two-player zero-sum Markov games in both the infinite-horien horizon and finite-horize settings. The proposed algorithm fol- lows the style of actor-critic (Konda and Tsitsiklis, 2000). with the actor updating the policy via the entropy-regularizee optimistic multiplicative weights update (OMWU) method (Cen et al., 2021b) and the critic updating the value function on a slower timescale. Both agents execute multiplicative and symmetric policy updates, where the learning rates carefully selected to ensure fast last- iterate convergence. In both the infinite-horizon and finite-horizon settings, we prove that the last iterate of the proposed method learns the optimal value function and converges a linear rate the Markov game, which can be further translated into finding
unique QRE of the murrop-regullate the NE by setting the regularization sufficiently small.
For the infinite-horizon discounted setting, the last iterate of our method takes at most
O S
(1 ((1 log
iterations for finding an 6-optimal QRE under entropy regularization, where O(.) hides logarith- mic dependencies. Here, [8| is the size of the state space, 7 is the discount factor, and is the regularization parameter. Moreover, this implies the last-iterate convergence with an iteration
complexity of
S
(1 700
for finding an e-optimal NE.
For the finite-horizon episodic setting, the last iterate of our method takes at most
H ① ( log e
!
iterations for finding e-optimal QRE under entropy regularization, where H is the horizon length. Similarly, this implies the last-iterate convergence with an iteration complexity of
H
for finding an e-optimal NE.
Detailed comparisons between the proposed method and prior arts provided in Table I and Ta- ble 2. To the best of our knowledge, this work presents the first method that simultaneously single-loop, symmetric, and achieves fast finite-time last-iterate convergence in terms of the duality gap in both infinite-horizon and finite-horizon settings. From technical perspective, the infinite- horizon discounted setting is in particular challenging, where ours is the first single-loop algorithm that guarantees an iteration complexity of ((1/e) for last-iterate convergence in terms of the du- ality gap, with clear and improved dependencies on other problem parameters in the meantime. In contrast, several existing works introduce additional
constants (Daskalakis et al., 2020; Wei et al., 202 Zeng et al., 2022) in the iteration complexity, which can scale rather cewemnittiiall--mmmmimmeee even exponentially-wwe problem dimensions (Li et al., 2021).
Our technical developments require novel ingredients that deviate from prior tools such error propagation analysis for Bellman operators (Perolat et al., 2015; Patek and Bertsekas, 1999) from a dynamic programming perspective, well the gradient dominance condition (Daskalakis et al., 2020; Zeng et al., 2022) from a policy optimization perspective. Importantly, at the core of our analysis lies a set of recursive error bounds for value learning, all of which tailored to the non- non-Euclidean OMWU update rules that have not been well studied in the setting of Markov games.
one-step contraction bound for policy learning, together with
3

---

Published as a conference paper at ICLR 2023
Solution
Iteration complexity
Single loop
Last-iterate convergence
Reference
Symmetrie
type
Pl-based Methods
Zhao et al. (2022)
| (1 7))2)
X
X
Alacaoglu et al. (2022)
VI-based Methods
Cen et al. (2021b)
σ (1->Pe)
Chen et al. (2021a)
Daskalakis et (2020)
Polynomial*
e-NB
Zeng et al. (2022)
[1
[T 18/ P!
Wei et al. (2021b)
[s] (1 (1-9))006622
((LA| +18)))?>
This Work
|st
(1-7)%
VI-based Methods
Cen al. (2021b)
(I-T33
1
log?!
x
| log
e-QRE
Zeng et al. (2022)
(1 2)
This Work
δ [s] (I->) log !
Table I: Comparison of policy optimization methods for finding an e-optimal NE or QRE of two-player zero- sum discounted Markov games in terms of the duality gap. Note that implies one-sided convergence, i.c., only one the agents is guaranteed achieve finite-time convergence to the equilibrium. Here, > refers to some problem-dependent constant. For simplicity and a fair comparison, we replace various notions of concentrability coefficient and distribution mismatch coefficient with crude upper bound ||1/p| where p is the initial state distribution.
Solution type
Iteration complexity
Single loop
Last-iterate convergence
Reference
Symmetric
Zhang et al. (2022)
38/5 2076
x
OFTRL
Zhang et al. (2022)
Õ H*
X
modified OFTRL
e-NE
Yang and Ma (2022)
5(
X
OFTRL
This Work
E-RRE
This Work
H2 log L)
Table Comparison of policy optimization methods finding an e-optimal NE or QRE two-player zero- sum episodic Markov games in terms of the duality gap.
1.3 RELATED WORKS
Learning in two-player zero-sum matrix games. Freund and Schapire (1999) showed that the average iterate of Multiplicative Weight Update (MWU) method converges to NE at rate of ((/VT)), which in principle holds for many other no-regret algorithms as well. Daskalakis et al. (2011) deployed the excessive gap technique of Nesterov and improved the convergence rate to (1/T)) which is achieved later by (Rakhlin and Sridharan, 2013) with simple modifi- cation of MWU method, named Optimistic Mirror Descent (OMD) or more commonly, OMWU. Moving beyond average-iterate convergence, Bailey and Piliouras (2018) demonstrated that MWU updates, despite converging in an ergodic manner, diverge from the equilibrium. Daskalakis and Panageas (2018); Wei et al. (2021a) explored the last-iterate convergence guarantee of OMWU,
4

---

Published as a conference paper at ICLR 2023
suming uniqueness of NE. Cen al. (2021b) established linear last-iterate convergence of entropy- regularized OMWU without uniqueness assumption. Sokota et al. (2022) showed that optimistic update is not necessary for achieving linear last-iterate convergence in the presence of regulariza- tion, alheit with a more strict restriction on the step size.
Learning in two-player zero-sum Markov games. In addition to the aforementioned works on policy optimization methods (policy-based methods) for two-player zero-sum Markoy games (cf. Ta- ble I and Table 2), a growing body of works have developed model-based methods (Liu et al., 2021; Zhang al., 2020; Li al., 2022) and value-based methods (Bai and Jin, 2020; Bai al., 2020; Chen et al., 2021b; Jin et al., 2021; Sayin et al., 2021; Xie et al., 2020), with a primary focus on learning NE in sample-efficient manner. Our work, together with prior literatures on policy optimization, focuses instead on learning NE in a computation-efficcent manner assuming full-information.
Entropy regularization in RL and games. Entropy regularization is a popular algorithmic idea in RL (Williams and Peng. 1991) that promotes exploration of the policy. A recent line of works (Mei et al., 2020; Cen et al., a0 Lan, 2022; Zhan et al., 2021) demonstrated that incorporating entropy regularization provably accelerates policy optimization in single-agent MDPs by enabling fast linear convergence. While the positive role of entropy regularization is also verified in various game- theoretic settings, e-g., two-player zero-sum matrix games (Cen et al., 2021b), zero-sum polymatrix games (Leonardos et al., 2021), and potential games (Cen et al., 2022). it remains highly unexplored the interplay between entropy regularization and policy optimization in Markov games with only a few exceptions (Zeng et al., 2022).
1.4 NOTATIONS
We denote the probability simplex over a set A ((A). We use bracket with subscript to index the entries of a vector or matrix, e.g., [x) for a-th element of vector x, or simply æ(a) when it is clear from the context. Given two distributions x, E (A), the Kullback-Leibler (KL) divergence from y to is denoted by (L (1) = EaeA z(a) (aa) - log (oa)) Finally, we denote by ||
the maximum entrywise absolute value of a matrix A, i.e., |l maxij |Aigl--
2 ALGORITHM AND THEORY: THE INFINITE- SETTING
2.1 PROBLEM FORMULATION
Two-player zero-sum discounted Markoy game. A two-player zero-sum discounted Markov game is defined by tuple M (S, p,r,y), with finite state space S, finite action spaces of the two players A and B, reward function : S x A x B + [0, 1J. transition probability kernel P 8 x A B ASS) and discount factor < 7 < 1. The action selection rule of the max player (resp. the min player) is represented by μ S + A(A) (resp. S A(B)), where the probability of selecting action a E A (resp. b E B) in state
S specified by μ(als) (resp. (b)s))) The probability of transitioning from state to a new state s' upon selecting the action pair (a,b) A, given by P(s'|s, a, b).
Value function and Q-function. For a given policy pair u, the state value of is evaluated by the expected discounted sum of rewards with initial state so s:
vs E S:
(P) = E
be), Dr
2'rr(se, ar
(1)
the quantity the max player seeks to maximize while the min player seeks to minimize. Here, the trajectory (80, on, bn, ...... is generated according to oz ~ p(-[st), by ~ v(-10)) and 8:41 ~ P(- oe, be). Similarly, the Q-function Qa.((s, a, b) evaluates the expected discounted cumulative reward with initial state and initial action pair (a, b):
ES Qu a, b) E Σ * (sr, or bi)lso s,ap = a, bo b (2)
5

---

Published as a conference paper at ICLR 2023
For notation simplicity, denote by Qs) RI the matrix 'Q ((a,)a) so that
E (s) pus) (s)v(ss.
Shapley (1953) proved the existence of a policy pair (u",, v²)) that solves the min-max problem max, min, Vua (s) for all E S simultaneously, and that the mini-max value is unique. A set of such optimal policy pair (μ*, ,,") is called the Nash equilibrium (NE) to the Markov game.
Entropy regularized two-player zero-sum Markov game. Entropy regularization is shown to provably accelerate convergence in single-agent RL (Geist et al., 2019; Mei et al., 2020; Cen et al., 2021a) and facilitate the analysis in two-player zero-sum matrix games (Cen al., 2021b) well as Markov games (Cen et al., 2021b; Zeng et al., 2022). The entropy-regularized value function (s) is defined
Vs E S
V.L (8) E
> (r(s,, - llgg((a)ss)) + log log
(3)
where + 2 O is the regularization parameter. Similarly, the regularized Q-function QH is given by a( E S x A
(s) r(s, b) + -PBss-(()....))))) (s))) (4)
It is known that (Cen al., 2021b) there exists unique pair of policy (1i, ug) that solves the min-max entropy-regularrzed problem max, min, (s) or equivalently
max min p(s) (s)v(s) + (H(ss))) TH(((s))
(5)
for all s S, and we call (1t, v²) the quantal response equilibrium (QRE) (McKelvey and Palfrey, 1995) to the entropy-reed reguupp-regulriized Markov game. We denote the associated regularized value function and Q-function by V**(s) (s) V
and (; a, b) = Q" b).
Goal. We seek to find an coppimal QRE or c-QRE (resp. e-optimal NE or (NN) (1, v) which satisfies
(V V.. (s) Se
max sES,p' .
(6)
(resp. max (vu' v (() Vui (5) c) in computationally efficient manner. In truth, the solution concept of e- e-QRE provides an approximation of e-NE with appropriate choice of the regularization parameter т. Basic calculations tell us that
yu' (s') Vu (s) (V.'"(6 V.L. (s)) + (V (() V.L (()) (Vue' (s) V.L. (s))
VV V.. (s) 7(log |A| + log (B8))
1-7
(1-2)e which guarantees that an e/2-QRE is e-NE as long S 2(1og I Hog B87) For technical conve- nience, we assume T < max Aog [B]] throughout the paper.
Additional notation. For notation convenience, we denote by Ç the concatenation of policy pair and v, i.c., <= (). v). The QRE to the regularized problem is denoted by Ç = =(G,, 1z2). We use shorthand notation pls) and v(s) to denote p(-ls) and v(([s). In addition, we write KL (M(() (s))
and KL (v(s) || as KL, (p (²) and KL. (v 1²), and let
(L KL. + By slight abuse of notation, (L (') denotes Banp [KL. for p E A(8).
2.2 SINGLE-LOOP ALGORITHM DESIGN
In this section, we propose a single-loop policy optimization algorithm for finding the QRE of the cntropy-regularizer Markov game, which is generalized from the cntropy-regularing OMWU method (Cen et al., 2021b) for solving raguopy-regularized matrix games, with a careful orchestrat- ing of the policy update and the value update.

---

Published as a conference paper at ICLR 2023
Algorithm 1: Entropy--egullrrzzed OMWU for Discounted Two-player Zero-sum Markov Game
Input: Regularization parameter > 0, learning rate for policy update > 0, learning rate for value update {ox)²=)-
Initialization: Set ( ; (0) and ( uniform policies; and set
2 = 0, v rllo AA| - -lo [3])
for t = 0, 1, do
for all E S do in parallel
When 2 1, update policy pair (s) as:
(als) & (a|s) 1- (x)
(9a)
(bls) (bls)) -epp-=--eppppppna (xp(-n(Q(((s) (x)()))))
Update policy pair (s) as:
(alt)) (a)) exp(nl (x00
(((+))((ls) x (bbs) - exp(-n (
(9b)
Update ((++1((s) and (((+t((s) (s) as
((, = =r(s, a, b) + 71By [v() (()t)((s)
= =(1-a4+1 (s)
+0t+1 (att1/(((t)(s)) ((t()))(((((()(tt(( + +H((l(+)(s))
(10)
Review: entropy-regularizze OMWU for two-player zero-sum matrix games. We briefly view the algorithm design of entropy-regularizze OMWU method for two-player zero-sum matrix game (Cen al., 2021b). The problem of interest can be described
max min J Av + TH()) - -HH(U), (EA(A) (EA(B)
(7)
where A E RIAX B is the payoff matrix of the game. The update rule of entropy-regularized OMWU with learning rate 17 > 0 is defined as follows: Va A. B,
(a) a n (a) exp(r[Ab()))) { (l)(()) (tt- exp(-n/A4 (()))))
(8a)
(a) x (x))))= (((+1)())
(8b)
(x))))==exp(())11 ())))))
We remark that the update rule can be alternatively motivated from the perspective of natural policy gradient (Kakade, 2002; Cen et al., 2021a) or mirror descent (Lan, 2022; Zhan et al., 2021) with opti- mistic updates. In particular, the midpoint (z(++1), (z(++)) serves as a prediction of (p(t+1), (u(++)),x(t))) (((+)) by running step of mirror descent. Cen et al. (2021b) established that the last iterate of entropy- regularized OMWU converges to the QRE of the matrix game (7) at a linear rate (1 - -" as long
as the step size 1) is no larger than min
2 2|
+27 4|
Single-loop algorithm for two-player zero-sum Markov games. In view of the similarity in the problem formulations of (5) and (7), it is tempting to apply the aforementioned method to the Markov game state-wise manner, where the Q-function assumes the role of the payoff matrix. is worth noting, however, that Q-function depends on the policy pair Ç (u, v) and is hence changing concurrently with the update of the policy pair. We take inspiration from Bai et (2020); Wei et al. (2021b) bb) and equip the entropy- regularzeed OMWU method with the following update rule that iteratively approximates the value function in an actor-critic fashion:
(1) b) = r(s, a, b) +
P(-ls.a.)) BBssa(()a..

---

Published as a conference paper at ICLR 2023
where V(++1) is updated convex combination of the previous V and the regularized game value induced by ((+++) as well as the policy pair (((+1) = (a(++1,, al(+1))
(s) -11-a11) (()))
(II)
+ + [ [ (s)
(s)
(H(D
The update of V becomes more conservative with a smaller learning rate at, hence stabilizing the update of policies. However, setting d2 too small slows down the convergence of V to V7. A key novelty- suggesed by our analysis- is the choice of the constant learning rates a := ag = ryr which updates at slower timescale than the policy due to < 1. This is in sharp contrast to the vanishing sequence a 2/(1-7)+1 adopted in Wei al. (2021b), which is essential in their 2/(17))+0
analysis but inevitably leads to a much slower convergence. We summarize the detailed procedure in Algorithm 1. Last but not least, it is worth noting that the proposed method access the reward via "first-order information", i.e., either agent can only update its policy with the marginalized value function ((s)((s) or (s))
((s)T((S u(ss). Update rules of this kind are instrumental in breaking the curse of multi-agents in the sample complexity when adopting sample-based estimates in (10), as we only need to estimate the marginalized Q-function rather than its full form (Li et al., 2022; Chen al., 2021a).
2.3 THEORETICAL GUARANTEES
Below we present our main results concerning the last-iterate convergence of Algorithm I for solving entropy- hunrop--rgularizedd two-player zero-sum Markov games in the infinite-horizon discounted setting. The proof is postponed to Appendix A.
(1->)²
Theorem 1. Setting < r S
32000|3T and a = T/T, it holds for all 2 0 that
( SS|
Σ SES
KL. (G.
1
ΣKL. (1))),
37
Σ (1)
(3)
max
2|5
[s|
SES
(1 - 2) (1
3000
(1 - -11 8
: (12a)
and
max sES. (Vu,000) (8) (s)) 6000
1) (1- (1 7)
5 (1 3
max
(1 - 7)- 17
(12b)
Theorem demonstrates that as long as the learning rate 17 is small enough, the last iterate of Algo- Markov game. Compared with prior analysis focuses the last-iterate convergence
rithm converges at a linear rate for the entropy-regulane literatures investigating on policy optimization, of non-Fuclidean updates the presence of entropy regularization, which appears to be the first of its kind. Several remarks are in order, with detailed comparisons in Table 1.
Linear convergence to the QRE. Theorem demonstrates that the last iterate of Algorithm takes most Ö [1~7)er log 4) iterations to yield e-optimal policy in terms of the KL di- vergence to the QRE max KL, (c# || (())) S c, the entrywise error of the regularized Q-function SES
(V (s) V P (()) S at once. ||Q - Qill s e, as well as the duality gap max sES.
Minimizing the bound over the learning rate 77, the proposed method is guaranteed to find an c-QRE within δ (1-2)* log iterations, which significantly improves upon the one-side con- vergence rate of Zeng et al. (2022).
(L=y)s Last-iterate convergence to e-optimal NE. By setting 7 = 2 [A] Tog]] this immedi- ately leads to provable last-iterate convergence to an e-NE, with an iteration complexity of which again outperforms the convergence rate in Wei et al. (2021b).
8

---

Published as a conference paper at ICLR 2023
Remark 1. The learning rate ni is constrained be inverse proportional (S), which is for the worst case and can be potentially loosened for problems with a small concentration coefficient. We refer interested readers Appendix for details.
ALGORITHM AND THEORY: THE EPISODIC SETTING
Episodic two-player zero-sum Markov game. An episodic two-player zero-sum Markov game
defined by a tuple {S, A, B, H, [hih {ra]-=1) h- 1). with S being a finite state space, .A and B denoting finite action spaces of the two players, and H > O the horizon length. Every step h E [H] + (SS) and reward function ry S A x B Thmm denote the policies of the two players, where the probability of the max player choosing a E A (resp. the min player choosing b E B) at time is specified by / (als) (resp. 1% (a)s))
admits transition probability kernel Pn. : S
[0, 1]. Furthermore, μ { ) and {Pa J
Entropy regularized value functions. The value function and Q-function characterize the ex- pected cumulative reward starting from step h by following the policy pair μs, For conciseness, we only present the definition of regropy- value functions below and remark that the their un-regularized counterparts Vit." and Q% can be obtained by setting T O. We have
H
Viat (s)
=E
(sw are bw awr
T log uh (ancls))) + log un un (bnr)s))))] sh
(s, 0, (s, 6) + E (ls,a))) V (s')
The solution concept of NE and QRE are defined in similar manner by focusing the episodic versions of value functions. We again denote the unique QRE by Ç (14, v;).
Proposed method and convergence guarantee It is straightforward to adapt Algorithm to the episodic setting with minimal modifications, with detailed procedure showcased in Algorithm (cf. Appendix B). The analysis, which substantially deviates from the discounted setting, exploits the structure of finite- linie-horrzoon MDP and time-inhomogee inhomogeneous policies, enabling much larger range of learning rates showed in the following theorem.
Theorem 2. Setting 0 < S
8H and a qp, it holds for all h E [H] and 2 Th == (H - --hTTstaa
1
with Tstart
log H that _ 1r
11th5 - -/111 ( - -1T)²² TT
(13a)
max (VH.Dt0) .ES,N.v
Vall
(s)) s 4(1 - nT)² -- max h,T
182
11
88H (
+ 6rt hht). Gnt (13b)
h,
T n
Theorem 2 implies that the last iterate of Algorithm 2 takes no more than Õ(HT + log !) 6 H 9r log :) iterations for finding an cQRE. Minimizing the bound over the learning rate 1), Algorithm 2 guaranteed to find an e-QRE Ö log iterations, which translates into an iteration complexity of Ō H for finding an e-NE in terms the duality gap, i.c.,
max V2,
((1) (8) -V-V (0 :0 (s)) S by setting + = O( Hllog|A|Hoog [3)
DISCUSSION
This work develops policy optimization methods for zero-sum Markov games that feature single- loop and symmetric updates with provable last-iterate convergence guarantees. Our approach yields better iteration complexities in both infinite-horizon and finite-horizon settings, by adopting entropy regularization and non-Eur -un-Euciidean policy update. Important future directions include investigating whether larger learning rates are possible without knowing problem-dependent information a priori, extending the framework to allow function approximation, and designing sample-efficient imple- mentations of the proposed method.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors would like to thank Gen Li and Zeyuan Allen-Zhu for valuable discussions. Part of this work was completed while S. Cen was an intern Meta AI Research. S. Cen and Y. Chi supported in part by the grants ONR N00014-18-1-2142 and N00014-19-1-2404, ARO W91 INF- 18- 18-1-0303, NSF CCF- 1901199, CCF-2007911, CCF-2106778 and CNS-2148212. S. Cen is also gratefully supported by Wei Shen and Xuehong Zhang Presidential Fellowship, and Nicholas Min- nici Dean's Graduate Fellowship in Electrical and Computer Engineering Carnegie Mellon Uni- versity.
REFERENCES
A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. Optimality and approximation with policy gradient methods in Markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR, 2020.
A. Alacuoglu. L. Viano, N. He, and V. Cevher. A natural actor-critic framework for zero-sum Markov games. In International Conference on Machine Learning, pages 307-366. PMLR, 2022.
Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In Interna- tional Conference on Machine Learning, pages 551-560. PMLR, 2020.
Y. Bai, C. Jin, and Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2111 2020.
J. P. Bailey and G. Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 321-338, 2018.
J. Bhandari and D. Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: (tt::/996.nne 7866, 2019.
Bhandari and D. Russo. A note on the linear convergence of policy gradient methods. arXiv preprint 2rXivv2007. 11100 2020.
S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021a.
Cen, Y. Wei, and Y. Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:27952-27966 279644, 2021b.
S. Cen, F. Chen, and Y. Chi. Independent natural policy gradient methods for potential games: Finite-time global convergence with entropy regularization. In 2022 IEEE 61th Conference on Decision and Control (CDC). IEEE, 2022.
Z. Chen, S. Ma, and Y. Zhou. Sample efficient stochastic policy extragradient algorithm for zero- sum markov game. In International Conference on Learning Representations, 2021a.
Z. Chen, D. Zhou, and Q Gu. Almost optimal algorithms for two-player Markov games with linear function approximation. arXiv preprint 40X.v:2102.07404, 2021b.
C. Daskalakis and I. Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv:/807.04233 2018.
C. Daskalakis, A. Deckelbaum, and A. Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithmms, pages 235-254. SIAM, 2011.
C. Daskalakis, J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 5527-5540, 2020.
Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, (91-2))79--133 1999.
10

---

Published as a conference paper at ICLR 2023
M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized Markov decision processes. In International Conference on Machine Learning, pages 2160-2169, 2019. 2019.
C. Jin, Q. Liu, Y. Wang, and T. Yu. V-leaming simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110. 14555,, 2021.
S. M. Kakade. A natural policy gradient. In Advances in neural information processing systems, pages 1531-1538, 2002.
Khodadadian, P. Jhunjhunwala, M. Varma, and T. Maguluri. On the linear convergence of natural policy gradient algorithm. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 3794-3799. IRHE, 2021.
V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. In Advances in neural information pro- cessing systems, pages 1008-1014. Citeseer, 2000.
G. Lan. Policy mirror descent for reinforcement learning: Linear convergence, sampling com- plexity, and generalized problem classes. Mathematical programming, pages 1-48, 2022.
S. Leonardos, G. Piliouras, and K. Spendlove. Exploration-explootaaton in multi-agent competition: convergence with bounded rationality. Advances in Neural Information Processing Systems, 34: 26318-26331, 2021.
G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Softmax policy gradient methods can take exponential time converge. In Conference on Learning Theory, pages 3107-3110. PMLR, 2021.
G. Li, Y. Chi, Y. Wei, and Y. Chen. Minimax-optimal multi-agent RL in zero-sum Markov games with a generative model. arXiv preprint arXiv:2208, 10458, 2022.
Q Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
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.
S. D. Patek and D. P. Bertsekas. Stochastic shortest path games. SIAM Journal on Control and Optimization, 37(3):804-8)) 824, 1999.
J. Perolat, B. Scherrer, B. Piot, and O. Pietquin. Approximate dynamic programming for two-player zero-sum Markov games. In International Conference on Machine Learning, pages 1321-1322 1329. PMLR. 2015.
J. Peters and S. Schaal. Natural actor-critic. Neurocompuling, 71(7-9):1180-1199 2008
A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. arXiv preprint 1xii:13111.860 2013.
M. Sayin, K. Zhang, D. Leslie, Basar, and A. Ozdaglar. Decentralized Q-learning in zero-sum Markov games. Advances in Neural Information Processing Systems. 34:18320-1833 2021.
Schulman, Levine, Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In Internutional conference machine learning, pages 1889-1897,201
Schulman, Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization 2017.
algorithms. arXiv preprint
L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):009- 1100, 1953.
11

---

in two-player Published as a conference paper at ICLR 2023
D. Silver, A. Huang. C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
S. Sokota, R. D'Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, Mitliagkas, N. Brown, and C. Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero- sum games. arXiv preprint 2tti:220000082225 2022.
R. S. Sutton, D. McAllester, S. Singh, and Mansour. Policy gradient methods for rein- forcement learning with function approximation. In Advances in neural information processing systems, pages 1057-1063, 2000.
J. Van Der Wal. Discounted markov games: Generalized policy iteration method. Journal of Opti- mization Theory and Applications, 25(1):125-133 138, 1978.
C.-Y. Wei, C.-W. Lee, M. Zhang, and Luo. Linear last-iterate convergence in constrained saddle- point optimization. In International Conference on Learning Representations (ICLR), 2021a.
C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent theory, pages 4259-4299 PMLR, 2021b.
Monite-hoorioon competitive markov games. In Conference on learning
R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992.
R. J. Williams and J. Peng. Function optimization using connectionist reinforcement learning algo- rithms. Connection Science, 3(3):241-266) 1991.
L. Xiao, On the convergence rates of policy gradient methods. arXiv preprint arXiv:2201.074433 2022.
Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. Conference on learning theory, pages 3674-3682. PMLR, 2020.
Y. Yang and C. Ma. O(T-1) convergence of zero-sum markov games. arXiv preprint arXiv:2209.1244 12430, 2022.
S. Zeng, T. T. Doan, and J. Romberg. Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 35, 2022.
W. Zhan, S. Cen, B. Huang, Y. Chen, J. D. Lee, and Y. Chi. Policy mirror descent for regular- ized reinforeement learning: A generalized framework with linear convergence, arXiv preprint arXiv:2105.1 1066, 2021.
K. Zhang, S. Kakade, T. Basar, and L. Yang. Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Sys- tems, 33, 2020.
R. Zhang, Q Liu, H. Wang, C. Xiong, N. Li, and Y. Bai. Policy optimization for Markov games: Unified framework and faster convergence. Advances in Neural Information Processing Systems, 35, 2022.
Y. Zhao, Y. Tian, J. Lee, and S. Du. Provably efficient policy optimization for two-player zero- sum markov games. In International Conference on Artificial Intelligence and Statistics, pages 2736-2761. PMLR, 2022.
12

---

sup Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Analysis for the infinite-horizon setting
13
B Analysis for the episodic setting
17
Proof key lemmas for the discounted setting
20
Lemma
C.2 Proof of Lemma
................................
22
C.3 Proof of Lemma
25
C.4 Proof of Lemma 4
27
C,5 Proof of Lemma 5
29
C.6 Proof of Lemma
30
Proof key lemmas for the episodic setting
30
Proof Lemma
D.2 Proof of Lemma 10
................................
32
E Proof of auxiliary lemmas
34
E.1 Proof of Lemma 11
34
E.2 Proof of Lemma 12
35
E.3
Proof of Lemma 13
................................
37
Proof Lemma
................................
37
F.5 Proof of Lemma 16
................................
38
E.6 Proof of Lemma 17
39
F Further discussion regarding approximate algorithms
40
G Further discussion regarding Wei et al. (2021b)
41
A ANALYSIS FOR THE INFINIE-HORIZON SETTING
Definition 1. Given p E A(S) with p(s) > Vs S, concentrabillit coefficient (t) is defined as
p pP2w you ... ... Pacc)) syt))
(t)
sup 200 1
(0 EB 1sist
where Pato yo0 E S| is the state transition matrix induced by a pair of deterministic policy x(0) y())
Pangeee P(s'l s, ( (s), (s)).
Let Cp be the maximum value of (t) over 0:
120
In addition, let T(p) be the set of all possible distribution over S induced by initial distribution and deterministic policy sequences, i.e.
r(p) = U {pP (p2201g00 ... Paso go 10 E EAS,y e EB M [t]
t=0
13

---

Published as a conference paper at ICLR 2023
We make note that Theorem is the direct corollary of following theorems, by setting p to the uniform distribution over S, where Cp admits a trivial upper bounded [S].
(ー-)" 320D0e, and a; = ryT, we have
Theorem 3. With < <ク S
1 KL, (K, 33 E s-p max (Lo(( (1
3000 7) (1 (1 7)r
(s)
4
Definition 2. We define regularized minimax mismatch coefficient by
dgeie (u)
(M)
- max
maxx
max
Here, (I) denotes the optimal policy of the min player when the max player adopts policy μ.:
v²(x) arg min (s)
v
and (v) is defined in a symmetric way. The discounted state visitation distribution dpp is defined as
(s) (8) = (1 7)
E samp
Σ
P(s = s|50)
t==0
Note that this definition parallels that of the (unregularized) minimax mismatch coefficient in (Daskalakis et al., 2020).
(1- and as = T)T, we have
Theorem 4. With 0 < 17 S
32000C,
(VrLoti) (s) - V. v (s)) S 6000/[1/pllz.
1 (1 (1 7n1
max sES
(1 max
(1-7)2 n
4
and
max (V2, R.P
(p) (p)- ( (p))
6000C - 7)- max
1 (1 22 # (1- (1 -1-1--
8
We start with the following lemma. The proof can be found in Appendix C.I. For notational sim-
plicity, set Q(-1) 0, ((-1) =<(0) and am 1. It follows from the update rule (9a) that
(()) (()) 7
Lemma 1. It holds for any step size 0 < S 1/T and t 2 0 that
4n
KLp 11 (((+1))) - (-)77) ((0)) + 1y5 1-7
KLL ((t(5(+
+ 1TTKL, (1(+2) (+)) (1- (1-1-)
21 i KL (((12) || ((++)) + mT) (1))
2n
KL (1](((1) (11)
1 1-7
4x72
12n
27 (t]()(+))(()))))))))))))))))))))
(s)ll + - (s) Q(t-))))))))
(s)
E smpp
+ 1-2
(14)
remains to bound the terms on the right hand side of (14). By a slight abuse of notation, we denote
[|Q(++]) Q711m sup E xei(p) x
[|o(++)(s) 17
and
[[Q(+1)) - xe((p) x~x
110) sup E
[|0(+1) ())
The following two lemmas establish [[] - (r) i=u.... (KL,("0+) -
set of { {((()))(s) (s)lmr with
recursive bounds that relate
and
14

---

Published as a conference paper at ICLR 2023
Lemma 2.
With 0 S min((1 - 7)/180, (1 - /4)8 holds for all t 2 1 that
[|qut))) -
-
1
+
on.1|Q Qut Qut 11(0)
+ 4C, Σ
on ku (
11((-11),,
2
1=1
1=1
(15)
Here, 01 is defined
II 0z).
01, 0i
i=1+1
When 1 = 0, we have Q(0 (p)
2
Proof. The proof can be found in Appendix C.2.
Lemma 3. With 7 - (1 -)2 it holds for all t that
(Q Qillr())
1 1+1 Σ an (10(0) Qullrw) 1
2m 11000 - Q1111111(0))
200,
(16)
2
When 1 = 0, we have [|Q(())) Qi Qillro $ l
Proof. The proof can be found in Appendix C.3.
The following lemma further demystify the complicated recursive bounds showed in Lemma 2 and
Lemma 4. Let Xt be defined
(1-1-2.00) oz))
A1. on II
4
i=/+1
Under the assumption of Lemma 2 and holds for all 2 0 that
A
- -Q(t=)/((1/)))0) +
12n
(1((+1)) - 1r()
(1 (1-
1=0
6250mC 7)3
550n
(L (|(00)
(1 7} A0,
Proof. The proof can be found in Appendix C.4.
We are now ready to prove our main results. Averaging (14) with weight À gives
14111441
KLp(St
(1 ((++1)) - - (C
1=0
+ (1
2n KL (1+1) (((+1)) + 37 -
1-7)
+ (1 (1- 19T
1 1-71 (1"))K
4n
(KL( ((0)
2n
(L. (1,(50113(-11)
KL
1-7
47²
137²
A141,411
E
5n|lQ(+1)(s)) @;(s)) + 1-7
(s)+
(s)
(s) Q
grup
1 r
1=0
12n
Q1) - (3+*)) + (1 (1-7)211Q (1Q (5)
<
7-11111
E
1=0
snpp
15

---

Published as a conference paper at ICLR 2023
31250nc
1-1 (1 (13
KL (5(+1) (1) + 2750g
$
(1 (1- An,t+1
1=0
for all 1 12 O. Rearranging terms, we have
ac+1 (CF 11 (((t1)) + +(11 (1-1-~ 2n
(s) (+++
KL
+ 3n E
smp
(1141 10 (1 (1)
Σ
141184(11110 (1-17- 1-7 (1 71-7)3/
4n 31250mC2
2n
KL(
A142,+1 7-
1=0
2750n
2750m
< (1 7)2
Ao,-+1 + (1-171 (11-))) KLp (57 (1) S (1 (1-7)² +111 A0,e+I-
{1-)} and ag = 1,,, we have A1,411 - (1 - ny A441.0+11111 2 0 (c.f. (40)), and 32000C,"
With < 75
A141,041( (1 1-
15p - 41 3125015.)
21
(1 (1-1}²
X142,+11 1-7
-
1+1
-1-1 as) (11 1-7
1 1
mT7) ( (1 117
4n 31250nC
2n
=
4
4
1 1-7
(1 -1 (1-))3]
1
2 0.
5=++3
follows that
KL (L + (11 1111)1111111111111 1-71
2n
KL (Lp(
+ 3n
E
emp
(17)
2750
1)
(1- T)1T
411
3000
(1 (1- -) (1) 4+1
< (1 (1-
4
(1
2
4
This proves the bound of KL, |1 (((+1)) and 37 E [||Q(++)((s) - (s)) in Theorem 3. grip
Note that the bound holds trivially for KLp(St ll ((0) and 3n E
(s) [x])) It re-
smp
mains to bound KL || 1))+
Lemma S. With 1 (1 7)/8, we have
1 KL, (c: ((+ + ( (|()
2n KL. KLx (1)()) + 2m (s) (s(s)
s (1 (L-
+ 1-
Proof. See Appendix C.5.
Combining the above Lemma with (17) gives
1 KL, 11: + K || (())
2
I (1 - mT) (11-nr((L((() (KLp(5 5(0) + (1- 1 1- KLL (L (1700) + 3n E
2n
(g))0(()))())))))))
srup
3000
(1- (1 (1- H+1
< (1 71-
We are now ready to bound the duality gap. Before proceeding, we introduce the following two lemmas:
16

---

max Published as a conference paper at ICLR 2023
Lemma 6. It holds for any policy pair v.v that
2Ch.
max a'p
(V) - V.Lv (0)) - 1 -
E smup
max [ Nn'
- 1)
(18)
and
(V) Viue Vs)e((s) - 1-
2/ll/e
(1-00:111)))--0-:-...) (19)
max #ES w
IE smp
max LK'
Proof. Note that (19) is slight generalization of (Wei et al., 2021b, Lemma 32). The proof can be found in Appendix C.6.
n
Lemma 7 ((Cen et al., 2021b, Lemma 4)). It holds for all & E S and policy pair p. v that
4
(f.(2t. 1.(Qi,,,)/)) - (1 7RT KL (1)) + +KLL,
Putting all pieces together, we arrive at
max (V= (p) - Vialt (D)) - 7
2ct
4
KL 15 ((+)1)) + TKL (7 || ((=+))
(1 - 2)2
2Ct p.t
- 7)) 7) ( kL
8
1
KLL (57 (5:11 (1(2)) - nTKL
( (2(++2) (1(7))
max
7
(1 7) max {
6000C p.7
8
1 } (1 (1
4 -
(1 - 7)2 1
(V
(s) - v(s)) as it follows virtually the same argu-
We omit the proof for ma
ment.
B ANALYSIS FOR THE EPISODIC SETTING
Throughout the analysis, we restrict our choice of value update step size to a2 1/.. We start with the following lemma which parallels Lemma 11 in the episodic Markov game setting:
Lemma 8. With 0 < 7 $ 1/T, it holds for all s E S, h E [H] and t 2 0 that
max {11m
(t+ 1) (s) - Ph (++1)
(s) (s) ||/ ((++)()) (s) Un (2+1) (s)lli s 2n
(22)
In addition, we have
max log c (s) || log th (s) log Ch.- (s)l S 2H 7
(23)
Lemma 9. With 0 n 1. it holds all 0 S t S t2 h E [H] and E S that
KL, ,r || c/2² (12)) (1 - 4n
|| ((!aa
$ (1 1/)) 12- (LL, || (( + (1 - 4n HnH (11) 1))
+ 4n
(1 -  777) -
11 ()) (s) - (s)
1=t
Proof. See Appendix D.1.
Lemma 10. With 0 < 17 S 8H it holds for all 0 < S to 2 2 h < H and E S that
(fta)) (s, a, b) 1 (8)
< 2(1 - m)) 12-1 H + 10mT
E s P -=t--1
Σ (1- (1--7))----110)) (s)
+ r(1 12-1
E
(KLs(Sh,) (11)-11) + (1 AnH)KL,(Sh (c((---) 11 [1]]
s'm P
17

---

Published as a conference paper at ICLR 2023
Algorithm 2: Entropy--reuularized OMWU for Episodic Two-player Zero-sum Markov Game
Input: Regularization parameter 5 > 0, learning rate for policy update > 0, learning rate for value update {ax)²=-
Initialization: Set ( ; (0) and (l uniform policies; set
Q = 0, v Flog AA| - log [3])
for t = 0, 1, ... do for all h [H). E S do in parallel
When 2 1, update policy pair 5% (s)
( as:
10 (als)
[t-1) (als) exp(n1 (s)) (s)la)
Hb
(20a)
U (bls) x v
1) (b|s) - nlp(-n11h 10 (s) a (s)lb)
Update policy pair z((+1)
(s) as:
Lh.
a++ (als) (1) (als) exp(rl ( (s)la)
P
(20b)
(b|s) x U (bls) exp(- - 11 (s) Ph (s)
Update Q (1+1) (s)
(s) and ((++1)
h (s) (()+t)(s)) as
(t-1) (s,
(s, a, b) + P [vif(((0)
v ((+t)) (s)
= (1 (1- a2+11) =(1-a4+1VV; (s)
+as+1 1/
(s) Q (++1) (s)p (s)+ +H((( - -TH(Dttt)
(s))
(21)
Proof. See Appendix D.2.
We prove Theorem 2 by induction. By definition, have
QQn,r Q ll = 11 < 1,
and || - 1| the statement holds for some h, invoke Lemma 10 with t Th + 1 and t 2 Th-1, which yields
IH rH Il.o 0 for fort> 0. So (13a) holds trivially for h H. When
| Qi-1,71
< 2(1 - 117)²
+ 10
E
Σ - -1- (s)
p(
1=Th
+(11 - Tw-1
(Sh (Th)) + 4nl1)
(Ta) ((( (c(
[-1
< 21 - 117)² To- -1 11 H + 10mT
E p(.a.aa)...))
Σ
(1 - 1- 1-2 -1
1=Th
7(1 - -177²* -Ta--
KL, (
Ch (Thh)
+ (1 4nH1)KL, (c.Ta) (((t))
s' (..0)))
$ -
(11-77)-77h-11 -----
Timt 10H 10 -
where the last step results from
7 KLL (Ch,r 5 ((Th)) + - -nnH)KLL (TTh)
|| (((Ta)
18

---

Published as a conference paper at ICLR 2023
<T (s) - log u
(Th) (s) + Vlog - log v
(Th) (s) (h)
+ |log 1h
(Tw) (s) (T)((s)
log P/
(Th) (s)
(s) am + |log un (Th) (s) - log / (Th) (8) (8)
S8H.
Therefore, with Tsttrt =
1 177 log H| we can guarantee that
_| 1h- S 10(1 - qπ) - Th- (1 -7)
Tame 77o) H + mpt h++1
I (1 (1- 17) - Th- 11
This completes the proof for (13a). Regarding (13b), we start by the following lemmas, which are simply Lemma and Lemma 7 applied to the episodic setting:
Lemma 5A. With
8H. have
KL. (th,r |1 ( + ryTKLs (C) (1(+1) || (h.7)
$ (1 - TT) (Sh.r 1 + +nHHKLs (12h2)) + 2n (s) (s)
Lemma 7A. It holds for all h [H], E S and policy pair μ. that
4H²
max (fo(Qi,t ph: vn) - fo( (h, v/h) S T Ne,
KLo (h) + 7KL, (h.T)
Combining Lemma 9 with Lemma 5A and Lemma 7A, we conclude that for S t S t2- 1,
max (fo(Qh. Nh. 2 f.(Qt. (4 H.N
(t2) ,,)),,)),,,,,))))) .w))
4
KL.(Gi, 11 (1( + rKL (2! (
8H2
KL. ( || (((aa) + nTTLLs (Z((2) (1
S &max
2
8H² 1
$ mmxx
(1 KKL 1/5h (112-11 + 2nH (c (12-1) 11 ((13-11) + 20|1@/
(
17
<max
8H² 1
((1
(1-17))²
--- (KL. 5/a (1:)) + (1 4nH)K,, 11 (1)
17
t2 Σ
+ 6z)
(1- 11 2h. (s)l
1=h
It is straightforward to verify that the above inequality holds for 0 I t, I tz by omitting the third step. Substitution of (13a) into the above inequality yields
max (Ja(Qh.T)Pa) Ph, h
fa( .
8
(1 ) Tr KLL (Shrr ch ((Th) + (1 (1nnH))Ls((." (TW) 1| ((fl))
S max
+ 6n Σ (1 )
1 (1 1n c 1
T=
8H 8H² 1 ( + 6tj! "nn1"
< (1 177) Th max
(24)
We prove the following results instead, where (13b) is direct conclusion of (25) by summing the two inequalities.
(V1,000) (s) Vii S 2(1 - max
8H 1
88 r
61t Hnnt--++)
max SES,
7
(25)
max +E
(V) - 1/ h.r (s)
< 2(1 17)) max
8H² 1
88
+ 6ez -411 61
19

---

Published as a conference paper at ICLR 2023
We prove by induction. Note that when h H. we have (s) fe(rH, (iTH,,H.P0 vH) f. ((rr),,,n)) vH) and the claim holds by invoking (24). When the claim holds for some 2 S
h H, we have
Vu 1, (s) - (5)
1 ( -H())
- (8) h (0- (1. TH
(/- (U
-.( Mh- h- 1, 1, 1 + 14- 14- (s) T (Qu. (5) Qh- (5)
& f.(0 M4-
(1)
fa(Q
1,+) + max
(urriio (s') - Viri(('')
h-1
s'ES 1,t
max 1h-111
(1(Q 1h 1/
[s QQ
(1) - P v/-1))
max
s'EB hir (s') -V (6))
$ $( - (m)))- Th-1 max
88 1
8H
6rt hb22 2x+2)
1
882 1
8H + 6rlt At1]
+ +2(1 - -77)" Th max
$ 2 nr)² T--1 max {
882
}
8H + 6et -
Taking maximum over μ verifies the claim for 1, thereby finishing the proof. The bound for be established by following similar argument and is therefore
VV (s) v/(")()))
((s)
max .ES., omitted.
C PROOF OF KEY LEMMAS FOR THE DISCOUNTED SETTING
C.1 PROOF OF LEMMA
Before proceeding, we shall introduce the following lemma that quantifies the distance between two consecutive updates, whose proof can be found in Appendix E.
Lemma 11. For 0 < S 1/T, it holds for all s E S and t 2 0 that
2m
max (1) - n (et) (+))
[[)(+)(())))+) w(t (0))))))l
S
1-
and that
max (1 (3)] || (s)
6n
<
1
For notational simplicity, we use y to denote equivalence up global shift for two vectors xr y:
r x= --
for some constant e R. Taking logarithm on the both sides of the update rule (9a), we get
(+)) (1 '/7) log (s) 1 ( log (tg((++)(s (1 11-mmy mr) log (s) 1 - ((((tt)))))
(26)
(s)
On the other hand, it holds for the optimal policies (ut, u²) that
np log (s) 1 (s) T/T (o) - (x)
(27)
Subtracting (27) from (26) and taking inner product with (()+) (s) gives
20

---

Published as a conference paper at ICLR 2023
- - (:
(11. (((00))))
- -n(bltt)
- -1000)00-00000000000000000000000 -x (;)) (c()))
= -0 (
(1)(s,, (Q((t) - -(((()) (((+))ss))
s ()) (7)+)
(28)
We rewrite the LHS as
(log (() (1 - m7) log -
(+))
= -lolgg ((tt)) (s) - (1 - 1T) log (s) yp log (b), (+))
+ (log (log((+)))) (s) (1 m7) log (s) 7p log loggllggg00 (s). (s)))ss))
+ +log S (++1) (s) - log ((t+
(s+)
-11 11) (5) log < <0 (
= KL. (1 - (1 - 177 KL, || (())
+ (1 - nT) (3((+1) || ((0)= ([(+t)1(((
+ nTKL, (((0=1) ((]
+ KL. KL (1+1) || (1(+1)) (log< (()+1) (s)
log < (1++)(()) (s), - (()+ -1))
+(1 -1 (T) (7(0) (0) - (1 - (7) (s) log (00) (s), 2 (s) - (s))
Rearranging terms, we have
KL. 11 ((())) - (L. |1 (()) + (1 - KL. (((00
TTL,, (c((+1) || (+) + KL, (1+) || (((+1))++ + (1
7T) (5(0) ())(0)
- (log (( (s) - log c (1+1) (s), (s), (s) - (s))
-1- (s) - log (()) (s), (s) (s)
S 2n (() (s)
bound (log((++ log ç ((++)) (())))))))) - (s)
It (log (s) log (s), ((++))))) - (s)). Note that
remains
to
and
(1og (s) log (1+) (s), (s) - (s)
= =n(00) (s)
(s) - q
- (s) Q (1t (s) (s) p (s)I
(s) (s), (1)))
(29)
We bound (s) - (1(4)) (8) as
(s) (s) - (((+1) (8) (8)
< | 2 (12111000)) p((+1) (s)],, + (s) (+)
(6) - ((++ + (())()()) - (s))
(0) (s)],
Plugging the above inequality into (29) and invoking Young's 's inequality yields
(log Fi (s)) - log (++)))ss....)).) (s), (()+)((s))))))) (s))
S 1 1-7 (1b(t-)16)- - ->)(l + (1) - (s))))
21

---

Published as a conference paper at ICLR 2023
+ (s) - (()+!)(s) 20 (s) (1) p((+
S 21 KL, || dl + 1-9 KLs (ullttit) (1lt+1) (| + 1
21
20²² (1) (s) oo'
1-7
where the last step results from Pinsker's 's inequality and Lemma 11. Similarly, we have
(log 1l(+t)(s)) (s) - log (()+t))ss,, (s), (s) (s))
27 KL, (plet1)) || (0))) + 27 KL. (wlet2) || El(t1) +
2n²² 1 (1) (s)l
1-7
Combining the above two inequalities gives
- (log ((gg((+)(()))) (s) - log c (1+1) (s). (s) (s))
2n KL. (L.(( || ) + 1-7
2n KL. (c(0t1) || (((tt + 1 (s) - (s)+
4n²²
< 1-
By a similar argument, when 1 2 1:
(log< (s) - log ( (8), g(( (s) - (s))
=10( ((Q(((() (5) n (s) - ()) p(c-1) (s), (s)) - (s))
Q (s)b(t (s), (s+t)
- (s)
2m KL. (1)) || ((()) + I 7-
2m
KL. (c (2(++1) (2(00
+ +n(latttt)
(s) - (p) + (b(t+) (s) - at (3)l)((() (s)
2m KL. (L)(
(1]() 27
KL. (L.
5
7
12n2
1-7 |Qth (('1))
Note that the above inequality trivially holds for 1 O, since log (1)) = llog ((0)(()))))
Putting pieces together, we conclude for that
KL. (G |1 ((++))) - (1 - (G + (1 (1- 1/p
1-7) --- -
4n 1
KL. (<(0tt) || (()))
+ + || (1) + (1- (1-1-) 1-1 KL. (L(()))))) ((+1)) + (1 - nT> (1
2n 2n KL. (2t) (1)
1-7
< 22)1( - ()) + +1 -
4n7 (s)
(s) + ' "1-9
12n²²
-s)))))>))))
Averaging over the distribution completes the proof.
C.2 PROOF OF LEMMA 2
Proof. By definition of Q, it holds for t 2 that
IQi+t)) (s, a. b)- - ( (s, a, b) s ((. [1 - v ((0-0(s))]
(30)
We denote by [a(Q. u., v) the one-step enaesggiiinttopp-rrrruuaaiae game value at state 8, i.e.,
fa n,, v) pus) ((s)(()) (())))(())((()+++++))))))))))))) (H(u(s)) HH(((s)).
We further simplify the notation by introducing
( = (1() (,(0),,00
22

---

Published as a conference paper at ICLR 2023
By recursively applying the update rule (s) = (1- a=))((-))(s) + we get
+ (s) = an o v
an (Q" )00) = Σ fe
1=1
1=0
Since ag = 11, it follows that
O1 = 000 =1
1=0
So we have
(s) ((()))
ail (t) - (s)
0111-1 a1,t-11 |1(0 - -
04
(31)
1-1
S 04
01,1-1
-
1=0
/=
The next lemma enables us to upper bound KL, (5(++1) || (()) (as well as their (t -t-11 1)-th iteration counter parts). The proof is postponed
|
with
I|Q(+1)(s) - (0) Il and
to Appendix E.2.
Lemma 12. For any & 2 0, S - 7)/180, we have
[((+1) - 1100 S (s))))(s) - (1)
+ (,,
3 +
KL, (1(0t)))1 ((0)
17
1-
12n
(s)
()-
2
KL, ((()) (t)))).
+ 1-7
+ '--7
Plugging the above lemma into (31),
(s)
(s)
1-1
Σ
+ (a+
I "1-)) KL. - ((aa)
4
24
01,6-
-
/=1
12n (s) Qu (s)l
2
KL. (55) [|
+ a4
+ '-
1-7
(1 11 i 12m |10(++)(s) ) (s)
+ [(-
- KL. ((5t
6
+
1-
-- (1) - Qa- (u)1)
12i1
+ +I- KL. (5 ((
011-1
Σ aj+1
(1+
12n
|1Q [1Q(+2)(()) Qu) + (=+ -- KL. KL. (5022) (10t2)
+ 6
01,1-1
i
1=0
1=0
1-2
12n
[|Q((+((s)- - (s) II. + I KL. (L || {0n]
+ 01
0141.-1
1-9
1-0
where the last step is due to az I aj for all j < t. To continue, by definition of a we have
0,0/+10011 S 1441--1(1 at) = a1+1, for 0 < 1 < t, and that
[-1
aj+1 01,1-1 aj+1 Σ
II
a1)
-
i=|+
23

---

Published as a conference paper at ICLR 2023
t-1
= -041
(1 - 03)
1=j+1
S 80j+
II (1 03) 00+11
i=1+2
Plugging into the inequality above gives
(s)
(s))
1-1
(1
) 1
12m
+ +( +
6 KL: KL. (|
-
|=0
12n 1-7
2
KL. (5.((5 (1 (
01+1,1
+ 1-7
(1+1-1
24n (s) (s)
+ -
0141,
Plugging the above inequality into (30) leads to
(Q
(s, b)bl
1-1
(1+1 1 1-1
24n
+ (5411)111))))000)
ST
E
11
1=0
When 1)
(1-2)²
we have 7(1 2 S 2 and hence that
48y
(s,
b) (s,aa, b)
a0t1. (5)) + - ( ( }
E
d(m.(-(b.a.))
2
1=0
Let (++1) E AS and y(t++1)) E B be defined as
(c+!)) (s)) (s(
( (s,
arg max (a
follows that VX E l'(p), we have XPrct- (t+n E l'(p) and hence
E [|Q(tt) (s) 0 (1)1
xxx
[1Qttt) - Q (s.a
(s) (=)(+))(())
1+1
(s) (20)) + KLL ||
<
E
a1+1.
s'rxp s'wxP,(0-, (((4))
1=0
1+9 7
1-1
a1+1.
-
-
4. 111x 1
X
KL (1,(5(+1)) (..)
1 7
[|QU+1())) (5)(( + 4Cp KLL ((tt))) [(00
a1+1,
(32)
2
1m0
Taking supremum over x E l(p)) completes the proof.
When / = O. we have (s) (*)) = =)) 22
24

---

Published as a conference paper at ICLR 2023
C.3
PROOF OF LEMMA 3
Note that if suffices to show for 0, S, (a,b) A B:
(s,
(x,
1+7
E
Σ a1t
- + I 1-7 -
2n
((-1)))))
[|
+ 200.t
2
s's.(s))
(33)
The remaining step follows a similar argument as (32) and is therefore omitted.
For 2 0, we have
((tta - (8,
= () 7 P(-laa))
Σ 2 fz)
(34)
We start by decomposing n! 8 as
p(t) f fa( n1(1) x(t)) 1G.
(Ia(0()), ,a((), b(0)) 11( ,700 v21) + 1.(Q0,."))
1o(27: 17, 17)
(falQ()), D()) fa((()) , .,)) + fe(07, (17) fo(27.14
+ (1) - (+) S f1(00) 1 2(0) - fa((()) ,42) -1)))
(2(s)
We bound the first two terms with the following lemma: Lemma 13. It holds for all t 2 0, E S and v(s) E A(B) that
(1 (0),, d(n) f((")) 1:0) ,))
= (s) vvs), (1) T 2110 (s)) -
+HH(2((s))
s 2m (s) Q(-11) (s) 2 +
(s))
_ (KL. (1 + KL. (1(t-11 || (((()))))
2
1-9
(1 - 1-
4n KLs (w(00) [100) -
1| -- (b(0) (((-11)
"
1 - t KL. (v (111)
1 KL, KL. (1)12(1t))
+
"
Proof. See Appendix E.3.
Applying Lemma 13 with v(s) = (s) gives
f(0 - fz < (1( (+) + 1-7
2n
(2) Q (s)
1 - TT KL, (1: (t-1))) - -KLL
(v, (0+1l111) (1)
n
17
(35)
1 (1
An
KL, (v(t) |(0)) 1- 17 KL, (E(() || (1--1))
7)
1-7
2
(KL. || |لل--)) + KL,
(1(t-1) (L,(n
(((-1)))
+
1 -
25

---

Published as a conference paper at ICLR 2023
By similar argument, we can derive
1 - ن:4 s 110 - Q:(0) + $1-9 +1 (1) (0)
2n
+ 1 at KLo (1, || [1 - 1 [KLs 1l 11))
(36)
- (1
4n 1L, || [1=100) -1-11- KL, (1((0) || (1)))
"
1 1-9
17
2
+ KLS (1)
|| 1
1 y
Computing (35) + - (36) gives
(1 - 1 1f
2
4
s <1+ 1 -- [|10000 (s) - Q1(()] ~ + I , - (3)]
2n
4
1
1- m
KL. (v 1| -1e- () +
1 1- - KL, [1= (111:1111111 [ - 1 KL. (0, (1(1())))))))))))))))
+ 1- 7
KK (1e [1(()))
+
7
4
4
2
(L((1((11) [1
+ 1 7 KL. KL. (x(l-1) || [((-
+
1 ?
4
1 (1
4n
[ 7 KL, KL. (1(²) || (1))) + KL. (1(1) [[](
1
1-9
+
2
1-nr np.
- 7 JKL ( -(ع- + ( --7
||
2
1-y
1- n,T
JKL (z(0) |
7-7
7
4
4
"
(37)
With 0 < 7 (1 - /)6/16, we have ( (12
1 1-mz 122) S 0,
(
2
1-1
1-m ) 1 0, and
1-
4
1
An 1-7
2 1
1- 4
2
7
1-
1
1- n/
To proceed, we introduce a shorthand notation
1 ()) = KL. (LL(VV (1))
1 -
7
KL, KL, (1; 11 [10))]]
4
2
(u(t) || | + KL, (v()) [[t1)]]
(1 ( 7)(1 - mTT)
We can then write (37) as
(1 - 1 - 7 1 - f2) $ (1 + 1 7, 1 ) (ss - (=))) + "1 (l)) - (((-1(())
2n
4
4
+ (1- (11-7))((-116
(s).
(38)
Note that when = 0, we have
[10) - 5 = T log |A| - T log |B| - (x) (6) - -H)( + ++((()))))))
= max min f. (0) p2 max min f. (Q)
(Q)
M(s) m(s)
m(s) u(s)
< | (s) Q7 20.
(39)
Substitution of (38) and (39) into (34) gives
(1tt)(ss, as,
Σ an - -5)
5 <TBogrP(aaa)) [000:1Q000 (6') - [oo)
26

---

Published as a conference paper at ICLR 2023
1+ (1-7)/4
Σ ane
- -
+ 1 "1-> 110 (s)))
2n
+ 7 1 1 (1 (1-110 (1-7)/4 P(r,a)))
7
(1 - 177) Σ (.. (an
+ 1 (1 7)/4 P(s.o,)))))
E
Note that
(1 177)
On G (8) Σ G
t-1
- at + at, (s')
S (s)) S 200, 17 < 200,0
where the second step is due to
(1 - n-nr)aat - 01 = ((1- ((1-17)a141 - -a(11 - -441))
II aj
j=|+2
$ ((1 ((1-n))aa41 - a1+1 + a1a141)
II 0j /=I+2
a041(a0 m75 II 0j 5.
(40)
j=|+2
So we conclude that
Q(++!) (s.a,b) a, b) (7,
$ y 1+ (17)//
Σ an. - + 27
1 1- 11000(0)) QU (s)
E
1- (1 7)/4 of P(s.ab))
+ 200gtt
1 1+7 E s'=P(s,a.b)
Σ and (6))
(100 +1-11Q0((>)) (6)1) [
2n
+ +1 1-
2
+ 220,.t
The other side of (33) can be obtained by computing 1-y. (35) (36) and following similar argument, and is therefore omitted.
For t = 0, we have (s,))s b) (2(s, S yaaxees 15 f31 - 2.
C.4
PROOF OF LEMMA 4
For t > 1, let
12n?
Uy = Q]](sss))))))))))))))))))<)))] (10(s))
+ (1 (1-7)² (Q) Qs)-
follows that
2y1
24n2
#1 1-9 y
S 1.
(1 - 333
27

---

Published as a conference paper at ICLR 2023
When t 2 1, invoking Lemma 2 and Lemma 3 gives
1e+1 I (1 1 7
(1--23)
a1e [1ll@0) - -illrr0) + (1-
2n²² + (1 - 7)2 |1000 Q"1 [r()
12n²²
C
04 KL, (2" + 200 + ao. 00 (0) (ml)
+ (1 7)²
1=1
< (1 3
48
Σ
on, (L + 4n
a1.00 +
0n,
(1 - 7)2 1=1
7
1=1
(41)
Let
B1 on II
(1-
1 1-1-2 .i)
3
i-1+
It follows that for t 2 0,
a1,++14
(1 ax+1)
2 + #++1
< (1
1
1-7
48mCpp
Σ
or kl. (c ((]--
4n
a141
an + 06+11 (1
+
a0+1100.0
3
7)2
1 --9
1=1
[+1
1-7
7
48rC,
+ 4n
at 01,11.111+ +
B1+1,++1
a
3
(1
(1-77
1=2
1=1
1=1
S BLe4111 +
C8
at, 11, KLp (5") (|
+
4n
00,13,1100-11
(1 7)
1
1=1 E=1
< (1 (1- 1=1
200mC
Σ BL, (I
(()-))
+ 1 B,,
187
(42)
where the last step is due to the following lemma. Similar lemma has appeared in prior works (see ie., (Wei et al., 2021b, Lemma 36)). Our version features a simpler proof, which is postponed to Appendix F.4.
Lemma 14. Let two sequences {ō.), } be defined as 6, = Cj and
- C204,
where the constants ct, 02 satisfiy 0 < c1 C2
For I S 1, let dr, a1 I2 8, and
20r"
Ei, = ou I1 &s. We have
Σ ELodsiie S (1
2 61.-
C2 c
Substitution of (42) into (41) gives
04-1 1
(1-
1 1-7
a
4811 (1 (1-
Σ
0n
(L( (|]--
+ '1-7
4n
1=1
200nC,
18n
48nCC
4n 0..0
< (1 7)3 1=1
(L
|| (((-))))
1- Bo,t +
a1.
|| ((-
+
(1 7)
1-1 7
1=1
C50mC,
Σ ((0
'
22n
< (1 7)² 1=1
+ 1 Bo.
28

---

Published as a conference paper at ICLR 2023
for f.rt 2 1. It is straightforward to verify that the above inequality holds for = 0 as well.
So conclude that
A-1,--10441
1411,-17441
250mCp
B1, (1("-11) (1
+ 22n
A+111+1
1 30.1
(1 77)
1=0
250mGC 9
1
2217
31, S
1 (1] + 1 7
30,
7)
1=1 i=1
6250nC p
550m
KL("
+ (1 7)2 20,4+1
7)3
6250nC (1-
550m
A411,41KL (1))
+ (1 7)² 00,411
where the penultimate step invokes Lemma 14.
C.5
PROOF OF LEMMA 5
Taking logarithm on the both sides of the update rule (9b), we get
{ log (ott)) (s) - (1 log 10 (s)
= (s)
(43)
log (og)(+))(s) (1 m7) log (' _ - (s) (s) (s)
Subtracting (27) from (43) and taking inner product with (s)+ (s) gives
log (log (()+)(()) - - (o (0+))))) ())))
- (s) - +1 (((s))
- +166""00000000000000000000=00)11 -2)
I $1
+, 2n (KLL,( (| KL, (((+))) [| (0) + KL. (1(()))))) 2n (5) -
(1 - (s))) ()))) (;())
1 1-
LHS can be written as
(ttg)(++))s) - (1- log (s) by log (s)) (()
-log (logz(tti)) 11++ (s) - (1 n7) log (1) (s) yp log (8), (s))
+ (log 5 (() - (1 - 7r) log (s) - Lpt log (s), (s),5(tt))) (s)
(L (1 ITT) (1)
+1- (1+1+1) (1(( + nLKL, (2(++)) (1)).
So we conclude that
(1 (1-1 1 1-
4n KL. || ((++)) - (1 - Kc
29

---

Published as a conference paper at ICLR 2023
+ (1 (1-1 177
21 _ KL
( (5 || (() + mTLL, (1())
1 1-
2n KL. (L.(( 11 + 2n 27/ (1)) (1)
$ 1-?
With < 5
1-y
8 we have
1
KLL (KL,(( + TTTKL (1
2n
+ 1-7 KLo (5)) (1(00) + 2n|l(( -s)
C.6 PROOF OF LEMMA
We have
(s) (s) =
- ( + +T(((((s)
-H((s)
QF) ([(00()))))(0+(00)) -1 ut)
Y
E
as)
b-p()(s);
Applying the inequality recursively and averaging over p. we arrive
VI - ( = 1-7
E I (Q, v) - fe (Q7 MG, 11,,
(44)
slndp.
which is the well-known performance difference lemma applied to the setting of Markov games. follows that
vii (0) - (p) 1-7
E s'mdte (or)ar Co).e
E
fe
d' di (o)
E (rr
max LA'N"'
-
(45)
of s'nd
Ct
p.t
E
max P'
smp
A similar argument gives V: (()) (p)
C..-
maxx - v.))
E
1-7 smpp
Summing the two inequalities proves (18). Alternatively, we continue from (45) and show that 1
Vel(W)P(()) (s)
max (Fr(Q). for (Qr....))) [
S 1-7 s' (it)
||//lloo
(f.(Qt. - u.))
< 1 1->
max L
amp
Summing the inequality with the one for V,+ Vaue(()) (s) and taking maximum over S completes the proof for (19).
D PROOF OF KEY LEMMAS FOR THE EPISODIC SETTING
D. PROOF OF LEMMA 9
Following the similar argument of arriving (28), we have
(log ch (s)+)((s) (1 mp)) log c/ (s) Tpr log Gh (s), Sh
(((+)(())
-Gh -h)r(s))
30

---

Published as a conference paper at ICLR 2023
<
1 -
We rewrite LHS
(log Sh
(1+1) (s) - (1 - T7T) log Ste
(1) (s) - lo (5), Sh 211+1) (s) (s) - (s))
-logg Sh (1+1) (s) (1 - 1/r) log ch (8) - 1/ log Sh.r (8), Sh. (8))
+ (log 7(e+ 11 (s) - (1 - 7- log ch (0) (s) Tyr log Sh (s), z(1+ (s))
+ (log Sh
(1+1) (s) - log 5h 2((+1) (s), Sn (()) (s))
KL. (/ (((t1))) (1 - 177 KLs (-h,r || (1²))
(1 ( KL. (2tttt) (1)))))) + yp KLs (Sh
(h,r)
+ KL. (++1) || S/ ((+t))= (log Sh 1 (s) - log Sh (s),
(s)).,(t1)) (s) Sh (s))
Rearranging terms gives
KL (S 11 1sh ((+11) - (1 - kTL (Sh.r 11 (/n + KLs (z(t+1) || (11))
+ kTKL (5% (((111)
( KL. (((+1))) (((+1))
(46)
(log Sh
(((-1)) (s) -log Sh
2((+1( (( Sh.
(s) - 5% c((+)((s) (s)
< 22]l@((-11(s)) (5)
Note that
(log (1+1) (8) log (e+1) (8),
p (1)
(8) - 1h (s))
= =n(2/ (s) (s)p (s) Qn
(s), uh (1+)) (s) - Hh ())
(47)
$n|o (s) (s) Qn
(s) A (() pb
(++1) (s)ll,
We bound (6)0 o (s)o
(s) (s)] as
(s)] (s) Φh (s) (s)]l
$ $1 [1
(8) - // (4 (3) 11 + (1 - - o)))
$ 2H 1/ (s) - a (s)), + 100
(1+1)
(s)
$2H $2H| ()) (5) u/ (s)], + 2/ (s) of (+)] + ||Q - -f (s)
Plugging the above inequality into (47) and invoking Young's inequality yields
(log Ph (++1) ()) log pi (++1) (s), ph (+t)) (s) 1/ (s))
S H [| (1++)) (s) // (s) || 10 (s) (>)l + 2 1/ 1 (s) 1hh (s) IPt)
+ +n + (s) (3)
(- (s) 11 |1 (() -1p
1b ((+1)
< Hn (v% (b) 11( + HnH (v (l + AHHLL. (1+1) || p1/t11
+ 27 H Q (0) (s) Q!! ((+1)) ()) lbo
where the last step results from Pinsker's inequality and Lemma 8. Similarly, we have
(log ((+1) (s) - log ( (z), ((t)))() 1// (s))
< 2rL (1 ((+1) (1 + 2n HKL (1)
(1(11)) + AnHKL, (u (2ttt) || 1/ (
+ 27² H @ (s) - Q (1+1) (s)
Summing the above two incqualities gives (log (ogg (s) log (s), 2h (((+)(
(s) c/ c(((1)
31

---

Published as a conference paper at ICLR 2023
S 21HKL, (Sh
(G: (c (()))) + 22///KL (1) (1(%))
(CH (((tt)) (c 11 (1()))
+ 4nj H Q (1) (s) - Q(tt1(
s 22//HLL, (Z. (1(()) + +2///LL, (10 || (1)) + 44HHKL, (ch
11 Sh ()
+ 2 2 (100 (s) Qh (5)l + 1 (s) - Qh.- (+)l
where the second step invokes triangular inequality and the fact that n S 8H Plugging the above inequality into (46) gives
KL3 (Sh.- 11 (1(+)))) - (1 (1- (Lt-r))L(((irr (1 + (1
n/T + +2H))
(5h ((((+1) || (1<h))
+ tTk Ch
(11) [[m,,) + (1 - 4nl (32 11 |1 11 (((+))) - 23 21, (Sh || 2(0)
511 - 2 11
(s) (( Q7(5)]( + "110%²² (s) - Q7(5)) [
With s 8H. we have (1 - (1 - (1--))11-4441/))) Hn 2 H1 H and 1 - 11(T + 2H) 2 0. It follows that
KL, (5 l1 Sh )) + - 4nH (ch 11 || (11+ + 1y (L. || (t,r)
1 (1 - mT)K, (sh, 11 (14%))))) + H22 (c) || (1((% ((0))
+ 5y
1110//1 (11 (s) - Q7(5)) ~ 2110%
!
_ (s) - Q+(s)
2
S (1 - m7) [KL (St 11 +(1 - -n, (ch. || )
+ |1
57 (1+1) 1) (s) (5) ~ 2 "2100% (s) (s))
11 h
Therefore, it holds for 0 tı tu that
(Gi, (1 ((2)) + (1 4n (((t)) || x( + mTKL, (E(ta) [
$ (1 - 7r) t1 [KL (S || 5/ (b1) + - 4n) (1:1 ((7))
+ Σ
(1 - m))) )/2 1- 5m
[
110
(1) (s) (3))
+ 2
(1 *2110%
7
- -s((s(
f' 1
< (1 m/) 7-)²² 1ー (KL ( (h.rr ) + (1 - 4n (1:) 1| (1))))
+ 4nj Σ (1 - mイ)  1|0 (s) - (:))l
1=b
D.2 PROOF OF LEMMA 10
For to > 0, we have (12)
Q hh (s, a. b) - (3,
(s,a,
E B V/ v)((-11(s)) (5') - (+))
s' (-P.1((11,,00))
(1 - 177 tt (v (s') - (5)(
E
s' 1(1,,0006)
f--1
+ 1/T
(()( (( -mh ((i)) S (her:
1/) 1/ -1
12-1
< (1 (1-77))0-012
+
E
>
(1 - (1-
- frr( Wh..r virrr)
8 s (11,,bbb)
1=t1
(48)
32

---

Published as a conference paper at ICLR 2023
We start by decomposing 18 f
fs fl( f . ( , x/ - fo(Qu, Ph. k/,r))
(f.(O)) (1) (1)
Ph ; )/ - 1.10%%
(1) (1) P (/,r)) + f.(0) .p .1h.t) - folQ), 1hi vh,r)
I (f.10 (1) Ph (1) (0 f.(0 p/ vh.))) + f.((2t 1ha))) f. f.( Mh, 1h,-))
+ 100 (s) (8)l
S f.10% 1 (1) , k f.(0f) 1/ (h,,) + (s) Qi, (s)loo
Note that Lemma 13 can be applied to the episodic setting by simply replacing 1/(1 7) with H, which yields
f10 p/0 ( - Ph.
10 (5) Qh (+)] + 2n 1/ (8) (s) Q4 (s)]loo
1 - " KLs (vi 11 1) - 1
+
KL, (v/,r - || ///h))
(49)
"
17
1 (1- knH]KL (uh (1) || )//)) 1- rxT
(t) --1TT KLs (b) (11)))))
"
1
+ 211 (KL (1) ( KL. (k/ (1 || 1///111 11)
By a similar argument,
f.QQh...
(1)
Ph (11))
< //00000 (s) 2h (0) + H| Q100)) (s) 211 (5))
+ 1 "T KL (ph.t 11 1//2 11) KL. (1ihr 14/
(50)
"
17
1 (1 - KL (1/ || (1 1 1- 1|T KLs (1% || 11 (1))
1-11T
+ 2H [KL. (7/1)) 1/ ()) + KL. (Lh (1/h-1) (1 (1
Computing (49) + 3. (50) gives
3 [1(()) 10 1 (0)) - ʃa (h [
s [100 (5) (1) + 2n 0// (s) -
5
- TTT KLL (1h 1//0 ((-11) + KL. (Hh.r 11 [11
- _
KL..
2 3KL, (1
+
7
17
3
+ 2H [KLs (1/h
(1-1) || 2// ((-1))
+
2
KL. (v/
11-1) || 1/ [1-1
3
1 (1 4ntt]]
(1-4ntt)
[
kL, (1/
(t)
(1
KL.
(1/
(1) 1/11 ||,;1/]
"
3
+ (2H-
1- nT
2
KL, (م19)) || (ل + (HH
2
1 T1T KL. (2(0) (((0)|/(t1)). (51)
n
3
3
With 17 S 3H we have
1 - TπT 2
2
1- 17T
1 1 m7) 4nH)
2 2 2H.
2H
<
0,
2H
2o, and
7
3
1)
Let
(6) = KL,
(L,
/12
+
KL, (Hi.r (1 (1)
3
33

---

Published as a conference paper at ICLR 2023
+ 2 -nnl))) (uh (1(2)) (L, 11/])]]
We can simplify (51) as
T2(21) p1)) ( - fa ,h, vT(r) (( (s) ohr [s) + QQ
(0) (6) - (s)1la)) 1 77 (() c (s).
(s).
"
1f
Plugging the above inequality into (48) gives
Q (12) (s, a, b) - 1 a))
S (1 m/)) 12-22221
1-11
5U9T Σ (1 - (1-m))---1(100 - (8) + 27H 10000
1 (5') - (s')ll))))
E + Ph Pl. 1(11,,0,8)
l=t1
7(1 m77) ((
s'~ 1 ())
$ (1 77)) 22-2 H1
h-1
Σ (1-m7))>1--1100)) (s') - 2h, (6')l
+ 10nT
E ('MPa-i((le...))
L
+ T(1 (-(1-1))22-
(
(Chur 11 111-11) + (1 4n (G( ((c(h--1)
E PROOF OF AUXILIARY LEMMAS
E. PROOF OF LEMMA 11
We first single out a set of bounds for (()) and Q(0, which can be obtained by a simple induction:
log
((0 S 1+ log LAI
v(s, a, b) E A
log
B
Q a, < 1orro
(52)
We invoke the following lemma to bound several key quantities that will be helpful in the analysis. Lemma 15 ((Mei et al., 2020, Lemma 24)). Let n. a' E A(A) such that (a) x exp(6(a)), 7 (a) xc 8' (a) for some 0, 0' BlAA, It holds that
|| n 112 S 110 0'
With this lemma in mind, for any 1. 2 0, it follows that
(s) (((+))(s))) (s)
S min cER
|log ((++1((s))) - log ((t))((ss) - cc 1 1//0
$ 1/ Q (t) (s) (()+))(s)) (s) 10.0
< <. 1 7T (log
|A| + log BB)
2m
< 1 1-7"
1-?
and similar argument reveals that
[[((tt)())) - ((++ (s)]l S -T-7
2n
Next we make note of the fact that when 1. 12 1,
((+)((als)) ( (al ( (s)((t)ss) (s))
n ( (a|s) 1 1- "F exp (1((()()))()))))
-1- ()))) (s)o(t))))))))
(53)
34

---

Published as a conference paper at ICLR 2023
where
w0 ((0))(0)))) (1 (1)))((()))0(() - (3)())))))) - - -log (s)
satisfies
||
|o 00
< 11
(s)
(s) [s) + || log ş (0) (s) +1 (s)(() (s)(t()
20
2
2
+ 2(1 17T)
$
1-y
where the second step is due to the following bound:
2
Vt 2 0, S,
max ([)log(())))) |oog (s)
(54)
(1 -))
Recall that when have p((+1) =1(l). So we have
(s) (0)] - 6n
S,t 0,
1
It remains to prove the claim (54).
Proof. is worth noting that (s) can be always written as (alss x (xp(w for some w(t) E RlAl satisfying
yT log [B] 1-7 S (a) S + 7T log |A|
Va A,
1-y
To see this, note that the claim trivially holds for with w(()) 0. for some t 2 O, we have
When the statement holds
p (als) x p (als) exp(n (++ (s))(+++))
exp (((1 - (/r) nr Q (s)(+))))) x exp (111 /T);
with ((+1) = (1 177 (w() + Q (8) (s)) We conclude that the claim holds for / + by recalling (52). then follows straightforwardly that
( (a1) exp (0 (az)
(ai) ((() (az) S exp
(1 + y (log (A| + log (B1)
(1 - 7)
for any E A. This allows us to show that
min 1 (a) 2 aEd
1
Σ (a)
Axc exp (log (log [4)
|A exp (1 +log (8)) (1-7)r
(1-7)r
aEA
which gives
(log 10
1mx <
+ 7r |A| + log [B)
log |A| S (1 71-
1
+
log |A| + log [B]
7)7
7
< (1 - 7)T""
E.2 PROOF OF LEMMA 12
We decompose the term fa (Q(()))), ((((t))),,((111))) (((11))- - (a(0(1),,))) ,700, zl() as follows:
(.(()+)), (00((t),,,(++)))) (1(+1), z((++)) (1) ,7(0) ()(1)
((((()) (((11) (((+))) (.((()) ,(((t1) r((+1) + 11( (1(t1))) (((t1)) (((00.000) 200)
35

---

Published as a conference paper at ICLR 2023
= =)) ( (s) ( (s)
+ + , ,01)) - 11( b(0) + S1( ,1 (((t)) - (0000 ,00))
+ + ,plttt) " plltl)) + f2( 2l0)) s((( - 11111),, - f.(Q 1,1000, " ]lttiia (httee
.n
& - - (1) ([)(+t)((s) Note that (s) (Q((t))s)) - (19)) (s) (s) { in the bracket, have
For the terms
(1 plltt), bl(+1)) + f(( (1()) -(0)) -f((0() ,((+1), p(0) f(((()) ,00) ](tt)]]
(n(tt) (s)) (s) (s))
2 KL. (c || (10).
v 1 1-7
remains to bound the two difference terms ( p(+)), dl)) (,(00),,p)) p000,,00)] and [ nl0, p((+1)) - f.(Q(0,, n20, b(0)] To proceed, we show that fe( ,00000),000000000 210)- - f.(("") p((t1) )())
= (s) (s), (s) (() ++)(( -
(s) (s), (s) (s) + (1 - (1))(( - Q Q(t- () (s)
+ +TH(T (8)) (+)
(1 - nT) (1
(5) ((tt1)( (s), Q (s) (s) Q(t (s)
1 KL. (1 || /((t2))- 1 1-1 17 KL. (z((+11) || 210000
=
"
7
-11 (p())) (s) 1 Q (s) (s) Q(t (s)(t-))
(55)
Here, the third step results from Lemma 17 along with (53). Recall from previous discussion (ef. (53)) that [((++) x (alss) (xp())((0) (s)) with some (1) e R5 satisfying
w |oo I1.0 S 7-
6
We can ensure that (1 S 1/30 with n-! 2
1-y' and the next lemma guarantees
180
KL3 || ()( s 2KL, (p((-1) 1) || (1)) in this case.
Lemma 16. Let w E RIAI, n, E ((A) satisfy, for each E A. r'(a) x T(a) exp(w(a)) with ||w]oo < 30 It holds that
KL(T [|') S 22L((T)) I))
Therefore, we can continue (55) by showing that (f(())) ((QQ0,,(())) ((11), x(0))=
(Q) 10 |(0))|
$ KL. (1(0) 11 + 1 - ., KL, ( (1(++1) || 2(00
"
+ (((a(( - (00 (1) (s) - Q( (s) (32+t-)))))))))))))))))))))111)) oc
3 KL. (2((t2) || (1)) + ([) - (3)) (s) (s))
"
+ (x) (s) - (1)) (s) - plc (s)]l
( + 2112n) KL. (2/4411) (00)) + I-7 KL. (2 || إاداار +
3 2
6n - 11)000( - Qi)-)
One can bound (Q()), together, we arrive at
(2()),,, (()) (((+1))] with similar argument. Putting all pieces
((((1) ,((0)))),(0)))) b((+1)) 11((()) m E(0))
36

---

Published as a conference paper at ICLR 2023
$ (0) + (
1- KL. (1((+
4
2 1-7
KLg 1)
+
20
12n (s) Q1=11) (s)
+ 1-7
E.3 PROOF OF LEMMA
(s) - (z)) Q (1)3))))) + HH(2((s))
= (s) (s), ( (1) (
+ (s) (s),
(s) [H(E(( + (s((0((s))
+ (s) -(),,,
(8) (H((()())) +H((G)())
(s) - (s), (s)),((11
(()) (s) (s) (s) (s) (s)
+ 1- KL,
-K, KL. (v(0) ( _ KL. (v(1) (1] || 1- KL, (D()) ( [1(111)
1
"1
+ 1 - VT KL.
KL. (1 ||-l111) - 1 KL (vv [(att)
- --11 KL. (ult)) (1(t-11) (L,(u(0)uult-))
I || (s) (1) (s) (s) -Q(t-1) (x)))))))(s)11
KLL 1 || 1 1- - kL, (b(()) [((t11) + 1- nT KL, (v= (1
KL, (v, vl0)..
17
17
(56)
The second step results from the following three- point lemma: Lemma (Regularized 3-point lemma). Let x E (AA) be defined as
x(a) x v(a)) exp(-)pu(a))
for some w E TRllA| and y E A(A). It holds for all A(A) that
1) - tjT (x - 2, u) - -H((x) - -H((s)] = (L 1- (L(2 - (L
We bound the first term in (56) follows:
(s) (s)
w0)) (s) (s)) - (s) (s) (s)
$ (s) (s))), -1(-0)))))(--))))))) T
+ (1010 - (s))
(s) (3)))) (s) (s)
I - | (s) ()) (1)1 -)))(
2n (s) Q 10-)))) (8) + 1 - 211000 (s) w (s)]
s 1
+ (s) - (- (0)) + (1 - n² 10 (s)
2n (s) Q (s) + 1 KL, (x(0)) (())
4
2 (L( (1))
(+)) + ア-ク
2
(L(
(s) (s)
1-7
Substitution of the above inequality into (56) completes the proof.
E.4 PROOF LEMMA 14
We have
o = aj II
(1 caa)
i=1+1
37

---

Published as a conference paper at ICLR 2023
= aj II (1 0204 + (02 - )a;a
i=+1
ar(e2 c1)4111 II
cza4 (oz c)aa)) + arl1 c2a1+1)
II (1 02a1 + ((2-
i=(2
i=++
= aj t=+11
(02 - -1)a
(1 - oraz).
II (1 cas) +
II (1 - c20:)
==++1
k=
[=+1
(c2 - -1)
Σ
fu, + Er.
i=141
Rearranging terms,
Σ a1d111, + E E,10011,1
im1+1
a1+1
01 + Σ
a++1
= 1 - 1-0+1
a; - -9041)
i=1+1
81,1 2
Σ
E1,581. 51,
2 (ōτ, E1,1) 1 (1
2
61.41
C2 -
02 c2
1=/+1
where the inequality due to a4+1 S a S 1/2 and 1 cia 2 1/2 for all 1.
E.5 PROOF LEMMA 16
Proof. For any 11, it holds that
x²
x²
log(1 +
S x
+
2
3
x²
x
1
x
$
x
2
3
2
and that
x²
log(1 + x)) 2
3(1 + x/3
2
3
[r| 3(1 + 2
3(1 + x)
Therefore, when To we have
(1 + .:)3 > 3/2 and thus
1 x 5 +
x2 S log(1 + x) Sx
2
Let be a shorthand notation for |/wl The following lemma is standard (see, e,g., (Mei et al., 2020, Lemma 23), (Cen et al., 2021a, Lemma 3)), which ensures that |log log < 2c. Lemma 18. Let n, n' E A(A) satisfy (aa) exp(f(a)) and (a(a) cxp(6'(a)) for some 0 0,0' R It holds that
||oog - -
log log 1' S <2|10 0'11o0
Since e < 1/30, we have
((a)
-eep ( (log T'(a) ) exp(0) I log ((a) log n xa(a) max {1, T(a)) 2cexp((2c]) 3c, Va A.
T(a))
r'(a) }
n (a)
38

---

Published as a conference paper at ICLR 2023
Therefore, can bound KL(TT) ||
x²)
as
((a)
KL (T || x²) = Σ T(a)
log
(a)
aEA
S Σ T(a)
(a)
1 - 2
c)
T(a)
-1)
T())
aEA
x²(==²² - 1 c) Σ T(a)
1
[(aa
1) 2
(57)
7'(a)
aEd
S <x((x;²')) - -(2 c) (1 - 3c)
Σ
π'(a)
((a)
1)
(a(a)
aEd
(1
1 2
c)( -3c))33))) x2 (T;:'')
On the other hand, we have
T'(a)
KL
||
Σ
x'(a)l0
log
T(a)
aEA
(a)
1 3c
TT
1) ))
Σ (1)
T(a)
T(U)
aEA
= (x((m
1+ 3c
Σ ('(a)
T (aaa)
- 1) 2
(58)
2
T(a)
aEA
2 (T('T)))
(c+3
T(a) (a
T(a) - 1)
acA
3c)²
(1 2
(
By definition, we have
x(a)
- 1)² 2 =Σ
(T(a) r' 2
(T;=)')= = Σ 7'(a)
(a(aa
r'(a)
aEd
aEd
(T'(a) - -a))
(59)
$ 1
T(a)
aEA
$ (1 + 3c) (=
Combining (57), (58) and (59) gives
1- (1/2- 3c)
KL(T|I=)) - (1 + 3c)
1- (1+ -3)///2 KL( 1)
It is straightforward to verify that the factor is less than 2 when e S 1/30.
E.6 PROOF OF LEMMA 17
Proof. We have
KL(2 |1 v) -H((2) + H(y) - (2 - y. log y)
= =-H((z) + H(x) - (2 2, log v)
H((x) + H(y)) (x y, v,
=-H(==) + H(x) -(= xr, log x)
H(x)) H(y) -(x y, vologv) (2 -2--2, log y
log
-KL(211)) + (L(x 1 1/T
(2 x, w + :log
Rearranging terms gives
77
{x 2, w) (L(=11)) -KL(2 =|) KL (8)) + 1 9pt
1/T
(2 x. log
39

---

Published as a conference paper at ICLR 2023
Adding 1-
+ H(2)) (-H(x))
to both sides, are left with
97T (2= 2, w) +H()) + +H(=)]
(L(= (1y) KL(x KL(x (1
mT _ ( -H(()) + H((x) - (2- I,, log
1- 157
= <KL(=1l)) 1 Tp
KL(z (|) - (L
F FURTHER DISCUSSION REGARDING APPROXIMATE ALGORITHMS
In this section we verify the convergence of the proposed method equipped with inexact value up- dates in the infinite-horizon setting, where (10) in Algorithm I is replaced by
(s, = r((s,a,)) + +7 [v)] + (1, a,
(() (11- - a2+1)
+0++1 (s) (1)+)()))(H)))))))))) + (H(x - +H((((-1)()))]
equivalently
(s,tt)ssaa,)) = (1 - ai) b) + (ou[r(s,a, b) + -B
(s)
+ - (H((") + (s,
Here, ö(s, a, b)(++1) E IR represents the error due to approximate evaluation. For simplicity we focus on the case where the policy update rules (9a), (9b) remain unchanged. The following theorems reveal that the algorithm converges linearly to the QRE until it reaches an error floor determined by (
(1-ا)² and a; T7T, we have 3200UC,
Theorem 5. With 0 <1 <
max (SL (0))
KL KL
11 (1) 3n E
(() (+)) (+))) }
2
soup
< 71-7 (1-3)nr ! 1500
3000
|
1000 |iroo
max
- (1-
osist
(1-n)²
Theorem 6. With 0 < 17 S
and a; = ITT, we have
32000C,
max (VaLets (s) ".a"" (s) sES.
v 2111/pllo max (1-
1 1 71-
8
n
1 1-7
[ 3000
(1
(1
(1-7)
1500
|5(0
2
4
(1 7)r
osist
max
[(6]
and
max (Vmoe (p) (p)-1a(0) (p)) < 2.2
20 P.z.
8
1
(1 - 1->mmm
max
1
1 y
(1 (1-77) 2
17
4
3000
(1
(1 11-7)mg -))1
1500
max ||
+
(1 - 2T
4
(1 (1-7)) 7)r
osist
We remark that || (P())) can be bounded either by Estat Cpestat with evaluation error guarantee Estat respectively.
max,es (1)) S Estat and E
srop [l]5((
The remaining part of this section outlines the proof for the above Theorems. For simplicity, we only highlight the key difference from the previous proof due evaluation error and omit the proof for corresponding lemmas. We first remark that Lemma I depends solely on the policy update rules and hence still holds. The error propagation of {8()) is captured by the following lemmas which parallels Lemma 2 and Lemma 16:
40

---

Published as a conference paper at ICLR 2023
Lemma 19. With 0 17 S min -
(1 (1-11/181)) 1800
/48), it holds for all t that
- 1+1
+
4Cp
0n
kL
(1
2 1=1
"
t=1
+
+ (Te)) (1ip) + ---1|1/((11) 1rres
(60)
When t = 0, we have -8) (s) [()) 2 + 001| 1|T6
Lemma 20. With 0 < n (111)//
/1. it holds for all 2 1 that
|Q((+1)
@illr()
+ <
one -Qilro) + +1 11000 Qth (1roo)) + 200. + arllo(0)
2n
2
(61)
When t = 0, we have -000-orllroo S S + am | 1rroy
Following the similar argument in Lemma 4, we can show that
Lemma 21. Under the assumption of Lemma 19 and 20, it holds for all 2 0 that
12n/
N 1 Inll: - ((++1)) (ro) + (1 (1
1=0
6250nCp
[-1
A (1
(1 7)2 Au,t+1 + 60n Σ
550n
- (1 - 7)3
With 0y 7nt for I 2 1. we have
1111,4100 |ro: S 01,041|1800110
+
max isist
|800
A441,44110
1=0
1=1
S S1.441|18100 (r()
max sist
|8000
S
max
(500
1 1-
1
osist
It is then straightforward to put together the above lemmas in similar way to the proof in Appendix A to obtain Theorem 5 and 6.
G FURTHER DISCUSSION REGARDING WEI AL. (2021B)
This section demonstrates how the last-iterate convergence result in Wei et al. (202 Theorem 2) in terms of the Euclidean distance the set of NEs can be translated to that of the duality gap. Given any policy pair = (1, v) and a NE 5* = (H",v*), we can invoke performance difference lemma (44) and obtain:
(a)(p) v*(p) 7 s'audii
(uss')QQ( -10
<
E
max n/ (s') ())x)())))00000))))0000000000000
? s'ovd
max // (s')'('')))))") ( (oc_0)))))mmxx(()0000000
?
el e'
<
max (3)())
7
7) s'nd
41

---

Published as a conference paper at ICLR 2023
Setting j the best-response policy of v, L.e, / (i(() arg max, (p)( get
max Vi (p) (p) = (n((s),(() (p)
1
$ (1 - 7)2
[||x(s)) 1² (s') [[
stouth (r).e
||0b (w):01)
1
[[s()) - -s)))
(1 - 7)2
YES
Similarly, we have
|10b
(p) min Va (0) S
lu(s') (5')
(1 7)2
Taken together, the duality gap can be bounded by the policy's 's l distance to NE (n², v*) as
(p)
Vuv (D) - (1 7)² Σ (11(2)) u² (s'il +
10 -1
1 w'
18 ( 18))
- (3)) +l((ll((s)))))) (o(ss')-'(ss))) 1/2
(1 71-
where the second step results from Cauchy-Schie Schwwrz inequality. Finally, recall from Wei et al. (2021b, Theorem 2) that it takes at most
S 11 2
iterations to ensure
- - +1l((=)) (- s
S
#ES
with 1j² 0((1 -) 7) 11-1)) Putting pieces together and minimizing the bound over n, this leads
to an iteration complexity of
||AA( + 1/2 (1 - 1660622
to achieve e-NE in a last-iterate fashion.
42


Reviews:
[{"review_id": "YXms0GqGwp", "reviewer": "Reviewer_mJWC", "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 focuses on two-player zero-sum Markov games and studies equilibrium finding algorithms in the infinite-horizon discounted setting and the finite-horizon episodic setting. The authors propose a novel single-loop policy optimization method with symmetric updates from both agents. They show the proposed method achieves a sublinear last-iterate convergence to the Nash equilibrium by controlling the amount of regularization in the full-information tabular setting. Their results improve upon the best-known iteration complexities.", "summary_of_the_review": "See the Strength And Weaknesses section.", "strength_and_weaknesses": "Strength: This paper presents a novel algorithm for policy optimization in zero-sum Markov games, which can lead to an improvement over the existing rate. Moreover, the proposed algorithm is single-loop and symmetric, which are good properties for an algorithm. The overall algorithm design seems to be inspired by the optimistic mirror descent algorithm. But given that the algorithm and the corresponding result are novel to the research area of policy optimization in multi-agent RL, the contribution of this paper is significant. \n\nI only have one question regarding this paper: is it possible to extend this algorithm to a more realistic bandit setting, where both the reward and the transition are unknown to the learner? If it is not, what is the major challenge?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WP1cpgLNPK", "reviewer": "Reviewer_1xjS", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 work \"Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games\" studies two-player zero-sum Markov games, where the goals are to find the Nash Equilibrium (NE) or Quantal Response Equilibrium (QRE).\n\nThe authors proposed actor-critic methods (two similar variants, one for discounted and one for episodic settings), where the actor update is the entropy-regularized optimistic multiplicative weights update (OMWU) method in Cen2021b, and the critic update is slower (as shown in Eq. (10) in Algorithm 1). The proposed algorithms are single-loop, symmetric, with finite-time last-iterate convergence toward equilibria.\n\nIn particular, Theorem 1 shows that Algorithm 1 enjoys linear convergence toward QRE, and by setting the temperature $\\tau$ for the entropy the algorithm can find $\\epsilon$-NE with $\\tilde{O}\\left( \\frac{ |\\mathcal{S}| }{(1 - \\gamma)^5 \\epsilon} \\right)$ iteration complexity.\n\nThe above results outperform existing works as summarized in Tables 1 and 2, achieving the same desirable iteration complexity of $\\tilde{O}\\left( \\frac{1}{\\epsilon} \\right)$ as in PI- and VI-based methods while using only single-loop updates.", "summary_of_the_review": "Overall, this work studies an important problem and the theoretical results are strong. The techniques are from or motivated by prior works, but extending those results from matrix games to Markov games requires non-trivial work. The only missing part is lack of empirical supports.\n\n\n~~~~~after rebuttal~~~~~\n\nThank you for the comments. I would like to maintain my current score.", "strength_and_weaknesses": "**Strenghs**:\n\n1. This work studied an important problem of finding equilibria in two-player zero-sum Markov games. The presentation is clear and easy to follow. Existing related works are also discussed well enough.\n\n2. The results obtained are strong and promising, achieving the same iteration complexity of $\\tilde{O}\\left( \\frac{1}{\\epsilon} \\right)$ as for PI- and VI-based methods while using only single-loop updates.\n\n3. The techniques are also insightful. It shows that the existing contraction techniques used in matrix games in Cen2021b can be generalized to Markov games and can be combined with critic updates to work, which seems non-trivial and novel to my knowledge.\n\n**Weaknesses**:\n\nI have some questions after reading the paper.\n\n1. If $\\eta \\le \\frac{(1 - \\gamma)^3 }{32000 |\\mathcal{S}| } $, then the linear rate also seems to be very small in Eq. (12a) since $\\eta$ also appears there. The authors did mention that $|\\mathcal{S}|$ can be replaced with concentration coefficient in Remark 1 and Appendix A, but how smaller that replacement could be is still unclear from the paper. Could you elaborate more on what in the current analysis makes the learning rate $\\eta$ have to be very small in Theorem 1? It seems to me bounding the state distribution in $V$ is the bottleneck (Theorem 2 in Appendix A).\n\n2. It would be great to use some simulation results to verify the theoretical results.\n\n    - It would be curious to verify and observe the linear rate itself (in terms of $t$), as well as how slow it could be (in terms of $\\eta$);\n    - It would be also interesting to see if in practice larger learning rates than $\\eta \\le \\frac{(1 - \\gamma)^3 }{32000 |\\mathcal{S}| } $ could be used and still achieve convergence, which means the analysis has space for improvement; or larger learning rates lead to non-convergence, which means it has to be what is used in Theorem 1 (in this case, I think the authors should do better jobs in explaining the difficulties of using large learning rates here).\n\n3. I did not find any assumption of unique NE in the draft (the authors did mention that other works require unique NE assumptions, and this seems to say that they do not need this kind of assumption). Could you comment on what is the quality of NE for the convergence results in the paragraph below Theorem 1 (\"Last-iterate convergence to $\\epsilon$-optimal NE\")?\n", "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": {}}, {"review_id": "SuG701SDG_", "reviewer": "Reviewer_Ki1t", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper discusses policy optimization in two-player zero-sum Markov games with sharp last iterate guarantee.", "summary_of_the_review": "This paper discusses policy optimization in two-player zero-sum Markov games with a sharp last iterate guarantee. The paper doesn't come with an appendix and covers very little about the proof techniques in the main text.", "strength_and_weaknesses": "The paper doesn't come with an appendix and I can't verify the correctness of the paper. The discussion about the technical highlight is also very limited. The authors may want to move the episodic case to the appendix and discuss more the proof sketch and technical contribution, including the limits of the existing results. I think it would be super helpful for readers.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DWXWdx-Xjk", "reviewer": "Reviewer_HSt5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies computing Nash equilibria in two-player zero-sum Markov games, by proposing a single-loop and symmetric algorithm with last-iterate convergence guarantee. The derived iteration complexity improves over previous works by a factor of $H$.", "summary_of_the_review": "Despite the improved iteration complexity, there is still unneglectable ambiguity regarding the rationality of the setting considered and the novelty of the algorithm design and analysis. I am willing to raise the score if the above issues are well addressed.", "strength_and_weaknesses": "# Strength\n\n- The iteration complexity improves over the best previous results by a factor of $H$.\n- The paper is mostly clearly written.\n\n\n# Weakness (and questions)\n\n- The proposed algorithm simply combines the entropy-regularized OMWU method (Cen et al., 2021b) with the V-learning style value update rule (Bai et al., 2020). The techniques used in the proofs also look quite similar to the previous ones. So it's a bit unclear to me how much algorithmic and technical novelty this submission possess beyond blending the existing ideas.\n\n- The interaction protocol considered in this paper is very strong, which basically enables running any dynamic-programming style algorithms. In this case, why isn't it a better choice to run DP-style algorithms, which is algorithmically simpler, theoretically easier to analyze, and oftentimes have better iteration complexity.\n\n- The results in this paper seem to highly rely on the gradient feedback being exact to guarantee the linear convergence rate on the strongly convexified problem, which makes it hard to generalize to the sample-based setting. \n\n\n\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster