Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
Authors: Shicong Cen
Yuting Wei
Yuejie Chi
Venue: NeurIPS 2021 Poster (2021)
Keywords: zero-sum matrix game
zero-sum Markov game
entropy regularization
global convergence
multiplicative updates
extragradient methods

Abstract: This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled as a constrained saddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods in the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, especially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization in single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods to find the quantal response equilibrium (QRE)---which are solutions to zero-sum two-player matrix games with entropy regularization---at a linear rate. The proposed algorithms can be implemented in a decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own payoff without observing the opponent's actions directly.  In addition, by controlling the knob of entropy regularization, the proposed algorithms can locate an approximate Nash equilibrium of the unregularized matrix game at a sublinear rate without assuming the Nash equilibrium to be unique. Our methods also lead to efficient policy extragradient algorithms for solving entropy-regularized zero-sum Markov games at a linear rate. All of our convergence rates are nearly dimension-free, which are independent of the size of the state and action spaces up to logarithm factors, highlighting the positive role of entropy regularization for accelerating convergence.


Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
Shicong Cen
Yuting Wei University of Pennsylvania ytwei@wharton. upenn edu
Yuejie Chi Carnegie Mellon University yuejiechi@cmu. edu
Carnegie Mellon University shicongc@andrew. cmu. edu
Abstract
This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled constrained aaddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, espe- cially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods find the quantal response equilibrium (QRB)-whid) are solutions to zero-sum two-player matrix games with entropy regularization- at linear rate. The proposed algorithms be implemented in decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own payoff without observing the opponent's 's actions directly. In addition, by controlling the knob of entropy regularization, the pro- posed algorithms can locate approximate Nash equilibrium of the unregularized matrix game at sublinear rate without assuming the Nash equilibrium to be unique. Our methods also lead efficient policy extragradient algorithms for solving cntropy-regulanee
zero-sum Markov games at a linear rate, All of our convergence rates are nearly dimension -free, which are independent of the size of the state and action spaces up to logarithm factors, highlighting the positive role of entropy regularization for accelerating convergence.
Introduction
Finding the equilibrium of competitive games, which can be viewed as constrained saddle-point optimization problems with probability simplex constraints, lies at the heart of modern machine leam- ing and decision making paradigms such as Generative Adversarial Networks (GANs) (Goodfellow al., 2014), competitive reinforcement learning (RL) [Littman] 1994). game theory (Shapley 1953)
adversarial training (Mertikopoulos et al. 2018b), to name a few.
In this paper, we study one of the most basic forms of competitive games, namely two-player zero-sum games, in both the matrix setting and the Markov setting. Our goal is to find the equilibrium policies of both players in independent and decentralized manner (Daskalakis (2211a) with guaranteed last-iterat convergence. Namely, each player will exccute symmetric and independent updates iteratively using its own payoff without observing the opponent's actions directly, and the final policies the iterative process should be close approximation to the equilibrium up to any preseribed precision. This kind of algorithms is more advantageous and versatile especially in federated environments, as it requires neither prior coordination between the players like two- timescale algorithms, a central controller collect and disseminate the policies of all the players, which are often unavailable due to privacy constraints.
al. 2020 Wei et al.)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1 Last-iterate convergence in competitive games
In recent years, there have been significant progresses in understanding the last-iterate convergence of simple iterative algorithms for unconstrained saddle-point optimization, where one is interested in bounding the sub-optimality of the last iterate of the algorithm, rather than say, the ergodic iterate which is the average of all the iterations that commonly studied in the earlier literature. This shift of focus is motivated, for example, by the infeasibility of averaging large machine learning models in training GANs (Goodfellow et al.) 2014). While vanilla Gradient Descent/ / Ascent (GDA) may diverge or cycle even for bilinear matrix games (Daskalakis et al.] 2018). quite remarkably, small modifications lead to guaranteed last-iterate convergence to the equilibrium in non-asymptotic fashion. A flurry of algorithms is proposed. including Optimistic Gradient Descent Ascent (OGDA)
(Rakhlin and Sridharan 2013 Daskalakis and Panageas 2018b Wei al. 2021b), predictive updates (adav et al. (2017). implicit updates (Liang and Stokes 2019), and more. Several unified analyses of
these algorithms have been carried out (see, e.g. Mokhtari al. (2020a) Liang and Stokes (2019) and references therein), where these methods in principle all make clever extrapolation of the local curvature in a predictive manner to accelerate convergence. With slight abuse of terminology, in this
paper. we refer to this ensemble of algorithms as extragradient methods (Korpelevich) 1976 Tseng 1995: Mertikopoulos et al., 201 Sa: Harker and Pang 1990).
However, saddle-point optimization in the constrained setting, which includes competitive games as special case, remains largely under-explored even for bilinear matrix games. While it is possible to reformulate constrained bilinear games to unconstrained ones using softmax parameterization of the probability simplex, this approach falls short of preserving the bilinear structure and convex- concave properties in the original problem, which are crucial to the convergence of gradient methods. Therefore, there is strong necessity of understanding and developing improved extragradient methods in the constrained setting. Daskalakis and Panageas (2018a) proposed the optimistic variant of the multiplicative weight updates (MWU) method (Arora et | 2012)- which extremely natural and popular for optimizing over probability simplexes - called Optimistic Multiplicatiiee Weight Updates (OMWU), and established the asymptotic last-iterate convergence of OMWU for matrix games. Very recently. Wei et al. (202Tb) established non-asymptotic last-iterate convergences of OMWU. However, these last-iterate convergence results require the Nash equilibrium to be unique, and cannot be applied to problems with multiple Nash equilibria.
1.2 Our contributions
Motivated by the algorithmic role of entropy regularization in single-agent RL (Neu et al. 2017 Geist et al.] [219]] Cen et al. 2020) as well as its wide use in game theory to account for imperfect and noisy information (McKelvey and Palfrey, 1995 Savas et al.] 2019), we initiate the design and analysis of extragradient algorithms using multiplicative updates for finding the quantal response equilibrium (QRE), which are solutions to competitive games with entropy regularization (McKelvey and Palfrey 1995). While finding QRE is of interest in its own right, by controlling the knob of entropy regularization, the QRE provides a close approximation to the Nash equilibrium (NE), and in turn acts smoothing scheme for finding the NE. Our contributions summarized below.
Near dimension-free last-iterate convergence to QRE of catropy-regularzzer matrix games. We propose two policy extragradient algorithms to solve entropy-regularte Predictive Update (PU) and OMWU methods, where both players execute symmetric and multiplica- tive updates without knowing the entire payoff matrix nor the opponent's 's actions. Encouragingly. we show that the last iterate of the proposed algorithms converges to the unique QRE at a linear rate that is almost independent of the size of the action spaces. Roughly speaking, to find an e-optimal
matrix games, namely the
QRE in terms of Kullback-Leibler (KL) divergence, it takes no more than δ log (t)) iterations,
where Ö()) hides logarithmic dependencies. Here, T is the regularization parameter, and 1) is the learning rate of both players. Maximizing the learning rate, the iteration complexity is bounded by Ô ((1 + [T) log()/))), where || = max., |At,l is the for norm of the payoff matrix A.
Last-iterate convergence to e-NE of unregularized matrix games without uniqueness assumption. The QRE provides an accurate approximation to the NE by setting the entropy regularization T sufficiently small, therefore our result directly translates to finding NE with last-iterate convergence guarantee. Roughly speaking, to find an e-NE (Zhang et al., 2020 Definition 2.1). it takes no more iterations with optimized learning rates, which is again independent of the size than δ (1 ||Al)>))
2

