Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
Year: 2022

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.

heading: 1 Introduction
text: 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 learning and decision making paradigms such as Generative Adversarial Networks (GANs) (Goodfellow et 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 an independent and decentralized manner (Daskalakis et al., 2020; Wei et al., 2021a) with guaranteed last-iterate convergence. Namely, each player will execute symmetric and independent updates iteratively using its own payoff without observing the opponent’s actions directly, and the final policies of the iterative process should be a close approximation to the equilibrium up to any prescribed precision. This kind of algorithms is more advantageous and versatile especially in federated environments, as it requires neither prior coordination between the players like twotimescale algorithms, nor a central controller to collect and disseminate the policies of all the players, which are often unavailable due to privacy constraints.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1.1 Last-iterate convergence in competitive games
text: 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 are 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 a non-asymptotic fashion. A flurry of algorithms is proposed, including Optimistic Gradient Descent Ascent (OGDA) (Rakhlin and Sridharan, 2013; Daskalakis and Panageas, 2018b; Wei et al., 2021b), predictive updates (Yadav 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 et 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., 2018a; Harker and Pang, 1990).
However, saddle-point optimization in the constrained setting, which includes competitive games as a 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 convexconcave properties in the original problem, which are crucial to the convergence of gradient methods. Therefore, there is a 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 al., 2012) – which is extremely natural and popular for optimizing over probability simplexes – called Optimistic Multiplicative Weight Updates (OMWU), and established the asymptotic last-iterate convergence of OMWU for matrix games. Very recently, Wei et al. (2021b) 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.

heading: 1.2 Our contributions
text: Motivated by the algorithmic role of entropy regularization in single-agent RL (Neu et al., 2017; Geist et al., 2019; 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 as a smoothing scheme for finding the NE. Our contributions are summarized below.
• Near dimension-free last-iterate convergence to QRE of entropy-regularized matrix games. We propose two policy extragradient algorithms to solve entropy-regularized matrix games, namely the Predictive Update (PU) and OMWU methods, where both players execute symmetric and multiplicative updates without knowing the entire payoff matrix nor the opponent’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 ϵ-optimal QRE in terms of Kullback-Leibler (KL) divergence, it takes no more than Õ ( 1 ητ log ( 1 ϵ )) iterations,
where Õ(·) hides logarithmic dependencies. Here, τ is the regularization parameter, and η is the learning rate of both players. Maximizing the learning rate, the iteration complexity is bounded by Õ ((1 + ∥A∥∞/τ) log(1/ϵ)), where ∥A∥∞ = maxi,j |Ai,j | is the ℓ∞ norm of the payoff matrix A. • Last-iterate convergence to ϵ-NE of unregularized matrix games without uniqueness assumption. The QRE provides an accurate approximation to the NE by setting the entropy regularization τ sufficiently small, therefore our result directly translates to finding a NE with last-iterate convergence guarantee. Roughly speaking, to find an ϵ-NE (Zhang et al., 2020, Definition 2.1), it takes no more than Õ ( 1 + ∥A∥∞ϵ ) iterations with optimized learning rates, which is again independent of the size
of the action spaces up to logarithmic factors. Unlike prior literature (Daskalakis and Panageas, 2018a; Wei et al., 2021b), 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 infinite-horizon discounted entropyregularized zero-sum Markov games, which finds an ϵ-optimal minimax soft Q-function—in terms of ℓ∞ error—in at most Õ ( 1 τ(1−γ)2 log 2 ( 1 ϵ )) iterations, where γ ∈ (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-regularized competitive games with multiplicative updates and dimension-free linear last-iterate convergence, and demonstrates entropy regularization as a smoothing technique to find ϵ-NE without the uniqueness assumption. Table 1 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).

heading: 1.3 Related works
text: 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 (1999) showed that many standard methods such as GDA and MWU have a converging average duality gap at the rate of O(1/ √ T ), which is improved to O(1/T ) by considering optimistic variants of these methods, such as OGDA and OMWU (Rakhlin and Sridharan, 2013; Daskalakis et al., 2011; Syrgkanis et 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 (2018a) showed the asymptotic convergence of the last iterate of OMWU to the unique equilibrium, and Wei et al. (2021b) showed the last iterate of OMWU achieves a linear rate of convergence after an initial phase of sublinear convergence, however the rates therein can be highly pessimistic in terms of the problem dimension, while our rate for entropy-regularized OMWU is dimension-free up to logarithmic factors.
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., 2020a,b; Nemirovski, 2004; Liang and Stokes, 2019). However, the last-iterate convergence of constrained convex-concave saddle-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 lastiterate 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-concave constrained saddle-point optimization with an explicit rate.
Entropy regularization in RL and games. In single-agent RL, 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., 2019; Mei et al., 2020; Cen et al., 2020; Lan, 2021; Zhan et al., 2021). Turning to the game setting, entropy regularization is used to account for imperfect information in the seminal work of McKelvey and Palfrey (1995) 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., 2015; Zhang et al., 2020), value-based algorithms (Bai and Jin, 2020; Xie et al., 2020), and policybased algorithms (Daskalakis et al., 2020; Wei et al., 2021a; Zhao et al., 2021). The iteration complexities in prior works (Perolat et al., 2015; Daskalakis et al., 2020; Wei et al., 2021a; Zhao et 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) the probability simplex over the set A. We overload the functions such as log(·) and exp(·) to take vector inputs with the understanding that the function is applied in an entrywise manner. For instance, given any vector z = [zi]1≤i≤n ∈ Rn, the notation exp(z) denotes exp(z) := [exp(zi)]1≤i≤n; other functions are defined analogously. Given two probability distributions µ and µ′ over A, the KL divergence from µ′ to µ is defined by KL ( µ ∥µ′ ) := ∑ a∈A µ(a) log µ(a) µ′(a) . Given a matrix A, ∥A∥∞ is used to denote entrywise maximum norm, namely, ∥A∥∞ = maxi,j |Ai,j |. The all-one vector is denoted as 1.

