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 -reee, 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 cntropy-regularicn 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 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 (Dakkalakis 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 Au T Of (EA(A) (EA(B)
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 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-regullaizeed matrix game (2) at <= (,, is defined as DualGap,(() = maxp'eΔ(A) I=(p',
m) [+ 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+)), ((++) 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
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
r. 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-regularized 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) == p(-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--egularizzed 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
(s, 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": "q6NNc42ed-a", "reviewer": "Reviewer_bKGv", "summary": "The paper proposes provably efficient policy extragradient methods for MG, where the last iterates are proven to converge linearly to the QRE of the game. Such a rate of convergence is dimension independent, and the methods can be implemented without further assuming the uniqueness of NE. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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\nThe paper is original. The algorithms themselves are not original but the finite-time last iterate analysis is novel and technically sound. \n\n### quality \nThe paper is of good quality. \n\n### clarity \nThe paper is well written and easy to follow. \n\n### significance\nMG is an important type of games and the paper targets on solving MG using QRE as an approximation of NE, without further assuming that NE is unique. \n\n## minor issues\nWhy entropy regularization is important in Markov games? Can we loose the condition here? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "mHwkHMCLT_B", "reviewer": "Reviewer_v4uF", "summary": "In this work, the authors propose to apply a multiplicative extragradient method (under the label \"preductive updates\" (PU)) and a variant (optimistic multiplicative weight update) to the solution of entropy-regularized matrix games and two-agent tabular markov games.\n \n", "questions": "", "limitations": "", "rating": 4, "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 first part of the paper (pages 3-7) studies the application of a multiplicative form of the extragradient method and optimistic mirror descent to entropy-regularized matrix games.\nConvergence results are derived, including a suggestion for the choice of the regularization weight in order to compute an approximate equilibrium of the unregularized problem.\nFinally, a synthetic experiment with an i.i.d random payoff matrix is provided.\n\nThe second part of the paper (pages 7-9) studies the application of the same algorithm to the solution of entropy-regularized value iteration in tabular markov games.\nLeveraging the results from the first part, the authors provide an end-to-end convergence result for this application, in the absence of no sampling noise.\n\nWhile there has been a vast number of recent papers studying variants of the extragradient method to different multi-agent games, there could still be space for a paper studying\nthe explicit application to matrix games.\nHowever, the work is presently unfocused in its contribution (new algorithm vs analyzing an existing algorithm, theoretical novelty vs practical improvement) that I have to recommend rejection for now.\n\nSuggestions for improvement:\nSince algorithm 2 is the specialization of a known algorithm and \"PU\" can be obtained from the extragradient method by replacing the additive gradient step with a multiplicative one, it seems that the motivation and introduction of these algorithms is excessive.\nSince there are numerous existing theoretical results on extragradient-type algorithms, it would be helpful to more clearly point our differences to existing results.\nAlso, since the PU and OMWU seem to perform almost identically, it is unclear why the authors consider both variants.\nThroughout the paper, there are no empirical comparisons to other methods. If the authors could provide more evidence regarding when and why to use the methods presented in the paper and how they compare to other approaches, this could greatly increase the potential impact of the paper.\n\n\nMinor comments:\n(1) Line 62: \"which is extremely natural and popular for optimizing over probability simplexes\" To me, such strong yet vague statements without supporting evidence do not seem suitable for a scientific publication.\n\n(2) Proposition 2: This result has nothing to do with the choice of the inner optimization loop. Is this a new result?\n                                       \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should more clearly formulate the significance of their results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "fXLsiEvNBC", "reviewer": "Reviewer_1R9o", "summary": "In this work, the authors aim to complete the recent line of research in last-iterate convergence guarantees for saddle-point optimization (applicable to game theory, GANs, etc.) with efficient methods that converge to an approximate Nash equilibrium *without* the equilibrium uniqueness guarantee. The key is to simply apply the previously analyzed methods (OMWU in particular) on a regularized version of the payoff. The regularization ensures uniqueness of what is called QRE, quantal response equilibrium, which can be used for finding an approximate Nash equilibrium. As a bonus, the authors show that their results apply to Markov games too.", "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": "I believe this work has enough significance to be published at this conference. The main contribution is getting rid of the uniqueness assumption in finding approximate Nash equilibria in bilinear games, since last-iterate convergence results for the constrained setting (with that assumption) have been derived in recent prior work. There is no algorithmic novelty, the methods are the same as in previous work. The key difference is using entropy regularization to ensure uniqueness, then convert to Nash, the desired outcome. The work might seem incremental in terms of techniques, methods, etc. but it still improves upon prior work by getting rid of a nontrivial assumption and that alone is sufficient for me to accept the paper.", "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": "8"}, "extra_text": {}}, {"review_id": "JiPC4aNCbh7", "reviewer": "Reviewer_wNLY", "summary": "This paper proposes to leverage entropic regularization and optimistic-type methods to solve zero-sum (ZS) matrix games and ZS Markov games.\nThe authors begin with ZS matrix games on the simplex: they add entropic regularization, thus transforming this game into a strongly-concave/strongly-concave problem.\nSlight variants of Mirror-prox/extragradient and optimistic mirror descent with multiplicative updates are introduced, and the authors show that, for several performance measures, the last-iterate of these methods converge linearly to a solution of the regularized problem thanks to the added strong convexity/concavity.\nTheir rates are (almost) dimension-free, and do not require the uniqueness of the solution.\nAs a consequence, they explain how to obtain $\\epsilon$-Nash-equilibrium with $O(1/\\epsilon)$ iterations by tuning the regularization parameter.\nFinally, the authors propose to put to use their results to tackle ZS infinite-horizon Markov games.", "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": "## Originality and significance\n\n### ZS Matrix Games\n- Optimistic methods and their last-iterate convergence have been heavily studied recently.\n- Entropic regularization for games seem also to have attracted interest, especially as an alternative solution concept (see references from the submission)\nThe authors seem to be the first to combine these two principles and to demonstrate the computational benefits of such a match.\n\n### ZS Markov Games\n- Optimistic methods have also gained traction for this problem [Wei et al. 2021a, Zhao et al. 2021]\n- Entropic regularization has also been proposed in the single-agent MDP case, for instance [Cen et al. 2020]\nAgain, the authors combine these two notions, and seem almost to be the first to do so.\nIndeed, though this may be considered concurrent work (appeared on arXiv 3 months before the NeurIPS deadline), [Zhao et al. 2021] also consider entropic regularization in section 4.1. Though I would expect their rate to be worse than the one of the submission, I am not sure it is the case (their step-size seems bigger...).\n\n## Quality and clarity\nThe paper seems technically sound and is quite clear.\n\n## Strengths and weaknesses\n\n### Strengths\n- The authors propose a simple yet theoretically efficient method to solve ZS matrix games, with little assumption and dimension-free rates.\n- They use their method as a subroutine to solve ZS Markov Games efficiently.\n+ Good comparison with existing work on OMWU\n\n### Weaknesses\n- Lack of (at least theoretical) comparison with other methods to solve ZS Markov games (cf question below)\n\n### Questions\n- Could the authors expand on the comparison with the results with  entropic regularization of [Zhao et al. 2021], and more generally compare their work more thoroughly to the litterature on ZS Markov games, in particular with [Wei. et al. 2021a, Zhao et al.2021, Daskalakis et al. 2020] which are already cited in the submission?\n- Is is possible, using this approach for ZS Markov games, to have performance guarantees w.r.t. the solution of the unregularized problem? (in the same fashion as lines 255-265 for ZS matrix games, and since the authors seem to imply that this is also the case for ZS Markov games lines 299-300)\n- Why is the last-iterate convergence so important for ZS games? In particular, what would be advantages of finding an approximate Nash equilibrium with the method from this paper vs classical averaged Mirror-Prox? (the number of iteration is of the same order with the same dimension-free properties, as far as I understand)\n\n### Typos\n- Line 64 of the supplementary material: inequalities -> equalities\n- First equality below line 169 in the supplemnetray material: $\\mu$ -> $\\mu(s)$, $\\nu$ -> $\\nu(s)$\n\n### Edit after authors' response\nRating changed, see my response below", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper treats the convergence of a regularized variant of the multiplicative weights and optimistic multiplicative weights update (MWU and OMWU respectively) in zero-sum games. A second part of the paper concerns the applications of these methods to zero-sum Markov games.

This paper was extensively discussed by the committee, and the reviewers identified both strong and weak points in the paper. On the positive side, the authors' linear convergence result for the regularized MWU/OMWU methods seems to be new (at the very least, the committee members were not aware of an equivalent result in the literature). On the negative side, the presentation and positioning of the paper left a lot to be desired, especially with regard to the similarity of the proposed regularized methods to other existing methods – and, in particular, running MWU/OMWU on a regularized game.

The main point of contention is as follows: if one considers an entropic regularization of the underlying game, it is immediate to see that the game's set of Nash equilibria is replaced by a unique quantal response equilibrium - or, rather, a logit equilibrium (as QRE are called in the context of entropic regularization; the term "Nash distribution" is also sometimes used). Thus, by focusing on QRE, the authors are essentially side-stepping the unique equilibrium requirement: they do not require equilibrium uniqueness, but they prove convergence to a perturbed equilibrium, not a Nash equilibrium. This point is crucial for the proper positioning of the paper, but it is not made clear by the authors.

Building on this, given that logit equilibria are _de facto_ interior, and given that the regularized game is strongly monotone, it is natural to expect a geometric rate of convergence for mirror descent / mirror-prox methods. [This, after all, is an entropic variant of the standard Tikhonov regularization approach.] Of course, the fact that this may be a "natural" result, does not subtract from its merit: however, a much clearer presentation of the topic would be expected in order to position these results in the proper context. [Further compounding the issue is that the authors' algorithm is not _exactly_ MWU/OMWU ran on the regularized game but closely related to it - and, if anything, this raises the question of why the authors' chose one variant over the other (especially since the former approach would seem simpler to analyze)]

Finally, regarding the applications to Markov games and $Q$-learning: one important limitation is that the paper operates in the "full-information" framework (with respect to individual player knowledge, not global one). While this assumption is meaningful from an "offline" viewpoint, it is harder to justify in the online setting where such algorithms are typically deployed (since only obtained payoffs are observed and counterfactual reasoning is not feasible in general). The authors touch on this issue briefly in the conclusions section, where they comment on the relevance of two-time-scale algorithms for the $Q$-learning problem: in this regard, the authors might want to check the 2005 paper of Leslie and Collins [1] and a follow-up by Coucheney et al. [2]. Both papers treat the problem of learning in normal-form games with entropic regularization and partial information, and the algorithms studied in both papers are very closely related to the regularized MWU algorithm studied by the authors; more to the point, [1] considers a two-time-scale variant that seems to do what the authors suggest in the conclusions section (modulo the extra-gradient part).

To sum up, the extent of the revision required to bring the paper's contributions into focus led the committee to the conclusion that the paper should go through another round of review before being considered again for publication. The decision to reject the current version was taken in this light, and I would strongly encourage the authors to resubmit a suitably revised version of the paper at the next opportunity once they have addressed the committee's concerns.

[1] D. S. Leslie and E. J. Collins, Individual Q-learning in normal form games, SIAM Journal on Control and Optimization 44 (2005), no. 2, 495–514.

[2] P. Coucheney, B. Gaujal, and P. Mertikopoulos, Penalty-regulated dynamics and robust learning procedures in games, Mathematics of Operations Research 40 (2015), no. 3, 611– 633.
Decision: Accept (Poster)