Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games

Introduction

Multi-agent reinforcement learning studies how multiple agents should interact with each other and the environment, and has wide applications in, for example, playing board games (Silver et al., 2017) and real-time strategy games (Vinyals et al., 2019). To model these problems, the framework of Markov games (also called stochastic games) (Shapley, 1953) is often used, which can be seen as a generalization of Markov Decision Processes (MDPs) from a single agent to multiple agents. In this work, we focus on one fundamental class: two-player zero-sum Markov games.

In this setting, there are many centralized algorithms developed in a line of recent works with near-optimal sample complexity for finding a Nash equilibrium (Wei et al., 2017; Sidford et al., 2020; Xie et al., 2020; Bai and Jin, 2020; Zhang et al., 2020a; Liu et al., 2021). These algorithms require a central controller that collects some global knowledge (such as the actions and the rewards of all players) and then jointly decides the policies for all players. Centralized algorithms are usually convergent (as defined in (Bowling and Veloso, 2001)), in the sense that the policies of the players converge to the set of Nash equilibria.

On the other hand, there is also a surge of studies on decentralized algorithms that run independently on each player, requiring only local information such as the player’s own action and the corresponding reward feedback (Zhang et al., 2019; Bai et al., 2020; Tian et al., 2021; Liu et al., 2020; Daskalakis et al., 2020). Compared to centralized ones, decentralized algorithms are usually more versatile and can potentially run in different environments (cooperative or competitive). Many of them enjoy the property of being rational (as defined in (Bowling and Veloso, 2001)), in the sense that a player’s policy converges to the best response to the opponent no matter what stationary policy the opponent uses. However, it is also often more challenging to show the convergence to a Nash equilibrium when the two players execute the same decentralized algorithm.

It can be seen that a rational algorithm has different benefits compared to a convergent algorithm – the former satisfies individual player’s interests, while the latter might be better for achieving social good. Therefore, a single algorithm that possesses both properties is highly desirable. For example, in a market where “enforcing” all traders to follow the same rule is difficult, but “recommending” them to use a specific algorithm is possible, a rational and convergent algorithm would be a good candidate — if all traders follow the recommendation, then a social equilibrium is quickly attained; otherwise, those who follow the recommendation are still satisfied because they best respond to a stationary environment.

Based on this motivation, our main contribution is to develop the first decentralized algorithm that is simultaneously rational, last-iterate convergent (with a concrete finite-time guarantee),Note that while average-iterate convergence is possible (and standard) for stateless convex-concave games (e.g. (Syrgkanis et al., 2015)), it does not work for Markov games since the problem is nonconvex-nonconcave in the space of policies (Daskalakis et al., 2020). agnostic, and symmetric (more details to follow in \texorpdfstring\hyperref[subsec: related work]Section 1.1Section 1.1) for two-player zero-sum Markov games. Our algorithm is based on Optimistic Gradient Descent/Ascent (OGDA) (Chiang et al., 2012; Rakhlin and Sridharan, 2013) and importantly relies on a critic that slowly learns a certain value function for each state. Following previous works on learning MDPs (Abbasi-Yadkori et al., 2019; Agarwal et al., 2020) or Markov games (Perolat et al., 2018), we present the convergence guarantee in terms of the number of iterations of the algorithm and the estimation error of some gradient information (along with other problem-dependent constants), where the estimation error can be zero in a full-information setting, or goes down to zero fast enough with additional structural assumptions (e.g. every stationary policy pair induces an irreducible Markov chain, similar to (Auer and Ortner, 2007)).

While the OGDA algorithm, first studied in (Popov, 1980) under a different name, has been extensively used in recent years for learning matrix games (a special case of Markov games with one state), to the best of our knowledge, no previous work has applied it to learning Markov games and derived a concrete last-iterate convergence rate. Several recent works derive last-iterate convergence of OGDA for matrix games (Hsieh et al., 2019; Liang and Stokes, 2019; Mokhtari et al., 2020; Golowich et al., 2020; Wei et al., 2021), and our analysis is heavily inspired by the approach of (Wei et al., 2021). However, the extension to infinite-horizon Markov games is highly non-trivial as there is additional “instability penalty” in the system that we need to handle; see \texorpdfstring\hyperref[sec:analysis]Section 4Section 4 for detailed discussions.

In this section, we discuss and compare related works on learning two-player zero-sum Markov games. We refer the readers to a thorough survey by (Zhang et al., 2020b) for other topics in multi-agent reinforcement learning.

Shapley (1953) first introduces the Markov game model and proposes an algorithm analogous to value iteration for solving two-player zero-sum Markov games (with all parameters known). Later, Hoffman and Karp (1966) propose a policy iteration algorithm, and Pollatschek and Avi-Itzhak (1969) propose another policy iteration variant that works better in practice but cannot always converge. With the efforts of Van Der Wal (1978) and Filar and Tolwinski (1991), a slight variant of the (Pollatschek and Avi-Itzhak, 1969) algorithm is proposed in (Filar and Tolwinski, 1991) and proven to converge. In such a full-information setting where all parameters are know, our algorithm has no estimation error and can also be viewed as a new policy-iteration algorithm.

Littman (1994) initiates the study of competitive reinforcement learning under the framework of Markov games and proposes an extension of the single-player Q-learning algorithm, called minimax-Q, which is later proven to converge under some conditions (Szepesvári and Littman, 1999). While minimax-Q can run in a decentralized manner, it is conservative and only converges to the minimax policy but not the best response to the opponent.

To fix this issue, the work of Bowling and Veloso (2001) argues that a desirable multi-agent learning algorithm should have the following two properties simultaneously: rational and convergent. By their definition, a rational algorithm converges to its opponent’s best response if the opponent converges to a stationary policy,It is tempting to consider an even stronger rationality notion, that is, having no regret against an arbitrary opponent. This is, however, known to be computationally hard (Radanovic et al., 2019; Bai et al., 2020). while a convergent algorithm converges to a Nash equilibrium if both agents use it. They propose the WoLF (Win-or-Learn-Fast) algorithm to achieve this goal, albeit only with empirical evidence. Subsequently, Conitzer and Sandholm (2007); Perolat et al. (2018); Sayin et al. (2020) design decentralized algorithms that provably enjoy these two properties, but only with asymptotic guarantees.

Recently, there is a surge of works that provide finite-time guarantees and characterize the tight sample complexity for finding Nash equilibria (Perolat et al., 2015; Pérolat et al., 2016; Wei et al., 2017; Sidford et al., 2020; Xie et al., 2020; Zhang et al., 2020a; Bai and Jin, 2020; Liu et al., 2021). These algorithms are all essentially centralized. Below, we focus on comparisons with several recent works that propose decentralized algorithms and provide finite-time guarantees.

These algorithms, like minimax-Q, converge to the minimax policy instead of the best response to the opponent, even when the opponent is weak (i.e., not using its best policy). In other words, these algorithms are not rational. Another drawback of these algorithms is that the learner has to observe the actions taken by the opponent. Our algorithm, on the other hand, is both rational and agnostic to what the opponent plays.

Comparison with Optimistic Nash V-Learning (Bai et al., 2020; Tian et al., 2021)

The Optimistic Nash V-Learning algorithm handles the finite-horizon tabular case. It runs an exponential-weight algorithm on each state, with importance-weighted loss/reward estimators. It is unclear whether the dynamics of Optimistic Nash V-Learning leads to last iterate convergence. After training, however, Optimistic Nash V-Learning can output a near-optimal non-Markovian policy with size linear in the training time. In contrast, our algorithm exhibits last-iterate convergence, and the output is a simple Markovian policy.

Comparison with Smooth-FSP (Liu et al., 2020)

The Smooth-FSP algorithm handles the function approximation setting. The objective function it optimizes is the original objective plus an entropy regularization term. Because of this additional regularization, the players are only guaranteed to converge to some neighborhood of the minimax policy pair (with a constant radius), even when their gradient estimation error is zero. In contrast, our algorithm converges to the true minimax policy pair when the gradient estimation error goes to zero.

Comparison with Independent PG (Daskalakis et al., 2020)

Daskalakis et al. (2020) studies independent policy gradient in the tabular case. To achieve last-iterate convergence, the two players have to use asymmetric learning rates, and only the one with a smaller learning rate converges to the minimax policy. In contrast, the two players of our algorithm are completely symmetric, and they simultaneously converge to the equilibrium set.

Preliminaries

We consider a two-player zero-sum discounted Markov game defined by a tuple $(\mathcal{S},\mathcal{A},\mathcal{B},\sigma,p,\gamma)$, where: 1) $\mathcal{S}$ is a finite state space; 2) $\mathcal{A}$ and $\mathcal{B}$ are finite action spaces for Player 1 and Player 2 respectively; 3) $\sigma$ is the loss (payoff) function for Player 1 (Player 2), with $\sigma(s,a,b)\in$ specifying how much Player 1 pays to Player 2 if they are at state $s$ and select actions $a$ and $b$ respectively; 4) $p:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow\Delta_{\mathcal{S}}$ is the transition function, with $p(s^{\prime}|s,a,b)$ being the probability of transitioning to state $s^{\prime}$ after actions $a$ and $b$ are taken by the two players respectively at state $s$ ($\Delta_{\mathcal{S}}$ denotes the set of probability distributions over $\mathcal{S}$); 5) and $\frac{1}{2}\leq\gamma<1$ is a discount factor.The discount factor is usually some value close to $1$, so we assume that it is no less than $\frac{1}{2}$ for simplicity. Also note that we consider the discounted setting instead of the finite-horizon episodic setting because the former captures more challenges of this problem (and is also the original setting considered in (Bowling and Veloso, 2001)). Indeed, in the episodic setting where states have a layered structure, convergence can be directly shown in a layer-by-layer manner; see (Lee et al., 2020), an early version of (Wei et al., 2021).

A stationary policy of Player 1 can be described by a function $\mathcal{S}\rightarrow\Delta_{\mathcal{A}}$ that maps each state to an action distribution. We use $x^{s}\in\Delta_{\mathcal{A}}$ to denote the action distribution for Player 1 on state $s$, and use $x=\{x^{s}\}_{s\in\mathcal{S}}$ to denote the complete policy. We define $y^{s}$ and $y=\{y^{s}\}_{s\in\mathcal{S}}$ similarly for Player 2. For notational convenience, we further define $z^{s}=(x^{s},y^{s})\in\Delta_{\mathcal{A}}\times\Delta_{\mathcal{B}}$ as the concatenated policy of the players on state $s$, and let $z=\{z^{s}\}_{s\in\mathcal{S}}$.

For a pair of stationary policies $(x,y)$ and an initial state $s$, the expected discounted value that the players pay/gain can be represented as

The minimax game value on state $s$ is then defined as

It is known that a pair of stationary policies $(x_{\star},y_{\star})$ attaining the minimax value on state $s$ is necessarily attaining the minimax value on all states (Filar and Vrieze, 2012), and we call such $x_{\star}$ a minimax policy, such $y_{\star}$ a maximin policy, and such pair a Nash equilibrium. Further define \mathcal{X}^{s}_{\star}=\{x^{s}_{\star}\in x_{\star}:\text{x_{\star}is a minimax policy}\} and similarly \mathcal{Y}^{s}_{\star}=\{y^{s}_{\star}\in y_{\star}:\text{y_{\star}is a maximin policy}\}, and denote $\mathcal{Z}_{\star}^{s}=\mathcal{X}^{s}_{\star}\times\mathcal{Y}^{s}_{\star}$. It is also known that any $x=\{x^{s}\}_{s\in\mathcal{S}}$ with $x^{s}\in\mathcal{X}^{s}_{\star}$ for all $s$ is a minimax policy (similarly for $y$) (Filar and Vrieze, 2012).

We also define the Q-function on state $s$ under policy pair $(x,y)$ as

where $\eta$ is some learning rate. As one can see, unlike the standard Gradient Descent Ascent algorithm which simply sets $(x_{t},y_{t})=(\widehat{x}_{t},\widehat{y}_{t})$, OGDA takes a further descent/ascent step using the latest gradient to obtain $(x_{t},y_{t})$, which is then used to evaluate the gradient (of the function $f(x,y)=x^{\top}Qy$). Wei et al. (2021) prove that the iterate $(\widehat{x}_{t},\widehat{y}_{t})$ (or $(x_{t},y_{t})$) converges to the set of Nash equilibria of the matrix game at a linear rate, which motivates us to generalize it to Markov games. As we show in the following sections, however, the extensions of both the algorithm and the analysis are highly non-trivial.

We remark that while Wei et al. (2021) also analyze the last-iterate convergence of another algorithm called Optimistic Multiplicative Weight Update (OMWU), which is even more commonly used in finite-action games, they also show that the theoretical guarantees of OMWU hold under more limited assumptions (e.g., requiring the uniqueness of the equilibrium), and its empirical performance is also inferior to that of OGDA. We therefore only extend the latter to Markov games.

Algorithm and Main Results

A natural idea to extend OGDA to Markov games is to run the same algorithm described in \texorpdfstring\hyperref[sec:prelim]Section 2Section 2 for each state $s$ with the game matrix $Q$ being $Q_{x_{t},y_{t}}^{s}$. However, an important difference is that now the game matrix is changing over time. Indeed, if the polices are changing rapidly for subsequent states, the game matrix $Q_{x_{t},y_{t}}^{s}$ will also be changing rapidly, which makes the update on state $s$ highly unstable and in turn causes similar issues for previous states.

At the end of each iteration $t$, the critic then updates the value function via $V^{s}_{t}=(1-\alpha_{t})V^{s}_{t-1}+\alpha_{t}\rho_{t}^{s}$, where $\rho_{t}^{s}$ is an estimation of $x_{t}^{s^{\top}}Q^{s}_{t}y^{s}_{t}$ such that $|\rho^{s}_{t}-x_{t}^{s^{\top}}Q^{s}_{t}y^{s}_{t}|\leq\varepsilon$.For simplicity, here we assume that the two players share the same estimator $\rho_{t}^{s}$ (and thus same $V^{s}_{t}$ and $Q^{s}_{t}$). However, our analysis works even if they maintain different versions of $\rho_{t}^{s}$, as long as they are $\varepsilon$-close to $x_{t}^{s^{\top}}Q^{s}_{t}y^{s}_{t}$ with respect to their own $Q^{s}_{t}$. To stabilize the game matrix, we require the learning rate $\alpha_{t}$ to decrease in $t$ and go to zero. Most of our analysis is conducted under this general condition, and the final convergence rate depends on the concrete form of $\alpha_{t}$, which we set to $\alpha_{t}=\frac{H+1}{H+t}$ with $H=\frac{2}{1-\gamma}$ inspired by (Jin et al., 2018) (there could be a different choice leading to a better convergence though).

Our main results are the following two theorems on the last-iterate convergence of \texorpdfstring\hyperref[algo: main alg]Algorithm 1Algorithm 1.

[algo: main alg]Algorithm 1Algorithm 1 with the choice of $\alpha_{t}=\frac{H+1}{H+t}$ where $H=\frac{2}{1-\gamma}$ guarantees

[algo: main alg]Algorithm 1Algorithm 1 with the choice of $\alpha_{t}=\frac{H+1}{H+t}$ where $H=\frac{2}{1-\gamma}$ guarantees with $\widehat{z}_{T}^{s}=(\widehat{x}_{T}^{s},\widehat{y}_{T}^{s})$,

[thm: main 1]Theorem 3.1Theorem 3.1 shows that the average duality-gap for each state $s$ goes to zero when both $1/T$ and $\varepsilon$ go to zero, though it does not show the convergence of the policy. \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2, on the other hand, shows a concrete finite-time convergence rate on the distance of $\widehat{z}_{T}^{s}$ from the equilibrium set, which goes down at the rate of $1/T$ up to the estimation error $\varepsilon$. The problem-dependent constant $C$ is similar to the matrix game case analyzed in (Wei et al., 2021), as we will discuss in \texorpdfstring\hyperref[sec:analysis]Section 4Section 4. As far as we know, this is the first symmetric algorithm with finite-time last-iterate convergence for both players simultaneously.

In the full-information setting where all parameters of the Markov game are given, we can calculate the exact value of $Q^{s}_{t}y^{s}_{t}$, $Q_{t}^{s^{\top}}x^{s}_{t}$, and $x_{t}^{s^{\top}}Q^{s}_{t}y^{s}_{t}$, making $\varepsilon=0$. In this case, our algorithm is essentially a new policy-iteration style algorithm for solving Markov games. However, in a learning setting where the parameters are unknown, the players need to estimate these quantities based on any feedback from the environments. Here, we discuss how to do so when the players only observe their current state and their loss/reward after taking an action.

Specifically, in iteration $t$ of our algorithm and with $(x_{t},y_{t})$ at hand, the two players interact with each other for a sequence of $L$ steps, following a mixed strategy with a certain amount of uniform exploration defined via: $\widetilde{x}^{s}_{t}(a)=\left(1-\frac{\varepsilon^{\prime}}{2}\right)x^{s}_{t}(a)+\frac{\varepsilon^{\prime}}{2|\mathcal{A}|}$ and $\widetilde{y}^{s}_{t}(b)=\left(1-\frac{\varepsilon^{\prime}}{2}\right)y^{s}_{t}(b)+\frac{\varepsilon^{\prime}}{2|\mathcal{B}|}$, where $\varepsilon^{\prime}=(1-\gamma)\varepsilon$. This generates a sequence of observations $\{(s_{i},a_{i},\sigma(s_{i},a_{i},b_{i}))\}_{i=1}^{L}$ for Player 1 and similarly a sequence of observations $\{(s_{i},b_{i},\sigma(s_{i},a_{i},b_{i}))\}_{i=1}^{L}$ for Player 2, where $a_{i}\sim\widetilde{x}^{s_{i}}_{t}$, $b_{i}\sim\widetilde{y}^{s_{i}}_{t}$, and $s_{i+1}\sim p(\cdot|s_{i},a_{i},b_{i})$. Then we construct the estimators as follows:

(If any of the denominator is zero, define the corresponding estimator as zero.) To make sure that these are accurate estimators for every state, we naturally need to ensure that every state is visited often enough. To this end, we make the following assumption similar to (Auer and Ortner, 2007), which essentially requires that the induced Markov chain under any stationary policy pair is irreducible.

There exists $\mu>0$ such that $\frac{1}{\mu}=\max_{x,y}\max_{s,s^{\prime}}T^{s\rightarrow s^{\prime}}_{x,y}$, where $T^{s\rightarrow s^{\prime}}_{x,y}$ is the expected time to reach $s^{\prime}$ from $s$ following the policy pair $(x,y)$.

Under this assumption, the following theorem shows that taking $L\approx 1/\varepsilon^{3}$ is enough to ensure the accuracy of the estimators (see \texorpdfstring\hyperref[app: samples]Appendix HAppendix H for the proof).

Together with \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1 and \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2, given a fixed number of interactions between the players, we can now determine optimally how many iterations we should run our algorithm (and consequently how large we should set $\varepsilon$). Equivalently, we show below how many iterations or total interactions are need to achieve a certain accuracy. (The choice of $\alpha_{t}$ is the same as in \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1 and \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2.)

If \texorpdfstring\hyperref[assum:irreducibility]Assumption 1Assumption 1 holds, then running \texorpdfstring\hyperref[algo: main alg]Algorithm 1Algorithm 1 with estimators \texorpdfstring\hyperref[eq: est1]Eq. (7)Eq. (7), \texorpdfstring\hyperref[eq: est2]Eq. (8)Eq. (8), \texorpdfstring\hyperref[eq: est3]Eq. (9)Eq. (9) and $L=\widetilde{\Omega}\left(\tfrac{(|\mathcal{A}|^{3}+|\mathcal{B}|^{3})|\mathcal{S}|^{6}}{(1-\gamma)^{13}\mu\eta^{3}\xi^{6}}\log^{2}(T/\delta)\right)$ for $T=\widetilde{\Omega}\left(\frac{|\mathcal{S}|^{2}}{\eta^{2}(1-\gamma)^{4}\xi^{2}}\right)$ iterations ensures with probability at least $1-\delta$, $\frac{1}{T}\sum_{t=1}^{T}\max_{s,x^{\prime},y^{\prime}}(V^{s}_{\widehat{x}_{t},y^{\prime}}-V^{s}_{x^{\prime},\widehat{y}_{t}})\leq\xi$. Ignoring other dependence, this requires $\widetilde{\Omega}({1}/{\xi^{8}})$ interactions in total.

2 Rationality

Finally, we argue that from the perspective of a single player (take Player 1 as an example), our algorithm is also rational, in the sense that it allows Player 1 to converge to the best response to her opponent if Player 2 is not applying our algorithm but instead uses an arbitrary stationary policy.The rationality defined by Bowling and Veloso (2001) requires that the learner converges to the best response as long as the opponent converges to a stationary policy. While our algorithm does handle this case, as a proof of concept, we only consider the simpler scenario where the opponent simply uses a stationary policy. We show this single-player-perspective version in \texorpdfstring\hyperref[algo: main alg single]Algorithm 2Algorithm 2, where Player 1 still follows the updates \texorpdfstring\hyperref[eq: update 1]Eq. (2)Eq. (2), \texorpdfstring\hyperref[eq: update 2]Eq. (3)Eq. (3), and \texorpdfstring\hyperref[eq: update 5]Eq. (6)Eq. (6), while $y_{t}$ is fixed to a stationary policy $y$ used by Player 2.

[algo: main alg single]Algorithm 2Algorithm 2 with the choice of $\alpha_{t}=\frac{H+1}{H+t}$ where $H=\frac{2}{1-\gamma}$ guarantees

and for $\mathcal{X}_{BR}=\left\{x:V^{s}_{x,y}=\min_{x^{\prime}}V^{s}_{x^{\prime},y},\forall s\in\mathcal{S}\right\}$ and some problem-dependent constant $C^{\prime}>0$,

Analysis Overview

In this section, we give an overview of how we analyze \texorpdfstring\hyperref[algo: main alg]Algorithm 1Algorithm 1 and prove \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1 and \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2. We start by giving a quick review of the analysis of (Wei et al., 2021) for matrix games, and then highlight how we overcome the challenges when generalizing it to Markov games.

Recall the update in \texorpdfstring\hyperref[eq:OGDA_matrix_games]Eq. (1)Eq. (1) for a fixed matrix $Q$. Wei et al. (2021) show the following two convergence guarantees:

where $\Delta(z)=\max_{x^{\prime},y^{\prime}}\left(x^{\top}Qy^{\prime}-x^{\prime\top}Qy\right)$ is the duality gap of $z=(x,y)$.

By taking $\eta\leq\frac{1}{8}$, summing over $t$, canceling the penalty term with the bonus term, telescoping and rearranging, we get $\sum_{t=1}^{T}\Delta^{2}(\widehat{z}_{t})\leq\mathcal{O}(1/\eta^{2})$. An application of Cauchy-Schwarz inequality then proves \texorpdfstring\hyperref[eq: matrix game duality gap]Eq. (10)Eq. (10).

By upper bounding $\|z_{t}-z_{t-1}\|^{2}\leq 2\|z_{t}-\widehat{z}_{t}\|^{2}+2\|\widehat{z}_{t}-z_{t-1}\|^{2}$ and rearranging, they further obtain:

Overview of our proofs

We are now ready to show the high-level ideas of our analysis. For simplicity, we consider the case with $\varepsilon=0$ and also assume that there is a unique equilibrium $(x_{\star},y_{\star})$ (these assumptions are removed in the formal proofs). Our analysis follows the steps below.

Step 1 (\texorpdfstring\hyperref[app: step-1]Appendix BAppendix B)

Similar to \texorpdfstring\hyperref[eq: single step for matrix game]Eq. (12)Eq. (12), we conduct a single-step analysis for OGDA in Markov games (\texorpdfstring\hyperref[lemma: distance decrease]Lemma B.3Lemma B.3), which shows for all state $s$:

Comparing this with \texorpdfstring\hyperref[eq: single step for matrix game]Eq. (12)Eq. (12), we see that, importantly, since the game matrix $Q_{t}^{s}$ is changing over time, we have two extra instability penalty terms: $\eta^{2}\left\|Q_{t}^{s}-Q_{t-1}^{s}\right\|^{2}$ and $\eta\left\|Q_{t}^{s}-Q_{\star}^{s}\right\|$. Our hope is to further upper bound these two penalty terms by something related to $\|z_{t}^{s}-z_{t+1}^{s}\|^{2}$, so that they can again be canceled by the bonus term $-(\left\|\widehat{z}_{t+1}^{s}-z_{t}^{s}\right\|^{2}+\left\|z_{t}^{s}-\widehat{z}_{t}^{s}\right\|^{2})$. Indeed, in Steps 3-5, we show that part of them can be bounded by a weighted sum of $\{\|z_{\tau}^{s^{\prime}}-z_{\tau+1}^{s^{\prime}}\|^{2}\}_{s^{\prime}\in\mathcal{S},\tau\leq t}$.

for some coefficient $\alpha^{\tau}_{t}$ defined in \texorpdfstring\hyperref[app: aux coeff]Appendix A.2Appendix A.2. With recursive expansion, the above implies that $\left\|Q^{s}_{t+1}-Q^{s}_{t}\right\|^{2}$ can be upper bounded by a weighted sum of $\|z_{\tau}^{s^{\prime}}-z_{\tau-1}^{s^{\prime}}\|^{2}$ for $s^{\prime}\in\mathcal{S}$ and $\tau\leq t$.

We first upper bound $\|Q_{t}^{s}-Q_{\star}^{s}\|$ with respect to the following weighted-regret quantity

To do so, we define $\Gamma_{t}=\max_{s}\|Q_{t}^{s}-Q_{\star}^{s}\|$ and show for the same coefficient $\alpha^{\tau}_{t}$ mentioned earlier,

In this step, we further relate $\overline{\text{\rm Reg}}_{t}$ to $\{\|z_{\tau}^{s^{\prime}}-z_{\tau-1}^{s^{\prime}}\|^{2}\}_{\tau\leq t,s^{\prime}\in\mathcal{S}}$. From a one-step regret analysis of OGDA, we have the following (for Player 1):

Recall that $\overline{\text{\rm Reg}}_{t}$ is defined via a weighted sum of the left-hand side above with weights $\alpha^{\tau}_{t}$. Therefore, we take the weighted sum of the above and bound $\sum_{\tau=1}^{t}\alpha^{\tau}_{t}(x_{\tau}^{s}-x_{\star}^{s})^{\top}Q_{\tau}^{s}y_{\tau}^{s}$ by

where in the inequality we rearrange the first summation and use the fact $\alpha^{\tau}_{t}-\alpha^{\tau-1}_{t}\leq\alpha_{\tau-1}\alpha^{\tau}_{t}$ (see the formal proof in \texorpdfstring\hyperref[lem: interval regret discount nonuniform]Lemma E.3Lemma E.3). Since the case for $\sum_{\tau=1}^{t}\alpha^{\tau}_{t}x_{\tau}^{s^{\top}}Q_{\tau}^{s}(y_{\star}^{s}-y_{\tau}^{s})$ is similar, by the definition of $\overline{\text{\rm Reg}}_{t}$, we conclude that $\overline{\text{\rm Reg}}_{t}$ is upper bounded by the maximum over $s$ of the sum of the three terms in \texorpdfstring\hyperref[eq: upper bounde barReg]Eq. (19)Eq. (19). Note that, $\textbf{term}_{2}$ is itself a weighted sum of $\{\|z_{\tau}^{s}-z_{\tau-1}^{s}\|^{2}\}_{\tau\leq t}$, and $\textbf{term}_{3}$ can also be upper bounded by a weighted sum of $\{\|z_{\tau}^{s^{\prime}}-z_{\tau-1}^{s^{\prime}}\|^{2}\}_{\tau\leq t,s^{\prime}\in\mathcal{S}}$ as we already showed in Step 3.

Combining all steps.

Summing up \texorpdfstring\hyperref[eq: single step MG]Eq. (16)Eq. (16) over all $s$, and based on all earlier discussions, we have

Obtaining average duality-gap bound

To obtain the average duality-gap bound in \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1, we sum \texorpdfstring\hyperref[eq: aggre]Eq. (20)Eq. (20) over $t$, and further argue that the sum of $\textbf{term}_{5}$ over $t$ is smaller than the sum of $\textbf{term}_{6}$ over $t$ (hence they are canceled with each other). Rearranging and telescoping leads to

As long as $\alpha_{t}$ is decreasing and going to zero, the right-hand side above can be shown to be sub-linear in $T$. Further relating $\max_{x^{\prime},y^{\prime}}\left(V^{s}_{\widehat{x}_{t},y^{\prime}}-V^{s}_{x^{\prime},\widehat{y}_{t}}\right)$ to $\Delta(\widehat{z}_{t}^{s})$ (\texorpdfstring\hyperref[lem: relate duality gap]Lemma F.5Lemma F.5) proves \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1.

Obtaining last-iterate convergence bound

Then ideally we would like to follow a similar argument from \texorpdfstring\hyperref[eq: matrix game last-iterate]Eq. (14)Eq. (14) to \texorpdfstring\hyperref[eq: linear lastiterate]Eq. (15)Eq. (15) to obtain a last-iterate convergence guarantee. However, we face two more challenges here. First, we have an extra $\textbf{term}_{4}$. Fortunately, this term vanishes when $t$ is large as long as $\alpha_{t}$ decreases and converges to zero. Second, in \texorpdfstring\hyperref[eq: matrix game last-iterate]Eq. (14)Eq. (14), the indices of the negative term $\|\widehat{z}_{t+1}-z_{t}\|^{2}+\|z_{t}-\widehat{z}_{t}\|^{2}$ and the positive term $\eta^{2}\|z_{t}-z_{t-1}\|^{2}$ are only offset by $1$ so that a simple rearrangement is enough to get \texorpdfstring\hyperref[eq: linear lastiterate]Eq. (15)Eq. (15), while in \texorpdfstring\hyperref[eq: aggre last iterate]Eq. (21)Eq. (21), the indices in $\textbf{term}_{6}$ and $\textbf{term}_{5}$ are far from each other. To address this issue, we further introduce a set of weights and consider a weighted sum of \texorpdfstring\hyperref[eq: aggre last iterate]Eq. (21)Eq. (21) over $t$. We then show that the weighted sum of $\textbf{term}_{5}$ can be canceled by the weighted sum of $\textbf{term}_{6}$. Combining the above proves \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2. Note that due to these extra terms, our last-iterate convergence rate is only sublinear (while \texorpdfstring\hyperref[eq: matrix game last itera]Eq. (11)Eq. (11) shows a linear rate for matrix games).

Conclusion and Future Directions

In this work, we propose the first decentralized algorithm for two-player zero-sum Markov games that is rational, convergent, agnostic, symmetric, and having a finite-time convergence rate guarantee at the same time. The algorithm is based on running OGDA on each state, together with a slowly changing critic that stabilizes the game matrix on each state.

Our work studies the most basic tabular setting, and also requires a structural assumption when estimation is needed that sidesteps the difficulty of performing exploration over the state space. Important future directions include relaxing either of these assumptions, that is, extending our framework to allow function approximation and/or incorporating efficient exploration mechanisms. Studying OGDA-based algorithms beyond the two-player zero-sum setting is also an interesting future direction.

This work is supported by NSF Award IIS-1943607 and a Google Faculty Research Award.

References

Appendix A Notations

We define the following notations to simplify the proofs:

Besides, for a matrix $Q$, we define $\left\|Q\right\|=\max_{i,j}|Q_{ij}|$. To avoid cluttered notation, a product of the form $x^{\top}Qy$ is usually simply written as $xQy$.

A.2 Auxiliary Coefficients

In this subsection, we define several coefficients that are related to the value learning rate $\{\alpha_{t}\}$.

($\alpha^{\tau}_{t}$) For non-negative integers $\tau$ and $t$ with $\tau\leq t$, define $\alpha^{\tau}_{t}=\alpha_{\tau}\prod_{i=\tau+1}^{t}(1-\alpha_{i})$.

($\delta^{\tau}_{t}$) For non-negative integers $\tau$ and $t$ with $\tau\leq t$, define $\delta^{\tau}_{t}\triangleq\prod_{i=\tau+1}^{t}(1-\alpha_{i})$.

($\beta^{\tau}_{t}$) For positive integers $\tau$ and $t$ with $\tau<t$, define $\beta^{\tau}_{t}=\alpha_{\tau}\prod_{i=\tau}^{t-1}(1-\alpha_{i}+\alpha_{i}\gamma)$. Define $\beta^{t}_{t}=1$.

($\lambda_{t}$) For positive integers $t$, define $\lambda_{t}=\max\left\{\frac{\alpha_{t+1}}{\alpha_{t}},1-\frac{\alpha_{t}(1-\gamma)}{2}\right\}$.

($\lambda^{\tau}_{t}$) For positive integers $\tau$ and $t$ with $\tau<t$, define $\lambda^{\tau}_{t}=\alpha_{\tau}\prod_{i=\tau}^{t-1}\lambda_{i}$. Define $\lambda^{t}_{t}=1$.

A.3 Auxiliary Variables

In this subsection, we define several auxiliary variables to be used in the later analysis.

($J^{s}_{t}$) For every state $s\in\mathcal{S}$, define the sequence $\{J_{t}^{s}\}_{t=1,2,\ldots}$ by

Furthermore, define $J_{t}\triangleq\max_{s}J_{t}^{s}$.

($K^{s}_{t}$) For every state $s\in\mathcal{S}$, define the sequence $\{K_{t}^{s}\}_{t=1,2,\ldots}$ by

Furthermore, define $K_{t}\triangleq\max_{s}K_{t}^{s}$.

($\widehat{x}_{t\star}^{s},\widehat{y}_{t\star}^{s},\widehat{z}_{t\star}^{s}$) Define $\widehat{x}_{t\star}^{s}=\Pi_{\mathcal{X}_{\star}^{s}}(\widehat{x}_{t}^{s})$, i.e., the projection of $\widehat{x}_{t}^{s}$ onto the set of optimal policy $\mathcal{X}_{\star}^{s}$ on state $s$. Similarly, $\widehat{y}_{t\star}^{s}=\Pi_{\mathcal{Y}_{\star}^{s}}(\widehat{y}_{t}^{s})$, and $\widehat{z}_{t\star}^{s}=\Pi_{\mathcal{Z}_{\star}^{s}}(\widehat{z}_{t}^{s})=(\widehat{x}_{t\star}^{s},\widehat{y}_{t\star}^{s})$.

($\Delta^{s}_{t}$) Define $\Delta^{s}_{t}=\max_{x^{\prime},y^{\prime}}\left(\widehat{x}_{t}^{s}Q_{\star}^{s}y^{\prime s}-x^{\prime s}Q_{\star}^{s}\widehat{y}_{t}^{s}\right)$ for all $t\geq 1$.

($\overline{\text{\rm Reg}}^{s}_{t}$) Define

and $\overline{\text{\rm Reg}}_{t}=\max_{s}\overline{\text{\rm Reg}}_{t}^{s}$.

($\Gamma_{t}$) Define $\Gamma_{t}=\max_{s}\left\|Q_{t}^{s}-Q_{\star}^{s}\right\|$.

($\theta^{s}_{t}$) Define $\theta_{t}^{s}=\frac{1}{16}\|\widehat{z}_{t}^{s}-z_{t-1}^{s}\|^{2}+\frac{1}{16}\|z_{t-1}^{s}-\widehat{z}_{t-1}^{s}\|^{2}$

We require $\alpha_{t}$ to satisfy the following:

$\alpha_{t}\rightarrow 0$ as $t\rightarrow\infty$

Furthermore, $\alpha_{0}\triangleq 1$. Below is an useful lemma that is used in many places:

If $\{h_{t}\}_{t=0,1,2,\ldots}$ and $\{k_{t}\}_{t=1,2,\ldots}$ are non-negative sequences that satisfy $h_{t}=(1-\alpha_{t})h_{t-1}+\alpha_{t}k_{t}$ for $t\geq 1$, then $h_{t}=\sum_{\tau=1}^{t}\alpha^{\tau}_{t}k_{\tau}$.

We prove it by induction. When $t=1$, since $\alpha_{1}=1$, $h_{1}=k_{1}=\alpha^{1}_{1}k_{1}$. Assume that the formula is correct for $h_{t}$. Then

$V^{s}_{t}=\sum_{\tau=1}^{t}\alpha^{\tau}_{t}\rho^{s}_{\tau}$

$J_{t}^{s}=\sum_{\tau=1}^{t}\alpha^{\tau}_{t}\left\|z_{\tau}^{s}-z_{\tau-1}^{s}\right\|^{2}$

$K_{t}^{s}=\sum_{\tau=1}^{t}\alpha^{\tau}_{t}\left\|Q_{\tau}^{s}-Q_{\tau-1}^{s}\right\|^{2}$

They immediately follow from \texorpdfstring\hyperref[lemma: recur1]Lemma A.15Lemma A.15 and the definition of $J_{t}^{s},K_{t}^{s},V^{s}_{t}$.

Appendix B Proof for Step 1: Single-Step Inequality

By standard proof of OGDA (see, e.g., the proof of Lemma 1 in (Wei et al., 2021) or Lemma 1 in (Rakhlin and Sridharan, 2013)), we have

Combining them with \texorpdfstring\hyperref[eq: x-regret]Eq. (22)Eq. (22) and the fact that $\eta\varepsilon\leq\frac{\eta}{1-\gamma}\leq\frac{1}{8}$, we get the first inequality that we want to prove. The other inequality is similar.

Summing up the two inequalities in \texorpdfstring\hyperref[lem: one-step regret bound]Lemma B.1Lemma B.1, we get

The left-hand side above, can be lower bounded by

Combining the inequalities and using the definition of $\theta^{s}_{t}$ finish the proof.

By \texorpdfstring\hyperref[eq: update 1]Eq. (2)Eq. (2) and the optimality condition for $\widehat{x}_{t+1}^{s}$, we have

where in the last inequality we use \texorpdfstring\hyperref[eq: temp100]Eq. (23)Eq. (23). Thus we have for any $x^{\prime s}\in\Delta_{\mathcal{A}}$,

Using the fact that $\frac{\eta}{1-\gamma}\leq\frac{1}{16}$, we get

Similarly, we have $\|\widehat{y}_{t+1}^{s}-y_{t}^{s}\|+\|y_{t}^{s}-\widehat{y}_{t}^{s}\|+\sqrt{2}\eta\varepsilon\geq\frac{\eta}{2}\max_{y^{\prime}}x_{t}^{s}Q_{t}^{s}(y^{\prime s}-y_{t}^{s})$. Combining them and using $\left\|z-z^{\prime}\right\|\geq\frac{1}{2}\left\|x-x^{\prime}\right\|+\frac{1}{2}\left\|y-y^{\prime}\right\|$, we get

(Key Lemma for Average Duality-gap Bounds) For all $t\geq 1$, we have

Combining \texorpdfstring\hyperref[lem: step-2]Lemma C.1Lemma C.1 with \texorpdfstring\hyperref[lemma: distance decrease]Lemma B.3Lemma B.3, we get

(Key Lemma for Point-wise Convergence Bounds) There exists a constant $C^{\prime}>0$ (which depends on the transition and the loss/payoff functions) such that for all $t\geq 1$,

By Theorem 5 of (Wei et al., 2021) or Lemma 3 of (Gilpin et al., 2012), we have

for some problem-dependent constant $0<C\leq\frac{1}{1-\gamma}$ ($C$ depends on $\{Q^{s}_{\star}\}_{s}$). Thus \texorpdfstring\hyperref[theorem: main theorem discount]Theorem C.3Theorem C.3 implies

By defining $C^{\prime 2}=\frac{C^{2}}{128}$, we further get

Notice that $\frac{5}{1+\eta^{2}C^{\prime 2}}\geq\frac{5}{1+\frac{1}{16^{2}}\times\frac{1}{128}}\geq 4.5$. Thus we further have

where in the last inequality we use $\frac{1}{1+\eta^{2}C^{\prime 2}}\leq\frac{4.5}{1+\eta^{2}C^{\prime 2}}-3$ because $\eta^{2}C^{\prime 2}\leq\frac{1}{16^{2}}\times\frac{1}{128}$.

We have for $t\geq 2$ and all $s\in\mathcal{S}$,

It is equivalent to prove that for all $t\geq 1$,

Now it suffices to upper bound $\left(V_{t}^{s}-V_{t-1}^{s}\right)^{2}$ for any $s$. By \texorpdfstring\hyperref[cor: useful corollary]Corollary A.17Corollary A.17, we have $V_{t-1}^{s}=\sum_{\tau=1}^{t-1}\alpha^{\tau}_{t-1}\rho^{s}_{\tau}$. Therefore,

where we use $(a+b+c+d+e)^{2}\leq\frac{8}{1-\gamma}a^{2}+\frac{2}{1+\gamma}b^{2}+\frac{8}{1-\gamma}c^{2}+\frac{8}{1-\gamma}d^{2}+\frac{8}{1-\gamma}e^{2}$ which is due to Cauchy-Schwarz inequality. By \texorpdfstring\hyperref[lemma: recur1]Lemma A.15Lemma A.15 and the definitions of $J^{s}_{t}$, $K^{s}_{t}$, $J_{t}$, $K_{t}$ in \texorpdfstring\hyperref[def: cumm path length]Definition A.7Definition A.7 and \texorpdfstring\hyperref[def: cumm Q diff]Definition A.8Definition A.8,

Combining them with the previous upper bound for $(V_{t}^{s}-V_{t-1}^{s})^{2}$, we get

for all $s$. Further combining this with \texorpdfstring\hyperref[eq: relate Q to V]Eq. (26)Eq. (26), we get

Summing the first bound in \texorpdfstring\hyperref[lem: one-step regret bound]Lemma B.1Lemma B.1 over $\tau=1,\ldots,t$ with weights $\alpha^{\tau}_{t}$, and dropping negative terms $-\|\widehat{x}_{t+1}^{s}-x_{t}^{s}\|^{2}-\|x_{t}^{s}-\widehat{x}_{t}^{2}\|^{2}$, we get

Observe that by definition, we have for $\tau\geq 2$,

where in the inequality we use $\alpha_{\tau}\leq\alpha_{\tau-1}$. Using this in \texorpdfstring\hyperref[eq: temp 167]Eq. (27)Eq. (27), we get

Using $J_{n}^{s}\leq J_{n},K_{n}^{s}\leq K_{n}$, and the definition of $Z_{t},\overline{\text{\rm Reg}}_{t}$ finishes the proof.

Appendix F Combining Lemmas to Show Last-iterate Convergence

In this section, we provide proofs for \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1 and \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2. To achieve so, we first prove \texorpdfstring\hyperref[lemma: ut bound]Lemma F.1Lemma F.1 by combining the results in \texorpdfstring\hyperref[app: step-3]Appendix DAppendix D and \texorpdfstring\hyperref[app: step-4-5]Appendix EAppendix E. Then we combine \texorpdfstring\hyperref[theorem: main theorem discount]Theorem C.3Theorem C.3, \texorpdfstring\hyperref[lemma: using SPRSI]Lemma C.5Lemma C.5, and \texorpdfstring\hyperref[lemma: ut bound]Lemma F.1Lemma F.1 to prove \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1 and \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2.

where $C_{1}=1152\times 80$ and $C_{2}=10$.

By \texorpdfstring\hyperref[lem: key lemma 1]Lemma D.1Lemma D.1, for all $t\geq 2$,

By \texorpdfstring\hyperref[lem: optimistic lemma discount]Lemma E.1Lemma E.1 and \texorpdfstring\hyperref[lem: interval regret discount nonuniform]Lemma E.3Lemma E.3, for all $t\geq 2$,

Now, multiply \texorpdfstring\hyperref[eq: final 2]Eq. (29)Eq. (29) with $\frac{1-\gamma}{16}$, and then add it to \texorpdfstring\hyperref[eq: final 1]Eq. (28)Eq. (28). Then we get that for $t\geq 2$,

where in the second inequality we use that $\frac{2\gamma^{2}}{1+\gamma}+\frac{1-\gamma}{4}-\gamma=(1-\gamma)\left(\frac{1}{4}-\frac{\gamma}{1+\gamma}\right)\leq 0$ since $\gamma\geq\frac{1}{2}$, and in the last inequality, we use $K^{s}_{t-1}=\sum_{\tau=1}^{t-1}\alpha^{\tau}_{t-1}\|Q^{s}_{\tau}-Q^{s}_{\tau-1}\|^{2}$. Define the new variable

Then the above implies that for all $t\geq 2$,

Observe that \texorpdfstring\hyperref[eq: key 1]Eq. (30)Eq. (30) is in the form of \texorpdfstring\hyperref[lemma: double recursion]Lemma G.1Lemma G.1 with the following choices:

because $u_{t}\leq\frac{\eta^{2}}{(1-\gamma)^{2}}+\frac{1-\gamma}{16}\leq\frac{1-\gamma}{2}$. Further using \texorpdfstring\hyperref[lemma: triple recursion]Lemma G.3Lemma G.3 on the first two terms on the right-hand side, and noticing that $\frac{1}{\gamma^{2}}\leq 4$, we further get that for $t\geq 2$,

Finally, notice that according to the definition of $u_{t}$, we have $5\eta\Gamma_{t}+8\eta^{2}\left\|Q_{t}^{s}-Q^{s}_{t-1}\right\|^{2}\leq\frac{80}{1-\gamma}u_{t}$. Combining \texorpdfstring\hyperref[eq: key 3]Eq. (31)Eq. (31), we finish the proof for case for $t\geq 2$. The case for $t=1$ is trivial since $5\eta\Gamma_{t}+8\eta^{2}\left\|Q_{t}^{s}-Q^{s}_{t-1}\right\|^{2}\leq 1\leq 80=80\beta^{1}_{1}$.

of \texorpdfstring\hyperref[thm: main 1]Theorem 3.1Theorem 3.1. Define $C_{\alpha}(T)\triangleq 1+\sum_{t=1}^{T}\alpha_{t}$ and let $C_{\beta}$ be an upper bound of $\sum_{t=\tau}^{\infty}\beta^{\tau}_{t}$ for any $\tau$. With the choice of $\alpha_{t}$ specified in the theorem, we have $C_{\alpha}(T)=1+\sum_{t=1}^{T}\frac{H+1}{H+t}=\mathcal{O}\left(H\log T\right)=\mathcal{O}\left(\frac{\log T}{1-\gamma}\right)$. By \texorpdfstring\hyperref[lem: sum of beta 1]Lemma G.15Lemma G.15, we have $C_{\beta}\leq\frac{2}{1-\gamma}+3$. Define $S=|\mathcal{S}|$.

Combining \texorpdfstring\hyperref[lemma: ut bound]Lemma F.1Lemma F.1 and \texorpdfstring\hyperref[theorem: main theorem discount]Theorem C.3Theorem C.3, we get that for $t\geq 1$,

Summing the above over $s\in\mathcal{S}$ and $t\in[T-1]$, and denoting $\Theta_{t}=\sum_{s}\theta_{t}^{s}$, we get

and $\sum_{t=1}^{T}\beta^{1}_{t}\leq C_{\beta}$. Combining these three inequalities with \texorpdfstring\hyperref[eq: tmp bound]Eq. (32)Eq. (32), we get

By Cauchy-Schwarz inequality, we further have

Finally, by \texorpdfstring\hyperref[lem: relate duality gap]Lemma F.5Lemma F.5, we get

of \texorpdfstring\hyperref[thm: main 2]Theorem 3.2Theorem 3.2. Combining \texorpdfstring\hyperref[lemma: using SPRSI]Lemma C.5Lemma C.5 and \texorpdfstring\hyperref[lemma: ut bound]Lemma F.1Lemma F.1, we get that for all $t\geq 1$,

The key idea of the following analysis is to use the negative (bonus) term $-3\Theta_{t}$ to cancel the positive (penalty) term $\frac{C_{1}S\eta^{2}}{(1-\gamma)^{4}}\sum_{\tau=1}^{t}\beta^{\tau}_{t}\Theta_{\tau}$. Since the time indices do not match, we perform smoothing over time to help. Consider the following weighted sum of $L_{\tau}+4.5\Theta_{\tau}$ with weights $\lambda^{\tau}_{t+1}$:

where in the second-to-last inequality we use \texorpdfstring\hyperref[lem: consecutive lambda for special choice]Lemma G.17Lemma G.17: with the special choice of $\alpha_{t}$ specified in the theorem, we have $\lambda^{\tau}_{t}=\alpha_{t}\leq\lambda^{\tau+1}_{t}$ for $\tau\leq t-1$.

Let $t_{0}=\min\left\{\tau:\frac{3C_{2}S}{1-\gamma}\alpha_{\tau}\leq\frac{\eta^{2}C^{\prime 2}}{2}\right\}$. Then we have

Finally, we add $\lambda^{1}_{t+1}(L_{1}+4.5\Theta_{1})$ to both sides, and note that

where the first and second equality is by \texorpdfstring\hyperref[lem: consecutive lambda for special choice]Lemma G.17Lemma G.17. Then we get

Then we can further write that for $t\geq 1$,

Applying \texorpdfstring\hyperref[lemma: final recursion]Lemma G.13Lemma G.13 with $c=\frac{0.1\eta^{2}C^{\prime 2}}{1+0.1\eta^{2}C^{\prime 2}}$, $g_{t}=Y_{t+1}$, $h_{t}=\frac{274C_{2}S^{2}t_{0}}{1-\gamma}\lambda_{t}^{\min\{t_{0},t\}}+\frac{87S\eta\varepsilon}{(1-\gamma)^{2}}\sum_{\tau=1}^{t}\lambda_{t}^{\tau}$, we get

With the choice of $\alpha_{t}=\frac{H+1}{H+t}$ where $H=\frac{2}{1-\gamma}$, we have

Combining them and noticing that $(1+0.1\eta^{2}C^{\prime 2})^{-\frac{t}{2}}=\mathcal{O}(\frac{1}{t})$ when $t\geq\frac{20}{\eta^{2}C^{\prime 2}}$, we get that for $t\geq 2t_{0}=\Theta\left(\frac{S}{(1-\gamma)^{2}\eta^{2}C^{\prime 2}}\right)$,

Since $Y_{t}\leq 22S+22S(t-1)\alpha_{t}\leq\mathcal{O}(\frac{S\log t}{1-\gamma})$, the above bound also trivially holds for $t\leq 2t_{0}$. Then noticing that $L_{t}\leq Y_{t}$ finishes the proof.

For any policy pair $x,y$, the duality gap on the game can be related to the duality gap on individual states as follows:

Notice that for any policy $x$ and state $s$,

Taking max over $s$ on two sides and rearranging, we get

Appendix G Auxiliary Lemmas

Let $\{g_{t}\}_{t=1,2,\ldots},\{h_{t}\}_{t=1,2,\ldots}$ be non-negative sequences that satisfy $g_{t}\leq\gamma\sum_{\tau=1}^{t-1}\alpha^{\tau}_{t-1}g_{\tau}+h_{t}$ for all $t\geq 1$. Then $g_{t}\leq\sum_{\tau=1}^{t}\beta^{\tau}_{t}h_{\tau}$.

We prove it by induction. When $t=1$, the condition guarantees $g_{1}\leq h_{1}=\beta^{1}_{1}h_{1}$. Suppose that it holds for $1,\ldots,t-1$. Then

It remains to prove that $\sum_{\tau=i}^{t-1}\gamma\alpha^{\tau}_{t-1}\beta^{i}_{\tau}\leq\beta^{i}_{t}$ for all $i\leq t-1$. We use another induction to show this. Fix $i$ and $t$, and define the partial sum $\zeta_{r}=\sum_{\tau=i}^{r}\gamma\alpha^{\tau}_{t-1}\beta^{i}_{\tau}$ for $r\in[i,t-1]$. Below we show that

Notice that the right-hand side above is $\beta^{i}_{t}$ when $r=t-1$, which is exactly what we want to prove.

When $r=i$, $\zeta_{r}=\gamma\alpha^{i}_{t-1}=\gamma\alpha_{i}\prod_{\tau=i+1}^{t-1}(1-\alpha_{\tau})\leq\alpha_{i}(1-\alpha_{i}+\alpha_{i}\gamma)\prod_{\tau=i+1}^{t-1}(1-\alpha_{\tau})$ where the inequality is because $1-\alpha_{i}+\alpha_{i}\gamma-\gamma=(1-\alpha_{i})(1-\gamma)\geq 0$. Now assume that \texorpdfstring\hyperref[eq: double induction]Eq. (34)Eq. (34) holds up to $r$ for some $r\geq i$. Then

Let $\{h_{t}\}_{t=1,2,\ldots}$ and $\{k_{t}\}_{t=1,2,\ldots}$ be non-negative sequences that satisfy $h_{t}=\sum_{\tau=1}^{t}\alpha^{\tau}_{t}k_{\tau}$. Then $\sum_{\tau=2}^{t}\beta^{\tau}_{t}h_{\tau-1}\leq\frac{1}{\gamma^{2}}\sum_{\tau=1}^{t-1}\beta^{\tau}_{t}k_{\tau}.$