heading: 2 Zero-sum matrix games with entropy regularization
text: We first consider a 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 = {1, . . . ,m} and B = {1, . . . , n} be the action spaces of each player.

heading: 2.1 Background and problem formulation
text: 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 as the following min-max problem (or saddle point optimization problem):
max µ∈∆(A) min ν∈∆(B)
f(µ, ν) := µ⊤Aν, (1)
where A ∈ Rm×n denotes the payoff matrix, µ ∈ ∆(A) and ν ∈ ∆(B) stand for the mixed/randomized policies of each player, defined respectively as distributions over the probability simplex ∆(A) and ∆(B). A pair of policies (µ⋆, ν⋆) is said to be a Nash equilibrium (NE) of (1) if f(µ⋆, ν) ≥ f(µ⋆, ν⋆) ≥ f(µ, ν⋆) for all (µ, ν) ∈ ∆(A)×∆(B). Entropy-regularized 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 A, McKelvey and Palfrey (1995) 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 µ∈∆(A) min ν∈∆(B)
fτ (µ, ν) := µ ⊤Aν + τH(µ)− τH(ν), (2)
where H(π) = −∑i πi log(πi) denotes the Shannon entropy of a distribution π, and τ ≥ 0 is the regularization parameter. As is well known, the optimal solution (µ⋆τ , ν ⋆ τ ) to (2), dubbed as the QRE,
is unique whenever τ > 0 (due to the presence of strong concavity/convexity), which satisfies the following fixed point equations:µ ⋆ τ (a) = exp([Aν⋆τ ]a/τ)∑m a=1 exp([Aν ⋆ τ ]a/τ) ∝ exp([Aν⋆τ ]a/τ), for all a ∈ A,
ν⋆τ (b) = exp(−[A⊤µ⋆τ ]b/τ)∑n
b=1 exp(−[A⊤µ⋆τ ]b/τ) ∝ exp(−[A⊤µ⋆τ ]b/τ), for all b ∈ B.
(3)
Goal. We aim to efficiently compute the QRE of the entropy-regularized matrix game in a decentralized manner, and investigate how an efficient solver of QRE can be leveraged to find a NE of the unregularized matrix game (1). Namely, we only assume access to “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 is formally described in the following sampling oracle. Definition 1 (Sampling oracle for matrix games). For any policy pair (µ, ν) and payoff matrix A, the sampling oracle returns the exact values of µ⊤A and Aν.
Additional notation. For notational convenience, we let ζ represent the concatenation of µ ∈ R|A| and ν ∈ R|B|, namely, ζ = (µ, ν). The solution to (2), which is specified in (3), is denoted by ζ⋆τ = (µ ⋆ τ , ν ⋆ τ ). For any ζ = (µ, ν) and ζ
′ = (µ′, ν′), we shall often abuse the notation and let KL ( ζ ∥ ζ ′ ) = KL ( µ ∥µ′ ) + KL ( ν ∥ ν′ ) . The duality gap of the entropy-regularized matrix game (2) at ζ = (µ, ν) is defined as DualGapτ (ζ) = maxµ′∈∆(A) fτ (µ ′, ν) − minν′∈∆(B) fτ (µ, ν′) which is clearly nonnegative and DualGapτ (ζ ⋆ τ ) = 0. Similarly, let the optimality gap of the entropy-
regularized matrix game (2) at ζ = (µ, ν) be OptGap(ζ) = ∣∣fτ (µ, ν)− fτ (µ⋆τ , ν⋆τ )∣∣.

