Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games
Authors: Sihan Zeng
Thinh T. Doan
Justin Romberg
Venue: NeurIPS 2022 Accept (2022)
Keywords: Markov game
reinforcement learning
minimax optimization

Abstract: We study the problem of finding the Nash equilibrium in a two-player zero-sum Markov game. Due to its formulation as a minimax optimization program, a natural approach to solve the problem is to perform gradient descent/ascent with respect to each player in an alternating fashion. However, due to the non-convexity/non-concavity of the underlying objective function, theoretical understandings of this method are limited. In our paper, we consider solving an entropy-regularized variant of the Markov game. The regularization introduces structures into the optimization landscape that make the solutions more identifiable and allow the problem to be solved more efficiently. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descent ascent algorithm converges to the Nash equilibrium of the original unregularized problem. We explicitly characterize the finite-time performance of the last iterate of our algorithm, which vastly improves over the existing convergence bound of the gradient descent ascent algorithm without regularization. Finally, we complement the analysis with numerical simulations that illustrate the accelerated convergence of the algorithm.

Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games
Sihan Zeng
Thinh Doan
Dept. of Electrical and Computer Engineering
Dept. of Electrical and Computer Engineering
Georgia Institute of Technology
Virginia Tech
Atlanta, GA 30318
Blacksburg, VA 24061
szeng30@gatech.ed edu
thinhdoan@vt.cmm edu
Justin Romberg
Dept. of Electrical and Computer Engineering
Georgia Institute of Technology
Atlanta, GA 30318 j wamndece.gatech....
Abstract
We study the problem of finding the Nash equilibrium in a two-player zero-sum Markov game. Due its formulation as minimax optimization program, natural approach to solve the problem is to perform gradient descent/ascent with respect each player in an alternating fashion. However, due the non-convexityynon- concavity of the underlying objective function, theoretical understandings of this our paper, we consider solving an entropy- reguuapzeggl variant of the Markov game. The regularization introduces structure into the opti- mization landscape that make the solutions more identifiable and allow the problem to be solved more efficiently. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descent ascent algorithm converges to the Nash equilibrium of the original unregularized problem. We ex- plicitly characterize the finite-time performance of the last iterate of our algorithm, which vastly improves over the existing convergence bound of the gradient descent ascent algorithm without regularization. Finally, we complement numerical simulations that illustrate the accelerated convergence of the algorithm.
method are limited.
analysis with
Introduction
The two-player zero-sum Markov game is a special case of competitive multi-agent reinforcement learning where two agents driven by opposite reward functions jointly determine the state transition in an environment. Usually cast as a non-convex non-concave minimax optimization program, this framework finds applications in many practical problems including game playing [Lanctot al.
2019 Vinyals et al., 2019), robotics [Riedmiller and Gabel 2007 Shalev-Shwartz et al. 2016 and
robust policy optimization PPinoo et al. 2017
convenient class of methods frequently used to solve multi multi-agent reinforcement learning problems the independent learning approach. Independent learning algorithms proceed iteratively with each player taking turns to optimize its own objective while pretending that the other players' policies are fixed to their current iterates. In the context of two-player zero-sum Markov games, the independent learning algorithm performs gradient descent ascent (GDA), which alternates between the gradient updates of the agents that seek to maximize and minimize the same value function. Despite
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the popularity of such algorithms in practice, their theoretical understandings are sparse and do not follow from those in the single-agent case as the environment not stationary from the eye of any agent. Daskalakis et al. 2017] shows that iterates of GDA can possibly diverge or be trapped in limit cycles even in the simplest single-state case when the two players learn with the same rate.
It may be tempting to analyze the two-player zero-sum Markov game by applying the existing theoretical results on minimax optimization. However, as the objective function Markov game not convex or concave, current analytical tools in minimax optimization that require the objective function be convex/concave at least on one side are inapplicable. Fortunately, the Markov game has its own structure: it exhibits a "gradient domination" condition with respect to each player, which essentially guarantees that every stationary point of the value function is globally optimal. Exploiting this property. Daskalakis et al. [2020) builds on the theory of Lin et al. [2020a] and shows that a two-time-scale GDA algorithm converges to the Nash equilibrium of the Markov game with complexity that depends polynomially on the specified precision. However, deriving an explicit finite-time convergence rate is still an open problem. addition, the analysis in Daskallkis et al. [0200 does not guarantee the convergence of the last iterate; convergence is shown on the average of all past iterates.
In this paper, we show that introducing an entropy regularizer into the value function significantly accelerates the convergence of GDA to the Nash equilibrium. By dynamicially adjusting the regular- ization weight towards zero, we are able to give a finite-time last-iterate convergence guarantee to the Nash equilibrium of the original Markov game.
Main Contributions
We show that the entropy-regularize regularized Markov game is highly structured; in particular, it obeys condition similar to the well-known oolyak-Lojasiewict condition, which allows linear convergence of GDA to the (unique) equilibrium point of the regularized game with fixed regularization weight. We also show that the distance of the equilibrium point of the regularized game to the equilibrium point of the original game can be bounded in terms of the regularizing weight.
We show that by dynamically driving the regularization weight towards zero, we can solve the original Markov game. We propose two approaches to reduce the regularization weight and study their finite-time convergence. The first approach uses a piecewise constant weight that decays geometrically fast, and its analysis follows case of fixed regularization weight. To reach a Nash equilibrium of the Markov game up to error e, we find that this approach requires at most ( 3) gradient updates, where O only hides structural constants. The second approach reduces the regularization weight online along with the gradient updates. Through multi-time-scale analysis, we optimize the regularization weight sequence along with the step size as polynomial functions of k where l is the iteration index. We show that the last iterate of the GDA algorithm converges to the Nash equilibrium of the original Markov game at rate of O(k- 1/3). Compared with the state-of- of-the-art analysis of the GDA algorithm without regularization which shows that the convergence rate of the averaged iterates is polynomial in the desired precision and all related parameters, algorithms enjoy faster last-iterate convergence guarantees.
straightforward consequence of our analysis for the
1.1 Related Work
A Markov game reduces to standard Markov Decision Process (MDP) with respect to one player if the policy of the other player fixed. This is an important observation that allows our work to exploit the recent advances in the analysis of policy gradient methods for MDPs (Nachum et al.) 2017 Neu
ct al. 2017 Agarwal ct al., 2020 Mei et al. 2020 Lan 2022). Various cntropy-based regularizers are introduced in these works that inspire the regularization of this paper. Our particular regularization is also considered by [en et al. [202T]. but we discuss and leverage structure in the regularized Markov game that was previously unknown.
As the two-player zero-sum Markov game can be formulated a minimax optimization problem. our work relates to the vast volume of literature in this domain. Minimax optimization has been extensively studied in the case where the objective function convex/concave with respect to at
least one variable [Lin et al. 2020a b Wang and Li, 2020 Ostrovskii et al. 2021]. In the general non-convex non-concave setting, the problem becomes much more challenging as even the notion
of stationarity is unclear (Jin et al. 2020]. In Nouiched et al. 2019). non-convex non-concave

