Sample Efficient Stochastic Policy Extragradient Algorithm for Zero-Sum Markov Game
Authors: Ziyi Chen
Shaocong Ma
Yi Zhou
Venue: ICLR 2022 Poster (2022)
Keywords: Two-player Zero-sum Markov game
Entropy regularization
Policy extragradient
Nash equilibrium
Sample complexity

Abstract: Two-player zero-sum Markov game is a fundamental problem in reinforcement learning and game theory. Although many algorithms have been proposed for solving zero-sum Markov games in the existing literature, many of them either require a full knowledge of the environment or are not sample-efficient. In this paper, we develop a fully decentralized and sample-efficient stochastic policy extragradient algorithm for solving tabular zero-sum Markov games. In particular, our algorithm utilizes multiple stochastic estimators to accurately estimate the value functions involved in the stochastic updates, and leverages entropy regularization to accelerate the convergence. Specifically, with a proper entropy-regularization parameter, we prove that the stochastic policy extragradient algorithm has a sample complexity of the order $\widetilde{\mathcal{O}}(\frac{A_{\max}}{\mu_{\text{min}}\epsilon^{5.5}(1-\gamma)^{13.5}})$ for finding a solution that achieves $\epsilon$-Nash equilibrium duality gap, where $A_{\max}$ is the maximum number of actions between the players, $\mu_{\min}$ is the lower bound of state stationary distribution, and $\gamma$ is the discount factor. Such a sample complexity result substantially improves the state-of-the-art complexity result. 

Published as a conference paper at ICLR 2022
SAMPLE EFFICIENT STOCHASTIC POLICY EXTRAGRA- DIENT ALGORITHM FOR ZERO-SUM MARKOV GAME
Ziyi Chen, Shaocong Ma, Yi Zhou Department of ECE
University of Utah
Salt Lake City, UT 84112, USA (u1276972, zhou, ma) @utah.
ABSTRACT
Two-player zero-sum Markov game is a fundamental problem in reinforcement learning and game theory. Although many algorithms have been proposed for solving zero-sum Markov games in the existing literature, many of them either require a full knowledge of the environment or are not sample-efficient. In this paper, we develop fully decentralized and sample-efficient stochastic policy extragradient algorithm for solving tabular zero-sum Markov games. In particular, our algorithm utilizes multiple stochastic estimators to accurately estimate the value functions involved in the stochastic updates, and leverages entropy regularization to accelerate the convergence. Specifically, with proper natropy-regularization parameter, we prove that the stochastic policy extragradient algorithm has sample complexity of the order O e-Nash equilibrium duality gap, where Amax is the maximum number of actions between the players, Mmin is the lower bound of state stationary distribution, and r is the discount factor. Such sample complexity result substantially improves the the-hhr art complexity result.
Puice (m ) for finding solution that achieves
state-of offe-oofiie sitee-of-th-aaa
INTRODUCTION
Competitive reinforcement learning (RL) an emerging and popular framework that has broad applications in various areas, including market pricing applications (Kononen and Oja, 2004), real- time strategy-maken mrakegg (Vinyals al., 2019), board games (Silver et al., 2017; Moerland et al., 2018) and inverse RL (Zhang et al., 2019). In particular, important and fundamental formulation of competitive RL is the two-player zero-sum Markov game, which involves two competing players that interact with common environment and receive zero-sum rewards. Both players aim to learn the optimal policy that achieves the Nash equilibrium of accumulated rewards.
Algorithms for solving Markov games are very different from conventional single-agent RL algo- rithms. In particular, both players must learn to improve their policies based on feedback from the opponent and the environment, but usually the opponent will reveal any sensitive information (e.g., actions or policy) or cooperate with each other. In the existing literature, numerous algorithms have been developed for solving zero-sum Markov games, including Q-learning (Fan et al., 2020: Zhu and Zhao, 2020), fitted Q iteration (Zhang et al., 2021), policy gradient (Daskalakis et al., 2020; Zhao al., 2021), policy extragradient (Cen et al., 2021), model-based Monte Carlo estimation (Zhang et al., 2020), optimistic gradient descent ascent (Wei et al., 2021), etc. However, many of these algorithms require both players to access their opponent's actions (Wei et al., 2017: Sidford et al., 2020; Huang et al., 2021; Jafarnia-Jahromi et al., 2021), which causes privacy issues. On the other hand, some algorithms need to know about the environment transition kernel and reward mapping (Cen et al., 2021), which are usually unknown priori in practice. Moreover, other algorithms require both players to perform asymmetric policy updates using different numbers of iterations, learning rates or exploration probabilities (Zhao et al., 2021; Daskalakis et al., 2020), which generally

---

Published as a conference paper at ICLR 2022
hard to coordinate in advance between two competing players. Therefore, it is desired develop an algorithm for solving Markov games that avoids all the aforementioned issues.
Moreover, from theoretical perspective, the convergence and sample complexity of these cxisting algorithms for solving Markov games have not been comprehensively studied. Specifically, some studies established the convergence of the algorithms with i.i.d. samples (Zhao et al., 2021; Guo et al., 2021), which violates the dependent nature samples collected from the dynamic Markov decision process. Also, other algorithms suffer from an extremely high sample complexity to achieve an approximate Nash equilibrium solution (Wei et al., 2021). Hence, we are motivated to answer the following fundamental question.
Q: Can we develop fully decentralized algorithm that is model-free and takes symmetric and private policy updates for solving zero-sum Markov games, with provable convergence guarantee and an improved sample complexity for achieving a Nash equilibrium solution?
In this paper, we provide positive and comprehensive answers to this question by developing a fully decentralized stochastic policy extragradient algorithm. In Table of Appendix F, we compare the key properties and sample complexity of our algorithm with those of the existing algorithms.
1.1 OUR CONTRIBUTIONS
We consider standard zero-sum Markov game with discounted reward over infinite horizon. To solve such a Markov game, we propose stochastic variant of the policy extragradient algorithm (Cen al., 2021) that satisfies the following amenable properties.
Our algorithm uses multiple stochastic estimators to estimate the value functions involved in the predictive updates for solving not rely any prior knowledge of the environment transition kernel (model-free). Moreover, the resulting stochastic policy updates of our algorithm for both players are symmetric and do not involve any sensitive information of the opponent (private).
matrix games, and therefore the algorithm does
Compared with the stochastic estimators used in (Wei al., 2021), estimators have much smaller variance that helps improve the estimation accuracy. Specifically, by developing new techniques (explained in the next bullet), establish tight high-probability estimation error bounds for our stochastic estimators with Markovian samples. Then, with a proper entropy- regularization parameter, we show that stochastic policy extragradient algorithm requires achieve e-Nash equilibrium duality gap,
sample complexity of the order O which substantially improves the state-of-the- complexity result of (Wei et al., 2021).
We develop novel techniques to bound the estimation error of the proposed stochastic estimators, whose numerator and denominator involve sample average approximations First, we propose a special estimation error decomposition that avoids divergence of the bound caused by possibly small numerical values of the sample average involved in the denominator of the stochastic estimators. Second, we leverage this error decomposition and the recursive structure of the stochastic estimators to derive a contraction property of the estimation errors, which eventually leads to tight bounds for the estimation error. We refer to Section for more elaboration on our technical novelties.
1.2 OTHER RELATED WORK
Other settings of two-player zero-sum Markov games. In this paper, we focus on standard setting of two-player zero-sum Markov game with discount and infinite horizon in the discrete time domain. There are other settings of two-player zero-sum Markov games. For example, Bai al. (2020); Huang et al. (2021) studied a two-player zero-sum Markov game with finite horizon and without discount, whereas Daskalakis et al. (2020) considered finite random horizon without discount. Jafarnia-Jahron et al. (2021) also considered the setting without discount, and it allows one of the players to constantly adjust its policy based on the entire history of states and actions. Ghosh et al. (2021) studied two-player zero-sum Markov game in the continuous time domain.
Multi-agent general-sum Markov game. Some works studied multi-agent Markov games, which extend the two-player zero-sum Markov games multiple players without the zero-sum constraint (Wang and Sandholm, 2002; Hu and Wellman, 2003; Deng et al., 2021: Leonardos et al., 202 I). More specifically, Leonardos al. (2021) defined and studied Markov potential game which has potential
2

---