---

Equilibrium
Require
Method
Convergence rale
Dimension-free
type
unique NE
PU & OMWU
c-QRE
(this work)
linear
yes
n/a
OMWU
Daskalakis and Panageas 2018a)
asymptotic
n1
yes
eNNB
Wei et al. 2021b
OMWU
sublinear linear
yes
PU & OMWU
(this work)
sublinear
yes
Comparisons of last-iterate convergence of the proposed entropy-regularizzd PU and OMWU methods with prior results for finding c- c-QRE or c-NE competitive matrix games. We note that the convergence rates of unregularized OMWU established in Wei et al. (2021b) are problem- dependent, and scale at least polynomially on the size of the action spaces. Desirable features in the last two columns are highlighted in blue.
Table 1:
of the action spaces up to logarithmic factors. Unlike prior literature (Daskalakis and Panageas 2018 8a: Wei et al. 202Tb), our last-iterate convergence guarantee does not require the NE to be unique.
Extensions to two-player zero-sum Markov games. By connecting value iteration with matrix games, we propose a policy extragradient method for solving mdinite-horizon discounted entropy- regularized zero-sum Markov games, which finds an e-optimal minimax soft Q-function--a iitetioon-inni terms of
Lo error in at most (7(1-))z log? (t) iterations, where y E (0, 1) is the discount factor.
To the best of our knowledge, our paper is the first that develops policy extragradient algorithms for solving entropy rngropy-regularrize competitive games with multiplicative updates and dimension- smoothing technique
linear last-iterate convergence, and demonstrates entropy regularization to find e-NE without the uniqueness assumption. Table provides detailed comparisons of the proposed methods with prior arts for solving matrix games. Our results highlight the positive role of entropy regularization for accelerating convergence and safeguarding against imperfect information in competitive games. We defer the complete proof of our results to
Cen et al. (2021).
1.3 Related works
Our work lies at the intersection of saddle-point optimization, game theory, and reinforcement learning. In what follows, we discuss a few topics that are closely related to ours.
Unregularized matrix game. Freund and Schapire (9999) showed that many standard methods such as GDA and MWU have converging average duality gap at the rate of O(1 (T), which is improved to OL1/T) by considering optimistic variants of these methods, such as OGDA and al., 2015). However, the last-iterate convergence of these methods are less understood until recently (Daskalakis and Panageas 2018a| Wei et al. 2021b). In particular, under the assumption that the NE is unique for the unregularized matrix game, Daskalakis and Panageas (2018g 8a) showed the asymptotic convergence of the last iterate of OMWU to the unique equilibrium, and Wei et al. (202Tb) showed the last iterate of OMWU achieves linear rate of convergence after initial phase of sublinear convergence, however the rates therein can be highly pessimistic in terms of the problem dimension, while our rate for entropy-regularize OMWU is dimension-fin free up to logarithmic factors.
OMWU (Rakhlin and Sridharam, 2013) Daskalakis et al., 2011 Syrgkanis
Saddle-point optimization. Considerable progress has been made towards understanding OGDA and extragradient (EG) methods in the unconstrained convex-concave saddle-point optimization with general objective functions (Mokhtari et al., 2020aa] b) [emirovskii 2004] [iang and Stokes| 2019). However, the last-iterate convergence of constrained convex-concave saddle-pont point optimization still lacks theoretical understanding in general and most works fall short of characterizing a finite-time convergence result. In particular, Mertikopoulos et al. (2018a) demonstrated the asymptotic last- iterate convergence of EG, and Hsieh et al. (2019) investigated similar questions for single-call EG algorithms. Lei et al. (2021) showed that OMWU converges to the equilibrium locally without

---