---

objective functions obeying one-sided PE condition are considered, which the authors use to show the convergence of GDA. Yang et al. [2200 analyzes GDA under a two-sided PL condition and has a tight connection to our work as the value function of our regularized Markov game also has structure that is similar to, but weaker than, the Pt. condition on two sides.
By exploiting the gradient domination condition of a Markov game with respect to each player, Daskalakis et al. [2020] is the first to show that the GDA algorithm provably converges to a Nash equilibrium of a Markov game. A finite-time complexity is not derived in Daskalakis et al. [2020]. but their analysis and choice of step sizes indicate that the convergence rate is at least worse than O(k-1/10.5). Additionally, Daskalakis Daskallkki et al. (020) does not guarantee the convergence of the last iterate, but rather analyzes the average of all iterates. In contrast, our work provides a finite-time convergence analysis on the last iterate of the GDA algorithm.
While our work treats the Markov game purely from the optimization perspective, we would like to point out another related line of works that consider value-based methods [Perolat et al., 2015 Bai
and Jin 2020 Xie et al.] 2020 Cen et al. [021] Sayin et al., 2022]. In particular, Perolat et al. (011
among the first works extend value- baseee-bbdddde methods from single-agent MDP to two- two-player Markov games. Since then, the basic techniques for analyzing value- based methods for Markov games are relatively well-known. Bai and Jin [2020] considers a value iteration algorithm with confidence
bounds. In Cen et al. 2021]. J. a nested- loop algorithm is designed where the outer loop employs value iteration and the inner loop runs bimatrix game. In comparison, pure policy optimization algorithms are much less understood for Markov games, but this is an important subject to study due to their wide use in practice. In single- agent MDPs, value-basee methods and policy optimization methods enjoy comparable convergence guarantees today, and our work aims to narrow the gap between the understanding of these two classes of algorithms in two- two-player Markov games.
algorithm to solve regularized
Finally, we note the recent surge of interest in solving two-player games and minimax optimization programs with extragradient or optimistic gradient methods in the cases where vanilla gradient algorithms often cannot be shown converge (Chavdarova al. (219 Mokhtari et al.
2020
Li et al.
|022] Wei et al, 202T Zhao et al. 202T Cen et al. [001]] Chen et all (021]. These methods typically require multiple gradient evaluations each iteration and are more complicated to implement. Most
related to our work. Cen et al. [202T] shows the linear convergence of an extragradient algorithm for solving regularized bilinear matrix games. They also show that a regularized Markov game can be decomposed into series of regularized matrix games and present a nested-loop extragradient algorithm which solves these games successively and eventually converges to the Nash equilibrium of the regularized Markov game. The regularization weight can then be selected based on the desired precision of the unregularized problem. Although our overall goal of finding the Nash equilibrium of general Markov game is the same, the manner in which we decompose and analyze the problem different. Our analysis here is based on GDA applied directly to general regularized Markov game. We show that for fixed regularization parameter for a general Markov game, GDA has linear convergence to the modified equilibrium point. We also give a scheduling scheme for adjusting the regularization parameter as the GDA iterations proceed, making them converge to the solution to the original problem.
2 Preliminaries
We consider a two-player Markov game characterized by .M- = (S, 7, Here, S is the finite state space, AA and B are the finite action spaces of the two players, 7 E (0, 1) is the discount factor, and r : S x A x B > [0. 1] is the reward function. Let Ar denote the probability simplex over set F, and P S x A x B > As be the transition probability kernel, with P(s' |s s,a,b) specifying the probability of the game transitioning from state to s' when the first player selects action a E A and the second player selects E B. The policies of the two players are denoted by v E A and & E A with T[a s), d(b 8) denoting the probability of selecting action a, b in state according to π. G. Given a policy pair (T, Φ). we measure its performance in state E S by the value function
(s) = Eag~ (.0
* (Sk, ak. bx) |00 = s].
=]
k=o
Under a fixed initial distribution p As, define the discounted cumulative reward under (n, Φ)
J [ 6) A [
3

---

where the dependence on p is dropped for simplicity. is known that the Nash equilibrium always exists two-player zero-sum Markov games (Shapley 1953 i.c. there exists an optimal policy pair (x","" (6) such that
min [ 6) min max [TT, ④) = " TEAX PEAg
ΦEA TEA
However, as J is generally non-concave with respect to the policy of the first player and non-convex with respect to that of the second player, direct GDA updates may not find (s* ,d*) and usually exhibit an oscillation behavior, which we illustrate through numerical simulations Section Our approach to address this issue is to enhance the structure of the Markov game through regularization
2.1 Entropy-Reguulrizzed Two-Player Zero-Sum Markov Games
In this section we define the entropy regularization and discuss structure of the regularized objective function and its connection the original problem. Let the regularizers be
M1. (s, Ø) & (osma((
log π (ax 8%) 8o =
k=0
(8, σ) A (a
t log di (bx 88) 180 =
k=0
We define the regularized value function
(s) & V (s) + (H, T, Hols, T,
Fm Σ 7 ( au by) - log (ax (8)) log 6(bx (w))) 100
where T is a weight parameter. Again under fixed initial distribution p E As we denote (TT, σ) $ EVm The regularized advantage function is
A b) e r(s, a) b) log (aa) $) + r log o(b s) + [V (s),
which later helps to express the policy gradient.
We use d= E As to denote the discounted visitation distribution under any policy pair (N,, Φ) and the initial state distribution P
(8) - FF
k== EE 1
=s) ~
For sufficient state visitation, we assume that the initial state distribution is bounded away from zero
This is standard assumption in the matropy-regularizee MDP literature (Mei et al., 2020 Ying et al.
2022
Assumption
The initial state distribution p strictly positive for any state, and we denote Pmin minngs p(s) > 0.
When the policy of the first player is fixed to क E A the Markov game reduces to an MDP for the second player with state transition probability (s' s. = P(s') 8, a, b) (a s) and reward function (s b) = LocA r(s, a, b)T(( 8). A similar argument holds for the first player if the second player's policy is fixed. To denote the operators that map one player's policy the best response of the other player and the corresponding value function, we define
n (d) argmax J, (T, TEAS 9r (T) min Jr x) = (T. (T)). ΦE
d (T) A argmin (,
For any 7 >> 0, the following lemma bounds the performance difference between optimal and sub- optimal policies and establishes the uniqueness π. (Φ) and (T)). When O, we use m)()) and (D(T)) to denote one of the maximizers and minimizers since they may not be unique.

---

Lemma 1 (Performance Difference). Under Assumption ! and given T > 0, (Ø) is unique for any Ag. and (T( is unique for any A Given any min player policy & E Ag.
(=)==(0), J.( 0) 2 log(2) [T) T|?
Ppmin
Vi E A
(3)
Given any max player policy π E A
- J- 6) - 2 (0g
Tpmin ( - G11 vØ E Ag.
(4)
The Nash equilibrium of the regularized problem is sometimes referred to as the quantal response equilibrium [McKelvey and Palfrey| 1995] and is known to exist under any т. Leveraging Lemma [ we formally state the conditions guaranteeing its existence and affirm that it is unique.
Lemma 2 (Minimax Theorem for
Markov Game). Under Assumption 4 for any regularization weight T > 0, there exists a unique Nash equilibrium policy pair (mi, Q7) such that
max min Jr(m,, x) = min max J+ ()) (+(,, REAX SEAS
(5)
dEAg TEAS
We only interested in the solution of the regularized Markov game if it gives knowledge of the original problem in (T). In the following lemma, we show that the distance between the Nash equilibrium of the regularized game and that of the original one is bounded by the regularization weight. This is an important condition guaranteeing that we can find an approximate solution to the original Markov game by solving the regularized problem. In addition, this lemma also shows that the same policy pair produces value functions with bounded distance under two regularization weights.
Lemma 3. For any 2 +' 2 0 and policy
-Tr 4 7') log [B] S ( 07)) - Jr (T, 07,1 S (r -') log [Al.
(6)
(r - T') log |8| 5 (T) gr (T) = (+)))
S (T- (T))))
log [A].
(7)
T T- log |B| v (T の) (r, Φ)
T-
1 1-7 log AA.
(8)
2.2 Softmax Parameterization
In this work we use tabular softmax policy parameterization and maintain two tables @ e RSXA
RSB that parameterize the policies of the two players according
exp (0(s, a))
exp (1((8) b))
(a 8) Ed'es
and dw 8) = Evee exp (1(ss
E exp (f(s,
The gradients of the regularized value function with respect the policy parameters admit closed- form expressions
aJ, aJ Qv)
1
(s)TT(a) s) E bEB @b ()AAs (s, as,a,b))
a0(s,a)
1-
OJ, (Je Qv)
1
d Bo t
(b) EncA Ta (a| S)A (0,0000ss,,,, ())
(v(s,b)
and computing them exactly requires knowledge of the dynamics of the environment. Note that the gradients of value function and the regularizer are Lipschitz with respect to the policy parameters with constants Lv (1-7)² and I 1o8 Al This property is more formally stated and proved (1-
&
in Lemmas and o of the appendix.
We next present an important property that we will later exploit to study the convergence of the GDA updates to the solution of the regularized Markov game. Under the softmax parameterization, the regularized value function enjoys gradient domination condition with respect to the policy parameter that resembles the PL condition.
5

---

Lemma 4 (PL-Type Condition). Under Assumption
we have for any 0 E RSxA and v E RSxB
2(1 - P)
(T))
min Ta(a s) 8,8
(J+(T+ (TO, &b))),
[S]
(To, 2(1 7)
min 2 (b| (s) (J+(TT, - J. (TO. or (Too))))
|S|
8.6
The Pt. condition is a tool commonly used in the optimization community to show the linear convergence of the gradient descent algorithm [Karimi et al. 2016 Yu and Jin 2019 Khaled and Richtárik, 2020, Zeng et al. 2021b). The condition in Lemma is weaker than the common PL condition in two aspects. First, our PE coefficient a function of the smallest policy entry. When we seek to bound the gradient of the iterates [[V (TT,, vvr) )1² and [[ Oo)))l
>l1 later in the analysis, the PL coefficients will depend on min,,a To, (a s) and ming,b Qe. (6 s), which may not be lower bounded by any positive constant. Second, the coefficients involve т, which is not constant but needs be carefully chosen to control the error between the regularized problem and the original one.
3 Solving Regularized Markov Games
Leveraging the structure introduced in Section our first aim to establish the finite-time conver- gence of the GDA algorithm to the Nash equilibrium of the regularized Markov game under fixed regularization weight 0. The GDA algorithm executes the updates
(9) The convergence bound we will derive reflects trade-off for the regularization weight т: when is large, we get faster convergence to the Nash equilibrium of the regularized problem, but it is farther away from the Nash equilibrium of the original one. The result in this section will inspire the adjustment schemes designed later in the paper to achieve the best possible convergence to the Nash equilibrium of the original unregularized Markov game.
0x+1 = 02 + O (
th++1 = 1/x B& V Jr (TO, Dvr)
can be shown that the Nash equilibrium of the regularized Markov game is a pair of completely mixed policies, i.c. VT > 0 there exists c, > 0 such that min, x (a s) cr, and min,, (b () 2 Cr (Nachum et al. 2017]. In this work, we further assume the existence of uniform lower bound on the entries of (m,,, ) across r. We provide more explanation of the assumption in Remark [
Assumption 2. There exists a positive constant (independent of T) such that for any T >
min (a s) 2
min o (b
2
s.b
To measure the convergence of the iterates to the Nash equilibrium of the regularized Markov game, recall the definition of 9r in ( and define
% J+ ( (
(Tor),
= Der) 9r (TTL)
(10)
The convergence metric is asymmetric for two players: the first player is quantified by its performance when the second player takes the most adversarial policy, while the second player is evaluated under the current policy iterate of the first player. We note that 8% and 6% are non-negative, and o _% = 0 implies that (Tay. owr) ) is the Nash equilibrium. Under this convergence metric, the following theorem states that the GDA updates in 9 solve the regularized Markov game linearly fast. The proofs of the theoretical results this paper are presented in Section A of the appendix.
2
Theorem 1. We define L = 3Lx max 1}. C1
/1--7Pmmne and choose 64 [2g and C2
Pmin
the initial policy parameters to be Gg = 0 E R|S|x|AI and &so are uniform). Let the step sizes of be
and thu = 0 E R|S|x|6] (the initial policies no
ay = a,
B2 = B,
with a, 3 satisfying
a (1- 7) mmnn 2
CyL2 7
1
max (a, 33 S L B
min
152 log | 1 8), a S miin([.+
- p c27

---

If Assumptioo ?
holds and
30/ + 6 S CTT,
(11)
then the ieerats of satisfy for all k:
3 + 0% S (1 (1 aT P P ) (305 +.))
32 S
Theorem [ Testablishes the linear convergence of the iterates of to the Nash equilibrium of (5). provided that the initial condition (TT) is satisfied. The convergence is faster when is large and slower when T is small. Choosing to be large enough guarantees the initial condition (see Section C of the appendix for more discussion) but causes the Nash equilibrium the regularized Markov game to be distant from that of the original Markov game. This motivates us to make the regularization weight a decaying sequence that starts off large enough to meet the initial condition and becomes smaller over time to narrow the gap between the regularized Markov game and the original one. We discuss two such schemes of reducing the regularization weight in the next section.
Main Results Solving the Original Markov Game
This section presents two approaches to adjust the regularization weight that allow the GDA algorithm to converge to the Nash equilibrium of the original Markov game. The first approach uses piecewise constant weight and results in the nested-loop updates stated in Algorithm 1 In the inner loop the regularization weight and step sizes are fixed, and the two players update their policy iterates towards the Nash equilibrium of the regularized Markov game. The outer loop iteration reduces the regularization weight to make the regularized Markov game approach the original one. The regularization weight decays geometrically in the outer loop, i.e. Ta+1 IJTs, where E (0, 1) must be carefully balanced. On the one hand, recalling the definition of gr in and defining
87 = Jr, (T,,,
9r. (TT,,)) 6 Jr (T Per,) 9r, (T...)
we need 1) to be large enough that if 0r,0 and thx,0 observe the initial condition 357, + 0% CiTE. then do 82+1.0 and 11+1.0 in the worst case. On the other hand, 1) selected excessively large makes the reduction of T, too slow to achieve the best possible convergence rate. Our next theoretical result, corollary of Theorem ! properly chooses 1) and K, and establishes the convergence of Algorithm to the Nash equilibrium of the original original problem.
Algorithm 1: Nested-Loop Policy Gradient Descent Ascent Algorithm with Piecewise Constant Regularization Weight
Initialize: Policy parameters fo,0 = e R and t/o.0 = R step size sequences (az) and {BB,,, ). an initial regularization parameter To for f 0, 1... T do
for k = 0, 1.... K. do Max player update:
0r.411 = 0z,5 + az VoJr (o Dorc.)
2) Min player update:
Weck+1 = Ve.k 3, V. (. vvnn)
end
Set initial policies for next outer loop iteration 0z-1.0 0r, 1/2+1.0 = the,
Reduce regularization weight Te+1 = -yT, and properly adjust (it, ,t.
end
Corollary 1. Suppose that Assumption 2 hold and To chosen such that 363 + 06,0 < Ci
We choose 7j 20142Ls'
C, +2Ls where Ls log AA| + 3log [B]
log [B] and C1 defined in Theorem
'This inequality is guaranteed to hold with large enough To if neo and 4vo are initialized to be uniform. of the appendix for more discussion.
See Section of
7

---

Then, under proper choices of ar and Br, the iterates of Algorithm converge to a point such that J(T", x²) 9o (Trro) S and J PVr,a) go( S
(12)
in at most T = (loo(( outer loop iterations. The total number of gradient updates required is Ei=o Ke= = O
Corollary guarantees that (Toy Peyy. converge to an e-approximate Nash equilibrium of the original Markov game in T O( $) gradient steps. In order achieve this rate, Ke has to be adjusted along with Te: we need K2 (T, when 7, becomes smaller than 1. The varying number of inner loop iterations may cause inconvenience for practical implementation. To address this issue, we next propose another scheme of adjusting the regularization weight that is carried out online along with the update of the policy iterates.
Algorithm 2: Policy Gradient Descent Ascent Algorithm with Diminishing Regularization Weight
Initialize: Policy parameters A 0 R-S and 4/p 0 E RSx step size sequences {ax} and {.8}]. regularization parameter sequence {Tk}
for k = 0, 1.... K do
Max player update:
0 0% + Ork VoJra (TO. vva)
2) Min player update:
Wk+1 = 1/4 - 3B V Vo. (T0
end
Presented in Algorithm - the second approach is single-loop algorithm that reduces the regular- ization weight as a polynomial function of the iteration k. We define the auxiliary convergence metrics
5r Jr. (TT (7.) 9rc (To,),
5- Jr. (Tay vvr) 9r.. (Ta,))
which measure the convergence of (TO, (ea)) to the Nash equilibrium of the Markov game regularized with weight тę- To judge the performance of the iterates in the original Markov game, we are 9o (TT.). ). Thanks to
ultimately interested in bounding J(x", ,²") (0*)= (o(TT.)) and :
Lemma 3 we can quantify how fast 87 and d% approach these desired quantities as т. decays Under an initial condition on 0% and 0%. we now establish the convergence rate of Algorithm to (IT", (²)) of ① through multi-time-scale analysis.
Theorem 2. Let the step sizes and regularization parameter be
Tu
Og (k+ h)2/s
B Bo,
Tk (k + h)1/3'
with ang 3o, To, and h satisfying a system of inequalities discussed in details in the analysis.
Under Assumption the iterates of Algorithm 2 satisfy for all k 2 0
J(x", ,6) -90( CiTO + 3(log A|| + log BB)
(13)
3(k h)
(1 (1-7)Cmm + (log |A| + log [B))
Hmo, vvx) go(
(14)
- (k + h)//3
where the constant C1 is defined in Theorem
Theorem 2 states that the last iterate of Algorithm converges to an -1-3) (app-///)apprroximaat Nash equilibrium of the original Markov game in & iterations. This translates to the same sample complexity as Algorithm| deeiiedd in Corollary μ Compared with Algorithm I reducing тı online along with the gradient updates in single loop simplifies the algorithm and makes tracking the regularization weight, step sizes, and policy iterates simpler and more convenient. We note that the techniques in Daskalakis et al. 2020 may be used to analyze the finite-tima performance of GDA for Markoy games and lead to convergence rate at least worse than -k111100.5 which we improve over.
8

---

Remark 1. Assumption 2 is restrictive assumption that does not seem necessary but rather arises as an artifact of the current analysis. When we apply the weaker PL-type condition (Lemma ! in the analysis, the entries of the iterates n Pyr, need to be uniformly lower bounded, which is difficult to establish using the game structure. We come up with an innovative induction approach to quantify the connection between ming,a Te, (a 5), ming,5 Uue (b 8) and the optimal gap 5% & This approach allows to transform the uniform lower bound requirement T62 Qur to that on the Nash equilibrium, leading to Assumption 2 It is a future work to remove/velax this assumption.
A Markov game is said to be completely mixed if every Nash equilibrium of the game consists of a pair of completely mixed policies, i.e. mins,a x {a s) > O, mins, 6- (b > 0 for any Nash equilibrium (x', ,6)) ) of the Markov game (if more than one exists). Assumption 2 intuitively seems no stronger than requiring the original Markov game to be completely mixed. If the original Markov game has at least one completely mixed Nash equilibrium, the Nash equilibrium of the regularized Markov game should also be completely mixed even when the regularization weight is small, since the regularization encourages the solution to be more uniform. The reward function that results in completely mixed Markov games is well studied in Raghavan 1978), Kaplansky 1995]. Das et al. [2017].
5 Numerical Simulations
In this section, numerically verify the convergence of Algorithm 2 on small-scale synthetic Markov games. Our aim is to confirm that the algorithm indeed converges rather than to visualize the exact convergence rate, as achieving the theoretical rate derived in Theorem 2 requires very careful selection of all involved parameters. Considering an environment with |S| 2 and |A| = |B| 2,
we first choose the reward and transition probability kemel such that the Markov game completely
mixe
a.=
1e- 3. B. 1e 2, T4= (k+
11
a le= 3, le T0=0
de 1e=le- 3. B. 1e T2 =0
Convergence Metric
10
10
J(nt Unn''') 1 (m(
10
Rir 0-) go (mg)
Jm, " ()t
J(na,- Au.) - )o(
Ji - (.
J(m, Q.) gl(
100
100
10-1
10a
10-2
10-1
10-3
-1
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
10000
20000
30000
00000
50000
k
k
k
Figure 1: Convergence of GDA for Completely Mixed Markov game
1)-13 1/3 and We run Algorithm for 50000 iterations with a₁ 10 3, = 10-2 Th (k +
measure the convergence of म. and de by metrics considered in [3 and of Theorem 2 As shown in the first plot of Figure [ the last iterate exhibits initial oscillation behavior but converge smoothly after 10000 iterations. In comparison, we visualize the convergence of the last iterate and averaged iterate of the GDA algorithm without any regularization (second and third plots of Figure D.
where the average computed with equal weights as म - Ei= TB, OR x+T Σ Pvs- The existing theoretical results in this case guarantee the convergence of the averaged iterate but not the last iterate DDaskalakis et al. 2020]. According to our simulations, the last iterate indeed does not converge, while the averaged iterate does, but a slower rate than the convergence of the last iterate of the GDA algorithm under the decaying regularization.
The theoretical results derived in this paper rely on Assumption To investigate whether this assumption is truly necessary, we also apply Algorithm 2 to a Markov game that has a deterministic
"To create a completely mixed game with - = [B] such that r(s, :) as a 2x2 matrix is diagonal dominant or sub-diagonal dominant for any state s E S, and we can use an arbitrary transition probability kernel. The exact choice of the reward function and transition kernel well the Nash equilibrium of this Markov game presented in Section D of the appendix.
2, we simply need to choose the reward function

---

Nash equilibrium and does not observe Assumption As illustrated in Figure 2 the experiment shows that Algorithm 2 still converges correctly (T' 6*) of O This observation suggests that Assumption 2 may be artifact of the current analysis and motivates for us to investigate ways to remove/relax this assumption in the future. We note that the pure GDA approach without regularization also has a last-iterate convergence and does not exhibit the oscillation behavior observed in Figure | since the gradients of both players never change signs regardless of the policy of the opponent in this Markov game.
d,=
1e-lee- 3. 8. T (K
18
le 3. le-
le- 3, le- To
Convergence Metric
10a
10a
10-
j(n", (-) go(tte))
Jin [1) (- go(mo,)
Jmn "nn,,") go (fx)
10
jina, du) go(m).)
10a
Mina, tu.) go(rs.))
Ji... h.) gol
100
10-1
10-2
10-2
10-1
30000
50000
k
k
k
Figure 2: Convergence of GDA for Deterministic Markov game
6 Conclusion & Future Work
In this paper, we present the finite-time analysis of two GDA algorithms that provably find the Nash equilibrium of Markov game with the help of structured entropy regularization. Future directions of this work include formalizing the link between Assumption and completely mixed Markov games, investigating the possibility of relaxing this assumption, and characterizing the convergence of the stochastic GDA algorithm where the players do not have knowledge of the environment dynamics and can only take samples to estimate the gradients.
Acknowledgement
Sihan Zeng and Justin Romberg were supported in part by ARL DCIST CRA W91INF-17-2-0181 The work of Thinh T. Doan was supported in part by the Commonwealth Cyber Initiative.
References
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes, In Conference on Learning Theory, pages 64-66. PMLR, 2020.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference Machine Learning, pages 551-560. PMLR, 2020.
Pierre Bernhard and Alain Rapaport. On theorem of danskin with an application to theorem of von neumann-sion. Nonlinear Analysis: Theory, Methods & Applications, 2408):1133-1181, 1995.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34, 2021.
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. Advances in Neural Information Processing Systems, 32, 2019.
Ziyi Chen, Shaocong Ma, and Yi Zhou. Sample efficient stochastic policy extragradient algorithm for zero-sum markov game. In International Conference on Learning Representations, 2021.
The detailed description of the game is again deferred to Section D of the appendix.
10

---

Purba Das. T Parthasarathy, and G Ravindran. On completely mixed stochastic games. arXiv preprint arXiv:1703.04619, 2017.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. arXiv preprint arXiv:/711.0014/ 2017.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing systems, 33: 5527-5540, 2020.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconeee minimax optimization? In International Conference on Machine Learning, pages 4880-48899. PMLR, 2020.
Irving Kaplansky. A contribution von neumann's theory of games. ii. Linear algebra and its applications, 226:371-373, 1995.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-tojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer, 2016.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03329, 2020.
Guanghui Lan, Policy mirror descent for reinforcement learning: Linear convergence, new sampling
complexity, and generalized problem classes. Mathematical programming, pages 1 1-48, 2022.
Marc Lanetot, Edward Lockhart, Jean- -ap-tttt Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafici, et al. Openspiel: A framework for reinforcement learning games, arXiv preprint arXiv:1906 0e01199080945,,, 09453, 2019.
Chris Junchi Li, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael Jordan. On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging. International Conference on Artificial Intelligence and Statistics, pages 9793-9826. PMLR, 2022.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093, PMLR, 2020a.
Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2779. PMLR, 2020b.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games.
Games and Economic Behavior, 10(1):6-38, 1995.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829. PMLR, 2020.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra- estra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497-1507. PMLR, 2020.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances neural information processing systems, 30, 2017.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of retropy-rr markov decision processes. arXiv preprint I 2017.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.

---

Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-coneat smooth min-max problems. SIAM Journal on Optimization, 31 01:2508822336 2021.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, pages 1321-1329. PMLR, 2015.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference Machine Learning, pages 2817-2826. PMLR, 2017.
TES Raghavan. Completely mixed games and M-matrices. Linear Algebra and its Applications, 21 (1):35-45, 1978.
Martin Riedmiller and Thomas Gabel. On experiences a complex and competitive gaming domain: Reinforcement learning meets RoboCup. In 2007 IEEE Symposium Computational Intelligence and Games, pages 17-23. IEEE, 2007.
Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. SIAM Journal on Control and Optimization, 60(4):2095-2114, 2022.
Shai Shalev-Shwarzz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295. 2016.
Lloyd $ Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350-3344 2019, 2019.
Yuanhao Wang and Jian Li. Improved algorithms for convex-concave minimax optimization. Ad-
vances in Neural Information Processing Systems, 33:4800-4810 2020.
Chen-Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on Leurning Theory, pages 4259-4299. PMLR, 2021.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674-3682 PMLR, 2020.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of nonconvex-noncoonan minimax problems. arXiv preprint arXiv:2002.096621 2020.
Donghao Ying, Yuhao Ding. and Javad Lavaei. dual approach constrained markov decision processes with entropy regularization. In International Conference on Artificial Intelligence and Statistics, pages 1887-1909, PMLR, 2022.
Hao Yu and Rong Jin. On the computation and communication complexity of parallel sgd with dynamic batch sizes for stochastic non-convex optimization. In International Conference Machine Learning, pages 7174-7183. PMLR, 2019.
Sihan Zeng, Malik Aqeel Anwar, Thinh T Doan, Arijit Raychowdhury, and Justin Romberg. A decentralized policy gradient approach to multi-task reinforcement learning. In Uncertainty in Artificial Intelligence, pages 1002-1000 2012. PMLR, 2021a.
Sihan Zeng, Thinh T Doan, and Justin Romberg. A two-time-scale stochastic optimization framework with applications control and reinforcement learning. arXiv preprint arXiv:2109, 14756, 202
Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon S Du. Provably efficient policy gradient methods for two-player zero-sum markov games. arXiv preprint arXiv:2102.08903; 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Remark and Section S we discuss the assumption on the completely mixed Nash equilibrium that we currently have to make and how that may be an artifact in the analysis that can be relaxed in the future.
(c) Did you discuss any potential negative societal impacts your work? [No] The work is most of theoretical nature and does not have any direct societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the supplementary material we present the proof of all theorems and supporting lemmas.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] The code is in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] Not applicable. No training involved this work.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The experiment is very small-scale and the computational resource used is negligible.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We do not use existing assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] We do create assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A] We have not used crowdsourcing or conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xFHZFLF__dm", "reviewer": "Reviewer_KhY2", "summary": "This paper provided a new algorithm to find the Nash equilibrium for a two-player zero-sum Markov game. The new algorithm is based on a gradient descent with KL regularization. For completely mixed Markov games, the authors prove that the algorithm can find Nash equilibrium efficiently. They also conduct a simple experiment for tabular Markov games with low dimensions. The experiments support their main theoretical results and show that their algorithm may also work for the Markov games that are not completely mixed.", "questions": "1. How can we access the gradient $\\nabla J$?\n\n2. Can this algorithm be applied to Markov games with more complex structures?\n\n3. What's the advantage of the new algorithm compared with other algorithms that are designed for tabular settings such as [4]?\n\n\n[4] Bai, Yu, and Chi Jin. \"Provable self-play algorithms for competitive reinforcement learning.\" International conference on machine learning. PMLR, 2020.", "limitations": "The authors have addressed their work's limitations and potential negative social impact.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well organized, and the proofs seem sound to me. However, I still have several concerns about the clarity and significance of the main results. \n\n1. The main result of this paper only works for \"completely mixed Markov games.\" I would recommend the authors indicate that in the title. Otherwise, it would be kind of misleading. Moreover, completely mixed Markov games seem quite strong in the applications, which may limit the significance of the theoretical result.\n\n2. The authors conduct experiments and show that their algorithm may work for Markov games without completely mixed assumptions. However, the experiment is too simple to support their claims seems it is a tubular Markov game with dimension 2. \n\n3. One of the biggest advantages of using gradient descent to solve Markov games is that it can deal with complex models. However, this paper only conducted simple tubular Markov games by using a tabular softmax policy parameterization. Can the algorithm be applied to Markov games with more complex structures, such as with linear function approximation [1,2] or general function approximation [3]?\n\n4. This paper assumes that we can access the expected value function during the training and doesn't consider the exploration problem. \n\n\n[1] Xie, Qiaomin, et al. \"Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium.\" Conference on learning theory. PMLR, 2020.\n\n[2] Chen, Zixiang, Dongruo Zhou, and Quanquan Gu. \"Almost optimal algorithms for two-player Markov games with linear function approximation.\" arXiv preprint arXiv:2102.07404 (2021).\n\n[3] Huang, Baihe, et al. \"Towards general function approximation in zero-sum Markov games.\" arXiv preprint arXiv:2107.14702 (2021).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lEGeYfAZVX", "reviewer": "Reviewer_j9tp", "summary": "This paper shows last iterate convergence for regularized gradient descent-ascent on markov games with finite state and action space under the assumption that the smallest coefficients of the support of the regularized markov games are uniformly (uniformly lower bounded over the regularization parameter.) Additionally, the authors assume that the initial state distribution has a full support. ", "questions": "- After (1), you mention that J is non-concave with respect to the policy of the first player. But it seems to me that J is actually linear (with respect to the policy) since we have $$V^{\\lambda \\pi_1 + (1-\\lambda)\\pi_2,\\phi} = \\lambda V^{\\pi_1,\\phi}  + (1-\\lambda) V^{\\pi_2,\\phi}$$ (playing according to the mixed policy is equivalent to tossing a coin and playing according to either the first or the second policy). Can you comment on that point?\n- What is your opinion on the optimal convergence rate? Are there lower bounds ? (since the problem is nonconcave-nonconvex in the parameters pre-softmax the standard convex-concave lower bounds do not hold) \n- It seems that Assumption 2 could be connected to the Maximum entropy Nash (MaxEnt). (the lower bound should be on the support of the MaxEnt. One way to prove such a result could be by saying that the MaxEnt is the limit of the regularized Nash. Since the Regularized Nash always has full support (the regularization goes to +\\infty for non-full support solutions) and its limit (the MaxEnt for no regularization and the uniform distribution for infinite regularization) also has full support, there exists a (uniform) lower bound on the support of any regularized Nash. However, it does not show that this lower bound is the lower bound on the MaxEnt (which seems intuitively true). Any comment on that?\n\n\nI will be eager to increase my score if the authors answer my questions and are able to show that Assumption 2 can be relaxed. ", "limitations": "- This work is limited to the full batch case which is not practical.\n- The proposed rate may be suboptimal. It could be interesting to investigate experimentally different decays ($1/t$, $1/\\sqrt{t}$). \n- Also a log-log scale for the plots could help to visualize the experimental convergence rate. \n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nstrengths:\n- To the extent of my knowledge, the result seems novel and relevant to the community.\n- This paper is well written. \n\nweaknesses: \n- Assumption 2 is strong and does not seem necessary.\n- There is no discussion on the optimality of the rate proposed rate. \n- Algorithm is not practical since one needs access to the (full) gradient of J.\n- The authors could do more experiments to investigate these questions left open. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_VEA53u8QOrU", "reviewer": "Reviewer_C5Kb", "summary": "This work studies the so-called two-player zero-sum Markov game. They provides theoretical analysis of the convergence (to the Nash equilibrium) of practical gradient descent ascent (GDA) algorithms with some new numerical tools. In particular, they introduce an entropy regularization to the value function of the original game, and shows the linear convergence of GDA to the equilibrium point of the regularized game.\n\nIn addition, in order to derive practical algorithms to solve the original problem, they also studies a critical parameter, the weight parameter of the regularizer. Since there is a clear trade-off between improving convergence rate and minimizing the gap between the regularized game and the original one, they provide some practical schemes to adjust the regularization weight. The hope is that when the regularization weight is iteratively reduced to zero, the GDA algorithm will converge to the Nash equilibrium of the original game and hence the original game will be solved.", "questions": "The questions are listed above.", "limitations": "no.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper is well-written, self-contained and organized. \n2. This work extends the current research on finding the Nash equilibrium of two-player zero-sum Markov game. They provide significant contributions to convergence analysis of practical gradient-based algorithms.\n3. They also derive some practical algorithms to apply their regularization technique to solve the original game.\n\nWeakness:\n1. The description of the numerical experiments part is too simplified. I would like to see more details, for example, more information about the game environment, why the current setting of the synthetic game is chosen, more analysis on the results.  Although some of the details have been provided in appendix, but I think that is not enough, and some details should be put into the main paper.\n2. The role of Assumption 2 played in the main results of this work is not clear. As the paper itself mentioned, some of the experimental results show that the Algorithm 2 still converges correctly when it is applied to a Markov game that does not observe Assumption 2. \n3. In some of experimental results,  the pure GDA approach without regularization also has a last-iterate convergence and does not exhibit the oscillation behavior. Did the authors choose an appropriate game environment to valid their contributions?\n4. The idea of introducing an entropy regularizer to improve the structure of the game is straightforward.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KPoRmJ2IQHO", "reviewer": "Reviewer_7QJ7", "summary": "This paper develops policy gradient algorithms for entropy-regularized zero-sum games. Under some assumptions, the authors show that the entropy-regularized objective function obeys a Polyak-Łojasiewicz type condition, which allows linear convergence of policy-gradient-based GDA to the equilibrium point of the regularized game. Then, the authors propose two scheduling schemes for the regularization parameter and analyze their convergence and complexities. ", "questions": "Overall, the paper is well written, and the references are properly cited. I have the following questions/comments.\n\n1. Entropy-regularized zero-sum game has been studied in the existing literature (Cen 2021), and I think this paper provides a policy-gradient-based solution and complexity analysis. \n\n2. The convergence metric used in this paper is different from the duality gap metric used in Cen 2021, is there a connection between these two metrics? How do your convergence rate and complexity compare with those established in Cen 2021?\n\n3. Comparing with the analysis of Cen 2021, the authors stated that they discuss and leverage structure in the regularized Markov\ngame that was previously unknown. While I agree that the policy gradient approach and PL condition of the Entropy-regularized zero-sum game were not discussed in Cen 2021, their analysis actually leverages certain similar structures implicitly. Specifically, Cen 2021 follows the standard value iteration algorithm that has a linear convergence rate. In the inner loop, they need to solve an entropy-regularized bilinear matrix game, which satisfies a strongly-convex-strongly-concave type geometry due to the entropy regularization (w.r.t to the $\\ell_1$ norm). In their convergence proof, this geometry helps them achieve a linear convergence. ", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: comprehensive theoretical result.\n\nWeakness: It is still not clear why Assumption 2 is needed and justifiable. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept