1 Introduction↩︎

Reinforcement learning has become an increasingly popular framework for solving large-scale sequential decision-making problems due to its solid theoretical foundation [1] and remarkable empirical successes [2]. However, real-world applications, such as autonomous driving and robotics, often involve multiple decision-makers interacting in a common environment with possibly misaligned goals [3]. In these scenarios, practical multi-agent reinforcement learning (MARL) algorithms are often extended directly from their single-agent counterparts, overlooking the adaptive strategies of multiple agents. Consequently, the resulting algorithms can be unreliable. For example, even in the game of Go, super-human AIs are susceptible to adversarial attacks [4].

To realize the practical potential of MARL, a growing body of literature seeks to provide theoretical insights into MARL and inform the design of efficient and provably convergent algorithms. Related work in this area can be broadly categorized into cooperative MARL, where agents share a common goal [5]–[8], and competitive MARL, where agents have individual objectives [9]–[13]. While early work in this area focused on asymptotic convergence, there is increasing interest in understanding the finite-time/sample behavior of MARL algorithms. Compared with asymptotic analysis, finite-sample analysis provides more detailed theoretical insights into algorithmic behavior and can also guide implementation.

In this paper, we consider the benchmark settings of two-player zero-sum matrix games and stochastic (Markov) games, and focus on best-response-based learning algorithms. As one of the most natural and fundamental classes of adaptive learning algorithms [14]–[16], these learning algorithms update each player’s policy incrementally toward an estimated smoothed best response to its opponent’s latest policy. Moreover, they are independent, requiring no explicit coordination between players during learning, and rational, in the sense that each player converges to the (smoothed) best response to the opponent when the opponent plays an (asymptotically) stationary policy [17]. This is consistent with the setting of learning among self-interested players, where communication or coordination should not be imposed. Moreover, we study these learning algorithms in the challenging setting of decentralized learning, where each player observes only the state and its own realized payoff at each stage, without knowing the opponent’s policy or actions.

From this perspective, our goal is to understand whether such canonical best-response-based learning algorithms can be implemented in a decentralized manner while retaining provable finite-sample guarantees. Our contributions are detailed as follows.

• Two-Player Zero-Sum Matrix Games. We begin with the matrix-game setting, which serves both as a stateless benchmark and as the building block for the stochastic-game setting. We analyze the best-response-based learning algorithm first proposed in [18], in which both players update symmetrically using only their own realized payoff observations. We establish finite-sample bounds under both constant and diminishing stepsizes. These bounds imply a sample complexity of \(\mathcal{O}(\epsilon^{-1})\) for finding an \(\epsilon\)-Nash distribution [19]. Since a Nash distribution is generally different from a Nash equilibrium, this guarantee does not directly yield a sample complexity polynomial in \(\epsilon^{-1}\) for finding an \(\epsilon\)-Nash equilibrium. We identify the lack of exploration as the key obstacle, introduce an exploration-encouraging variant, and show that it achieves a sample complexity of \(\tilde{\mathcal{O}}(\epsilon^{-8})\) for finding an \(\epsilon\)-Nash equilibrium. To the best of our knowledge, for zero-sum matrix games, this is the first finite-sample guarantee for best-response-based learning algorithm that is simultaneously payoff-based, convergent, and symmetric between the two players.

• Two-Player Zero-Sum Stochastic Games. Building on the matrix-game analysis, we develop a learning algorithm named value iteration with smoothed best-response (VI-SBR) for stochastic games. The learning algorithm consists of two loops: an inner loop that runs the aforementioned smoothed best-response-based learning algorithm for an induced auxiliary matrix game, and an outer loop that performs a decentralized and model-free approximation of minimax value iteration. We establish finite-sample bounds for the VI-SBR algorithm. As in the matrix-game setting, however, the lack of exploration prevents these bounds from directly yielding a sample complexity polynomial in \(\epsilon^{-1}\) for finding an \(\epsilon\)-Nash equilibrium. We therefore introduce an exploration-enhanced variant and prove that it achieves a sample complexity of \(\tilde{\mathcal{O}}(\epsilon^{-8})\) for finding an \(\epsilon\)-Nash equilibrium. To the best of our knowledge, this is the first finite-sample analysis of best-response-based learning algorithm that is simultaneously decentralized, convergent, and rational for two-player zero-sum stochastic games.

• Technical Contributions. The key challenge in our analysis, in both the matrix-game and stochastic-game settings, is that they involve multiple sets of stochastic iterates updated in a coupled manner. To address this challenge, we develop a coupled Lyapunov-based approach: we construct a Lyapunov function for each set of stochastic iterates, establish the corresponding Lyapunov drift inequality, and then combine these drift inequalities to derive convergence rates. Several components are specific to stochastic games: a generalized regularized Nash-gap Lyapunov function for auxiliary matrix games that are not exactly zero-sum during learning, a Lyapunov function that tracks the non-zero-sum error induced by independently maintained value functions, and a treatment of time-inhomogeneous Markovian noise generated by time-varying policies. A more detailed discussion of the challenges and proof techniques is provided in Section 4. More broadly, the coupled Lyapunov-drift framework developed in this paper offers a systematic approach to analyzing learning algorithms in which multiple stochastic iterates evolve jointly under nonstationary, policy-dependent sampling processes.

This paper builds upon and significantly extends the conference version [20], which provided a finite-sample analysis of decentralized learning algorithms for two-player zero-sum matrix and stochastic games. A major limitation of [20] is that its bounds do not yield polynomial dependence on \(\epsilon^{-1}\) for finding an \(\epsilon\)-Nash equilibrium. We address this limitation by identifying the lack of exploration as the source of the exponential dependence and by introducing exploration-enhanced variants whose sample complexities depend polynomially on \(\epsilon^{-1}\).

1.1 Related Literature↩︎

In this subsection, we review the most relevant work on reinforcement learning for matrix and stochastic games.

Zero-Sum Matrix Games. Fictitious play (FP) [21], [22] is one of the earliest methods of independent learning in zero-sum matrix games and, together with its smoothed variant [14], [23], can be analyzed by the associated ordinary differential equation/inclusion of (smoothed) best-response dynamics using a Lyapunov approach [15]. Notably, the Lyapunov function used in such an analysis is the regularized Nash gap [15], [19], [24], a variant of which is also employed in our analysis framework. To adapt the learning algorithm to the payoff-based setting, [18] developed a two-timescale reinforcement learning algorithm with asymptotic convergence guarantees. The learning algorithm in [18] serves as the basis for ours in the matrix-game setting. More broadly, no-regret learning algorithms, which have been extensively studied in online learning, can also serve as independent learning algorithms for matrix games [25]; these algorithms are convergent, rational [17], and implemented symmetrically by the players. However, regret bounds generally do not imply convergence bounds measured by the last iterate, as we establish in this work.

For finite-sample analysis in settings with payoff feedback, the closest work to ours is [26], which was concurrent with the conference version of this work. Specifically, [26] studied payoff-based learning algorithms based on online mirror descent, and established high-probability and anytime last-iterate convergence bounds, which imply a sample complexity of \(\tilde{\mathcal{O}}(\epsilon^{-8})\). Subsequently, more recent papers [27]–[29] have enhanced the last-iterate convergence of such mirror-descent-based algorithms, improving the sample complexity to \(\tilde{\mathcal{O}}(\epsilon^{-5})\) and \(\tilde{\mathcal{O}}(\epsilon^{-4})\), respectively. In comparison, we provide a finite-sample analysis for the natural best-response-based learning algorithm, which also serves as the basis for our learning algorithm for stochastic games studied later. Since their learning algorithms are based on mirror descent whereas ours are based on smoothed best responses, the exact sample complexity bounds are not directly comparable. For such a best-response-based learning algorithm, [30] established a sample complexity of \(\tilde{\mathcal{O}}(\epsilon^{-8-\nu})\) for some \(\nu>0\); in comparison, our bound is \(\tilde{\mathcal{O}}(\epsilon^{-8})\).

Zero-Sum Stochastic Games. For zero-sum stochastic games, establishing non-asymptotic, finite-sample analyses has received increasing attention recently, see e.g., [12], [13], [31]–[35]. Most of these studies, however, focused on the finite-horizon setting with online exploration, and conducted regret analysis, which differs from our last-iterate finite-sample analysis under the stochastic approximation framework, for the infinite-horizon discounted setting. Additionally, due to the finite-horizon nature of the setting, these algorithms are episodic and not best-response-type independent learning dynamics that are run for infinitely long, as a non-equilibrating adaptation process. Finite-sample complexity has also been established particularly for the policy-gradient methods [11], [36]–[38]. However, these methods are asymmetric among players, requiring them to update their policies on different timescales, which thus enforces explicit coordination across players.

When it comes to symmetric and independent/decentralized learning, [26], [39], [40] are the recent studies that provided non-asymptotic analyses. In comparison, the learning algorithms in [26], [39], [40] are variants of mirror-descent-based methods (e.g., optimistic gradient descent/ascent and extragradient descent/ascent), whereas our focus is on analyzing the natural learning dynamics based on smoothed-best-response. Additionally, the methods in [39], [40] require some coordination between players during the sampling process. Best-response-type independent learning for zero-sum stochastic games has also been explored recently in [41]–[44]. Yet, these works only established asymptotic convergence guarantees, which motivated the present work.

Organization. The rest of this paper is organized as follows. In Section 2, we focus on zero-sum matrix games and present payoff- and best-response-based reinforcement learning algorithms, together with their finite-sample guarantees. In Section 3, we extend the algorithmic idea to stochastic games and present the VI-SBR learning algorithm, together with its finite-sample guarantees. In Section 4, we present the proof of one of our main results, discuss the key technical challenges, and explain how we overcome them using a coupled Lyapunov-based approach. The detailed proofs of the other theoretical results are provided in the appendix. We conclude the paper in Section 5.

2 Two-Player Zero-Sum Matrix Games↩︎

For \(i\in \{1,2\}\), let \(\mathcal{A}^i\) be the finite action space of player \(i\), and denote \(m_i=|\mathcal{A}^i|\). Let \(R_i\in\mathbb{R}^{m_i\times m_{-i}}\) be the payoff matrix of player \(i\), where \(-i\) denotes the opponent of player \(i\). Note that \(R_1+R_2^\top =0\) in the zero-sum setting. Since there are finitely many actions, we assume without loss of generality that \(\max_{a^1,a^2}|R_1(a^1,a^2)|\leq 1\). Furthermore, we denote \(m=\max(m_1,m_2)\). The decision variables here are the policies \(\pi^i\in \Delta(\mathcal{A}^i)\), \(i\in \{1,2\}\), where \(\Delta(\mathcal{A}^i)\) denotes the probability simplex supported on \(\mathcal{A}^i\). Given a joint policy \((\pi^1,\pi^2)\), the expected reward received by player \(i\) is \(\mathbb{E}_{A^i\sim \pi^i(\cdot),A^{-i}\sim \pi^{-i}(\cdot)}[R_i(A^i,A^{-i})]=(\pi^i)^\top R_i\pi^{-i}\). Both players aim to maximize their rewards against their opponents.

Unlike the single-player setting, since the performance of player \(i\)’s policy depends on its opponent \(-i\)’s policy, there is, in general, no universal optimal policy. Instead, we use the Nash gap and also the regularized Nash gap as measurements of the performance of the learning algorithm, as formally defined below.

By definition, \(\text{NG}(\pi^1,\pi^2)=0\) if and only if \((\pi^1,\pi^2)\) is a Nash equilibrium of the matrix game, in which no player has an incentive to deviate from its current policy. Note that the Nash equilibrium need not be unique.

A joint policy \((\pi^1,\pi^2)\) satisfying \(\text{NG}_\tau(\pi^1,\pi^2)=0\) is called the Nash distribution [19] or the quantal response equilibrium [45], which, unlike the Nash equilibrium, is unique in a two-player zero-sum matrix game. Note that, as the parameter \(\tau\) approaches \(0\), the corresponding Nash distribution approximates a Nash equilibrium [46].

2.1 Algorithm↩︎

We start by presenting in Algorithm 1 the payoff-based reinforcement learning algorithm for zero-sum matrix games firstly proposed in [18]. Given \(\tau > 0\) and \(i \in \{1, 2\}\), we use \(\sigma_\tau : \mathbb{R}^{m_i} \to \mathbb{R}^{m_i}\) to represent the softmax function with temperature \(\tau\), i.e., \[\begin{align} [\sigma_\tau(q^i)](a^i)= \frac{\exp(q^i(a^i)/\tau)}{\sum_{\tilde{a}^i \in \mathcal{A}^i} \exp(q^i(\tilde{a}^i)/\tau)} \end{align}\] for all \(a^i \in \mathcal{A}^i\) and \(q^i \in \mathbb{R}^{m_i}\).

We next provide a detailed illustration of Algorithm 1, which also motivates our learning algorithm for stochastic games in Section 3. At a high level, Algorithm 1 can be viewed as a discrete and smoothed variant of the best-response dynamics, where each player constructs an approximation of the smoothed best response to its opponent’s policy using the \(q\)-function. The update equation for the \(q\)-function is in the spirit of the TD-learning method in reinforcement learning [47].

The Policy Update. To understand the update equation for the policies (cf. Algorithm 1, Line \(3\)), consider the discrete version of the smoothed best-response dynamics: \[\begin{align} \label{eq:FP} \pi_{k+1}^i=\pi_k^i+\beta_k(\sigma_\tau(R_i\pi_k^{-i})-\pi_k^i),\quad i\in \{1,2\}. \end{align}\tag{1}\] In (1 ), each player updates its policy \(\pi_k^i\) incrementally towards the smoothed best response to its opponent’s current policy. While (1 ) provably converges for two-player zero-sum matrix games [16], implementing it requires player \(i\) to compute \(\sigma_\tau(R_i\pi_k^{-i})\). Note that \(\sigma_\tau(R_i\pi_k^{-i})\) involves the knowledge of the opponent’s policy and the reward matrix, both of which cannot be accessed in decentralized and model-free reinforcement learning. This leads to the update equation for the \(q\)-function, which estimates the quantity \(R_i\pi_k^{-i}\) needed for implementing (1 ).

The \(q\)-Function Update. Suppose for now that we are given a stationary joint policy \((\pi^1,\pi^2)\). Fixing \(i\in \{1,2\}\), the problem of player \(i\) estimating \(R_i\pi^{-i}\) can be viewed as a policy evaluation problem in reinforcement learning, which can be solved by TD-learning [47]. Specifically, the two players repeatedly play the matrix game with the joint policy \((\pi^1,\pi^2)\) and produce a sequence of joint actions \(\{(A_k^1,A_k^2)\}\). Then, player \(i\) estimates \(R_i\pi^{-i}\) iteratively through the following algorithm: \[\begin{align} \label{eq:q95bandit} q_{k+1}^i(a^i)=q_k^i(a^i)+\alpha_k \mathbb{1}_{\{a^i=A_k^i\}}(R_i(A_k^i,A_k^{-i})-q_k^i(A_k^i)),\quad \forall\,a^i\in\mathcal{A}^i, \end{align}\tag{2}\] with an arbitrary initialization \(q_0^i\in\mathbb{R}^{m_i}\), where \(\alpha_k>0\) is the stepsize. To understand (2 ), suppose that \(q_k^i\) converges to some \(\Bar{q}^i\). Then, the update equation (2 ) should be “stationary” at the limit point \(\Bar{q}^i\) in the sense that \(\mathbb{E}_{A^i\sim \pi^i(\cdot),A^{-i}\sim \pi^{-i}(\cdot)}[\mathbb{1}_{\{a^i=A^i\}}(R_i(A^i,A^{-i})-\Bar{q}^i(A^i))]=0\) for all \(a^i\in\mathcal{A}^i\), which implies \(\Bar{q}^i=R_i\pi^{-i}\), as desired. Although we motivated (2 ) assuming the joint policy \((\pi^1,\pi^2)\) is stationary, the joint policy \((\pi_k^1,\pi_k^2)\) from (1 ) is time-varying. A natural approach to address this issue is to make sure that the policies evolve much more slowly compared to that of the \(q\)-functions, so that \(\pi_k\) is close to being stationary from the perspective of \(q_k^i\). This can be achieved by making \(\beta_k\ll \alpha_k\), where \(\beta_k\) is the stepsize for updating the policies and \(\alpha_k\) is the stepsize for updating the \(q\)-functions. When Algorithm 1 was first proposed [18], this was achieved by requiring \(\lim_{k\rightarrow\infty}\beta_k/\alpha_k=0\), making Algorithm 1 a two-timescale algorithm. In this work, we propose to update \(\pi_k^i\) and \(q_k^i\) on a single timescale but with only a multiplicative constant difference in their stepsizes, i.e., \(\beta_k=c_{\alpha,\beta}\alpha_k\) for some sufficiently small \(c_{\alpha,\beta}\in (0,1)\).

2.2 Finite-Sample Analysis Measured by the Regularized Nash Gap↩︎

To study Algorithm 1, we consider either constant stepsizes, i.e., \(\alpha_k\equiv \alpha\) and \(\beta_k\equiv \beta\), or harmonically diminishing stepsizes, i.e., \(\alpha_k=\alpha/(k+h)\) and \(\beta_k=\beta/(k+h)\), where \(h\geq 0\) is a tunable parameter. In either case, we ensure that \(\alpha_k,\beta_k\in (0,1)\) for all \(k\) and \(\beta=c_{\alpha,\beta}\alpha\) so that the algorithm operates on a single timescale. We begin by stating the requirements for choosing the stepsizes.

We next state the finite-sample bounds of Algorithm 1. The proof of the following theorem is presented in Appendix 6.

The convergence bounds in Theorem 1 are qualitatively consistent with the existing results on the finite-sample analysis of general stochastic approximation algorithms [48]–[53]. Specifically, when using constant stepsizes, the bound consists of a geometrically decaying term (also referred to as the optimization error) and a constant term (also referred to as the statistical error) that are proportional to the stepsizes. When using diminishing stepsizes with suitable hyperparameters, both errors can achieve an \(\mathcal{O}(1/K)\) rate of convergence.

Although Theorem 1 is stated in terms of the expectation of the regularized Nash gap, it implies the mean-square convergence of the joint policy \((\pi_K^1,\pi_K^2)\). To see this, note that the regularized Nash gap \(\text{NG}_\tau(\pi^1,\pi^2)\) is a \(\tau\)-strongly convex function (see Lemma 5 for a proof), the unique minimizer of which, denote by \((\pi_{*,\tau}^1,\pi_{*,\tau}^2)\), is the Nash distribution. Therefore, using the quadratic growth property of strongly convex functions, we have \(\text{NG}_\tau(\pi_k^1,\pi_k^2) \geq \frac{\tau}{2}(\|\pi_k^1-\pi_{*,\tau}^1\|_2^2+\|\pi_k^2-\pi_{*,\tau}^2\|_2^2)\). As a result, up to a constant multiplicative factor, the convergence bound for \(\mathbb{E}[\text{NG}_\tau(\pi_k^1,\pi_k^2)]\) directly implies a convergence bound of \(\mathbb{E}[\|\pi_k^1-\pi_{*,\tau}^1\|_2^2]+\mathbb{E}[\|\pi_k^2-\pi_{*,\tau}^2\|_2^2]\).

Based on Theorem 1, we next derive the sample complexity of Algorithm 1, measured by the regularized Nash gap, in the following corollary, whose proof is presented in Appendix 6.5.

To the best of our knowledge, Theorem 1 and Corollary 1 provide the first finite-sample analysis of Algorithm 1, first proposed in [18]. Importantly, using only realized payoff feedback, we establish a sample complexity of \(\mathcal{O}(\epsilon^{-1})\) for finding an \(\epsilon\)-Nash distribution.

2.3 Finite-Sample Analysis Measured by the Nash Gap↩︎

Although Theorem 1 shows that Algorithm 1 achieves a fast \(\mathcal{O}(1/K)\) rate of convergence measured by the regularized Nash gap, this result does not directly translate to a fast convergence measured by the Nash gap. To illustrate the difference, note that the following bound holds: \[\begin{align} \label{eq:NG95RNG95main} \text{NG}(\pi^1,\pi^2)\leq \text{NG}_\tau(\pi^1,\pi^2)+\underbrace{2\tau \log(m)}_{\text{Smoothing Bias}},\quad \forall\,(\pi^1,\pi^2), \end{align}\tag{3}\] where the second term can be viewed as the bias due to using the smoothed best response. We have conducted numerical experiments in Appendix 10 to demonstrate that such a smoothing bias is, in general, not removable. Combining (3 ) with Corollary 1, we have the following result, whose proof is presented in Appendix 6.6.

Importantly, the function \(f(\epsilon)\) is exponentially small in \(\epsilon\). Therefore, when using the Nash gap as the performance metric, Algorithm 1 does not admit a sample complexity polynomial in \(\epsilon^{-1}\). Tracing back to the finite-sample bound of Algorithm 1 in Theorem 1, the key reason is that the constant \(\ell_\tau\), which we establish in Lemma 10 as a lower bound for \(\min_{0\leq k\leq K}\min_{a^i}\pi_k^i(a^i)\), is exponentially small in \(\tau\). To address this issue, recall that the constant \(\ell_\tau\) captures the exploration capability of Algorithm 1; see Remark [remark:exp95bound]. We next introduce a more exploration-encouraging variant of Algorithm 1 that has a sample complexity polynomial in \(\epsilon^{-1}\) for achieving \(\mathbb{E}[\text{NG}(\pi_K^1,\pi_K^2)]\leq \epsilon\). Note that our goal is to make minimal modification of the algorithm, keeping the (natural) best-response-type update rules.

Given \(\Bar{\epsilon}\in [0,1]\) and \(\tau>0\), let \(\sigma_\tau^{\bar{\epsilon}}:\mathbb{R}^{m_i}\to \Delta(\mathcal{A}^i)\) be defined as \[\begin{align} \sigma_\tau^{\bar{\epsilon}}(q^i) = \Bar{\epsilon} \cdot \text{Unif}(\mathcal{A}^i) + (1-\Bar{\epsilon})\cdot \sigma_\tau(q^i),\quad \forall\,q^i\in\mathbb{R}^{m_i},i\in \{1,2\}, \end{align}\] where \(\text{Unif}(\mathcal{A}^i)\) denotes the uniform distribution supported on \(\mathcal{A}^i\). With this modification, we can explicitly control the lower bound of the components of \(\sigma_\tau^{\bar{\epsilon}}(\cdot)\) through the tunable parameter \(\Bar{\epsilon}\), thus preventing the components from being exponentially small in \(\tau\). By replacing \(\sigma_\tau(\cdot)\) with \(\sigma_\tau^{\bar{\epsilon}}(\cdot)\) in Algorithm 1, we have Algorithm 2 presented as follows.

We next present the last-iterate finite-sample analysis of Algorithm 2 measured by the Nash gap. For ease of presentation, we only consider the case with constant stepsizes, which can be directly extended to that with diminishing stepsizes. Let \[\begin{align} \ell_{\tau,\Bar{\epsilon}}:=\frac{\Bar{\epsilon}}{m}+\frac{(1-\Bar{\epsilon})}{(m-1)\exp(2/\tau)+1}, \end{align}\] which, analogous to \(\ell_\tau\) in Condition 1, is a uniform lower bound of the policies generated by Algorithm 2 (cf. Lemma 17).

The proof of Theorem 2 is presented in Appendix 7. In view of Theorem 2, we no longer have any problem-dependent constants that are exponential in \(\tau\). Based on Theorem 2, we next present the sample complexity of Algorithm 2, whose proof is presented in Appendix 7.5.

We briefly compare Corollary 3 with existing finite-sample results for payoff-based learning in zero-sum matrix games; see the related work section for a more detailed discussion. Existing results largely fall into two types: online-mirror-descent-based algorithms [26]–[29], which are different from the smoothed-best-response-based algorithm studied here, and smoothed-best-response-based algorithms [30], for which the best available sample complexity is \(\tilde{\mathcal{O}}(\epsilon^{-8-\nu})\) for some \(\nu>0\). In comparison, Corollary 3 establishes a sample complexity of \(\tilde{\mathcal{O}}(\epsilon^{-8})\).

3 Two-Player Zero-Sum Stochastic Games↩︎

Consider an infinite-horizon discounted two-player zero-sum stochastic game \(\mathcal{M}=(\mathcal{S},\mathcal{A}^1,\mathcal{A}^2,p,R_1,R_2,\gamma)\), where \(\mathcal{S}\) is a finite state space, and \(\mathcal{A}^1\) and \(\mathcal{A}^2\) are the finite action spaces of players \(1\) and \(2\), respectively. We denote \(n=|\mathcal{S}|\) and \(m=\max(m_1,m_2)\), where \(m_1=|\mathcal{A}^1|\) and \(m_2=|\mathcal{A}^2|\). The transition probabilities are specified by \(p\), where \(p(s'\mid s,a^1,a^2)\) is the probability of transitioning to state \(s'\) when player \(1\) takes action \(a^1\) and player \(2\) takes action \(a^2\) simultaneously at state \(s\). The reward functions are given by \(R_1:\mathcal{S}\times\mathcal{A}^1\times\mathcal{A}^2\to \mathbb{R}\) and \(R_2:\mathcal{S}\times\mathcal{A}^2\times \mathcal{A}^1\to \mathbb{R}\) for players \(1\) and \(2\), respectively, and \(\gamma\in (0,1)\) is the discount factor. The zero-sum condition requires that \(R_1(s,a^1,a^2)+R_2(s,a^2,a^1)=0\) for all \((s,a^1,a^2)\). As in the matrix-game setting, we assume without loss of generality that \(\max_{s,a^1,a^2}|R_1(s,a^1,a^2)|\leq 1\).

Given a joint (Markov stationary) policy \(\pi=(\pi^1,\pi^2)\), where \(\pi^i:\mathcal{S}\to\Delta(\mathcal{A}^i)\), \(i\in \{1,2\}\), we define the local \(q\)-function \(q_\pi^i\in\mathbb{R}^{nm_i}\) of player \(i\) as \[\begin{align} q_\pi^i(s,a^i)=\mathbb{E}_\pi\left[\sum_{k=0}^\infty\gamma^kR_i(S_k,A_k^i,A_k^{-i})\;\middle|\; S_0=s,A_0^i=a^i\right],\quad \forall\,(s,a^i), \end{align}\] where we use the notation \(\mathbb{E}_\pi[\,\cdot\,]\) to indicate that the actions are chosen according to the joint policy \(\pi\). Furthermore, we define the (state) value function \(v_\pi^i\in\mathbb{R}^{n}\) as \(v_\pi^i(s)=\mathbb{E}_{A^i\sim \pi^i(\cdot|s)}[q_\pi^i(s,A^i)]\) for all \(s\in\mathcal{S}\), and the utility function \(U^i(\pi^i,\pi^{-i})\in\mathbb{R}\) as \(U^i(\pi^i,\pi^{-i})=\mathbb{E}_{S\sim p_o}[v^i_\pi(S)]\), where \(p_o\in\Delta(\mathcal{S})\) is a fixed initial distribution on the states.

The Nash gap in the case of stochastic games is defined in the following.

A joint policy \(\pi=(\pi^1,\pi^2)\) satisfying \(\text{NG}(\pi^1,\pi^2)=0\) is then called a Nash equilibrium⁶.

Additional Notation. Since the stochastic game we study has a finite state-action space, the policy, local \(q\)-function, and value function can all be viewed as vectors. As we will frequently work with vectors in \(\mathbb{R}^{nm_i}\), \(\mathbb{R}^{nm_{-i}}\), and \(\mathbb{R}^{nm_im_{-i}}\), where \(i\in \{1,2\}\), to simplify notation, for any \(x\in\mathbb{R}^{nm_im_{-i}}\) (e.g., \(x\) may represent a joint policy), we use \(x(s)\) to denote the \(m_i\times m_{-i}\) matrix whose \((a^i,a^{-i})\)-th entry is \(x(s,a^i,a^{-i})\). For any \(y\in\mathbb{R}^{nm_i}\) (e.g., \(y\) may represent the local \(q\)-function or policy of player \(i\)), we use \(y(s)\) to denote the \(m_i\)-dimensional vector whose \(a^i\)-th entry is \(y(s,a^i)\).

3.1 Value Iteration with Smoothed Best-Response Learning↩︎

Our learning algorithm for stochastic games (cf. Algorithm 3) builds on the matrix-game algorithm studied in Section 2.1, with the additional incorporation of minimax value iteration, a well-known approach for solving two-player zero-sum stochastic games [54].

To motivate the learning algorithm, we first introduce minimax value iteration. For \(i\in \{1,2\}\), let \(\mathcal{T}^i:\mathbb{R}^{n}\to\mathbb{R}^{nm_im_{-i}}\) be an operator defined as \[\begin{align} [\mathcal{T}^i(v)](s,a^i,a^{-i})= R_i(s,a^i,a^{-i})+\gamma\mathbb{E}\left[ v(S_1)\mid S_0=s,A_0^i=a^i,A_0^{-i}=a^{-i}\right] \end{align}\] for all \((s,a^i,a^{-i})\) and \(v\in\mathbb{R}^{n}\). Given an \(m_i\times m_{-i}\) matrix \(X_i\), we define \(\textit{val}^i:\mathbb{R}^{m_i\times m_{-i}}\to\mathbb{R}\) as \[\begin{align} \textit{val}^i(X_i)=\max_{\mu^i\in\Delta(\mathcal{A}^i)}\min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})}\{(\mu^i)^\top X_i\mu^{-i}\} =\min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})}\max_{\mu^i\in\Delta(\mathcal{A}^i)}\{(\mu^i)^\top X_i\mu^{-i}\}. \end{align}\] Then, the minimax Bellman operator \(\mathcal{B}^i:\mathbb{R}^{n}\to\mathbb{R}^{n}\) is defined as \[\begin{align} [\mathcal{B}^i(v)](s)=\textit{val}^i([\mathcal{T}^i(v)](s)),\quad \forall\,s\in\mathcal{S}, \end{align}\] where \([\mathcal{T}^i(v)](s)\) is an \(m_i\times m_{-i}\) matrix according to our notation. It is known that the operator \(\mathcal{B}^i(\cdot)\) is a contraction mapping with respect to the \(\ell_\infty\)-norm [54], hence it admits a unique fixed point, which we denote by \(v_*^i\).

A common approach for computing equilibria in zero-sum stochastic games is to first apply minimax value iteration, \(v^i_{t+1}=\mathcal{B}^i(v_t^i)\), to obtain \(v_*^i\) [55], and then, for each state \(s\in\mathcal{S}\), solve the matrix game \(\max_{\mu^i\in\Delta(\mathcal{A}^i)}\min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})}(\mu^i)^\top\mathcal{T}^i(v_*^i)(s)\mu^{-i}\). However, implementing this procedure requires complete knowledge of the transition probabilities. Moreover, since its output is independent of the opponent’s actual policy and instead assumes that the opponent always best responds, this procedure is better viewed as an equilibrium computation algorithm rather than a rational one in the sense of [17].

To make minimax value iteration model-free and rational, let us first rewrite it as \[\tag{4} \begin{align} \hat{v}(s)=\,&\max_{\mu^i\in\Delta(\mathcal{A}^i)}\min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})}(\mu^i)^\top \mathcal{T}^i(v_t^i)(s)\mu^{-i},\quad \forall\,s\in\mathcal{S}.\tag{5}\\ v_{t+1}^i=\,&\hat{v}.\tag{6} \end{align}\] In view of 4 , minimax value iteration may be understood as a two-step procedure. For each state \(s\), one first solves a zero-sum matrix game with payoff matrix \([\mathcal{T}^i(v_t^i)](s)\), and then updates the value of the game to \(v_{t+1}^i(s)\). In light of Algorithm 1, we already know how to perform payoff-based learning in matrix games. Thus, what remains to do is to combine Algorithm 1 with (4 ). This leads to Algorithm 3.

For each state \(s\), the inner loop of Algorithm 3 is designed to learn the matrix game with payoff matrices \(\mathcal{T}^1(v_t^1)(s)\) and \(\mathcal{T}^2(v_t^2)(s)\) for each state \(s\in\mathcal{S}\). However, in general, since \(v_t^1\) and \(v_t^2\) are independently maintained by players \(1\) and \(2\), we do not necessarily have \(\mathcal{T}^1(v_t^1)(s,a^1,a^2)+\mathcal{T}^2(v_t^2)(s,a^2,a^1)=0\) for all \((a^1,a^2)\). As a result, the auxiliary matrix game (with payoff matrices \(\mathcal{T}^1(v_t^1)(s)\) and \(\mathcal{T}^2(v_t^2)(s)\)) at state \(s\)) is not necessarily a zero-sum matrix game, which presents a major challenge in the finite-sample analysis. Such a breaking of the zero-sum structure was also observed as one key challange in the analyses of independent learning dynamics in [41], [42]. We will elaborate on this challenge and our technique to overcome it in more detail in Section 4.

The outer loop of Algorithm 3 is an approximation of the minimax value iteration. To see this, note that, ideally, we would synchronize \(v_{t+1}^i(s)\) with \(\pi_{t,K}^i(s)^\top \mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s)\), which is an approximation of \([\mathcal{B}^i(v)](s)=\textit{val}^i([\mathcal{T}^i(v_t^i)](s))\) by design of our inner loop. However, player \(i\) has no access to \(\pi_{t,K}^{-i}\) in our decentralized learning setting. Fortunately, the local \(q\)-function \(q_{t,K}^i\) is precisely constructed to estimate \(\mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s)\), as illustrated in Section 2.1, which leads to the outer loop of Algorithm 3. In Algorithm 3, Line \(9\), we set \(S_0=S_K\) to ensure that Algorithm 3 is driven by a single trajectory of Markovian samples.

