Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization

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 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 two-timescale algorithms, nor a central controller to collect and disseminate the policies of all the players, which are often unavailable due to privacy constraints.

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 convex-concave 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, where existing analyses in the unconstrained setting do not generalize straightforwardly. 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.

2 Our contributions

Motivated by the algorithmic role of entropy regularization in single-agent RL (Neu et al.,, 2017; Geist et al.,, 2019; Cen et al., 2022b, ) 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 so-called 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, with the detailed problem formulations provided in Section 2.1 for matrix games and Section 3.1 for Markov games, respectively.

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 $\epsilon$-optimal QRE in terms of Kullback-Leibler (KL) divergence, it takes no more than

Last-iterate convergence to $\epsilon$-NE of unregularized matrix games without uniqueness assumption. The QRE provides an accurate approximation to the NE by setting the entropy regularization $\tau$ sufficiently small, therefore our result directly translates to finding a NE with last-iterate convergence guarantee. Roughly speaking, to find an $\epsilon$-NE (measured in terms of the duality gap), it takes no more than

iterations with optimized learning rates, 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.

No-regret learning of entropy-regularized OMWU. We further establish that under a decaying learning rate, the proposed OMWU method achieves a logarithmic regret for the entropy-regularized matrix game — on the order of $\mathcal{O}(\log T)$ — even when only one player follows the algorithm against arbitrary plays of the opponent. By setting $\tau$ appropriately, this translates to a regret of $\mathcal{O}((T\log T)^{1/2})$ for the unregularized matrix game, therefore matching the regret in Rakhlin and Sridharan, (2013) without the need of mixing in an auxiliary uniform distribution for exploration.

To the best of our knowledge, our paper is the first one 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 $\epsilon$-NE without the uniqueness assumption. Table 1 and Table 2 provide detailed comparisons of the proposed methods with prior arts for solving competitive games. Our results highlight the positive role of entropy regularization for accelerating convergence and safeguarding against imperfect payoff information in competitive games.

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.

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/\sqrt{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. In terms of no-regret analysis, Rakhlin and Sridharan, (2013) established a no-regret learning rate of $O(\log T/{T}^{1/2})$ with an auxiliary mixing of a uniform distribution at each update, which is later improved to $O(1/{T}^{1/2})$ in Kangarshahi et al., (2018) with a slightly different algorithm.

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, ; Mokhtari et al., 2020b, ; Nemirovski,, 2004; Liang and Stokes,, 2019). However, most works have focused on either average-iterate convergence (also known as ergodic convergence) (Nemirovski,, 2004), or the characterization of Euclidean update rules (Mokhtari et al., 2020a, ; Mokhtari et al., 2020b, ; Liang and Stokes,, 2019), where parameters are updated in an additive manner. These analyses do not generalize in a straightforward manner to non-Euclidean updates. As a result, the last-iterate convergence of non-Euclidean updates for 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 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-concave constrained saddle-point optimization with an explicit rate.

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., 2022b, ; Lan,, 2022; 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 but are not limited to Savas et al., (2019); Hofbauer and Sandholm, (2002); Mertikopoulos and Sandholm, (2016); Cen et al., 2022a .

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; Sidford et al.,, 2020; Zhang et al.,, 2020; Li et al.,, 2022; Cui and Yang,, 2021), value-based algorithms (Bai and Jin,, 2020; Xie et al.,, 2020; Mao et al.,, 2022), and policy-based algorithms (Daskalakis et al.,, 2020; Wei et al., 2021a, ; Zhao et al.,, 2021). 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. 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. In addition, while the last-iterate convergence guarantees in (Perolat et al.,, 2015; Daskalakis et al.,, 2020; Zhao et al.,, 2021) are applicable to the duality gap, Wei et al., 2021a proves the last-iterate convergence in terms of the Euclidean distance to NE, together with an average convergence in terms of the duality gap.

It is worth mentioning that the study of model-based and value-based algorithms typically focuses on the statistical issues in terms of sample complexity under the generative model or the online model of data collection; on the other end, the study of policy-based algorithms highlights the optimization issues by sidestepping the statistical issues using exact gradient evaluations, and later translating to sample complexity guarantees by leveraging model-based or value-based policy evaluation algorithms. Indeed, after the appearance of the initial version of this paper, Chen et al., (2021) has built on our algorithm to develop a sample-efficient version of policy extragradient methods in the online setting using bandit feedback.

4 Notation

Zero-sum matrix games with entropy regularization

In this section, we 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 $\mathcal{A}=\{1,\ldots,m\}$ and $\mathcal{B}=\{1,\ldots,n\}$ be the action spaces of each player. The proofs for this section are collected in Appendix A.

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):

In words, the NE corresponds to when both players play their best-response strategies against their respective opponents.

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):

where $\mathcal{H}(\pi)\coloneqq-\sum_{i}\pi_{i}\log(\pi_{i})$ denotes the Shannon entropy of a distribution $\pi$, and $\tau\geq 0$ is the regularization parameter. As is well known, the optimal solution $(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$ to (3), dubbed as the QRE, is unique whenever $\tau>0$ (due to the presence of strong concavity/convexity), which satisfies the following fixed point equations:

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.

For any policy pair $(\mu,\nu)$ and payoff matrix $A$, the sampling oracle returns the exact values of $\mu^{\top}A$ and $A\nu$.

For notational convenience, we let $\zeta$ represent the concatenation of $\mu\in{}^{|\mathcal{A}|}$ and $\nu\in{}^{|\mathcal{B}|}$, namely, $\zeta=(\mu,\nu)$. The solution to (3), which is specified in (4), is denoted by $\zeta_{\tau}^{\star}=(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$. For any $\zeta=(\mu,\nu)$ and $\zeta^{\prime}=(\mu^{\prime},\nu^{\prime})$, we shall often abuse the notation and let

The duality gap of the entropy-regularized matrix game (3) at $\zeta=(\mu,\nu)$ is defined as

which is clearly nonnegative and $\mathsf{DualGap}_{\tau}(\zeta_{\tau}^{\star})=0$. Similarly, let the optimality gap of the entropy-regularized matrix game (3) at $\zeta=(\mu,\nu)$ be \mathsf{OptGap}(\zeta)=\big{|}f_{\tau}({\mu},{\nu})-f_{\tau}(\mu_{\tau}^{\star},\nu_{\tau}^{\star})\big{|}.

2 Proposed extragradient methods: PU and OMWU

To begin, assume we are given a pair of policies $z_{1}\in\Delta(\mathcal{A})$, $z_{2}\in\Delta(\mathcal{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 $z_{2}$ (resp. $z_{1}$), the saddle-point optimization problem (3) is then decoupled into two independent min/max optimization problems:

which are naturally solved via mirror descent / ascent with KL divergence. Specifically, one step of mirror descent / ascent takes the form

where $\eta$ is the learning rate, or equivalently

The above update rule forms the basis of our algorithm design.

To begin with, we select the policy pair $(z_{1},z_{2})=\zeta^{(t+1)}:=(\mu^{(t+1)},\nu^{(t+1)})$ as the solution to the following equations, and call the conceptual update rule as the Implicit Update (IU) method:

Though unrealistic — since it uses the future updates and denies closed-form solutions — it leads to a one-step convergence to the QRE when $\eta=1/\tau$ (see the optimality condition in (4)). Encouragingly, we have the following linear convergence guarantee of IU when adopting a general learning rate.

Assume $0<\eta\leq 1/\tau$, then for all $t\geq 0$, the iterates $\zeta^{(t)}:=(\mu^{(t)},\nu^{(t)})$ of the IU method in (7) satisfy

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 $(z_{1},z_{2})$ employed in (6) serve as good predictions of $(\mu^{(t+1)},\nu^{(t+1)})$, such that the resulting algorithms are both practical and retain the appealing convergence rate of IU.

We propose two extragradient algorithms for solving the entropy-regularized matrix game, namely the Predictive Update (PU) method and the Optimistic Multiplicative Weights Update (OMWU) method, where the latter is adapted from Rakhlin and Sridharan, (2013). Detailed procedures can be found in Algorithm 1 and Algorithm 2, respectively. On a high level, both algorithms maintain two intertwined sequences $\{(\mu^{(t)},\nu^{(t)})\}_{t\geq 0}$ and $\{(\bar{\mu}^{(t)},\bar{\nu}^{(t)})\}_{t\geq 0}$, and in each iteration $t=0,1,\ldots$, proceed in two steps:

The midpoint $(\bar{\mu}^{(t+1)},\bar{\nu}^{(t+1)})$ serves as a prediction of $(\mu^{(t+1)},\nu^{(t+1)})$ by running one step of mirror descent / ascent (cf. (6)) from either $(z_{1},z_{2})=(\mu^{(t)},\nu^{(t)})$ (for PU) or $(z_{1},z_{2})=(\bar{\mu}^{(t)},\bar{\nu}^{(t)})$ (for OMWU).

The update of $(\mu^{(t+1)},\nu^{(t+1)})$ then mimics the implicit update (7) using the prediction $(\bar{\mu}^{(t+1)},\bar{\nu}^{(t+1)})$ obtained above.

When the proposed algorithms converge, both $(\mu^{(t)},\nu^{(t)})$ and $(\bar{\mu}^{(t)},\bar{\nu}^{(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 $\tau=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.

It is worth highlighting that the proposed algorithms are different from the mirror prox algorithm (Nemirovski,, 2004) or the optimistic mirror descent method (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.

3 Last-iterate linear convergence guarantees

We are now positioned to present our main theorem concerning the last-iterate convergence of PU and OMWU for solving (3). Its proof can be found in Section A.2.

Suppose that the learning rates $\eta_{t}=\eta=\eta_{\mathsf{PU}}$ of PU in Algorithm 1 and $\eta_{t}=\eta=\eta_{\mathsf{OMWU}}$ of OMWU in Algorithm 2 satisfy

Then for any $t\geq 0$, the iterates $\zeta^{(t)}=(\mu^{(t)},\nu^{(t)})$ and $\bar{\zeta}^{(t)}=(\bar{\mu}^{(t)},\bar{\nu}^{(t)})$ of both PU and OMWU achieve

Linear convergence of policies in KL divergence and entrywise log-ratios:

Linear convergence of values in optimality and duality gaps:

To further understand the term \mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\zeta^{(0)}}}\big{)} in (9), setting $\mu^{(0)}$ and $\nu^{(0)}$ to be uniform policies leads to a universal bound

regardless of $\zeta_{\tau}^{\star}=(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$.

Similar results continue to hold even when the two players use different regularization parameters $\tau_{\mu},\tau_{\nu}>0$ in (3), as long as the regularization parameter $\tau$ is replaced by $\max\{\tau_{\mu},\tau_{\nu}\}$ in the upper bounds of the learning rate, and the contraction parameter is replaced by $1-\min\{\tau_{\mu},\tau_{\nu}\}\eta$.

Theorem 1 characterizes the convergence of the last-iterates $\zeta^{(t)}$ and $\bar{\zeta}^{(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. (8)). 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 $\epsilon$-accurate estimate of the QRE in terms of the KL divergence, the bound (9a) tells that it is sufficient to take

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 $\left(1+\|A\|_{\infty}/\tau\right)\log(1/\epsilon)$ (modulo log factors), which only depends on the ratio $\|A\|_{\infty}/\tau$.

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. (9c)) and the duality gap (cf. (9d)) 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.

Figure 1 illustrates the performance of the proposed PU and OMWU methods for solving randomly generated entropy-regularized matrix games. It is evident that both algorithms converge linearly, and achieve faster convergence rates when the regularization parameter increases.

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 $\epsilon$-NE by setting $\tau$ sufficiently small in (3). According to (Zhang et al.,, 2020, Definition 2.1), a policy pair $\zeta=(\mu,\nu)$ is an $\epsilon$-NE if it satisfies

Observe that setting $\tau=\frac{\epsilon/4}{\log|\mathcal{A}|+\log|\mathcal{B}|}$ guarantees

in view of the boundedness of the Shannon entropy $\mathcal{H}(\cdot)$. Theorem 9 (cf. (9d)) also ensures that our proposed algorithms find an approximate QRE $\bar{\zeta}^{(T)}$ such that $\mathsf{DualGap}_{\tau}(\bar{\zeta}^{(T)})\leq\epsilon/2$ after taking $T=\widetilde{O}\left(\frac{1}{\eta\epsilon}\right)$ iterations, which is no more than

iterations with optimized learning rates. It follows immediately that

and therefore $\bar{\zeta}^{(T)}$ is an $\epsilon$-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 ($\tau=0$), our last-iterate convergence does not require the NE of (1) to be unique. See Table 1 for further comparisons.

For simplicity, we have set the regularization parameter $\tau$ on the order of the final accuracy $\epsilon$. In practice, it might be desirable to use an annealing schedule of $\tau$ similar to the doubling trick, see e.g. Yang et al., (2020); Li et al., (2021). We omit such straightforward generalizations for conciseness.

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 $\nu$, the update of player 1 reduces to

In this case, Theorem 1 can be established in exactly the same fashion by restricting attention only to the updates of $\mu^{(t)}$.

4 No-regret learning of entropy-regularized 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). Therefore, no-regret algorithms provide a sort of robustness especially when operating in contested environments, when the opponent is potentially adversarial. 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. Moreover, since algorithms that call the sampling oracle more than once per iteration often incurs a linear regret (Golowich et al.,, 2020), we focus on OMWU (Algorithm 2) and establish it as a no-regret algorithm.

We begin by formally defining the notion of regret. Suppose that player 2 plays according to Algorithm 2 to update $\nu^{(t)}$ and $\bar{\nu}^{(t)}$ based on the received payoff sequence $\{A^{\top}\bar{\mu}^{(t)}\}$, $t=0,1,\ldots$, whose construction potentially is deviated from the update rule of Algorithm 2, and even adversarial. Let

which is the regularized game value upon fixing the policy of player 1 as $\mu=\bar{\mu}^{(t)}$. The regret experienced by player 2 is then defined as

which measures the gap between the actual performance and the performance in hindsight. The following theorem shows that with appropriate choices of the learning rate, OMWU achieves a logarithmic regret bound $O(\log T)$.

Suppose only one player (say, player 2) follows the entropy-regularized OMWU method in Algorithm 2. Setting the learning rate as $\eta_{t}=\frac{1}{(t+1)\tau}$ and the initialization policy as the uniform policy, i.e. $\nu^{(0)}(b)=1/|\mathcal{B}|,\forall b\in\mathcal{B}$, the regret against any sequence $\{A^{\top}\bar{\mu}^{(t)}\}_{t=0}^{T}$ of play is bounded by

Theorem 2 implies that the average regret satisfies

which goes to zero as $T$ increases, therefore implies the entropy-regularized OMWU method is no-regret.

Similar to earlier discussions, one can still hope to control the regret of the unregularized matrix game, by appropriately setting $\tau$ sufficiently small. It is easily seen that the regret of the unregularized matrix game is given by

Therefore, by setting $\tau=O((\log T/T)^{1/2})$, we can ensure that the regret with regard to the unregularized problem is bounded by $\mathsf{Regret}_{0}(T)=O((T\log T)^{1/2})$, which is on par with the regret established in Rakhlin and Sridharan, (2013). It is worthwhile to highlight that the OMWU method in (Rakhlin and Sridharan,, 2013) requires blending in a uniform distribution every iteration to guarantee no-regret learning, while a similar blending is enabled in ours without extra algorithmic steps.

Zero-sum Markov games with entropy regularization

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, which is again formulated as finding the equilibrium of a saddle-point optimization problem. We start by introducing its basic setup, along with the entropy-regularized Markov game, which will be followed by the proposed policy extragradient method with its theoretical guarantees. The proofs for this section are collected in Appendix B.

We consider a discounted Markov Game (MG) which is defined as $\mathcal{M}=\{\mathcal{S},\mathcal{A},\mathcal{B},P,r,\gamma\}$, with discrete state space $\mathcal{S}$, action spaces of two players $\mathcal{A}$ and $\mathcal{B}$, transition probability $P$, reward function $r:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\to$ and discount factor $\gamma\in[0,1)$. A policy $\mu:\mathcal{S}\to\Delta(\mathcal{A})$ (resp. $\nu:\mathcal{S}\to\Delta(\mathcal{B})$) defines how player 1 (resp. player 2) reacts to a given state $s$, where the probability of taking action $a\in\mathcal{A}$ (resp. $b\in\mathcal{B}$) is $\mu(a|s)$ (resp. $\nu(b|s)$). The transition probability kernel $P:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\to\Delta(\mathcal{S})$ defines the dynamics of the Markov game, where $P(s^{\prime}|s,a,b)$ specifies the probability of transiting to state $s^{\prime}$ from state $s$ when the players take actions $a$ and $b$ respectively. The state value of a given policy pair $(\mu,\nu)$ is evaluated by the expected discounted cumulative reward:

where the trajectory $(s_{0},a_{0},b_{0},s_{1},\cdots)$ is generated by the MG $\mathcal{M}$ under the policy pair $(\mu,\nu)$, starting from the state $s_{0}$. Similarly, the Q-function captures the expected discounted cumulative reward with an initial state $s$ and initial action pair $(a,b)$ for a given policy pair $(\mu,\nu)$:

In a zero-sum game, one player seeks to maximize the value function while the other player wants to minimize it. The minimax game value on state $s$ is defined by

Similarly, the minimax Q-function $Q^{\star}(s,a,b)$ is defined by

It is proved by Shapley, (1953) that a pair of stationary policy $(\mu^{\star},\nu^{\star})$ attaining the minimax value on state $s$ attains the minimax value on all states as well (Filar and Vrieze,, 2012), and is called the NE of the MG.

Motivated by entropy regularization in Markov decision processes (MDP) (Geist et al.,, 2019; Cen et al., 2022b, ), we consider an entropy-regularized variant of MG, where the value function is modified as

where the quantity $\tau\geq 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}_{\tau}^{\mu,\nu}$ of a policy pair $(\mu,\nu)$ is related to ${V}_{\tau}^{\mu,\nu}$ as

We will call ${V}_{\tau}^{\mu,\nu}$ and ${Q}_{\tau}^{\mu,\nu}$ the soft value function and soft Q-function, respectively. A policy pair $(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$ 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\in\mathcal{S}$, i.e.

where $V_{\tau}^{\star}$ is called the optimal minimax soft value function, and similarly $Q_{\tau}^{\star}:=Q_{\tau}^{\mu_{\tau}^{\star},\nu_{\tau}^{\star}}$ is called the optimal minimax soft Q-function.

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, and leverage the QRE to find an approximate NE of the unregularized MG.

2 From value iteration to policy extragradient methods

In parallel to the original Bellman operator, we denote the soft Bellman operator $\mathcal{T}_{\tau}$ as

where for each per-state Q-value matrix $Q(s)$, we introduce an entropy-regularized matrix game in the form of

The entropy-regularized value iteration then proceeds as

where $Q^{(0)}$ is an initialization. By definition, the optimal minimax soft Q-function obeys $\mathcal{T}_{\tau}(Q_{\tau}^{\star})=Q_{\tau}^{\star}$ 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 to the optimal minimax soft Q-function at a rate of the discount factor $\gamma$.

The entropy-regularized value iteration (17) converges at a linear rate, i.e.

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\geq 0}$ in (17), a task that can be accomplished by adopting the fast extragradient methods developed earlier. To proceed, we first define the following first-order 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.

Given any policy pair $\mu(s),\nu(s)$ and Q-value matrix $Q(s)$ for any $s\in\mathcal{S}$, the first-order oracle returns

for any $a\in\mathcal{A}$ and $b\in\mathcal{B}$.

Algorithm 3 describes the proposed policy extragradient method. 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, as dictated by the following theorem.

Assume $|\mathcal{A}|\geq|\mathcal{B}|$ and $\tau\leq 1$. Setting $\eta_{t}=\eta=\frac{1-\gamma}{2(1+\tau(\log|\mathcal{A}|+1-\gamma))}$, the total iterations (namely, the product $T_{\text{\rm main}}\cdot T_{\text{\rm sub}}$) required for Algorithm 3 to achieve $\left\|{Q^{(T_{\text{\rm main}})}-Q_{\tau}^{\star}}\right\|_{\infty}\leq\epsilon$ is at most

Theorem 3 ensures that within $\widetilde{O}\left({\frac{1}{\tau(1-\gamma)^{2}}\log^{2}\left(\frac{1}{\epsilon}\right)}\right)$ iterations, Algorithm 3 finds a close approximation of the optimal minimax soft Q-function $Q_{\tau}^{\star}$ in an entrywise manner to a prescribed accuracy $\epsilon$. Remarkably, the iteration complexity is independent of the dimensions of the state space and the action space (up to log factors). In addition, the iteration complexity becomes smaller when the amount of regularization increases.

3 Last-iterate convergence to approximate NE

Similar to the case of matrix games, solving the entropy-regularized MG provides a viable strategy to find an $\epsilon$-approximate NE of the unregularized MG, where the optimality of a policy pair is typically gauged by the duality gap (Zhang et al.,, 2020). To begin, define the duality gap of the entropy-regularized MG at a policy pair $\zeta=(\mu,\nu)$ as

Encouragingly, the following corollary ensures that Algorithm 3 yields a policy pair with $\epsilon$-optimal duality gap for the entropy-regularized MG.

Assume $|\mathcal{A}|\geq|\mathcal{B}|$ and $\tau\leq 1$. Setting $\eta_{t}=\eta=\frac{1-\gamma}{2(1+\tau(\log|\mathcal{A}|+1-\gamma))}$, Algorithm 3 takes no more than $\widetilde{O}\left(\frac{1}{\tau(1-\gamma)^{2}}\log^{2}\left(\frac{1}{\epsilon}\right)\right)$ iterations to achieve $\mathsf{DualGap}_{\tau}^{\mathsf{markov}}(\zeta)\leq\epsilon$.

With Corollary 1 in place, setting the regularization parameter sufficiently small, i.e. \tau=O\big{(}\frac{(1-\gamma)\epsilon}{\log|\mathcal{A}|}\big{)}, and invoking similar discussions as (10) allows us to find an $\epsilon$-approximate NE of the unregularized MG within

iterations. See Table 2 for further comparisons with Perolat et al., (2015); Wei et al., 2021a ; Daskalakis et al., (2020); Zhao et al., (2021). To the best of our knowledge, the proposed method is the only one that simultaneously possesses symmetric updates, problem-independent rates, and last-iterate convergence.

Conclusions

This paper develops provably efficient policy extragradient methods (PU and OMWU) for entropy-regularized 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 Q-function 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)? A recent work by Cen et al., 2022c partially answered this question under exact gradient evaluation. Can we generalize the proposed algorithms to handle more general regularization terms, similar to what has been accomplished in the single-agent setting (Lan,, 2022; Zhan et al.,, 2021)? Can we generalize the proposed algorithm to other type of games (Ao et al.,, 2022)? We leave the answers to future work.

Acknowledgments

S. Cen and Y. Chi are supported in part by the grants ONR N00014-18-1-2142 and N00014-19-1-2404, ARO W911NF-18-1-0303, NSF CCF-1901199, CCF-2007911 and CCF-2106778. S. Cen is also gratefully supported by Wei Shen and Xuehong Zhang Presidential Fellowship, and Nicholas Minnici Dean’s Graduate Fellowship in Electrical and Computer Engineering at Carnegie Mellon University. Y. Wei is supported in part by the NSF grants CCF-2007911, DMS-2147546/2015447, CCF-2106778 and CAREER award DMS-2143215.

References

Appendix A Analysis for entropy-regularized matrix games

Before embarking on the main proof, it is useful to first consider the update rule (6) that underlies both PU and OMWU, which is reproduced below for convenience:

where $z_{1}\in\Delta(\mathcal{A})$ and $z_{2}\in\Delta(\mathcal{B})$. These updates satisfy the following property, whose proof is provided in Appendix C.1.

Denote $\zeta^{(t)}=(\mu^{(t)},\nu^{(t)})$ and $\zeta(z)=(z_{1},z_{2})$. The update rule (21) satisfies:

As we shall see, the above lemma plays a crucial role in establishing the claimed convergence results. The next lemma gives some basic decompositions related to the game values that are helpful.

For every $(\mu,\nu)\in\Delta(\mathcal{A})\times\Delta(\mathcal{B})$, the following relations hold

In addition, we also make record of the following elementary lemma that is used frequently.

For any $\mu_{1},\mu_{2}\in\Delta(\mathcal{A})$ satisfying

where the latter inequality holds for all $c\in\real$.

Setting $\zeta(z)=\zeta^{(t+1)}$ in Lemma 1, we have

By the definition of the KL divergence, one has

Combining the above two equalities with (25), we arrive at

This immediately leads to \mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\zeta^{(t+1)}}}\big{)}\leq(1-\eta\tau)\mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\zeta^{(t)}}}\big{)} by the nonnegativity of the KL divergence, as long as $1-\eta\tau\geq 0$. Therefore