heading: 2.2 Proposed extragradient methods: PU and OMWU
text: To begin, assume we are given a pair of policies z1 ∈ ∆(A), z2 ∈ ∆(B) 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 policy is fixed as z2 (resp. z1), the saddle-point optimization problem (2) is then decoupled into two independent min/max optimization problems:
max µ∈∆(A) µ⊤Az2 + τH(µ)− τH(z2) and min ν∈∆(B) z⊤1 Aν + τH(z1)− τH(ν),
which are naturally solved via mirror descent / ascent with KL divergence. Specifically, one step of mirror descent / ascent takes the formµ (t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Az2]a), for all a ∈ A,
ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤z1]b), for all b ∈ B, (4)
where η is the learning rate. The above update rule forms the basis of our algorithm design.
Motivation: a form of implicit updates with linear convergence. It turns out, if we could select the policy pair (z1, z2) = ζ(t+1) := (µ(t+1), ν(t+1)) as the ones to be taken in the future, and call the resulting update rule as the Implicit Update (IU) method:
Implicit Update:
µ (t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν(t+1)]a), for all a ∈ A,
ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ(t+1)]b), for all b ∈ B. (5)
Though unrealistic — since it uses the future updates — it leads to a one-step convergence to the QRE when η = 1/τ (see the optimality condition in (3)). Encouragingly, we have the following linear convergence guarantee of IU when adopting a general learning rate. Proposition 1 (Linear convergence of IU). Assume 0 < η ≤ 1/τ , then for all t ≥ 0, the iterates ζ(t) := (µ(t), ν(t)) of the IU method in (5) satisfy KL ( ζ⋆τ ∥ ζ(t) ) ≤ (1− ητ)tKL ( ζ⋆τ ∥ ζ(0) ) .
In words, the IU method achieves an appealing linear rate of convergence that is independent of the problem dimension. Motivated by this observation, we seek to design algorithms where the policies (z1, z2) employed in (4) serve as good predictions of (µ(t+1), ν(t+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 entropy-regularized matrix game, namely the Predictive Update (PU) method and the Optimistic Multiplicative Weights
Algorithm 1: The PU method 1 initialization: µ(0), ν(0). 2 for t = 0, 1, 2, · · · do 3 Update µ̄ and ν̄ according to{
µ̄(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν(t)]a), ν̄(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ(t)]b).
4 Update µ and ν according to{ µ(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν̄(t+1)]a), ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ̄(t+1)]b).
Algorithm 2: The OMWU method 1 initialization: µ(0) = µ̄(0), ν(0) = ν̄(0). 2 for t = 0, 1, 2, · · · do 3 Update µ̄ and ν̄ according to{
µ̄(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν̄(t)]a), ν̄(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ̄(t)]b).
4 Update µ and ν according to{ µ(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν̄(t+1)]a), ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ̄(t+1)]b).
Update (OMWU) method, the latter adapted from Rakhlin and Sridharan (2013); Daskalakis et al. (2011). Detailed procedures can be found in Algorithm 1 and Algorithm 2, respectively. On a high level, both algorithms maintain two intertwined sequences {(µ(t), ν(t))}t≥0 and {(µ̄(t), ν̄(t))}t≥0, and in each iteration t = 0, 1, . . ., proceed in two steps:
• The midpoint (µ̄(t+1), ν̄(t+1)) serves as a prediction of (µ(t+1), ν(t+1)) by running one step of mirror descent / ascent (cf. (4)) from either (z1, z2) = (µ(t), ν(t)) (for PU) or (z1, z2) = (µ̄(t), ν̄(t)) (for OMWU).
• The update of (µ(t+1), ν(t+1)) then mimics the implicit update (5) using the prediction (µ̄(t+1), ν̄(t+1)) obtained above.
When the proposed algorithms converge, both (µ(t), ν(t)) and (µ̄(t), ν̄(t)) 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 τ = 0 (i.e., no entropy regularization is enforced), the OMWU method in Algorithm 2 reduces to the method analyzed in Rakhlin and Sridharan (2013); Daskalakis and Panageas (2018a); Wei et al. (2021b) without entropy regularization.
Remark 1. It is worth highlighting that the proposed algorithms are different from Mertikopoulos et al. (2018a), as the extragradient is only applied to the bilinear term but not the entropy regularization term. This seemingly small, but important, difference leads to a more concise closed-form update rule and a cleaner analysis, as shall be seen momentarily.