Published as a conference paper at ICLR 2022
function assumption. Guo et al. (2019); Elie et al. (2020); Gu et al. (2021) studied mean-field games with large number of players.
Entropy regularization and value iteration Our algorithm leverages entropy regularization and value iteration to accelerate convergence. Entropy regularization is a popular technique that has been widely used in reinforcement learning (Neu al., 2017; Geist et al., 2019; Mei et al., 2020; Cen et al., 2020) and Markov game (Mertikopoulos and Sandholm, 2016; Savas et al., 2019; Cen et al., 2021) to encourage environment exploration and accelerate algorithm convergence. Value iteration is also a classical method that is widely used in both single-agent reinforcement learning (Ernst et al., 2005; Tamar et al.. 2016; Farahmand and Ghavamzadeh, 2021) and Markov games (Zhu and Zhao, 2020; Cen et al., 2021). With full knowledge of the environment, it exponentially converges to the fixed point of Bellman operator (Cen et al., 2021). Compared to another similar classical method called policy iteration, value iteration does not need policy evaluation which involves additional computation (Sutton and Barto, 2018).
BACKGROUND OF MARKOV GAME AND ENTROPY REGULARIZATION
2.1 TWO-PLAYER ZERO-SUM MARKOV GAME
In a zero-sum Markov game, two players compete with each other in a common environment. Throughout, the state space denoted as S. The action spaces and policies of both players are denoted as A (11) and A 722), respectively. Here, T(1) A(IA4)), (22) ((44(2)) random policies defined over the corresponding simplex sets. The reward function is denoted as R: S x A x (2) - [0. 1). and the discount factor is denoted as 7y E (0, 1).
At any time t, both players observe state 8 S of the environment. Then, both players respectively select their actions following their own policies, i.e., at (2) ~ (-Iss) and a; (2) ~ T (-1st). After that, the environment state transfers
state $t+1 following the underlying transition kernel
P(. of dj (2)), and both players receive zero-sum rewards, i.e., nZ(2)
R( R. where (2)) With this Markov decision process, we can define the following state value Rg [s af ai function associated with the players' policies π (1) and (2) for any environment state E S.
Vo 12) (s)
? Re 80 s)
(1)
t=
The goal of both players is to compete via the following minimax game in all states
min max
V (s).
x()) x(1)
In particular, it has been shown in (Shapley, 1953) that there exists Nash equilibrium policy pair n (1) (2) for zero-sum Markov games, i.e., V Va (s) S V2 ا.يي (8) S Va _ (s) holds for n.
any other policies x(1,, n (2) and for all states s.
2.2 ENTROPY-REGULARIIZE MARKOV GAME
Entropy regularization is a popular technique that has been widely used in reinforcement learning (Neu al., 2017; Geist et al., 2019; Mei et al., 2020; Cen et al., 2020) and Markov game (Mertikopoulos and Sandholm, 6; Savas et al., 2019; Cen et al., 2021) to encourage environment exploration and accelerate algorithm convergence.
Specifically, for the zero-sum Markov game, can define retropy-regularizee state value function by adding entropy regularization to the state value function (1) as follows (Cen et al., 2021).
20 { T In (") ((()) (s))
((r) 7(0) (2)
In n (2 [st]] so = s
(3)
where T > 0 is called the regularization parameter. With the above definition, we further define the following regulaizee state-action value function (also called Q-function) (Cen et al., 2021).
277 20 (s, (1),, (a())) := =R(s, (1), (a()) 7B P(-ss, ((())) (V]
((0) (s')]
(4)
3

---

Published as a conference paper at ICLR 2022
In partieular, ((() xx() be obtained from O xx follows.
v(r) =0) (r ) (s) (s)] o 200 (z) () (8) + - -x(
f=f= (Q a0 (s), x: ( (s), (s)).
where H( denotes the entropy of policy x. and we define this mapping as fr for convenience.
For the entropy regularized Markov game, it has an equilibrium policy pair that solves the minimax optimization problem mingra) maxx(1) V(T) (()))=())())) (8). Such a policy pair called the quantal response equilibrium (QRE). Our goal is to find the equilibrium policy pair of the original Markov game in (2) by solving the entropy-rege reguuaaireg Markov game with proper regularization parameter т. In particular, compared with the equilibrium policy of the Markov game, the QRE tends to have a larger entropy due the entropy regularization, which encourages the players explore and obtain better understanding of the environment. Another advantage of considering the entropy-regularize Markov game that the entropy regularization makes the minimax problem have better optimization geometry that accelerates the convergence of the optimization process.
3 STOCHASTIC POLICY EXTRAGRADIENT ALGORITHM FOR ENTROPY-REGULARRZED MARKOV GAME
In this section, we develop stochastic policy extragradient (SPE) algorithm for solving entropy- regularized Markov games. First, we recap the policy extragradient (PE) algorithm, which is introduced in (Cen al., 2021) solve entropy-regulariiee Markov games with full knowledge of the environment transition kernel and reward mapping. Then, we propose the model-free SPE algorithm that solves cutropy-regularizee Markov games using only stochastic samples.
3.1 REVIEW OF POLICY EXTRAGRADIENT ALGORITHM
Value iteration is classical reinforcement learning algorithm that requires full knowledge of the environment and achieves an exponential convergence rate. In particular, for the entropy- regullaiee Markov game, the k-th value iteration update defined as follows.
Qu(s, (1), a (2)) =R(s, (1),, (a(2) "B a00) [Vo(s'], (s)a()),a(2) (s+
min max fr (Qu(s); x (s), (s)), Vs. (s) (s)
where we define Qu(s) =- Q2(8, :.)) R This algorithm alternatively updates all the entries of the value functions Q2 and Vg. Thanks to the entropy regularization in the function fr (see (5) for the definition), the minimax matrix game in (7) r-strongly concave in (11) and 7-strongly convex in (22), and therefore has a unique solution.
To solve the
minimax matrix game in (7), Cen et al. (2021) proposed predictive
update (PU) algorithm. Specifically, with uniform policy initialization, i.e., = (s) |Lttmpp Vm (1,2), Vs E S, the PU algorithm performs the following policy updates: for f = 0, 1, 2,...
T (1)
(1)
T (a --) exp (1
(2)
u (a
T 1- exp n7 (s, (s,a
(s)
(PU):
(8)
Th.ti (a
1-) exp (nQ (1Q
(2) (a
-- cxp ( n 1 (s, (s,a(2))
*k.4
where we use the following notations (superscript ((m) denotes the opponent of the m-th player.).
(m) (s, (m)) = E
Fa(m) Qu () 1) (1,2}
(9)
Qkatt (s, alm)) = Ea (1m) Qu (2) [ m (1,2).
(10)
4

---

Published as a conference paper at ICLR 2022
(2)) of the PU algorithm, we can obtain approxi- Once we obtain the output policy pair (Tk Tk
(1)
(2) (s)), which will be further used in the next Q-value function update (6) to replace (s'). The updates (6), (7) & (8) are referred to as policy extragradient (PE) algorithm.
mation of (s) as (s)) = fr (Qx(s) Th
(1) (s), *
In the PE algorithm, the PU update in (8) allows both players to take symmetric updates without revealing their private actions, and has been shown to converge to the unique solution of the entropy- regularized matrix game (7) exponentially fast (Cen et al., 2021). However, the PE algorithm has several limitations. First, in the PU update, each player m {1. 2} needs to query the quantities
Q (m) Qk.t (s,a a(m) from its opponent. To compute these quantities, the opponent needs to multiply the entire Q-table by its own policy vector. This requires both players to coordinate with each other and share Q-table. Second, the update of the Q-table in (6) requires full knowledge of the environment transition kernel P and the reward mapping R. which are unknown a priori in practice. To overcome these limitations, we develop a fully stochastic PE algorithm in the next subsection.
(m)
3.2 STOCHASTIC POLICY EXTRAGRADIENT ALGORITHM
The major challenge of the PE algorithm is computing the quantities Q QE.t and V44 which requires coordinating with the opponent and involves the environment information. Here, we develop model-free and fully stochastic variant of PE that estimates these key quantities using Markovian stochastic samples. We refer to this algorithm as stochastic policy extragradient (SPE).
Specifically, we first estimate the quantity (s) = (S)s Th (s), x (2) (s)). By definition of fr in (5) and the update of Qk in (6) (now we use (s((s') instead of Vs()") and using some standard tricks on random variables (see Lemma 2 in Appendix for full proof), we can rewrite V/ (s) as
E (R(3, ai)) ) ((3
V 2 (8)
(+( (s)) (((=((((s) (11)
(s)
where p4 (s) denotes the stationary state distribution associated with the policy pair (5 2 (2)). ). and the expectation is taken over ş ~ pk, ((1) mh
(s), =/)'(s),, a(2) Tf (s), s' P(- (()), 2(2)). To
estimate this quantity, we query a set N6+1 (with cardinality Nk+11) of samples from the Markoy decision process following the pair of policies (= Te (=))). Then, we estimate (s) as
(1)
(s) No+1 EieNut (R, + ( [8)
+ (H
(I(T (s) (12)
No41 EiENEn 1(s = =}}
Intuitively, we use the sample average of Markovian samples to estimate the expectation terms in (II). Thanks to the concentration phenomenon of dependent samples (Paulin, 2015), these sample averages converge to the desired expected values provided that the sample size is sufficiently large.
Next, we estimate @Lm)) characterization for both players E 1, (see Lemma 2 in Appendix B for the proof of equivalence).
1,2. Leveraging (9) and (6), we obtain the following equivalent
E (R(G, a0), ((2) + VV(('') = 76)) = amm))
(m)) (s, (m))
(13)
(s) (m)) (s()))ss)
where 11-} denotes the indicator function, 2 denotes the stationary state distribution associated me.)) and the expectation taken over Pk,t, 7(1) a(1) T (()((s),, (s),a(?)
with the policy pair (m()) (1)
The (s), ~ P(-15, a()) (,(())) To estimate this quantity, we query a set Ne.t (with cardinality Nx.:)
(2)
of samples from the Markov decision process following a pair of smoothed policies Tk, (s) =
((m)
(1 - c')=( (s) +
e' | 1, where c' E [0, 1] is a small smoothing constant that will be theoretically determined later. Then, we estimate (.T²) (s, (m)) as follows.
@lm)) (s, (m)) Ne. EiENe, (B, + ( 1)) s, s,a.m)) al))
(m)
(14)
(Nh, Eiere. 1{s s))=m(())) T (a(m)(s)
1m))
5

---

(1) (2) Published as a conference paper at ICLR 2022
where we have replaced the expectations with sample averages, and replaced Vi((') with Vs
(1) (22) Here, the Markovian samples are queried following the c'ssmoothed policies (Tk. TK,t On one hand, e' should not be too small so that it keeps the denominator of the above estimation away from zero. On the other hand, e' should be too large so that it is sufficiently close to the original policy.
Similarly, to estimate Q we query another set N,, (with cardinality Nx.e) of samples from the Markov decision process following a pair of smoothed policies The ((m)
(s) = (1 - -0='))n ET)T (s)+ 7'
(m))
1
where E' E [0, 1] will be theoretically determined later. Then, we estimate That as follows.
1 EiENE.. (R. + ( =s (m)) {m))
(m) Que (s, (m) Nu.
(15)
(,,,, Eier., 110; = 8)) T = ((m)) (a(m)]s)
Remark 1. The estimators (12), (14) & (15) essentially use ratio of sample averages to approximate ratio of expectations. Estimators with similar structure have been used in (Oriner and Auer, 2007; Xia et al., 2016; Wei et al., 2021). However, these works analyze the estimation ervor of their estimators with independence samples. As comparison, our analysis of the estimation ervor bounds the additional bias induced by the correlated Markovian samples, and achieves an improved sample complexity in the main Theorem 2.
We summarize our stochastic policy extragradient (SPE) algorithm in Algorithm 1. Specifically, in SPE, we estimate the quantities @(m)) ) V/ using their corresponding stochastic estimators. As a result, the SPE algorithm model-free, and the updates for both players are symmetric and private.
Algorithm Stochastic policy extragradient (SPE) for entropy-regularizeed Markov game Initialize: (s(s) for all E S. for value iterations h 0, 1....,
do Initialize T2,0 *ko with uniform distribution.
(2) (2)
for PU iterations t = 0, I....,Tk, T 1 do
Players 1,2 sample NE., Markovian samples following smoothed policies *k, "k,t
((1) ((2)
Every player m {1,2} computes @ (s, (m)) for all s, (m) using (14).
Players 1,2 sample Nx.e Markovian samples following smoothed policies k,, Tket"
((1) (2)
((m) Every player m {1,2) computes QR,t (s, (m)) for all (m)) using (15).
Implement the f-th PU iteration for all 8, (1)), (2) using (8) with estimations (15)&(15).
end
(m)
(m) (m) kTT m = 2. Players sample N₂ Markovian samples following Te : TT
Let TT
Compute Vx+1(s) for all s using (12).
end
Output: #K-1: K-1
FINITE-TIME CONVERGENCE ANALYSIS OF SPE
Throughout our convergence analysis, we adopt the following two standard assumptions.
Assumption 1. Denote (x (s, s') inf (t 1 8 = s'|so +) as the first-visit time under the policy pair x z(1), 7(2), We assume that
x2),
sup sup E Exo e 7()) (2)
[T to (s) < +00.
(16)
Assumption is widely used in the reinforcement learning literature (Ortner and Auer, 2007; Ortner, 2020; Wei et al., 2021; once within finite duration of time, thus ensuring that all the states will be visited infinitely often.
et al., 2021). ensures that every state will be visited at least

---

Published as a conference paper at ICLR 2022
This guarantees sufficient exploration. In analysis, use the following equivalent statement of Assumption for convenience, which means that the stationary state distribution (x0))x(2)) has a uniform lower bound jmmin > O. Their equivalence is based on Theorem 5.5.11 of (Durrett, 2019).
Amin == inf inf Px00) (0) = sup sup 10 (2)) ( Two x (5, s)) >
(17)
sES x(1) (1())
#ES x0)
Assumption 2. There exists a mixing time tmix E such that for any policy pair x1), x(()) and its corresponding stationary state distribution ((1) have
1
drv (Pat), (x (St (,00) a3
4
where P P=(1)==00 (5t) (st denotes the state distribution under the policy pair x0), (() at time tmko and drv denotes the total variation distance between two probability distributions.
In this subsection, we analyze the finite-time convergence of Algorithm for solving the entropy- regularized Markov game (5). We focus the convergence rate of the following Nash equilibrium duality gap, which is a standard optimality metric widely adopted in the existing literature (Xu et al., 2020; Jin and Sidford, 2021; Wei et al., 2021).
(TT (2)) max max (+) (, (s) min (2(T)
In particular, when r 0, D(0) (T (1), x (2)) corresponds to the duality gap of the original Markov game. Throughout, we define Amax == max (A Qmax := 1477 Am and Vmax =
1-7
14- in Amas, We also require that the batch sizes Algorithm satisfy the following conditions.
1-7
650lmix Amax
20T sum A1Amx)
NR. NA.
In
Ak,t,
(18)
Umin
8 Pmmn
650tmix
4
No+1
Vk:
(19)
Manin
8 V/Pmin"
Then, we obtain the following convergence result of Algorithm 1, where Tsum := E Tk.
Theorem 1 (Finite-time convergence rate). Apply Algorithm 1 to solve the entropy-regularize Markov game with E (0, 1]. Choose learning rate r) = [2(T + Qmax)]= initialization [| S Vinax and batch sizes Ny.e, k,,s N&+1 that satisfy (18) & (19). Then, the Nash equilibrium duality
gup converges at the following rate with probability at least 1 5.
1K-1: K-1) S 0 Vmax In Amax
K-1
(1) D (
(2)
K K=
177
1-7
k=
K-1
Tx-1
Vmax
tmm Amin
In
Trum S Amuas
2/3
K K-k-1 k
T2- (1- 2-t
1
Vmax
8pmin
2/2/3
22/3
7
k.t+1
max 7
tmix max
V-3
K|S|
K K-k-1
In
(20)
72 7)2
22mim (1
7)3
8pmin
N++1
k=0
Remark 2. In the proof of Theorem 1, we also prove that the convergence rate of the Q-function
estimation error ||Q - Q(=²) || (1 (1-7) times the convergence rate (20). Here, QK corresponds to the Q-function associated with the policy pair (# TT iteration, and QL corresponds to the optimal Q-function associated with the Nash equilibrium policy pair nuT n of the entropy- regullaiied Markov game.
(2) produced by Algorithm I in the K-th
Theorem 1 characterizes the convergence of duality gap of the SPE algorithm under general hy- perparameter scheduling of the batch sizes NR.t, NR,,, N&+1 and number of inner iterations T Specifically, it can seen that as the number of outer iterations K and inner iterations Tę increase, 2/3
the duality gap converges exponentially weighted average of K,t
2/3 NN-
k,t+1 and N=11 and the
7

---

Published as a conference paper at ICLR 2022
gap can be made arbitrarily small by choosing sufficiently large batch sizes. To provide intuitive understanding. we can set these typer--arameter as constants, i.e, Tj. = Nx. = N, Nu. = N, Nk+1 = N', and then the convergence rate in (20) simplifies to
r² 7)2 + MVaax In Amax (1 11-177 ---)))=-1_- P2pmin (1
V R
mmix V3
K K|S| 1
max
In
(1-7)²
7/3
6pumin N
V max
mmix Amax In
TTu [S) Amax
2/3
1
Viax
+
(21)
177(1 77)(( - 7)2 (4min
6fmmin
N2/3
TN2/3/
To elaborate, the first term characterizes the exponential convergence of the K outer value iterations. This convergence is faster than the sublinear convergence Of O( K/K) established in (Wei et al., 2021). The second term characterizes the exponential convergence of the T inner PU iterations.
Moreover, the last two terms characterize the estimation errors O(N-1) and ( + O(N 2/3) of the estimators (12) and (14, respectively. As comparison, Wei al. (2021) established a much larger estimation error ((N-1/5). These improvements, as we show in Theorem 2 later, lead to substantially improved overall sample complexity over the state-of-the--e art result. In particular, due to the exponentially weighted average structure in (20), the sample complexity can be further optimized by an adaptive scheduling of the batch sizes.
Technical Novelty. We further comment on the proof of Theorem Note that the analysis of the PE algorithm in (Cen et al., 2021) requires full knowledge of the environment and does not characterize the convergence of duality gap. As a comparison, to establish the duality gap convergence rate (20) of the model-free SPE, we need to make substantial new developments to tightly bound the estimation errors of the proposed stochastic estimators. We elaborate our technical contributions below.
As we explained in Remark the sample averages involved in our estimators are correlated Markovian samples. To bound the additional bias induced by these correlated samples, we apply the concentration inequalities developed in (Paulin, 2015) for dependent samples establish tight giggh-rrbbbblity estimation error bounds.
We develop much refined analysis of the state value function estimation error 1 Vi+ llo which is the key to develop tight bounds for all the other estimation errors. Specifically, we first propose the following error decomposition for any state
1s+
Uk+1 UK+1(S) (s)
(() 22 (
PM(s) (s)
[ (s) V
(5)
(+)== (+++
[0x+1(s)|
(s)
(s)
pe (5) (xx))))
where uk+1 (s), (s) are sample average estimators of uk+1 (8), ( respectively, and we refer to Appendix B for the definitions of these terms. The motivation is that the [Tx+1 (s) in the second term helps cancel out the estimator fi (s) in the denominator, and then all the denominators do not involve any sample average estimators, which may take a small numerical value that causes divergence and a loose concentration bound. By leveraging this special decomposition and the recursive structure of the stochastic estimator (12), we are able to establish the following key contraction property of the estimation error (see (85) in Appendix B).
[i - Vl S v - V + O(N
By telescoping the above contraction bound, we obtain tight estimation error bounds for all the proposed stochastic estimators. As comparison, Wei et al. (2021) directly applied the Azuma- Hoeffding inequality with independent samples to bound the entire estimator and obtain a loose error bound, and Liu et al. (2021) simply assumed small upper bound for the estimation error.
We develop a stochastic predictive update (SPU) algorithm with general inexact value function estimations and finite-time convergence analysis of its duality gap (see Lemma 1 for the SPU algorithm and its convergence proof). This generalizes the convergence result of the PU algorithm established in (Cen et al., 2021), which uses exact value functions based on full knowledge of the environment. Finally, by incorporating our developed tight estimation error bounds into the finite-time duality gap bound of SPU, we obtain the desired convergence rate in Theorem 1.
Based on Theorem we obtain the following sample complexity of SPE for achieving an e-Nash (2)
cquilibrium duality gap of the original Markov game, i.e., D(()) (T 1 TK < e. Here, we adopt an adaptive batch size scheduling scheme to optimize the complexity order. The overall sample
complexity is given by ΣK-1 [Ne+1 + +2 EEl----Ne + No.et))..
8

---

Published as a conference paper at ICLR 2022
Theorem 2 (Sample complexity). Implement Algorithm with vj = ( - 7),
-= O el e((-)))
0 1 In K
A ]
and Tk =++ Im(1-1r) Choose the following adaptive batch sizes.
kmm
((tmiall) Am
Emix
Nu.e - Nu,e (1 (1->)= -0("=mi Amax (1 175)
NR+1
2 @umini (1 - 7)8
Pminn (1 7)3
Then, for any C In Amax, the overall sample complexity to achieve D (1)
(2)
K- T K-1) I is
1-7
( Amax (1.6 (1-9)18..) Please refer to (118) in Appendix E for a complete expression.
The above complexity result is obtained by choosing a small T O <(1-2) for the convergence rate
In Amax
result in Theorem Specifically, we show in Lemma that the duality gap Lipschitz continuous with regard to the entropy regularization parameter, i.e., [x()((=(1) n 222)
D (=(((=())) . ((())] <
2r Amax
Therefore, by choosing a proper small т, convergence of the duality gap D of the
reguliy-re Markov game implies the convergence of the duality gap D(O) of the original Markov game.
Remark on Improvement of Sample Complexity. We elaborate on the improvement of sample complexity in two different levels: population level (with known environment) and stochastic level (using stochastic samples). First, the population level, the original policy extragradient (PE) algorithm in (Cen et al., 2021) already achieves faster convergence rate than the OGDA- algorithm proposed in (Wei et al., 2021). Specifically, to achieve an e-Nash equilibrium point of the original Markov game, PE requires O (1--)e In2 In + iterations by choosing a proper entropy
regularization parameter T ( c(1-)))
In Alax ). As a comparison, the OGDA-based algorithm requires iterations by substituting
[S) (1-7)²2
0 (no stochastic error) and their choice of step size into
the Theorem of Wei et al. (2021). This improvement is in the order of Õ(e=)) and is due to the use of entropy regularization in the PE algorithm, which improves the geometry of the bilinear matrix game. Second, the rest of the improvement of sample complexity (about ((c-1.5) comes from the stochastic level. Specifically, our stochastic PE (SPE) allows to use a large constant learning rate whereas the OGDA-based algorithm in (Wei et al., 2021) needs to use a substantially smaller learning rate 77 O (1)(11))'(8))))))
7 = 00
7), 7),,
which significantly slows down its convergence in both the population and stochastic levels. Moreover, both the PE and our SPE take (IIne inner updates to achieve an accurate solution of the matrix game (7), whereas the OGDA-based algorithm uses only one inner update to solve the matrix game and hence suffers from a larger optimization error. Finally, as we explained in the previous technical novelty paragraph, we improve the techniques used in bounding the estimation errors. Specifically, Wei et al. (2021) bounds the estimation errors in all the iterations by a small constant c using independent samples. As a comparison, we establish a key contraction property of the estimation error over the iterations with correlated Markovian samples. Such a property allows us to use a growing batch size that bounds the errors loosely in the initial iterations and achieves tight error bounds in the end.
CONCLUSION
In this paper, we developed a model-free, provably convergent, sample efficient, symmetric and private stochastic policy extra gradient algorithm for solving two-player zero-sum Markov games. Our algorithm leverages entropy regularization to facilitate the algorithm convergence and develops new stochastic estimators to accurately estimate the value functions. We proved that our SPE algorithm achieved a fast convergence rate in terms of the Nash equilibrium duality gap and moreover, achieves a substantially improved sample complexity over the state-of-the-al result. We believe our algorithm deepens the understanding of Markov games from a computation complexity perspective. In the future study, it is interesting to extend SPE algorithm to the multi-agent setting for solving general-sum Markov games and competitive games that involve multiple cooperative teams. Another interesting direction is to improve the algorithm to further reduce the sample complexity to approach the theoretical lower bound established in (Zhang et al., 2020).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The work of Ziyi Chen, Shaocong Ma and Yi Zhou was supported in part by U.S. National Science Foundation under the Grants CCF-2106216 and DMS-2134223.
REFERENCES
Bai, Y., Jin, C., and Yu, T. (2020). Near-optimal reinforcement learning with self-play. Proc. Advances in Neural Information Processing Systems (Neurips), 33.
Cen, S., Cheng, C.,, Chen, Y., Wei, Y., and Chi, Y. (2020). Fast global convergence of natural policy gradient methods with entropy regularization. ArXiv:2007.06558
Cen, S., Wei, Y., and Chi, Y. (2021). Fast policy extragradient methods for competitive games with entropy regularization. ArXiv:2105.1514
Daskalakis, C.,, Foster, D. J., and Golowich, N. (2020). Independent policy gradient methods for competitive reinforcement learning. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 33.
Deng, X., Li, Y., Mguni, D. H., Wang, J., and Yang. Y. (2021). On the complexity of computing markov perfect equilibrium in general-sum stochastic games. ArXiv:2109.01 100.:99999.
Durrett, R. (2019). Probability: theory and examples, volume 49. Cambridge university press.
Elie, R., Perolat, J., Laurière, M., Geist, M., and Pietquin, O. (2020). On the convergence of model free learning in mean field games. In Proc. the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 7143-7150.
Ernst, D., Geurts, P., and Wehenkel, L. (2005). Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556.
Fan, J., Wang, 7.,, Xie, Y., and Yang. 7. (2020). theoretical analysis of deep q-learning. In Proc. Learning for Dynamics and Control (L,DC), pages 486-489.
Farahmand, A.-M. and Ghavamzadeh, M. (2021). Pid accelerated value iteration algorithm. In Proc. International Conference Machine Learning (ICML), pages 3143-3153.
Geist, M., Scherrer, B., and Pietquin, O. (2019). A theory of regularized markov decision processes.
In Proc. International Conference on Machine Learning (ICML), pages 2160-2169.
Ghosh, M. K., Golui, S., Pal, C., and Pradhan, S. (2021). Zero-sum games for continuous-time markov decision processes with risk-sensitive average cost criterion. ArXiv:2109.08837
Gu, H., Guo, X., Wei, X., and Xu, R. (2021). Mean-field multi-agent reinforcement learning: A decentralized network approach. ArXiv:2108.027
Guo, H., Fu, Z., Yang. Z., and Wang. Z. (2021). Decentralized single-timescale actor-critic on zero-sum two-player stochastic games. In Proc. International Conference Machine Learning (ICML), pages 3899-3909.
Guo, X., Hu, A., Xu, R., and Zhang, J. (2019). Learning mean-field games. Proc. Advances in Neural Information Processing Systems (Neurips), 32:4966
Hu, J. and Wellman, M. P. (2003). Nash lelarnnng for general-sum stochastic games. Journal of machine learning research, 10Nov):103--106)
Huang, B., Lee, J. D., Wang, Z., and Yang. Z. (2021). Towards general function approximation in zero-sum markov games. 1177:22107.44702..
Jafarnia-Jahromi, M., Jain, R., and Nayyar, A. (2021). Learning zero-sum stochastic games with posterior sampling. ArXiv:2109.03396
Jin, Y. and Sidford, A. (2021). Towards tight bounds on the sample complexity of average-reward mdps In Proc. International Conference Machine Learning (ICMI),, pages 5055-5064.
10

---

Published as a conference paper at ICLR 2022
Kononen, V. and Oja, E. (2004). Asymmetric multiagent reinforcement learning in pricing ap- plications. In Proc. IEEE International Joint Conference on Neural Networks (IEEE Cat. No. 04CH37541), volume 2, pages 1097-1102.
Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. (2021). Global convergence of multi- agent policy gradient in markov potential games, ArXiv:2106.01966
Liu, B., Yang, Z., and Wang. Z. (2021). Policy optimization in zero-sum markov games: Fictitious self-play provably attains nash equilibria.
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020). On the global convergence rates of softmax policy gradient methods. In Proc. International Conference on Machine Learning (ICML), pages 6820-6829.
Mertikopoulos, and Sandholm, W. H. (2016). Learning games via reinforcement and regulariza- tion. Mathematics of Operations Research, 11(4::1297-1324
Moerland, T. M., Broekens, J., Plaat, A., and Jonker, C. M. (2018). A0c: Alpha zero in continuous action space. ArXiv:1805 /80,00613.
Neu, G., Jonsson, A., and Gómez, V. (2017). unified view of entropy-regularizee markov decision processes. ArXi::705..0799..
Ortner, P. and Auer, R. (2007). Logarithmic online regret bounds for undiscounted reinforcement learning. In Proc. Advances Neural Information Processing Systems (Neurips), volume 19, page 49.
Ortner, R. (2020). Regret bounds for reinforcement learning via markov chain concentration. Journal of Artificial Intelligence Research, 67:115-125
Paulin, D. (2015). Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20:1-32.
Savas, Y., Ahmadi, M., Tanaka, T., and Topeu, U. (2019). Entropy-regularrized stochastic games, In Proc. IEEE 58th Conference on Decision and Control (CDC), pages 5955-5962.
Shapley, L. S. (1953). Stochastic games. Proceedings of the national academy of sciences, 39910):0055-1100.
Sidford, A., Wang, M., Yang, L., and Ye, Y. (2020). Solving discounted stochastic two-player games with near-optimal time and sample complexity. In Proc. International Conference on Artificial Intelligence and Statisties (AISTATS), pages 2992-3002.
Silver, D., Schrittwieser, Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017). Mastering the game of go without human knowledge. nature, 550(7676):354-4 359.
Sutton, R. and Barto, G. (2018). Reinforcement learning: An introduction. MIT press.
Tamar, A., Wu, Y., Thomas, G., Levine, and Abbeel, (2016). Value iteration networks, In Proc. Advances in neural information processing systems (Neurips), pages 2154-2162.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R., Ewalds, T., Georgiev, P., al. (2019). Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782):3003355
Wang, X. and Sandholm, T. (2002). Reinforcement learning to play optimal nash equilibrium in team markov games. volume 15, pages 1603-1610.
Wei, Y., Hong, Y.-T., and Lu, C.-J. (2017). Online reinforcement learning in stochastic games. In Proc. Advances in neural information processing systems (Neurips), pages 4994-5004
Wei. C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021). Last-iterate convergence of decentralized op- timistic gradient descent/ascent in infiiteehhoizonn competitive markov games. Proc. Conference Learning Theory (CO1.T).
11

---

Published as a conference paper at ICLR 2022
Xia, Y., Ding, W., Zhang, X.-D., Yu, N., and Qin, T. (2016). Budgeted bandit problems with continuous random costs. In Proc. Asian conference on machine learning (ACML), pages 317-332.
Xu, Y., Deng, Z., Wang, M., Xu, W., So, A. M.-C,, and Cui, S. (2020). Voting-based multiagent reinforcement learning for intelligent iot. IEEE Internet of Things Journal, 8(4):268
Zhang, K., Kakade, S., Basar, T., and Yang, (2020). Model-based multi-agent in zero-sum markov games with near-optimal sample complexity. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 33.
Zhang. K., Yang, Z., Liu, H., Zhang, T., and Basar, T. (2021). Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents. IEEE Transactions on Automatic Control.
Zhang, X., Zhang, K., Michling, E., and Basar, T. (2019). Non-cooperative inverse reinforcement learning. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 32, pages 9487-9497.
Zhao, Y., Tian, Y., Lee, J. D., and Du, S. S. (2021). Provably efficient policy gradient methods for two-player zero-sum markov games. ArXiv:2102.0890)
Zhu, Y. and Zhao, D. (2020). Online minimax q network learning for two-player zero-sum markoy games. IEEE Transactions Neural Networks and Learning Systems.
Zou, S., Xu, T., and Liang, Y. (2019). Finite-sample analysis for sarsa and q-learning with linear function approximation. ArXiv:1902.02244
12

---

Published as a conference paper at ICLR 2022
Appendix
Table of Contents
Analysis of stochastic (SPU) for eatropy-regularized matrix game
B Estimation error bounds
18
C Properties of the Duality Gap
25
D Proof of Theorem 1
27
E Proof of Theorem 2
31
F Summary of Comparison of Sample Complexities
34
G Rationality
35
A ANALYSIS OF STOCHASTIC PU (SPU) FOR ENTROPY-REGULARIZED MATRIX GAME
We first consider the following zero-sum entropy regularized matrix game, which can be considered as simple special case of Markov game with only one state.
max min hr (14 2) = 1 Qu-QU - TH(U) -H()). (EA(d)) (E)(
(22)
where Q IRd xd is fixed. The solution (²) of the above problem, also known as the quantal response equilibrium (QRE), satisfies the following condition (Cen al., 2021)
1 xcxp(QU(/TT) & exp(-Q' P²/T).
(23)
Our stochastic PU (SPU) algorithm for the above matrix game written as follows,
(a) (xte(a)
(- 1-nr exp (nl Qu, o0 1.)
(24)
Be+1(b) (b) xu (b) - exp (- n(QT nt o(²1),) (a+ (a) --タp exp (n (u,+1 + +
(25)
(26)
(b) (b)) exp ( (- n[Q Fe41 + 7.22) ln)
(27)
where 5(1) is an additive noise to the underlying true quantity Qu, and the other noises ((2)
7(1)
x(2) are similar. all these noises are zero, the above stochastic PU algorithm reduces to the PU algorithm for matrix game defined in Section 2 of (Cen al., 2021).
The convergence rate stochastic PU for matrix game shown below. The proof logic follows from that of (Cen et al., 2021).
Lemma 1. Choose learning rate S [2(T +[ and use the uniform policy initialization (4g = 1/d1, No = 1/dz. Then, the SPU algorithm defined by eqs. (24)-277) for entropy-regularized matrix game has the following convergence rates.
K (L(pEllue) (L(()()))
< (11 (
13

---

Published as a conference paper at ICLR 2022
1-1
+ Σ (1 n7) 1-1 2n/ (106) + 12)) + 24 11
(2)
1 +
=10g/ 12e)
(28)
1=0
(1 v7) , ((+1)l
$ 1
(1 In))d))
+
Σ (1 ) 11- (81(10) + +110,00130 126) + 47
33
(10)))
1 + 10 1200 11,)
(29)
1=0
max h (1, F(+1) - min hr (T)+ (Ed(d1)
rEA(ds)
2
< (1 n7)) l2(d
+ Σ (1 )-) [66 12c + 118))912)) + - (10,5112 11. + 110)
12
(30)
j=0
Proof. Eq. (26) implies that for some constant e. TR,
In p++1 (1 -/)r In + nQu++1 ((1)) + cl
( In Me+1 (1 17) In Hr 71Q 0/ ), Fet1 -+2) = 0. where we used (Te411 - pr; 1) 0. Similarly, eqs. (27)&(23) respectively imply that (Inv++1 - (1 17) lu + nQ F + 0, ) F/+1 - 1/-) =0 ( (In QQ / T, Fl+11 - (G/ =0 Inv + Q 10//t/T TT,11111111110 -V²) -0.
(31)
(32)
(33)
(34)
Similarly, eqs. (24)&(26) imply that
(In(M4+1/ He+1 - 1441)
= (m1[0( - Fe41) 8. 5(111 F Mot1)
I <1101l 1117 Metallalle Fetill1 1|11=1100 + v/(o!²)
-6 1100 7 M141112
(())
< 1101 1100) 11 |lu 1(t1l1)) 2(1 0110)
17
10(
5((1)
11:
1 ( -
+
Pet1ll
(9 2 K KT(pet11/Tz nll KT 2n (1665)) 183 +
12.))
(35)
where uses the Pinsker's inequality and 2(( [[Q11=>)]
Similarly to the above derivation, we can infer from eqs. (25)&(27) that
(In(Fc+1/M411) P++1 M141) SKL(p 12+1) + L
+ 2n (116 + 10! 1120)
(36)
Computing eq. (31)teq, (32)-1r(eq. (33)+eq. (34) yields that
n .1441 - /1)) 5(()) F - v;;) =(Iupe+) - (1 - 17) In μ4 リp ln μ4 - Q -V7), Flet1 - -1/) +(Inv1+1 -(1 (1-177) (1
177,F
+QQ (Th+11 1,), vz))
=(In(pe+1/n()) - (001 vr))
14

---

Published as a conference paper at ICLR 2022
+ (In(ur1///) /v,) (1 1--m11 //f), -if)
-K (1 >
+ + (In(F /// - -In(7<+1//et1)> (1- (n In(7(+1/He) /mli Pltt)
+ KL (2+1) - (1 -7T)/((((()
+ + (In(Pe+1/V) -1
- In(Pr+1/ po+1)
=KI - - (a + 1
+ (1 - KT (100://||lll)++KKK/eeeeell......
+
1pr (T
+ + [1--))))1L1111111)))<-4444444444
-1 | Do+1 - Mt+1)
2 (1(G)11)))) ạ)) (.
(114) 1T (1(]) + ( l1
*K((++lu++) - (1- 177 L + ( [1+]+ + (1-nn-nllQll>>> (Pe+1
2172 + +116," 1 + 11 + 110 12a):
(37)
where (i) uses eqs. (35)&(36) The left side of the above inequality has the following upper bound.
(5( (1)
T mG)) (5, (2)
D2+1 v;)
<nl
0
100
[1++1 - 11111 + +, =1 |100| - -łlli
2110
113e
+ T
2110, (2)
112
+ - || 1 -v71l)
2
2
(10)) 1)
113
TTT
[ ( KT(E(+1lll)))
(38)
2
Substituting eq. (38) into eq. (37) and rearranging it yields that
KL KL + (L(v) + 1/7 2
[KL 1lG)) + KL(V++1lPG)]
+ 2 K KL (1 + + K
$ m7) (MC (1)) + K (L( + 2n7² (11 123 + 110)
+ (10,
21 (1)
1
1| ",tt">13, 112):
(39)
where we use 77 [2(T |1Q|| - (2r)-1. This further implies that
KL + KL(W
$ (1 - 17) ( (1 + KL(()(())
+ 2n7² (1o5 + 112)) + 2n (11, 12
12 + -1.
(40)
Consequently, eq. (28) can be proved via iterating the above inequality and using the facts that LL(pEll))) I In d1, K L (1)) & In (Since Mu and 2/y are uniform probability vectors).
Next, we will prove (29).
Computing eq. (31) eq. (33) yields that (Q(7++1 n2),, Tle+1 11;) = -1 (In M211 (1 - 17)) In 17 In =(1) Pe+1 -,7)
(41)
Hence, we conclude that
hr (Fr411 P++1) - 70- 0,,,, v.7) h h (144411 Me+1) hr 1,(4+111 U7)
15

---

Published as a conference paper at ICLR 2022
F441 Q(1141 - v2) + -1,)
TV/11 In 11411 TV, Inv;
(T - ( Q(7(+1 - 1/²) + P Q - -V²) + TD In 1 TV. Inv;
M4+1 - (1 -1) In Mr lpr In nr; - 1101 (3)
11 (en TP/41 In TMē I
T141 14;) T( In 12, Pe+1 vt)
( "/ (KL(llllee))) - (1 - LL) + (L + (1 - 175) K KLLL(1 (
- 106") ,1++1 - 14)
+ 117
<1 - -1-111111111
(1, + (L(+++++ll
+ (1-1)7) ( - KL -KL +
1
06
(1)
11:0
+
5 11411 1771
2r
2
(00)
3 7 1 (KL(A])l(() + (K
KL (K( +
+ - 11, 10 12
1
4T
(0)
+ +KGUG))))+++ (16 + 11a) + 27 (10b
(1) 123 + 11, (1x)
41
1
10
4T
(0)
- 4n 1 [KL + [[(111b
+ ( 18o + 116,2) (1x)) + 33
4T (15,
(1)
12
+ 13
(2)
1
(42)
where (i) uses eq. (41)& (ii) follows the derivation of eq. (37), (iii) uses the Pinsker's 's inequality, (iv) uses eq. (39), and (v) uses 1) S [2(r + [1Q1lcc)] -1 In similar way, we can also prove that
h h,(",, u²) hr (1 M(+1) < h- ( ve+1) - h- (Fr+1. Mt+1)
4n [KL (m,)) KL (v
+8 (11( 1o + 12x)) + 33
47 (10,
1
1130 +
+10, (1))))))
(43)
Combining eqs. (42)&(43) yields that 1 v/) - (T 1e+1)]
$ -1 [KI(NI])u)) + [ KL(H]]))) + 81100 + 12)) +
33
(13
(1) 113 + 1: 11=))
4T
(1)
3 4n (11 - (1-1))) l2(2
1-1
Σ (1 - mT) 11- S7 (n6 12. + (11f9(12)) + (105)) 1130 +
+
1=0
+ +80(11))) 1118)1112 11:0 + 11)
33
47 (1o (1)
12 + 10, 12))
+
< -1 - )- d2()
t
Σ (1 - S
( (1661600
+ +1655) (2=) +
33
(15)
113 + 11))
4T
j=0
where (i) uses eq. (28). This proves eq. (29).
Next, to prove the duality gap (30), we first derive an upper bound of K KL ([TT )) + (I(
KL(rtIPP++1 = -KL(V(]/e+2)) - KKL(T4zilPet)) + (Ve41 - V1,In1441 - In in
<KL(I/]/ee1)) + (Be+1 - -2,,00 (Tr+1 ma) + m6( - -b(2))
<KT(U;]IuAt1) + || - -Rall: (1]lQ - melli
+ -Meli
((2) 11=0)
16

---

Published as a conference paper at ICLR 2022
< <KI(v]l(ett))
+ 1 + +4) [11l0110
- + 11 - milli + 1,, - -6,² 11.]
2
kL(vt|lutta) 3 (K((+\(0(+a) + ) KL (1m) )
4n7 (16 1 ا 1bx.)
(44)
where (i) uses the Pinker's inequality and r) S [2(T + [1Q yields that
Rearranging the above inequality
2KL 2K 1617 (60 (1
+ 10.))
(45)
Similarly, we can prove that
( (4Kl(tt))))s) 2KL(D(41)M) +
+ =1o, 11xe) 1677 2K(())=ll)++16)(((((
(46)
Summing up eqs. (45)&(46) yields that
KT 11++1) + KT (T(((lpt)))
I 4 [KL(N | [1+11 + KK( 2 (T +
+ 16n (106) 10,," 1) 1 (16!2)12 1
(
- [[LL(E [4) + (b( + 24n (1165") 12 + 12.)
(10, + 16n (1) 113o + 13 (2) 11z0).
(47)
where (i) uses eq. (39) and - [(( + [1 S (27)-1.
Finally, we prove the duality gap bound (30).
hy (nG, v2) hr (1, (u, 11) T Qu? + Tp In - TH T In p.
T((μ - M1, In (&)) + p In - n,, T kn ( [L(llln))
(48)
where (i) uses eq. (33).
h (, - hr (1)
= 0(Te+1111 - v1 + T 7 TV," TT In
(H- -m-- (TTT)(/())T))))) Q(T(++++11111 -1²) +
μリ T
Q2 -1+) + TD In74+1 Tu;" In
S ||p 1 n1; 11 |744
vイ ||1 - 7( In v,, 7141 - n² + NŪ. In - TV, In;;
1
1/ |T||K- || + -
111/7]
T K [((()()))) + LK +|+))
+ - K [b
(49)
where (i) uses eq. (34) and (ii) uses the Pinsker's inequality. Then, eq. (49) & eq. (48) imply that
hr h (ut,, S STKL( + 11 K LL
(50)
where (i) uses eq. (45), (ii) uses the Pinker's inequality and 1) < [2(7 + 11Q1 Similarly, it can be proved that
ht (pt, ",) lrr (T+41 v) S
K KL
(51)
Therefore, the duality gap (30) can be proved as follows.
max hr (1, min h (7) vEA(dz) (1, - hr (Ma-1: v)]
HEA(d1)
max (EA(()))EE((d))
17

---

Published as a conference paper at ICLR 2022
-[KL(T--lll))) + (10606200||||+++000++/+++1)+++11 (
+ (L(T(((e+t)
(6)
+|KT(1441ll))) +KK/0/+41||(+++K(((4++)1++))++++ 11
4 4[KT((]))))) + ( +ttp:l/))))+2//(111111 21407(110") + 110))0122) + 167 (10; (1)
1 + 12:)
(682)
2 4112122
max
n
T
(166 11=- + +11, 113)] + 21 (16!"1 123 + -0(²1 ((0)
( + 22
+ +1Q12 24n 110 + [1x) + 167
T (10, 11 1 + _ [P:]]
+
(10)
2 (11 11-mmy (
17
1-1
+ (1 1-3 22/ [ (100")11 + +110f=113c) ((x) + 2n (10 11:0 + +10,g1 12]) 1))))
1=
+ (6 + 112) + 12 (10 "1"5"112 1|20 + +1b0, -11,,"120)
2 (1 np) (2(d)2))
<
"
+ > (1-nn)----1 (677 12 + +10)9112)) + 12 5 (105)) 12: + (8.""112))
(52)
1=0
where (i) adds up eqs. (50) & (51), (ii) uses eq. (47), (iii) uses eq. (39), and (iv) uses eq. (28) and
4T -IQ11 s 2/n (since 7 I [2(T + [[]]==]]]] , 7 S 1). This proves eq. (30)
B ESTIMATION ERROR BOUNDS
(m)
In this section, we derive error bounds for the estimators Vi+1 = Vi+1, Øim) = Q(m) used in Algorithm 1. For convenience, we define the following additional notations.
Qua
=
=Q
(s)
1
Σ
1ss = 5} ~ (s))
(53)
No+1
sEA4+1
(s) == E
[ ((())) + VV
1/3= st]
(54)
(1)
2/4 (s) = E
[R(3,at), (()) Vi((''] 1 st}
(55)
(1)
(2)
1
[RA+ 1 ( 1 (5,= = =s} ~ r1))2(s) ss vs))
0k+1(8) = No+1 iEN++1
(56)
Qk (0 == R(s, (1)) (2)) + 1
[V](s']
(57)
(s) = (r(( T (s), T (s) = (s))(s)
(5), (2)
(s(s) + TH (TT²²) (s) - -T(( (s))
(58)
(E+)(s)= = (8)
7 +T((T(T (s)) - -T((T
(2) (s) ~ (s)
(59)
(s)
(s),(s): == 1 Σ
1(s = 22 (5) ps))(s),
(60)
Nu. seNo.
((m) (m)) E
(1)
[ (00) + +V s, am)) = a mm)
(61)
Ghet (s, a (m))
:= E
(1) (2) [R(5, (1) ) + v s, a(m) mm)]
(62)
My +
18

---

Published as a conference paper at ICLR 2022
The (s,al (e
Σ
[ [Rs + ( =s,a,") )
Nua iENi.
= 9x.t (s, a (mm)) = the (s. (s, (m))
(m))
(63)
(mm) (s, a(m)
Q (s, (m)) E am (s)
(s) (u ,c))]]
(64)
W (s) (im)
(a(m))s)
Thit (m))
@laml (s, (s,a(m)) amm))==
Q (s, (0, (m)) x (s, (s,a(mm) (m))
(65)
(s) (m) (a(m)|s)
where eqs. (53)-(59) and (60)-(65) are introduced for the description and error bound proof of the estimations V8+1 R Vi++1 and @(m) ss Qim)) respectively. Specifically, eq. (53) estimates
the stationary state distribution μı associated with the policy pair Th T
(1) (2) using state frequency
(8). In eqs. (54)&(55), the expectation is taken over 8 ~ jkx a(2) Tk (2) a!2) ~ T (2) (s), P(-3, a.2)). The definition of E " "N.
(2)) in eqs. (61)&(62) is similar. Equations (58)
& (64) give two equivalent definitions of k+1 and Q'ir" (s,alm)) respectively 1 (We will prove the equivalence in Lemma 2 below). Equation (60) estimates the stationary state distribution pk,t (() (2)
associated with the smoothed policy pair The "k,t" and thus approximates the stationary state
(1) (2) distribution uk associated with the current policy pair Th, "k,e"
To prove the estimation error bounds, first prove the following two lemmas.
Lemma 2. Eq. (13) and the second "=" of eqs. (58) & (64) hold for all a2)) (2))
Proof. The second "=" of eq. (64) under m = can be proved as follows.
Te.t (s,
(1)
(
Hk (2) [R a 20))))))))))))))) + > s, s, = mm(m)
(0)3 x(م)
[R(s, (00))
V 1 ((1)) = a d1)
110
|| =; = a
Bay ((ll) R(( (1)) ((()) [/(('']
(Q((s, (0)
(s) 01 ())
where (i) uses eq. (61) which denotes E (1) as expectation over 3 ~ u 7(1) He me
Tktt (3).
1(1)
a(2) ~ Thtt (3), ~ P(- P(- ((()),, (ii) uses independence between
Mlae: 701) The (s)
(2) and ((22) ~ Tht (s), 5' ~ P(. (2), a, (iii) uses eq. (57), and (iv) uses the first definition of eq. (64). The second "=" of eq. (64) under m = 2 and eq. (13) can be proved in a similar way.
The second "=" of eq. (58) can be proved as follows.
(s)
(K)
(1) (2))) ( ((2)) + 7V(('')) 113 = =s}
E B (1) (z) (s) ,(e (R(s,a"),500) + 7V(66)]1f3= st
'The definition after the second "=" of eq. (58) is the same eq. (11)
19

---

Published as a conference paper at ICLR 2022
(18)
[1
"lls,,a,,,0 + [Vi((s)]
(826)
(F T (5), QQ [(2))]
TH( (TT (5) 7H (s)
(1)) pa((s) [i (s) - -H T (8) + (H(TT (s))
where (i) uses eq. (54), (ii) uses independence between s' ~ p and a(a) Th (s), a(2)
(2) K (s), s P(-ls, " a. (iii) uses eq. (57), and (iv) uses eq. (58).
Lemma 3. V/lVole I Vmax 1 In Amax, then for all ls 0.
we have
1-y
V VVVille, || S Viax:
(66)
( & 2V (s), Vs E S,
(67)
max (112 11 |o (10"1(cc) - Qmax:
(68)
where Qmax == + Vaax
1+gr Amax with Amax == max (14())),1A()))) 1-y
Proof. We will first prove liVello I max in eq. (66) by induction. Suppose || | Ioc S Vmaax holds for a certain & N. Then, eq. (59) implies that for all s E S.
((s) (T) (TT (s)
[v+a(s)]
S
E EiENee1
[|a + > 7/ (s++1))) 1(s: = [}
+ T In Amax
ΣiEN 1fs: = =}
(0) EieNum
+ 7Vmax) 1881 =
+ In Amax
EieNar 1(9; =s}
7(1 + In Amax) =14
+ Amax Vmax,
(69)
1 1-7
where (i) uses the inequality that 0 S H(( < In [(m)) < In Amax, (m()) A(IA(m)). Since
Volloc I Vmaxx |/Ve I Vmax for all & E N. A similar induction yields that || b0 S Vmmx-
Vmax. || S Qmax in eqs. (66) & (68) respectively. Notice that V* and Q* have the following relation.
Next, we prove || S
(1) (" (a()) = R(s, (1) el)) + 7E, -E. V*('',
(2) + + -[H( H(x (s))) Q2 (s) (s)
Hence,
||0 <1+>|V ||
(70)
| - 1|Q ol + T In Amax
(71)
Substituting eq. (70) into eq. (71) yields that
|x I 11+ V 7 In Amax 1| V
The proof of eq. (66) is finished. Then, substituting ||V* S Vinx into eq. (70) proves that ||Q^ 11 S Qmax-
Equation (67) can be proved as follows.
(8) (1) Vi + + (=)(=((())) H()m S Vinax + T In A 2V
(18)
(s)
20

---

Published as a conference paper at ICLR 2022
where (i) uses eq. (58) and (ii) uses Viaax
14.r In Amax
In Amax.
1-7
Next, we prove eq. (68). It can be easily seen from eqs. (57) & (66) that
( < R(sss, aa 1), a())) PlB (0 Vi((')) 21 VVnax Qmax+
which implies that ||Q+1l>> I Qmax. Hence,
( 1 a )l S E A (m)) (0) ( , S Qmax
where uses eq. (64). This proves eq. (68).
With the above two Lemmas, we can derive the estimation error bounds as follows.
Lemma 4, Use hyperparameter choices NE. NA. 2
000 In (20T AS/Amax and No-1 2 à //ain
Paniu
650
(1-7)" In 6 in Algorithm 1. Then with probability at least 8, all the following
bounds hold for all 0 k KKK- 1 To - 1,2, E S, alm) E A where RK-
Tawm
Ek= Tk-
16 Vill S 2V mmm
171 max
Imix
In
SK|S|
(72)
1 1-7
N
8 V/min
(mm) 11
6400mi:
20T Sum Am
tmix
20T sum S|Amax
S <max
In
+ 25
+ e'
Nk
5% Mmmin
Ne
8 //min
+ 2 V2
Villoo
(73)
1
(m)
(m))
11
6400tmis
20T sum Am|x
tmir Amir
20T num Amax
$ <mmax
+ 25
In
+
N Na.tMmiie
d~ M/min
N Ne.eHmiie
6. Pmin
+ 22 Villos
(74)
More specifically, the upper bounds (73)&(74) can be simplified respectively follows when e' =
1/3
1/3
Amax In Na.emmin
220/ (S) Amacx
and E'
630tm
In
20T Amax &
N Ne.ekmin
10mm
-O(on) 11.0
$18Q max
Umix Amax
20T sum [S|Amax
11100
1/3
+ + -Vill 00
(75)
Nk.eMminn
///mmu
(m) - - $18Qmac
AmaxxAuax
20T pm ||Auax
1/3
Qu,
In
- -21 - Villao (76)
N Nk.t/min
P/mla
Proof. If the initial state distribution of the minibatch NK. equals Uleer ie., sk,000 Me.
afm) (s, a (m)) ΣieN,, 9(s;, al", ,ff),,s44)) s141 (g(s;, a(") aa( (141) [R, then Ne
>V((sHt)] (s; 8, a (m) a (m))) and its expectated value Ne. (m)) (s, (m)) satisfy the fol- lowing concentration bound.
<(m) P N (s, (m)) - Nx (s, (m)) 2 u}
((m))
(m))
(6)
2² u2yppa
< 2exp
8(NK, + 1/7ma) Pr P (6) (mm) (a(()))) + 40mQQuQu max
(6)
u² m2/(22mmis)
S 2 2exp
(77)
(a(m)]s) (s) + 4440QuQu.. max 8(NK.t + 21 Q ($) (s) ((m)
21

---

Published as a conference paper at ICLR 2022
where Pag. is under the initial state distribution 14,,, (i) uses Theorem 3.4 of (Paulin, 2015) and the inequalities that [g(s;, at" af s141) Esrwi, g(s, of at?) si+1)l S 2(1
y Vmax) = 2@max (Based on Lemma 3) and that vars [9(8;, oj (1) (1+11]] S
Besmiter [R. + +V]((s (s; s. s.a = amm))] I (1 (1++Vmmx)) p4, (s)
(mm) (a(m)
max ( (s) ((m) [s). (ii) uses Proposition 3.4 of (Paulin, 2015) which states that the pseudo spectral gap Tps has a lower bound m2(x for any uniformly ergodic Markov chain (This condition holds for our MDP with finitely many states and actions). Then, for any initial state distribution $1,k,0 Ç, Proposition 3.10 of (Paulin, 2015) implies that
Pe( 1k. (m))
(s, (m)) 19. ((m)) (s, a (m))) 2 u}
{(s)
((m) PAE. Na, ((m) (m))())) NN, (s, alm)) 2 u}
E
(1)
(8)
u² u²/ (4tmmix)
exp
(78)
Mmin
8(NK, + mis ) ( (s)
(mm) (a(m))s) + 4004Q0uu max
where (i) uses eq. (77) and the inequality that Bengg
{(a)
(s)
Amin
In a similar way, the following concentration bound can be proved for N = EieNa. 1fs, s} and NR.t = Eug.
(N [N
I exp 8(Nu. + 2/ ) + 40u.
u² (4tmnis)
Pe ( Neath, 2 u} S V Mmin
(79)
where we use the inequalities that varpé, 1(8 =8 S e (8) and that [1{s; = =}} Eyg. 1
}}} < 1. Letting the right hand sides of eqs. (78)&(79) be upper bounded by 6/4 and applying the union bound yields that, with probability at least 1 --8 8//2 the following two inequalities simultaneously hold.
(f(m)) (s, a!m)
- Okit (s, (m))
/(ma))
160Q mmix tmix In /
NR.1
6Qmax
tanix (1 + 2t /tmx//Nk.)) /Nk.) (s) (m)) (mm) (a(m)|s) In
4
(80)
/ /Nu.t
8 //min
(s))(s)
(s)
160
tmix In
NR.t
8 Mimin
(
4
Lmix (1 + 2mmix/ (e
o o
(81)
V /Nke
where (i) holds since No.t
650Hmt Amax
In 20/T SS Amaxx b/Pmm
650tmix and (s) 2 pmin.
Pmiin
Similarly, can be proved that the following two inequalities holds with probability at least 8/2.
(0)) u/ (s)]
< 160Qmax mmix In (7/ T
6Qmax
mmix (1 + 21 (imxx/No41)uole ( /
+
(82)
No+1
Nk+1
[s) - -Mx(s)
< No+1 Imix In (5 /
160
6
4
+
bmix + 20 /Na+ (u (s) In
(83)
VN++1
22

---

Published as a conference paper at ICLR 2022
Hence, eqs. (80)-(83) hold with probability at least 8. In this case, we have that (s+1(s) 1*)]
< (0)+1(8) u + (0)+1(() - 1x+1(s)
160Q tmxx In (
4
6Q 00uax
4
Emix (1 + 2f / /Nk (Nx))) In
(
N++1
( /8/Mmin VN
/
+ ylR
(2) M
(Va(t') -V(6')
160Q
+ 6Qmax
4
No+1 mix In
tmix + 2tmix O (s) In
8 /
/N++1
0 /
+ y max [2()))
Vi(s')
1(3 ss
160Q max
No+1 mix In (
5 / )
+ 6Qmax max
/mix (1 + 2lmix/Na- (s)) (
4 ( 6
+ + [ Villoo
(84)
where (i) uses eqs. (54), (55) & (82).
k+1 (8) (s)]
(s) (8)
(s) (s(s)
Ma(()) - (s(s)
< Mx (8))0041(5)) uk+ 1 (5)+1(()]
(N)
(8)
160Q tmix In
4
6Qmax
4 / Mumin
I M4 (s)
tmix (1 + 2t / NN (ps(s) In
Nu+1
V/mmn
/N++1
160
4
[ Villo0) + 2V Vmax/4
(s)
tmix In
Nx+1
8 Ammin
6
4
Emixx (1 2t / /Ne+ (N+)) In
(
Net11
(112)
Vmax
m80t
4
V Villoo +
In
pa (s)
Nk+1
(m))
+ 18
(1 2lmix/ 2lmix/Nx+11 In
NL+1
(iv)
40fmix
1.05l In
2//V2 VVlloo + Vmax
24
In
+ 18
N k+ 11mmn
M'min
N1+1pmin / Umin
(0)
400mix
4
1.05lmix
S V Villoo + Vinxx
V
In
18
In
Nkt1/4min
Nat1/Amin
tmix
S <>11B Villo + 171V Viax
Nk+1 In //Pimn
(85)
where (i) uses cqs. (58)&(59), (ii) uses eqs. (67), (83)&(84), (ii) uses Qmax S Vinax (iv) uses
(s((s) 2 Amin and N 2 40tmi In 6yPmt 40tmix and (v) uses No+1 2 40tnis In (
Parto
pmin
Applying the union bound to the above inequality over all S S K 1, 8 S and taking maximum over E S, we obtain that with probability at least 1 - 6.
tmix Nkt1pmin
|| 1 Vitalloo 5>1lV - Villoo + 171V max
In
8 M/min
23

---

Published as a conference paper at ICLR 2022
Iterating the above inequality yields that with probability at least 1 - 8,
VIVe Villoo S Villo + 171V max
Lmix
4K S
In
1-7 7
Wk+1Muinn
8 /V/Mmin
171V
fmix
4K|S|
2V m 1
In
(86)
V/Pmin
where (i) uses the fact that V oc; 1VVo Vmmx-
Hence, with probability at least 20, eqs. (80), (81) & (86) hold simultaneously. this case,
(m)) Th,t (s, (m))
Ok.t (s, (m))
(m))
@ (s, (m)) - 2/. (s, amm))
(
(s),(s))
((m) ( (a(m)(s) (1,,(5)) (1m) (a(m) ss)
(60) ((mm) (s, alm)) - That (s, alm)))
(s) ((m)) (a(m))s) (s)
(x,c(s)) - (+)
+ 11 (/r)) (al ((m) (s, (ml))
((m)) (a(m)
(118) 2 2/ (s, a(m)) ((m) (s, (m))) + (k,t (s, a (m)) Uh.t (
(8, a (m)))
())
(a(m)))) (a(m)]s)
(m))
2Qmax (x,:))) - (M)
(1))(()
(Kv)
20max
320
4 8 /
tmix In
1/,, (8) (5)=
(m)) (almn)ss) (s)
Nk.t
12
/mixx (1 + 2tmix Naeix/Nee))ddl (N, (8) (mm) (alm))s)ll
4 (
+2
Vill
V No,
640tmix Amax In ( ( + 1
tmix Amax Nec.llmine
4 V/min
Q max
In
+2
Villoe
Na.tlmint
(87)
where (i) uses eqs. (64)&((65), (ii) uses eq. (64), (iii) uses eq. (68) and the inequality that (s) > " (s)/2 implied by (i) of eq. (81), (iv) uses eqs. (81)&(81) and the following inequality based
on eqs. (61)&(62), and (v) uses (s) 2 Mmin (based on Assumption 1), T (m))(a (a(m) = (1
cd (m))
(m(m))s) (a) c' (m/) 2 c/Amax and NN, 2 650tmii-
(m)) 1kkt (s,a(m)) Test (s, (s,aa (m)))]
[A((')) (1(5))/(33=s, = {m))
I TB Me Me
101) the
(m)) $ (s) Tk. (s, (s.a(m)) (m)) || Vall
Notice that the following incquality always holds.
(m)) ket
(s, (m)) - ( (s, a (m))
Qa(s, a (2) a | 1 (m1)) (a (a(mm)ss)
TRe (a((m)))) [s)
(1m)
a(mm)
2
Q maaxe
Thet
(1m) (a (mm))))s) - ( S Qmaxe',
(88)
where (i) uses eq. (68).
24

---

Published as a conference paper at ICLR 2022
Hence, combining eqs. (87)&(88), it can be seen that with probability at least 26, the following inequality holds
Qhape (s,a(
Quee (s, amm))]
6400 Amax In
4 ( /
Umix Amax In Na.tllmine
S max
V
+
Ne.ePemine
+ 2 -Villoo
(89)
Similarly, it can be proved that with probability least 25,
Que (s, (m))) - -Q 2 (s, alm))
(m)
6400 In
( W/Himn
Imix Amax In
( 8
$ Qmax
V
Ne.ePunin
Nx.ePrine
+ + V/.
-Vill
(90)
Finally, eqs. (72)-(74) are proved by applying a union bound to eq. (86) and eqs. (89)&(90) over all k T 1,0 1 T 1, m 1,2, s E S, a!!) A(m)..
Now we consider the hyperparameter choice c' = 6500 In 220T (S) (ms 5///mi
) First, this is
No. Ne.eHtmin
a valid choice, since Nx.1 2 650t Amax In 20T Amax implies that e' E [0, 1]. Then, for this e', o
Mmin
the upper bound (73) simplified as follows.
1 - -
(mm) ll
640 Amax 200 sum [||maxx) V'min
Emix Amax In 200 Sum [S|Amax
$ Qmax
25
Nu.t
Nx.tMainne
8, Amia
+ 2
Vollos
(4)
640
25
12 +
Villos +2
max
650
650
(2)
tmix Amax In Ne
20 S|Amax O
+ )
1/3
2Q m' + +
+
Vn
Vill 00
18Q
- Vi
where (i) uses futs Amax In sfAmm
e3 e53/500, and (ii) uses e' E [0, This proves eq. (75).
The proof of eq. (76) similar.
C PROPERTIES OF THE DUALITY GAP
In this section, we prove some useful properties of the duality gap
(-(1, (22))==
[v(T]
212) (s) - v(F)
7(1), (12) (s)].
max 8, a (22)
Lemma 5. For any policy pair (1) (2), àt holds that
(1)) ((2)) S -
1 max (6),
(s), (s))
(12))
This Lemma generalized the Lemma 32 of (Wei et al., 2021) entropy-regularize Markov game.
Proof. Throughout this proof, we denote the policy pair (T (2) as the Nash equilibrium and
their associated V-function and Q-function are respectively denoted y(7) and Q(?)
25

---

Published as a conference paper at ICLR 2022
Note that
*100 ,100,=10)))) (s) - (s)
(((r)
Σ 10 sTiLss strr (8, ( 1100))
(s al (a))))))))) (a
+ +T|M(T'''
( +
H
(+r (2) (s))
E
x (s, (0.
a0) 2062)
(s.
-a))))))))
[H(
=Y Σ
(0 ",0,,,,,,,,00,00000000000 (s)) (s.
a0)
+ "0
+5 +T((( H( ((= H H(TTT (5)
2 max [v(7] (6) (s9)
+Tf
(8) x (3) (s) - -TI (Q. (s); (s), n (2) (s))
(s),
$ y max [V (5') (s)]
+ + (8); (8), n (s))) - T min Jr (= (z): (s), (22)
)(())
where (i) uses f. (Q (T) (s): Ter (s). nut (s)) max,"() min fr (Q) (7) (s); n (s), (() 2
ming.ca fo (Q (s): n. (1) (s), क (s)).
Applying max,, to both sides of the above inequality and rearranging it yields that [1G2)
max 8,7'(1 ( (8) - v((
1 max
(1), (s)] - (s), (s),
( [0)]] (91)
1-7 a (s)
Similarly, we can obtain that
max (,3
((T)
+00, (e (s)
[f+(Q!))(s) (1)) - fr 12! x (0))] (92)
max
1 7 a. 10 (20)
Therefore,
(T(1), N (2))
((1()) x()) (s)
max [((
(((
2()) (o (s)
[V(T] 201) (8) (s)]
+ max [v) (s) v(+)
max
(,77(1
2.)
(
2
(s), - fo (Q) (s),
max
1-7
(3)
where (i) uses eqs. (91)&(92).
Lemma 6. ( (2)) is 2In Amax Lipschitz continuous with regard to
26

---

Published as a conference paper at ICLR 2022
Vtr) Proof. The definition of the state value function
x00, (r(3) in (3) can be rewritten follows.
((F)
a0), x(1,xx3)) (8) E
7" Ru
80 s]
Σ
y' H(T - (()))))s)))
(93)
1=
t=
Hence, for any T 2 0,
v(2')
x(1), (2 (8) - [(7)
a11) a00 xx2) (+)
7'17' - - =||H(( - 77( (2))))))x)))
In Amax 17 7|.
Σ 7/ T| In Amax S
(94)
1
1=0
where (i) uses 0 S H(T((())s s In |m/mmm))) S In Amax- Hence, this Lemma can be proved as follows.
D (T (1) (x))))))))))))1) (=))( [
[W(F'
(7(1),=711 (s) (s)
v(r))
x [s)]
a, x100 (s)
max [v(T]
v((r)
x00, x0 [5)
max
(,,"11),xx112)
max W 1,,
[v(t')
(7(2) (8) v(2')
x(1)) ((1)) (s)]
[vrtt) v(()), (c))) (8) [(r)
(())) (s)]
x((1) s7(2))
|((t)
x0 (8) v(r)
m()) (2)) (s) + |(()
H(), , (s) - pr(T')
a(13) (8)]
max
8, ",) (2)
(1) 2 In Amax
-'
where (i) uses eq. (94).
D PROOF OF THEOREM
Theorem 1 (Finite-time convergence rate). Apply Algorithm 1 to solve the regroie-e
Markov game with E (0, 11. Choose learning rute 1) = [2(TT + Qmax)) initialization [|Vll < Vmax and batch sizes Nk.1, Na, Nx+1 that satisfy (18) & (19). Then, the Nash equilibrium duality gap converges at the following rate with probability at least 1 8.
( K-1 - (- S 0 =0(
Vmax In Amax
K-1
K-* (1 7-)
K=0
+ Vnux Tlmir Amax In
Trum S Amax
2/3
K-1
Th-
Vmax
K
(1 m5)
2- Th-2
?
Amin
8pmin
km
1=
2/33
T
N/2
k.4+1
V + 7 72
mix V3 max
K
K-1
K
---1
+
In
(20)
72 72 (1 7)3
8pmin
Nx+1
Am
Proof. First, consider the SPU iterations that are defined by replacing Q d(m) in (8) with p(m)
(m)
Qu141 respectively, for m = 1. We can apply Lemma I with the quantities being specified as follows.
Q = Qu(s), hr (u, = fr (Qu(ss)
Me (s), == T (s), F4,+1 := = = De41 := (2) 7 (s),
: m, (1) (s), 1 = = (s),
(s),
(2)
27

---

Published as a conference paper at ICLR 2022
dm : IA(m))
d(m) = Qumn (6) - Q (s), olme) == Qu.t11 (0) - Qhei Q
(mm)
(1) (6), T (3)²(s) (s) is the solution policy pair to the minimax optimization problem (1) maxx(((s) fr ()); (*))
where T/
Consequently, eqs. (29) & (30) with t= Th- imply the following two inequalities, respectively.
f- (Qx(s)) E. (s), R.T (s) - (=(( (I) (s), T ())()s))
Vitt (8) - fr (s); (1)) (s), Tx x12) (s)) (s))
8 -1 ) In Amax +
Σ
(1 mr) Th Th-2-t
1)
1=
2
Σ
Snl1@ (s) 0m (s)
33
-s)
- (m) -
(95)
4T
(s), (s)) - (1 (5), ग (2) (s))]
max
#0 (1)
(s)
[5=(Qx (s); x (s), (s)) - (=(((()): (s): x (2) (s))
max x (8)
T--1
4 (1 - )r))=a-11n Amax +
Σ t=0
(1 - 17)) 777 T---
1)
2
12 (m)
16m||@km
(m)) (s)
2 ( (s)
2 + (k)) (s) - -k
(96)
m=1
Then, define the soft Bellman operator B, as follows.
(+( (1) ((2))
max min Jr (())) = ()) .a(2)) +T (( (s)))()(()())
(97)
where Q: S A1)) x 222) - R and Q(s') E 1x with each entry given by [Q(s')la (0 == Q(s, (1), (2) It can be proved that B, is a contraction operator and has unique fixed point -!T²) (Cen et al., 2021), that is,
[BB, (Q)) (Q))lo 5T - o1 )+(Q!")))0) =Q!T)
(98)
(99)
As a result, we obtain that
10++1
o!a² 1rx
11Q++1
- 1Q++1ss, (2()) - (sx) a()) (0())))) [ + - 100
(1)
<
max
5,0(1)
R(s, a) a(),a() (2))))))))))) + TIE, Pp (0c2)) (s')
max s,0()),(0))
- -[R(s,a (2)) + -E fo (Qx T (8'), x (2) (s)) + +111, - Q! |la
max max EE8
y
- fr (=x (s')
(5'), - (2) (s')) + 1 11 Q!! (7) I
(100)
28

---

Published as a conference paper at ICLR 2022
where (i) uses eq. (99) and (ii) uses eq. (98). Throughout the proof, suppose that eqs. (72), (75) & (76) hold simultaneously which occurs with probability at least 6. In this case, we have
| m2)
(s)
Q (m)) (s)
k,t
mmix Amax
200 ||AA Amux
) + +8/1 - Vill
S
648Qu max
NN.emmiin
8
(1)
mmix A Amax
207 (S) A max
)
648Q max
In
V/miu
29241 mix 1/2
4K|5|
+ 32V
(101)
max
N++1/minl (1 -7)
8 V/Pmin
where (i) uses eq. (75) and the inequality that (a + b)2 < 2a² + 212 for any a, b 2 0, (ii) uses eq.
(72) and also (a + 6)2 < 20² + 262 for any a, b 0. Similarly, obtain that
(m)
(Q) (s) Qhi4 (
$ 648Q
tmix Amax In
20T 20 sum ( |S|Amax 2/3
)}
8 / 4K|S|
29241 Mmnix Viaxx In N4t1/minl (1 - 7)2 8 //Pain
+ 2 max
26
(102)
Then, iterating eq. (100) yields that
1Qk-1- 10 a
K-2
< ~x S>--11Q00 - -Q!T
11
+
K-k k-
max x'ES
Vi+1(s') F=(Q2(s)) ; (1) (s'), x
(2 (s)))
k=0
(1) K k-1 max +
K-2
Tx-
S 27
Σ
K-k-1
(1 177) To In Amax
m)) T7
Σ
Ssml@Qae (s)
(m))
(s)l
11= +
33
Q (x.441() - Q2.411(5)) (s)
~ (m)
4T
m=1
K-2
88
Tx-1
27
K- Qmax +
K
K--1
- 177 In Amax
+
Σ
(1 - (-)
11
k=
1=0
Σ
648Q2
maxx
Emix A Amax
In
20Tsumi S ||Amuux
]
2/3
81)
+
33
m=1
Amin
8 Pumin
N223
4T
N
2/3
k1
33
29241f mix Vinax
4K|S|
+
817 +
32V2
7 26
In
45
max
N N 1 (1 7)2
8 Punin
8
(1i))
8
K-2
< 27th
K Quax +
In Amax
K k----pp (1 - T1-
k=0
mmix A Amax In
20T
S| A|Amax
)
+ 32422 max
Mmnn
//mmi
K-2
Th-1
32m
33
1568 K K-122
k-1
(1 m5T) U2 22-
N2233
TN
2/3
1) -7)
k=0
k,
1432809t V
SK|S
K-2
In
K- -- -N-1
Not
(103)
1/7 1p2immnn (1 7)
//Immin
k=
(1))
Vinxx In Amax
K-2
Σ
K-
177)
Ta-1
Vmax
Imix Amax In (T (S] Amax 22/3
)
Amin
8pmmiu
k=0
29

---

Published as a conference paper at ICLR 2022
K-2
Tk-
1
V Viax
K KK--1 k-1
(1 T1T) Ta-2-1
+
N
TN
2/3
k=0
2=0
k,t+1
V
max
7
mmxx V
max
In
K|S]
K-2
7 K
-K---11 Nx11
(104)
721 7)
72
Mminn (1
-)
0pmnn
k=0
where (i) uses eqs. (68)&(95), (ii) uses eqs. (101)&(102), (iii) uses 17 = (2(T + Quax)] 11/(2T).
Ei=o (1 T S (]([--]]] S f/r
and Σk 7 K < and (iv) uses Qmax
O(Vmax) for y ~ 1 and = [2(T + Qmax) ) I ( O(V (Since Qmax Y ((T)).
Using Lemma 5, the convergence rate of the duality gap in eq. (20) can be proved as follows.
(TT)
K--11 2211)
(1)
2
max
1 - --y s (3)
(2)
max
1 Y (1) (2))
+ 2
(3) ( (0x
max
7 (1 (2)
|=((0-1(())= (1)
2 (s)) - fo (2)
+ 1 7 (, (2))
max
2 Tx-1-1
(0)
8
(1 (-1r)) 1-1 - Amax
(1 m 1k
17 - 7)
1-7
2
167/ (6n]|@km]) (m) (s) ( [1)
(s)
+ 7
+
12
11
~ (m)
(8) - (--1)+1())1
m=1
2
[ (s) (s) QK (s)1
max
7
(,((1)
"K-1 (s) T [Q Q! (s)) (s)
(1)
+
max
7 (3)
(08) 8 In A Amax (1 177) TK- 1
Tk-1-1
- (1-1 Tx-1-221-2-
1111 7)
648Q2 max tmix Amax In
20T sum (S) |S|Amax
2/3
167
12
Amin
8. 8
N2/3
1,t
T K 1,141
2/33 2/3
+ 32m +
24 )
32V max
y 2)
29241t mix max
In
8 / )1
4K|S|
N NK (1 72
+ 11x-1- -Q(") 10
(10)
811 Amax
2592Q
mmix Amax In
20T sum [S|Amax
)1 2//3
(1 177) TK--1+
max
1111 7)
1
Mmin
5, MMmin
Tw-1-1
Σ (1 -1-18 11-1))2--1--211
16n
12
2213 -K- 1,t
TN 2/333
2/3
t=
111
160 +32V2
29241 Imix V22-0
4K|S|
max 2(K-1) +
In
1772 1 7
NK (1 - 7)3
8 S/Puuin
89 K K-10 Quaxx
-K-Qquxx
32In In Amax
K-2
K R k- (1 m75) Tx-1
+ n11 7)
7
1 1-7
k=0
30

---

Published as a conference paper at ICLR 2022
1296Q max
mix Amax
20T sum |S| A|Amax
2/3
In
1 1-7
Mmin
ō M/min
K-2
7
-
K
Tk-1
-2- (1-177) --(
(1
22/3
32n
TN
33
2/3
6272 max
17r 7)
k=0
t=
k,4+1
5731 m316
1/2 max In
4K|S|
K
K K-k- ---1 N=11
77 Munin
7)
8 6/Pumin
k+1
k=0
8 K xIIQmax max
32 In Amax
K-1
Σ
K-k-1
(1 177) Th-
1-7
771 7)
1296Q max
mix Amax
20T |S| AmAx
2/3
1-7
Muoin
//Amin
K-1
Tk-1
32n
33
11 max
K-
11--17)7-22-
-2
2/3
T/T 7)2
k=0
t=
k,t+1
5731 m3x V2
4K|S|
K
max In
K-k-- k- k+1
No+1
17 Mumn (1
73
8. /Pmmn
k=0
Vinx In Amax
K-1
Σ
Kk k< (1-1)=)
17T))=n-1 Th-1
Vmax
tmix A Amax
In
Tsum |S) A 2/3
)
?
Pmin
84min
k=0
K-1
Te
Vmaax 2/3 TN k,+1
Vmaxx 7
K-h-1 k-1
(1 (1-1)T) -2-
2/33 k,t
72 - 7)
k=0
t=
mix
73
In
K|SI
K-1
7
K
N
Not1
72 Umin 11 7)3
51tmin
A=
where (i) uses Lemma 5, (ii) uses eq. (96) and the definition of the function fr, (iii) uses eqs. (101)&(102) (iv) uses eq. (103) and 17 = [2(T + mmax)]=1 < 1/(2r), E Ih-11(
7) ( Th---1
" and (v) uses Qmax = ((Vmax) for 7 zs 1 and r7 = [2(r + Q max)] O(Q =
(Since Qmax 2 yT Or)).
E PROOF OF THEOREM 2
<(1->) Theorem 2 (Sample complexity). Implement Algorithm with 7j = 011 T= O (0i Amaa k k
K 0 - In ( ) and Tk =1 In(1
Choose the following adaptive batch sizes.
()) ([(1-)))+
No+1 = 0( tmir (In² Am NR.1 = NR (1 (1= 66(""mm) ((fEmix Amax 177)
3(112)
emmainal (1 - 7)8
Pmin (1 7)3
Then, for any <
In Amas, the overall sample complexity to achieve D (TK-1 π (2))) S is
(
I-7
Please refer to (118) in Appendix E for a complete expression.
Proof. Since 0 0 =01(1-))
we have
Amas
1 1 T Amax
Vmax
= -1)
(105)
1-7
1-7
1 + 1 In Amax
1
Quaa
+0() ((1-)))1)
(106)
1-y
1-7
31

---

Published as a conference paper at ICLR 2022
Since T3 1 + In(1-97 T, we have
=lay-
K-1
k inn
T sam
Σ
1 + In(1 717) -/7))-
k=U
K(K' - 1)
1
=K
+
2
11T
K K(K - 1)
1
In Amax
2
6(1 7)
O K2 In Amax
c(1 -7)
In Amax
In Amax
]
In?
(107)
E1 - 7)3
E((1 -
Hence,
Tsum S) Amax
= 0 (S] |S]Amax In Amax
c(1 --)) --)) )
In Amax
In
+ In (2
8painn
8ppruin - 7)33
edjumin (1 77)) }}
|
0
In
(108)
Similarly,
In
K|
=0 In
8/4min (()mmin
In
In Amax c(1 ((17))
8 6mmin
In(cc In A Amax)
)]
+ +0 in ((
(S)
1
Symmiu (1 -7)) In
8ptmin (1 - 7)
1-
[S] |S] In[[ee Amax)
[S]
O In
+ + In
8ptain (1 - 7)
S1miuu11 - 7)
-o In
[S] In(e In Amax
(109)
8pmin
7)
With the above equalities, we will prove below that the hyperparameter choices in Theorem 2 are valid and satisfy the conditions of Theorem 1 with proper constants hidden in (()) 77 [2(T + Qmax)] 0(1 (1
where (i) uses e < Amax I-
(110)
= E(1 c(1-7)
E [0,
(111)
In Amax
1 K In In
In 5/2 Amax
1 In
In Amax ) 2
O [1 -
(112)
e5(1 7.5
ee(1 - 7)
k kln
Тk =1 + In(1 - 1)T) -1 2
(113)
No41 = tmix (In Amax) Rk/22
k/2
S In(e
In Amax)
In
2m (1
7)8
Öpmin (1 7)
650tmix In 6 Ammin
4
=0
tmix In Hmmi
(114)
Umin
8pmmin
NR. =0 mmix Amax
(1 1/T) -3((+1)/5
[S] AS)Amax
In
(1-))) (1))
Munin (1
7)
cōpmmial
650% Amax In
20T sum SI S|Amax
= = mmix Amax
|S] |S)Amax
In edd (1 7)
(115)
Mmin
6 Munin
Mmin
Emix Amaz (In (113/2 3/2
Amax )1 177)
3(t+1)/55
coppain - }
|S] |S|Amax
NR.1 =0
In
Mmin
3/2
32

---

Published as a conference paper at ICLR 2022
650t mix Amax
20T sum S|Amax
o tmix In
|S] ||Amaxx
)
In
(116)
Amin
8 /Pmmn
Mmnn
e00lmin
With these hyperparameters and eqs. (108)&(109), the duality gap bound (20) can simplified as follows,
D
(2) K-11 T --11
(1)
Vimax In Amax
K-1
V max
Umix Amax
Tsum |S] Amax
)] 2/3
0
K- RR- (7))
Th-
In
1 1-9
Mmin
5ffmiu
k=0
K-1
Σ K-k-1
-h-1
(1 )T)) T2-2-1
1
Vmax
V-3 max 7k
k=0
1=0
N-2/3
T
NN
2/3
k11+1
72 7)2
mmxx max
KSS
K- 1
1-1
In 7)3
2 Mmin (1
8puanin
Nk+1
k=
K-1
In A
K Righ
7)2 km0
+ (1 (1-
AmixxAaxx In .éppmii (1 7)
|S|Amax
2/3 K-1
Σ
K- k-
Th-1
Σ
(1 - (--77)²+-- ---
Mmin
k=U
t=0
(0) mmix Amax
Mmin (1 7)3 In edjumin (1 (1- )
/||Amax
2/3
(1- - 1/T
) 2(++1)/5
+ 0 In Amax
c(1 - -7) )0l
mixx Amna (I13/2 Amuux)
In
|S] |S]Amax
)
-2/3
(1 )/7) 220441)66
Munin 3/2 76
7 K (In? Amax)
Lmix (mix(1n2 Amax)
|8] In(e In Amax))
In
e1 7)7
2 (1 7/5
8pmiin (1 - 7)
1
mmix (In² Ammax) -k/2 k/22
[ In([ In A Amax)
K k---10
In
e² 22mmin (1 - 7)
8fmmin (1 77)
k=0
Amax K-a R
K-1
Th
0
7 K
K-k-1
(1 1/T) Th -1 332+
(1 7)2
k=
K (In? Amax)
K-1
K- R-/22-1
el 7)T
km
(1)
In Amax
K-1
K-1 (1 175) (175-3/5(11 175 3 1]
7)2 Ka
+
- 113/))-3/5-
k=
7 K (In? 2 Amax)
+ 7 x- 7- K//2
e1 -7
7/ 1122 -
(18)
In Amax
K-1
n 31-35
K <(In2 Amaxx)
7(K (1/21)/2
K
+
+
- (1 (1-17))33 13/5
<2 7)7
1- 1-12
k=0
(10)
In Amax Kigk + 7k K-1 (3K//5 - 11)
((nn2 Amax)
+ x/2
+
72
(T -3/5 -1)
c²(1 - 7)7
-
In Amax
<e( 7)) )
In Amax
+ 7 22K/5 In Amax
2 K (IIn Amax)
7 K/22
0
In
7)3
<(1 -11-0 733
e² 71
1-7
1-x
(1 22.75
(vis)
o
E + 3
-(E)) I ce
(117)
In Amax
In 5/4 Amax
33

---

Published as a conference paper at ICLR 2022
where (i). (ii) and (iii) use (1-17)) Th- 7 based on eq. (113), (i) also uses eqs. (105), (108)-(11)
& (114)-(116), (iv) uses 1 - (1 73/5 (nT), 1 71/2 O(1 7)) (v) uses eqs. (110)-
(112), (vi) uses O z In (1-))² In
In Amax e(1-7)
S o
-- implied by K (la² Amax] and 7K In Amex
((1-))
eq. (112), and the numeric constant c > 0 in (vii) exists. By replacing with e/c, we obtain that
Dr(TT (TTK-1 K-1-
(1) x x-))) S which means (T 1 "K -K-1) is an c-Nash equilibrium policy pair, and the
(2)
orders of all the hyperparameter choices remain the same. In this case, the overall sample complexity is given by
No+1 +2 2 Ta
Σ
(Ne, + NERett)]
mmix (In? Amass)
[S] In(e In Amax)
K-1
E² Punin (1 - 7)8 In
? k/2
8pmmin (1 - 7)
k=
+ 0 mmix Amax (In3/2 Amax) In Ledprnin (1 Mmin e 7)6
AS)Amax
K Tw-1
(1 (1-
3//4-1//5
7)
k=U 1=
=0 Emix (In? Amax)
SS] In(e In Amax)
7
K/2
222umn (1 - 7)8
5tmmio (1 -7)
7-1/2 -
15)Amas mix Amax (In 3/2 Amax) In coppenin (1 Mmin 532in 76
K
[1 - -1777 3T -/7)--3//555
1
+ O
Σ
(1 (1-17)33/
k=
(11)
mix (In² Amax)
|8] Iu(E In Amax)) 7
0
Plmin (1 - 7)8 In
8pmmin (1 - 7)
m Amixx Amax (/n Amax) In Leppmin (1 - 7)
|8]Amax
In Amax
K
+
o
3k/3
M/mine3/2 76
c(1 77
k=
< 0
taix (In2 Amax)
7)8 In
SS Infc
In Amaxx)
7 K//2
é 2mmnia (1
5ytmiu (1 - 7)
mmix Amnax (In 5/2 Amax)
A
? -3//5
+
In
e/2 - 7)8
cdppmin (1 -
7 3/5 3/5 -
(116)
tmix (In? Amax)
|S| Ln|e In Amax)
In 5/4 Amax
In
2 (2iin (1 - 7)8
8ymmin (1 - 7)
c5/2(1 - 73)3.75
mmix Amaxx (In Amax)
18)Anan
1n13/2 Amax
+ o
In cddpuain (1 - 7)
Mmin 5// e/
7)
c3 7).5 5.5
(6v)
m Amax (In' A Amax)
In
(e0 (1 - )
18| Am|Amax
(118)
e - (1- 13.5
tamix Amax
= =
Mmin 5.3 (1 13.5
where (i) uses No.t NR. and eqs. (114)&(116), (ii) uses -110)-100000)))1111--11 ////))///--
(117) = 1 {(1-)) Amax and (1 (1- = (iii) uses -3/3 - = 0(1-7) and nK
In Amayy
implied by the hyperparameter choice (112), and (iv) uses the fact that the second term of (iii) larger than the first term of (iii).
F SUMMARY OF COMPARISON OF SAMPLE COMPLEXITIES
In the column "Model-free", a / means that an algorithm does not need any prior knowledge of the environment, including reward mapping and transition kernel.
In the column "Private update", a means that the algorithm updates do not involve the opponent's sensitive information, including action and policy.
34

---

Published as a conference paper at ICLR 2022
Table I: Summary of sample complexity of algorithms for solving discounted infinite-horizon sum Markov games. (JS) is the number of states, Amax is the maximum number of actions between the players. pmin the lower bound of state stationary distribution. ? is the discount factor.)
Work
Model -free
Private update
Symmetric update
Data type Markovian i.id.. i.i.d.
Sample complexity (duality gap E)
Zou et al. (2019)
x
Zhao et al. (2021)
v
Guo al. (2021)
/
Cen et al. (2021)
/
A S 1015
Wei et al. (2021)
v
Markovian
Pmiin (1 22933
Our work
Markovian
Amax
2 Piiin
13.5
In the column "Symmetric update", a v means that both players perform symmetric updates.
In the column "Data type", "Markovian" means that the algorithm uses samples queried from the dependent Markov decision process. The sign means no stochastic samples are used.
The sample complexity is defined as the total number of samples required to achieve an e-duality gap for the Markov game. A "_" sign in this column means that such type of sample complexity is unavailable in that paper or its setting is different from ours. We use O to hide all the logarithm factors.
We next explain how the sample complexity of (Wei et al., 2021) is calculated. Corollary 4 of (Wei et al., 2021) shows that the aterate-average duality gap is smaller than e with the hyper-parameter choices: number of iterations T δ アリーाア
|s| and number of samples queried per iteration
A 15
(we replace & with c). Hence, the overall sample complexity is
(1 23
A3
max S
A3 S 10.5
10.5
LT = 5 (1 (1->) Pm
max
7)
29.5 Umin
where (i) uses the choice of learning rate S
required by their Algorithm 1.
G RATIONALITY
In this section, we will prove that the policy extragradient (PE) algorithm Cen et al. (2021) is rational. The following analysis can be directly extended to our stochastic policy extragradient (SPE) algorithm by applying the estimation enror bounds in Appendix B.
algorithm is called rational if, whenever the player adopts an arbitrary stationary pol- icy (22), the policy of the player converges to the best response to ((2), i.c., +(1) (s) ((F arg max,("(a) 7(1) (en) (s) for all S. We add tilde in #(!) (s) to differentiate it from the Nash policy pair (T)),
(s), TTT (s)) and some consequent notations are similar. Denote Q = Q a (2))
(((T) = (TT
as the optimal value functions and define the soft Bellman operator as follows
Rey (a))
(+) (1) (1)(21))
:= R(ssss (1) (((()) + B (aaa0))))
max fr (Q(s'); (Q())); ( (()))))))
(119)
Similar to eqs. (98), can be proved that the soft Bellman operator B, also a contraction operator and has a unique fixed point "(T), i.c.,
(15,(Q)) (Q) StilQ' Q11
(120)
35

---

Published as a conference paper at ICLR 2022
(
(121)
To solve modified Markov game with fixed policy ((2), develop the single-plaeer-perspecci version of the PE algorithm in Algorithm 2, which basically approximates the value iteration Q++1 =
B, (Qk). The main modification from the original PE algorithm is that the new policy update (126)
only keeps the third expression of the PU steps (8) since only that affects the final policy of player 1 with fixed (22), This new policy update (126) aims find x(2) that maximizes the following hingle-plaeer Markov game problem with fixed (x(s) and ( (s) for all S, while the original PU algorithm seeks the Nash equilibrium (r1 (2)) of the following function.
max (+K((()) (s), (s) = (s) (2)))=(((s)) + (H(
- (H)
(122)
Similar to eq. (23), it can be derived that the solution R x011 (s) satisfies the following condition Cen al. (2021).
(s) to the above optimization problem
(s) x exp(Qa(s)Te($)/T)
(123)
Algorithm 2 Single- plaleerppperere perspective PE algorithm for retropy-rreullarized Markov game.
Initialize: (o(s) for all E S.
for value iterations k = 0, 1,..,. K - do Compute the following Q functions for all (s, (1), (0, 2
Q (l))) R(ss, (1) (2)) + Pl. Vi(5) o - Qu((s (1) a!2))
(124)
(125)
Initialize T2.0 with uniform distribution. for PU iterations t = 0, ,...., T do Player implements the i-th policy update for all s, (2) as follows.
(a a (1) (s)))) exp (nQ (s, ( (s)a
(126)
end
(1) (1) Let a k. and perform the following value iteration for all 8
(s+ = fr(Qu(s): m ( (2), (s))
(127)
end
(1) Output: #K-1-
We first prove that the value functions Vs and Qs in Algorithm 2 are bounded as follows.
Lemma 7. If Volloe I Viax := 1+r Amax in Algorithm 2, then for all k 2 0, 0 st Ty - 1, we have
1-4
max (1IV 110 S Viaxx
(128)
max (110 @.2² 1/011)))))) S Qmax,
(129)
where Qmax := + Vmax
1+gr in Amax with Amax == max (14(1), (1())).
Proof.
The proof is similar to that of Lemma 3.
L
Similar to Lemma 1, we can prove the following lemma about the convergence rates of the modified PU steps defined by eq. (126).
36

---

Published as a conference paper at ICLR 2022
Lemma 8. Apply Algorithm 2 to solve the entropy regularized game with T > O. Choose learning
rate S T and initialization ||Volls I Vmax- Then, the policy update defined by eq. (126) for maximizing the functiin (122) has the following convergence rates.
K (s) + ( (T) (s)) 1 2Q (1 - (1-15)²
(130)
T
[+(Qu(s); (s), Vi++ (+) = - (KT(TT (1) (s)) S 20mam (17) (131)
Proof. Taking logarithm of eq. (126) yields that there exists Caat E R such that (1) In k (s) (1 1yr) In x (s)
(s) + (T2 ck,c1.
Iterating the above equality over 0, 1, ..... yields that there exists E R such that
1 1 (1 n1- (x(s)T2(s)) e1
In (1) (s)
(132)
where we use the uniform policy initialization T2,0 1/ 1/
(1)
Taking logarithm of eq. (123) yields that there exists c* E R such that (s) (s) Q2())
In k
(133)
Therefore, eq. (130) can be proved as follows.
K (s) (s)l (s)) + (LL))) (s)
(s))
(T (s). In x (') (s) In (x) + (TH
(7 In nn
(10(1) (s) -7 (.T((s) (s), (1 )-)² (x()) + (c' - c)1) -c)1
(1)
(0)
(1 TT
[T (8) - TT
(1)
(1)
T
(181) 2Q max (1 (1-
where (i) uses eqs. (132)&(133), (ii) uses (1 (b), 1) = and (iii) uses [|Qx(*) <
Qmax, || - x - 11 S 1T2(ss and 1 - 17T > 0.
f+ (s) - Vs+
= (0) +30"0000000000000000000000000000 - (s), In m- (s))
(
=
() - (1) (0)
- - (s), In नx (1)
(s)
KL (T) (s)
2Q max (1 --)
where (i) uses eq. (133) and ()) (s), 1) and (ii) uses eq. (130).
(s)
Finally, we prove the convergence rate of Algorithm 2 as follows.
Theorem 3. Apply Algorithm solve the entropy regularized game with O. Choose learning
rate E - and initialization \ olx < Viaax. Then, the Q function estimation error 1|Q
1 Bloc and the function value gap max, ()) v(r) "K
_ (s)] converge at the following rates
K + 27Q max (1 )TT)²²
- 1 100 S 2
(134)
1
max (1()(()) - ((7)
1 12-() (8)
5
2Q max
2g K-1 11 + 1-
1 1 (1 - --7)²²
(135)
37

---

Published as a conference paper at ICLR 2022
Proof.
10++1- - 10
11Q+11 - (B,(0))
(4)
Qu+1(s, - (Qx) ( ,a(1) + +110x - 100
max
,,a(+), .01)
((ls,a()aa)) + PB Vs+1
max 2,011),((2)
- -[R(s,a() _222)
+ ( f (Qu(s)): tt
(5') (2) (6) (6))] + +>112x - 10%%
S myma V*+1((')) - fr ( (Q t (5'), () (5 + 1Q - 10
*ES
((F))
S 2aQ (1 - -- + 7 Qx= - : ممح
where (i) uses eq. (121), (ii) uses eq. (120), (iii) uses eq. (131). Iterating the above inequality yields that
- --
1Qk-1 - 1bc
llo S 110 - -1++) 1000 + m1x 177)
1 1-7
S mmxxx K + 27.0max (1 1777 (1-
1-7
which proves eq. (134). Finally, eq. (135) can be proved as follows
v. (s) ((r)
m(()) (s)
(5 (5 (1) a (1
=
( Monc
[H
(s)))
Σ
(Qth (8, a (1) (l21) 1(7
)e (s,)))) |= -T (s(2)
Σ
(s,
a (1) (a 22 (aWWss - (2) (1
a(t) (at))
[M
H(
=7 Σ
K 1s)
p( a03) (7/ v(+)
(1) _ (6)1
(#!)) (s) π (1)
K-1 (8))
(s)) - H( [s)
S max (s') ((
(5') + (3) x (s) (2) (s))
+ + (s)) - (
Applying max, to both sides of the above inequality and rearranging it yields that (8)
max (s) - v(r)
1 (s)]
max
1 max
1 γ
max
1 max
(1000 - f, (Qk-1()) (1) (3) (3)))
1 1-7
38

---

Published as a conference paper at ICLR 2022
max (F(( - --(
(s); (s): (1) (-), (3))
1 7
1
max max /r (Q_ ( (())s))
max fo (00
1
((1)(s))
1
max
()):
Vx((s)
fr [=( (5) fr f- 5-( (s); (8), x ((1
+
max
1
2
7* + 21Qmax (1 --)"" + 2Q (1 kr)
2Q 2maxx?*
1-7
2Q mQaxx
27 27 + - (1-m)²
where (i) uses eq. (131) and the following inequality that holds for all s, (1) (ii) uses eq.
(134) and (s) fo (o (5); (s) (s)).
(s) - (5);
S-
1|Qk- (9)
S 2Qmax7
2mQmax
1-7 (1-17)² m77)²
In Theorem 3, the convergence rates of both the Q function estimation error 11Q=-1- 1loo and the funetion value gap max, V.. (s)
((()
TK-1.T (9) (s) consist of two terms 0(**) and O(1 nr)""
which characterize the exponential convergence rates of the K outer value iterations and the T inner policy updates respectively. Such convergence result indicates that Algorithm 2 converges to the optimal solution to the regularized Markov game, and thus can be arbitrarily close to the optimal solution of the unregularized Markov game with sufficiently small т. As result, the PU algorithm Cen et al. (2020) is rational. Similar result can be directly extended to our stochastic policy extragradient (SPE) algorithm by applying the estimation error bounds in Appendix B.
39


Reviews:
[{"review_id": "wPysAgAM2xg", "reviewer": "Reviewer_RwGu", "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": "The paper investigates a multi-agent RL problem from a policy gradient perspective, which is an interesting problem. The paper is well-written. Below are my comments and questions regarding the paper.\n\n- In the single-agent case, entropy regularization with coefficient $\\tau > 0$ has two effects: improves convergence rate in the regularized MDP, and encourages exploration (Mei et al., 2020; Bhandari & Russo, 2019; Shani et al., 2019). In particular, entropy regularization makes $\\min_{s,a}\\pi(a|s)$ bounded away from 0, which seems to be important to prove convergence. In this paper, the regularization coefficient $\\tau$ is chosen arbitrarily small to show convergence in the unregularized MDP. The first effect of entropy regularization (i.e., convergence rate) is clearly observed. What is the impact of small $\\tau$ on exploration, for example, in terms of minimum action probabilities? Is it hidden in some parameters (e.g., $\\mu_{min}$)?\n\n- The paper assumes that the minimum steady-state probability under each policy pair throughout the trajectory of the policy optimization is bounded away from 0, which is a strong assumption as it imposes a condition on the nature of the policies. Furthermore, $1/\\mu_{min} \\geq |\\mathcal{S}|$ in the most optimistic case. The dependence on $|\\mathcal{S}|$ can be more clearly stated for the sake of clarity. If one considers a duality gap notion based on an initial state distribution where the initial state is distributed according to $s_0\\sim\\rho$, could it be possible establish a similar convergence bound under milder assumptions (e.g., $\\|d_{\\rho}^{\\pi^{(1)}, \\pi^{(2)}}/\\rho\\|_\\infty < \\infty$)?\n\n- Concentration inequalities to estimate quantities of type $\\frac{\\mathbb{E}[X]}{\\mathbb{E}[Y]}$ by using $\\{(X_i,Y_i): i \\geq 0\\}$ are used in other domains (e.g., (Xia et al., 2016; Hsu et al., 2012)). It can be clarified that the number of samples should be sufficiently large to bound the denominator away from zero with high probability for the stability of the estimator.\n\n- An interesting scenario is the function approximation regime, where a restricted policy class is considered to address large state spaces. Can the results in this paper be extended to that regime? This question is related to my first two questions, i.e., dependence on $\\mu_{min} \\geq |\\mathcal{S}|$ and the distribution mismatch. I would be glad if the authors could provide insights on these.\n\n---\nY. Xia et al. \"Budgeted bandit problems with continuous random costs.\" Asian conference on machine learning. PMLR, 2016.\n\nD. Hsu et al., \"Random design analysis of ridge regression.\" In Conference on learning theory, pp. 9-1. JMLR Workshop and Conference Proceedings, 2012.\n", "summary_of_the_paper": "The paper proposes an entropy-regularized policy extragradient method for zero-sum Markov games in the tabular setting. By using low-variance value function estimators, and entropy regularization, the algorithm is shown to achieve improved sample complexity for a given target duality gap for a Nash equilibrium solution.", "summary_of_the_review": "The impact of entropy regularization on the exploration is elusive. The assumption that the minimum steady-state probability under each policy pair during the policy optimization steps is strong. It would be good if further insights could be provided on these.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nPwLW9q3pec", "reviewer": "Reviewer_5TU3", "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": "\n## Strength\n\nOverall the paper is well-written and clear to follow. Given that the standard policy extra gradient algorithm requires both players to coordinate with each other and share a Q-table, and updating the Q-table requires full knowledge of the transition kernel P and the reward mapping, the proposed stochastic version of it nicely addressed these limitations. Though the proposed algorithm, which uses the Markovian stochastic samples is intuitive and natural, the finite-time analysis turns out to be more involved and required some new analysis techniques. \n\n## Weakness\n\nAs mentioned above, the stochastic variant of the policy extra gradient algorithm appears to be a very natural design choice. In terms of the technical novelty, I acknowledge that there has been a fast growing line of works on Markov games and due to my limited familiarity, I can not fully confirm on the technical novelty part of this paper.\n\nMoreover although the main contribution is purely theoretical, the paper did not mention or include possible simulations to demonstrate the sample complexity bounds, or improvements over the past algorithms.\n\n## Further comments\nIs there any way to say about the optimality of the sample complexity that is achieved using the stochastic samples? ", "summary_of_the_paper": "## Summary \n\nThis paper studies a decentralized stochastic policy extra-gradient algorithm for solving two-player zero-sum Markov game. In comparison to the standard policy extra-gradient algorithm, this algorithm uses a set of stochastic estimators to estimate the value functions involved in the stochastic updates. Improved sample complexity guarantee is also derived.\n", "summary_of_the_review": "Overall I find the paper well-written and provides good contribution to the current line of works for solving two-player zero-sum Markov games. In comparison to the standard policy extra-gradient algorithm, the proposed stochastic policy extra-gradient algorithm is model-free, and is proven to obtain a better sample complexity than the state-of-art. The paper also presented clearly the intuition of the algorithm and the new technical techniques that were involved. \n\n\n\n-----\nPost rebuttal update: I have read the authors' response and will keep my original score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "i9OxZJVhaz", "reviewer": "Reviewer_sRxd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nFirst of all I think the theoretical result is solid, and in terms of the result, the improvement over existing work is clear ($\\epsilon$ dependency from $1/\\epsilon^8$ to $1/\\epsilon^{5.5}$). I also find it satisfying that the sample complexity analysis is placed at a central position in this paper, as with gradient-based algorithms sometimes only the population analysis is presented (assuming full game knowledge). Given that two-player zero-sum MGs is maybe one of the most important problem settings for multi-agent RL / games, I think this result should be of good interest to the community. \n\nOverall the presentation of this paper seems clear. All the problem settings, assumptions, and results seem clearly presented as well. There is a reasonable amount of discussions on the proof techniques (for example, the improved stochastic estimators) from which I can get a hint of where the theoretical improvements come from. \n\nWeaknesses:\n\nAfter comparing with the closely related prior works of Cen et al. (2021) and Wei et al. (2021), I find the present contribution perhaps a bit incremental. The relationship seems to be that Cen et al. proposed the population version of the extragradient algorithm but did not do a sample complexity analysis. Wei et al. gives the sample complexity analysis, but for the vanilla policy gradient algorithm (without extragradient, and with Euclidean projection instead of mirror map). In this sense, at a high level, the present paper may be seen as somewhat a direct combination of these two papers, though some technical improvements are made (e.g. the better stochastic estimators in (14)(15)). \n\nRelated to the above point, I also find the paper lacking some high-level discussions in terms of where the theoretical gains over Wei et al. come from. First, I wonder in the population case, what is the comparison between extragradient (+mirror map) vs. policy gradient of Wei et al. The authors mentioned on Page 5 the regularized (smoothed) extragradient algorithm converges exponentially for each $\\tau$, but how about picking $\\tau$ to get convergence to $\\epsilon$-unregularized Nash? In this case what is the difference in the convergence rates between extragradient and gradient? (Feels like this may be resolved by presenting a head-to-head comparison between the population results of Cen et al. and Wei et al.)? Then, after going from population -> samples, how many additional $\\epsilon$’s does the present paper pay (and how does Wei et al. do?) Since this paper uses improved stochastic estimators, is the number of additional $\\epsilon$’s better than Wei et al.?\n\nFinally, I am very suspicious of the motivation of “private policy updates” in the abstract / intro, as many prior algorithms also have this feature (as the paper mentions in Table 1) and this is quite common for any sample-based decentralized learning algorithm. Further, the joint features of “model-free, convergent, sample efficient, symmetric, and private policy updates” are also not that uncommon, for example in the V-learning algorithm of Bai et al. (2020), as well as the vanilla policy gradient algorithm of Wei et al. (2021). Therefore the claim of “we develop algorithms… with all these properties” needs to be revised. I suggest the authors modify the tone here to focus more on the improved sample complexity for the gradient-based algorithm (which is the key contribution in my opinion) instead of the above features. \n\nOther comments / typos:\n\n\nEquation (14), (15): Denominators should be $\\pi^{'(m)}_{k, t}(a^{(m)} | s)$?\n\n---\nUpdate: I thank the authors for their response and revisions to the paper. I think the authors have addressed my concerns about the theoretical improvement of population vs. samples via the added discussions below Theorem 2, and I am now more convinced about the technical contributions. I have raised my score accordingly.", "summary_of_the_paper": "This paper theoretically studies gradient-based algorithms for two-player zero-sum Markov Games (MGs), an important problem in multi-agent reinforcement learning. The main contribution of this paper is a sample-based policy extragradient algorithm for finding an approximate Nash equilibrium of the MG, with improved sample complexity guarantees over existing policy gradient based algorithms.", "summary_of_the_review": "Overall, I think this paper makes a solid theoretical contribution in the problem of gradient-based algorithms for zero-sum MGs. However currently the contributions seem slightly incremental over the two recent prior works, and there is a lack of high-level discussions on where (population vs. samples) the exact improvements come from. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "aBu4iV7_SMa", "reviewer": "Reviewer_Hsr5", "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": "The problem the authors consider is important in competitive RL, where the authors show some improvement on the state-of-the-art result, so in general I think this is a good paper. To me the most significant contribution is the usage of new estimators in (12), (14), (15). Other than that, it seems like the algorithms come directly from Cen et al. However, the estimators seem not very novel to me. I meant to successfully apply them in this setting may not be trivial, but the estimators themselves should be used in other papers I think (or very similar ones). I guess the authors should do some survey and cite these paper when introducing these estimators.   \n\nComparing with Wei et al. I think authors should discuss more on the contributions of each component to their improved bounds. Because the base algorithm is very different from Wei et al., I am not sure if the improvement comes from the estimators, EG, or the entropy regularization. Or put another way, is it possible to analyze the sample complexity of the algorithm in Wei et al. using the new estimators, or analyze the SPE algorithm with the estimator in Wei et al. I guess either way would help us to understand the significance of the estimators, as well as the other components. \n\nRegarding the technical contributions, I think that is also one of my concern, First, the authors use Assumption 2, but I think Wei et al. didn't need this. If that is the case, I think the paper, strictly speaking, is not comparable with Wei et al. Secondly, I didn't notice the authors explain the technical difficulty when analyzing this algorithm in the main text. If it turns out it is straightforward to combine the new estimator with the algorithm in Cen et al., the paper becomes less interesting to me. Lastly, as highlighted in Wei et al., their algorithm is rational (converging to the opponent’s best response when it uses a stationary policy). It doesn't seem like SPE has this property, which I think may be important. \n\n", "summary_of_the_paper": "The authors consider two-player zero-sum Markov games. The goal is to develop decentralized, model-free, symmetric algorithm. With entropy regularization and new estimators, the authors show the stochastic policy extragradient algorithms have these properties and the sample complexity improves the sate-of-the-art. ", "summary_of_the_review": "It is an interesting paper, which improves the best known bound in the field. However, I have some concerns regarding the novelty, comparison with the previous work, and technical significance. If the authors can address my concerns, I am happy to increase my score and recommend acceptance.   \n\nAfter the discussion period, my concerns are addressed so I changed my score accordingly. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PM-HnhS4tmd", "reviewer": "Reviewer_8RN2", "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": "The concepts of this paper mainly adopt from the well-studied PE algorithm and the sampling technique, which slightly hinders the novelty of this paper. However, with the elaborate design of the stochastic estimators and refined analysis, this paper achieves a significant improvement over the sample complexity. This improvement is a valid contribution to the understanding of the Markov Games. Besides, by utilizing the concentration inequalities for dependent samples as in [Paulin, 2015], the assumptions in this paper are slightly weaker. The paper is clearly presented, with each theoretical result followed by interpretations and comparisons with [Wei et al, 2021]. \n\nThe main concern of this paper is on the novelty, it is not clear whether the improvement over [Wei et al. 2021] is due to the alternation from OGDA to EG, and the entropy regularization. While both techniques are previously analyzed in [Cen et al., 2021]. I am not very sure if the novel design of the estimators is a natural adaptation to the PE algorithm, or does the two approaches: the sampling from the state-action frequency to the state frequency, and the accurate original policy, have also contributed to the improvement in the sample complexity. Besides, as this paper introduces several hyperparameters taking completely different values, intuitive illustration of the convergence rate, like theoretical convergence curves under different choices of the batch sizes, the $T_k$, is preferred in comparison with [Wei et al., 2021].", "summary_of_the_paper": "This paper focuses on the two-player zero-sum Markov Game setting and proposes a stochastic version of the policy extragradient (PE). The PE algorithm, which solves an entropy-regularized minimax matrix game problem by predictive update (PU) [Cen et al., 2021], has been well studied under the deterministic case in the work of [Cen et al., 2021], proven to converge exponentially to a unique solution. However, with an inquiry into the full Q-table, and the full transition matrix P, the original PE algorithm has its limitations in practice.\n\nThe authors of this paper design a stochastic counterpart of the PE algorithm, the main sampling technique of introducing stochasticity is similar to the stochastic OGDA in [Wei et al. 2021] with several substantial technical improvements. Theoretically, by tightly bounding the estimation error via a novel error decomposition, this paper obtains a significant sample complexity of $\\tilde{\\mathcal{O}}(\\frac{A_{\\max}}{\\epsilon^{5.5}(1 - \\gamma)^{13.5}})$, compared with the previous state-of-the-art result $\\tilde{\\mathcal{O}}(\\frac{A_{\\max}^3 |S|^{10.5}}{\\epsilon^8 (1 - \\gamma)^{29.5}})$.", "summary_of_the_review": "Overall, this paper is well written. The techniques of extending from a deterministic PE algorithm to a stochastic PE algorithm through Markovian sampling are similar as in [Wei et al, 2021], with novel design on the estimators and necessary adaptation to the PE framework. I am leaning towards accepting this paper but have some concerns about the novelty.", "strength_and_weaknesses": "", "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:

Meta-review: This work presents  a new sample-based policy extragradient algorithm for finding an approximate Nash equilibrium in tabular two-player zero-sum Markov games with improved sample complexity guarantees. While originally the reviewers had concerns regarding the novelty and technical difficulty of the paper, these were successfully resolved during the rebuttal, and now all reviewers agree that this is an interesting contribution. Hence, I recommend acceptance of the paper.

In the final version the authors should make the following changes:
- Please mention early on (e.g., in the abstract and the introduction, as well as in the definition of the Markov game) that you consider a tabular problem (finite state and action spaces). Furthermore, it would be important to define informally the quantities in the bound in the abstract and when presenting Table 1. 
- While not entirely uncommon, Assumption 1 is quite strong, requiring mixing for any policies. It would be great if the authors could also add a comment on this, emphasizing that this is the case, as well as explaining how weakening the assumption would introduce problems (as explained in the response to Reviewer RwGu).
- The comparison to the lower bound of Zhang et al. (2020) should also be included, as discussed in the response to Reviewer 5TU3.
- Please discuss Assumption 2 in relation to the work of Wei et al. (2021), and rephrase the relation to the latter paper accordingly, as promised in the discussion with Reviewer Hsr5.
Decision: Accept (Poster)