3.2 Finite-Sample Analysis↩︎

We now state our main results for two-player zero-sum stochastic games, which is based on the following assumption.

Assumption 1 is imposed to ensure sufficient exploration during learning. Such exploration assumptions are standard in the literature, even for establishing the asymptotic convergence of single-agent algorithms [50], [56]–[58]. We note that the aperiodicity assumption could be relaxable using recent approaches based on Poisson-equation decompositions of Markovian noise [59], [60]. We leave this relaxation as a future direction. Importantly, although Assumption 1 concerns only deterministic policies, we show in the proof that it guarantees a uniform exploration property for all policies generated by Algorithm 3; see Lemma 7.

For Algorithm 3, we consider either constant stepsizes, i.e., \(\alpha_k\equiv \alpha\) and \(\beta_k\equiv \beta\), or harmonically diminishing stepsizes, i.e., \(\alpha_k=\alpha/(k+h)\) and \(\beta_k=\beta/(k+h)\), where \(h\geq 0\). In both cases, we ensure \(\alpha_k,\beta_k\in (0,1)\) and \(\beta_k=c_{\alpha,\beta}\alpha_k\) for all \(k\), where \(c_{\alpha,\beta}\in (0,1)\) is the stepsize ratio. In the stochastic-game setting, we redefine \[\begin{align} \label{definition:ell95tau} \ell_\tau=\frac{1}{1+(m-1)\exp(2/[(1-\gamma)\tau])}, \end{align}\tag{7}\] which, analogously to the matrix-game setting, is a uniform lower bound on the entries of the policies generated by Algorithm 3 (cf. Lemma 2). We next state our requirement for choosing the stepsizes.

We next state the finite-sample bound of Algorithm 3. For simplicity of presentation, we use \(a\lesssim b\) to denote that there exists an absolute constant \(c>0\) such that \(a\leq bc\).

The proof of Theorem 3 is presented in Section 4. We next discuss the implications of the theorem. In Theorem 3 (1), the bound consists of a value-iteration error term \(\mathcal{E}_1\), an optimization error term \(\mathcal{E}_2\), a statistical error term \(\mathcal{E}_3\), and a smoothing-bias term \(\mathcal{E}_4\). The term \(\mathcal{E}_1\) would be the only error term if exact minimax value iteration could be performed to solve the game. Since minimax value iteration converges geometrically, \(\mathcal{E}_1\) also decays at a geometric rate. The optimization error term \(\mathcal{E}_2\) and the statistical error term \(\mathcal{E}_3\) arise from learning the inner-loop auxiliary matrix games, while the smoothing-bias term \(\mathcal{E}_4\) is due to using smoothed best responses instead of exact best responses. These three terms are the stochastic-game counterparts of the error terms that appeared in the matrix-game analysis. In Theorem 3 (2), due to the use of diminishing stepsizes, both the optimization error and the statistical error converge at a rate of \(\tilde{\mathcal{O}}(K^{-1/2})\).

Although the transient terms in Theorem 3 have desirable convergence rates, including geometric decay in \(T\) and \(\tilde{\mathcal{O}}(K^{-1/2})\) decay in \(K\), the stepsize ratio \(c_{\alpha,\beta}\), which is exponentially small in \(\tau^{-1}\), appears as \(c_{\alpha,\beta}^{-1}\) in the bound. Therefore, due to the smoothing bias, achieving an \(\epsilon\)-NE with \(\mathbb{E}[\text{NG}(\pi_{T,K}^1,\pi_{T,K}^2)]\leq \epsilon\) may require an overall sample complexity that has exponential dependence on \(\epsilon^{-1}\). This phenomenon is analogous to the zero-sum matrix-game setting. As explained in detail in Section 2, it arises from the limited exploration induced by (the natural) exponential softmax policies.

To achieve an overall sample complexity polynomial in \(\epsilon^{-1}\), we next modify Algorithm 3 to encourage exploration, leading to Algorithm 4. Recall that our goal is to keep the (natural) best-response-type update rules, with minimal modification to Algorithm 3. Specifically, recall that given \(\bar{\epsilon}\in (0,1)\) and \(\tau>0\), the operator \(\sigma_\tau^{\bar{\epsilon}}:\mathbb{R}^d\to \mathbb{R}^d\), where \(d\) can be either \(m_1\) or \(m_2\), is defined as \[\begin{align} \sigma_\tau^{\bar{\epsilon}}(x) = \bar{\epsilon}\cdot \text{Unif}_d + (1-\bar{\epsilon})\cdot \sigma_\tau(x),\quad \forall\,x\in\mathbb{R}^d, \end{align}\] where \(\text{Unif}_d\) denotes the \(d\)-dimensional uniform distribution and \(\sigma_\tau(\cdot)\) is the softmax operator with temperature \(\tau\). Note that the only difference between Algorithm 3 and Algorithm 4 is that, in Algorithm 4, Line \(4\), we used \(\sigma_\tau^{\bar{\epsilon}}(q_{t,k}^i(s))\) instead of \(\sigma_\tau(q_{t,k}^i(s))\).

Next, we present the finite-sample analysis of Algorithm 4; see Appendix 9 for the proof. Similarly, we only present the result for constant stepsizes, as the result for diminishing stepsizes follows by a straightforward extension.

To the best of our knowledge, Theorem 4 provides the first finite-sample analysis of a decentralized best-response-based learning algorithm for zero-sum stochastic games with sample complexity polynomial in \(\epsilon^{-1}\). In the concurrent work [26], the authors established an \(\mathcal{O}(\epsilon^{-9-\nu})\) (for some \(\nu>0\)) sample complexity for decentralized learning in zero-sum stochastic games. Although our sample complexity is \(\mathcal{O}(\epsilon^{-8})\), these two results are not directly comparable. Their algorithm is based on online mirror descent, whereas ours is based on smoothed best-response dynamics. Moreover, our bound is in expectation and uses stepsizes tuned to the target accuracy level, while their bound holds with high probability and provides anytime last-iterate convergence guarantees.

Finally, we consider the case where the opponent of player \(i\) plays a stationary policy, and provide a finite-sample bound for player \(i\) to find a best response. This is pertinent to the desired feature of rationality [17] for decentralized learning dynamics. The proof of the following corollary is presented in Appendix 9.6.

The rationality property follows from the on-policy nature of the learning algorithm. When the opponent’s policy is stationary, player \(i\) faces an induced single-agent Markov decision process. Notably, the behavior policy used to generate samples is the same policy that is being updated toward a smoothed best response. This contrasts with off-policy procedures, where the behavior policy may be unrelated to the policy being improved. Thus, the same mechanism that makes the learning algorithm independent and symmetric also yields best-response learning against a stationary opponent.

4 Proof of Theorem 3: A Coupled Lyapunov-Based Approach↩︎

In this section, we use Theorem 3 as a representative example to present the key challenges and highlight the main technical novelties in our proof. The main difficulty is that VI-SBR maintains multiple sets of stochastic iterates, including the policies, the local \(q\)-functions, and the value functions, which are updated in a coupled manner. Thus, no component can be analyzed in isolation: the policy updates depend on the accuracy of the \(q\)-functions, the \(q\)-function updates are driven by time-varying policies and value functions, and the value-function updates depend on the outputs of the inner-loop.

Several additional and unique challenges arise in the stochastic-game setting: (1) the independently maintained value functions induce auxiliary matrix games that are not exactly zero-sum during learning; (2) the data are collected along a single trajectory under time-varying policies, leading to time-inhomogeneous Markovian noises in the stochastic iterates. To address these challenges, we develop a coupled Lyapunov-based approach: we construct Lyapunov functions for the coupled iterates, establish their drift inequalities, and solve the resulting system jointly to obtain the finite-sample bounds. This framework may be useful more broadly for analyzing stochastic iterative algorithms with multiple coupled sets of iterates.

4.1 Introducing the Lyapunov Functions↩︎

We start by introducing the Lyapunov functions we use to analyze Algorithm 3. Specifically, for any \(t,k\geq 0\) and \(i\in \{1,2\}\), let \(\Bar{q}_{t,k}^i\in\mathbb{R}^{nm_i}\) be defined as \(\Bar{q}_{t,k}^i(s)=\mathcal{T}^i(v_t^i)(s)\pi_{t,k}^{-i}(s)\) for all \(s\in\mathcal{S}\), and let \[\begin{align} \mathcal{L}_v(t)=\,&\sum_{i=1,2}\|v_t^i-v_*^i\|_\infty,\quad \mathcal{L}_{\text{sum}}(t)=\|v_t^1+v_t^2\|_\infty,\quad \mathcal{L}_q(t,k)=\sum_{i=1,2}\|q_{t,k}^i-\Bar{q}_{t,k}^i\|_2^2,\\ \mathcal{L}_\pi(t,k)=\,&\max_{s\in\mathcal{S}} \sum_{i=1,2}\max_{\mu^i\in\Delta(\mathcal{A}^i)}\left\{(\mu^i-\pi_{t,k}^i(s))^\top \mathcal{T}^i(v_t^i)(s)\pi_{t,k}^{-i}(s)+\tau \nu(\mu^i)-\tau\nu(\pi_{t,k}^i(s))\right\}, \end{align}\] where \(v_*^i\) is the unique fixed point of the minimax Bellman operator \(\mathcal{B}^i(\cdot)\). We will provide more detailed explanations of the Lyapunov function construction as we go over the proofs below.

The first step is to bound the Nash gap in terms of the Lyapunov functions introduced above. This is formalized in the following lemma, whose proof is presented in Appendix 8.3.

The remainder of the proof is devoted to bounding the Lyapunov functions. Before proceeding, we present an important boundedness property of the iterates generated by Algorithm 3.

The proof of Lemma 2 is based on a nested induction argument, and is presented in Appendix 8.2. This result will be used frequently in our analysis.

4.2 Analysis of the Outer Loop: the \(v\)-Function Update↩︎

We first consider the Lyapunov functions \(\mathcal{L}_v(T)\) and \(\mathcal{L}_{\text{sum}}(T)\), which are defined in terms of the value functions updated in the outer loop of Algorithm 3.

Recall from Section 3.1 that the outer loop of Algorithm 3 is designed as an approximation of the minimax value iteration \(v_{t+1}^i=\mathcal{B}^i(v_t^i)\), where \(i\in \{1,2\}\). Since it is known that the minimax Bellman operator \(\mathcal{B}^i(\cdot)\) is a contraction mapping with respect to the \(\ell_\infty\)-norm [54], we use \(\mathcal{L}_v(t)=\sum_{i=1,2}\|v_t^i-v_*^i\|_\infty\) as the Lyapunov function to study the evolution of the value functions \((v_t^1,v_t^2)\). In the following lemma, we present the Lyapunov drift inequality for \(\mathcal{L}_v(t)\):

The proof of Lemma 3 is presented in Appendix 8.4.1. Since \(\gamma\in (0,1)\), the inequality is contractive; equivalently, \(\mathcal{L}_v(t)\) has a negative drift, which is consistent with the geometric convergence of minimax value iteration. The additive error terms on the right-hand side of ?? involve other Lyapunov functions, which is why we refer to ?? as a coupled Lyapunov drift inequality.

Moving to the Lyapunov function \(\mathcal{L}_{\text{sum}}(t)\), recall from Section 3.1 that, due to decentralized learning, we do not necessarily have \(v_t^1+v_t^2=0\). As a result, the auxiliary matrix game at state \(s\) with payoff matrices \(\mathcal{T}^1(v_t^1)(s)\) and \(\mathcal{T}^2(v_t^2)(s)\) that the inner loop of Algorithm 3 is designed to solve is not necessarily a zero-sum matrix game, which presents a major challenge in the analysis. The error induced from such a non-zero-sum structure appears in existing work [41], [42], and was handled by designing a novel truncated Lyapunov function. However, the truncated Lyapunov function was sufficient to establish the asymptotic convergence, but did not provide the explicit rate at which the induced error goes to zero. To enable finite-sample analysis, we introduce \(\mathcal{L}_{\text{sum}}(t)=\|v_t^1+v_t^2\|_\infty\) as a Lyapunov function in our coupled Lyapunov framework, which is customized to capture the behavior of the induced error from the non-zero-sum structure of the inner-loop matrix game.

The next lemma presents the Lyapunov drift inequality for \(\mathcal{L}_{\text{sum}}(t)\). Its proof is presented in Appendix 8.4.2.

Note that (?? ) is also a coupled Lyapunov drift inequality as it consists of a negative drift and an additive error term defined in terms of other Lyapunov functions.

It now remains to bound \(\mathcal{L}_q(t,k)\) and \(\mathcal{L}_\pi(t,k)\), which are defined in terms of the \(q\)-functions and the policies updated in the inner loop of Algorithm 3.

4.3 Analysis of the Inner Loop: the Policy Update↩︎

As illustrated in Section 3.1, for each state \(s\), the policy update can be viewed as a discrete-time stochastic variant of the smoothed best-response dynamics [19]; see 1 . For smoothed best-response dynamics in zero-sum matrix games, formulated as an ODE, the regularized Nash gap has been shown to be a valid Lyapunov function [15]. Motivated by this observation, given the pair of value functions \(v_t=(v_t^1,v_t^2)\) from the outer loop of Algorithm 3, we would like to construct a Lyapunov function for the inner-loop policy iterates by considering the induced matrix game at each state \(s\). Specifically, since the inner loop of Algorithm 3 is designed to solve the matrix game with payoff matrices \(\mathcal{T}^1(v_t^1)(s)\) and \(\mathcal{T}^2(v_t^2)(s)\), a natural candidate is \[\begin{align} \mathcal{L}_\pi(t,k) = \max_{s\in\mathcal{S}} \sum_{i=1,2} \max_{\mu^i\in\Delta(\mathcal{A}^i)} \Big\{ (\mu^i-\pi_{t,k}^i(s))^\top \mathcal{T}^i(v_t^i)(s)\pi_{t,k}^{-i}(s) +\tau \nu(\mu^i)-\tau\nu(\pi_{t,k}^i(s)) \Big\}. \end{align}\] Here, the operator \(\max_{s\in\mathcal{S}}(\cdot)\) accounts for the fact that Algorithm 3 induces a separate matrix game at each state.

While this construction of Lyapunov function is natural, the results in [15] are not directly applicable for establishing a negative drift in our setting for three reasons: (1) our learning algorithm is discrete-time, (2) the induced inner-loop matrix game need not be zero-sum, i.e., \([\mathcal{T}^1(v_t^1)](s)+[\mathcal{T}^2(v_t^2)](s)\neq 0\), and (3) the payoff vectors, i.e., \([\mathcal{T}^1(v_t^1)](s)\pi_{t,k}^2(s)\) and \([\mathcal{T}^2(v_t^2)](s)\pi_{t,k}^1(s)\)), are estimated through the local \(q\)-functions and are thus not exact. Therefore, to facilitate our analysis, we consider the function \[\begin{align} \label{eq:RNG95X} V_X(\mu^1,\mu^2) = \sum_{i=1,2} \max_{\hat{\mu}^i\in\Delta(\mathcal{A}^i)} \left\{ (\hat{\mu}^i-\mu^i)^\top X_i\mu^{-i} + \tau \nu(\hat{\mu}^i) - \tau\nu(\mu^i) \right\}, \end{align}\tag{8}\] defined for all \((\mu^1,\mu^2)\in\Delta(\mathcal{A}^1)\times\Delta(\mathcal{A}^2)\), where \(X_i\), \(i\in \{1,2\}\), is an \(m_i\times m_{-i}\) matrix. Note that we do not assume \(X_1+X_2^\top =0\). We establish a sequence of properties of \(V_X(\cdot,\cdot)\) to overcome the three challenges described above.

Let \(\Pi_\tau=\{(\mu^1,\mu^2)\mid \min_{a^1}\mu^1(a^1)\geq \ell_\tau,\min_{a^2}\mu^2(a^2)\geq \ell_\tau\}\). Note that Lemma 2 implies that \((\pi_k^1(s),\pi_k^2(s))\in\Pi_\tau\) for all \(k\geq 0\) and \(s\in\mathcal{S}\). The proof of the following lemma is presented in Appendix 8.5.1.

The four properties in Lemma 5 play distinct roles in the Lyapunov drift analysis. Properties (1) and (2) provide the strong convexity and smoothness needed to control the discretization error when passing from the continuous-time smoothed best-response dynamics to the discrete stochastic updates in our learning algorithm. Property (3) establishes a negative drift for the regularized Nash-gap Lyapunov function, up to an additive error proportional to \(\|X_1+X_2^\top\|_2^2\); this term handles the deviation of the induced auxiliary game from being exactly zero-sum. Property (4) controls the error caused by using the estimated local \(q\)-functions in the policy update, rather than the exact payoff vectors. Together, these properties allow us to derive a Lyapunov drift inequality that simultaneously accounts for discretization, the non-zero-sum perturbation of the auxiliary games, and the local \(q\)-function evaluation error.

With the properties of \(V_X(\cdot,\cdot)\) in hand, we establish the Lyapunov drift inequality for \(\mathcal{L}_\pi(t,k)\) in the following lemma, whose proof is deferred to Appendix 8.5.2. For notational convenience, let \(\mathcal{F}_t\) denote the history of Algorithm 3 immediately before the \(t\)-th outer-loop iteration, and write \(\mathbb{E}_t[\cdot]\) for \(\mathbb{E}[\cdot \mid \mathcal{F}_t]\).

To interpret (?? ), suppose that we were considering the continuous-time smoothed best-response dynamics [15]. Then, the Additive Errors would disappear in the sense that the time-derivative of the Lyapunov function along the trajectory of the ODE is strictly negative. Thus, the three terms in the Additive Errors on the right-hand side of (?? ) can be interpreted, respectively, as (1) the discretization error in the update equation, (2) the stochastic error in the \(q\)-function estimate, and (3) the error due to the non-zero-sum structure of the inner-loop auxiliary matrix game.

4.4 Analysis of the Inner Loop: the \(q\)-Function Update↩︎

Our next focus is the \(q\)-function, whose update equation is in the same spirit as TD-learning in reinforcement learning [58], [61]. Inspired by the existing literature studying TD-learning [50], [52], [58], [61], we will reformulate the update equation of the \(q\)-function as a stochastic approximation algorithm for estimating the solution of a time-varying target equation. For ease of presentation, since we are focusing on the inner loop, we will omit the iteration index \(t\) for the outer loop.

For \(i\in \{1,2\}\), fixing a value function \(v^i\in\mathbb{R}^{n}\) from the outer loop, let \(F^i:\mathbb{R}^{n m_i}\times \mathcal{S}\times \mathcal{A}^i\times \mathcal{A}^{-i}\times \mathcal{S}\to \mathbb{R}^{n m_i}\) be defined as \[\begin{align} [F^i(q^i,s_0,a_0^i,a_0^{-i},s_1)](s,a^i) =\mathbb{1}_{\{(s,a^i)=(s_0,a_0^i)\}}\left(R_i(s_0,a_0^i,a_0^{-i})+\gamma v^i(s_1)-q^i(s_0,a_0^i)\right) \end{align}\] for all \((q^i,s_0,a_0^i,a_0^{-i},s_1)\) and \((s,a^i)\). Then Algorithm 3, Line \(6\), can be compactly written as \[\begin{align} \label{sa:reformulation95sketch} q_{k+1}^i=q_k^i+\alpha_k F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1}). \end{align}\tag{9}\] For any \(k\geq 0\), let \(\mu_k\in\Delta(\mathcal{S})\) denote the stationary distribution of the Markov chain \(\{S_n\}_{n\geq 0}\) induced by the joint policy \(\pi_k=(\pi_k^1,\pi_k^2)\), provided it exists and is unique. We will verify this existence and uniqueness shortly. Let \(\Bar{F}_k^i:\mathbb{R}^{n m_i}\to \mathbb{R}^{n m_i}\) be defined as \[\begin{align} \Bar{F}_k^i(q^i) =\mathbb{E}_{S_0\sim \mu_k(\cdot),A_0^i\sim \pi_k^i(\cdot|S_0), A_0^{-i}\sim \pi_k^{-i}(\cdot|S_0), S_1\sim p(\cdot|S_0,A_0^i,A_0^{-i})}\left[F^i(q^i,S_0,A_0^i,A_0^{-i},S_1)\right] \end{align}\] for all \(q^i\in\mathbb{R}^{nm_i}\). Then, the update equation (9 ) can be viewed as a stochastic approximation algorithm for solving the time-varying equation \(\Bar{F}_k^i(q^i)=0\) with time-inhomogeneous Markovian noise \(\{(S_k,A_k^i,A_k^{-i},S_{k+1})\}\). Note that the reason for the Markov chain \(\{(S_k,A_k^i,A_k^{-i},S_{k+1})\}\) being time-inhomogeneous is that our learning algorithm uses time-varying policies \(\{\pi_k\}\).

Before analyzing the update in 9 , we first need to show that, under Assumption 1, for each \(k\), the stationary distribution \(\mu_k\) of the Markov chain \(\{S_n\}_{n\geq 0}\) induced by \((\pi_k^1,\pi_k^2)\) exists and is unique. In addition, to guarantee exploration, we need \(\min_{1\leq k\leq K}\min_s\mu_k(s)>0\). To this end, we present the following lemma, which establishes uniform mixing and uniform exploration properties for all policies encountered by the learning algorithm. Its proof is presented in Appendix 8.5.4.

In Lemma 7, Part (1) ensures that every policy encountered by the algorithm induces a well-defined stationary distribution. Part (2) strengthens this to a uniform mixing bound over the policy class \(\Pi\), which allows us to control the Markovian sampling bias uniformly along the algorithm trajectory. Part (3) provides a Lipschitz-type sensitivity bound for the stationary distribution with respect to the changes in policy, which is used to handle the time-inhomogeneity caused by time-varying policies. Finally, Part (4) guarantees a uniform positive lower bound on all state stationary probabilities, ensuring that every state is visited with nonvanishing frequency under all policies encountered by the learning algorithm.

Now, we are ready to study the stochastic approximation algorithm 9 . We start by presenting a sequence of properties of the operators \(F^i(\cdot)\) and \(\Bar{F}_k^i(\cdot)\) in the following lemma, whose proof is presented in Appendix 8.5.3.

Among the properties established in the previous lemma, Part (4) is particularly important. It justifies the use of the standard quadratic Lyapunov function \[\begin{align} \mathcal{L}_q(k) = \sum_{i=1,2}\|q_{k}^i-\bar{q}_k^i\|_2^2 \end{align}\] to study 9 , where we recall that the outer-loop index \(t\) is omitted.

Using \(\mathcal{L}_q(k)\) as a Lyapunov function, we obtain a negative drift through a binomial decomposition and Lemma 8 (4). The key challenge is to handle the time-inhomogeneous Markovian noise \(\{(S_k,A_k^i,A_k^{-i},S_{k+1})\}\). To overcome this challenge, building on existing results [50], [52], [56], [57] and Lemma 7, we develop an argument that combines mixing-time analysis with a sensitivity analysis of the stationary distribution with respect to the learning policies. This leads to the following overall Lyapunov drift inequality for \(\mathcal{L}_q(k)\).

The proof of Lemma 9 is presented in Appendix 8.5.5.

4.5 Solving Coupled Lyapunov Drift Inequalities↩︎

Until this point, we have established the Lyapunov drift inequalities for the individual \(v\)-functions, the sum of the \(v\)-functions, the policies, and the \(q\)-functions in (?? ), (?? ), (?? ), and (?? ), respectively. They are restated as follows: \[\begin{align} \mathcal{L}_{v}(t+1)\leq \,&\gamma\mathcal{L}_{v}(t)+4\mathcal{L}_{\text{sum}}(t)+4\mathcal{L}_{\pi}(t,K)+2\mathcal{L}_q^{1/2}(t,K)+6\tau\log(m),\tag{10}\\ \mathcal{L}_{\text{sum}}(t+1)\leq\,& \gamma \mathcal{L}_{\text{sum}}(t)+2\mathcal{L}_q^{1/2}(t,K),\tag{11}\\ \mathbb{E}_t[\mathcal{L}_{\pi}(t,k+1)]\leq\,& (1-3\beta_k/4)\mathbb{E}_t[\mathcal{L}_{\pi}(t,k)]+C_1(\beta_k^2+\beta_k\mathbb{E}_t[\mathcal{L}_{q}(t,k)]+\beta_k \mathcal{L}_{\text{sum}}^2(t)),\tag{12}\\ \mathbb{E}_t[\mathcal{L}_{q}(t,k+1)]\leq\,& (1-\mu_{\min}\ell_\tau\alpha_k)\mathbb{E}_t[\mathcal{L}_{q}(t,k)]+\beta_k\mathbb{E}_t[\mathcal{L}_{\pi}(t,k)]/4+C_2z_k^2\alpha_k^2,\tag{13} \end{align}\] where \(C_1,C_2\) are problem-dependent constants introduced for the simplicity of notation. Moreover, to obtain (13 ) from (?? ), we used the fact that \(\alpha_{k-z_k,k-1}=\mathcal{O}(z_k\alpha_k)\) [51].

To decouple the highly coupled Lyapunov inequalities, our high-level ideas are: (1) using the Lyapunov drift inequalities in a combined way instead of in a separate manner, and (2) a novel bootstrapping procedure where we first derive a crude bound on \(\mathbb{E}[\mathcal{L}_{q}(t,K)]\) and then substitute the crude bound back into the Lyapunov drift inequalities to derive a tighter bound. We next elaborate on our approach with more details.

For ease of presentation, for a scalar-valued quantity \(W\) that is a function of \(k\) and/or \(t\), we say \(W=o_k(1)\) if \(\lim_{k\rightarrow\infty} W=0\) and \(W=o_t(1)\) if \(\lim_{t\rightarrow\infty} W=0\). The explicit convergence rates of the \(o_k(1)\) term and the \(o_t(1)\) term will be revealed in the complete proof in Appendix 8.6, but are not important for the illustration here.

Step 1. Adding up (12 ) and (13 ) and then repeatedly using the result, we obtain: \[\begin{align} \label{eq:sketch5} \mathbb{E}_t[\mathcal{L}_{\pi}(t,k)]\leq \mathbb{E}_t[\mathcal{L}_{\pi}(t,k)+\mathcal{L}_{q}(t,k)]= o_k(1)+\mathcal{O}(1)\mathcal{L}_{\text{sum}}^2(t),\quad \forall\,t,k. \end{align}\tag{14}\]

Step 2. Substituting the bound for \(\mathbb{E}_t[\mathcal{L}_{\pi}(t,k)]\) in (14 ) back into (13 ) and repeatedly using the resulting inequality, we obtain \(\mathbb{E}_t[\mathcal{L}_{q}(t,K)]=o_K(1)+\mathcal{O}(c_{\alpha,\beta})\mathcal{L}_{\text{sum}}^2(t)\) for all \(t\), which in turn implies (by first using Jensen’s inequality and then taking the total expectation) that: \[\begin{align} \label{eq:sketch6} \mathbb{E}[\mathcal{L}_{q}^{1/2}(t,K)]=o_K(1)+\mathcal{O}(c^{1/2}_{\alpha,\beta})\mathbb{E}[\mathcal{L}_{\text{sum}}(t)],\quad \forall\,t, \end{align}\tag{15}\] where we recall that \(c_{\alpha,\beta}=\beta_k/\alpha_k\) is the stepsize ratio. The fact that we are able to get a factor of \(\mathcal{O}(c^{1/2}_{\alpha,\beta})\) in front of \(\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]\) is crucial for the decoupling procedure in the next step.

Step 3. Taking total expectation on both sides of (11 ) and then using the upper bound of \(\mathbb{E}[\mathcal{L}^{1/2}_{q}(t,K)]\) we obtained in (15 ), we further get \(\mathbb{E}[\mathcal{L}_{\text{sum}}(t+1)]\leq (\gamma +\mathcal{O}(c^{1/2}_{\alpha,\beta}))\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+o_K(1)\) for all \(t\). By choosing \(c_{\alpha,\beta}\) so that \(\mathcal{O}(c^{1/2}_{\alpha,\beta})\leq (1-\gamma)/2\), the previous inequality implies \[\begin{align} \mathbb{E}[\mathcal{L}_{\text{sum}}(t+1)]\leq \left(1-\frac{1-\gamma}{2}\right)\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+o_K(1),\quad \forall\,t, \end{align}\] which can be repeatedly used to obtain \(\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]= o_t(1)+o_K(1)\). Substituting the previous bound on \(\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]\) into (14 ), we obtain \(\max(\mathbb{E}[\mathcal{L}_{\pi}(t,K)],\mathbb{E}[\mathcal{L}_{q}(t,K)])= o_t(1)+o_K(1)\).

Step 4. Substituting the bounds we obtained for \(\mathbb{E}[\mathcal{L}_{\pi}(t,K)]\), \(\mathbb{E}[\mathcal{L}_{q}(t,K)]\), and \(\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]\) into (10 ), and then repeatedly using the resulting inequality from \(t=0\) to \(t=T\), we obtain \(\mathbb{E}[\mathcal{L}_{v}(T)]=o_T(1)+o_K(1)+\mathcal{O}(\tau)\). Now that we have obtained finite-sample bounds for \(\mathbb{E}[\mathcal{L}_{v}(T)]\), \(\mathbb{E}[\mathcal{L}_{\text{sum}}(T)]\), \(\mathbb{E}[\mathcal{L}_{\pi}(T,K)]\), and \(\mathbb{E}[\mathcal{L}_{q}(T,K)]\); using them in (?? ), we finally obtain the desired bound for the expected Nash gap.

Proof of Theorem 3. The proof of Theorem 3 is completed by carrying out Steps 1 – 4 described above with explicitly specified stepsizes. 0◻

5 Conclusion↩︎

We studied decentralized learning in two-player zero-sum matrix games and infinite-horizon discounted stochastic games. In both settings, we established finite-sample guarantees for smoothed-best-response-based learning algorithms. For matrix games, the analysis yields an \(\mathcal{O}(\epsilon^{-1})\) sample complexity for finding an \(\epsilon\)-Nash distribution and, after introducing explicit exploration, an \(\tilde{\mathcal{O}}(\epsilon^{-8})\) sample complexity for finding an \(\epsilon\)-Nash equilibrium. For stochastic games, the exploration-enhanced VI-SBR-based learning algorithm also achieves an \(\tilde{\mathcal{O}}(\epsilon^{-8})\) sample complexity for finding an \(\epsilon\)-Nash equilibrium.

The main technical contribution is a coupled Lyapunov-drift framework that handles several features arising simultaneously from decentralized learning in stochastic games: multiple interacting stochastic iterates, auxiliary games that are not exactly zero-sum during learning, and time-inhomogeneous Markovian noise generated by time-varying policies. This framework may be useful for analyzing other learning algorithms with coupled stochastic iterates.

Two directions remain particularly important as future work. First, focusing on analyzing natural best-response-type algorithms, the current bounds are unlikely to be optimal, and improving the dependence on \(\epsilon^{-1}\), the discount factor, and the mixing parameters is worth further investigation. Second, the present analyses only focus on the tabular setting, and extending the algorithmic and analytical framework to the function approximation setting would be necessary for large-scale real-world applications.

6 Proof of Theorem 1↩︎

The proof is divided into \(4\) steps. In Appendix 6.1, we prove an important boundedness property for the iterates generated by Algorithm 1. In Appendices 6.2 and 6.3, we analyze the evolution of the policies and the \(q\)-functions by establishing negative drift inequalities with respect to their associated Lyapunov functions. In Appendix 6.4, we solve the coupled Lyapunov drift inequalities to prove Theorem 1. The proofs of Corollary 1 and Corollary 2 are presented in Appendices 6.5 and 6.6, respectively. The statements and proofs of all supporting lemmas used in this section are presented in Appendix 6.7.

6.1 Boundedness of the Iterates↩︎

The following lemma presents the boundedness property.

We prove the result by induction. Since \(q_0^i=0\) and \(\pi_0^i\) is initialized as the uniform distribution on \(\mathcal{A}^i\), the base case holds. Suppose that the result holds for some \(k\geq 0\). By Line 5 of Algorithm 1, for any \(a^i\in\mathcal{A}^i\), \[\begin{align} |q_{k+1}^i(a^i)| =\,& \left| (1-\alpha_k \mathbb{1}_{\{a^i=A_k^i\}})q_k^i(a^i) + \alpha_k\mathbb{1}_{\{a^i=A_k^i\}} R_i(A_k^i,A_k^{-i}) \right|\\ \leq\,& \max\left\{ |q_k^i(a^i)|,\, (1-\alpha_k)|q_k^i(a^i)| + \alpha_k |R_i(A_k^i,A_k^{-i})| \right\}\\ \leq\,&1, \end{align}\] where the last inequality follows from the induction hypothesis \(\|q_k^i\|_\infty\leq 1\) and the bound \(|R_i(a^i,a^{-i})|\leq 1\). Hence, \(\|q_{k+1}^i\|_\infty\leq 1\).

Next, by Line 3 of Algorithm 1, for any \(a^i\in\mathcal{A}^i\), \[\begin{align} \pi_{k+1}^i(a^i) =\,& (1-\beta_k)\pi_k^i(a^i) + \beta_k[\sigma_\tau(q_k^i)](a^i)\\ \geq\,& (1-\beta_k)\ell_\tau + \frac{\beta_k}{(m-1)\exp(2\|q_k^i\|_\infty/\tau)+1} }\\ \geq\,& (1-\beta_k)\ell_\tau+\beta_k\ell_\tau \\ =\,& \ell_\tau. \end{align}\] The induction is complete. 0◻

6.2 Analysis of the Policies↩︎