heading: 2.3 Performance guarantees
text: We are now positioned to present our main theorem concerning the last-iterate convergence of PU and OMWU for solving (2).
Theorem 1 (Last-iterate convergence of PU and OMWU). Suppose that the learning rates η = ηPU of PU in Algorithm 1 and η = ηOMWU of OMWU in Algorithm 2 satisfy
0 < ηPU ≤ 1
τ + 2 ∥A∥∞ , and 0 < ηOMWU ≤ min
{ 1
2τ + 2 ∥A∥∞ ,
1
4 ∥A∥∞
} . (6)
Then for any t ≥ 0, the iterates ζ(t) = (µ(t), ν(t)) and ζ̄(t) = (µ̄(t), ν̄(t)) of PU and OMWU achieve • Linear convergence of policies in KL divergence and entrywise log-ratios:
max { KL ( ζ⋆τ ∥ ζ(t) ) , 12KL ( ζ⋆τ ∥ ζ̄(t+1) )} ≤ (1− ητ)tKL ( ζ⋆τ ∥ ζ(0) ) , (7a)∥∥∥∥log ζ(t)ζ⋆τ ∥∥∥∥ ∞ ≤ 2(1− ητ)t ∥∥∥∥log ζ(0)ζ⋆τ ∥∥∥∥ ∞ + 8 ∥A∥∞ τ (1− ητ)t/2KL ( ζ⋆τ ∥ ζ(0) )1/2 . (7b)
• Linear convergence of values in optimality and duality gaps:
OptGapτ (ζ̄ (t)) ≤ η−1 · 1 1− (τ + ∥A∥∞)η · (1− ητ) t 1− (1− ητ)tKL ( ζ⋆τ ∥ ζ(0) ) , (7c)
DualGapτ (ζ̄ (t)) ≤ ( η−1 + 2τ−1∥A∥2∞ ) (1− ητ)t−1KL ( ζ⋆τ ∥ ζ(0) ) . (7d)
Remark 2. Setting µ(0) and ν(0) to be uniform policies leads to a universal bound KL ( ζ⋆τ ∥ ζ(0) ) = log |A|+ log |B| − H(µ⋆τ )−H(ν⋆τ ) ≤ log |A|+ log |B|.
Remark 3. Similar results continue to hold even when the two players use different regularization parameters τµ, τν > 0 in (2), as long as the regularization parameter τ is replaced by max{τµ, τν} in the upper bounds of the learning rate, and the contraction parameter is replaced by 1−min{τµ, τν}η.
Theorem 1 characterizes the convergence of the last-iterates ζ(t) 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 to QRE. To achieve an ϵ-accurate estimate of the QRE in terms of the KL divergence, the bound (7a) tells that it is sufficient to take
1
ητ log
( log |A|+ log |B|
ϵ ) iterations using either PU or OMWU. Notably, this iteration complexity does not depend on 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 + ∥A∥∞/τ) log(1/ϵ) (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 ℓ∞ 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 (cf. (7c)) 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 be the key enabler for generalizing our algorithms to Markov games, and bounding the duality gap allows to directly translate our results to finding a NE of unregularized matrix games.
Last-iterate convergence to approximate NE. The entropy-regularized matrix game can be thought as a smooth surrogate of the unregularized matrix game (1); in particular, it is possible to find an ϵ-NE by setting τ sufficiently small in (2). According to (Zhang et al., 2020, Definition 2.1), a policy pair ζ = (µ, ν) is an ϵ-NE if it satisfies DualGap(ζ) := maxµ′∈∆(A) f(µ′, ν)−minν′∈∆(B) f(µ, ν′) ≤ ϵ.
Observe that setting τ = ϵ/4log |A|+log |B| guarantees that |fτ (µ, ν) − f(µ, ν)| < ϵ/4 uniformly over (µ, ν) ∈ ∆(A)×∆(B) in view of the boundedness of the Shannon entropy H(·). Theorem 7 (cf. (7d)) also ensures that our proposed algorithms find an approximate QRE ζ̄(T ) such that DualGapτ (ζ̄
(T )) ≤ ϵ/2 after taking T = Õ ( 1 ηϵ ) iterations, which is no more than Õ ( 1 + ∥A∥∞ϵ ) iterations with optimized learning rates. It follows immediately that
DualGap(ζ̄(T )) ≤ DualGapτ (ζ̄ (T )) + max
µ′,ν′ ∣∣∣fτ (µ′, ν̄(T ))− fτ (µ̄(T ), ν′)− (f(µ′, ν̄(T ))− f(µ̄(T ), ν′))∣∣∣ ≤ ϵ, and therefore ζ̄(T ) is an ϵ-NE. Intriguingly, unlike prior work (Daskalakis and Panageas, 2018a;
Wei et al., 2021b) that analyzed the last-iterate convergence of OMWU in the unregularized setting (τ = 0), our last-iterate convergence does not require the NE of (1) to be unique.
Rationality. Another attractive feature of the algorithms developed above is being rational (as introduced in Bowling and Veloso (2001)) in the sense that the algorithm returns the best-response
policy of one player when the opponent takes any fixed stationary policy. More specially, in terms of matrix games, when player 2 sticks to a stationary policy ν, the update of player 1 reduces to µ(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν]a). In this case, Theorem 1 can be established in exactly the same fashion by restricting attention only to the updates of µ(t).
No-regret learning of OMWU. Besides convergence to equilibria, in game-theoretical settings, it is often desirable to design and implement no-regret algorithms, which are capable of providing black-box guarantees over arbitrary sequences played by the opponent (Cesa-Bianchi and Lugosi, 2006; Rakhlin and Sridharan, 2013). Fortunately, it turns out that entropy regularization not only accelerates the convergence, but also enables no-regret learning somewhat “for free”: it encourages exploration by putting a positive mass on every action, therefore guards against adversaries. By using a properly chosen learning rate schedule, the proposed OMWU (Algorithm 2) can be further established as a no-regret algorithm; the details can be found in (Cen et al., 2021).