A.2 Proof of Theorem 1

First noticing that both PU and OMWU share the same update rule for $\mu^{(t+1)}$ and $\nu^{(t+1)}$, which takes the form

Regarding this sequence, Lemma 1 (cf. (23)) gives

In view of the similarity of (25) and (28), we can expect similar convergence guarantees to that of the implicit updates established in Proposition 1 with the optimism that $\bar{\zeta}^{(t+1)}$ approximates $\zeta^{(t+1)}$ well. Following the same argument as (26), we have

On the other hand, it is easily seen that

Combining equalities (29), (30) with (28), we are left with the following relation pertaining to bounding \mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\zeta^{(t)}}}\big{)}:

In addition, to bound \mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\bar{\zeta}^{(t+1)}}}\big{)}, we will resort to the following three-point equality, which reads

which can be checked directly using the definition of the KL divergence.

To proceed, we need to control \big{\langle}{\log\bar{\zeta}^{(t+1)}-\log\zeta^{(t+1)},\bar{\zeta}^{(t+1)}-\zeta^{(t+1)}}\big{\rangle} on the right-hand side of inequality (31), and \big{\langle}{\zeta_{\tau}^{\star}-\bar{\zeta}^{(t+1)},\log\bar{\zeta}^{(t+1)}-\log\zeta^{(t+1)}}\big{\rangle} on the right-hand side of inequality (32), for which we continue the proofs for PU and OMWU separately as follows.