Let \(V_R:\Delta(\mathcal{A}^1)\times \Delta(\mathcal{A}^2)\to \mathbb{R}\) be defined as \[\begin{align} \label{def:V95R-matrix} V_R(\mu^1,\mu^2) = \sum_{i=1,2} \max_{\hat{\mu}^i\in\Delta(\mathcal{A}^i)} \left\{ (\hat{\mu}^i-\mu^i)^\top R_i\mu^{-i} +\tau \nu(\hat{\mu}^i)-\tau\nu(\mu^i) \right\}, \end{align}\tag{16}\] where \(\nu(\cdot)\) is the Shannon entropy. For simplicity of notation, we use \(\nabla_1 V_R(\cdot,\cdot)\) and \(\nabla_2 V_R(\cdot,\cdot)\) to represent the gradients with respect to the first and second arguments of \(V_R(\cdot,\cdot)\), respectively. A sequence of properties regarding \(V_R(\cdot,\cdot)\) are provided in Lemma 16.

Next, we present the negative drift inequality of the policies generated by Algorithm 1 with respect to the Lyapunov function \(V_R(\cdot,\cdot)\).

By Lemma 10, we have \((\pi_k^1,\pi_k^2)\in\Pi_\tau\) for all \(k\geq 0\). Using the smoothness property of \(V_R(\cdot,\cdot)\) in Lemma 16 (1) and the update equation in Algorithm 1, Line 3, we have \[\begin{align} V_R(\pi_{k+1}^1,\pi_{k+1}^2) \leq\,& V_R(\pi_k^1,\pi_k^2) +\langle \nabla_1V_R(\pi_k^1,\pi_k^2),\pi_{k+1}^1-\pi_k^1 \rangle +\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\pi_{k+1}^2-\pi_k^2 \rangle\\ &+\frac{L_\tau}{2}\sum_{i=1,2}\|\pi_{k+1}^i-\pi_k^i\|_2^2\\ =\,& V_R(\pi_k^1,\pi_k^2) +\beta_k\langle \nabla_1V_R(\pi_k^1,\pi_k^2),\sigma_\tau(q_k^1)-\pi_k^1 \rangle\\ &+\beta_k\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\sigma_\tau(q_k^2)-\pi_k^2 \rangle +\frac{L_\tau\beta_k^2}{2}\sum_{i=1,2}\|\sigma_\tau(q_k^i)-\pi_k^i\|_2^2\\ \leq\,& V_R(\pi_k^1,\pi_k^2) +\beta_k\langle \nabla_1 V_R(\pi_k^1,\pi_k^2),\sigma_\tau(R_1\pi_k^2)-\pi_k^1 \rangle\\ &+\beta_k\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\sigma_\tau(R_2\pi_k^1)-\pi_k^2 \rangle\\ &+\beta_k\langle \nabla_1 V_R(\pi_k^1,\pi_k^2),\sigma_\tau(q_k^1)-\sigma_\tau(R_1\pi_k^2) \rangle\\ &+\beta_k\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\sigma_\tau(q_k^2)-\sigma_\tau(R_2\pi_k^1) \rangle +2L_\tau\beta_k^2\\ \leq\,& \left(1-\frac{\beta_k}{2}\right)V_R(\pi_k^1,\pi_k^2) +4\beta_k\left(\frac{1}{\tau \ell_\tau^2}+\frac{m^2}{\tau^3}\right) \sum_{i=1,2}\|q_k^i-R_i\pi_k^{-i} \|_2^2 +2L_\tau\beta_k^2, \end{align}\] where the last line follows from Lemma 16 (2) and (3), and we used \(\sum_{i=1,2}\|\sigma_\tau(q_k^i)-\pi_k^i\|_2^2\leq 4\).

Taking expectations on both sides and using \(c_{\alpha,\beta}=\frac{\beta_k}{\alpha_k}\leq \min\left\{\frac{\tau \ell_\tau^3}{32},\frac{\ell_\tau \tau^3}{32m^2}\right\}\), we obtain \[\begin{align} \mathbb{E}[V_R(\pi_{k+1}^1,\pi_{k+1}^2)] \leq\,& \left(1-\frac{\beta_k}{2}\right)\mathbb{E}[V_R(\pi_k^1,\pi_k^2)] +\frac{\ell_\tau\alpha_k}{4}\sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i} \|_2^2] +2L_\tau\beta_k^2. \end{align}\] This completes the proof. 0◻

6.3 Analysis of the q-Functions↩︎

For \(i\in \{1,2\}\), let \(F^i:\mathbb{R}^{m_i}\times \mathcal{A}^i\times \mathcal{A}^{-i}\to \mathbb{R}^{m_i}\) be an operator defined as \[\begin{align} [F^i(q^i,a_0^i,a_0^{-i})](a^i)=\mathbb{1}_{\{a_0^i=a^i\}} \left(R_i(a_0^i,a_0^{-i})-q^i(a_0^i)\right),\quad \forall\,(q^i,a_0^i,a_0^{-i}) \text{ and }a^i. \end{align}\] Then, Line \(5\) of Algorithm 1 can be compactly written as \[\begin{align} \label{eq:q95SA95matrix} q_{k+1}^i=q_k^i+\alpha_kF^i(q_k^i,A_k^i,A_k^{-i}). \end{align}\tag{17}\] Given a joint policy \((\pi^1,\pi^2)\), let \(\bar{F}_\pi^i:\mathbb{R}^{m_i}\to \mathbb{R}^{m_i}\) be defined as \[\begin{align} \bar{F}_\pi^i(q^i):=\mathbb{E}_{A^i\sim \pi^i(\cdot),A^{-i}\sim \pi^{-i}(\cdot)}[F^i(q^i,A^i,A^{-i})]=\text{diag}(\pi^i)(R_i\pi^{-i}-q^i). \end{align}\] Then, (17 ) can be viewed as a stochastic approximation algorithm for tracking the solution of the time-varying equation \(\bar{F}_{\pi_k}^i(q^i)=0\). We next present the negative drift inequality of the \(q\)-functions generated by Algorithm 1 with respect to a norm-square Lyapunov function.

For any \(k\geq 0\) and \(i\in \{1,2\}\), define \[\Delta_k^i=q_k^i-R_i\pi_k^{-i}, \qquad \widetilde{\Delta}_k^i=q_k^i-R_i\pi_{k+1}^{-i}.\] Since \(A_k^i\sim \pi_{k+1}^i(\cdot)\) and \(A_k^{-i}\sim \pi_{k+1}^{-i}(\cdot)\), we have \[\begin{align} \bar{F}_{\pi_{k+1}}^i(q_k^i) = \text{diag}(\pi_{k+1}^i)(R_i\pi_{k+1}^{-i}-q_k^i). \end{align}\] Using the update equation in Line 5 of Algorithm 1, we obtain \[\begin{align} \mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] =\,& \mathbb{E}[\|\widetilde{\Delta}_k^i+\alpha_k F^i(q_k^i,A_k^i,A_k^{-i})\|_2^2]\\ \leq\,& \mathbb{E}[\|\widetilde{\Delta}_k^i\|_2^2] +2\alpha_k\mathbb{E}[\langle \bar{F}_{\pi_{k+1}}^i(q_k^i),\widetilde{\Delta}_k^i\rangle] +4\alpha_k^2\\ \leq\,& (1-2\ell_\tau\alpha_k)\mathbb{E}[\|\widetilde{\Delta}_k^i\|_2^2] +4\alpha_k^2, \end{align}\] where the last inequality follows from Lemma 10 and \(\mathbb{E}[\|F^i(q_k^i,A_k^i,A_k^{-i})\|_2^2]\leq 4\).

Next, by Line 3 of Algorithm 1, \[\begin{align} \widetilde{\Delta}_k^i = \Delta_k^i + R_i(\pi_k^{-i}-\pi_{k+1}^{-i}) = \Delta_k^i - \beta_k R_i(\sigma_\tau(q_k^{-i})-\pi_k^{-i}). \end{align}\] Using the inequality \(\|x+y\|_2^2\leq (1+\eta)\|x\|_2^2+(1+\eta^{-1})\|y\|_2^2\) with \(\eta=\ell_\tau\alpha_k/2\), we have \[\begin{align} (1-2\ell_\tau\alpha_k)\|\widetilde{\Delta}_k^i\|_2^2 \leq\,& \left(1-\frac{3\ell_\tau\alpha_k}{2}\right)\|\Delta_k^i\|_2^2 + \frac{3\beta_k^2}{\ell_\tau\alpha_k} \|R_i(\sigma_\tau(q_k^{-i})-\pi_k^{-i})\|_2^2, \end{align}\] where we used the stepsize condition \(\ell_\tau\alpha_k\leq 1\). Therefore, \[\begin{align} \mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] \leq\,& \left(1-\frac{3\ell_\tau\alpha_k}{2}\right) \mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\\ &+ \frac{3m^2\beta_k^2}{\ell_\tau\alpha_k} \mathbb{E}[\|\sigma_\tau(q_k^{-i})-\pi_k^{-i}\|_2^2] +4\alpha_k^2. \end{align}\] Moreover, \[\begin{align} \mathbb{E}[\|\sigma_\tau(q_k^{-i})-\pi_k^{-i}\|_2^2] \leq\,& 2\mathbb{E}[\|\sigma_\tau(q_k^{-i})-\sigma_\tau(R_{-i}\pi_k^i)\|_2^2] + 2\mathbb{E}[\|\sigma_\tau(R_{-i}\pi_k^i)-\pi_k^{-i}\|_2^2]\\ \leq\,& \frac{2}{\tau^2} \mathbb{E}[\|q_k^{-i}-R_{-i}\pi_k^i\|_2^2] + \frac{4}{\tau}\mathbb{E}[V_R(\pi_k^1,\pi_k^2)]. \end{align}\] where we used the \(1/\tau\)-Lipschitz continuity of \(\sigma_\tau(\cdot)\) and Lemma 15. Hence, \[\begin{align} \mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] \leq\,& \left(1-\frac{3\ell_\tau\alpha_k}{2}\right) \mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\\ &+ \frac{6m^2\beta_k^2}{\ell_\tau\tau^2\alpha_k} \mathbb{E}[\|q_k^{-i}-R_{-i}\pi_k^i\|_2^2]\\ &+ \frac{12m^2\beta_k^2}{\ell_\tau\tau\alpha_k} \mathbb{E}[V_R(\pi_k^1,\pi_k^2)] +4\alpha_k^2. \end{align}\] Summing over \(i=1,2\), we obtain \[\begin{align} \sum_{i=1,2}\mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] \leq\,& \left( 1-\frac{3\ell_\tau\alpha_k}{2} + \frac{6m^2\beta_k^2}{\ell_\tau\tau^2\alpha_k} \right) \sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\\ &+ \frac{24m^2\beta_k^2}{\ell_\tau\tau\alpha_k} \mathbb{E}[V_R(\pi_k^1,\pi_k^2)] +8\alpha_k^2\\ \leq\,& \left(1-\frac{\ell_\tau\alpha_k}{2}\right) \sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2] + \frac{\beta_k}{4}\mathbb{E}[V_R(\pi_k^1,\pi_k^2)] +16\alpha_k^2, \end{align}\] where the last line follows from Condition 1. 0◻

6.4 Solving Coupled Lyapunov Drift Inequalities↩︎

For simplicity of notation, denote \(\mathcal{L}_q(k)=\sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\) and \(\mathcal{L}_\pi(k)=\mathbb{E}[V_R(\pi_k^1,\pi_k^2)]\). Then, Lemmas 11 and 12 imply that \[\begin{align} \mathcal{L}_\pi(k+1) \leq \,& \left(1-\frac{\beta_k}{2}\right)\mathcal{L}_\pi(k) +\frac{\ell_\tau\alpha_k}{4}\mathcal{L}_q(k) +2L_\tau\beta_k^2,\\ \mathcal{L}_q(k+1) \leq\,& \left(1- \frac{\ell_\tau\alpha_k}{2}\right)\mathcal{L}_q(k) +\frac{\beta_k}{4}\mathcal{L}_\pi(k) +16\alpha_k^2,\quad \forall\,k\geq 0. \end{align}\] Adding the previous two inequalities, we obtain \[\begin{align} \mathcal{L}_q(k+1)+\mathcal{L}_\pi(k+1) \leq \,& \left(1-\frac{\beta_k}{4}\right)\mathcal{L}_\pi(k) + \left(1- \frac{\ell_\tau\alpha_k}{4}\right)\mathcal{L}_q(k) +2L_\tau\beta_k^2+16\alpha_k^2\nonumber\\ \leq \,& \left(1-\frac{\beta_k}{4}\right)(\mathcal{L}_\pi(k)+\mathcal{L}_q(k)) +2L_\tau\beta_k^2+16\alpha_k^2, \label{matrix95recursion95fast} \end{align}\tag{18}\] where the second inequality follows from \(\beta_k\leq \ell_\tau\alpha_k\), or equivalently \(c_{\alpha,\beta}\leq \ell_\tau\); see Condition 1.

6.4.1 Constant Stepsizes↩︎

When using constant stepsizes, i.e., \(\alpha_k\equiv \alpha\) and \(\beta_k\equiv \beta\), iterating 18 gives, for all \(k\geq 0\), \[\begin{align} \mathcal{L}_q(k)+\mathcal{L}_\pi(k) \leq \,& \left(1-\frac{\beta}{4}\right)^k (\mathcal{L}_\pi(0)+\mathcal{L}_q(0)) +8L_\tau\beta+\frac{64\alpha^2}{\beta}\\ \leq \,& \left(1-\frac{\beta}{4}\right)^k (4+2\tau \log(m)+2m) +8L_\tau\beta+\frac{64\alpha^2}{\beta}\\ =\,& B_{\text{in}}\left(1-\frac{\beta}{4}\right)^k +8L_\tau\beta+\frac{64\alpha}{c_{\alpha,\beta}}, \end{align}\] where the second inequality follows from \(\mathcal{L}_\pi(0)\leq 4+2\tau \log(m)\) and \(\mathcal{L}_q(0)\leq 2m\). Theorem 1 (1) follows by observing that \(\mathcal{L}_q(k)+\mathcal{L}_\pi(k)\geq \mathcal{L}_\pi(k)=\mathbb{E}[\text{NG}_\tau(\pi_k^1,\pi_k^2)]\).

6.4.2 Diminishing Stepsizes↩︎

Consider using \(\alpha_k=\alpha/(k+h)\) and \(\beta_k=\beta/(k+h)\), where \(\beta=c_{\alpha,\beta}\alpha\). Recursions of the form 18 have been well studied in the literature on convergence rates of iterative algorithms [48], [50], [51]. Since \(\beta>4\), using the same line of analysis as in [51], we have \[\begin{align} \mathbb{E}[\text{NG}_\tau(\pi_k^1,\pi_k^2)]= \mathcal{L}_\pi(k)\leq \mathcal{L}_q(k)+\mathcal{L}_\pi(k) \leq\,& B_{\text{in}}\left(\frac{h}{k+h}\right)^{\beta/4} + \left(64e L_\tau\beta +\frac{512e \alpha}{c_{\alpha,\beta}}\right) \frac{1}{k+h}. \end{align}\]

6.5 Proof of Corollary 1↩︎

We use Theorem 1 (1) to derive the sample complexity, and choose \(\beta=c_{\alpha,\beta}\alpha\) with \(c_{\alpha,\beta}\) satisfying Condition 1. To achieve \(\mathbb{E}[\text{NG}_\tau(\pi_K^1,\pi_K^2)]\leq \epsilon\), in view of Theorem 1 (1), it is sufficient that \[\begin{align} B_{\text{in}}e^{-\beta K/4}\leq \frac{\epsilon}{3},\quad 8L_\tau\beta\leq \frac{\epsilon}{3},\quad \frac{64\alpha}{c_{\alpha,\beta}}\leq \frac{\epsilon}{3}. \end{align}\] The first inequality is satisfied when \(K\geq 4\log(3B_{\text{in}}/\epsilon)/\beta\). Since \(\alpha=\beta/c_{\alpha,\beta}\), the last two inequalities are satisfied when \(\beta\leq \min\left\{\frac{\epsilon}{24L_\tau},\frac{\epsilon c_{\alpha,\beta}^2}{192}\right\}\). Therefore, \(\mathbb{E}[\text{NG}_\tau(\pi_K^1,\pi_K^2)]\leq \epsilon\) holds as long as \[\begin{align} K\geq \frac{96\log(3B_{\text{in}}/\epsilon)}{\epsilon} \max\left\{L_\tau,\frac{8}{c_{\alpha,\beta}^2}\right\}. \end{align}\] The result follows by observing that \(\max\{L_\tau,8/c_{\alpha,\beta}^2\}\leq 8L_\tau/c_{\alpha,\beta}^2\).

6.6 Proof of Corollary 2↩︎

In view of 3 , for the output \((\pi_K^1,\pi_K^2)\) of Algorithm 1, we have \[\begin{align} \mathbb{E}[\text{NG}(\pi_K^1,\pi_K^2)] \leq \mathbb{E}[\text{NG}_\tau(\pi_K^1,\pi_K^2)] + 2\tau\log(m). \end{align}\] Therefore, given \(\epsilon>0\), to achieve \(\mathbb{E}[\text{NG}(\pi_K^1,\pi_K^2)]\leq \epsilon\), it is sufficient that \(\mathbb{E}[\text{NG}_\tau(\pi_K^1,\pi_K^2)]\leq\epsilon/2\) and \(2\tau \log(m)\leq \epsilon/2\). The previous two inequalities hold as long as \[\begin{align} \label{eq:sc:matrix95slow} \tau\leq \frac{\epsilon}{4\log(m)}, \quad \text{and}\quad K\geq \frac{3200L_\tau\log(3B_{\text{in}}/\epsilon)}{c_{\alpha,\beta}^2\epsilon}, \end{align}\tag{19}\] where the second condition follows from the same line of analysis as in the proof of Corollary 1.

Choose \[\begin{align} c_{\alpha,\beta} = \min\left\{ \frac{\tau \ell_\tau^3}{32}, \frac{\ell_\tau \tau^3}{128m^2}, \frac{2\sqrt{2}}{L_\tau^{1/2}} \right\}, \end{align}\] which satisfies Condition 1. Taking \(\tau=\epsilon/(4\log(m))\), we have \[\begin{align} \ell_\tau = \frac{1}{(m-1)\exp(2/\tau)+1} = \frac{1}{(m-1)\exp(8\log(m)/\epsilon)+1} =: f(\epsilon). \end{align}\] Moreover, since \(L_\tau=\tau/\ell_\tau+m^2/\tau\), we have \(L_\tau=\mathcal{O}(1/(\tau\ell_\tau))\), where the hidden constant depends only on \(m\). Thus, \[\begin{align} \frac{L_\tau}{c_{\alpha,\beta}^2} = \mathcal{O}\left( \max\left\{ \frac{L_\tau}{\tau^2\ell_\tau^6}, \frac{L_\tau}{\ell_\tau^2\tau^6}, L_\tau^2 \right\} \right) = \mathcal{O}\left( \max\left\{ \frac{1}{\tau^3\ell_\tau^7}, \frac{1}{\tau^7\ell_\tau^3} \right\} \right), \end{align}\] where the term \(L_\tau^2\) is dominated by the first term because \(\tau\leq 1\) and \(\ell_\tau\leq 1\). Substituting \(\tau=\epsilon/(4\log(m))\) and \(\ell_\tau=f(\epsilon)\) into 19 , we obtain \[\begin{align} K = \mathcal{O}\left( \frac{\log(1/\epsilon)}{\epsilon^4 f(\epsilon)^3\min\{f(\epsilon)^4,\epsilon^4\}} \right). \end{align}\]

6.7 Statements and Proofs of Supporting Lemmas↩︎

Given any \(x\in\mathbb{R}^d\) and \(j\in[d]\), we have \[\begin{align} [\sigma_\tau(x)]_j =\,&\frac{\exp(x_j/\tau)}{\sum_{\ell=1}^d\exp(x_\ell/\tau)}\\ =\,&\frac{1}{\sum_{\ell\neq j}\exp((x_\ell-x_j)/\tau)+1}\\ \geq\,&\frac{1}{(d-1)\exp(2\|x\|_\infty/\tau)+1}. \end{align}\] The claim follows since the right-hand side is independent of \(j\). 0◻

Fix \(i\in \{1,2\}\). For any \(\mu^i\in \Delta(\mathcal{A}^i)\) satisfying \(\min_{a^i\in\mathcal{A}^i}\mu^i(a^i)\geq \ell_\tau\), the Hessian of the negative entropy function \(\nu(\cdot)\) satisfies \[\begin{align} 0\cdot I_{m_i} \succeq\nabla^2 \nu(\mu^i) = -\text{diag}(\mu^i)^{-1} \succeq \frac{-1}{\min_{a^i\in\mathcal{A}^i}\mu^i(a^i)} I_{m_i} \succeq \frac{-1}{\ell_\tau} I_{m_i}. \end{align}\] Therefore, \(\nabla \nu(\cdot)\) is \(1/\ell_\tau\)-Lipschitz continuous with respect to \(\|\cdot\|_2\) on the set \(\{\mu^i\in\Delta(\mathcal{A}^i)\mid \min_{a^i\in\mathcal{A}^i}\mu^i(a^i)\geq \ell_\tau\}\) [62]. This proves the desired inequality. 0◻

Recall that the entropy function \(\nu(\cdot)\) is \(1\)-strongly concave with respect to \(\|\cdot\|_2\) [63]. Fix \(i\in \{1,2\}\) and \(\mu^{-i}\in\Delta(\mathcal{A}^{-i})\). Define \[\begin{align} F_i(\mu^i) := \max_{\hat{\mu}^i\in\Delta(\mathcal{A}^i)} \left\{ (\hat{\mu}^i-\mu^i)^\top R_i\mu^{-i} + \tau \nu(\hat{\mu}^i) - \tau\nu(\mu^i) \right\}. \end{align}\] As a function of \(\mu^i\), \(F_i(\mu^i)\) is \(\tau\)-strongly convex. Moreover, its minimizer is \(\sigma_\tau(R_i\mu^{-i})\), and \(F_i(\sigma_\tau(R_i\mu^{-i}))=0\). Therefore, by the quadratic growth property of strongly convex functions, \[\begin{align} \|\sigma_\tau(R_i\mu^{-i})-\mu^i\|_2^2 \leq \frac{2}{\tau}F_i(\mu^i) \leq \frac{2}{\tau}V_R(\mu^1,\mu^2). \end{align}\] This proves the desired result. 0◻

Denote \(\Pi_\tau=\{(\pi^1,\pi^2)\in\Delta(\mathcal{A}^1)\times\Delta(\mathcal{A}^2)\mid \min_{a^1\in\mathcal{A}^1}\pi^1(a^1)\geq \ell_\tau,\min_{a^2\in\mathcal{A}^2}\pi^2(a^2)\geq \ell_\tau\}\). Note that Lemma 10 implies that \((\pi_k^1,\pi_k^2)\in\Pi_\tau\) for all \(k\geq 0\).

Recall the definition of \(V_R(\cdot,\cdot)\) in 16 . By Danskin’s theorem [64] and the zero-sum condition \(R_1+R_2^\top=0\), we have \[\tag{20} \begin{align} \nabla_1V_R(\mu^1,\mu^2) =\,& -\tau \nabla \nu(\mu^1) + R_2^\top \sigma_\tau(R_2\mu^1), \tag{21}\\ \nabla_2V_R(\mu^1,\mu^2) =\,& -\tau \nabla \nu(\mu^2) + R_1^\top \sigma_\tau(R_1\mu^2). \tag{22} \end{align}\]

(1) For any \((\mu^1,\mu^2),(\Bar{\mu}^1,\Bar{\mu}^2)\in\Pi_\tau\), we have by 20 that \[\begin{align} \|\nabla_1V_R(\mu^1,\mu^2)-\nabla_1V_R(\Bar{\mu}^1,\Bar{\mu}^2)\|_2 \leq\,& \tau \|\nabla \nu(\Bar{\mu}^1)- \nabla \nu(\mu^1)\|_2 + \|R_2\|_2 \|\sigma_\tau(R_2\mu^1)-\sigma_\tau(R_2\Bar{\mu}^1)\|_2\\ \leq\,& \frac{\tau}{\ell_\tau}\|\mu^1-\Bar{\mu}^1\|_2 + \frac{\|R_2\|_2^2}{\tau}\|\mu^1-\Bar{\mu}^1\|_2\\ \leq\,& \left(\frac{\tau}{\ell_\tau}+\frac{m^2}{\tau}\right) \|\mu^1-\Bar{\mu}^1\|_2\\ =\,& L_\tau \|\mu^1-\Bar{\mu}^1\|_2 \end{align}\] where the second inequality follows from Lemma 14 and the \(1/\tau\) – Lipschitz continuity of \(\sigma_\tau(\cdot)\) in \(\|\cdot\|_2\) [63], and the last inequality follows from \(\|R_i\|_2\leq \sqrt{m_1m_2}\leq m\) for \(i\in \{1,2\}\). Similarly, \[\begin{align} \|\nabla_2V_R(\mu^1,\mu^2)-\nabla_2V_R(\Bar{\mu}^1,\Bar{\mu}^2)\|_2 \leq L_\tau \|\mu^2-\Bar{\mu}^2\|_2. \end{align}\] It follows that \[\begin{align} \|\nabla V_R(\mu^1,\mu^2)-\nabla V_R(\Bar{\mu}^1,\Bar{\mu}^2)\|_2^2 \leq\,& L_\tau^2 \sum_{i=1,2}\|\mu^i-\Bar{\mu}^i\|_2^2. \end{align}\] Therefore, \(V_R(\cdot,\cdot)\) is an \(L_\tau\) – smooth function on \(\Pi_\tau\) [62].

(2) By the optimality condition of the softmax map, we have \[\begin{align} \left\langle R_1\mu^2+\tau \nabla \nu(\sigma_\tau(R_1 \mu^2)), \sigma_\tau(R_1\mu^2)-\mu^1 \right\rangle = 0. \end{align}\] Thus, by 20 , \[\begin{align} \langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(R_1\mu^2)-\mu^1 \rangle =\,& \tau\langle \nabla \nu(\sigma_\tau(R_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau(R_1\mu^2)-\mu^1 \rangle\\ &+ ( \sigma_\tau(R_2 \mu^1)-\mu^2)^\top R_2( \sigma_\tau(R_1\mu^2)-\mu^1 ). \end{align}\] By the concavity of \(\nu(\cdot)\) and the same optimality condition, \[\begin{align} &\langle \nabla \nu(\sigma_\tau(R_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau(R_1\mu^2)-\mu^1 \rangle\\ \leq\,& \frac{1}{\tau} \left[ (\mu^1)^\top R_1 \mu^2 + \tau \nu(\mu^1) - \max_{\hat{\mu}^1\in\Delta(\mathcal{A}^1)} \left\{ (\hat{\mu}^1)^\top R_1\mu^2+\tau \nu(\hat{\mu}^1) \right\} \right]. \end{align}\] Therefore, \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(R_1\mu^2)-\mu^1 \rangle\\ \leq\,& (\mu^1)^\top R_1 \mu^2 + \tau \nu(\mu^1) - \max_{\hat{\mu}^1\in\Delta(\mathcal{A}^1)} \left\{ (\hat{\mu}^1)^\top R_1\mu^2+\tau \nu(\hat{\mu}^1) \right\}\\ &+ ( \sigma_\tau(R_2 \mu^1)-\mu^2)^\top R_2( \sigma_\tau(R_1\mu^2)-\mu^1 ). \end{align}\] Similarly, \[\begin{align} &\langle \nabla_2V_R(\mu^1,\mu^2),\sigma_\tau(R_2\mu^1)-\mu^2 \rangle\\ \leq\,& (\mu^2)^\top R_2 \mu^1 + \tau \nu(\mu^2) - \max_{\hat{\mu}^2\in\Delta(\mathcal{A}^2)} \left\{ (\hat{\mu}^2)^\top R_2\mu^1+\tau \nu(\hat{\mu}^2) \right\}\\ &+ ( \sigma_\tau(R_1 \mu^2)-\mu^1)^\top R_1( \sigma_\tau(R_2\mu^1)-\mu^2 ). \end{align}\] Adding the previous two inequalities and using \(R_1+R_2^\top=0\), we obtain \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(R_1\mu^2)-\mu^1 \rangle + \langle \nabla_2V_R(\mu^1,\mu^2),\sigma_\tau(R_2\mu^1)-\mu^2 \rangle\\ \leq\,& -V_R(\mu^1,\mu^2) + ( \sigma_\tau(R_1 \mu^2)-\mu^1)^\top (R_1+R_2^\top ) ( \sigma_\tau(R_2\mu^1)-\mu^2 )\\ =\,& -V_R(\mu^1,\mu^2). \end{align}\]

(3) By the optimality condition of the softmax map, we have \[\begin{align} \left\langle R_1\mu^2+\tau \nabla \nu(\sigma_\tau(R_1 \mu^2)), \sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2) \right\rangle = 0. \end{align}\] Therefore, by 20 , \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2)\rangle\\ =\,& \tau\langle \nabla \nu(\sigma_\tau(R_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2) \rangle\\ &+ ( \sigma_\tau(R_2 \mu^1)-\mu^2)^\top R_2( \sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2)). \end{align}\] By the Cauchy–Schwarz inequality and the AM-GM inequality, for any \(c_1,c_2>0\), \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2)\rangle\\ \leq\,& \frac{\tau}{2 c_1} \|\nabla \nu(\sigma_\tau(R_1 \mu^2))- \nabla \nu(\mu^1)\|_2^2 + \frac{\tau c_1}{2} \|\sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2) \|_2^2\\ &+ \frac{1}{2 c_2}\|\sigma_\tau(R_2 \mu^1)-\mu^2\|_2^2 + \frac{c_2}{2}\|R_2( \sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2) )\|_2^2\\ \leq\,& \frac{\tau}{2 c_1 \ell_\tau^2}\|\sigma_\tau(R_1 \mu^2)- \mu^1\|_2^2 + \frac{c_1}{2\tau}\|q^1-R_1\mu^2 \|_2^2\\ &+ \frac{1}{2 c_2}\|\sigma_\tau(R_2 \mu^1)-\mu^2\|_2^2 + \frac{c_2 \|R_2\|_2^2}{2 \tau^2}\| q^1-R_1\mu^2 \|_2^2\\ \leq\,& \left(\frac{1}{c_1 \ell_\tau^2}+\frac{1}{\tau c_2}\right) V_R(\mu^1,\mu^2) + \frac{c_1}{2\tau}\|q^1-R_1\mu^2 \|_2^2\\ &+ \frac{c_2 \|R_2\|_2^2}{2 \tau^2}\| q^1-R_1\mu^2 \|_2^2, \end{align}\] where the second inequality follows from Lemma 14 and the \(1/\tau\) – Lipschitz continuity of \(\sigma_\tau(\cdot)\), and the last inequality follows from Lemma 15. Choosing \(c_1=8/\ell_\tau^2\) and \(c_2=8/\tau\) gives \[\begin{align} \langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2)\rangle \leq\,& \frac{1}{4}V_R(\mu^1,\mu^2) + \frac{4}{\tau \ell_\tau^2}\|q^1-R_1\mu^2 \|_2^2\\ &+ \frac{4 \|R_2\|_2^2}{ \tau^3}\| q^1-R_1\mu^2 \|_2^2. \end{align}\] Similarly, \[\begin{align} \langle \nabla_2V_R(\mu^1,\mu^2),\sigma_\tau(q^2)-\sigma_\tau(R_2\mu^1)\rangle \leq\,& \frac{1}{4}V_R(\mu^1,\mu^2) + \frac{4}{\tau\ell_\tau^2}\|q^2-R_2\mu^1\|_2^2\\ &+ \frac{4 \|R_1\|_2^2}{ \tau^3}\| q^2-R_2\mu^1\|_2^2. \end{align}\] Summing up the previous two inequalities and using \(\|R_i\|_2\leq m\) for \(i\in \{1,2\}\), we obtain \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2)\rangle + \langle \nabla_2V_R(\mu^1,\mu^2),\sigma_\tau(q^2)-\sigma_\tau(R_2\mu^1)\rangle\\ \leq\,& \frac{1}{2}V_R(\mu^1,\mu^2) + 4\left(\frac{1}{\tau \ell_\tau^2}+\frac{m^2}{ \tau^3}\right) \sum_{i=1,2}\|q^i-R_i\mu^{-i} \|_2^2. \end{align}\]

0◻

7 Proof of Theorem 2↩︎

The proof of Theorem 2 follows the same high-level structure as that of Theorem 1: we first establish boundedness of the iterates, then derive Lyapunov drift inequalities for the policies and the \(q\)-functions, and finally solve the resulting coupled inequalities. However, because Algorithm 2 replaces \(\sigma_\tau(\cdot)\) with \(\sigma_\tau^{\bar{\epsilon}}(\cdot)\), the drift inequalities for both the policies and the \(q\)-functions differ substantially from those in the proof of Theorem 1.

7.1 Boundedness of the Iterates↩︎

The proof of Lemma 17 is identical to that of Lemma 10, and therefore is omitted.

7.2 Analysis of the Policies↩︎

We also use the Lyapunov function \(V_R(\cdot,\cdot)\) defined in 20 to analyze the policies. Lemma 20 provides the properties of \(V_R(\cdot,\cdot)\) needed for the proof of Theorem 2. We next present the negative drift inequality for the policies generated by Algorithm 2.

Using the smoothness property of \(V_R(\cdot,\cdot)\) in Lemma 20 (1) and the update equation in Line 3 of Algorithm 2, we have for any \(k\geq 0\) that \[\begin{align} V_R(\pi_{k+1}^1,\pi_{k+1}^2) \leq \,& V_R(\pi_k^1,\pi_k^2) +\beta_k\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\sigma_\tau^{\bar{\epsilon}}(q_k^2)-\pi_k^2 \rangle\\ &+\beta_k\langle \nabla_1V_R(\pi_k^1,\pi_k^2),\sigma_\tau^{\bar{\epsilon}}(q_k^1)-\pi_k^1 \rangle +\frac{L_{\tau,\Bar{\epsilon}}\beta_k^2}{2}\sum_{i=1,2}\|\sigma_\tau^{\bar{\epsilon}}(q_k^i)-\pi_k^i\|_2^2\\ \leq \,& V_R(\pi_k^1,\pi_k^2) +\beta_k\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\sigma_\tau(R_2\pi_k^1)-\pi_k^2 \rangle\\ &+\beta_k\langle \nabla_1 V_R(\pi_k^1,\pi_k^2),\sigma_\tau(R_1\pi_k^2)-\pi_k^1 \rangle\\ &+\beta_k\langle \nabla_2V_R(\pi_k^1,\pi_k^2),\sigma_\tau^{\bar{\epsilon}}(q_k^2)-\sigma_\tau(R_2\pi_k^1) \rangle\\ &+\beta_k\langle \nabla_1 V_R(\pi_k^1,\pi_k^2),\sigma_\tau^{\bar{\epsilon}}(q_k^1)-\sigma_\tau(R_1\pi_k^2) \rangle +2L_{\tau,\Bar{\epsilon}}\beta_k^2\\ \leq \,& (1-\beta_k)V_R(\pi_k^1,\pi_k^2) +2L_{\tau,\Bar{\epsilon}}\beta_k^2\\ &+\frac{2\beta_k}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+m\right) \sum_{i=1,2}\|q_k^i-R_i\pi_k^{-i}\|_2 +8\Bar{\epsilon}\beta_k\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+m\right), \end{align}\] where the last line follows from Lemma 20 (2) and (3), and we used \(\sum_{i=1,2}\|\sigma_\tau^{\bar{\epsilon}}(q_k^i)-\pi_k^i\|_2^2\leq 4\).

Taking expectations on both sides gives \[\begin{align} \mathbb{E}[V_R(\pi_{k+1}^1,\pi_{k+1}^2)] \leq \,& (1-\beta_k)\mathbb{E}[V_R(\pi_k^1,\pi_k^2)] +2L_{\tau,\Bar{\epsilon}}\beta_k^2\\ &+\frac{2\beta_k}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+m\right) \sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2]+8\Bar{\epsilon}\beta_k\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+m\right). \end{align}\] Finally, \[\begin{align} \sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2] \leq\,& \sum_{i=1,2} \left(\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\right)^{1/2}\\ \leq\,& \left(2\sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\right)^{1/2}\\ \leq\,& 2\left(\sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\right)^{1/2}. \end{align}\] Substituting this bound into the previous display gives the desired result. 0◻

7.3 Analysis of the q-Functions↩︎

Similar to the analysis of Algorithm 1, for \(i\in \{1,2\}\), let \(F^i:\mathbb{R}^{m_i}\times \mathcal{A}^i\times \mathcal{A}^{-i}\to \mathbb{R}^{m_i}\) be defined as \[\begin{align} [F^i(q^i,a_0^i,a_0^{-i})](a^i) = \mathbb{1}_{\{a_0^i=a^i\}} \left(R_i(a_0^i,a_0^{-i})-q^i(a_0^i)\right), \quad \forall\,(q^i,a_0^i,a_0^{-i}) \text{ and }a^i. \end{align}\] Then, Algorithm 2, Line 5, can be compactly written as \[\begin{align} \label{eq:q95SA95matrix95slow} q_{k+1}^i=q_k^i+\alpha_kF^i(q_k^i,A_k^i,A_k^{-i}). \end{align}\tag{23}\] Given a joint policy \(\pi=(\pi^1,\pi^2)\), let \(\bar{F}_\pi^i:\mathbb{R}^{m_i}\to \mathbb{R}^{m_i}\) be defined as \[\begin{align} \bar{F}_\pi^i(q^i) = \mathbb{E}_{A^i\sim \pi^i(\cdot),A^{-i}\sim \pi^{-i}(\cdot)} [F^i(q^i,A^i,A^{-i})] = \text{diag}(\pi^i)(R_i\pi^{-i}-q^i). \end{align}\] We next establish the negative drift inequality of the \(q\)-functions generated by Algorithm 2 with respect to the norm-square Lyapunov function.

For any \(k\geq 0\) and \(i\in\{1,2\}\), define \(\Delta_k^i=q_k^i-R_i\pi_k^{-i}\) and \(\widetilde{\Delta}_k^i=q_k^i-R_i\pi_{k+1}^{-i}\). Since \(A_k^i\sim \pi_{k+1}^i(\cdot)\) and \(A_k^{-i}\sim \pi_{k+1}^{-i}(\cdot)\), we have \[\begin{align} \bar{F}_{\pi_{k+1}}^i(q_k^i) = \text{diag}(\pi_{k+1}^i)(R_i\pi_{k+1}^{-i}-q_k^i). \end{align}\] Using 23 , we obtain \[\begin{align} \mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] =\,& \mathbb{E}[\|\widetilde{\Delta}_k^i+\alpha_kF^i(q_k^i,A_k^i,A_k^{-i})\|_2^2]\\ =\,& \mathbb{E}[\|\widetilde{\Delta}_k^i\|_2^2] +2\alpha_k \mathbb{E}[\langle \bar{F}_{\pi_{k+1}}^i(q_k^i),\widetilde{\Delta}_k^i\rangle] +\alpha_k^2 \mathbb{E}[\|F^i(q_k^i,A_k^i,A_k^{-i})\|_2^2]\\ \leq\,& (1-2\ell_{\tau,\Bar{\epsilon}}\alpha_k) \mathbb{E}[\|\widetilde{\Delta}_k^i\|_2^2] +4\alpha_k^2, \end{align}\] where the last line follows from Lemma 17 and \(\mathbb{E}[\|F^i(q_k^i,A_k^i,A_k^{-i})\|_2^2]\leq 4\).

Next, by Line 3 of Algorithm 2, \[\begin{align} \widetilde{\Delta}_k^i = q_k^i-R_i\pi_{k+1}^{-i} = \Delta_k^i-\beta_kR_i(\sigma_\tau^{\bar{\epsilon}}(q_k^{-i})-\pi_k^{-i}). \end{align}\] Using \(\|x+y\|_2^2\leq (1+\eta)\|x\|_2^2+(1+\eta^{-1})\|y\|_2^2\) with \(\eta=\ell_{\tau,\Bar{\epsilon}}\alpha_k/2\), and using \(\ell_{\tau,\Bar{\epsilon}}\alpha_k\leq 1\), we have \[\begin{align} (1-2\ell_{\tau,\Bar{\epsilon}}\alpha_k)\|\widetilde{\Delta}_k^i\|_2^2 \leq\,& (1-\ell_{\tau,\Bar{\epsilon}}\alpha_k)\|\Delta_k^i\|_2^2 + \frac{3\beta_k^2}{\ell_{\tau,\Bar{\epsilon}}\alpha_k} \|R_i(\sigma_\tau^{\bar{\epsilon}}(q_k^{-i})-\pi_k^{-i})\|_2^2. \end{align}\] Therefore, \[\begin{align} \mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] \leq\,& (1-\ell_{\tau,\Bar{\epsilon}}\alpha_k) \mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\\ &+ \frac{3\beta_k^2}{\ell_{\tau,\Bar{\epsilon}}\alpha_k} \mathbb{E}[\|R_i(\sigma_\tau^{\bar{\epsilon}}(q_k^{-i})-\pi_k^{-i})\|_2^2] +4\alpha_k^2. \end{align}\] Since both \(\sigma_\tau^{\bar{\epsilon}}(q_k^{-i})\) and \(\pi_k^{-i}\) are probability vectors, we have \(\|\sigma_\tau^{\bar{\epsilon}}(q_k^{-i})-\pi_k^{-i}\|_2^2\leq 4\). Hence, \[\begin{align} \mathbb{E}[\|R_i(\sigma_\tau^{\bar{\epsilon}}(q_k^{-i})-\pi_k^{-i})\|_2^2] \leq 4\|R_i\|_2^2 \leq 4m^2. \end{align}\] It follows that \[\begin{align} \mathbb{E}[\|q_{k+1}^i-R_i\pi_{k+1}^{-i}\|_2^2] \leq\,& (1-\ell_{\tau,\Bar{\epsilon}}\alpha_k) \mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2] +4\alpha_k^2 +\frac{12m^2}{\ell_{\tau,\Bar{\epsilon}}\alpha_k}\beta_k^2. \end{align}\] The final result follows by summing the previous inequality over \(i\in\{1,2\}\). 0◻

7.4 Solving Coupled Lyapunov Drift Inequalities↩︎

Denote \(\mathcal{L}_q(k)=\sum_{i=1,2}\mathbb{E}[\|q_k^i-R_i\pi_k^{-i}\|_2^2]\) and \(\mathcal{L}_\pi(k)=\mathbb{E}[V_R(\pi_k^1,\pi_k^2)]\) for simplicity of notation. When \(\alpha_k\equiv \alpha\) and \(\beta_k\equiv \beta\), Lemmas 18 and 19 state that \[\begin{align} \mathcal{L}_q(k+1) \leq \,& \left(1-\ell_{\tau,\Bar{\epsilon}}\alpha\right)\mathcal{L}_q(k) +16\alpha^2+\frac{24m^2}{\alpha\ell_{\tau,\Bar{\epsilon}}}\beta^2, \tag{24}\\ \mathcal{L}_\pi(k+1) \leq \,& (1-\beta)\mathcal{L}_\pi(k) +\frac{4\beta}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+ m\right)\mathcal{L}_q^{1/2}(k)+ 8\Bar{\epsilon}\beta\left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}}+m\right) +2L_{\tau,\Bar{\epsilon}} \beta^2. \tag{25} \end{align}\] Iterating 24 , we have for all \(k\geq 0\) that \[\begin{align} \mathcal{L}_q(k) \leq\,& \left(1-\ell_{\tau,\Bar{\epsilon}}\alpha\right)^k\mathcal{L}_q(0) +\frac{16\alpha}{\ell_{\tau,\Bar{\epsilon}}} +\frac{24\beta^2m^2}{\alpha^2\ell_{\tau,\Bar{\epsilon}}^2}. \end{align}\] Therefore, \[\begin{align} \mathcal{L}_q^{1/2}(k) \leq\,& \left(1-\ell_{\tau,\Bar{\epsilon}}\alpha\right)^{k/2}\mathcal{L}_q^{1/2}(0) +\frac{4\sqrt{\alpha}}{\ell_{\tau,\Bar{\epsilon}}^{1/2}} +\frac{5\beta m}{\alpha \ell_{\tau,\Bar{\epsilon}}}. \end{align}\] Substituting this bound into 25 , we obtain \[\begin{align} \mathcal{L}_\pi(k+1) \leq \,& (1-\beta)\mathcal{L}_\pi(k) +8\Bar{\epsilon}\beta\left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}}+ m\right) +2L_{\tau,\Bar{\epsilon}}\beta^2\\ &+ \frac{4\beta}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+ m\right) \left[ \left(1-\ell_{\tau,\Bar{\epsilon}}\alpha\right)^{k/2}\mathcal{L}_q^{1/2}(0) +\frac{4\sqrt{\alpha}}{\ell_{\tau,\Bar{\epsilon}}^{1/2}} +\frac{5\beta m}{\alpha \ell_{\tau,\Bar{\epsilon}}} \right]. \end{align}\] Iterating the previous inequality, and using \(\beta\leq \ell_{\tau,\Bar{\epsilon}}\alpha/2\), we have \[\begin{align} \mathcal{L}_\pi(k) \leq \,& (1-\beta)^k\mathcal{L}_\pi(0) +8\Bar{\epsilon}\left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}}+ m\right) +2L_{\tau,\Bar{\epsilon}}\beta\\ &+ \frac{8}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+ m\right) \beta k(1-\beta)^k\mathcal{L}_q^{1/2}(0)+ \frac{4}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+ m\right) \left[ \frac{4\sqrt{\alpha}}{\ell_{\tau,\Bar{\epsilon}}^{1/2}} +\frac{5\beta m}{\alpha \ell_{\tau,\Bar{\epsilon}}} \right]\\ \leq \,& (1-\beta)^k\left( \mathcal{L}_\pi(0) + 8\left(\frac{1}{\ell_{\tau,\Bar{\epsilon}}} + \frac{m}{\tau}\right) \beta k \mathcal{L}_q^{1/2}(0) \right)\\ &+ 8\Bar{\epsilon}\left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}}+ m\right) +\ell_{\tau,\Bar{\epsilon}} L_{\tau,\Bar{\epsilon}} \alpha+ 4\left(\frac{1}{\ell_{\tau,\Bar{\epsilon}}} + \frac{m}{\tau}\right) \left[ \frac{4\sqrt{\alpha}}{\ell_{\tau,\Bar{\epsilon}}^{1/2}} +\frac{5\beta m}{\alpha \ell_{\tau,\Bar{\epsilon}}} \right], \end{align}\] where we used \(2L_{\tau,\Bar{\epsilon}}\beta\leq \ell_{\tau,\Bar{\epsilon}}L_{\tau,\Bar{\epsilon}}\alpha\).

Since \(\ell_{\tau,\Bar{\epsilon}}\geq \Bar{\epsilon}/m\) by Lemma 17, \(\Bar{\epsilon}=\tau\), and \(L_{\tau,\Bar{\epsilon}}=\tau/\ell_{\tau,\Bar{\epsilon}}+m^2/\tau\), we have \[\begin{align} \mathcal{L}_\pi(k) \leq\,& (1-\beta)^k\left( \mathcal{L}_\pi(0)+8\alpha k \mathcal{L}_q^{1/2}(0) \right) +16\tau m +\frac{2m}{\tau}\alpha +\frac{32m^{3/2}\sqrt{\alpha}}{\tau^{3/2}} +\frac{40\beta m^3}{\alpha \tau^2}. \end{align}\] Note that \(\mathcal{L}_\pi(0)\leq 4+2\tau \log(m)\), \(\mathcal{L}_q(0)\leq 2m\), and \(\text{NG}(\pi_k^1,\pi_k^2) \leq \mathcal{L}_\pi(k)+2\tau\log(m)\). Therefore, \[\begin{align} \mathbb{E}[\text{NG}(\pi_k^1,\pi_k^2)] \leq\,& (1-\beta)^k \left( 4+2\tau\log(m)+8\sqrt{2m}\alpha k \right)\\ &+ 16\tau m +2\tau\log(m) +\frac{2m}{\tau}\alpha +\frac{32m^{3/2}\sqrt{\alpha}}{\tau^{3/2}} +\frac{40\beta m^3}{\alpha \tau^2}\\ \leq\,& 20\sqrt{m}k(1-\beta)^k+ 18\tau m +\frac{2m}{\tau}\alpha +\frac{32m^{3/2}\sqrt{\alpha}}{\tau^{3/2}} +\frac{40\beta m^3}{\alpha \tau^2}. \end{align}\]

7.5 Proof of Corollary 3↩︎

In view of Theorem 2, we have \[\begin{align} \mathbb{E}[\text{NG}(\pi_K^1,\pi_K^2)] \leq\,& 20\sqrt{m}K(1-\beta)^K +18\tau m +\frac{2m}{\tau}\alpha +\frac{32m^{3/2}\sqrt{\alpha}}{\tau^{3/2}} +\frac{40\beta m^3}{\alpha \tau^2}. \end{align}\] Given \(\epsilon>0\), choose \(\tau=\epsilon/(90m)\), \(\alpha=\epsilon^2\tau^3/(160^2m^3)\), and \(\beta=\epsilon\alpha\tau^2/(200m^3)\). Then \(18\tau m=\epsilon/5\), and direct substitution gives \[\begin{align} \frac{2m}{\tau}\alpha \leq \frac{\epsilon}{5},\qquad \frac{32m^{3/2}\sqrt{\alpha}}{\tau^{3/2}} = \frac{\epsilon}{5},\qquad \frac{40\beta m^3}{\alpha \tau^2} = \frac{\epsilon}{5}. \end{align}\] It remains to control the transient term. Since \((1-\beta)^K\leq e^{-\beta K}\), it is sufficient to ensure \(20\sqrt{m}K e^{-\beta K}\leq \epsilon/5\). This holds whenever \[\begin{align} K \geq \frac{2}{\beta} \log\left(\frac{100\sqrt{m}}{\epsilon\beta}\right). \end{align}\] Indeed, for such \(K\), we have \(\beta K\geq 2\log(100\sqrt{m}/(\epsilon\beta))\), and hence \(K e^{-\beta K}\leq \epsilon/(100\sqrt{m})\). Therefore, \(20\sqrt{m}K e^{-\beta K}\leq \epsilon/5\). Combining the previous bounds gives \(\mathbb{E}[\text{NG}(\pi_K^1,\pi_K^2)]\leq \epsilon\).

Finally, substituting \(\tau=\epsilon/(90m)\) and \(\alpha=\epsilon^2\tau^3/(160^2m^3)\) into \(\beta=\epsilon\alpha\tau^2/(200m^3)\) gives \(\beta=\Theta(\epsilon^8/m^{11})\). Therefore, \[\begin{align} K = \mathcal{O}\left( m^{11}\epsilon^{-8} \log\left(\frac{m}{\epsilon}\right) \right). \end{align}\]

7.6 Statements and Proofs of Supporting Lemmas↩︎

Let \(\Pi_{\tau,\Bar{\epsilon}}=\{(\pi^1,\pi^2)\in\Delta(\mathcal{A}^1)\times\Delta(\mathcal{A}^2)\mid \min_{a^1\in\mathcal{A}^1}\pi^1(a^1)\geq \ell_{\tau,\Bar{\epsilon}},\min_{a^2\in\mathcal{A}^2}\pi^2(a^2)\geq \ell_{\tau,\Bar{\epsilon}}\}\). Note that Lemma 17 implies that \((\pi_k^1,\pi_k^2)\in\Pi_{\tau,\Bar{\epsilon}}\) for all \(k\geq 0\).

The proof of Lemma 20 (1) and (2) is identical to that of Lemma 16 (1) and (2), and therefore is omitted. For Lemma 20 (3), recall that by Danskin’s theorem [64], \[\begin{align} \nabla_1V_R(\mu^1,\mu^2)=\,&-\tau \nabla \nu(\mu^1)+R_2^\top \sigma_\tau(R_2\mu^1),\\ \nabla_2V_R(\mu^1,\mu^2)=\,&-\tau \nabla \nu(\mu^2)+R_1^\top \sigma_\tau(R_1\mu^2). \end{align}\] By the optimality condition of the softmax operator, we have \[\begin{align} \left\langle R_1\mu^2+\tau \nabla \nu(\sigma_\tau(R_1\mu^2)), \sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2) \right\rangle = 0. \end{align}\] Therefore, \[\begin{align} \langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\rangle =\,& \tau\langle \nabla \nu(\sigma_\tau(R_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2) \rangle\\ &+(\sigma_\tau(R_2 \mu^1)-\mu^2)^\top R_2 (\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)). \end{align}\] By the Cauchy–Schwarz inequality, we obtain \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\rangle\\ \leq\,& \left( \tau\|\nabla \nu(\sigma_\tau(R_1 \mu^2))- \nabla \nu(\mu^1)\|_2 +\|\sigma_\tau(R_2 \mu^1)-\mu^2\|_2 \|R_2\|_2 \right)\|\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\|_2 . \end{align}\] Since \((\mu^1,\mu^2)\in\Pi_{\tau,\Bar{\epsilon}}\), Lemma 14 implies \[\begin{align} &\langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\rangle\\ \leq\,& \left( \frac{\tau}{\ell_{\tau,\Bar{\epsilon}}} \|\sigma_\tau(R_1 \mu^2)- \mu^1\|_2 +\|\sigma_\tau(R_2 \mu^1)-\mu^2\|_2 \|R_2\|_2 \right)\|\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\|_2 . \end{align}\] Since \(\|\sigma_\tau(R_1 \mu^2)- \mu^1\|_2 +\|\sigma_\tau(R_2 \mu^1)-\mu^2\|_2 \leq 2\), we obtain \[\begin{align} \langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\rangle \leq 2\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}} +\|R_2\|_2\right) \|\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\|_2 . \end{align}\] Moreover, by Lemma 21 and the \(1/\tau\)-Lipschitz continuity of \(\sigma_\tau(\cdot)\), \[\begin{align} \|\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\|_2 \leq\,& \|\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(q^1)\|_2 +\|\sigma_\tau(q^1)-\sigma_\tau(R_1\mu^2)\|_2\\ \leq\,& 2\Bar{\epsilon} +\frac{1}{\tau}\|q^1-R_1\mu^2\|_2 . \end{align}\] Combining the previous two bounds yields \[\begin{align} \langle \nabla_1V_R(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(R_1\mu^2)\rangle \leq\,& 2\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}} +\|R_2\|_2\right) \left( 2\Bar{\epsilon} +\frac{1}{\tau}\|q^1-R_1\mu^2\|_2 \right)\\ =\,& 4\Bar{\epsilon} \left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}} +\|R_2\|_2\right) +\frac{2}{\tau} \left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}} +\|R_2\|_2\right) \|q^1-R_1\mu^2\|_2\\ \leq\,& 4\Bar{\epsilon} \left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}} +m\right) +\frac{2}{\tau} \left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}} +m\right) \|q^1-R_1\mu^2\|_2, \end{align}\] where the last line follows from \(\|R_2\|_2\leq m\). Similarly, we have \[\begin{align} \langle \nabla_2V_R(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^2)-\sigma_\tau(R_2\mu^1)\rangle \leq\,& 4\Bar{\epsilon}\left(\frac{\tau }{\ell_{\tau,\Bar{\epsilon}}}+ m\right) +\frac{2}{\tau}\left(\frac{\tau}{\ell_{\tau,\Bar{\epsilon}}}+ m\right) \| q^2-R_2\mu^1\|_2. \end{align}\] The claim follows from adding the previous two inequalities. 0◻

Given \(i\in \{1,2\}\), for any \(q^i\in\mathbb{R}^{m_i}\), we have \[\begin{align} \|\sigma_\tau^{\bar{\epsilon}}(q^i)-\sigma_\tau(q^i)\|_2^2 = \Bar{\epsilon}^2 \sum_{a^i\in\mathcal{A}^i} \left(\frac{1}{m_i}-\sigma_\tau(q^i)(a^i)\right)^2 \leq 4\Bar{\epsilon}^2, \end{align}\] where the inequality follows because both \(\text{Unif}(\mathcal{A}^i)\) and \(\sigma_\tau(q^i)\) are probability vectors. It follows that \(\|\sigma_\tau^{\bar{\epsilon}}(q^i)-\sigma_\tau(q^i)\|_2\leq 2\Bar{\epsilon}\). 0◻

8 Details for the Proof of Theorem 3↩︎

We begin with a summary of notation.

8.1 Notation↩︎

(1) Given a pair of matrices \(\{X_i\in\mathbb{R}^{m_i\times m_{-i}}\}_{i\in \{1,2\}}\) and a pair of distributions \(\{\mu^i\in\Delta(\mathcal{A}^i)\}_{i\in \{1,2\}}\), we define \[\begin{align} \label{def:Nash95Gap} V_{X}(\mu^1,\mu^2) = \sum_{i=1,2} \max_{\hat{\mu}^i\in\Delta(\mathcal{A}^i)} \left\{ (\hat{\mu}^i-\mu^i)^\top X_i\mu^{-i} +\tau \nu(\hat{\mu}^i)-\tau\nu(\mu^i) \right\}, \end{align}\tag{26}\] where \(\nu(\cdot)\) is the entropy function. Note that \(V_X(\cdot,\cdot)\) is similar to \(V_R(\cdot,\cdot)\) defined in Appendix 6.2 for matrix games. However, we do not assume that \(X_1+X_2^\top =0\).

(2) Given a pair of value functions \(v=(v^1,v^2)\) and a state \(s\in\mathcal{S}\), when \(X_i=\mathcal{T}^i(v^i)(s)\) for \(i\in \{1,2\}\), we write \(V_{v,s}(\cdot,\cdot)\) for \(V_X(\cdot,\cdot)\).

(3) For any joint policy \((\pi^1,\pi^2)\) and state \(s\), given \(i\in \{1,2\}\), we define \(v^i_{*,\pi^{-i}}(s)=\max_{\hat{\pi}^i}v^i_{\hat{\pi}^i,\pi^{-i}}(s)\), \(v^i_{\pi^i,*}(s)=\min_{\hat{\pi}^{-i}}v^i_{\pi^i,\hat{\pi}^{-i}}(s)\), \(v^{-i}_{\pi^{-i},*}(s)=\min_{\hat{\pi}^i}v^{-i}_{\pi^{-i},\hat{\pi}^i}(s)\), and \(v^{-i}_{*,\pi^i}(s)=\max_{\hat{\pi}^{-i}}v^{-i}_{\hat{\pi}^{-i},\pi^i}(s)\). Note that \(v^1_{*,\pi^2}+v^2_{\pi^2,*}=0\) and \(v^1_{\pi^1,*}+v^2_{*,\pi^1}=0\) because of the zero-sum structure.

(4) For \(i\in \{1,2\}\), denote by \(v_*^i\) the unique fixed point of the equation \(\mathcal{B}^i(v^i)=v^i\), where \(\mathcal{B}^i(\cdot)\) is the minimax Bellman operator defined in Section 3.1. Note that \(v_*^1+v_*^2=0\).

(5) For any \(t,k\geq 0\) and \(i\in \{1,2\}\), let \(\Bar{q}_{t,k}^i\in\mathbb{R}^{nm_i}\) be defined as \(\Bar{q}_{t,k}^i(s)=\mathcal{T}^i(v_t^i)(s)\pi_{t,k}^{-i}(s)\) for all \(s\in\mathcal{S}\). In addition, let \[\begin{align} \mathcal{L}_{\text{sum}}(t) =\,& \|v_t^1+v_t^2\|_\infty,\quad \mathcal{L}_v(t) = \sum_{i=1,2}\|v_t^i-v_*^i\|_\infty,\\ \mathcal{L}_q(t,k) =\,& \sum_{i=1,2}\sum_{s\in\mathcal{S}} \|q_{t,k}^i(s)-\mathcal{T}^i(v_t^i)(s)\pi_{t,k}^{-i}(s)\|_2^2 = \sum_{i=1,2}\|q_{t,k}^i-\Bar{q}_{t,k}^i\|_2^2,\\ \mathcal{L}_\pi(t,k) =\,& \max_{s\in\mathcal{S}} V_{v_t,s}(\pi_{t,k}^1(s),\pi_{t,k}^2(s)). \end{align}\] These will be the Lyapunov functions used in the analysis.

(6) Given \(k_1\leq k_2\), we denote \(\beta_{k_1,k_2}=\sum_{k=k_1}^{k_2}\beta_k\) and \(\alpha_{k_1,k_2}=\sum_{k=k_1}^{k_2}\alpha_k\).

8.2 Proof of Lemma 2↩︎

Let \(i\in \{1,2\}\). The proof uses induction arguments.

(1) Fixing \(t\geq 0\), we first show by induction that, if \(\|v_t^i\|_\infty\leq \frac{1}{1-\gamma}\) and \(\|q_{t,0}^i\|_\infty\leq \frac{1}{1-\gamma}\), then \(\|q_{t,k}^i\|_\infty\leq \frac{1}{1-\gamma}\) for all \(k\geq 0\). The base case holds by the assumption \(\|q_{t,0}^i\|_\infty\leq \frac{1}{1-\gamma}\). Suppose that \(\|q_{t,k}^i\|_\infty\leq \frac{1}{1-\gamma}\) for some \(k\geq 0\). Then, by Algorithm 3, Line 6, we have for all \((s,a^i)\) that \[\begin{align} |q_{t,k+1}^i(s,a^i)| =\,& |q_{t,k}^i(s,a^i)+\alpha_k\mathbb{1}_{\{(s,a^i)=(S_k,A_k^i)\}} (R_i(S_k,A_k^i,A_k^{-i})+\gamma v_t^i(S_{k+1})-q_{t,k}^i(S_k,A_k^i))|\nonumber\\ \leq \,& (1-\alpha_k\mathbb{1}_{\{(s,a^i)=(S_k,A_k^i)\}})|q_{t,k}^i(s,a^i)|\nonumber\\ &+ \alpha_k\mathbb{1}_{\{(s,a^i)=(S_k,A_k^i)\}} |R_i(S_k,A_k^i,A_k^{-i})+\gamma v_t^i(S_{k+1})|\nonumber\\ \leq \,& (1-\alpha_k\mathbb{1}_{\{(s,a^i)=(S_k,A_k^i)\}})\frac{1}{1-\gamma} +\alpha_k\mathbb{1}_{\{(s,a^i)=(S_k,A_k^i)\}} \left(1+\frac{\gamma}{1-\gamma}\right)\label{eq:boundedness1}\\ = \,& \frac{1}{1-\gamma},\nonumber \end{align}\tag{27}\] where 27 follows from the induction hypothesis, the assumption \(\|v_t^i\|_\infty\leq \frac{1}{1-\gamma}\), the bound \(\max_{s,a^i,a^{-i}}|R_i(s,a^i,a^{-i})|\leq 1\), and the stepsize condition \(\alpha_k\in[0,1]\). The induction is complete, and hence \(\|q_{t,k}^i\|_\infty\leq \frac{1}{1-\gamma}\) for all \(k\geq 0\) whenever \(\|v_t^i\|_\infty\leq \frac{1}{1-\gamma}\) and \(\|q_{t,0}^i\|_\infty\leq \frac{1}{1-\gamma}\).

We next use induction to show that
$\|v_t^i\|_\infty\leq \frac{1}{1-\gamma}$ and
$\|q_{t,0}^i\|_\infty\leq \frac{1}{1-\gamma}$ for all $t\geq 0$. The
initialization ensures that
$\|v_0^i\|_\infty\leq \frac{1}{1-\gamma}$ and
$\|q_{0,0}^i\|_\infty\leq \frac{1}{1-\gamma}$. Suppose that
$\|v_t^i\|_\infty\leq \frac{1}{1-\gamma}$ and
$\|q_{t,0}^i\|_\infty\leq \frac{1}{1-\gamma}$ for some $t\geq 0$.
Using the update equation for $v_{t+1}^i$ in
Algorithm [-@fig:algo:stochastic95game], Line 8, and the fact that
$\|q_{t,k}^i\|_\infty\leq \frac{1}{1-\gamma}$ for all $k\geq 0$, we
have for all $s\in\mathcal{S}$ that
$$\begin{align} |v_{t+1}^i(s)| = \left|\sum_{a^i\in\mathcal{A}^i}\pi^i_{t,K}(a^i|s)q_{t,K}^i(s,a^i)\right| \leq \sum_{a^i\in\mathcal{A}^i}\pi^i_{t,K}(a^i|s)\|q_{t,K}^i\|_\infty \leq \frac{1}{1-\gamma}.
\end{align}$$ Thus, $\|v_{t+1}^i\|_\infty\leq \frac{1}{1-\gamma}$.
Moreover, Algorithm [-@fig:algo:stochastic95game], Line 9, gives
$\|q_{t+1,0}^i\|_\infty=\|q_{t,K}^i\|_\infty\leq \frac{1}{1-\gamma}$.
The induction is complete, and hence
$\|v_t^i\|_\infty\leq \frac{1}{1-\gamma}$ and
$\|q_{t,0}^i\|_\infty\leq \frac{1}{1-\gamma}$ for all $t\geq 0$.

(2) We first use induction to show that, given \(t\geq 0\), if \(\min_{s,a^i}\pi_{t,0}^i(a^i\mid s)\geq \ell_\tau\), then \(\min_{s,a^i}\pi_{t,k}^i(a^i\mid s)\geq \ell_\tau\) for all \(k\in \{0,1,\cdots,K\}\). The base case holds by the assumption. Suppose that \(\min_{s\in\mathcal{S},a^i\in\mathcal{A}^i}\pi_{t,k}^i(a^i\mid s)\geq \ell_\tau\) for some \(k\geq 0\). Then, by Algorithm 3, Line 4, we have \[\begin{align} \pi_{t,k+1}^i(a^i\mid s) =\,& (1-\beta_k)\pi_{t,k}^i(a^i\mid s)+\beta_k\sigma_\tau(q_{t,k}^i(s))(a^i)\\ \geq\,& (1-\beta_k) \ell_\tau+\beta_k\ell_\tau\\ =\,& \ell_\tau, \end{align}\] where the inequality follows from the induction hypothesis, Part (1), Lemma 13, and the stepsize condition \(\beta_k\in[0,1]\). The induction is complete.

We next use induction to show that
$\min_{s,a^i}\pi_{t,0}^i(a^i\mid s)\geq \ell_\tau$ for all
$t\in \{0,1,\cdots,T\}$. Since $\pi_{0,0}^i$ is initialized as a
uniform policy, the base case holds. Suppose that
$\min_{s,a^i}\pi_{t,0}^i(a^i\mid s)\geq \ell_\tau$ for some
$t\geq 0$. Then $\min_{s,a^i}\pi_{t,k}^i(a^i\mid s)\geq \ell_\tau$
for all $k\in \{0,1,\cdots,K\}$. Since $\pi_{t+1,0}^i=\pi_{t,K}^i$
by Algorithm [-@fig:algo:stochastic95game], Line 9, we have
$\min_{s,a^i}\pi_{t+1,0}^i(a^i\mid s)\geq \ell_\tau$. The induction
is complete.

0◻

8.3 Proof of Lemma 1↩︎

Our ultimate goal is to bound the Nash gap \[\begin{align} \label{explicit95Nash} \text{NG}(\pi_{T,K}^1,\pi_{T,K}^2)=\sum_{i=1,2}\left(\max_{\pi^i}U^i(\pi^i,\pi_{T,K}^{-i})-U^i(\pi_{T,K}^i,\pi_{T,K}^{-i})\right) \end{align}\tag{28}\] as a function of the Lyapunov functions. We first bound the Nash gap using the value functions of the output policies from Algorithm 3.

Using the definition of the utility function, we have \[\begin{align} \sum_{i=1,2}\left(\max_{\pi^i}U^i(\pi^i,\pi_{T,K}^{-i})-U^i(\pi_{T,K}^i,\pi_{T,K}^{-i})\right) = \,& \sum_{i=1,2}\left(\max_{\pi^i}\mathbb{E}_{S\sim p_o}\left[v^i_{\pi^i,\pi_{T,K}^{-i}}(S)-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}(S)\right]\right)\\ \leq \,& \sum_{i=1,2}\mathbb{E}_{S\sim p_o}\left[\max_{\pi^i}v^i_{\pi^i,\pi_{T,K}^{-i}}(S)-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}(S)\right]\\ = \,& \sum_{i=1,2}\mathbb{E}_{S\sim p_o}\left[v^i_{*,\pi_{T,K}^{-i}}(S)-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}(S)\right]\\ \leq \,& \sum_{i=1,2}\left\|v^i_{*,\pi_{T,K}^{-i}}-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}\right\|_\infty. \end{align}\] 0◻

The next lemma bounds the right-hand side of (?? ) using the iterates from Algorithm 3.

For any \(s\in\mathcal{S}\) and \(i\in \{1,2\}\), we have \[\begin{align} 0 \leq \,& \left|v^i_{*,\pi_{T,K}^{-i}}(s)-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}(s)\right|\\ =\,& v^i_{*,\pi_{T,K}^{-i}}(s)-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}(s)\\ \leq \,& v^i_{*,\pi_{T,K}^{-i}}(s)-v^i_{\pi_{T,K}^i,*}(s)\\ =\,& -v^{-i}_{\pi_{T,K}^{-i},*}(s)-v^i_{\pi_{T,K}^i,*}(s)\\ =\,& v^i_*(s)-v^{-i}_{\pi_{T,K}^{-i},*}(s) + v^{-i}_*(s)-v^i_{\pi_{T,K}^i,*}(s)\\ \leq \,& \sum_{j=1,2}\left\|v^{-j}_*-v^{-j}_{\pi_{T,K}^{-j},*}\right\|_\infty. \end{align}\] Since the right-hand side does not depend on \(s\), we have, for \(i\in \{1,2\}\), \[\begin{align} \left\|v^i_{*,\pi_{T,K}^{-i}}-v^i_{\pi_{T,K}^i,\pi_{T,K}^{-i}}\right\|_\infty \leq \sum_{j=1,2}\left\|v^{-j}_*-v^{-j}_{\pi_{T,K}^{-j},*}\right\|_\infty. \label{eq:last95policy95bound} \end{align}\tag{29}\] It remains to bound the right-hand side of 29 . For any \(s\in\mathcal{S}\) and \(i\in \{1,2\}\), we have \[\begin{align} 0 \leq\,& v^{-i}_*(s)-v^{-i}_{\pi_{T,K}^{-i},*}(s)\nonumber\\ =\,& v^i_{*,\pi_{T,K}^{-i}}(s)-v^i_*(s)\nonumber\\ =\,& \max_{\mu^i\in\Delta(\mathcal{A}^i)} (\mu^i)^\top \mathcal{T}^i(v^i_{*,\pi_{T,K}^{-i}})(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i\in\Delta(\mathcal{A}^i)} \min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})} (\mu^i)^\top \mathcal{T}^i(v_*^i)(s)\mu^{-i}\nonumber\\ \leq \,& \left| \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_{*,\pi_{T,K}^{-i}})(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_{*})(s)\pi_{T,K}^{-i}(s) \right|\nonumber\\ &+ \left| \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_{*})(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\pi_{T,K}^{-i}(s) \right|\nonumber\\ &+ \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\mu^{-i}\nonumber\\ &+ \left| \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\mu^{-i} - \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v_*^i)(s)\mu^{-i} \right|. \label{eq:connect1} \end{align}\tag{30}\] We next bound the four terms on the right-hand side of 30 .

For the first term, using the definition of \(\mathcal{T}^i(\cdot)\), we have \[\begin{align} &\left| \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_{*,\pi_{T,K}^{-i}})(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_{*})(s)\pi_{T,K}^{-i}(s) \right|\\ \leq\,& \max_{\mu^i} \left| (\mu^i)^\top \left(\mathcal{T}^i(v^i_{*,\pi_{T,K}^{-i}})(s)-\mathcal{T}^i(v^i_{*})(s)\right) \pi_{T,K}^{-i}(s) \right|\\ \leq\,& \gamma \left\|v^i_{*}-v^i_{*,\pi_{T,K}^{-i}}\right\|_\infty. \end{align}\] Similarly, the second term is bounded by \[\begin{align} \left| \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_{*})(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\pi_{T,K}^{-i}(s) \right| \leq \gamma \left\|v^i_*-v^i_T\right\|_\infty. \end{align}\]

We next consider the third term. We decompose it as \[\begin{align} &\max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\mu^{-i}\nonumber\\ \leq\,& \left| \max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v_T^i)(s)\pi_{T,K}^{-i}(s) - \min_{\mu^{-i}} (\pi_{T,K}^i(s))^\top\mathcal{T}^i(v_T^i)(s)\mu^{-i} \right|\nonumber\\ \leq\,& \left| \max_{\mu^{-i}} (\mu^{-i})^\top \mathcal{T}^{-i}(v_T^{-i})(s)\pi_{T,K}^i(s) + \min_{\mu^{-i}} (\mu^{-i})^\top \mathcal{T}^i(v_T^i)(s)^\top \pi_{T,K}^i(s) \right|\nonumber\\ &+ \left| \sum_{j=1,2} \max_{\mu^j} (\mu^j)^\top \mathcal{T}^j(v_T^j)(s)\pi_{T,K}^{-j}(s) \right|. \label{eq95decompose:le:Nash95Gap} \end{align}\tag{31}\] For the first term on the right-hand side of 31 , we have \[\begin{align} &\left| \max_{\mu^{-i}} (\mu^{-i})^\top \mathcal{T}^{-i}(v_T^{-i})(s)\pi_{T,K}^i(s) + \min_{\mu^{-i}} (\mu^{-i})^\top \mathcal{T}^i(v_T^i)(s)^\top \pi_{T,K}^i(s) \right|\\ =\,& \left| \max_{\mu^{-i}} (\mu^{-i})^\top \mathcal{T}^{-i}(v_T^{-i})(s)\pi_{T,K}^i(s) - \max_{\mu^{-i}} (\mu^{-i})^\top [-\mathcal{T}^i(v_T^i)(s)]^\top \pi_{T,K}^i(s) \right|\\ \leq\,& \max_{\mu^{-i}} \left| (\mu^{-i})^\top \left(\mathcal{T}^{-i}(v_T^{-i})(s)+\mathcal{T}^i(v_T^i)(s)^\top\right) \pi_{T,K}^i(s) \right|\\ \leq\,& \gamma \left\|v_T^{-i}+v_T^i\right\|_\infty. \end{align}\] For the second term on the right-hand side of 31 , using the Lyapunov function \(V_{v_T,s}(\cdot,\cdot)\), we have \[\begin{align} \left| \sum_{j=1,2} \max_{\mu^j} (\mu^j)^\top \mathcal{T}^j(v_T^j)(s)\pi_{T,K}^{-j}(s) \right| =\,& \sum_{j=1,2} \max_{\mu^j} (\mu^j-\pi_{T,K}^j(s))^\top \mathcal{T}^j(v_T^j)(s)\pi_{T,K}^{-j}(s)\\ &+ \left| \sum_{j=1,2} (\pi_{T,K}^j(s))^\top \mathcal{T}^j(v_T^j)(s)\pi_{T,K}^{-j}(s) \right|\\ \leq\,& V_{v_T,s}(\pi_{T,K}^1(s),\pi_{T,K}^2(s)) +2\tau \log(m) + \gamma\|v_T^1+v_T^2\|_\infty. \end{align}\] Using the previous two bounds in 31 , we obtain \[\begin{align} &\max_{\mu^i} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\pi_{T,K}^{-i}(s) - \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\mu^{-i}\nonumber\\ \leq\,& V_{v_T,s}(\pi_{T,K}^1(s),\pi_{T,K}^2(s)) +2\gamma\|v_T^1+v_T^2\|_\infty +2\tau \log(m). \label{bound:3rd95Term} \end{align}\tag{32}\]

For the fourth term, using the definition of \(\mathcal{T}^i(\cdot)\) and the Lipschitz property of the matrix-game value, we have \[\begin{align} &\left| \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v^i_T)(s)\mu^{-i} - \max_{\mu^i} \min_{\mu^{-i}} (\mu^i)^\top \mathcal{T}^i(v_*^i)(s)\mu^{-i} \right|\\ \leq\,& \max_{a^i,a^{-i}} \left| \mathcal{T}^i(v^i_T)(s,a^i,a^{-i}) - \mathcal{T}^i(v_*^i)(s,a^i,a^{-i}) \right|\\ \leq\,& \gamma \|v_T^i-v_*^i\|_\infty. \end{align}\] Combining the bounds for the four terms in 30 , we obtain \[\begin{align} \left\|v^{-i}_*-v^{-i}_{\pi_{T,K}^{-i},*}\right\|_\infty \leq\,& \gamma\left\|v^i_{*,\pi_{T,K}^{-i}}-v^i_{*}\right\|_\infty +2\gamma\|v_T^1+v_T^2\|_\infty +2\gamma\|v^i_T-v^i_{*}\|_\infty\\ &+ \max_{s\in\mathcal{S}}V_{v_T,s}(\pi_{T,K}^1(s),\pi_{T,K}^2(s)) +2\tau \log(m)\\ \leq\,& \gamma\|v^{-i}_*-v^{-i}_{\pi_{T,K}^{-i},*}\|_\infty +2\mathcal{L}_{\text{sum}}(T) +2\|v^i_T-v^i_{*}\|_\infty+ \mathcal{L}_\pi(T,K) +2\tau \log(m). \end{align}\] Rearranging terms gives \[\begin{align} \left\|v^{-i}_*-v^{-i}_{\pi_{T,K}^{-i},*}\right\|_\infty \leq \frac{1}{1-\gamma} \left( 2\mathcal{L}_{\text{sum}}(T) +2\|v^i_T-v^i_{*}\|_\infty +\mathcal{L}_\pi(T,K) +2\tau \log(m) \right). \end{align}\] Summing both sides over \(i\in \{1,2\}\), we have \[\begin{align} \sum_{i=1,2} \left\|v^{-i}_*-v^{-i}_{\pi_{T,K}^{-i},*}\right\|_\infty \leq \frac{2}{1-\gamma} \left( 2\mathcal{L}_{\text{sum}}(T) +\mathcal{L}_v(T) +\mathcal{L}_\pi(T,K) +2\tau \log(m) \right). \end{align}\] Using the previous inequality in 29 , we obtain the desired result. 0◻ The proof of Lemma 1 follows by combining Lemmas 22 and 23 in 28 .

8.4 Analysis of the Outer Loop↩︎

8.4.1 Proof of Lemma 3↩︎

For \(i\in \{1,2\}\), using the outer-loop update equation in Algorithm 3, Line 8, and the fact that \(\mathcal{B}^i(v_*^i)=v_*^i\), we have for any \(t\geq 0\) and \(s\in\mathcal{S}\) that \[\begin{align} v_{t+1}^i(s)-v_*^i(s) =\,& \pi_{t,K}^i(s)^\top q_{t,K}^i(s)-v_*^i(s)\\ =\,& \mathcal{B}^i(v^i_t)(s)-\mathcal{B}^i(v_*^i)(s) +\pi_{t,K}^i(s)^\top q_{t,K}^i(s)-\mathcal{B}^i(v^i_t)(s). \end{align}\] Since the minimax Bellman operator \(\mathcal{B}^i(\cdot)\) is a \(\gamma\) – contraction mapping in \(\|\cdot\|_\infty\), we have \[\begin{align} \left|v_{t+1}^i(s)-v_*^i(s)\right| \leq\,& \gamma\left\|v^i_t-v_*^i\right\|_\infty + \left|\pi_{t,K}^i(s)^\top q_{t,K}^i(s)-\mathcal{B}^i(v^i_t)(s)\right|. \label{eq1:prop:outer} \end{align}\tag{33}\] It remains to bound the second term on the right-hand side of 33 . Using the definition of \(\mathcal{B}^i(\cdot)\), we have \[\begin{align} &\left|\pi_{t,K}^i(s)^\top q_{t,K}^i(s)-\mathcal{B}^i(v^i_t)(s)\right|\\ =\,& \left| \pi_{t,K}^i(s)^\top q_{t,K}^i(s) - \max_{\mu^i\in\Delta(\mathcal{A}^i)} \min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})} (\mu^i)^\top \mathcal{T}^i(v_t^i)(s)\mu^{-i} \right|\\ \leq \,& \left| \max_{\mu^i\in\Delta(\mathcal{A}^i)} (\mu^i)^\top \mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s) - \pi_{t,K}^i(s)^\top q_{t,K}^i(s) \right|\\ &+ \left| \max_{\mu^i\in\Delta(\mathcal{A}^i)} (\mu^i)^\top \mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s) - \max_{\mu^i\in\Delta(\mathcal{A}^i)} \min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})} (\mu^i)^\top \mathcal{T}^i(v_t^i)(s)\mu^{-i} \right|\\ \leq\,& \max_{\mu^i\in\Delta(\mathcal{A}^i)} (\mu^i-\pi_{t,K}^i(s))^\top \mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s)\\ &+ \left| (\pi_{t,K}^i(s))^\top \left(\mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s)-q_{t,K}^i(s)\right) \right|\\ &+ \left| \max_{\mu^i\in\Delta(\mathcal{A}^i)} (\mu^i)^\top \mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s) - \max_{\mu^i\in\Delta(\mathcal{A}^i)} \min_{\mu^{-i}\in\Delta(\mathcal{A}^{-i})} (\mu^i)^\top \mathcal{T}^i(v_t^i)(s)\mu^{-i} \right|\\ \leq\,& \left\|\mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s)-q_{t,K}^i(s)\right\|_\infty +2V_{v_t,s}(\pi_{t,K}^1(s),\pi_{t,K}^2(s))\\ &+ 2\gamma\|v_t^1+v_t^2\|_\infty +3\tau \log(m), \end{align}\] where the last line follows from the same argument as in 32 , with \(T\) replaced by \(t\). Using the previous inequality in 33 , we obtain \[\begin{align} \left\|v^i_{t+1}-v_*^i\right\|_\infty \leq\,& \gamma\left\|v^i_t-v_*^i\right\|_\infty + \max_{s\in\mathcal{S}} \left\|\mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s)-q_{t,K}^i(s)\right\|_\infty\\ &+ 2\max_{s\in\mathcal{S}}V_{v_t,s}(\pi_{t,K}^1(s),\pi_{t,K}^2(s)) +2\gamma\|v_t^1+v_t^2\|_\infty +3\tau \log(m). \end{align}\] Summing both sides over \(i\in \{1,2\}\) gives \[\begin{align} \mathcal{L}_v(t+1) \leq\,& \gamma \mathcal{L}_v(t) +4\mathcal{L}_{\text{sum}}(t) +4\mathcal{L}_\pi(t,K) +6\tau \log(m)\\ &+ \sum_{i=1,2} \max_{s\in\mathcal{S}} \left\|\mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s)-q_{t,K}^i(s)\right\|_\infty. \end{align}\] To bound the last term, observe that \[\begin{align} \sum_{i=1,2} \max_{s\in\mathcal{S}} \left\|\mathcal{T}^i(v^i_t)(s)\pi_{t,K}^{-i}(s)-q_{t,K}^i(s)\right\|_\infty =\,& \sum_{i=1,2}\left\|\Bar{q}_{t,K}^i-q_{t,K}^i\right\|_\infty\nonumber\\ \leq\,& \sum_{i=1,2}\left\|\Bar{q}_{t,K}^i-q_{t,K}^i\right\|_2\nonumber\\ \leq\,& \left( 2\sum_{i=1,2}\left\|\Bar{q}_{t,K}^i-q_{t,K}^i\right\|_2^2 \right)^{1/2}\nonumber\\ \leq\,& 2\mathcal{L}_q^{1/2}(t,K). \label{eq:Jensen} \end{align}\tag{34}\] Therefore, \[\begin{align} \mathcal{L}_v(t+1) \leq\,& \gamma \mathcal{L}_v(t) +4\mathcal{L}_{\text{sum}}(t) +2\mathcal{L}_q^{1/2}(t,K) +4\mathcal{L}_\pi(t,K) +6\tau \log(m). \end{align}\] This completes the proof. 0◻

8.4.2 Proof of Lemma 4↩︎

Using the outer-loop update equation in Algorithm 3, Line 8, we have for any \(t\geq 0\) and \(s\in\mathcal{S}\) that \[\begin{align} \left|v_{t+1}^1(s)+v_{t+1}^2(s)\right| =\,& \left|\sum_{i=1,2}\pi_{t,K}^i(s)^\top q_{t,K}^i(s)\right|\\ \leq \,& \left|\sum_{i=1,2}\pi_{t,K}^i(s)^\top (q_{t,K}^i(s)-\mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s))\right|\\ &+ \left| \sum_{i=1,2} (\pi_{t,K}^i(s))^\top \mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s) \right|\\ \leq \,& \sum_{i=1,2}\max_{s\in\mathcal{S}} \| q_{t,K}^i(s)-\mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s)\|_\infty\\ &+ \max_{(s,a^i,a^{-i})} \left| \mathcal{T}^i(v_t^i)(s,a^i,a^{-i}) + \mathcal{T}^{-i}(v_t^{-i})(s,a^i,a^{-i}) \right|\\ \leq \,& \sum_{i=1,2}\max_{s\in\mathcal{S}} \| q_{t,K}^i(s)-\mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s)\|_\infty +\gamma\|v_t^1+v_t^2\|_\infty, \end{align}\] where the last line follows from the definition of \(\mathcal{T}^i(\cdot)\). Since the right-hand side does not depend on \(s\), we have \[\begin{align} \|v_{t+1}^1+v_{t+1}^2\|_\infty \leq \gamma\|v_t^1+v_t^2\|_\infty + \sum_{i=1,2}\max_{s\in\mathcal{S}} \| q_{t,K}^i(s)-\mathcal{T}^i(v_t^i)(s)\pi_{t,K}^{-i}(s)\|_\infty. \end{align}\] The result follows from using 34 to bound the last term on the right-hand side and then using \(\mathcal{L}_{\text{sum}}(t)\) and \(\mathcal{L}_q(t,K)\) to simplify the notation. 0◻

8.5 Analysis of the Inner Loop↩︎

For ease of presentation, we write down only the inner loop of Algorithm 3 in Algorithm 5, where we omit the outer-loop index \(t\). Similarly, we write \(\mathcal{L}_q(k)\) for \(\mathcal{L}_q(t,k)\) and \(\mathcal{L}_\pi(k)\) for \(\mathcal{L}_\pi(t,k)\). All results derived for the \(q\)-functions and policies of Algorithm 5 can be combined with the outer-loop analysis of Algorithm 3 using a conditioning argument and the Markov property.

8.5.1 Proof of Lemma 5↩︎

To begin with, by Danskin’s theorem [64], we have \[\begin{align} \label{eq:V95gradient} \nabla_1V_X(\mu^1,\mu^2) =\,& -(X_1+X_2^\top )\mu^2 -\tau \nabla \nu(\mu^1) +X_2^\top \sigma_\tau(X_2\mu^1). \end{align}\tag{35}\] A similar result holds for \(\nabla_2V_X(\mu^1,\mu^2)\).

(1) It is clear that the function \(V_X(\cdot,\cdot)\) is non-negative. The strong convexity follows from the following two observations.

(i) The negative entropy $-\nu(\cdot)$ is $1$ -- strongly convex
    with respect to $\|\cdot\|_2$ [@beck2017first].

(ii) Given $i\in \{1,2\}$, the function
     $\max_{\hat{\mu}^{-i}\in\Delta(\mathcal{A}^{-i})}\{(\hat{\mu}^{-i})^\top X_{-i}\mu^i+\tau \nu(\hat{\mu}^{-i})\}$,
     as a function of $\mu^i$, is the maximum of linear functions in
     $\mu^i$, and therefore is convex.

It follows that, for any $i\in \{1,2\}$, the function
$V_X(\mu^1,\mu^2)$ is $\tau$ -- strongly convex in $\mu^i$ with
respect to $\|\cdot\|_2$, uniformly over $\mu^{-i}$.

(2) For any \((\mu^1,\mu^2),(\Bar{\mu}^1,\Bar{\mu}^2)\in\Pi_\tau\), we have by 35 that \[\begin{align} &\left\|\nabla_1V_X(\mu^1,\mu^2)-\nabla_1V_X(\Bar{\mu}^1,\Bar{\mu}^2)\right\|_2\nonumber\\ =\,& \left\| (X_1+X_2^\top)(\mu^2-\Bar{\mu}^2) +\tau(\nabla \nu(\mu^1)-\nabla \nu(\Bar{\mu}^1)) +X_2^\top(\sigma_\tau(X_2\Bar{\mu}^1)-\sigma_\tau(X_2\mu^1)) \right\|_2\nonumber\\ \leq\,& \|X_1+X_2^\top\|_2\|\mu^2-\Bar{\mu}^2\|_2 + \left(\frac{\tau}{\ell_\tau}+\frac{\|X_2\|_2^2}{\tau}\right) \left\|\Bar{\mu}^1-\mu^1\right\|_2, \label{eq:smoothness951nequality} \end{align}\tag{36}\] where 36 follows from Lemma 14 and the Lipschitz continuity of \(\sigma_\tau(\cdot)\) [63]. Similarly, \[\begin{align} \left\|\nabla_2V_X(\mu^1,\mu^2)-\nabla_2V_X(\Bar{\mu}^1,\Bar{\mu}^2)\right\|_2 \leq \|X_2+X_1^\top\|_2\|\mu^1-\Bar{\mu}^1\|_2 + \left(\frac{\tau}{\ell_\tau}+\frac{\|X_1\|_2^2}{\tau}\right) \left\|\Bar{\mu}^2-\mu^2\right\|_2. \end{align}\] Using the previous two inequalities, we have \[\begin{align} &\left\|\nabla V_X(\mu^1,\mu^2)-\nabla V_X(\Bar{\mu}^1,\Bar{\mu}^2)\right\|_2^2\\ \leq\,& \sum_{i=1,2} \left[ 2\left(\frac{\tau}{\ell_\tau}+\frac{\|X_{-i}\|_2^2}{\tau}\right)^2 \left\|\Bar{\mu}^i-\mu^i\right\|_2^2 + 2\|X_i+X_{-i}^\top\|_2^2 \|\mu^{-i}-\Bar{\mu}^{-i}\|_2^2 \right]\\ \leq\,& 2\left[ \left(\frac{\tau}{\ell_\tau} +\frac{\max(\|X_1\|_2^2,\|X_2\|_2^2)}{\tau}\right)^2 +\|X_1+X_2^\top\|_2^2 \right] \sum_{i=1,2}\|\Bar{\mu}^i-\mu^i\|_2^2. \end{align}\] Therefore, \(V_X(\cdot,\cdot)\) is an \(\tilde{L}_\tau\) – smooth function on \(\Pi_\tau\) [62], where \[\begin{align} \tilde{L}_\tau = 2\left( \frac{\tau}{\ell_\tau} +\frac{\max(\|X_1\|_2^2,\|X_2\|_2^2)}{\tau} +\|X_1+X_2^\top\|_2 \right). \end{align}\]

(3) By the optimality condition of the softmax map, we have \[\begin{align} \left\langle X_1\mu^2+\tau\nabla\nu(\sigma_\tau(X_1\mu^2)), \sigma_\tau(X_1\mu^2)-\mu^1 \right\rangle = 0. \end{align}\] Using 35 , we have \[\begin{align} \langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau(X_1\mu^2)-\mu^1 \rangle =\,& \tau\langle \nabla \nu(\sigma_\tau(X_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau(X_1\mu^2)-\mu^1 \rangle\\ &+ ( \sigma_\tau(X_2 \mu^1)-\mu^2)^\top X_2( \sigma_\tau(X_1\mu^2)-\mu^1 ). \end{align}\] By the concavity of \(\nu(\cdot)\) and the same optimality condition, \[\begin{align} &\langle \nabla \nu(\sigma_\tau(X_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau(X_1\mu^2)-\mu^1 \rangle\\ \leq\,& \frac{1}{\tau} \left[ (\mu^1)^\top X_1 \mu^2+\tau \nu(\mu^1) - \max_{\hat{\mu}^1\in\Delta(\mathcal{A}^1)} \left\{ (\hat{\mu}^1)^\top X_1\mu^2+\tau \nu(\hat{\mu}^1) \right\} \right]. \end{align}\] Therefore, \[\begin{align} \langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau(X_1\mu^2)-\mu^1 \rangle \leq\,& (\mu^1)^\top X_1 \mu^2+\tau \nu(\mu^1) - \max_{\hat{\mu}^1\in\Delta(\mathcal{A}^1)} \left\{ (\hat{\mu}^1)^\top X_1\mu^2+\tau \nu(\hat{\mu}^1) \right\}\\ &+ ( \sigma_\tau(X_2 \mu^1)-\mu^2)^\top X_2( \sigma_\tau(X_1\mu^2)-\mu^1 ). \end{align}\] Similarly, \[\begin{align} \langle \nabla_2V_X(\mu^1,\mu^2),\sigma_\tau(X_2\mu^1)-\mu^2 \rangle \leq\,& (\mu^2)^\top X_2 \mu^1+\tau \nu(\mu^2) - \max_{\hat{\mu}^2\in\Delta(\mathcal{A}^2)} \left\{ (\hat{\mu}^2)^\top X_2\mu^1+\tau \nu(\hat{\mu}^2) \right\}\\ &+ ( \sigma_\tau(X_1 \mu^2)-\mu^1)^\top X_1( \sigma_\tau(X_2\mu^1)-\mu^2 ). \end{align}\] Adding the previous two inequalities gives \[\begin{align} &\langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau(X_1\mu^2)-\mu^1 \rangle + \langle \nabla_2V_X(\mu^1,\mu^2),\sigma_\tau(X_2\mu^1)-\mu^2 \rangle\nonumber\\ \leq\,& -V_X(\mu^1,\mu^2) + ( \sigma_\tau(X_1 \mu^2)-\mu^1)^\top (X_1+X_2^\top) ( \sigma_\tau(X_2\mu^1)-\mu^2 )\nonumber\\ \leq\,& -V_X(\mu^1,\mu^2) + 2\| \sigma_\tau(X_1 \mu^2)-\mu^1\|_2 \|X_1+X_2^\top \|_2, \label{eq:gradient95V951} \end{align}\tag{37}\] where the last line follows from \(\| \sigma_\tau(X_2\mu^1)-\mu^2 \|_2\leq \| \sigma_\tau(X_2\mu^1)\|_1+\|\mu^2 \|_1\leq 2\). Using Part (1) together with the quadratic growth property of strongly convex functions, we have \[\begin{align} \| \sigma_\tau(X_1 \mu^2)-\mu^1\|_2 \leq \frac{\sqrt{2}}{\sqrt{\tau}}V_X(\mu^1,\mu^2)^{1/2}. \end{align}\] It follows from 37 that \[\begin{align} &\langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau(X_1\mu^2)-\mu^1 \rangle + \langle \nabla_2V_X(\mu^1,\mu^2),\sigma_\tau(X_2\mu^1)-\mu^2 \rangle\\ \leq\,& -V_X(\mu^1,\mu^2) + \frac{2\sqrt{2}}{\sqrt{\tau}} V_X(\mu^1,\mu^2)^{1/2}\|X_1+X_2^\top \|_2\\ \leq\,& -\frac{7}{8}V_X(\mu^1,\mu^2) + \frac{16}{\tau}\|X_1+X_2^\top \|_2^2. \end{align}\]

(4) For any \(u^1\in\mathbb{R}^{m_1}\), using 35 and the optimality condition of the softmax map in inner-product form, we have \[\begin{align} &\langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau(u^1)-\sigma_\tau(X_1\mu^2)\rangle\\ =\,& \tau\langle \nabla \nu(\sigma_\tau(X_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau(u^1)-\sigma_\tau(X_1\mu^2) \rangle\\ &+ ( \sigma_\tau(X_2 \mu^1)-\mu^2)^\top X_2( \sigma_\tau(u^1)-\sigma_\tau(X_1\mu^2) )\\ \leq\,& \left( \tau\|\nabla \nu(\sigma_\tau(X_1 \mu^2))- \nabla \nu(\mu^1)\|_2 +\|\sigma_\tau(X_2 \mu^1)-\mu^2\|_2 \|X_2\|_2 \right) \| \sigma_\tau(u^1)-\sigma_\tau(X_1\mu^2)\|_2\\ \leq\,& \left( \frac{\tau}{\ell_\tau}\|\sigma_\tau(X_1 \mu^2)- \mu^1\|_2 +\|\sigma_\tau(X_2 \mu^1)-\mu^2\|_2 \|X_2\|_2 \right) \frac{1}{\tau}\| u^1-X_1\mu^2\|_2\\ \leq\,& \frac{\sqrt{2}}{\sqrt{\tau}} \left(\frac{1}{\ell_\tau}+\frac{\|X_2\|_2}{\tau}\right) V_X(\mu^1,\mu^2)^{1/2} \| u^1-X_1\mu^2\|_2\\ \leq\,& \frac{1}{16}V_X(\mu^1,\mu^2) + \frac{8}{\tau} \left(\frac{1}{\ell_\tau}+\frac{\|X_2\|_2}{\tau}\right)^2 \| u^1-X_1\mu^2\|_2^2. \end{align}\] Similarly, for any \(u^2\in\mathbb{R}^{m_2}\), \[\begin{align} \langle \nabla_2V_X(\mu^1,\mu^2),\sigma_\tau(u^2)-\sigma_\tau(X_2\mu^1) \rangle \leq\,& \frac{1}{16}V_X(\mu^1,\mu^2) + \frac{8}{\tau} \left(\frac{1}{\ell_\tau}+\frac{\|X_1\|_2}{\tau}\right)^2 \| u^2-X_2\mu^1\|_2^2. \end{align}\] Adding the previous two inequalities gives \[\begin{align} &\langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau(u^1)-\sigma_\tau(X_1\mu^2)\rangle + \langle \nabla_2V_X(\mu^1,\mu^2),\sigma_\tau(u^2)-\sigma_\tau(X_2\mu^1) \rangle\\ \leq\,& \frac{1}{8}V_X(\mu^1,\mu^2) + \frac{8}{\tau} \left( \frac{1}{\ell_\tau} +\frac{\max(\|X_1\|_2,\|X_2\|_2)}{\tau} \right)^2 \sum_{i=1,2}\| u^i-X_i\mu^{-i}\|_2^2. \end{align}\]

0◻

8.5.2 Proof of Lemma 6↩︎

We will use \(V_{v,s}(\cdot,\cdot)\) (see Appendix 8.1) as the Lyapunov function to study the evolution of \((\pi_k^1(s),\pi_k^2(s))\). To begin with, we identify the smoothness parameter of \(V_{v,s}(\cdot,\cdot)\). Using Lemma 5 (1) and the definition of \(V_{v,s}(\cdot,\cdot)\), we have \[\begin{align} \tilde{L}_\tau =\,& 2\left(\frac{\tau}{\ell_\tau} +\frac{\max(\|X_1\|_2^2,\|X_2\|_2^2)}{\tau} +\|X_1+X_2^\top\|_2\right)\\ =\,& 2\left(\frac{\tau}{\ell_\tau} +\frac{\max(\|\mathcal{T}^1(v^1)(s)\|_2^2,\|\mathcal{T}^2(v^2)(s)\|_2^2)}{\tau} +\|\mathcal{T}^1(v^1)(s)+\mathcal{T}^2(v^2)(s)^\top\|_2\right)\\ \leq \,& 2\left(\frac{\tau}{\ell_\tau} +\frac{m^2}{\tau(1-\gamma)^2} +\frac{2m}{1-\gamma}\right) :=L_\tau, \end{align}\] where the inequality follows from \(|\mathcal{T}^i(v^i)(s,a^i,a^{-i})|\leq \frac{1}{1-\gamma}\) for all \((s,a^i,a^{-i})\) and \(i\in \{1,2\}\). Therefore, \(V_{v,s}(\cdot,\cdot)\) is an \(L_\tau\) – smooth function on \(\Pi_\tau\).

Using the smoothness of \(V_{v,s}(\cdot,\cdot)\), for any \(s\in\mathcal{S}\), we have by the policy update equation in Algorithm 5, Line 3, that \[\begin{align} &V_{v,s}(\pi_{k+1}^1(s),\pi_{k+1}^2(s))\\ \leq \,& V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\beta_k\langle \nabla_2V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau(q_k^2(s))-\pi_k^2(s) \rangle\\ &+\beta_k\langle \nabla_1V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau(q_k^1(s))-\pi_k^1(s) \rangle +\frac{L_\tau\beta_k^2}{2}\sum_{i=1,2}\|\sigma_\tau(q_k^i(s))-\pi_k^i(s)\|_2^2\\ \leq \,& V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\beta_k\langle \nabla_2V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau(\mathcal{T}^2(v^2)(s)\pi_k^1(s))-\pi_k^2(s) \rangle\\ &+\beta_k\langle \nabla_1 V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau(\mathcal{T}^1(v^1)(s)\pi_k^2(s))-\pi_k^1(s) \rangle\\ &+\beta_k\langle \nabla_2V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau(q_k^2(s))-\sigma_\tau(\mathcal{T}^2(v^2)(s)\pi_k^1(s)) \rangle\\ &+\beta_k\langle \nabla_1 V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau(q_k^1(s))-\sigma_\tau(\mathcal{T}^1(v^1)(s)\pi_k^2(s)) \rangle +2L_\tau\beta_k^2\\ \leq \,& \left(1-\frac{3\beta_k}{4}\right)V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\frac{16\beta_k}{\tau}\|\mathcal{T}^1(v^1)(s)+\mathcal{T}^2(v^2)(s)^\top \|_2^2\\ &+\frac{8\beta_k}{\tau} \left(\frac{1}{\ell_\tau} +\frac{\max_{i\in \{1,2\}}\|\mathcal{T}^i(v^i)(s)\|_2}{\tau}\right)^2 \sum_{i=1,2}\| q_k^i(s)-\mathcal{T}^i(v^i)(s)\pi_k^{-i}(s)\|_2^2 +2L_\tau\beta_k^2, \end{align}\] where the last line follows from Lemma 5 (3) and (4).

Since \(\max_{i\in \{1,2\}}\|\mathcal{T}^i(v^i)(s)\|_2 \leq \frac{m}{1-\gamma}\) and \[\begin{align} \|\mathcal{T}^1(v^1)(s)+\mathcal{T}^2(v^2)(s)^\top \|_2^2 \leq m^2\|v^1+v^2\|_\infty^2, \end{align}\] we have \[\begin{align} &V_{v,s}(\pi_{k+1}^1(s),\pi_{k+1}^2(s))\\ \leq \,& \left(1-\frac{3\beta_k}{4}\right)V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\frac{16\beta_k m^2}{\tau}\|v^1+v^2\|_\infty^2\\ &+\frac{8\beta_k}{\tau} \left(\frac{1}{\ell_\tau}+\frac{m}{\tau(1-\gamma)}\right)^2 \sum_{i=1,2}\| q_k^i(s)-\mathcal{T}^i(v^i)(s)\pi_k^{-i}(s)\|_2^2 +2L_\tau\beta_k^2\\ \leq \,& \left(1-\frac{3\beta_k}{4}\right) \max_{s\in\mathcal{S}}V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\frac{16\beta_k m^2}{\tau}\|v^1+v^2\|_\infty^2\\ &+\frac{8\beta_k}{\tau} \left(\frac{1}{\ell_\tau}+\frac{m}{\tau(1-\gamma)}\right)^2 \sum_{i=1,2}\sum_{s\in\mathcal{S}}\| q_k^i(s)-\mathcal{T}^i(v^i)(s)\pi_k^{-i}(s)\|_2^2 +2L_\tau\beta_k^2\\ =\,& \left(1-\frac{3\beta_k}{4}\right)\mathcal{L}_\pi(k) +\frac{16\beta_k m^2}{\tau}\|v^1+v^2\|_\infty^2\\ &+\frac{8\beta_k}{\tau} \left(\frac{1}{\ell_\tau}+\frac{m}{\tau(1-\gamma)}\right)^2 \mathcal{L}_q(k) +2L_\tau\beta_k^2. \end{align}\] Since the right-hand side does not depend on \(s\), we have \[\begin{align} \mathcal{L}_\pi(k+1) \leq \,& \left(1-\frac{3\beta_k}{4}\right)\mathcal{L}_\pi(k) +\frac{16\beta_k m^2}{\tau}\|v^1+v^2\|_\infty^2+\frac{8\beta_k}{\tau} \left(\frac{1}{\ell_\tau}+\frac{m}{\tau(1-\gamma)}\right)^2 \mathcal{L}_q(k) +2L_\tau\beta_k^2\\ \leq \,& \left(1-\frac{3\beta_k}{4}\right)\mathcal{L}_\pi(k) +\frac{16\beta_k m^2}{\tau}\|v^1+v^2\|_\infty^2+\frac{32m^2\beta_k}{\tau^3\ell_\tau^2(1-\gamma)^2}\mathcal{L}_q(k) +2L_\tau\beta_k^2, \end{align}\] where the last line follows from \(\tau\leq 1/(1-\gamma)\). 0◻

8.5.3 Proof of Lemma 8↩︎

(1) For any \((q_1^i,q_2^i)\) and \((s_0,a_0^i,a_0^{-i},s_1)\), we have \[\begin{align} &\|F^i(q_1^i,s_0,a_0^i,a_0^{-i},s_1)-F^i(q_2^i,s_0,a_0^i,a_0^{-i},s_1)\|_2^2\\ =\,& \sum_{(s,a^i)} \left( [F^i(q_1^i,s_0,a_0^i,a_0^{-i},s_1)](s,a^i) - [F^i(q_2^i,s_0,a_0^i,a_0^{-i},s_1)](s,a^i) \right)^2\\ =\,& \left(q_1^i(s_0,a_0^i)-q_2^i(s_0,a_0^i)\right)^2\\ \leq\,& \|q_1^i-q_2^i\|_2^2. \end{align}\]

(2) For any \((s_0,a_0^i,a_0^{-i},s_1)\), we have \[\begin{align} \|F^i(0,s_0,a_0^i,a_0^{-i},s_1)\|_2^2 =\,& \sum_{(s,a^i)} \left([F^i(0,s_0,a_0^i,a_0^{-i},s_1)](s,a^i)\right)^2\\ =\,& \left(R_i(s_0,a_0^i,a_0^{-i})+\gamma v^i(s_1)\right)^2\\ \leq\,& \frac{1}{(1-\gamma)^2}, \end{align}\] where the last line follows from \(\|v^i\|_\infty\leq 1/(1-\gamma)\) and \(|R_i(s_0,a_0^i,a_0^{-i})|\leq 1\).

(3) We first write the operator \(\Bar{F}_k^i(\cdot)\) explicitly. Using the definition of \(\mathcal{T}^i(\cdot)\), we have \[\begin{align} \Bar{F}_k^i(q^i)(s) = \mu_k(s)\text{diag}(\pi_k^i(s)) \left(\mathcal{T}^i(v^i)(s)\pi_k^{-i}(s)-q^i(s)\right), \quad \forall\,s\in\mathcal{S}. \end{align}\] Since \(\mu_k(s)\geq \mu_{\min}>0\) by Lemma 7 (4), and \(\text{diag}(\pi_k^i(s))\) has strictly positive diagonal entries by Lemma 2, the equation \(\Bar{F}_k^i(q^i)=0\) has a unique solution \(\Bar{q}_k^i\in\mathbb{R}^{nm_i}\), given by \[\begin{align} \Bar{q}_k^i(s) = \mathcal{T}^i(v^i)(s)\pi_k^{-i}(s), \quad \forall\,s\in\mathcal{S}. \end{align}\]

(4) Using the expression of \(\Bar{F}_k^i(\cdot)\), we have for any \(q_1^i,q_2^i\in\mathbb{R}^{nm_i}\) that \[\begin{align} (q_1^i-q_2^i)^\top (\Bar{F}_k^i(q_1^i)-\Bar{F}_k^i(q_2^i)) =\,& -\sum_{s,a^i} \mu_k(s)\pi_k^i(a^i|s) (q_1^i(s,a^i)-q_2^i(s,a^i))^2\\ \leq\,& -\min_{s,a^i}\mu_k(s)\pi_k^i(a^i|s) \|q_1^i-q_2^i\|_2^2\\ \leq\,& -\mu_{\min}\ell_\tau\|q_1^i-q_2^i\|_2^2and Lemma~\ref{le:exploration}}\\ =\,& -c_\tau\|q_1^i-q_2^i\|_2^2. \end{align}\]

This completes the proof. 0◻

8.5.4 Proof of Lemma 7↩︎

Let \(\Pi_{\det}\) denote the set of deterministic stationary policy pairs. Since the state and action spaces are finite, \(\Pi_{\det}\) is finite and \(\Pi\) is compact.

For each \(\pi\in\Pi_{\det}\), Assumption 1 implies that the transition matrix \(P_\pi\) of the induced Markov chain \(\{S_k\}\) is irreducible and aperiodic. Hence, there exists a positive integer \(r(\pi)\) such that \(P_\pi^r\) has strictly positive entries for all \(r\geq r(\pi)\); see, e.g., [65]. Define \(r_* := \max_{\pi\in\Pi_{\det}} r(\pi)\). Then \(P_\pi^{r_*}(s,s')>0\) for all \(\pi\in\Pi_{\det}\) and all \(s,s'\in\mathcal{S}\).

We next show that the same positivity holds uniformly over all stationary policy pairs. Fix any \(\pi\in\Pi\). For each state \(s\in\mathcal{S}\) and each player \(i\in\{1,2\}\), let \(a^i(s)\in\mathcal{A}^i\) be an action such that \(\pi^i(a^i(s)\mid s)>0\). Let \(d=(d^1,d^2)\) be the deterministic stationary policy pair defined by \(d^i(s)=a^i(s)\). Since \(d\in\Pi_{\det}\), we have \(P_{d}^{r_*}(s,s')>0\) for all \(s,s'\in\mathcal{S}\). Therefore, for any \(s,s'\in\mathcal{S}\), there exists at least one path \(s=s_0,s_1,\ldots,s_{r_*}=s'\) such that \[\begin{align} \prod_{\ell=0}^{r_*-1} P(s_{\ell+1}\mid s_\ell,d^1(s_\ell),d^2(s_\ell)) >0. \end{align}\] Along the same path, under the stationary policy pair \(\pi\), the probability of choosing the action pair \((d^1(s_\ell),d^2(s_\ell))\) at state \(s_\ell\) is positive for every \(\ell\). Hence \(P_\pi^{r_*}(s,s')>0\) for all \(s,s'\in\mathcal{S}\).

Since \(P_\pi^{r_*}(s,s')\) is continuous in \(\pi\) and \(\Pi\) is compact, we have \[\begin{align} \label{eq:uniform95positive95power} p_* := \inf_{\pi\in\Pi} \min_{s,s'\in\mathcal{S}} P_\pi^{r_*}(s,s')>0. \end{align}\tag{38}\] The constants \(r_*\) and \(p_*\) depend only on the transition kernel and the finite state-action spaces, and not on \(\ell_\tau\).

We now prove the four claims.

(1) Since 38 implies that, for every \(\pi\in\Pi\), the transition matrix \(P_\pi\) of the induced Markov chain \(\{S_k\}\) has a strictly positive power, \(P_\pi\) is irreducible and aperiodic [65]. Therefore, there exists a unique stationary distribution \(\mu_\pi\) for each \(\pi\in\Pi\).

(2) Fix \(\pi\in\Pi\). By 38 and the fact that \(\mu_\pi(s')\leq 1\) for every \(s'\in\mathcal{S}\), we have the minorization condition \[\begin{align} \label{eq:minorization95mu} P_\pi^{r_*}(s,s') \geq p_* \mu_\pi(s'), \quad \forall s,s'\in\mathcal{S}. \end{align}\tag{39}\] Equivalently, for every \(s\in\mathcal{S}\), \(P_\pi^{r_*} = p_* \mathbf{1}\mu_\pi^\top + (1-p_*)Q_\pi\), where \(\mathbf{1}\) is the all-ones vector and \(Q_\pi\) is a transition kernel. Now let \(\xi\) be such that \(\xi^\top \mathbf{1}=0\). Then, we have \[\begin{align} \label{eq:doeblin95contraction} \|\xi^\top P_\pi^{r_*}\|_1 = \|p_* \xi^\top \mathbf{1}\mu_\pi^\top + (1-p_*)\xi^\top Q_\pi\|_1 = (1-p_*)\|\xi^\top Q_\pi\|_1\leq (1-p_*)\|\xi\|_1. \end{align}\tag{40}\]

Let $k=qr_*+r$ with $q=\lfloor k/r_*\rfloor$ and $0\leq r<r_*$. For
any $s\in\mathcal{S}$, let $\xi_s:=\delta_s-\mu_\pi$, where
$\delta_s$ denotes the binary vector with its $s$-th entry being one
and zero everywhere else. Since $\mu_\pi^\top P_\pi=\mu_\pi^\top$,
we have
$$\begin{align} \|P_\pi^k(s,\cdot)-\mu_\pi(\cdot)\|_{\text{TV}} =\,&\frac{1}{2} \|\xi_s^\top (P_\pi^{r_*})^q P_\pi^r\|_1\\ \leq \,&\frac{1}{2}(1-p_*)^q\|\xi_s^\top P_\pi^r\|_1\\ \leq \,&\frac{1}{2}(1-p_*)^q\|\xi_s\|_1\\ \leq \,&(1-p_*)^q.
\end{align}$$ Define $\rho_*:=\exp(-p_*/(2r_*))\in(0,1).$ Using
$(1-p_*)^q\leq 2\rho_*^k$ for all $k\geq 0$, we obtain
$$\begin{align} \sup_{\pi\in \Pi} \max_{s\in\mathcal{S}} \|P_\pi^k(s,\cdot)-\mu_\pi(\cdot)\|_{\text{TV}} \leq 2\rho_*^k, \quad \forall\, k\geq 0.
\end{align}$$ Consequently,
$\sup_{\pi\in \Pi}\max_{s\in\mathcal{S}}\|P_\pi^k(s,\cdot)-\mu_\pi(\cdot)\|_{\text{TV}}\leq \eta$
holds whenever $2\rho_*^k\leq \eta$, that is,
$$\begin{align} k \geq \frac{\log(2/\eta)}{\log(1/\rho_*)}.
\end{align}$$

(3) Fix \(\pi=(\pi^1,\pi^2),\bar{\pi}=(\bar{\pi}^1,\bar{\pi}^2)\in\Pi\) and write \(P=P_\pi\), \(\bar P=P_{\bar{\pi}}\), \(\mu=\mu_\pi\), and \(\bar{\mu}=\mu_{\bar{\pi}}\). Define \[\begin{align} \Delta(\pi,\bar{\pi}) := \max_{s\in\mathcal{S}}\|\pi^1(s)-\bar{\pi}^1(s)\|_1 + \max_{s\in\mathcal{S}}\|\pi^2(s)-\bar{\pi}^2(s)\|_1. \end{align}\] For each \(s\in\mathcal{S}\), we have \[\begin{align} \|P(s,\cdot)-\bar P(s,\cdot)\|_1 \leq \|\pi^1(s)-\bar{\pi}^1(s)\|_1 + \|\pi^2(s)-\bar{\pi}^2(s)\|_1 \leq \Delta(\pi,\bar{\pi}). \end{align}\] Therefore, \[\begin{align} \label{eq:P95difference95bound} \max_{s\in\mathcal{S}}\|P(s,\cdot)-\bar P(s,\cdot)\|_1 \leq \Delta(\pi,\bar{\pi}). \end{align}\tag{41}\]

Let $x:= (P-\bar P)^\top \mu$. Since both $P$ and $\bar P$ are
transition matrices, $x^\top \mathbf{1}=0$. Moreover, by
@eq:eq:P95difference95bound , $$\begin{align}
\label{eq:x95bound} \|x\|_1 = \|\mu^\top (P-\bar P)\|_1 \leq \max_{s\in\mathcal{S}}\|P(s,\cdot)-\bar P(s,\cdot)\|_1 \leq \Delta(\pi,\bar{\pi}).
\end{align}$$ {#eq:eq:x95bound}  Since $\bar P$ is irreducible and
aperiodic by Part (1) of this lemma, we have
$\lim_{N\rightarrow\infty}\mu^\top \bar P^N\to\bar{\mu}^\top$
[@levin2017markov]. Hence
$$\begin{align} \mu-\bar{\mu} = \lim_{N\to\infty}\mu(I-\bar P^N) = \lim_{N\to\infty} \sum_{j=0}^{N-1}\mu(I-\bar P)\bar P^j.
\end{align}$$ Since $\mu^\top P=\mu^\top$, we have
$\mu^\top(I-\bar P)=\mu^\top(P-\bar P)=x$. Therefore,
$$\begin{align} \|\mu-\bar{\mu}\|_1 &\leq \sum_{j=0}^{\infty}\|x\bar P^j\|_1\\ &\leq \left(\sum_{j=0}^{\infty}(1-p_*)^{\lfloor j/r_*\rfloor}\right)\Delta(\pi,\bar{\pi}) and \eqref{eq:x95bound}}\\ &\leq \frac{r_*}{p_*}\Delta(\pi,\bar{\pi}).
\end{align}$$ Thus Part (3) holds with $L_p=r_*/p_*$, which is
independent of $\ell_\tau$.

(4) Finally, for any \(\pi\in\Pi\), using stationarity and 38 , we have for every \(s'\in\mathcal{S}\), \[\begin{align} \mu_\pi(s') = \sum_{s\in\mathcal{S}}\mu_\pi(s)P_\pi^{r_*}(s,s') \geq \sum_{s\in\mathcal{S}}\mu_\pi(s)p_* = p_*. \end{align}\] Taking the infimum over \(\pi\in\Pi\) and the minimum over \(s'\in\mathcal{S}\) gives \[\begin{align} \mu_{\min} = \inf_{\pi\in \Pi}\min_{s'\in\mathcal{S}}\mu_\pi(s') \geq p_* >0. \end{align}\]

8.5.5 Proof of Lemma 9↩︎

Using \(\|\cdot\|_2^2\) as a Lyapunov function, we have by the update equation 9 that \[\begin{align} \label{eq:q95Lyapunov95decomposition} \mathbb{E}[\|q_{k+1}^i-\bar{q}_{k+1}^i\|_2^2] =\,&\mathbb{E}[\|q_{k+1}^i-q_k^i+q_k^i-\bar{q}_k^i+\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]\nonumber\\ =\,&\mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\mathbb{E}[\|q_{k+1}^i-q_k^i\|_2^2] +\mathbb{E}[\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]\nonumber\\ &+2\alpha_k\mathbb{E}[(q_k^i-\bar{q}_k^i)^\top \bar{F}_k^i(q_k^i)]\nonumber\\ &+2\alpha_k\mathbb{E}[(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)]\nonumber\\ &+2\mathbb{E}[(\bar{q}_k^i-\bar{q}_{k+1}^i)^\top (q_{k+1}^i-q_k^i)]\nonumber\\ &+2\mathbb{E}[(q_k^i-\bar{q}_k^i)^\top (\bar{q}_k^i-\bar{q}_{k+1}^i)]\nonumber\\ \leq \,&(1-2\alpha_k c_\tau)\mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\mathbb{E}[\|q_{k+1}^i-q_k^i\|_2^2] +\mathbb{E}[\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]\nonumber\\ &+2\mathbb{E}[(\bar{q}_k^i-\bar{q}_{k+1}^i)^\top (q_{k+1}^i-q_k^i)]\nonumber\\ &+2\mathbb{E}[(q_k^i-\bar{q}_k^i)^\top (\bar{q}_k^i-\bar{q}_{k+1}^i)]\nonumber\\ &+2\alpha_k\mathbb{E}[(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)], \end{align}\tag{42}\] where the last line follows from Lemma 8 (4).

The terms \(\mathbb{E}[\|q_{k+1}^i-q_k^i\|_2^2]\), \(\mathbb{E}[\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]\), \(\mathbb{E}[(\bar{q}_k^i-\bar{q}_{k+1}^i)^\top (q_{k+1}^i-q_k^i)]\), and \(\mathbb{E}[(q_k^i-\bar{q}_k^i)^\top (\bar{q}_k^i-\bar{q}_{k+1}^i)]\) on the right-hand side of 42 are bounded in the following lemma, whose proof is presented in Appendix 8.7.1.

We next consider the last term on the right-hand side of 42 , which involves the difference between the operator \(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})\) and its expected version \(\bar{F}_k^i(q_k^i)\), and hence can be viewed as the stochastic error due to sampling. Since the sample at time \(k\) is generated using \(\pi_{k+1}\) while \(\bar{F}_k^i\) is defined using the stationary distribution and action distribution associated with \(\pi_k\), the term \(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i)\) contains both the Markovian sampling error and the one-step policy-shift error. Lemma 25 controls both effects using the slow variation of the policies and the Lipschitz sensitivity of the stationary distribution.

The fact that the Markov chain \(\{(S_k,A_k^i,A_k^{-i},S_{k+1})\}\) is time-inhomogeneous presents a challenge in our analysis. To overcome this challenge, observe that: (1) the policy, and hence the transition probability matrix of the induced Markov chain, is changing slowly compared to the \(q\)-function; see Algorithm 5, Line 3, and (2) the stationary distribution as a function of the policy is Lipschitz; see Lemma 7 (3). These two observations together enable us to develop a refined conditioning argument to handle the time-inhomogeneous Markovian noise. The result is presented in the following lemma, whose proof is presented in Appendix 8.7.2.

Using the upper bounds we obtained for all the terms on the right-hand side of 42 , we have the one-step Lyapunov drift inequality for \(q_k^i\). Specifically, for \(i\in \{1,2\}\), we have from 42 , Lemma 24, and Lemma 25 that \[\begin{align} \mathbb{E}[\|q_{k+1}^i-\bar{q}_{k+1}^i\|_2^2] \leq \,&(1-2\alpha_kc_\tau)\mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\frac{4nm}{(1-\gamma)^2}(\alpha_k^2+2\alpha_k\beta_k+\beta_k^2)\\ &+\frac{34nm^2\beta_k}{\tau(1-\gamma)^2}\mathbb{E}[\| q_k^i-\bar{q}_k^i\|_2^2] +\frac{\beta_k}{8}\mathbb{E}[\mathcal{L}_\pi(k)] +\frac{34z_k\alpha_k\alpha_{k-z_k,k-1}}{(1-\gamma)^2}\\ \leq \,&\left(1-2\alpha_kc_\tau+\frac{34nm^2\beta_k}{\tau(1-\gamma)^2}\right) \mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\frac{\beta_k}{8}\mathbb{E}[\mathcal{L}_\pi(k)]\\ &+\frac{50nm}{(1-\gamma)^2}z_k\alpha_k\alpha_{k-z_k,k-1}, \end{align}\] where the second inequality follows from \(\beta_k=c_{\alpha,\beta}\alpha_k\) with \(c_{\alpha,\beta}\leq 1\), the monotonicity of \(\{\alpha_k\}\), and \(z_k\geq 1\), which imply \(\alpha_k^2+2\alpha_k\beta_k+\beta_k^2 \leq 4\alpha_k^2 \leq 4z_k\alpha_k\alpha_{k-z_k,k-1}\). Since \[\begin{align} c_{\alpha,\beta}\leq \frac{c_\tau\tau(1-\gamma)^2}{34nm^2}, } \end{align}\] we have \[\begin{align} \mathbb{E}[\|q_{k+1}^i-\bar{q}_{k+1}^i\|_2^2] \leq \,& \left(1-\alpha_kc_\tau\right)\mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\frac{\beta_k}{8}\mathbb{E}[\mathcal{L}_\pi(k)] +\frac{50nm}{(1-\gamma)^2}z_k\alpha_k\alpha_{k-z_k,k-1}. \end{align}\] Summing the previous inequality over \(i=1,2\), we obtain \[\begin{align} \mathbb{E}[\mathcal{L}_q(k+1)] \leq\,& \left(1-\alpha_kc_\tau\right)\mathbb{E}[\mathcal{L}_q(k)] +\frac{\beta_k}{4}\mathbb{E}[\mathcal{L}_\pi(k)] +\frac{100nm}{(1-\gamma)^2}z_k\alpha_k\alpha_{k-z_k,k-1}. \end{align}\] This completes the proof. 0◻

8.6 Solving Coupled Lyapunov Drift Inequalities↩︎

We first restate the Lyapunov drift inequalities from previous sections. Recall our notation \(\mathcal{L}_q(t,k)=\sum_{i=1,2}\|q_{t,k}^i-\bar{q}_{t,k}^i\|_2^2\), \(\mathcal{L}_\pi(t,k)=\max_{s\in\mathcal{S}}V_{v_t,s}(\pi_{t,k}^1(s),\pi_{t,k}^2(s))\), \(\mathcal{L}_{\text{sum}}(t)=\|v_t^1+v_t^2\|_\infty\), and \(\mathcal{L}_v(t)=\sum_{i=1,2}\|v_t^i-v_*^i\|_\infty\). Let \(\mathcal{F}_t\) be the history of Algorithm 3 right before the \(t\)-th outer-loop iteration. Note that \(v_t^1\) and \(v_t^2\) are both measurable with respect to \(\mathcal{F}_t\). In what follows, for ease of presentation, we write \(\mathbb{E}_t[\cdot]\) for \(\mathbb{E}[\cdot\mid \mathcal{F}_t]\).

• Lemma 3: It holds for all \(t\geq 0\) that \[\begin{align} \label{eq:Lyapunov95v} \mathcal{L}_v(t+1) \leq\,& \gamma \mathcal{L}_v(t) +4\mathcal{L}_{\text{sum}}(t) +2\mathcal{L}_q^{1/2}(t,K) +4\mathcal{L}_\pi(t,K) +6\tau \log(m). \end{align}\tag{43}\]

• Lemma 4: It holds for all \(t\geq 0\) that \[\begin{align} \label{eq:Lyapunov95v43} \mathcal{L}_{\text{sum}}(t+1) \leq \gamma\mathcal{L}_{\text{sum}}(t) +2\mathcal{L}_q^{1/2}(t,K). \end{align}\tag{44}\]

• Lemma 6: It holds for all \(t,k\geq 0\) that \[\begin{align} \label{eq:Lyapunov95pi} \mathbb{E}_t[\mathcal{L}_\pi(t,k+1)] \leq\,& \left(1-\frac{3\beta_k}{4}\right)\mathbb{E}_t[\mathcal{L}_\pi(t,k)] +\frac{16m^2\beta_k}{\tau}\mathcal{L}_{\text{sum}}(t)^2\nonumber\\ &+ \frac{32m^2\beta_k}{\tau^3\ell_\tau^2(1-\gamma)^2} \mathbb{E}_t[\mathcal{L}_q(t,k)] +2L_\tau\beta_k^2. \end{align}\tag{45}\]

• Lemma 9: It holds for all \(t\geq 0\) and \(k\geq z_k\) that \[\begin{align} \label{eq:Lyapunov95q} \mathbb{E}_t[\mathcal{L}_q(t,k+1)] \leq\,& \left(1-\alpha_kc_\tau\right)\mathbb{E}_t[\mathcal{L}_q(t,k)] +\frac{\beta_k}{4}\mathbb{E}_t[\mathcal{L}_\pi(t,k)]\\ &+ \frac{100nm}{(1-\gamma)^2}z_k\alpha_k\alpha_{k-z_k,k-1}.\nonumber \end{align}\tag{46}\]

Adding 45 and 46 , and using \(c_{\alpha,\beta}\leq \min\{L_\tau^{-1/2},c_\tau \tau^3\ell_\tau^2(1-\gamma)^2/(128m^2),c_\tau\}\) from Condition 2, we obtain \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k+1)+\mathcal{L}_q(t,k+1)] \leq\,& \left(1-\frac{\beta_k}{2}\right) \mathbb{E}_t[\mathcal{L}_\pi(t,k)+\mathcal{L}_q(t,k)]\nonumber\\ &+ \frac{16m^2 \beta_k}{\tau}\mathcal{L}_{\text{sum}}(t)^2 +\frac{102nm}{(1-\gamma)^2}z_k\alpha_k\alpha_{k-z_k,k-1}. \label{eq:before95stepsize} \end{align}\tag{47}\]

8.6.1 Constant Stepsize↩︎

When using constant stepsizes, i.e., \(\alpha_k\equiv \alpha\) and \(\beta_k\equiv \beta=c_{\alpha,\beta}\alpha\), iterating 47 from \(z_\beta\) to \(k\) gives \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k)+\mathcal{L}_q(t,k)] \leq\,& \left(1-\frac{\beta}{2}\right)^{k-z_\beta} (\mathcal{L}_\pi(t,0)+\mathcal{L}_q(t,0))\nonumber\\ &+ \frac{32m^2}{\tau}\mathcal{L}_{\text{sum}}(t)^2 +\frac{204nm}{(1-\gamma)^2c_{\alpha,\beta}}z_\beta^2\alpha. \label{eq:polish1} \end{align}\tag{48}\] We next bound \(\mathcal{L}_\pi(t,0)+\mathcal{L}_q(t,0)\). For \(i\in \{1,2\}\), we have \[\begin{align} \mathcal{L}_\pi(t,0) =\,& \max_{s}V_{v_t,s}(\pi_{t,0}^1(s),\pi_{t,0}^2(s))\\ =\,& \max_{s} \sum_{i=1,2} \max_{\mu^i} \left\{ (\mu^i-\pi_{t,0}^i(s))^\top \mathcal{T}^i(v_t^i)(s)\pi_{t,0}^{-i}(s) +\tau \nu(\mu^i)-\tau\nu(\pi_{t,0}^i(s)) \right\}\\ \leq\,& 2\sum_{i=1,2}\max_{s,a^i,a^{-i}}|\mathcal{T}^i(v_t^i)(s,a^i,a^{-i})| +2\tau \log(m)\\ \leq\,& \frac{4}{1-\gamma}+2\tau \log(m), \end{align}\] and \[\begin{align} \mathcal{L}_q(t,0) = \sum_{i=1,2}\|q_{t,0}^i-\bar{q}_{t,0}^i\|_2^2 \leq \frac{8nm}{(1-\gamma)^2}. } \end{align}\] It follows that \[\begin{align} \mathcal{L}_\pi(t,0)+\mathcal{L}_q(t,0) \leq \frac{4}{1-\gamma}+2\tau \log(m)+\frac{8nm}{(1-\gamma)^2} = L_{\text{in}}. \end{align}\] Using this bound in 48 , we have \[\begin{align} \label{eq:cici} \mathbb{E}_t[\mathcal{L}_\pi(t,k)+\mathcal{L}_q(t,k)] \leq\,& L_{\text{in}}\left(1-\frac{\beta}{2}\right)^{k-z_\beta} +\frac{32m^2}{\tau}\mathcal{L}_{\text{sum}}(t)^2 +\frac{204nm}{(1-\gamma)^2c_{\alpha,\beta}}z_\beta^2\alpha. \end{align}\tag{49}\] In particular, \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k)] \leq\,& L_{\text{in}}\left(1-\frac{\beta}{2}\right)^{k-z_\beta} +\frac{32m^2}{\tau}\mathcal{L}_{\text{sum}}(t)^2 +\frac{204nm}{(1-\gamma)^2c_{\alpha,\beta}}z_\beta^2\alpha. \end{align}\] Substituting this inequality into 46 , we have \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k+1)] \leq\,& \left(1-\alpha c_\tau\right)\mathbb{E}_t[\mathcal{L}_q(t,k)] +\frac{151nm}{(1-\gamma)^2}z_\beta^2\alpha^2\\ &+ \frac{\beta L_{\text{in}}}{4} \left(1-\frac{\beta}{2}\right)^{k-z_\beta} +\frac{8m^2\beta}{\tau}\mathcal{L}_{\text{sum}}(t)^2. \end{align}\] Iterating the previous inequality and using \(c_{\alpha,\beta}\leq c_\tau\) gives \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k)] \leq\,& L_{\text{in}}\left(1-c_\tau\alpha\right)^{k-z_\beta} +\frac{\beta L_{\text{in}}(k-z_\beta)}{4} \left(1-\frac{\beta}{2}\right)^{k-z_\beta-1}\\ &+ \frac{8m^2c_{\alpha,\beta}}{c_\tau\tau}\mathcal{L}_{\text{sum}}(t)^2 +\frac{151nm}{(1-\gamma)^2c_\tau}z_\beta^2\alpha. \end{align}\] Thus, by Jensen’s inequality, \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k)^{1/2}] \leq\,& L_{\text{in}}^{1/2}\left(1-c_\tau\alpha\right)^{\frac{k-z_\beta}{2}} +\frac{\beta^{1/2} L_{\text{in}}^{1/2}(k-z_\beta)^{1/2}}{2} \left(1-\frac{\beta}{2}\right)^{\frac{k-z_\beta-1}{2}}\\ &+ \frac{3mc_{\alpha,\beta}^{1/2}}{c_\tau^{1/2}\tau^{1/2}}\mathcal{L}_{\text{sum}}(t) +\frac{13n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}}z_\beta\alpha^{1/2}. \end{align}\] Substituting the previous bound into 44 and then taking total expectation, we have \[\begin{align} \mathbb{E}[\mathcal{L}_{\text{sum}}(t+1)] \leq\,& \gamma\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +2L_{\text{in}}^{1/2}\left(1-c_\tau\alpha\right)^{\frac{K-z_\beta}{2}}\\ &+ \beta^{1/2}L_{\text{in}}^{1/2}(K-z_\beta)^{1/2} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}}\\ &+ \frac{6mc_{\alpha,\beta}^{1/2}}{c_\tau^{1/2}\tau^{1/2}} \mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +\frac{26n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}}z_\beta\alpha^{1/2}\\ \leq\,& \left(\frac{1+\gamma}{2}\right)\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +2L_{\text{in}}^{1/2}\left(1-c_\tau\alpha\right)^{\frac{K-z_\beta}{2}}\\ &+ \beta^{1/2}L_{\text{in}}^{1/2}(K-z_\beta)^{1/2} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}} +\frac{26n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}}z_\beta\alpha^{1/2}, \end{align}\] where the last line follows from \(c_{\alpha,\beta}\leq c_\tau\tau(1-\gamma)^2/(144m^2)\); see Condition 2. Since \(\|v_0^1+v_0^2\|_\infty\leq 2/(1-\gamma)\), iterating the previous inequality gives \[\begin{align} \label{eq:cicipp} \mathbb{E}[\mathcal{L}_{\text{sum}}(t)] \leq\,& \frac{2}{1-\gamma}\left(\frac{1+\gamma}{2}\right)^t +\frac{4L_{\text{in}}^{1/2}\left(1-c_\tau\alpha\right)^{\frac{K-z_\beta}{2}}}{1-\gamma}\nonumber\\ &+ \frac{2\beta^{1/2}L_{\text{in}}^{1/2}(K-z_\beta)^{1/2}}{1-\gamma} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}} +\frac{52n^{1/2}m^{1/2}}{(1-\gamma)^2c_\tau^{1/2}}z_\beta\alpha^{1/2}\nonumber\\ \leq\,& \frac{2}{1-\gamma}\left(\frac{1+\gamma}{2}\right)^t +\frac{6L_{\text{in}}^{1/2}(K-z_\beta)^{1/2}}{1-\gamma} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}} +\frac{52n^{1/2}m^{1/2}}{(1-\gamma)^2c_\tau^{1/2}}z_\beta\alpha^{1/2}. \end{align}\tag{50}\] Now we have obtained finite-sample bounds for \(\mathcal{L}_q(t,k)\), \(\mathcal{L}_\pi(t,k)\), and \(\mathcal{L}_{\text{sum}}(t)\). The next step is to use them in 43 to obtain a finite-sample bound for \(\mathcal{L}_v(t)\). Specifically, using 43 , 49 , and 50 , we have \[\begin{align} \mathbb{E}[\mathcal{L}_v(t+1)] \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +4\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +2\mathbb{E}[\mathcal{L}_q^{1/2}(t,K)] +4\mathbb{E}[\mathcal{L}_\pi(t,K)] +6\tau \log(m)\\ \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +\frac{266m^2}{\tau(1-\gamma)^2} \left(\frac{1+\gamma}{2}\right)^t\\ &+ \frac{805m^2L_{\text{in}}(K-z_\beta)^{1/2}}{(1-\gamma)^2\tau} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}}\\ &+ \frac{1223nm}{(1-\gamma)^2c_{\alpha,\beta}}z_\beta^2\alpha^{1/2} +6\tau \log(m). \end{align}\] Iterating the previous inequality from \(0\) to \(T-1\) and using \(\mathcal{L}_v(0)\leq 4/(1-\gamma)\), we obtain \[\begin{align} \mathbb{E}[\mathcal{L}_v(T)] \leq\,& \frac{270m^2T}{\tau(1-\gamma)^2} \left(\frac{1+\gamma}{2}\right)^{T-1}+ \frac{805m^2L_{\text{in}}(K-z_\beta)^{1/2}}{\tau(1-\gamma)^3} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}}\\ &+ \frac{1223nm}{(1-\gamma)^3c_{\alpha,\beta}}z_\beta^2\alpha^{1/2} +\frac{6\tau \log(m)}{1-\gamma}. \end{align}\]

Our next step is to use the bounds obtained for \(\mathcal{L}_q(t,k)\), \(\mathcal{L}_\pi(t,k)\), \(\mathcal{L}_{v}(t)\), and \(\mathcal{L}_{\text{sum}}(t)\) in Lemma 1. For simplicity of presentation, we use \(a\lesssim b\) to mean that there exists a numerical constant \(c\) such that \(a\leq cb\). Using the previous inequality, 49 , and 50 , we have \[\begin{align} \mathbb{E}[\text{NG}(\pi_{T,K}^1,\pi_{T,K}^2)] \leq\,& \frac{8}{1-\gamma}\mathbb{E}[\mathcal{L}_{\text{sum}}(T)] +\frac{4}{1-\gamma}\mathbb{E}[\mathcal{L}_v(T)] +\frac{4}{1-\gamma}\mathbb{E}[\mathcal{L}_\pi(T,K)] +\frac{8\tau \log(m)}{1-\gamma}\\ \lesssim\,& \frac{m^2T}{\tau(1-\gamma)^3} \left(\frac{1+\gamma}{2}\right)^{T-1} +\frac{m^2L_{\text{in}}(K-z_\beta)^{1/2}}{\tau(1-\gamma)^4} \left(1-\frac{\beta}{2}\right)^{\frac{K-z_\beta-1}{2}}\\ &+ \frac{nm}{(1-\gamma)^4c_{\alpha,\beta}}z_\beta^2\alpha^{1/2} +\frac{\tau \log(m)}{(1-\gamma)^2}. \end{align}\] The proof of Theorem 3 (1) is complete.

8.6.2 Diminishing Stepsizes↩︎

Consider using harmonically diminishing stepsizes, i.e., \(\alpha_k=\frac{\alpha}{k+h}\), \(\beta_k=\frac{\beta}{k+h}\), and \(\beta=c_{\alpha,\beta}\alpha\). Iterating 47 , we have for all \(k\geq k_0:=\min\{k'\mid k'\geq z_{k'}\}\) that \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k)+\mathcal{L}_q(t,k)] \leq \,& L_{\text{in}} \underbrace{\prod_{m=k_0}^{k-1}\left(1-\frac{\beta_m}{2}\right)}_{\hat{\mathcal{E}}_1} +\frac{204nm}{(1-\gamma)^2} \underbrace{\sum_{n=k_0}^{k-1}z_n^2\alpha_n^2 \prod_{m=n+1}^{k-1}\left(1-\frac{\beta_m}{2}\right)}_{\hat{\mathcal{E}}_2}\\ &+\frac{16m^2}{\tau}\mathcal{L}_{\text{sum}}(t)^2 \underbrace{\sum_{n=k_0}^{k-1}\beta_n \prod_{m=n+1}^{k-1}\left(1-\frac{\beta_m}{2}\right)}_{\hat{\mathcal{E}}_3}. \end{align}\] Next, we evaluate the terms \(\{\hat{\mathcal{E}}_j\}_{1\leq j\leq 3}\). Terms of this form have been well studied in the existing literature [48], [50], [51]. Specifically, using the same line of analysis as in [51] and \(\beta=4\), we have \[\begin{align} \hat{\mathcal{E}}_1\leq \frac{k_0+h}{k+h},\quad \hat{\mathcal{E}}_2\leq \frac{64ez_k^2}{(k+h)c_{\alpha,\beta}^2},\quad \text{and}\quad \hat{\mathcal{E}}_3\leq 2. \end{align}\] It follows that \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k)+\mathcal{L}_q(t,k)] \leq\,& L_{\text{in}}\frac{k_0+h}{k+h} +\frac{3264enm}{(1-\gamma)^2c_{\alpha,\beta}}z_k^2\alpha_k +\frac{32m^2}{\tau}\mathcal{L}_{\text{sum}}(t)^2, \end{align}\] which implies \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k)] \leq\,& L_{\text{in}}\frac{k_0+h}{k+h} +\frac{3264enm}{(1-\gamma)^2c_{\alpha,\beta}}z_k^2\alpha_k +\frac{32m^2}{\tau}\mathcal{L}_{\text{sum}}(t)^2. \label{eq:ci95di} \end{align}\tag{51}\] Using the previous inequality on \(\mathbb{E}_t[\mathcal{L}_\pi(t,k)]\) in 46 , we have \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k+1)] \leq \,& \left(1-\alpha_kc_\tau\right)\mathbb{E}_t[\mathcal{L}_q(t,k)] +\frac{100nm}{(1-\gamma)^2}z_k\alpha_k\alpha_{k-z_k,k-1}\\ &+\frac{L_{\text{in}} c_{\alpha,\beta}\alpha_k}{4}\frac{k_0+h}{k+h} +\frac{816enm}{(1-\gamma)^2}z_k^2\alpha_k^2 +\frac{8m^2\beta_k}{\tau}\mathcal{L}_{\text{sum}}(t)^2\\ \leq \,& \left(1-\alpha_kc_\tau\right)\mathbb{E}_t[\mathcal{L}_q(t,k)] +\frac{1017eL_{\text{in}}nm}{(1-\gamma)^2\alpha_{k_0}}z_k^2\alpha_k^2 +\frac{8m^2\beta_k}{\tau}\mathcal{L}_{\text{sum}}(t)^2. \end{align}\] Here the last inequality uses the monotonicity of \(\{\alpha_k\}\), the definition of \(k_0\), and the fact that \(z_k=\mathcal{O}(\log k)\); the constants are numerical and chosen conservatively.

Iterating the previous inequality starting from \(k_0\), and using \(\alpha c_\tau\geq 1\) from Condition 2, we have \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k)] \leq\,& L_{\text{in}}\frac{k_0+h}{k+h} +\frac{4068e^2L_{\text{in}}nm}{(1-\gamma)^2c_\tau\alpha_{k_0}}z_k^2\alpha_k +\frac{8m^2c_{\alpha,\beta}}{c_\tau\tau}\mathcal{L}_{\text{sum}}(t)^2. \end{align}\] Therefore, by Jensen’s inequality, \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k)^{1/2}] \leq L_{\text{in}}^{1/2}\left(\frac{k_0+h}{k+h}\right)^{1/2} +\frac{64eL_{\text{in}}^{1/2}n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}\alpha_{k_0}^{1/2}} z_k\alpha_k^{1/2}+ \frac{3m c_{\alpha,\beta}^{1/2}}{c_\tau^{1/2}\tau^{1/2}}\mathcal{L}_{\text{sum}}(t). \label{eeeq} \end{align}\tag{52}\] Taking total expectation on both sides of the previous inequality and then using the result in 44 , we obtain \[\begin{align} \mathbb{E}[\mathcal{L}_{\text{sum}}(t+1)] \leq\,& \gamma\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +2L_{\text{in}}^{1/2}\left(\frac{k_0+h}{K+h}\right)^{1/2}\\ &+ \frac{128eL_{\text{in}}^{1/2}n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}\alpha_{k_0}^{1/2}} z_K\alpha_K^{1/2} +\frac{6m c_{\alpha,\beta}^{1/2}}{c_\tau^{1/2}\tau^{1/2}} \mathbb{E}[\mathcal{L}_{\text{sum}}(t)]\\ \leq\,& \left(\frac{\gamma+1}{2}\right)\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +\frac{130eL_{\text{in}}^{1/2}n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}\alpha_{k_0}^{1/2}} z_K\alpha_K^{1/2}, \end{align}\] where the last line follows from \(c_{\alpha,\beta}\leq \frac{c_\tau\tau(1-\gamma)^2}{144m^2}\); see Condition 2. Iterating the previous inequality starting from \(0\), we have \[\begin{align} \mathbb{E}[\mathcal{L}_{\text{sum}}(t)] \leq\,& \frac{2}{1-\gamma}\left(\frac{1+\gamma}{2}\right)^t +\frac{260eL_{\text{in}}^{1/2}n^{1/2}m^{1/2}}{(1-\gamma)^2c_\tau^{1/2}\alpha_{k_0}^{1/2}} z_K\alpha_K^{1/2}. \label{eq:zls} \end{align}\tag{53}\]

The next step is to bound \(\mathcal{L}_v(t)\). Recall from 43 that \[\begin{align} \mathbb{E}_t[\mathcal{L}_v(t+1)] \leq\,& \gamma \mathcal{L}_v(t) +4\mathcal{L}_{\text{sum}}(t) +2\mathbb{E}_t[\mathcal{L}_q^{1/2}(t,K)] +4\mathbb{E}_t[\mathcal{L}_\pi(t,K)] +6\tau \log(m). \end{align}\] Using 51 , 52 , and 53 in the previous inequality, we obtain \[\begin{align} \mathbb{E}[\mathcal{L}_v(t+1)] \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +4\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +2\mathbb{E}[\mathcal{L}_q^{1/2}(t,K)] +4\mathbb{E}[\mathcal{L}_\pi(t,K)] +6\tau \log(m)\\ \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +\frac{130eL_{\text{in}}^{1/2}n^{1/2}m^{1/2}}{(1-\gamma)c_\tau^{1/2}\alpha_{k_0}^{1/2}} z_K\alpha_K^{1/2}\\ &+ \frac{4L_{\text{in}}\alpha_K}{\alpha_{k_0}} +\frac{13056enm}{(1-\gamma)^2c_{\alpha,\beta}}z_K^2\alpha_K +6\tau \log(m)\\ &+ \frac{522m^2}{\tau(1-\gamma)^2}\left(\frac{1+\gamma}{2}\right)^t +\frac{67860eL_{\text{in}}^{1/2}n^{1/2}m^{5/2}}{(1-\gamma)^3 \tau c_\tau^{1/2}\alpha_{k_0}^{1/2}} z_K\alpha_K^{1/2}\\ \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +\frac{522m^2}{\tau(1-\gamma)^2}\left(\frac{1+\gamma}{2}\right)^t+ \frac{15056eL_{\text{in}}nm}{(1-\gamma)^2\alpha_{k_0}^{1/2}c_{\alpha,\beta}} z_K^2\alpha_K^{1/2} +6\tau \log(m). \end{align}\] Iterating the previous inequality from \(0\) to \(T-1\) and using \(\mathcal{L}_v(0)\leq \frac{4}{1-\gamma}\), we have \[\begin{align} \mathbb{E}[\mathcal{L}_v(T)] \leq \frac{526m^2T}{\tau(1-\gamma)^2} \left(\frac{1+\gamma}{2}\right)^{T-1}+ \frac{15056eL_{\text{in}}nm}{(1-\gamma)^3\alpha_{k_0}^{1/2}c_{\alpha,\beta}} z_K^2\alpha_K^{1/2} +\frac{6\tau \log(m)}{1-\gamma}. \end{align}\] Finally, using the previous inequality, 51 , and 53 in Lemma 1, we obtain \[\begin{align} \mathbb{E}[\text{NG}(\pi_{T,K}^1,\pi_{T,K}^2)] \lesssim \frac{m^2 T}{\tau(1-\gamma)^3} \left(\frac{1+\gamma}{2}\right)^{T-1} +\frac{L_{\text{in}}nm}{(1-\gamma)^4\alpha_{k_0}^{1/2}c_{\alpha,\beta}} z_K^2\alpha_K^{1/2}+ \frac{\tau \log(m)}{(1-\gamma)^2}. \end{align}\] The proof of Theorem 3 (2) is complete.

8.7 Proofs of Supporting Lemmas↩︎

8.7.1 Proof of Lemma 24↩︎

(1) For any \(k\geq 0\), using the update equation 9 and Lemma 8 (1), we have \[\begin{align} \|q_{k+1}^i-q_k^i\|_2^2 =\,&\alpha_k^2\|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_2^2\\ =\,&\alpha_k^2\|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-F^i(0,S_k,A_k^i,A_k^{-i},S_{k+1})\\ &+F^i(0,S_k,A_k^i,A_k^{-i},S_{k+1})\|_2^2\\ \leq \,&\alpha_k^2\left(\|q_k^i\|_2+\frac{1}{1-\gamma}\right)^2\\ \leq \,&\alpha_k^2\left(\frac{\sqrt{nm}}{1-\gamma}+\frac{1}{1-\gamma}\right)^2 {1-\gamma} by Lemma \ref{le:boundedness95proof95outline}}\\ \leq \,&\frac{4nm\alpha_k^2}{(1-\gamma)^2}. \end{align}\] The result follows by taking expectation on both sides of the previous inequality.

(2) For any \(k\geq 0\), using the definition of \(\Bar{q}_k^i\) in Appendix 8.1, we have \[\begin{align} \|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2 =\,& \sum_{s}\|\mathcal{T}^i(v^i)(s)(\pi_{k+1}^{-i}(s)-\pi_k^{-i}(s))\|_2^2\\ =\,& \beta_k^2\sum_{s}\|\mathcal{T}^i(v^i)(s)(\sigma_\tau(q_k^{-i}(s))-\pi_k^{-i}(s))\|_2^2\\ \leq \,& \beta_k^2\sum_{s} \left( \|\mathcal{T}^i(v^i)(s)\sigma_\tau(q_k^{-i}(s))\|_2 + \|\mathcal{T}^i(v^i)(s)\pi_k^{-i}(s)\|_2 \right)^2\\ \leq \,&\frac{4nm\beta_k^2}{(1-\gamma)^2}. \end{align}\] The result follows by taking expectation on both sides of the previous inequality.

(3) For any \(k\geq 0\), we have \[\begin{align} \langle q_{k+1}^i-q_k^i,\bar{q}_k^i-\bar{q}_{k+1}^i\rangle \leq \|q_{k+1}^i-q_k^i\|_2\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2 \leq \frac{4nm\alpha_k\beta_k}{(1-\gamma)^2}, \end{align}\] where the last inequality follows from Parts (1) and (2). The result follows by taking expectation on both sides.

(4) For any \(k\geq 0\), we have \[\begin{align} &\langle q_k^i-\bar{q}_k^i,\bar{q}_k^i-\bar{q}_{k+1}^i\rangle\nonumber\\ =\,& \beta_k\sum_{s} \langle q_k^i(s)-\bar{q}_k^i(s), \mathcal{T}^i(v^i)(s)(\sigma_\tau(q_k^{-i}(s))-\pi_k^{-i}(s))\rangle\nonumber\\ \leq \,& \frac{c_1\beta_k}{2}\| q_k^i-\bar{q}_k^i\|_2^2 + \frac{\beta_k}{2c_1} \sum_{s}\|\mathcal{T}^i(v^i)(s)(\sigma_\tau(q_k^{-i}(s))-\pi_k^{-i}(s))\|_2^2, \label{eq:otherterms952} \end{align}\tag{54}\] where \(c_1>0\) is arbitrary. We next bound the second term on the right-hand side. For any \(s\in\mathcal{S}\), we have \[\begin{align} &\|\mathcal{T}^i(v^i)(s)(\sigma_\tau(q_k^{-i}(s))-\pi_k^{-i}(s))\|_2\\ =\,& \|\mathcal{T}^i(v^i)(s) (\sigma_\tau(q_k^{-i}(s))-\sigma_\tau(\bar{q}_k^{-i}(s)) +\sigma_\tau(\mathcal{T}^{-i}(v^{-i})(s)\pi_k^i(s))-\pi_k^{-i}(s))\|_2\\ \leq \,& \underbrace{\|\mathcal{T}^i(v^i)(s)(\sigma_\tau(q_k^{-i}(s))-\sigma_\tau(\bar{q}_k^{-i}(s)))\|_2}_{B_1}\\ &+ \underbrace{\|\mathcal{T}^i(v^i)(s)(\sigma_\tau(\mathcal{T}^{-i}(v^{-i})(s)\pi_k^i(s))-\pi_k^{-i}(s))\|_2}_{B_2}. \end{align}\] Since the softmax operator \(\sigma_\tau(\cdot)\) is \(\frac{1}{\tau}\) – Lipschitz continuous with respect to \(\|\cdot\|_2\) [63], we have \[\begin{align} B_1 \leq\,& \|\mathcal{T}^i(v^i)(s)\|_2 \|\sigma_\tau(q_k^{-i}(s))-\sigma_\tau(\bar{q}_k^{-i}(s))\|_2\\ \leq\,& \frac{m}{\tau(1-\gamma)} \|q_k^{-i}(s)-\bar{q}_k^{-i}(s)\|_2. \end{align}\] We next analyze \(B_2\). Using Lemma 5 (1) and the quadratic growth property of strongly convex functions, we have \[\begin{align} B_2 =\,& \|\mathcal{T}^i(v^i)(s)(\sigma_\tau(\mathcal{T}^{-i}(v^{-i})(s)\pi_k^i(s))-\pi_k^{-i}(s))\|_2\\ \leq \,& \|\mathcal{T}^i(v^i)(s)\|_2 \|\sigma_\tau(\mathcal{T}^{-i}(v^{-i})(s)\pi_k^i(s))-\pi_k^{-i}(s)\|_2\\ \leq \,& \frac{\sqrt{2}m}{\sqrt{\tau}(1-\gamma)} V_{v,s}(\pi_k^1(s),\pi_k^2(s))^{1/2}. \end{align}\] Combining the upper bounds for \(B_1\) and \(B_2\), we obtain \[\begin{align} &\sum_{s}\|\mathcal{T}^i(v^i)(s)(\sigma_\tau(q_k^{-i}(s))-\pi_k^{-i}(s))\|_2^2\\ \leq \,& \sum_{s}(B_1+B_2)^2\\ \leq \,& 2\sum_{s}(B_1^2+B_2^2)\\ \leq \,& 2\sum_{s} \left( \frac{m^2}{\tau^2(1-\gamma)^2} \|q_k^{-i}(s)-\bar{q}_k^{-i}(s)\|_2^2 + \frac{2m^2}{\tau(1-\gamma)^2} V_{v,s}(\pi_k^1(s),\pi_k^2(s)) \right)\\ \leq \,& \frac{2m^2}{\tau^2(1-\gamma)^2} \|q_k^{-i}-\bar{q}_k^{-i}\|_2^2 + \frac{4nm^2}{\tau(1-\gamma)^2}\mathcal{L}_\pi(k). \end{align}\] Returning to 54 , we have \[\begin{align} &\langle q_k^i-\bar{q}_k^i,\bar{q}_k^i-\bar{q}_{k+1}^i\rangle\\ \leq\,& \frac{c_1\beta_k}{2}\| q_k^i-\bar{q}_k^i\|_2^2 + \frac{m^2\beta_k}{c_1\tau^2(1-\gamma)^2} \|q_k^{-i}-\bar{q}_k^{-i}\|_2^2 + \frac{2nm^2\beta_k}{c_1\tau(1-\gamma)^2}\mathcal{L}_\pi(k). \end{align}\] Choosing \(c_1=\frac{32nm^2}{\tau(1-\gamma)^2}\) and taking expectations on both sides gives \[\begin{align} &\mathbb{E}[\langle q_k^i-\bar{q}_k^i,\bar{q}_k^i-\bar{q}_{k+1}^i\rangle]\\ \leq\,& \frac{16nm^2\beta_k}{\tau(1-\gamma)^2} \mathbb{E}[\| q_k^i-\bar{q}_k^i\|_2^2] + \frac{\beta_k}{32n\tau} \mathbb{E}[\|q_k^{-i}-\bar{q}_k^{-i}\|_2^2] + \frac{\beta_k}{16}\mathbb{E}[\mathcal{L}_\pi(k)]. \end{align}\] In particular, after summing over \(i=1,2\), we obtain \[\begin{align} \sum_{i=1,2} \mathbb{E}[\langle q_k^i-\bar{q}_k^i,\bar{q}_k^i-\bar{q}_{k+1}^i\rangle] \leq\,& \frac{17nm^2\beta_k}{\tau(1-\gamma)^2} \sum_{i=1,2}\mathbb{E}[\| q_k^i-\bar{q}_k^i\|_2^2] + \frac{\beta_k}{8}\mathbb{E}[\mathcal{L}_\pi(k)]. \end{align}\]

This completes the proof. 0◻

8.7.2 Proof of Lemma 25↩︎

For any \(k\geq z_k\), we decompose \[\begin{align} &\mathbb{E}[ (F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)]\nonumber\\ = \,& \underbrace{\mathbb{E}[ (F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -\bar{F}_{k-z_k}^i(q_{k-z_k}^i))^\top (q_{k-z_k}^i-\bar{q}_{k-z_k}^i)]}_{N_1}\nonumber\\ &+ \underbrace{\mathbb{E}[ (F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -\bar{F}_{k-z_k}^i(q_{k-z_k}^i))^\top (q_k^i-q_{k-z_k}^i)]}_{N_2}\nonumber\\ &+ \underbrace{\mathbb{E}[ (F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -\bar{F}_{k-z_k}^i(q_{k-z_k}^i))^\top (\bar{q}_{k-z_k}^i-\bar{q}_k^i)]}_{N_3}\nonumber\\ &+ \underbrace{\mathbb{E}[ (F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1}))^\top (q_k^i-\bar{q}_k^i)]}_{N_4}\nonumber\\ &+ \underbrace{\mathbb{E}[ (\bar{F}_{k-z_k}^i(q_{k-z_k}^i)-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)]}_{N_5}. \label{eq:N195N5} \end{align}\tag{55}\] To bound \(N_1\) to \(N_5\), we first use the following lemma.

For any \(k\in [k_1,k_2-1]\), we have by 9 that \[\begin{align} \|q_{k+1}^i-q_k^i\|_\infty = \alpha_k \|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_\infty \leq \frac{2\alpha_k}{1-\gamma}. \end{align}\] It follows that \(\|q_{k_2}^i-q_{k_1}^i\|_\infty\leq \frac{2\alpha_{k_1,k_2-1}}{1-\gamma}\). Similarly, for any \(k\in [k_1,k_2-1]\) and \(s\in\mathcal{S}\), \[\begin{align} \|\pi_{k+1}^i(s)-\pi_k^i(s)\|_1 = \beta_k\|\sigma_\tau(q_k^i(s))-\pi_k^i(s)\|_1 \leq 2\beta_k. \end{align}\] Thus, \(\max_{s\in\mathcal{S}}\|\pi_{k_2}^i(s)-\pi_{k_1}^i(s)\|_1\leq 2\beta_{k_1,k_2-1}\). 0◻

Let \(\mathcal{F}_k\) be the \(\sigma\)-algebra generated by \(\{S_0,A_0^i,A_0^{-i},\cdots,S_{k-1},A_{k-1}^i,A_{k-1}^{-i},S_k\}\).

The Term \(N_1\). Using the tower property of conditional expectations, we have \[\begin{align} N_1 =\,& \mathbb{E}\big[ \big(\mathbb{E}[F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\mid \mathcal{F}_{k-z_k}] -\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\big)^\top (q_{k-z_k}^i-\bar{q}_{k-z_k}^i) \big]\nonumber\\ \leq\,& \frac{2}{1-\gamma} \mathbb{E}\big[ \|\mathbb{E}[F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\mid \mathcal{F}_{k-z_k}] -\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \big]\nonumber\\ \leq\,& \frac{2}{1-\gamma} \mathbb{E}\big[ \|\bar{F}_k^i(q_{k-z_k}^i)-\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \big]\nonumber\\ &+ \frac{2}{1-\gamma} \mathbb{E}\big[ \|\mathbb{E}[F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\mid \mathcal{F}_{k-z_k}] -\bar{F}_k^i(q_{k-z_k}^i)\|_1 \big]. \label{eq:N195decomposition} \end{align}\tag{56}\] The first term on the right-hand side of 56 is bounded by \[\begin{align} \|\bar{F}_k^i(q_{k-z_k}^i)-\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \leq \frac{8nmL_p\beta_{k-z_k,k-1}}{1-\gamma}. \label{eq:1020} \end{align}\tag{57}\] Indeed, this follows from the total-variation characterization, Lemma 7 (3), and Lemma 26.

It remains to bound the second term on the right-hand side of 56 . Since the sample at time \(k\) is generated using \(\pi_{k+1}\), while \(\bar F_k^i\) is defined using the stationary distribution and action distribution associated with \(\pi_k\), this term contains both a state-distribution mixing error and a one-step policy-shift error. Using the definition of conditional expectations, we have \[\begin{align} &\|\mathbb{E}[F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\mid \mathcal{F}_{k-z_k}] -\bar{F}_k^i(q_{k-z_k}^i)\|_1\nonumber\\ \leq\,& \frac{2}{1-\gamma} \left\{ \left\|\prod_{j=k+1}^{k+z_k}P_{\pi_{j-z_k}}-P_{\pi_k}^{z_k}\right\|_\infty +2\rho_*^{z_k} \right\} + \frac{4\beta_k}{1-\gamma}. \label{eq:probability} \end{align}\tag{58}\] The last term \(\frac{4\beta_k}{1-\gamma}\) accounts for the one-step difference between sampling actions from \(\pi_{k+1}\) and using the action distribution \(\pi_k\) in \(\bar F_k^i\).