heading: 3 Zero-sum Markov games with entropy regularization
text: Leveraging the success of PU and OMWU in solving the entropy-regularized matrix games, this section extends our current analysis to solve the zero-sum two-player Markov game with entropy regularization, which is again formulated as finding the equilibrium of a saddle-point optimization problem. We start by introducing its basic setup, which will be followed by the proposed policy extragradient method with its theoretical guarantees.

heading: 3.1 Background and problem formulation
text: We consider a discounted Markov Game (MG) which is defined as M = {S,A,B, P, r, γ}, with discrete state space S, action spaces of two players A and B, transition probability P , reward function r : S × A × B → [0, 1] and discount factor γ ∈ [0, 1). A policy µ : S → ∆(A) (resp. ν : S → ∆(B)) defines how player 1 (resp. player 2) reacts to a given state s, where the probability of taking action a ∈ A (resp. b ∈ B) is µ(a|s) (resp. ν(b|s)). The transition probability kernel P : S ×A×B → ∆(S) defines the dynamics of the Markov game, where P (s′|s, a, b) specifies the probability of transiting to state s′ from state s when the players take actions a and b respectively.
Motivated by entropy regularization in Markov decision processes (MDP) (Geist et al., 2019), we consider an entropy-regularized variant of MG, where the value function is defined as
V µ,ντ (s) := E [ ∞∑ t=0 γt (r(st, at, bt)− τ logµ(at|st) + τ log ν(bt|st)) ∣∣ s0 = s] , (8)
where the quantity τ ≥ 0 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 Qµ,ντ of a
policy pair (µ, ν) is related to V µ,ντ as Qµ,ντ (s, a, b) = r(s, a, b) + γEs′∼P (·|s,a,b) [ V µ,ντ (s ′) ] . (9)
We will call V µ,ντ and Q µ,ν τ the soft value function and soft Q-function, respectively. A policy pair (µ⋆τ , ν ⋆ τ ) is said to be the quantal response equilibrium (QRE) of the entropy-regularized MG, if its value attains the minimax value of the entropy-regularized MG over all states s ∈ S, i.e.
V ⋆τ (s) = max µ min ν V µ,ντ (s) = min ν max µ
V µ,ντ (s) := V µ⋆τ ,ν ⋆ τ τ (s),
where V ⋆τ is called the optimal minimax soft value function, and similarly Q ⋆ τ := Q
µ⋆τ ,ν ⋆ τ
τ is called the optimal minimax soft Q-function.
Goal. Our goal is to find the QRE of the entropy-regularized MG in a decentralized manner where the players only observe its own reward without accessing the opponent’s actions. By setting the regularization parameter sufficiently small τ , this also allows us to find an approximate NE of the unregularized MG.