Following the update rule of $\bar{\zeta}^{(t+1)}=(\bar{\mu}^{(t+1)},\bar{\nu}^{(t+1)}$) in PU, we have

for some normalization constant $c$. With this relation in place, one has

Combined with Pinsker’s inequality, it is therefore clear that

Analogously, one can achieve the same bound regarding the quantity \big{\langle}{\log\bar{\nu}^{(t+1)}-\log\nu^{(t+1)},\bar{\nu}^{(t+1)}-\nu^{(t+1)}}\big{\rangle}. Summing up these two inequalities, we end up with

Plugging the above inequality into inequality (31) leads to

Therefore, as long as the learning rate $\eta$ satisfies $\eta\leq\frac{1}{\tau+\left\|{A}\right\|_{\infty}}$, we are ensured that

which further implies inequality (9a) when applied recursively.

𝑡1\mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\bar{\zeta}^{(t+1)}}}\big{)} for PU. By similar tricks of arriving at (34), we have

following from (33) and Pinsker’s inequality. A similar inequality for -{\big{\langle}{\nu_{\tau}^{\star}-\bar{\nu}^{(t+1)},\log\bar{\nu}^{(t+1)}-\log\nu^{(t+1)}}\big{\rangle}} can be obtained by symmetry, and summing together the two leads to