Moreover, \[\begin{align} \left\|\prod_{j=k+1}^{k+z_k}P_{\pi_{j-z_k}}-P_{\pi_k}^{z_k}\right\|_\infty \leq \sum_{\ell=1}^{z_k}\|P_{\pi_{k-\ell+1}}-P_{\pi_k}\|_\infty \leq 4z_k\beta_{k-z_k,k-1}, \end{align}\] where the last inequality follows from Lemma 26. Using the definition of \(z_k\), we have \(2\rho_*^{z_k}\leq \beta_k\). Hence, using \(z_k\geq 1\) and \(\beta_k\leq \beta_{k-z_k,k-1}\), we obtain \[\begin{align} &\|\mathbb{E}[F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\mid \mathcal{F}_{k-z_k}] -\bar{F}_k^i(q_{k-z_k}^i)\|_1\\ \leq\,& \frac{2}{1-\gamma} \left(4z_k\beta_{k-z_k,k-1}+\beta_k\right) + \frac{4\beta_k}{1-\gamma}\\ \leq\,& \frac{14z_k\beta_{k-z_k,k-1}}{1-\gamma}. \end{align}\] Using the previous inequality and 57 in 56 , we obtain \[\begin{align} N_1 \leq \frac{16L_pnm\beta_{k-z_k,k-1}}{(1-\gamma)^2} + \frac{28z_k\beta_{k-z_k,k-1}}{(1-\gamma)^2} \leq \frac{44L_pnmz_k\beta_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\]

The Term \(N_2\). For any \(k\geq z_k\), by Lemma 26, \[\begin{align} N_2 \leq\,& \mathbb{E}[ \|F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \|q_k^i-q_{k-z_k}^i\|_\infty]\nonumber\\ \leq\,& \frac{2\alpha_{k-z_k,k-1}}{1-\gamma} \mathbb{E}[ \|F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_1 +\|\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1]. \label{eq:N295decomposition} \end{align}\tag{59}\] Using the definition of \(F^i(\cdot)\) and Lemma 2, we have \[\begin{align} \|F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_1 \leq \frac{2}{1-\gamma}. \label{eq12395N2} \end{align}\tag{60}\] Moreover, by Jensen’s inequality, \[\begin{align} \|\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \leq \frac{2}{1-\gamma}. \label{eq12495N2} \end{align}\tag{61}\] Using 60 and 61 in 59 , we have \[\begin{align} N_2\leq \frac{8\alpha_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\]

The Term \(N_3\). For any \(k\geq z_k\), \[\begin{align} N_3 \leq\,& \mathbb{E}[ \| F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \|\bar{q}_{k-z_k}^i-\bar{q}_k^i\|_\infty]\\ \leq\,& \frac{4}{1-\gamma}\mathbb{E}[\|\bar{q}_{k-z_k}^i-\bar{q}_k^i\|_\infty], \end{align}\] where the last line follows from 60 and 61 . Observe that \[\begin{align} \|\bar{q}_{k-z_k}^i-\bar{q}_k^i\|_\infty =\,& \max_{s\in\mathcal{S}} \|\mathcal{T}^i(v^i)(s)(\pi_k^{-i}(s)-\pi_{k-z_k}^{-i}(s))\|_\infty\\ \leq\,& \max_{s\in\mathcal{S}}\|\mathcal{T}^i(v^i)(s)\|_{1,\infty} \|\pi_k^{-i}(s)-\pi_{k-z_k}^{-i}(s)\|_1\\ \leq\,& \frac{2\beta_{k-z_k,k-1}}{1-\gamma}, \end{align}\] where the last line follows from Lemma 26 and \(\|\mathcal{T}^i(v^i)(s)\|_{1,\infty}\leq \frac{1}{1-\gamma}\). Therefore, \[\begin{align} N_3\leq \frac{8\beta_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\]

The Term \(N_4\). For any \(k\geq z_k\), \[\begin{align} N_4 \leq \,& \mathbb{E}[ \|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_1 \|q_k^i-\bar{q}_k^i\|_\infty]\\ \leq \,& \frac{2}{1-\gamma} \mathbb{E}[ \|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1}) -F^i(q_{k-z_k}^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_1]\\ \leq\,& \frac{4\alpha_{k-z_k,k-1}}{(1-\gamma)^2}, \end{align}\] where the last inequality follows from Lemma 26.

The Term \(N_5\). For any \(k\geq z_k\), we have \[\begin{align} N_5 \leq\,& \frac{2}{1-\gamma} \mathbb{E}[\| \bar{F}_k^i(q_k^i)-\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1]\nonumber\\ \leq\,& \frac{2}{1-\gamma} \mathbb{E}[ \| \bar{F}_k^i(q_k^i)-\bar{F}_{k-z_k}^i(q_k^i)\|_1 + \|\bar{F}_{k-z_k}^i(q_k^i)-\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1]\nonumber\\ \leq\,& \frac{16L_pnm\beta_{k-z_k,k-1}}{(1-\gamma)^2} + \frac{2}{1-\gamma} \mathbb{E}[ \|\bar{F}_{k-z_k}^i(q_k^i)-\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1], \label{eq:N595decomposition} \end{align}\tag{62}\] where the last line follows from the same analysis used to obtain 57 . For the second term on the right-hand side of 62 , using the definition of \(\bar{F}_{k-z_k}^i(\cdot)\), we have \[\begin{align} \|\bar{F}_{k-z_k}^i(q_k^i)-\bar{F}_{k-z_k}^i(q_{k-z_k}^i)\|_1 \leq \|q_k^i-q_{k-z_k}^i\|_\infty \leq \frac{2\alpha_{k-z_k,k-1}}{1-\gamma}. \end{align}\] Using this in 62 , we obtain \[\begin{align} N_5 \leq \frac{16L_pnm\beta_{k-z_k,k-1}}{(1-\gamma)^2} + \frac{4\alpha_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\]

Combining the upper bounds for \(N_1\) to \(N_5\) in 55 , we obtain \[\begin{align} &\mathbb{E}[ (F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)]\\ \leq\,& \frac{44L_pnmz_k\beta_{k-z_k,k-1}}{(1-\gamma)^2} +\frac{8\alpha_{k-z_k,k-1}}{(1-\gamma)^2} +\frac{8\beta_{k-z_k,k-1}}{(1-\gamma)^2}\\ &+ \frac{4\alpha_{k-z_k,k-1}}{(1-\gamma)^2} +\frac{16L_pnm\beta_{k-z_k,k-1}}{(1-\gamma)^2} +\frac{4\alpha_{k-z_k,k-1}}{(1-\gamma)^2}\\ \leq\,& \frac{76L_pnmz_k\beta_{k-z_k,k-1}}{(1-\gamma)^2} +\frac{16\alpha_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\] Since \(c_{\alpha,\beta}=\beta_k/\alpha_k\leq 1/(76L_pnm)\) (cf. Condition 2), we have \(\beta_{k-z_k,k-1}\leq c_{\alpha,\beta}\alpha_{k-z_k,k-1}\), which implies \[\begin{align} \mathbb{E}[ (F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)] \leq \frac{17z_k\alpha_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\] This completes the proof. 0◻

9 Proof of Theorem 4↩︎

The high-level idea of proving Theorem 4 is similar to that of Theorem 3. However, due to the algorithmic modification, namely, replacing \(\sigma_\tau(\cdot)\) with \(\sigma_\tau^{\bar{\epsilon}}(\cdot)\), the negative drift inequalities for the policies and the \(q\)-functions are substantially different from those in the proof of Theorem 3.

9.1 Boundedness of the Iterates↩︎

The proof of Lemma 27 is identical to that of Lemma 2, and therefore is omitted.

9.2 Bounding the Nash Gap↩︎

We restate Lemma 1 to make the proof self-contained.

9.3 Analysis of the Outer Loop↩︎

We restate Lemma 3 and Lemma 4 to make the proof self-contained.

9.4 Analysis of the Inner Loop↩︎

For ease of presentation, we write down only the inner loop of Algorithm 4 in the following, where we omit the subscript \(t\). Similarly, we write \(\mathcal{L}_q(k)\) for \(\mathcal{L}_q(t,k)\) and \(\mathcal{L}_\pi(k)\) for \(\mathcal{L}_\pi(t,k)\).

9.4.1 Analysis of the Policies↩︎

We will use \(V_{v,s}(\cdot,\cdot)\) as a Lyapunov function to study the evolution of \((\pi_k^1(s),\pi_k^2(s))\). A sequence of properties regarding \(V_X(\cdot,\cdot)\) for arbitrary matrices \(X_1,X_2\) is presented in Lemma 34. To begin with, we identify the smoothness parameter of \(V_{v,s}(\cdot,\cdot)\). Using Lemma 34 (1) and the definition of \(V_{v,s}(\cdot,\cdot)\), we have \[\begin{align} L_{\tau,\Bar{\epsilon}} =\,& 2\left( \frac{m \tau}{\Bar{\epsilon}} +\frac{\max(\|X_1\|_2^2,\|X_2\|_2^2)}{\tau} +\|X_1+X_2^\top\|_2 \right)\\ =\,& 2\left( m +\frac{\max(\|\mathcal{T}^1(v^1)(s)\|_2^2,\|\mathcal{T}^2(v^2)(s)\|_2^2)}{\tau} +\|\mathcal{T}^1(v^1)(s)+\mathcal{T}^2(v^2)(s)^\top\|_2 \right) =\tau}\\ \leq \,& 2\left( m +\frac{m^2}{\tau(1-\gamma)^2} +\frac{2m}{1-\gamma} \right)\\ \leq \,& \frac{5m^2}{\tau(1-\gamma)^2} =\Bar{L}_{\tau}, \end{align}\] where the first inequality follows from \(|\mathcal{T}^i(v^i)(s,a^i,a^{-i})|\leq \frac{1}{1-\gamma}\) for all \((s,a^i,a^{-i})\) and \(i\in \{1,2\}\), and the last inequality follows from \(m\geq 2\) and \(\tau\leq 1/(1-\gamma)\). Therefore, \(V_{v,s}(\cdot,\cdot)\) is a \(\Bar{L}_\tau\) – smooth function on \(\Pi_{\Bar{\epsilon}}\), where \(\Pi_{\Bar{\epsilon}}=\{(\mu^1,\mu^2)\mid \min_{a^1}\mu^1(a^1)\geq \Bar{\epsilon}/m,\min_{a^2}\mu^2(a^2)\geq \Bar{\epsilon}/m\}\).

Using the smoothness of \(V_{v,s}(\cdot,\cdot)\), for any \(s\in\mathcal{S}\), we have by the policy update equation in Algorithm 6, Line 3, that \[\begin{align} &V_{v,s}(\pi_{k+1}^1(s),\pi_{k+1}^2(s))\\ \leq\,& V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\beta_k\langle \nabla_2V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau^{\bar{\epsilon}}(q_k^2(s))-\pi_k^2(s) \rangle\\ &+\beta_k\langle \nabla_1V_{v,s}(\pi_k^1(s),\pi_k^2(s)),\sigma_\tau^{\bar{\epsilon}}(q_k^1(s))-\pi_k^1(s) \rangle +\frac{\Bar{L}_\tau\beta_k^2}{2} \sum_{i=1,2}\|\sigma_\tau^{\bar{\epsilon}}(q_k^i(s))-\pi_k^i(s)\|_2^2\\ \leq\,& V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +\beta_k\langle \nabla_2V_{v,s}(\pi_k^1(s),\pi_k^2(s)), \sigma_\tau(\mathcal{T}^2(v^2)(s)\pi_k^1(s))-\pi_k^2(s) \rangle\\ &+\beta_k\langle \nabla_1 V_{v,s}(\pi_k^1(s),\pi_k^2(s)), \sigma_\tau(\mathcal{T}^1(v^1)(s)\pi_k^2(s))-\pi_k^1(s) \rangle\\ &+\beta_k\langle \nabla_2V_{v,s}(\pi_k^1(s),\pi_k^2(s)), \sigma_\tau^{\bar{\epsilon}}(q_k^2(s))-\sigma_\tau(\mathcal{T}^2(v^2)(s)\pi_k^1(s)) \rangle\\ &+\beta_k\langle \nabla_1 V_{v,s}(\pi_k^1(s),\pi_k^2(s)), \sigma_\tau^{\bar{\epsilon}}(q_k^1(s))-\sigma_\tau(\mathcal{T}^1(v^1)(s)\pi_k^2(s)) \rangle +2\Bar{L}_\tau\beta_k^2\\ \leq\,& (1-\beta_k)V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +4\beta_k\max_{s,a^1,a^2}\left| \sum_{i=1,2}\mathcal{T}^i(v^i)(s,a^i,a^{-i}) \right|\\ &+2\beta_k\left( m+ \frac{\max_{i\in\{1,2\}}\|\mathcal{T}^i(v^i)(s)\|_2}{\tau} \right) \sum_{i=1,2}\|q_k^i(s)-\mathcal{T}^i(v^i)(s)\pi_k^{-i}(s)\|_2\\ &+4\beta_k\Bar{\epsilon}\left( m+\sum_{i=1,2}\|\mathcal{T}^i(v^i)(s)\|_2 \right) +2\Bar{L}_\tau\beta_k^2, \end{align}\] where the last line follows from Lemma 34 (2) and (3), and \(\Bar{\epsilon}=\tau\).

Since \[\begin{align} \max_{s,a^i,a^{-i}}\left| \sum_{i=1,2}\mathcal{T}^i(v^i)(s,a^i,a^{-i}) \right| \leq \|v^1+v^2\|_\infty,\quad \|\mathcal{T}^i(v^i)(s)\|_2\leq \frac{m}{1-\gamma}, \end{align}\] and \(\tau\leq 1/(1-\gamma)\), we obtain \[\begin{align} \max_{s\in\mathcal{S}}V_{v,s}(\pi_{k+1}^1(s),\pi_{k+1}^2(s)) \leq\,& (1-\beta_k)\max_{s\in\mathcal{S}}V_{v,s}(\pi_k^1(s),\pi_k^2(s)) +4\beta_k\|v^1+v^2\|_\infty\\ &+\frac{4m\beta_k}{\tau(1-\gamma)} \sum_{i=1,2}\|q_k^i-\Bar{q}_k^i\|_2 +2\Bar{L}_\tau\beta_k^2 +\frac{12m\tau \beta_k}{1-\gamma}. \end{align}\] Taking expectation on both sides and using the pathwise inequality \[\begin{align} \sum_{i=1,2}\|q_k^i-\Bar{q}_k^i\|_2 \leq 2\left(\sum_{i=1,2}\|q_k^i-\Bar{q}_k^i\|_2^2\right)^{1/2} = 2\mathcal{L}_q(k)^{1/2}, \end{align}\] gives the desired result. 0◻

9.4.2 Analysis of the \(q\)-Functions↩︎

For \(i\in \{1,2\}\), fixing \(v^i\in\mathbb{R}^{n}\), let \(F^i:\mathbb{R}^{n m_i}\times \mathcal{S}\times \mathcal{A}^i\times \mathcal{A}^{-i}\times \mathcal{S}\to \mathbb{R}^{n m_i}\) be defined as \[\begin{align} [F^i(q^i,s_0,a_0^i,a_0^{-i},s_1)](s,a^i) = \mathbb{1}_{\{(s,a^i)=(s_0,a_0^i)\}} \left(R_i(s_0,a_0^i,a_0^{-i})+\gamma v^i(s_1)-q^i(s_0,a_0^i)\right) \end{align}\] for all \((q^i,s_0,a_0^i,a_0^{-i},s_1)\) and \((s,a^i)\). Then, Line 5 of Algorithm 6 can be written as \[\begin{align} \label{sa:reformulation95slow} q_{k+1}^i=q_k^i+\alpha_k F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1}). \end{align}\tag{63}\] Denote the stationary distribution of the Markov chain \(\{S_k\}\) induced by the joint policy \(\pi_k=(\pi_k^1,\pi_k^2)\) by \(\mu_k\in\Delta(\mathcal{S})\), the existence and uniqueness of which are guaranteed by Lemma 27 and Lemma 7 (1). Let \(\Bar{F}_k^i:\mathbb{R}^{n m_i}\to \mathbb{R}^{n m_i}\) be defined as \[\begin{align} \Bar{F}_k^i(q^i) = \mathbb{E}_{S_0\sim \mu_k(\cdot),A_0^i\sim \pi_k^i(\cdot|S_0), A_0^{-i}\sim \pi_k^{-i}(\cdot|S_0), S_1\sim p(\cdot|S_0,A_0^i,A_0^{-i})} \left[F^i(q^i,S_0,A_0^i,A_0^{-i},S_1)\right] \end{align}\] for all \(q^i\in\mathbb{R}^{nm_i}\).

Using the binomial theorem and the equivalent formulation of the update equation in 63 , we have for all \(k\geq 0\) and \(i\in \{1,2\}\) that \[\begin{align} \label{eq:q95Lyapunov95decomposition95slow} \mathbb{E}[\|q_{k+1}^i-\bar{q}_{k+1}^i\|_2^2] =\,& \mathbb{E}[\|q_{k+1}^i-q_k^i+q_k^i-\bar{q}_k^i+\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]\nonumber\\ =\,& \mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\alpha_k^2\mathbb{E}[\|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_2^2]\nonumber\\ &+\mathbb{E}[\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2] +2\alpha_k\mathbb{E}[(q_k^i-\bar{q}_k^i)^\top \bar{F}_k^i(q_k^i)]\nonumber\\ &+2\alpha_k\mathbb{E}[(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)]\nonumber\\ &+2\alpha_k\mathbb{E}[(\bar{q}_k^i-\bar{q}_{k+1}^i)^\top F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})]\nonumber\\ &+2\mathbb{E}[(q_k^i-\bar{q}_k^i)^\top (\bar{q}_k^i-\bar{q}_{k+1}^i)]\nonumber\\ \leq \,& \left(1-\frac{3\mu_{\min}\Bar{\epsilon}\alpha_k}{2m}\right) \mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +2\alpha_k^2\mathbb{E}[\|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_2^2]\nonumber\\ &+\frac{4m\mathbb{E}[\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]}{\mu_{\min}\Bar{\epsilon} \alpha_k}\nonumber\\ &+2\alpha_k\mathbb{E}[(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)], \end{align}\tag{64}\] where the last line follows from Lemma 8, the Cauchy–Schwarz inequality, and \(a^2/c+b^2c\geq 2ab\) for any \(a,b\in\mathbb{R}\) and \(c>0\).

Next, we bound the terms \(\mathbb{E}[\|F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})\|_2^2]\), \(\mathbb{E}[\|\bar{q}_k^i-\bar{q}_{k+1}^i\|_2^2]\), and \(\mathbb{E}[(F^i(q_k^i,S_k,A_k^i,A_k^{-i},S_{k+1})-\bar{F}_k^i(q_k^i))^\top (q_k^i-\bar{q}_k^i)]\) in the following lemma, which is a restatement of Lemma 24 and Lemma 25.

Using Lemma 33 in 64 , and recalling that \(\Bar{\epsilon}=\tau\), we have \[\begin{align} \mathbb{E}[\|q_{k+1}^i-\bar{q}_{k+1}^i\|_2^2] \leq\,& \left(1-\frac{3\mu_{\min}\tau\alpha_k}{2m}\right) \mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\frac{8\alpha_k^2}{(1-\gamma)^2}\\ &+\frac{16nm^2\beta_k^2}{\mu_{\min}\tau(1-\gamma)^2\alpha_k} +\frac{34z_k\alpha_k\alpha_{k-z_k,k-1}}{(1-\gamma)^2}\\ \leq\,& \left(1-\frac{3\mu_{\min}\tau\alpha_k}{2m}\right) \mathbb{E}[\|q_k^i-\bar{q}_k^i\|_2^2] +\frac{16nm^2\beta_k^2}{\mu_{\min}\tau(1-\gamma)^2\alpha_k}\\ &+\frac{42z_k\alpha_k\alpha_{k-z_k,k-1}}{(1-\gamma)^2}, \end{align}\] where the last inequality follows from \(z_k\geq 1\) and \(\alpha_{k-z_k,k-1}\geq \alpha_k\), which imply \(\alpha_k^2\leq z_k\alpha_k\alpha_{k-z_k,k-1}\). Summing the previous inequality over \(i\in\{1,2\}\) gives \[\begin{align} \mathbb{E}[\mathcal{L}_q(k+1)] \leq \left(1-\frac{3\mu_{\min}\tau\alpha_k}{2m}\right) \mathbb{E}[\mathcal{L}_q(k)] +\frac{32nm^2\beta_k^2}{\mu_{\min}\tau(1-\gamma)^2\alpha_k}+\frac{84z_k\alpha_k\alpha_{k-z_k,k-1}}{(1-\gamma)^2}. \end{align}\] This completes the proof. 0◻

9.5 Solving Coupled Lyapunov Drift Inequalities↩︎

We first restate the Lyapunov drift inequalities for the value functions, the \(q\)-functions, and the policies.

• Lemma 29: It holds for all \(t\geq 0\) that \[\begin{align} \label{eq:Lyapunov95v95slow} \mathcal{L}_v(t+1) \leq \,& \gamma \mathcal{L}_v(t) +4\mathcal{L}_{\text{sum}}(t) +2\mathcal{L}_q^{1/2}(t,K) +4\mathcal{L}_\pi(t,K) +6\tau \log(m). \end{align}\tag{65}\]

• Lemma 30: It holds for all \(t\geq 0\) that \[\begin{align} \label{eq:Lyapunov95v4395slow} \mathcal{L}_{\text{sum}}(t+1) \leq \gamma\mathcal{L}_{\text{sum}}(t) +2\mathcal{L}_q^{1/2}(t,K). \end{align}\tag{66}\]

• Lemma 31: It holds for all \(t,k\geq 0\) that \[\begin{align} \label{eq:Lyapunov95pi95slow} \mathbb{E}_t[\mathcal{L}_\pi(t,k+1)] \leq\,& (1-\beta)\mathbb{E}_t[\mathcal{L}_\pi(t,k)] +4\beta\mathcal{L}_{\text{sum}}(t) +c_\pi\beta\mathbb{E}_t[\mathcal{L}_q^{1/2}(t,k)]\nonumber\\ &+\frac{12m\tau\beta}{1-\gamma} +2\Bar{L}_\tau \beta^2, \end{align}\tag{67}\] where \(c_\pi=\frac{8m}{(1-\gamma)\tau}\) and \(\mathbb{E}_t[\cdot]\) denotes the conditional expectation given the history up to the beginning of the \(t\)-th outer loop.

• Lemma 32: It holds for all \(t\geq 0\) and \(k\geq z_\beta\) that \[\begin{align} \label{eq:Lyapunov95q95slow} \mathbb{E}_t[\mathcal{L}_q(t,k+1)] \leq \left(1-c_{q,1}\alpha\right)\mathbb{E}_t[\mathcal{L}_q(t,k)] +c_{q,2}\frac{\beta^2}{\alpha} +c_{q,3}z_\beta^2\alpha^2, \end{align}\tag{68}\] where \(c_{q,1}=\frac{3\mu_{\min}\tau}{2m}\), \(c_{q,2}=\frac{32nm^2}{\mu_{\min}\tau (1-\gamma)^2}\), and \(c_{q,3}=\frac{84}{(1-\gamma)^2}\).

Iterating 68 , we have for all \(k\geq z_\beta\) that \[\begin{align} \mathbb{E}_t[\mathcal{L}_q(t,k)] \leq\,& (1-c_{q,1}\alpha)^k\mathcal{L}_{q,\max} +\frac{c_{q,2}\beta^2}{c_{q,1}\alpha^2} +\frac{c_{q,3}z_\beta^2\alpha}{c_{q,1}}, \label{solving95recursion95q95slow} \end{align}\tag{69}\] where \(\mathcal{L}_{q,\max}=\frac{8nm}{(1-\gamma)^2}\). Using the previous inequality in 67 , and using \(\beta/\alpha\leq c_{q,1}/2\), which implies \((1-c_{q,1}\alpha)^{1/2}\leq 1-\beta\), we have \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k+1)] \leq\,& (1-\beta)\mathbb{E}_t[\mathcal{L}_\pi(t,k)] +4\beta\mathcal{L}_{\text{sum}}(t) +\frac{12m\tau\beta}{1-\gamma} +2\Bar{L}_\tau \beta^2\\ &+c_\pi\beta \left[ (1-\beta)^k\mathcal{L}_{q,\max}^{1/2} +\frac{c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha} +\frac{c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}} \right]. \end{align}\] Iterating the previous inequality gives \[\begin{align} \mathbb{E}_t[\mathcal{L}_\pi(t,k)] \leq\,& (1-\beta)^k(\mathcal{L}_{\pi,\max}+c_\pi\beta k\mathcal{L}^{1/2}_{q,\max}) +4\mathcal{L}_{\text{sum}}(t) +\frac{c_\pi c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha} +\frac{c_\pi c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}}\nonumber\\ &+\frac{12m\tau}{1-\gamma} +2\Bar{L}_\tau \beta. \label{recursion95pi95before} \end{align}\tag{70}\] Similarly, using 69 in 66 , and using \((1-c_{q,1}\alpha)^{1/2}\leq 1-\beta\), we have \[\begin{align} \mathbb{E}_t[\mathcal{L}_{\text{sum}}(t+1)] \leq\,& \gamma\mathcal{L}_{\text{sum}}(t) +2(1-\beta)^K\mathcal{L}_{q,\max}^{1/2} +\frac{2c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha} +\frac{2c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}}. \end{align}\] Taking total expectation on both sides and iterating, since \(\mathcal{L}_{\text{sum}}(0)\leq 2/(1-\gamma)\) by Lemma 27, we have \[\begin{align} \mathbb{E}[\mathcal{L}_{\text{sum}}(t)] \leq\,& \frac{2\gamma^t}{1-\gamma} +\frac{2\mathcal{L}_{q,\max}^{1/2}}{1-\gamma}(1-\beta)^K +\frac{2c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}(1-\gamma)\alpha} +\frac{2c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}(1-\gamma)}. \label{solving95recursion95vsum} \end{align}\tag{71}\]

Using 71 , 70 , and 69 in 65 , we obtain \[\begin{align} \mathbb{E}[\mathcal{L}_v(t+1)] \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +4\mathbb{E}[\mathcal{L}_{\text{sum}}(t)] +2\mathbb{E}[\mathcal{L}_q^{1/2}(t,K)] +4\mathbb{E}[\mathcal{L}_\pi(t,K)] +6\tau \log(m)\\ \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +\frac{40\gamma^t}{1-\gamma} +\frac{40\mathcal{L}_{q,\max}^{1/2}}{1-\gamma}(1-\beta)^K +\frac{40c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}(1-\gamma)\alpha}\\ &+\frac{40c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}(1-\gamma)} +4(1-\beta)^K(\mathcal{L}_{\pi,\max}+c_\pi\beta K\mathcal{L}^{1/2}_{q,\max})\\ &+\frac{4c_\pi c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha} +\frac{4c_\pi c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}} +\frac{48m\tau}{1-\gamma} +8\Bar{L}_\tau \beta\\ &+2(1-\beta)^K\mathcal{L}_{q,\max}^{1/2} +\frac{2c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha} +\frac{2c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}} +6\tau \log(m)\\ \leq\,& \gamma \mathbb{E}[\mathcal{L}_v(t)] +\frac{40\gamma^t}{1-\gamma} +\frac{7 c_\pi c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha} +\frac{7 c_\pi c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}}\\ &+(1-\beta)^K \left( 4\mathcal{L}_{\pi,\max} +4c_\pi\beta K\mathcal{L}^{1/2}_{q,\max} +\frac{42\mathcal{L}_{q,\max}^{1/2}}{1-\gamma} \right) +\frac{54m\tau}{1-\gamma} +8\Bar{L}_\tau \beta, \end{align}\] where the last inequality follows from \(c_\pi\geq 16/(1-\gamma)^2\). Iterating the previous inequality and using \(\mathcal{L}_v(0)\leq 4/(1-\gamma)\) by Lemma 27, we obtain \[\begin{align} \mathbb{E}[\mathcal{L}_v(t)] \leq\,& \frac{4\gamma^t}{1-\gamma} +\frac{40t\gamma^{t-1}}{1-\gamma} +\frac{7 c_\pi c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha(1-\gamma)} +\frac{7 c_\pi c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}(1-\gamma)}\nonumber\\ &+\frac{1}{1-\gamma}(1-\beta)^K \left( 4\mathcal{L}_{\pi,\max} +4c_\pi\beta K\mathcal{L}^{1/2}_{q,\max} +\frac{42\mathcal{L}_{q,\max}^{1/2}}{1-\gamma} \right) +\frac{54m\tau}{(1-\gamma)^2} +\frac{8\Bar{L}_\tau \beta}{1-\gamma}\nonumber\\ \leq\,& \frac{4\gamma^t}{1-\gamma} +\frac{40t\gamma^{t-1}}{1-\gamma} +\frac{7 c_\pi c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha(1-\gamma)} +\frac{7 c_\pi c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}(1-\gamma)}\nonumber\\ &+\frac{175n^{1/2}m^{3/2}K}{(1-\gamma)^3\tau}(1-\beta)^K +\frac{54m\tau}{(1-\gamma)^2} +\frac{8\Bar{L}_\tau \beta}{1-\gamma}, \label{recursion95Lv95slow} \end{align}\tag{72}\] where the last line follows from \(\mathcal{L}_{q,\max}\leq \frac{8nm}{(1-\gamma)^2}\) and \(\mathcal{L}_{\pi,\max}\leq \frac{4}{1-\gamma}+2\tau \log(m)\).

Using 69 , 71 , and 72 together with Lemma 28, we have \[\begin{align} \mathbb{E}[\text{NG}(\pi_{T,K}^1,\pi_{T,K}^2)] \leq\,& \frac{4}{1-\gamma} \mathbb{E}\left[ 2\mathcal{L}_{\text{sum}}(T) +\mathcal{L}_v(T) +\mathcal{L}_\pi(T,K) +2\tau \log(m) \right]\\ \lesssim\,& \frac{T\gamma^{T-1}}{(1-\gamma)^2} +\frac{c_\pi c_{q,2}^{1/2}\beta}{c_{q,1}^{1/2}\alpha(1-\gamma)^2} +\frac{c_\pi c_{q,3}^{1/2}z_\beta\alpha^{1/2}}{c_{q,1}^{1/2}(1-\gamma)^2}\\ &+\frac{n^{1/2}m^{3/2}}{(1-\gamma)^4\tau}K(1-\beta)^K +\frac{m\tau}{(1-\gamma)^3} +\frac{m^2\beta}{\tau(1-\gamma)^4}\\ \lesssim\,& \frac{T\gamma^{T-1}}{(1-\gamma)^2} +\frac{n^{1/2}m^{5/2}}{\mu_{\min}\tau^2(1-\gamma)^4}\frac{\beta}{\alpha} +\frac{m^{3/2}z_\beta\alpha^{1/2}}{\mu_{\min}^{1/2}\tau^{3/2}(1-\gamma)^4}\\ &+\frac{n^{1/2}m^{3/2}}{(1-\gamma)^4\tau}K(1-\beta)^K +\frac{m\tau}{(1-\gamma)^3} +\frac{m^2\beta}{\tau(1-\gamma)^4}, \end{align}\] where the last line follows from the definitions of \(c_{q,1}\), \(c_{q,2}\), \(c_{q,3}\), and \(c_\pi\).

In view of the previous inequality, to achieve \(\mathbb{E}[\text{NG}(\pi_{T,K}^1,\pi_{T,K}^2)]\leq \epsilon\), it is sufficient to choose \(T=\tilde{\mathcal{O}}(1)\), \(\tau=\Theta(\epsilon)\), \(\alpha=\tilde{\Theta}(\epsilon^5)\), and \(\beta=\tilde{\Theta}(\epsilon^8)\), and then take \(K=\tilde{\mathcal{O}}(\epsilon^{-8})\). Under this choice, all terms in the preceding bound are at most order \(\epsilon\). It follows that the total sample complexity is \(TK=\tilde{\mathcal{O}}(\epsilon^{-8})\).

9.6 Proof of Corollary 4↩︎

The following proof idea was previously used in [41] to show the rationality of their decentralized \(Q\)-learning algorithm.

Observe that Theorem 4 can be generalized to the case where the reward is corrupted by noise. Specifically, suppose that player \(i\) takes action \(a^i\) and player \(-i\) takes action \(a^{-i}\). Instead of assuming player \(i\) receives a deterministic reward \(R_i(s,a^i,a^{-i})\), we assume that player \(i\) receives a random reward \(r^i(s,a^i,a^{-i},\xi)\), where \(\xi\in \Xi\) is a random variable with distribution \(\mu_\xi(s)\) and is independent of everything else. The proof is identical as long as \(r^i+r^{-i}=0\) and the reward is uniformly bounded, i.e., \(\max_{s,a^i,a^{-i},\xi}|r^i(s,a^i,a^{-i},\xi)|<\infty\).

Now consider the case where player \(i\)’s opponent follows a stationary policy \(\pi^{-i}\). We incorporate the randomness of player \(-i\)’s action into the model and introduce a fictitious opponent with only one action \(a^*\). In particular, let the random reward function be defined as \(\hat{r}^i(s,a^i,a^*,A^{-i})=R_i(s,a^i,A^{-i})\) for all \((s,a^i)\), where \(A^{-i}\sim \pi^{-i}(\cdot\mid s)\), and let \(\hat{p}(s'\mid s,a^i,a^*)=\sum_{a^{-i}\in\mathcal{A}^{-i}}\pi^{-i}(a^{-i}\mid s)p(s'\mid s,a^i,a^{-i})\). Now the problem can be reformulated as player \(i\) playing against the fictitious player with a single action \(a^*\), with reward function \(\hat{r}^i\) and transition probabilities \(\hat{p}\). Using the same proof for Theorem 4, we obtain the desired finite-sample bound.

9.7 Statements and Proofs of Supporting Lemmas↩︎

Recall that \(\Pi_{\Bar{\epsilon}}=\{(\mu^1,\mu^2)\mid \min_{a^1}\mu^1(a^1)\geq \Bar{\epsilon}/m,\min_{a^2}\mu^2(a^2)\geq \Bar{\epsilon}/m\}\).

The proofs of Lemma 34 (1) and (2) are identical to those of Lemma 5 (1) and (2), and therefore are omitted. Here, we prove Lemma 34 (3).

For any \(q^1\in\mathbb{R}^{m_1}\) and \(q^2\in\mathbb{R}^{m_2}\), using the formula of the gradient of \(V_X(\cdot,\cdot)\) from 35 and the first-order optimality condition of the softmax map in inner-product form, we have \[\begin{align} &\langle \nabla_1V_X(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(X_1\mu^2)\rangle\\ =\,& \tau\langle \nabla \nu(\sigma_\tau(X_1 \mu^2))- \nabla \nu(\mu^1), \sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(X_1\mu^2) \rangle\\ &+ ( \sigma_\tau(X_2 \mu^1)-\mu^2)^\top X_2 ( \sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(X_1\mu^2) )\\ \leq\,& \tau\|\nabla \nu(\sigma_\tau(X_1 \mu^2))- \nabla \nu(\mu^1)\|_2 \|\sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(X_1\mu^2) \|_2\\ &+ \|\sigma_\tau(X_2 \mu^1)-\mu^2\|_2 \|X_2\|_2 \| \sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(X_1\mu^2)\|_2\\ \leq\,& 2\left(\frac{m\tau}{\Bar{\epsilon}}+\|X_2\|_2\right) \left( \| \sigma_\tau^{\bar{\epsilon}}(q^1)-\sigma_\tau(q^1)\|_2 +\| \sigma_\tau(q^1)-\sigma_\tau(X_1\mu^2)\|_2 \right)\\ \leq\,& 2\left(\frac{m\tau}{\Bar{\epsilon}}+\|X_2\|_2\right) \left( 2\Bar{\epsilon} +\frac{1}{\tau}\| q^1-X_1\mu^2\|_2 \right), \end{align}\] where the second last inequality follows from the \(m/\Bar{\epsilon}\) – smoothness of \(\nu(\cdot)\) on \(\Pi_{\Bar{\epsilon}}\) and the fact that the softmax function is \(\frac{1}{\tau}\) – Lipschitz continuous with respect to \(\|\cdot\|_2\) [63], and the last inequality follows from Lemma 21. Similarly, for any \(q^2\in\mathbb{R}^{m_2}\), \[\begin{align} \langle \nabla_2V_X(\mu^1,\mu^2),\sigma_\tau^{\bar{\epsilon}}(q^2)-\sigma_\tau(X_2\mu^1) \rangle \leq 2\left(\frac{m\tau}{\Bar{\epsilon}}+\|X_1\|_2\right) \left( 2\Bar{\epsilon} +\frac{1}{\tau}\| q^2-X_2\mu^1\|_2 \right). \end{align}\] The result follows by adding the previous two inequalities. 0◻

10 Numerical Simulations↩︎

We conduct numerical simulations to investigate the impact of choosing different \(\tau\), which is used to define the softmax operator in Algorithms 1 and 3. Our theoretical results indicate that there is an asymptotically non-vanishing bias due to using a positive \(\tau\). Intuitively, since a softmax policy always has strictly positive entries while a Nash equilibrium policy can have zero entries, we cannot, in general, expect the Nash gap to converge to zero. To demonstrate this phenomenon, consider the following example of a zero-sum matrix game. Let \[\begin{align} R_1=\begin{bmatrix} N & 1 & -1\\ -1 & 0 & 1\\ 1 & -1 & 0 \end{bmatrix} \end{align}\] be the payoff matrix for player \(1\), and let \(R_2=-(R_1)^{\top}\), where \(N>0\) is a tunable parameter. Note that this matrix game has a unique Nash equilibrium, which goes to the joint policy \(\pi^1=(1/3,2/3,0)\), \(\pi^2=(0,2/3,1/3)\) as \(N\rightarrow\infty\). In our simulations, we use constant stepsizes \(\alpha_k\equiv 0.5\) and \(\beta_k\equiv 0.01\) and run Algorithm 1 for \(100\) trajectories (each has \(K=2000\) iterations). Then, we plot the average Nash gap (averaged over the \(100\) trajectories) as a function of the number of iterations \(k\) in Figure 7 for different temperatures \(\tau\). To enable a fair comparison, we use the normalized \(q\)-function to compute the softmax, that is, instead of directly using \(\sigma_\tau(q_k^i)\) in Algorithm 1, we use \(\sigma_\tau(q_k^i/\|q_k^i\|_2)\). As we can see in Figure 7, as \(\tau\) increases, the asymptotic error also increases, which is consistent with our theoretical results.

References↩︎

---

1. IE, Purdue University. Email: chen5252@purdue.edu.↩︎

2. ECE, University of Maryland, College Park. Email: kaiqing@umd.edu.↩︎

3. CMS, Caltech. Email: mazumdar@caltech.edu.↩︎

4. EECS, MIT. Email: asuman@mit.edu.↩︎

5. CMS, Caltech. Email: adamw@caltech.edu.↩︎

6. Throughout the paper, we focus on such a notion of Markov stationary Nash equilibrium, and will refer to it as Nash equilibrium for short.↩︎