It remains to prove that for $i<t$, $\sum_{\tau=i+1}^{t}\beta^{\tau}_{t}\alpha^{i}_{\tau-1}\leq\frac{1}{\gamma^{2}}\beta^{i}_{t}$, or equivalently, $\gamma\sum_{\tau=i+1}^{t}\beta^{\tau}_{t}\alpha^{i}_{\tau-1}\leq\frac{1}{\gamma}\beta^{i}_{t}$. Below we use another induction to prove this. Fix $i$ and $t$, and define the partial sum $\zeta_{r}=\gamma\sum_{\tau=r}^{t}\beta^{\tau}_{t}\alpha^{i}_{\tau-1}$ for $r\in[i+1,t]$. We will show that

Suppose that \texorpdfstring\hyperref[eq: recur hard]Eq. (35)Eq. (35) holds up to $r$ for some $r\leq t$. Then

This finishes the induction. Applying the result with $r=i+1$, we get

where the last inequality is by $1-\alpha_{i}+\alpha_{i}\gamma-\gamma=(1-\alpha_{i})(1-\gamma)\geq 0$. This finishes the proof.

For $0\leq h\leq t$, $\sum_{\tau=0}^{h}\alpha^{\tau}_{t}=\delta^{h}_{t}$.

We prove it by induction on $h$. When $h=0$, $\sum_{\tau=0}^{h}\alpha^{\tau}_{t}=\alpha^{0}_{t}=\prod_{\tau=1}^{t}(1-\alpha_{\tau})=\delta^{h}_{t}$ since $\alpha_{0}=1$. Suppose that the formula holds for $h$. Then $\sum_{\tau=0}^{h+1}\alpha^{\tau}_{t}=\sum_{\tau=0}^{h}\alpha^{\tau}_{t}+\alpha^{h+1}_{t}=\prod_{\tau=h+1}^{t}(1-\alpha_{\tau})+\alpha_{h+1}\prod_{\tau=h+2}^{t}(1-\alpha_{\tau})=\prod_{\tau=h+2}^{t}(1-\alpha_{\tau})=\delta^{h+1}_{t}$, which finishes the induction.

For any positive integers $i,t$ with $i\leq t$, $\sum_{\tau=i}^{t}\lambda^{\tau}_{t}\beta^{i}_{\tau}\leq\frac{3}{1-\gamma}\lambda^{i}_{t}$.

for $r\in[i+1,t]$. When $r=t$, $\sum_{\tau=r}^{t}\lambda^{\tau}_{t}\beta^{i}_{\tau}=\lambda^{t}_{t}\beta^{i}_{t}=\beta^{i}_{t}=\alpha_{i}\prod_{\tau=i}^{t-1}(1-\alpha_{\tau}(1-\gamma))$. Suppose this holds for some $r\leq t$. Then

which finishes the induction. Notice that this implies

where the second inequality is by the definition of $\lambda_{i}$. Thus,

$\lambda^{\tau+1}_{t+1}\leq\lambda^{\tau}_{t}$.

where in the first inequality we use $\lambda_{t}\leq 1$ and in the second inequality we use the definition of $\lambda_{\tau}$. When $\tau=t$, we have $\frac{\lambda^{\tau+1}_{t+1}}{\lambda^{\tau}_{t}}=\frac{1}{1}=1$.

$\sum_{\tau=1}^{t}\beta^{\tau}_{t}\leq\frac{2}{1-\gamma}$.

Below we use induction to prove that for all $r=1,2,\ldots,t-1$,

When $r=1$, the left-hand side is $\beta^{1}_{t}=\alpha_{1}\prod_{i=1}^{t-1}(1-\alpha_{i}+\alpha_{i}\gamma)\leq\frac{1}{1-\gamma}\prod_{i=1}^{t-1}(1-\alpha_{i}+\alpha_{i}\gamma)$, which is the right-hand side.

Therefore, $\sum_{\tau=1}^{t}\beta^{\tau}_{t}=1+\sum_{\tau=1}^{t-1}\beta^{\tau}_{t}\leq 1+\frac{1}{1-\gamma}\leq\frac{2}{1-\gamma}$.

Let $\{g_{t}\}_{t=0,1,2,\ldots}$, $\{h_{t}\}_{t=1,2,\ldots}$ be non-negative sequences that satisfy $g_{t}\leq(1-c)g_{t-1}+h_{t}$ for some $c\in(0,1)$ for all $t\geq 1$. Then

The case of $t=1$ is clear. Suppose that this holds for $g_{t}$. Then

𝐻1𝐻𝑡\alpha_{t}=\frac{H+1}{H+t} Lemma G.15. For the choice $\alpha_{t}=\frac{H+1}{H+t}$ with $H\geq\frac{2}{1-\gamma}$, we have $\sum_{t=\tau}^{\infty}\beta^{\tau}_{t}\leq H+3$.

and thus $\sum_{t=\tau}^{\infty}\beta^{\tau}_{t}\leq H+3$.

For the choice $\alpha_{t}=\frac{H+1}{H+t}$ with $H\geq\frac{2}{1-\gamma}$, we have $\lambda^{\tau}_{t}=\alpha_{t}$ for $\tau<t$.

By the condition, we have $\frac{1-\gamma}{2}\times\frac{H+1}{H+t}\geq\frac{1}{H+t}\geq\frac{1}{H+t+1}$. Therefore, $\lambda_{t}=\frac{H+t}{H+t+1}=\frac{\alpha_{t+1}}{\alpha_{t}}$. Thus for $\tau<t$,

Appendix H Analysis on Sample Complexity

Therefore, with probability at least $1-\delta$, \texorpdfstring\hyperref[eq: epsA]Eq. (38)Eq. (38) holds if

Now it remains to determine $L$ to make \texorpdfstring\hyperref[eq: Az1]Eq. (39)Eq. (39) hold with high probability. Note that by \texorpdfstring\hyperref[assum:irreducibility]Assumption 1Assumption 1, we know that $T^{s^{\prime}\rightarrow s}_{\widetilde{x}_{t},\widetilde{y}_{t}}\leq\frac{1}{\mu}$ for any $s^{\prime}$. Let $\mathcal{T}_{s,a}$ be the distribution of random variable which is the number of rounds between the current state-action pair $(s^{\prime},a^{\prime})$ and the next occurrence of $(s,a)$ under strategy $\widetilde{x}_{t}^{s}$ and $\widetilde{y}_{t}^{s}$. The mean of this distribution is $t_{s,a}\leq 1+\frac{2|\mathcal{A}|}{\varepsilon^{\prime}\mu}\leq\frac{3|\mathcal{A}|}{\varepsilon^{\prime}\mu}$. Then by Markov inequality,

Therefore, with probability at least $1-\frac{\delta}{L}$, within $\Theta(\frac{|A|}{\varepsilon^{\prime}\mu}\log(L/\delta))$ rounds, we reach $(s,a)$ state-action at least pair once. Thus, \texorpdfstring\hyperref[eq: Az1]Eq. (39)Eq. (39) holds when $L=\Omega\left(\frac{|\mathcal{A}|^{3}}{\varepsilon^{\prime}\mu\varepsilon^{2}}\log^{2}(L/\delta)\right)$ with probability $1-\delta$. Solving $L$ gives $L=\widetilde{\Omega}\left(\frac{|\mathcal{A}|^{3}}{(1-\gamma)\mu\varepsilon^{3}}\log^{2}({1}/{\delta})\right)$. The cases for $r_{t}^{s}(b)$ and $\rho^{s}_{t}$ are similar. Finally, using a union bound on all $\mathcal{A}$, $\mathcal{B}$, $\mathcal{S}$, and all iterations, we know that with probability $1-\delta$, the $\varepsilon$-approximations are always guaranteed if we use the estimation above and take $L=\widetilde{\Omega}\left(\frac{|\mathcal{A}|^{3}+|\mathcal{B}|^{3}}{(1-\gamma)\mu\varepsilon^{3}}\log^{2}(T/{\delta})\right)$.