Plugging the above inequality into (32) and rearranging terms, we reach at

Therefore, with $\eta\leq 1/(\tau+2\left\|{A}\right\|_{\infty})$ we have

Following the update rule of $\bar{\zeta}^{(t+1)}=(\bar{\mu}^{(t+1)},\bar{\nu}^{(t+1)})$ for OMWU, we have

where $c$ is some normalization constant. Similar to the proof of relation (34), it can be easily demonstrated that

By symmetry, we can also establish a similar inequality for \big{\langle}{\log\bar{\nu}^{(t+1)}-\log\nu^{(t+1)},\bar{\nu}^{(t+1)}-\nu^{(t+1)}}\big{\rangle}, which in turns yields

Plugging the above inequality into equation (31) and re-organizing terms, we arrive at

With the choice of the learning rate $\eta\leq\min\{\frac{1}{2\left\|{A}\right\|_{\infty}+2\tau},\frac{1}{4\left\|{A}\right\|_{\infty}}\}$, it obeys

Combining the above inequality with (A.2.1) gives

For conciseness, let us introduce the shorthand notation

As a result, the above inequality can be restated as

Since we initialize OMWU with $\bar{\zeta}^{(0)}=\zeta^{(0)}$, therefore L^{(0)}=\mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\zeta^{(0)}}}\big{)}, which in turn gives

We complete the proof of inequality (9a) for OMWU.

𝑡1\mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\bar{\zeta}^{(t+1)}}}\big{)} for OMWU. By similar tricks of arriving at (38), we have

where the first line follows from (37). A similar inequality also holds for -{\big{\langle}{\nu_{\tau}^{\star}-\bar{\nu}^{(t+1)},\log\bar{\nu}^{(t+1)}-\log\nu^{(t+1)}}\big{\rangle}}. Summing the two inequalities leads to

Plugging the above inequality into (32) and rearranging terms, we reach at

where we recall the shorthand notation $L^{(t)}$ in (40). As the learning rate of OMWU satisfies $0<\eta<\min\left\{\frac{1}{2\left\|{A}\right\|_{\infty}+2\tau},\,\frac{1}{4\left\|{A}\right\|_{\infty}}\right\}$, it is clear that

where (i) follows from the recursive relation $L^{(t+1)}\leq(1-\eta\tau)L^{(t)}$ shown in inequality (41).

A.2.2 Proof of entrywise convergence of policy log-ratios (9b)

It is easily seen that $\mu^{(t)}(a)\propto\xi^{(t)}(a)=\exp(\log\xi^{(t)}(a))$ for $t\geq 0$. Noticing that $\mu_{\tau}^{\star}\propto\exp(A\nu_{\tau}^{\star})$, one has

Therefore it suffices for us to control the term $\left\|{\log\xi^{(t+1)}-A\nu_{\tau}^{\star}/\tau}\right\|_{\infty}$ on the right-hand side of inequality (43). Taking logarithm on both sides of (42b) yields

which, when combined with Pinsker’s inequality, implies

Plugging the bound of \mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\bar{\zeta}^{(t+1)}}}\big{)} from relation (9a) into (44) and invoking the inequality recursively leads to

where the last line results from the fact that $(1-\eta\tau)^{1/2}\leq 1-\eta\tau/2$. Combining pieces together, we end up with

Similarly, one can establish the corresponding inequality for $\left\|{\log\nu^{(t+1)}-\log\nu_{\tau}^{\star}}\right\|_{\infty}$, therefore completing the proof of inequality (9b).

A.2.3 Proof of convergence of optimality gap (9c)

To streamline our discussions, we only provide the proof of inequality (9c) concerning upper bounding $f_{\tau}(\bar{\mu}^{(t)},\bar{\nu}^{(t)})-f_{\tau}(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$ without taking the absolute value; the other direction of the inequality can be established in the similar manner and hence is omitted.

We first make note of an important relation that holds both for PU and OMWU. Consider the update rule of $(\mu^{(t+1)},\nu^{(t+1)})$, which is the same in PU and OMWU. Lemma 1 inequality (22a) gives

Similar to what we have done in the proof of (9a) (cf. (31)), based on the above relation, we can therefore rearrange terms and conclude that

In conjunction with Lemma 2 (cf. (24b)), we can further derive

where the second line follows from (46). From this point, we shall continue the proofs for PU and OMWU separately but follow similar strategies.

Plugging relation (34) into (47), we arrive at

where the last line holds since $\eta(\tau+\left\|{A}\right\|_{\infty})\leq 1$. Similarly, from Lemma 1 inequality (22b), one can establish the following inequality in parallel

We are ready to establish inequality (9c) for PU. Computing (48) $+\frac{2}{3}\cdot$ (49) gives

Here, the last step is due to the fact that $(1-\eta\tau)-\frac{2}{3}\eta\left\|{A}\right\|_{\infty}\geq 0$ and $\eta\left\|{A}\right\|_{\infty}-\frac{2}{3}(1-\eta\tau)\leq 0$ when $0<\eta\leq\frac{1}{\tau+2\left\|{A}\right\|_{\infty}}$. As a direct consequence, the difference $f_{\tau}(\mu_{\tau}^{\star},\nu_{\tau}^{\star})-f_{\tau}(\bar{\mu}^{(t)},\bar{\nu}^{(t)})$ satisfies

We conclude by noting that the other side of (9c) can be shown by considering $\frac{2}{3}\cdot$ (48) $+$ (49) combined with similar arguments, and are therefore omitted.

Similar to the case of PU, plugging (38) into (47) gives

Similarly, one can establish a symmetric inequality as follows

Directly computing (51) $+\frac{2}{3}\cdot$ (52) gives

With our choice of the learning rate $\eta\leq\min\{\frac{1}{2\left\|{A}\right\|_{\infty}+2\tau},\frac{1}{4\left\|{A}\right\|_{\infty}}\}$, it is guarantees that

To proceed, let us introduce the shorthand notation

With this piece of notation, we can write inequality (A.2.3) as

with $L^{(t)}$ defined in (40). This finishes the proof of (9c) for OMWU.

A.2.4 Proof of convergence of duality gap (9d)

The proof of inequality (9d) is built upon the following lemma whose proof is deferred to Appendix C.4.

The duality gap at $\zeta=(\mu,\nu)$ can be bounded as

Applying Lemma 4 to $\bar{\zeta}^{(t)}=(\bar{\mu}^{(t)},\bar{\nu}^{(t)})$ yields

where the second step results from (9a). It remains to bound \tau\mathsf{KL}\big{(}{{\bar{\zeta}^{(t)}}\,\|\,{\zeta_{\tau}^{\star}}}\big{)}, which we proceed separately for PU and OMWU.

From inequality (35), we are ensured that

where the last inequality is due to inequality (9a). Plugging the above inequality into (55) completes the proof of inequality (9d) for PU.

From inequality (41), we are ensured that

where the last equality follows from L^{(0)}=\mathsf{KL}\big{(}{{\zeta_{\tau}^{\star}}\,\|\,{\zeta^{(0)}}}\big{)}. Plugging the above inequality into (55) finishes the proof of inequality (9d) for OMWU.

A.3 Proof of Theorem 2

To begin, we note that in the no-regret setting, upon receiving $A^{\top}\bar{\mu}^{(t)}$ (which is possibly adversarial), the update rule of player 2 is given by

Recalling $f_{\tau}^{(t)}(\nu)=\bar{\mu}^{(t)\top}A\nu+\tau\mathcal{H}(\bar{\mu}^{(t)})-\tau\mathcal{H}(\nu)$, we introduce an important quantity which is the gradient of $f_{\tau}^{(t)}(\nu)$ at $\bar{\nu}^{(t)}$:

By the definition of $f_{\tau}^{(t)}(\nu)$, we have

where the last line follows from the definition of $\overline{\nabla}^{(t)}$ (cf. (57)). To continue, by the update rule in (56), we have

where the first three steps result from the update rule of $\bar{\nu}^{(t+1)}$, $\nu^{(t)}$ and $\bar{\nu}^{(t)}$, respectively, and the last line follows from (57). Here, $c_{1}$, $c_{2}$, and $c^{(t)}$ are some normalization constants.We shall set $\eta_{-1}=0$ and $\bar{\mu}^{(-1)}=\bar{\mu}^{(0)}$ to accommodate the case when $t=0$ in (59). Rearranging terms allows us to rewrite $\overline{\nabla}^{(t)}$ as

Summing the equality over $t=0,\ldots,T$ gives

Plugging the above relations into (61) leads to

Next, we seek to bound the two terms in (63) separately.

where the final step results from Lemma 5 and the last equality in (62). Summing the above inequality over $t=0,\cdots,T$ yields

where the last line follows from $\sum_{t=0}^{T}\eta_{t}\leq\tau^{-1}(\log T+1)$ due to the choice of the learning rate.

Observe that by the telescoping relation, we have

Due to Pinsker’s inequality and Lemma 3, we have

where the second line follows from (59), the third line follows from the triangle inequality, and the last line follows from Lemma 5. Plugging the above inequality into (65) leads to

where we use again $\sum_{t=0}^{T}\eta_{t}\leq\tau^{-1}(\log T+1)$.

Combining (64) and (66) into (63), we have

Appendix B Analysis for entropy-regularized Markov games

which is, in other words, the minimax value of the associated matrix game using a payoff matrix $Q^{(t)}(s)$. We start by making a simple observation that for $\mu(s)\in\Delta(\mathcal{A}),\nu(s)\in\Delta(\mathcal{B})$,

As a direct consequence, we can control $V^{(t)}(s)-V_{\tau}^{\star}(s)$ by

Recalling the definition of the soft Bellman operator $\mathcal{T}_{\tau}$ in (16), it then follows that

Recursively invoking the above inequality proves inequality (18).

B.2 Proof of Theorem 3

The inner loop of Algorithm 3 aims to solve an entropy-regularized matrix game indexed by $Q^{(t)}(s)$, which is done by running the proposed PU or OMWU methods. To analyze the efficacy of the inner loop, let us denote the exact minimax game value on state $s$ at $t$-th iteration by

which is adopted in the exact value iteration analyzed in Proposition 2, and achieved by the equilibrium $\zeta^{\star(t)}=(\mu^{\star(t)},\nu^{\star(t)})$ of (67).

Denote the output of the inner loop as $\bar{\zeta}^{(t,T_{\text{sub}})}=(\bar{\mu}^{(t,T_{\text{sub}})}(s),\bar{\nu}^{(t,T_{\text{sub}})}(s))$, which the entropy-regularized matrix game (67) is approximately solved by executing PU / OMWU for $T_{\text{sub}}$ iterations. Theorem 1 (cf. (9c)) guarantees that for every $s\in\mathcal{S}$, one has

where the last step makes use of the choice of the learning rate

and \mathsf{KL}\big{(}{{\zeta^{\star(t)}}\,\|\,{\zeta^{(0)}}}\big{)}\leq\log|\mathcal{A}|+\log|\mathcal{B}|\leq 2\log|\mathcal{A}|. As a consequence, setting

We now move to monitor the progress of the outer loop. Combining (69) with some basic calculations, we arrive at

Now invoking the above relation recursively, it is ensured that

In view of the above relation, if one takes

iterations of the outer loop in Algorithm 3, we have $\left\|{Q^{(T_{\text{\rm main}})}-Q_{\tau}^{\star}}\right\|_{\infty}\leq 2\epsilon$ as desired.

Putting things together, the total iteration complexity sufficient to achieve $\epsilon$-accuracy equals to

Therefore the advertised iteration complexity in Theorem 3 holds true by simply noticing that $\eta=\frac{1-\gamma}{2(1+\tau(\log(|\mathcal{A}|)+1))}$ and $\tau<1$, and hence

B.3 Proof of Corollary 1

We begin by recording two supporting lemmas whose proofs are deferred to Appendix C.6 and Appendix C.7.

Let $\zeta_{\tau}^{\star}=(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$ be the QRE of payoff matrix $A$ and $\widetilde{\zeta}^{\star}_{\tau}=(\widetilde{\mu}^{\star}_{\tau},\widetilde{\nu}^{\star}_{\tau})$ be that of $\widetilde{A}$. We have

For any single-agent MDP $(\mathcal{S},\mathcal{A},P,r,\gamma)$ with bounded reward $0\leq r\leq R$, the entropy-regularized value function satisfies

for any two policies $\pi$ and $\pi^{\prime}$.

We are now ready to prove Corollary 1, which we break into a few steps.

It is immediate from Theorem 3 that T_{\mathsf{Q}}=\widetilde{O}\big{(}\frac{1}{\tau(1-\gamma)^{2}}\log^{2}(\frac{1}{\epsilon_{\mathsf{Q}}})\big{)} iterations are sufficient to get a $\widetilde{Q}_{\tau}^{\star}\in{}^{|\mathcal{S}|\times|\mathcal{A}|\times|\mathcal{B}|}$ that achieves

Denote the QRE of the matrix game induced by $\widetilde{Q}_{\tau}^{\star}$ by $\widetilde{\zeta}_{\tau}^{\star}=(\widetilde{\mu}_{\tau}^{\star},\widetilde{\nu}_{\tau}^{\star})$. Specifically, for every $s\in\mathcal{S}$, $(\widetilde{\mu}_{\tau}^{\star}(s),\widetilde{\nu}_{\tau}^{\star}(s))$ solves the entropy-regularized matrix game induced by $\widetilde{Q}_{\tau}^{\star}(s)$. Invoking PU or OMWU with $\eta=\frac{1-\gamma}{2(1+\tau(\log|\mathcal{A}|+1-\gamma))}$ ensures that within T_{\mathsf{policy}}=\widetilde{O}\big{(}\frac{1+\tau\log|\mathcal{A}|}{(1-\gamma)\tau}\log\frac{1}{\epsilon_{\mathsf{policy}}}\big{)} iterations, we can find a policy pair $\zeta=(\mu,\nu)$ such that

Therefore, we can get $\left\|{\log\zeta-\log\zeta_{\tau}^{\star}}\right\|_{\infty}\leq\epsilon\cdot C^{-1}$ within

iterations as long as $C=\textsf{poly}\left({(1-\gamma)^{-1},\tau^{-1},\log|\mathcal{A}|}\right)$.

For any $\mu^{\prime},\nu^{\prime}$ we have

where in each term, only one of the policies is varied. Consequently, it is possible to invoke the well-known performance difference lemma for single-agent MDP.

We note that the same policy $\mu^{\prime}$ appears in both $V_{\tau}^{\mu^{\prime},\nu}(\rho)$ and $V_{\tau}^{\mu^{\prime},\nu_{\tau}^{\star}}(\rho)$, and it is therefore possible to invoke performance difference lemma for single-agent MDP to characterize $V_{\tau}^{\mu^{\prime},\nu}(\rho)-V_{\tau}^{\mu^{\prime},\nu_{\tau}^{\star}}(\rho)$, we construct a MDP $(\mathcal{S},\mathcal{B},\overline{P},\overline{r},\gamma)$ with

and denote the associated entropy-regularized value function by $\overline{V}_{\tau}$. This allows us to write $V_{\tau}^{\mu^{\prime},\nu}(\rho)=\overline{V}_{\tau}^{\nu}(\rho)$ and $V_{\tau}^{\mu^{\prime},\nu_{\tau}^{\star}}(\rho)=\overline{V}_{\tau}^{\nu_{\tau}^{\star}}(\rho)$ (cf. (14)). Applying Lemma 7 with $R=1+\tau\log|\mathcal{A}|$ gives

for the second term in (71). Plugging the above two inequalities into (71) gives

where the last inequality holds as long as $\left\|{\log\zeta-\log\zeta_{\tau}^{\star}}\right\|_{\infty}\leq\epsilon\cdot C^{-1}$ with

Therefore it takes \widetilde{O}\big{(}\frac{1}{\tau(1-\gamma)^{2}}\log^{2}(\frac{1}{\epsilon})\big{)} iterations to achieve

Appendix C Proof of auxiliary lemmas

Lemma 1 follows directly from the update sequence (6) and the form of the optimal solution pair $(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$, provided in (4). Given the update sequence (6), taking logarithm of both sides of the first equation gives

where $c$ is the corresponding normalization constant. By rearranging terms and taking the inner product with $z_{1}-\mu_{\tau}^{\star}$, we have

By summing up equations (72) and (73), it is guarantee that

On the other hand, recall the optimal policy pair $(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$ satisfies the following fixed point equation

Taking logarithm of both sides of the first relation gives

for some normalization constant $c$. Again, by taking the inner product with $z_{1}-\mu_{\tau}^{\star}$, we have

Combining inequalities (72) and (76), we arrive at inequality (22a); combining inequalities (73) and (77) gives inequality (22b). Moreover, putting together inequalities (74), (76) and (77) leads to

C.2 Proof of Lemma 2

We begin with establishing (24a). By the definition of $f_{\tau}(\mu,\nu)$, direct calculations yield

Here, the second equality is obtained by plugging in (75). Similarly, we have

Summing these two equalities completes the proof of (24a).

As a consequence, taking the difference of the above two equations leads to

This in turn allows us to write $f_{\tau}(\mu,\nu)-f_{\tau}(\mu_{\tau}^{\star},\nu_{\tau}^{\star})$ as follows

Finally, plugging (78) and (79) into (80) reveals the desired relation (24b).

C.3 Proof of Lemma 3

The second inequality follows directly from (Mei et al.,, 2020, Lemma 27). The first inequality has appeared, e.g., in Cen et al., 2022b . We reproduce a short proof for self-completeness. By straightforward calculations, the gradient of the function $\log(\left\|{\exp(x)}\right\|_{1})$ is given by

where $x_{c}$ is a certain convex combination of $x_{1}$ and $x_{2}$.

C.4 Proof of Lemma 4

it boils down to control $f_{\tau}(\mu^{\prime},\nu)-f_{\tau}(\mu,\nu^{\prime})$ for any $(\mu^{\prime},\nu^{\prime})\in\Delta(\mathcal{A})\times\Delta(\mathcal{B})$. Towards this, we have

where the last step is due to f_{\tau}(\mu,\nu_{\tau}^{\star})-f_{\tau}(\mu_{\tau}^{\star},\nu)=\tau\mathsf{KL}\big{(}{{\zeta}\,\|\,{\zeta_{\tau}^{\star}}}\big{)}, as revealed in Lemma 2 (cf. (24a)).

Plugging the above two equalities into (81) gives

where the second step invokes Lemma 2 (cf. (24a)), (i) follows from Young’s inequality, namely $ab\leq\frac{a^{2}}{2\varepsilon}+\frac{\varepsilon b^{2}}{2}$ with $\varepsilon=\frac{\left\|{A}\right\|_{\infty}}{\tau}$, and (ii) results from Pinsker’s inequality. Taking maximum over $\mu^{\prime},\nu^{\prime}$ finishes the proof.

C.5 Proof of Lemma 5

First, we show that the update of $\bar{\nu}^{(t)}$ (cf. (56b)) satisfies

For $t=0$, it is easily seen that $\bar{\nu}^{(0)}(b)=\frac{1}{|\mathcal{B}|}\propto\exp([A^{\top}\widetilde{\mu}^{(0)}]_{b}/\tau)$ with $\widetilde{\mu}^{(0)}=0$.

Now assume (82) holds for all steps up to $t$. The update rule (cf. (56b)) implies

with $\widetilde{\mu}^{(t+1)}=(1-\eta_{t}\tau)\widetilde{\mu}^{(t)}+\eta_{t}\tau\bar{\mu}^{(t)}\in\Delta(\mathcal{B})$.

Therefore, the claim (82) holds for all $t>0$.

It then follows from (82) straightforwardly that

for any $b_{1},b_{2}\in\mathcal{B}$. Therefore, we have

which gives $\min_{b\in\mathcal{B}}\bar{\nu}^{(t)}(b)\geq|\mathcal{B}|^{-1}\exp(-2\left\|{A}\right\|_{\infty}/\tau)$, or equivalently

We conclude the proof in view of the expression of $\overline{\nabla}^{(t)}$ in (57):

C.6 Proof of Lemma 6

Instantiating (76) at $z_{1}:=\mu^{\prime\star}_{\tau}$, we have

Similarly, instantiating (77) with $z_{2}:=\nu^{\prime\star}_{\tau}$, we obtain

Summing the above two equalities then leads to

In view of symmetry, the following equality holds as well

Taken the above relations collectively allows us to arrive at

where the second step results from Pinsker’s inequality. Combining (83) and (84) leads to

where the final step invokes (85). Since $\mu_{\tau}^{\star}\propto\exp(-A\nu_{\tau}^{\star}/\tau)$, $\mu^{\prime\star}\propto\exp(-A\nu^{\prime\star}/\tau)$, we invoke Lemma 3 to arrive at

C.7 Proof of Lemma 7

Using the regularized version of the performance difference lemma (see (Zhan et al.,, 2021, Lemma 7) or (Lan,, 2022, Lemma 2)), we have:

To control the first term, we notice that ${Q}_{\tau}(s,a)$ is bounded by $0\leq{Q}_{\tau}(s,a)\leq\frac{R}{1-\gamma}+\frac{\tau\log|\mathcal{A}|}{1-\gamma}$ for all $(s,a)$. Hence, we have

where the second step is due to (Mei et al.,, 2020, Lemma 24).

Turning to the entropy difference term in (86), let

We can then invoke mean value theorem to show

where $\log\xi=c\log\pi(\cdot|s)+(1-c)\log\pi^{\prime}(\cdot|s)$ for some constant $0<c<1$, and the last line follows from $\nabla F(\log\xi)=-\xi-\xi\odot\log\xi$, where $\odot$ denotes point-wise multiplication. Hölder’s inequality guarantees that

Introduce $\overline{\xi}$ which appends a scalar $1-\left\|{\xi}\right\|_{1}$ to $\xi$ as $\overline{\xi}=[\xi^{\top},1-\left\|{\xi}\right\|_{1}]^{\top}$, so that $\overline{\xi}$ is a probability vector. It is straightforward to get

Substitution of the above two inequalities into (88) gives

Plugging (89) and (87) into (86) completes the proof.