an explicit rate. Wei et al. (2021b) showed that the last-iterate of OGDA converges linearly for strongly-convex strongly-cone concaave constrained saddle-point optimization with an explicit rate.
Entropy regularization in RL. and games. In single-agent RI., the role of entropy regularization as
an algorithmic mechanism to encourage exploration and accelerate convergence has been investigated extensively (Neu et al. 2017 Geist et al., [019] Mei et al., 22020] Cen et al. 2020 Lan 2021 Zhan al. 2021). Turning to the game setting, entropy regularization used to account for imperfect
information in the seminal work of McKelvey and Palirey (995) that introduced the QRE, and a
few representative works on entropy and more general regularizations in games include [Savas et al.
(2019): Hofbauer and Sandholm 2002 Mertikopoulos and Sandholm (2016).
Zero-sum Markov games. There have been a significant recent interest in developing provably efficient self-play algorithms for Markov games, including model-based algorithms (Perolat et al.)
2013 Zhang et al.) 2020), nalue-based algorithms (Bai and Jin 2020 Xie et al.. 2020)) and policy-
based algorithms (Daskalakis et al., 2020; Wei et al., 2021a Zhao et al. 2021). The iteration complexities in prior works (Perolat et al. 2015 D Dakis et 2020 Wei et al.) 2021a] Zhao itt al. 2021) depend on various notions of concentrability coefficient and therefore can scale quite pessimistically with the problem dimension. Our approach can be regarded as a policy-based algorithm to approximate value iteration, which can be implemented in a decentralized manner with symmetric and multiplicative updates from both players, and the iteration complexity is almost independent of the size of the state-action space.
Notation. We denote by A(A) the probability simplex over the set A. We overload the func- tions such as log(.) and exp(-) to take vector inputs with the understanding that the function is applied in entrywise manner. For instance, given any vector = [zi]ısign tion exp(z) denotes exp(z) == [exp(z)]ısisw) other functions are defined analogously. Given two probability distributions μ and p' over A, the KL divergence from μí' to μ is defined by KL ll (²)== == EaeA pla) log p(aa)- Given a matrix A, ||All is used to denote entrywise maximum norm, namely, |a = max.;; |A,yl. The all-one vector is denoted as 1.
TR" the nota-
s(a)
2 Zero-sum matrix games with entropy regularization
We first consider two-player zero-sum game with bilinear objective and probability simplex constraints, and demonstrate the positive role of entropy regularization in solving this problem. Throughout this paper, let A {I....,m) m] and [l...., ,n] be the action spaces of each player.
2.1 Background and problem formulation
Zero-sum two-player matrix game. The focal point of this subsection is a constrained two-player zero-sum matrix game, which can be formulated the following min-max max problem (or saddle point optimization problem):
max min HE (E)()) WEA(B)
(U = 1 Au,
where A E Ruxn denotes the payoff matrix, l E A(A) and E A(B) stand for the mixed/randomized policies of each player, defined respectively as distributions over the proba- bility simplex A(A) and A(B). A pair of policies (μ², v²) is said to be a Nash equilibrium (NE) of ①[ if f("", v) 2 f(u", v*)= 2 f(u, I*)
for all (H,v) E A(A) x A(B).
Entropy-regularizer zero-sum two-player matrix game. There is no shortage of scenarios where the payoff matrix A might not be known perfectly. In an attempt to accommodate imperfect knowledge of McMellvyy and Palfrey (1993) proposed a seminal extension to the Nash equilibrium called the quantal response equilibrium (QRE) when the payoffs are perturbed by Gumbel-distributed noise. Formally, this amounts to solving the following matrix game with entropy regularization (Mertikopoulos and Sandholm 2016):
max min Jr (1, :- =I Of (EA(A) (EA(B)
Au A HH()) - TH(v).
where H(T)) = - E; n. log(T,) (T;) denotes the Shannon entropy of a distribution n, and 2 the regularization parameter. As is well known, the optimal solution v;) to (2). dubbed as the QRE,

---

is unique whenever > 0 (due to the presence of strong concavity/convexttyy which satisfies the following fixed point equations:
for all E A, 1 (+(aa Σem exp (b))77 x exp((Av/]a/T))
cxp([Ar_]o/T)
(3)
exp (./TT) (b) Ed -xp m2lb/r) & (xp(-[AA/4]b/> for all E B.
Goal. We aim efficiently compute the QRE of the entropy-regularized matrix game in decen- tralized manner, and investigate how an efficient solver of QRE can be leveraged to find NE of the unregularized matrix game (T). Namely, we only assume access "first-order information" as opposed to full knowledge of the payoff matrix A or the actions of the opponent. The information received by each player formally described in the following sampling oracle.
Definition 1 (Sampling oracle for matrix games), For any policy pair (n, v) and payoff matrix A, the sampling oracle returns the exact values of p. and Av.
Additional notation. For notational convenience, let ( represent the concatenation of p IR and Ri namely, < (H, The solution to (2, which is specified in (3). is denoted by G = (n,, vF). For any Ç = (1, and Ç² = (1L, v²), we shall often abuse the notation and let ( = KL n²) + (KL(v|//) The duality gap of the entropy-regularized matrix game (2) at <= (,, is defined as DualGap,(() = maxp'eΔ(A) I=(p',
() [+ v/) which O. Similarly, let the optimality gap of the entropy- regularized matrix game 2 Ç (1, be OptGap(() (M, (ft (r(,,
clearly nonnegative and DualGap,(C3)
2.2 Proposed extragradient methods: PU and OMWU
To begin, assume
A(A), 22 ABB) employed by each player respectively. If we proceed with fictitious play, i.e. player 1 (resp. player 2) aims to optimize its own policy by assuming the opponent's 's policy is fixed 22 (resp. 21 the saddle point optimization problem 2 then decoupled into two independent min/max optimization problems:
given pair of policies
max (AA(A)
11 A + (H( 72(22) and
A +H(()) TH(P), vEA(B)
min
which are naturally solved via mirror descent/ ascent with KL divergence. Specifically, one step of mirror descent/ ascent takes the form
n (a) (a) exp(n[Az2la),
for all E A,
(4)
((++)(()) x 110 (6)) 1- exp(-n(A" 21)6, for all E B,
where 7) the learning rate. The above update rule forms the basis of algorithm design.
Motivation: a form implicit updates with linear convergence. turns out, we could select the policy pair (21, 22) ((++1) : (p(t+)), ((+1) as the ones to be taken in the future, and call the resulting update rule as the Implicit Update (IU) method:
1 (a) n (a) 1- exp(n) exp(n]Au((42)),)
for all E A,
Implicit Update:
(5)
(((+1)()) & (b) 1
((0+1))) for all b B.
Though unrealistic since it uses the future updates it leads one-step convergence the QRE when 17 = 1/T (see the optimality condition in
3 Encouragingly, we have the following linear convergence guarantee of IU when adopting a general learning rate.
Proposition (Linear convergence of IU). Assume 0 < 1) 1/T, then for all f. 2 0, the iterates ((0) : (1,(t) (() of the IU method in satisfy KL(C; |1 (0) < (1 KL (0)).
In words, the IU method achieves an appealing linear rate of convergence that independent of the problem dimension. Motivated by this observation, we seek to design algorithms where the policies (2) 22) employed in 4 serve as good predictions (f(++1), y(++)) 1)), such that the resulting algorithms are both practical and retain the appealing convergence rate of IU.
Proposed algorithms. We propose two extragradient algorithms for solving the antropy-regularize matrix game, namely the Predictive Update (PU) method and the Optimistic Multiplicative Weights
5

---

Algorithm 1: The PU method
Algorithm 2: The OMWU method
initialization:
initialization: μ 7 v(0 plo).
for f 2,2, do
for i = 0, 1, do
Update and E/ according to
3
Update f and V according to
(a) x (a)" " "F exp(n[AAe()] la), (b) x (b) -- exp(-n/ A (1)
pltt)(a) x (a) " " exp()[A((())))
(l) (b) o" exp( exp(-n[A4 | A ((
Update y and according to
Update μ and according to
(a) (a) or (() x vlt)()) 'm exp(-1/l AAA (1(0)11))).
exp(n) exp(n[Abitt1jj
(a) x (a)" "-
exp()|Au(+))aa)
(l)+))(b)) x (b) exp( (n TTTTTpplA (((tt))o).
Update (OMWU) method, the latter adapted from Rakhlin and Sridharan (2013); Daskalakis et al. (201T). Detailed procedures can be found in Algorithm [ and Algorithm
2 respectively. On a high
level, both algorithms maintain two intertwined sequences {(u(t), v(0) J:20 and { )(20. and in each iteration & = 0, o,..... proceed in two steps:
The midpoint (1((+1),, p(+++)) serves as a prediction of (1((++1), (((()))))))) by running one step of
mirror / ascent (cf. (4) from either (z1, =2) = (n(0), u(0) (for PU) or (21, =2) = (jz(0, ((t) (for OMWU).
The update of (n(++11 ,((+)) then mimics the implicit update (((+)1)((+43 obtained above.
5 using the prediction
When the proposed algorithms converge, both (1(() (0) and (n a(0) converge to the same point. The two players are completely symmetric and adopt the same learning rate, and require only first-order information provided by the sampling oracle. While the two algorithms resemble each other in many aspects, a key difference lies in the query and use of the sampling oracle: in each iteration, OMWU makes a single call to the sampling oracle for gradient evaluation, while PU calls the sampling oracle twice. It is worth noting that, when r = O (i.e., no entropy regularization is enforced), the OMUU method in Algorithm 2 reduces to the method analyzed in Rakhlin and Sridharan (2013):
Daskalakis and Panageas (2018a); Wei et al. (202Tb) without entropy regularization.
Remark 1. It is worth highlighling that the proposed algorithms are different from Mertikopoulos el al.) (2078a), as the extragradient is only applied to the bilinear term but not the entropy regular- ization term. This seemingly small, but important, difference leads to more concise closed-form update rule and a cleaner analysis, as shall be seen momentarily.
2.3 Performance guarantees
We are now positioned to present our main theorem concerning the last-iterate convergence of PU and OMWU for solving (2).
Theorem (Last-iterate convergence of PU and OMWU). Suppose that the learning rates 1 = 7PPU of PU in Algorithm 7 and 17 nomwu of OMWU in Algorithm 2 satisfy
0 < TPU S + ||l and << NjoMwu S min
(6)
2r + 2||
4 ||A
Then for any t 2 0, the iterates ((t) = (1(1)) v(t) and g00) = (1(*), El of PU and OMWU achieve
Linear convergence of policies in KL divergence and entrywise log-ratios:
max (KL(<) 11 ((9), 1KL 11 ((+11))
< (1 (L=)))
(7a)
log (())
(0))
8 8|| x (1 - (1- 1/2
< 2 77)
log
+
(7b)
+

---

Linear convergence of values in optimality and duality gaps:
(1- 177)
OptGap, (5 17 1- (T (1ll00))))))) 1- 17)² KL KL(ct 1(
(7c)
DualGap;(<")) - +- (L- (1)
(7d)
Remark 2. Setting (0)) and (0) be uniform policies leads to a universal bound
(1 l1
loI + log [B] --((())) - H(v)) S log |A| + log IB).
Remark 3. Similar results continue to hold even when the two players use different regularization
parameters Tuy Tv > 0 in 2 as long as the regularization parameter T replaced by max (uu Tul in the upper bounds of the learning rate, and the contraction parameter is replaced by 1- min Tip Tuhn
Theorem characterizes the convergence of the tust-iterates (()) and ((t) of PU and OMWU as long as the learning rate lies within the specified ranges. While PU doubles the number of calls to the sampling oracle, it also allows roughly as large as twice the learning rate compared with OMWU (cf. (6)) Compared with the vast literature analyzing the average-iterate performance of variants of extragradient methods, our results contribute towards characterizing the last-iterate convergence of multiplicative update methods in the presence of entropy regularization and simplex constraints, which to the best of our knowledge, are the first of its kind. Several remarks are in order.
Linear convergence QRE. To achieve an e-accurate estimate of the QRE in terms of the KL divergence, the bound (7a) tells that it is sufficient to take
1
log |A| + log [
log
iterations using either PU OMWU. Notably, this iteration complexity does not depend any hidden constants and only depends double logarithmically on the cardinality of action spaces, which is almost dimension-free. Maximizing the learning rate, the iteration complexity is bounded by (1 + || (og(1)e) (modulo log factors), which only depends on the ratio ||A||
Entrywise error of the policy log-ratios. Both PU and OMWU enjoy strong entrywise guarantees in the sense we can guarantee the convergence of the Loo norm of the log-ratios between the learned policy pair and the QRE at the same dimension-free linear rate (cf. (7b)). which suggests the policy pair converges in a somewhat uniform manner across the entire action space.
Linear convergence of optimality and duality gaps. Our theorem also establishes the last-iterate convergence of the game values in terms of the optimality gap (ef. (7ch) and the duality gap (cf. (7d) for both PU and OMWU. In particular, as will be seen, bounding the optimality gap of matrix games turns out to the key enabler for generalizing our algorithms to Markov games, and bounding the duality gap allows to directly translate our results to finding NE of unregularized matrix games.
Last-iterate convergence approximate NE. The entropy-regularize matrix game can be thought as smooth surrogate of the unregularized matrix game (T); in particular, it is possible to find an e-NE by setting 7 sufficiently small in 2). According to (Zhang et al. 2020 Definition 2.1), a policy pair Ç (p, v/) is an c-NE if it satisfies DualGap(S) == (EA(())
T/ v) minwea(()) f(,, v') S c.
e/1 Observe that setting T log +log Bi guarantees that [f- v) f(u, D) < c/4 uniformly over (n, v) E (A) x A (B) in view of the boundedness of the Shannon entropy H(). Theorem (cf. 7d)
also ensures that our proposed algorithms find an approximate QRE ((T) such that DualGap, (((T))
c/2 after taking T = Ō optimized learning rates. It follows immediately that
iterations, which is no more than δ (1 [AAls>))
iterations with
DualGap(<2 < DDallaap, (E(T)) max f+(d', pi,"""
( ( )- (((() ((((T)
|1') S
and therefore ((T) is e-NE. Intriguingly, unlike prior work (Daskalakis and Panageas 2018a Wei et al.) 20216) that analyzed the last-iterate convergence of OMWU in the unregularized setting (T 0), our last-iterate convergence does not require the NE of (1 to be unique.
Rationality. Another attractive feature of the algorithms developed above being rational (as introduced in Bowling and Veloso (2001)) in the sense that the algorithm returns the best-response
7

---

10a
104
10
10²
DualGapp((**
(pt)
10
C7/C
10-2
10-9.
k)
OMWU
DualGap (Sal
10 4
6.
OptGap,
10-
10
log C//4
10
10-9
OMWU
10-40
1000
2000
3000
4000
5000
10"15
0.00
0.02
0.04
0.06
0.08
0.10
Iteration Count
Regularization Parameter
Figure 1: Performance illustration of the PU and OMWU methods for solving entropy-regularien matrix games with |A| [8] = 100, where the entries of the payoff matrix A is generated indepen- dently from the uniform distribution on 1,, The learning rates are fixed as 17 = 0.1. The left panel plots various error metrics of convergence w.r.t. the iteration count with 0.01, while the right panel plots these error metrics at 1000-th iteration with different choices of
policy of one player when the opponent takes any fixed stationary policy. More specially, in terms of matrix games, when player 2 sticks to stationary policy the update of player 1 reduces to (a) & (a) 1-17 exp(n[Ar)a). In this case, Theorem can be established in exactly the same fashion by restricting attention only to the updates of f(()
No-regret learning of OMWU. Besides convergence to equilibria, in game-theoretical settings, it often desirable design and implement no-regret algorithms, which are capable of providing black-box guarantees over arbitrary sequences played by the opponent (Cesa- Biaa-Biiachhi and Lugosi 2006 Rakhlin and Sridharan, 2013). Fortunately, turns out that entropy regularization not only accelerates the convergence, but also enables no-regret learning somewhat "for free": it encourages exploration by putting positive mass on every action, therefore guards against adversaries. By using properly chosen learning rate schedule, the proposed OMWU (Algorithm) 2 can be further established as a no-regret algorithm; the details can be found (Cen et al. 2021
Zero-sum Markov games with entropy regularization
Leveraging the success of PU and OMWU in solving the regroyy-regllarized matrix games, this section extends our current analysis solve the zero-sum two-player Markov game with entropy regularization, which is again formulated as finding the equilibrium of saddle-point optimization problem. We start by introducing basic setup, which will be followed by the proposed policy extragradient method with its theoretical guarantees.
3.1 Background and problem formulation
We consider discounted Markov Game (MG) which is defined as M B, discrete state space S, action spaces of two players A and B, transition probability P, reward function r S x A x B + [0, 1J and discount factor 7 E [0, 1). A policy μ S (AA) (resp. S + A (B)) defines how player (resp. player 2) reacts to a given state 8, where the probability of taking action
). with
A (resp. b E 13) is μ(aas) (resp. v(bls)). The transition probability kernel P:S. x A x B + (SS) defines the dynamics of the Markov game, where P(s a, b) specifies the probability of transiting to state s' from state when the players take actions and respectively.
Motivated by entropy regularization in Markov decision processes (MDP) GGest al. 2019 we consider an cemopy-regularized variant of MG, where the value function is defined as
V.L (8) = E
r (r(#t, az, b.) 7 log (((r)1))))))))))))))))))())))( + log (bb(8))) 800
(8)
where the quantity 7 2 O denotes the regularization parameter, and the expectation is evaluated over the randomness of the transition kernel as well as the policies. The regularized Q-function Qu. of

---

policy pair (p, v) is related to V. as
(s)
P( [V+ (s').
(9)
We will call V!." and Q the soft value function and soft Q-function, respectively. A policy pair (nt, vy) is said to be the quantal response equilibrium (QRE) of the entropy-regularizze MG, if its value attains the minimax value of the entropy-regularize, MG over all states E S.i.e
(s) max min V. (s) = min max (s) V (s), (s),
P
where V is called the optimal minimax soft value function, and similarly Q; = Qu called the optimal minimax soft Q-function.
Goal. Our goal is find the QRE of the entropy-reegllrrized MG in decentralized manner where the players only observe its own reward without accessing the opponent's s actions. By setting the regularization parameter sufficiently small т, this also allows to find an approximate NE of the unregularized MG.
3.2 From value iteration to policy extragradient methods
value iteration. It is known that classical dynamic programming approaches such as value iteration be extended to solve MG (Perolat al., 2015). where each iteration amounts to solving a series of matrix games for each state. Similar to the single-agent case (Cen et al. 2020), let us introduce the per-state Q-value matrix Q(s) = (s.,,,) ||A] for every S, where the element indexed by the action pair (a, b) is Q(s, a, b). Similarly, we define the per-state policies
Eatropy-regulatte
can extend these approaches to solve the reguuay-eeg MG. Setting the stage,
u(s) == ((-ls) E A(A) and vss) v(-ls) e AB) for both players.
In parallel to the original Bellman operator, we denote the soft Bellman operator T as
(s, a. b) r(s, a, ((sso)))
max min fr (=((())))())) (u(E))E((A) ((E))E((B)
where for each per-state Q-value matrix Q(s), we introduce an entropy-regularized matrix game in the form of
max min J- (=((ss) us)) = p(s)TQ((su(ss) (H(())) +(7((()))7((((())) HEA(A) (EA(B)
The entropy-regullrizeed value iteration then proceeds as
((++1) = Tr (Q))),
(10)
where Q(0) is an initialization. By definition, the optimal minimax soft Q-function obeys Tr();)
O and therefore corresponds to the fix point of the soft Bellman operator. Given the above entropy- regularized value iteration, the following lemma states its iterates contract linearly the optimal minimax soft Q- function at a rate of the discount factor y.
Proposition 2. The regulai-eg value iteration 110 converges at a linear rate, i.e. [[Q()) 2 & (1) - Q711
Approximate value iteration via policy extragradient methods. Proposition 2 suggests that the optimal minimax soft Q-function of the entropx-regularizzed MG can be found by solving a series of
antropy-regularin matrix games induced by { 1:20 in (10), a task that can be accomplished by adopting the fast extragradient methods developed earlier. To proceed, we first define the following sampling oracle, which makes rigorous that the proposed algorithm does not require access to the Q-function of the entire MG, but only its own single-agent Q-function when playing against the opponent's 's policy.
Definition 2 (Sampling oracle for Markov games). Given any policy pair p(s), u(s) and Q- D-value matrix Q(s) any S, the sampling oracle returns
[s)))(())}+ Esnr(s) [Q(s, a, b)],
and
[Q(s))((s)), EEnpp(s) [Q(s, a.b)
for any E A and b B.

---

Algorithm 3: Policy Extragradient Method for Entropy-regularized Markov Game
initialization: Q(9) = 0.
2 for 2.. mamin do
Let Q(1) denote
b) a(,,,, P(s.s V(O))))
(11)
Invoke PU (Algorithm I OMWU (Algorithm for Tuub iterations to solve the following entropy-regularized matrix game for every state s, where the initialization set as uniform distributions:
min Sr (s) (()EA(A)) (())AA(B)
max
(s), (s), plt.Tanhi) plt Set v(++2 S+ (=(((((()) (s): (s), pll:Zbch)
Return the last iterate ((t.Tamb)
Encouragingly, by judiciously setting the number of iterations in both the outer loop (for updating the Q-value matrices) and the inner loop (for updating the QRE of the corresponding Q-value matrix), we are guaranteed to find the QRE of the engropy-regulariieed MG in a small number of iterations without solving the veration-varying matrix games exactly, as dictated by the following theorem.
Theorem 2. Assume |A] 2
|B] and S 1. Setting 1) 2[1+r(log - the total iterations
(namely, the product T main Tubb) required for Algorithm 3 to achieve ||Q(Tau)) Qill S is at
most O
(log 1/1+ (log lox (1-7)c)
(1-7))
Theorem ensures that within -[1ーン}3 log" (t) iterations, Algorithm finds pair of policies
whose value close to the optimal minimax soft Q-function Q; in an entrywise manner prescribed accuracy Remarkably, the iteration complexity is independent of the dimensions of the state space and the action space (up to log factors).
Remark (Duality gap and solving the unregularized MG). Solving the entropy- retrare-egullrrieed MG provides viable strategy to find 6-approximate NE of the unregularized MG, where the optimality of policy pair is typically gauged by the duality gap. Fortunately, this can be achieved similar to the case of matrix games, and refer interested readers to Cen al. (202T) for details.
Conclusions
This paper develops provably efficient policy extragradient methods (PU and OMWU) for entropy- regularized matrix games and Markov games, whose last iterates guaranteed converge linearly to the quantal response equilibrium at a linear rate. Encouragingly. the rate of convergence is independent of the dimension of the problem, i.e. the sizes of the space space and the action space. In addition, the last iterates of the proposed algorithms can also be used to locate Nash equilibria for the unregularized competitive games without assuming the uniqueness of the Nash equilibria by judiciously tuning the amount of regularization. This work opens up interesting opportunities for further investigations of policy extragradient methods for solving competitive games. For example, can we develop two-time-scale policy extragradient algorithms for Markov games where the Q- function updated simultaneously with the policy but potentially different time scale, using samples, such in actor-critic algorithm (Konda and Tsitsiklis 2000
Acknowledgments and Disclosure of Funding
S. Cen and Y. Chi are supported in part by the grants ONR N00014-18-1-2144 and N00014-19-1- 2404, ARO 19-888-18- NSF CCF-1901 199, CCF-2007911 and CCF-2106778. Y. Wei supported in part by the NSF grants CCF-2007911, DMS-21475462201544 and CCF-2106778.
10

---

References
Arora, S., Hazan, E., and Kale, S. (2012). The multiplicative weights update method: meta-algorithm and applications. Theory of Computing, 8(1::21-164.
Bai, Y. and Jin, C. (2020), Provable self-play algorithms for competitive reinforcement learning. In Internationa Conference on Machine Learning, pages 551-560. PMLR.
Bowling, M. and Veloso, M. (2001). Rational and convergent learning in stochastic games. In Proceedings of the 17th international joint conference on Artificial intelligence Deeeligence-Volumee 2, pages 1021-1026.
Cen, S., Cheng, C.,, Chen, Y., Wei, Y., and Chi, Y. (2020). Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.065588
Cen, S., Wei, Y., and Chi, Y. (2021). Fast policy extragradient methods for competitive games with entropy regularization. arXiv preprint arXiv:2105.15186.
Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
Daskalakis, C., Deckelbaum, A., and Kim, A. (2011). Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium Discrete Algorithms,, pages 235-254. SIAM.
Daskalakis, C., Foster, D. J., and Golowich, N. (2020). Independent policy gradient methods for competitive reinforcement learning. In Advances Neural Information Processing Systems, volume 33, pages 5527-5540.
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. (2018). Training GANs with optimism. In International Conference Learning Representations (ICLR 2018).
Daskalakis, C. and Panageas. (2018a). Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv:
Daskalakis, C. and Panageas, I. (201 8b). The limit points of (optimistic) gradient descent min- max optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 9256-9266.
Freund, and Schapire, R. E. (1999). Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-133.
Geist, M., Scherrer, B., and Pietquin, O. (2019). A theory of regularized Markov decision processes. In International Conference on Machine Learning, pages 2160-2180 2169.
Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A..
and Bengio, Y. (2014). Generative adversarial networks. arXiv preprint
Harker, P. T. and Pang, J.-S. (1990). Finite-dimensional variational inequality and nonlinear comple- mentarity problems: survey of theory, algorithms and applications. Mathematical programming, 48(1):161-220.
Hofbauer, J. and Sandholm, W. H. (2002). On the global convergence of stochastic fictitious play. Econometrica, 2066:22665
Hsieh, Y.-G., lutzeler, F., Malick, J., and Mertikopoulos, (2019). On the convergence of single-call stochastic extra-gradient methods. arXiv preprint arXiv: (00.:/990..04555
Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014, Citeseer.
Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Matecon, 12:747-756.
Lan, (2021). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint 35X1v:2102.00135.
11

---

Lei, Q., Nagarajan, S. G., Panageas, I., and Wang, X. (2021). Last iterate convergence in no no-regret learning: constrained min-max optimization for convex-concave landscapes. International Conference on Artificial Intelligence and Statistics, pages 1441-1449. PMLR.
Liang, T. and Stokes, (2019). Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMLR.
Littman, M. L. (1994). Markov games framework for multi-agent reinforcement learning. In Machine Learning Proceedings, pages 157-163. Elsevier.
McKelvey, R. D. and Palfrey. T. R. (1995). Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38.
Mci, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020). On the global convergence rates of softmax policy gradient methods. arXiv preprint arXiv:2005.06399
Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. (2018a). Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In Interna- tional Conference on Learning Representations.
Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. (2018b). Cycles in adversarial regular- ized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717. SIAM.
Mertikopoulos, P. and Sandholm, W. H. (2016). Learning in games via reinforcement and regulariza- tion. Mathematics of Operations Research, 11444:1297-1324
Mokhtari, A., Ozdaglar, A., and Pattathil, S. (2020a). A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497-1507. PMLR.
Mokhtari, A., Ozdaglar, A. E., and Pattathil, S. (2020b). Convergence rate of O(1kk) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 33001)300
Nemirovski, A. (2004). Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-25 2511.
Neu, G., Jonsson, A., and Gómez, V. (2017). A unified view of entropy-regullrizze Markov decision processes. arXiv preprint arXiv:1705.0779:
Perolat, J., Scherrer, B., Piot, B., and Pietquin, O. (2015). Approximate dynamic programming for two-player zero-sum Markov games. In International Conference on Machine Learning, pages 1321-1329. PMLR.
Rakhlin, A. and Sridharan, K. (2013). Optimization, learning, and games with predictable sequences. arXiv preprint 1311.666
Savas, Y., Ahmadi, M., Tanaka, T., and Topeu, U. (2019), Entropy-regularty stochastic games, In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5955-5962. IEEE.
Shapley, L. S. (1953). Stochastic games. Proceedings of the National Academy of Sciences, 199500:0055-1100
Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. (2015). Fast convergence of regularized learning games. Proceedings of the 28th International Conference on Neural Information Processing Systems-Volas 2, pages 2989-2997.
Tseng, P. (1995). On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):277-252.
12

---

Wei, C.-Y., Lee, C.-W.. Zhang, M., and Luo, H. (2021a). Last-iterate convergence of decentralized optimistic gradient descent/ascent infinite-horizon competitive Markov games. arXiv preprint arXiv:2102.04500.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021b). Linear last-iterate convergence in constrained saddle-point optimization. In International Conference on Learning Representations (ICLR).
Xie, Q. Chen, Y., Wang, Z., and Yang, Z. (2020). Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium. In Conference Learning Theory, pages 3674-3682. PMLR.
Yadav, A., Shah, S., Xu, Z., Jacobs, D., and Goldstein, T. (2017). Stabilizing adversarial nets with prediction methods. arXiv preprint 1705.0770
Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, D., and Chi, Y. (2021). Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. arXiv preprint arv: 105. /0066.
Zhang, K., Kakade. S., Basar, T., and Yang, L. (2020). Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33.
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 preprint arXiv:2102.08900
13


Reviews:
[{"review_id": "XX7lLrBnPf6", "reviewer": "Reviewer_uEKj", "summary": "The authors propose to use mirror descent to solve classic entropy-regularized competitive games. Linear convergence rates are obtained for the proposed algorithm. In addition, the authors propose to use such an algorithm to solve the subproblem in the entropy-regularized Markov game and obtain a linear convergence rate to the regularized equilibrium.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Quality: The paper is well written in general.\n\nClarity: Clear for the most parts. However, I find the Markov game part misleading. The name of Algorithm 3 appears to be a policy optimization method for Markov games while the algorithm actually is a value iteration. The policy extragradient method is only used for solving a subroutine.\n\nOriginality/Significance: There are a few concerns on the originality and significance of this work:\n\n1. The algorithms proposed seem to be mirror descent (or mirror-prox) for the saddle point problems. Based on this, if we look at the structure of the entropy-regularized two-player matrix games, it is strongly convex-concave due to the nice geometry brought by the regularization. Thus, the results presented in this paper are not surprising at all (see, e.g., [1]). This makes me wondering: what is the technical novelty of this paper's analysis? How does this paper compare to [1]?\n\n2. The Markov game part resembles the framework of [Perolat 2015]. The difference is only replacing the policy iteration with value iteration, which is mentioned in [Perolat 2015]. For this part, I feel that the result here is only a combination of the already well-known contraction property of regularized Markov games and the results for matrix game solving derived earlier in this paper. I think the authors need to also explicitly highlight the significance here -- is the algorithm for solving Markov games novel, or are the techniques in the analysis here novel?\n\n--------------------------------------------------------------------------------------\n\nMore comments:\n\nDefinition 2: Is this sampling oracle realistic? How can one sample population quantities?\n\nIndependence of $|\\mathcal{S}|$: This is a bit counter-intuitive. What is the intuition behind such property? Is this related to the statement \"for any $s \\in \\mathcal{S}$\" in Definition 2? \n\n\n\n[1] Mokhtari, Aryan, Asuman Ozdaglar, and Sarath Pattathil. \"A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "JgW1xi3c8hw", "reviewer": "Reviewer_3nt9", "summary": "The paper studies two standard classes of games with entropy regularization: two-player zero-sum matrix games and zero-sum Markov games. For the regularized matrix games, the authors apply the mirror descent approach (using KL distance) to the regularized objective, and propose two first-order descent/ascent algorithms using different optimistic predictions: the Predictive Update (PU) and the Optimistic Multiplicative Weights Update (OMWU). The authors prove that both algorithms converge to the unique Nash equilibrium of the regularized game with constant stepsizes, linearly. The authors characterize the linear convergence via four measures: KL distance, infinity norm, optimality gap, and duality gap. It is featured by last-iterate convergence and almost dimension-free. For the regularized Markov games, the authors apply the proposed PU and OMWU to the $Q$-value functions at each state and prove the convergence in infinite norm to the optimal $Q$-value function of the regularized game. The convergence rate is slightly worse than the linear rate, but it is also almost dimension-free. The authors also provide computational experiments to verify the usefulness of the proposed algorithms. ", "questions": "", "limitations": "", "rating": 7, "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 authors generalize standard two-player zero-sum matrix games and zero-sum Markov games to be regularized ones with entropy terms. Although adding regularization is not a new idea, the authors establish several benefits theoretically for solving certain regularized game problems. The proposed extragradient algorithms are more general due to an extra regularization parameter. The established convergence results can be more favorable in some aspects, e.g., not need unique Nash equilibrium, if we compare them with existing non-regularized results, e.g., [1,2]. I believe that this work is significant in exploiting the regularization technique for the first time to develop several algorithms for solving game problems with new theoretical guarantees. \n\nThis paper is well-written. The proofs are easy to follow and the experimental results are convincing.   \n\nI only have a few questions regarding quality. \n\n(1) The studied problems and proposed algorithms include the basic non-regularized cases $\\tau = 0$. Your convergence proofs do not seem to work for $\\tau = 0$, and they have to reply on the regularized problem structure. This is a possible limitation of your proof technique. It would be great if you could explain it in the paper. Viewing some other results, e.g., OMWU for non-regularized problems [1], could you comment on the gap/difference your proof analysis to [1]? \n\n(2) As remarked after Theorem 1, the accuracy $\\epsilon$ has to be determined in advance to set $\\tau$. In practice, this might be the other way around: we often fix some $\\tau$ and run the algorithm for many steps in order to get a Nash as accurate as we can. How does your result help with this situation? Is it possible to use diminishing $\\tau$?   \n\n(3) A related question to (2) is that do you have a similar scheme for Theorem 2 to get an approximate Nash? diminishing $\\tau$?   \n\n(4) In Algorithm 3, it seems that step 5 still needs to know policies from both players. This might raise a concern about implementing it in a decentralized way.  \n\n\nHere are some minor clarity questions.\n\n(1) line 81. Does it imply both terms in $\\max$? \n\n(2) line 169. Misposition in notation $f$.\n\n\nReferences:\n\n[1] Linear last-iterate convergence in constrained saddle-point optimization. ICLR 2021.  \n\n[2] Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. COLT 2021.\n\n============================\n\nPOST-REBUTTAL: Thank you for your response. I have read the response and other reviews. The authors have addressed my comments. I just have two final remarks.\n\n(1) I made a few trials of running your code by tunning the regularization parameter. Too small regularization can lead to very slow convergence while it warrants a good accuracy in approximating an unregularized Nash in theory. It would be nice if you could highlight the tradeoff between the convergence speed and the accuracy of a Nash by varying $\\tau$. Moreover, for reproducing the Markov game simulations, I recommend supplementing the code for Markov games.\n\n(2) I tried to go over some proof steps I missed in the first round. I found a step in the inequality in line 170 is not straightforward. You might consider adding an explanation, e.g., by the weak duality.\n\nOverall, I do believe this paper has a good quality. The score has been increased accordingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "FFBQ_gluSpT", "reviewer": "Reviewer_Q1Zp", "summary": "The authors provide an analysis of an entropy regularized extra-gradient method for zero sum games. The proposed algorithms have last iterate convergence guarantees to the equilibrium of the regularized game at rate that is dimension free (up to double logarithmic factors) regardless if the unregularized game has a unique equilibrium. The algorithms can be used to find approximate equilibria of the unregularized game and in Markov zero sum games.", "questions": "", "limitations": "", "rating": 7, "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": "To the best of my knowledge the analysis of the proposed algorithms is indeed novel. Previous results for the unregularized OMWU required the existence of a unique Nash equilibrium and provided dimension dependent linear convergence rates. The proposed algorithms from the authors resolve both these problems using an entropy regularization.\n\nThe major difficulty faced by previous techniques was that the linear rates were only possible in a small area around the equilibrium so a separate analysis was required to bound the number of iterations required to reach this area. The use of regularization by the proposed algorithms obviates this two-step approach and in the process removes most of the dimension dependence.  \n\nThis clearly separates the author's work from prior work. I would suggest to the authors to discuss this difference more in the main paper and provide any insight they have about why regularization resolves the technical issues faced by prior work.\n\nI believe that this contribution is significant and can have further applications to other extra-gradient methods for constrained zero sum games. The extension to Markov zero sum games is also a nice addition.  \n\nI have read the authors' response to all reviews. The edits proposed are going to improve the paper and thus I remain in favor of accepting this submission. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and negative social impact have been adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "CRKsXQ2i13P", "reviewer": "Reviewer_KD2g", "summary": "The authors present a last-iterate linear convergence result for two extra-gradient type algorithms (PU and OMWU, using the paper's terminology) when applied to regularized matrix games. The authors propose a value-iteration based algorithm for solving Makov matrix game where the soft Bellman operator is implemented using PU or OMWU.", "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": "originality and significance\n\nThere are several theoretical highlights as already emphasised in the paper, like the last-iterate convergence to \u000fsaddle point of unregularized matrix games without uniqueness assumption, and the proposal of a value-iteration based algorithm to Markov game.\n\nquality and clarity\n\nThe paper is well-written. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Q1: Has it been established that mirror-prox (extragradient + Bregman divergence) [1]  in the strongly-convex-strongly-concave setting enjoys linear convergence? If yes, what makes this paper (and also several related works like (Wei et al. (2021b)) different?\n\nThe reason I ask this is, under the simplex setup of mirror-prox, the mirror-prox updates (and variants) are then just PU and OMWU. If such results for mirror-prox were available, then the results in this paper and several related works would be just special cases of such results. \n\nTo me, it seems that linear convergence of extragradient in the deterministic and strongly-convex-strongly-concave setting should be an available result. However, I did google a little bit and there are no easily accessible results on this. It would be great if the authors could clarify a little bit. The authors also emphasize they handle constrained matrix games but it seems to me that this is not a significant issue under the simplex setup. Please correct me if I am wrong.\n\n[1] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17– 58, 2011.\n\nUPDATE: The authors address my concerns. I maintain my previous rating.\n", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies classical classes of games with entropy regularization.
The proposed algorithm appears to be novel. The paper provides a good contribution to the literature.
I recommend acceptance of the work.
There are a few comments from reviewers that can be addressed as a minor revision when preparing the camera ready version of the paper.
Decision: Accept (Poster)