heading: 3.2 From value iteration to policy extragradient methods
text: Entropy-regularized value iteration. It is known that classical dynamic programming approaches such as value iteration can be extended to solve MG (Perolat et 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), we can extend these approaches to solve the entropy-regularized MG. Setting the stage, let us introduce the per-state Q-value matrix Q(s) := Q(s, ·, ·) ∈ R|A|×|B| for every s ∈ S, where the element indexed by the action pair (a, b) is Q(s, a, b). Similarly, we define the per-state policies µ(s) := µ(·|s) ∈ ∆(A) and ν(s) := ν(·|s) ∈ ∆(B) for both players. In parallel to the original Bellman operator, we denote the soft Bellman operator Tτ as
Tτ (Q)(s, a, b) := r(s, a, b) + γEs′∼P (·|s,a,b) [
max µ(s′)∈∆(A) min ν(s′)∈∆(B)
fτ ( Q(s′);µ(s′), ν(s′) )] ,
where for each per-state Q-value matrix Q(s), we introduce an entropy-regularized matrix game in the form of
max µ∈∆(A) min ν∈∆(B)
fτ ( Q(s);µ(s), ν(s) ) := µ(s)⊤Q(s)ν(s)− τH(µ(s)) + τH(ν(s)).
The entropy-regularized value iteration then proceeds as
Q(t+1) = Tτ (Q(t)), (10)
where Q(0) is an initialization. By definition, the optimal minimax soft Q-function obeys Tτ (Q⋆τ ) = Q⋆τ and therefore corresponds to the fix point of the soft Bellman operator. Given the above entropyregularized value iteration, the following lemma states its iterates contract linearly to the optimal minimax soft Q-function at a rate of the discount factor γ. Proposition 2. The entropy-regularized value iteration (10) converges at a linear rate, i.e. ∥Q(t) − Q⋆τ∥∞ ≤ γt∥Q(0) −Q⋆τ∥∞.
Approximate value iteration via policy extragradient methods. Proposition 2 suggests that the optimal minimax soft Q-function of the entropy-regularized MG can be found by solving a series of entropy-regularized matrix games induced by {Q(t)}t≥0 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 it 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 policy. Definition 2 (Sampling oracle for Markov games). Given any policy pair µ(s), ν(s) and Q-value matrix Q(s) for any s ∈ S, the sampling oracle returns
[Q(s)ν(s)]a = Eb∼ν(s) [Q(s, a, b)] , and [Q(s)⊤µ(s)]b = Ea∼µ(s) [Q(s, a, b)]
for any a ∈ A and b ∈ B.
Algorithm 3: Policy Extragradient Method for Entropy-regularized Markov Game 1 initialization: Q(0) = 0. 2 for t = 0, 1, 2, · · · , Tmain do 3 Let Q(t) denote
Q(t)(s, a, b) = r(s, a, b) + γEs′∼P (·|s,a,b)V (t)(s′). (11)
4 Invoke PU (Algorithm 1) or OMWU (Algorithm 2) for Tsub iterations to solve the following entropy-regularized matrix game for every state s, where the initialization is set as uniform distributions:
max µ(s)∈∆(A) min ν(s)∈∆(B)
fτ ( Q(t)(s);µ(s), ν(s) ) .
Return the last iterate µ̄(t,Tsub)(s), ν̄(t,Tsub)(s). 5 Set V (t+1)(s) = fτ ( Q(t)(s); µ̄(t,Tsub)(s), ν̄(t,Tsub)(s) ) .
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 entropy-regularized MG in a small number of iterations without solving the iteration-varying matrix games exactly, as dictated by the following theorem.
Theorem 2. Assume |A| ≥ |B| and τ ≤ 1. Setting η = 1−γ2(1+τ(log |A|+1−γ)) , the total iterations (namely, the product Tmain · Tsub) required for Algorithm 3 to achieve ∥∥Q(Tmain) −Q⋆τ∥∥∞ ≤ ϵ is at most O ( (log |A|+1/τ)
(1−γ)2 ( log log |A|(1−γ)ϵ )2) .
Theorem 2 ensures that within Õ (
1 τ(1−γ)2 log 2 ( 1 ϵ )) iterations, Algorithm 3 finds a pair of policies
whose value is close to the optimal minimax soft Q-function Q⋆τ in an entrywise manner to a prescribed accuracy ϵ. Remarkably, the iteration complexity is independent of the dimensions of the state space and the action space (up to log factors).
Remark 4 (Duality gap and solving the unregularized MG). Solving the entropy-regularized MG provides a viable strategy to find an ϵ-approximate NE of the unregularized MG, where the optimality of a policy pair is typically gauged by the duality gap. Fortunately, this can be achieved similar to the case of matrix games, and we refer interested readers to Cen et al. (2021) for details.

heading: 4 Conclusions
text: This paper develops provably efficient policy extragradient methods (PU and OMWU) for entropyregularized matrix games and Markov games, whose last iterates are guaranteed to 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 a two-time-scale policy extragradient algorithms for Markov games where the Qfunction is updated simultaneously with the policy but potentially at a different time scale, using samples, such as in an 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-2142 and N00014-19-12404, ARO W911NF-18-1-0303, NSF CCF-1901199, CCF-2007911 and CCF-2106778. Y. Wei is supported in part by the NSF grants CCF-2007911, DMS-2147546/2015447 and CCF-2106778.

Review summaries:
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.

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. 

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.

This paper proposes to leverage entropic regularization and optimistic-type methods to solve zero-sum (ZS) matrix games and ZS Markov games. The authors begin with ZS matrix games on the simplex: they add entropic regularization, thus transforming this game into a strongly-concave/strongly-concave problem. Slight 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. Their rates are (almost) dimension-free, and do not require the uniqueness of the solution. As a consequence, they explain how to obtain $\epsilon$-Nash-equilibrium with $O(1/\epsilon)$ iterations by tuning the regularization parameter. Finally, the authors propose to put to use their results to tackle ZS infinite-horizon Markov games.

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.