A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
Authors: Zaiwei Chen
Kaiqing Zhang
Eric Mazumdar
Asuman E. Ozdaglar
Adam Wierman
Venue: NeurIPS 2023 poster (2023)
Keywords: Zero-sum stochastic games
payoff-based independent learning
best-response-type dynamics
finite-sample analysis
TL;DR: We study best-response independent learning dynamics in zero-sum matrix games and stochastic games and provide finite-sample convergence guarantees.

Abstract: In this work, we study two-player zero-sum stochastic games and develop a variant of the smoothed best-response learning dynamics that combines independent learning dynamics for matrix games with the minimax value iteration for stochastic games. The resulting learning dynamics are payoff-based, convergent, rational, and symmetric between the two players. Our theoretical results present to the best of our knowledge the first last-iterate finite-sample analysis of such independent learning dynamics. To establish the results, we develop a coupled Lyapunov drift approach to capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.

A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
Zaiwei Chen Kaiqing Zhang', Eric Mazumdar', Asuman Ozdaglar', Adam Wierman'
CMS, Caltech, 'zchen458@caltech. edu, Inazuddar@calteed edu, adu,''ada adamw@caltech edu FECE & ISR, University of Maryland, College Park, kaiqing@umd. edu EEECS, MIT, asumanâmit.. edu
Abstract
this work, we study two-player zero-sum stochastic games and develop a vari- ant of the smoothed best-response learning dynamics that combines independent learning dynamics for matrix games with minimax value iteration for stochastic games. The resulting learning dynamics and symmetric between the two players. Our theoretical results present to the best of our knowledge the first last-iterate sample analysis of such independent learning dynamics. To establish the results, we develop a coupled Lyapunov drift approach capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.
payoff- based, convergent, rational,
Introduction
Recent years have seen remarkable successes in reinforcement learning (RL) in a variety of appli- cations, such board games [1], autonomous driving [2], robotics [3], and city navigation [4]. A common feature of these applications is that there are multiple decision makers interacting with each other in common environment. Although empirical successes have shown the potential of multi-agent reinforcement learning (MARL) [5, 6]. the training of MARL agents is largely based on heuristics and parameter tuning and, therefore, is not always reliable. In particular, many practical MARL algorithms are directly extended from their single-agent counterparts and lack guarantees because of the adaptive strategies of multiple agents.
growing literature seeks to provide theoretical insights to substantiate the empirical success of MARL and inform the design of efficient and provably convergent algorithms. Work along these lines can be broadly categorized into work on cooperative MARL where agents seek to reach a common goal [7-10], and work competitive MARL where agents have individual (and possibly misaligned) objectives [11-22]. While some earlier work focused on providing guarantees on the asymptotic recent ones share increasing interest in understanding the tnite-time//ample behavior. This follows from a line of recent advances in establishing finite-sample guarantees of single-agent RL algorithms, see e.g. [23-26] and many others.
convergence, the
In this paper, we focus on the benchmark setting of two-player' zero-sum stochastic games, and develop best-response-type learning dynamies with provable finite-sample guarantees. Crucially, our learning dynamics are independent (requiring no coordination between the agents in learning) and rational (each agent will converge to the best response to the opponent if the opponent plays an (asymptotically) stationary policy [27]). and therefore capture learning in settings with multiple game-theoretic agents. Indeed, learning dynamics with self-interested agents should information communication or coordination among agents. Furthermore, we focus on the more challenging but practically relevant setting of payoff-based learning, where each agent can only
enforce
Hereafter, we may use player and agent interchangcably.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

observe their realized payoff at each stage, without observing the policy or even the action taken by the opponent. For learning dynamies with such properties, we establish the best of our knowledge the first last-iterate finite-sample guarantees. We detail our contributions as follows.
1.1 Contributions
We first consider zero-sum matrix games and provide the last-iterate finite-sample guarantees for the smoothed best-response dynamics proposed in [28]. Then, we extend the algorithmic idea to the setting of stochastic games and develop an algorithm called value iteration with smoothed best-response dynamics (VI-SBR) that also enjoys last-iterate finite-sample convergence.
Two-Player Zero-Sum Matrix Games. We start with the smoothed best-response dynamics in [28] and establish the last-iterate finite-sample bounds when using stepsizes of various decay rates. The result implies a sample complexity of (c- in terms of the last iterate to find the Nash distribution [29], which is also known the quantal response equilibrium in the literature [30]. To our knowledge, this is the first last-iterate finite-sample result for best-response learning dynamics that are payoff-based, rational, and symmetric in zero-sum matrix games.
Two- Player Zero-Sum Stochastic Games. Building on the algorithmic ideas for matrix games, we develop best-response-type learning dynamics for stochastic games called VI-SBR, which uses a single trajectory of Markovian samples. Our learning dynamics consist of two loops and can be viewed as combination of the smoothed best-response dynamics for an induced auxiliary matrix game (conducted in the inner loop) and an independent way of performing minimax value iteration (conducted in the outer loop). In particular, in the inner loop, the iterate of the outer loop, i.e., the value function, is fixed, and the players learn the approximate Nash equilibrium of an auxiliary matrix game induced by the value function; then the outer loop is updated by approximating the minimax value iteration updates for the stochastic game, with only local information.
We establish the last-iterate finite-sample bounds for VI-SBR when using both constant stepsizes and diminishing stepsizes of ((1/k) decay rate. To the best of our knowledge, this appears to be the first last-iterate unite-sample analysis of best-response- type independent learning dynamics that are convergent and rational for stochastic games. Most existing MARL algorithms are either symmetric across players, but not mnyoff-based c.g., [31-35], or not symmetric and thus not rational, c.g.. [14, 36-38), or do not have last-iterate finite-time/sample guarantees, e.g., [39, 15, 40].
1.2 Challenges & Techniques
The main challenge in analyzing our learning dynamics that it maintains multiple sets of stochastic iterates and updates them in coupled manner. To overcome this challenge, we develop novel coupled Lyapunov drift approach. Specifically, we construct a Lyapunov function for each set the stochastic iterates and establish Lyapunov drift inequality for each. We then carefully combine the coupled Lyapunov drift incqualities to establish the finite-sample bounds. Although a more detailed analysis is provided in the appendices, we briefly give an overview of the main challenges in analyzing the payoff- based independent learning dynamics in stochastic games, as well as our techniques to overcome them.
Markovian Noise. The fact that our learning dynamics are payoff-basee based presents major challenges in handling the stochastic errors in the update. In particular, due to the best-response nature of the dynamics, the behavior policy for sampling becomes time-varying. In fact, the sample trajectory used for learning forms tine-inhomogeneous Markov chain. This makes it challenging to establish finite-sample guarantces, as iime-inhomoeeneity prevents us from directly exploiting the uniqueness of stationary distributions and the fast mixing of Markov chains. Building on existing work [23, 24, 41, 42], we overcome this challenge by tuning the algorithm parameters (in particular, the stepsizes) and developing refined conditioning argument.
Time-In Inhomogeneous
Non-Zero-Sum Payoffs Due to Independent Learning. As illustrated in Section 1.1, the inner loop of VI-SBR is designed to approximately learn the Nash equilibrium of an auxiliary matrix game induced by the value functions for the two players, which we denote by of and vZ. where i is the iteration index of the outer loop. Importantly, the value functions of and of are maintained individually by players and 2, and therefore do not necessarily satisfy of + of = 0 due to independent learning. As a result, the auxiliary matrix game from the inner loop does not necessarily

---

admit a vero-sum structure during learning. The error induced from such non-zero-son sum structure appears in existing work [15, 43], and was handled by designing a novel truncated Lyapumov 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 ||a + of al 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 auxiliary matrix game,
Coupled Lyapunov Drift Inequalities, In the existing literature of stochastic iterative algorithms [44, 24, 45, 46], when using Lyаpunov approach for finite-sample analysis, once the Lyapunov drift inequality is established, the maite- bound follows straightforwardly by repeatedly invoking the result. However, since our learning dynamics (for stochastic games) maintain multiple sets of stochastic iterates and update them in coupled manner, the Lyapunov drift inequalities we establish are also highly coupled. Decoupling these Lyapunov inequalities is a major challenge. 'oo overcome it, we develop a systematic approach for decoupling, which crucially relies on a bootstrapping argument. Specifically, we first use the Lyapunov inequalities in a direct way to establish crude bound for each Lyapunov function. Then, we substitute the crude bounds back into the Lyapunov drift inequalities to obtain tighter bounds. See Appendix B.4 for more detailed illustration of our decoupling procedure.
1.3 Related Work
Due to space constraints, here we only discuss related work in independent learning in matrix games and stochastic games, and single-agent RL. See Appendix A for a more detailed literature review.
Independent Learning in Matrix Games. Independent learning has been well-studied in the literature on learning in matrix games. Fictitious play (FP) [47] may be viewed as the earliest one of this kind, and its convergence analysis for the zero-sum setting is provided in [48]. Smoothed versions of FP have been developed [49, 50] to make the learning dynamics consistent [51, 52]. It was shown that the behavior of smoothed FP is captured by an ODE known the smoothed best-response dynamics, which were also studied extensively in the literature [53]. Note that the Lyapunov function used to study the smoothed best-response dynamics is the regularized Nash gap [54, 53, 29], variant basedd of which is also used in our Lyapunov framework. To make the learning dynamics [28] developed a two time-scale variant of the smoothed best-response dynamics and established the asymptotic convergence. Moreover, no-regret learning algorithmss, extensively studied in online learning, can also be used as independent learning dynamics for matrix games [55]. It is known that they are both convergent and rational by the definition in [27], and are usually implemented in symmetric way. See [55] for a detailed introduction to no-regret learning in games.
Independent Learning in Stochastic Games. For stochastic games, independent and symmetric policy gradient methods have been developed in recent years, mostly for the case of Markov potential games [18, 19, 56). The zero-sum case is more challenging since there is no single Lyapunov function to capture the learning dynamics (which is why we need to develop a coupled Lyapunov approach with multiple Lyapunov functions), such as the potential function in Markov potential games. For non-potential game settings, symmetric variants of policy gradient methods have been proposed, but have only been studied under the full-information setting without finite-sample guarantees [31, 32, 57, 33-35], with the exception of [58, 59]. However, the learning algorithm in [58] requires some coordination between the players when sampling, and is thus not completely independent; that in [59] is extragradient- based and needs some stage- based sampling process that also requires coordination across players. Best-response-type independent learning for stochastic games has been studied recently [39, 15, 43, 60, 40, 61, 62], with [15, 43, 40, 61] tackling the zero-sum setting. However, only asymptotic convergence was established in these works, which motivated this work.
Finite-Sample Analysis in Single-Agent RL. The most related works (in single-agent RL) to our paper are those that perform finite-sample analysis for RL in infinite-horizon discounted Markov decision processes following single trajectory of Markovian samples. See [63, 23, 41, 24-26, 64- 67, 10] and the references therein. Among these works, [23, 24] established Smite-sample bounds for temporal difference (TD)-leamiig (with linear function approximation), and [25, 64, 65] established finite-sample bounds for Q-learning. In both cases, the behavior policy for sampling is a stationary policy. For non-stationary behavior policies as we consider, [41] established finite-sample bounds for SARSA, an on-policy variant of Q-learning, and [10] provided finite-sample bounds for off- policy actor-critic, which is established based on a general framework of contractive stochastic approximation with time- inhommgeeooe Markovian noise.
3

---

2 Zero-Sum Matrix Games
We begin by considering zero-sum matrix games. This section introduces algorithmic and technical ideas that are important for the setting of stochastic games. For E {1,2), let A' be the finite action
space of player i, and let R2 E [lA"|x|AA" (where -i denotes the index of player i's opponent) be the payoff matrix of player i. Note that in a zero-sum game we have R₃ + RR = O. Since there are finitely many actions for each player, assume without loss of generality that max,, .a [R, (a' a²) s 1. Furthermore, we denote Amax I |.44).
The decision variables here are the policies n' E A(A"), i E (1,2), where A(4') denotes the probability simplex supported on A'. Given a joint policy (π' , the expected reward received by player is BA-=-r-A--~ to maximize their rewards against their opponents. Unlike in the single-agent 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 the regularized Nash gap as measurements of the performance of the learning dynamics, as formally defined below.
(A', A-1] = (T²) R where i E [1, Both players aim
Definition 2.1 (Nash Gap in Matrix Games). Given joint policy (T², the Nash gap NG 2) is defined as NG(TT, x²) - 2im1, maX)" - T²) RGT
Note that NG -²) ) if and only if (,?,=²)) is in Nash equilibrium of the matrix game (which may not be unique), in which no player has the incentive to change its policy.
Definition 2.2 (Regularized Nash Gap in Matrix Games). Given joint policy π = (m π and a constant т > 0, the entropy-regularized Nash gap NG= x²) is defined as NG- x
Ei=12 (max defined as v( = - E (a'))
x' RAT + Tu(#')= TT(TT)) } where v(-) is the entropy function
(a()' for i {1.2}.
A joint policy (x² T²) satisfying (x T²) = 0 is called the Nash distribution [29] or the quantal response equilibrium [30], which, unlike Nash equilibria, is unique in zero-sum matrix games. As т approaches 0, the corresponding Nash distribution approximates a Nash equilibrium [68].
2.1 The Learning Dynamics in Zero-Sum Matrix Games
We start by presenting in Algorithm 1 (from the perspective of player i, where {1,2}) the independent learning dynamics for zero-sum matrix games, which was first proposed in [28]. Given O, we use IR A'l + R14' for the softmax function with temperature that [a=(a')] exp(a'(a')/ E exp(d'("')/1 (7')/T) for all a' A', gf Rl4" and i (1,
Algorithm 1 Independent Learning Dynamics in Zero- Sum Matrix Games
Input: Integer K, initializations áó e R144 and xi Uni.
2: for k 0, 0.... K - do
3: mh+1 = _ + 3h (ar(()) )(.)
4: Play AG ~ T (against ), and receive reward R2 (Aj, AF')
5: (a*) of(aa) + an (ai=A{) (R. AF") (At)) for all at A'
6:
end for
To make this paper ceff-contained, we next provide a detailed interpretation of Algorithm 1, which also motivates our algorithm for stochastic games in Section 3. At high level, Algorithm 1 can be viewed as discrete and smoothed variant of the best-response dynamics, where each player constructs an approximation of the best response its opponent's 's policy using the q-function. The update for the q-function is in the spirit of the TD-learnin algorithm in RL [69].
The Policy Update. To understand the update equation for the policies (cf. Algorithm Line 3), consider the discrete version of the smoothed best-response dynamics:
T Tं. 3x (a.
(RATE") (a
=(), i E (1,2).
In Eq. (1), each player updates its policy of incrementally towards the smoothed best response to its opponent's 's current policy. While the dynamics in Eq. (1) provably converge for zero-sum matrix

---

games, see e.g., [70], implementing it requires player i to compute o, (R,TT'))) Note that o, (R involves the exact knowledge of the opponent's policy and the reward matrix, both of which cannot be accessed in payoff- hased independent learning. This leads to the update equation for the g-functions, which estimate the quantity R that is needed for implementing Eq. (1).
The q- F--Futtttin Update. Suppose for now that we are given a stationary joint policy π = (m',, x²). Fix E (1, the problem of player i estimating RT can be viewed policy evaluation problem, which is usually solved with TD-learning in RL [69]. Specifically, the two players repeatedly play the matrix game with the joint policy {(A), Al) I220. Then, player forms an estimate of R π through the following itcrative algorithm:
(m²) x²) and produce sequence of joint actions
(a') (a') + as (o'=A))) (R, A of (A)))
Va' A',
with an arbitrary initialization dó E R 1 where ag > 0 is the stepsize. To understand Eq. (2), suppose that of. converges to some T.. Then Eq. (2) should be "stationary" at the limit point q' in the sense that E () -() (a'=A')
- (AA))] = 0 for all a' E A'' which implies q' = R as desired. Although Eq. (2) is motivated by the case when the joint policy (m²,m²)) n²) is stationary, the joint policy T = ( m from Eq. (I) is time-varying. A natural approach to address this issue is to make sure that the policies evolve at slower time-scale compared to that of the q-functions, so that Tą is close to being stationary from the perspectives of qz.
Remark. In [28], where Algorithm was first proposed, the authors require 34 = o(aa) ) to establish the asymptotic convergence, making Algorithm I two time-scale algorithm. In this work, for finite-sample analysis and easier implementation, we update x and gf on single time scale with only a multiplicative constant difference in their stepsizes, i.e., 3e = Ca,3ay for some Ca.3 E (0, 1).
2.2 Finite-Sample Analysis
In this section, we present the finite-sample analysis of Algorithm 1 for the convergence to the Nash
distribution [29]. We consider using either constant stepsizes, i.e., 0g = a and 3 = 3 = Ca,90, or diminishing stepsizes with O(1/k) decay rate, i.e., Og = a/ + h) and 3r B/ + h) eo,sax/ (k- + h). Let f, [(Amax - 1) exp(2/r) +1]-1 and L,, = 7/L, + A2 Amax//T. The requirement
for choosing the stepsizes is stated in the following condition.
Condition 2.1. When using either constant or diminishing stepsizes, we choose T S 1, ag < 2 E
P < min(2, 128 max
and C / min
2V2
32
128.4
maR
We next state the sinite-sample bounds of Algorithm 1. See Appendix C for the proof.
Theorem 2.1. Suppose that both players follow the learning dynamics presented in Algorithm 1, and the stepsizes { and {3a] are chosen such that Condition 2.1 is satisfied. Then we have the following results.
(1) When using constant stepsizes, i.e., O4k = a and Bx = 3, we have
E[NG, xx Buc (1 (1- 3 K
64a
4 +L,
Ca.3
where Bin = 4 2r log (Amax) )+ + 2.Amax.
(2) When using ag = a/ + fi) and BE = =B/(k: + h), by choosing 3 > 4, we have
h
0/4
+ (6AeLL,3 + 512ea 1
E[NG, (T T < Bin
K +
Ca.3 K + h
The convergence bounds in Theorem 2.1 are qualitatively consistent with the existing results on the finite-sample analysis of general stochastic approximation algorithms [44, 46, 24, 65, 23, 42]. Specifically, when using constant stepsizes, the bound consists of a geometrically decaying term (known as the optimization error) and two constant terms (known the statistical error) that are proportional to the stepsizes. When using diminishing stepsizes with suitable hyperparameters, both the optimization error and the statistical error achieve O(1KK) rate of convergence.
5

---

Although Theorem 2.1 is stated in terms of the expectation of the regularized Nash gap. it implies the mean-square convergence of the policy iterates (# mÂ). To see this, note that the regularized Nash gap NG, ) has a unique minimizer, i.c., the Nash distribution and is denoted by (m..r: ()) In addition, fixing x' (respectively, n²), the function NG=(=', .-) (respectively, (G, π is T- strongly convex function with respect to x² (respectively, π²). See Lemma D.7 for proof. Therefore, by the quadratic growth property of strongly convex functions, we have
NG, ( p m = NG, x NG, =8) + NG, Ti) (T.,
7
2 [1| - , 113 + 1| 113)
As result, up to multiplicative constant, the convergence bound for EING, =1) implies convergence bound of |[ -- + E - 2,,1
Based on Theorem 2.1, we next derive the sample complexity of Algorithm 1 in the following corollary. See Appendix C.5 for the proof.
Corollary 2.1.1. Given E > 0, to achieve EING, (T m S e, the sample complexity is O(E-1)
To the best of our knowledge, Theorem 2.1 and Corollary 2.1.1 present the first last-iterate finite-
sample analysis of Algorithm [28]. Importantly, with only feedback in the form of realized payoffs, achieve a sample complexity of O(c-1) to find the Nash distribution. In general, for smooth and strongly monotone games, the lower bound for the sample complexity of payoff-based or zeroth-order algorithms is O 2) [71]. We have an improved O sample complexity due to the bilinear structure of the game (up to regularizer). In particular, with bandit feedback, the q-function is constructed as an efficient estimator for the marginalized payoff RoTg' which can also be interpreted as the gradient. Therefore, Algorithm enjoys the fast O sample complexity that is comparable to the first-order method [72].
The Dependence on the Temperature т. Although our finite-san mnite- bound enjoys the O(1/K)
rate of convergence, the stepsize ratio Ca. appears as Ca in the bound. Since Ca.8 = o(l,) (cf. Condition 2.1) and f, exponentially small in T, the finite-sample bound is actually exponentially large in - -- To illustrate this phenomenon, consider the update equation for the q-functions (cf. Algorithm Line 5). Observe that the q-functions are updated asynchronously because only one component (which corresponds to the action taken at time step k) of the vector-valued of is updated in the k-th iteration. Suppose that an action a² is never taken in the algorithm trajectory. which means that of (a") is never updated during learning. Then, in general, we cannot expect the convergence of of - Similarly, suppose that action is rarely taken in the learning dynamics, we would expect the overall convergence rate to be slow. Therefore, the finite-sample bound should depend on the quantity min. minosss K min,: (a"), which captures the exploration abilities of Algorithm 1. Due to the exponential nature of softmax functions, the parameter f, which we establish in Lemma C.2 as a lower bound of min (1.2) minoç&s K min,' =a()). is also exponentially small in т. This eventually leads to the exponential dependence in -- in the fnite-sample bound.
consequence of having such an exponential factor of -- in the sample complexity bound is that, if we want to have convergence to a Nash equilibrium rather than to the Nash distribution, the sample complexity can be exponentially large. To see this, note that the following bound holds regarding the Nash gap and the regularized Nash gap:
NG >² S (G, (m²) 27 log (Amax), A ( ;,,
which, after combining with Theorem 2. gives the following corollary. For simplicity of presentation, we only state the result for using constant stepsizes.
Corollary 2.1.2. Under the same conditions stated in Theorem 2.1 (1), we have
B[NG(T m Bin (1
B K + BL+
64x
2r log( Amax)-
Ca.8
The last term on the RHS of Eq. (4) can be viewed as the bias due to using smoothed best-response. In view of Eq. (4), to achieve [mT +) S e, we need 7 = O(e). Since Ca,9 appears in the denominator of our finite-sample bound and is exponentially small in 7, the overall sample complexity

---

for the convergence to Nash equilibrium can be exponentially large in e-!. In Appendix F, we conduct numerical experiments to investigate the impact of 7 on this smoothing bias.
In light of the discussion before Corollary 2. 2.1.2, the reason for such an exponentially large sample complexity for finding Nash equilibrium is due the limitation of using the softmax policies in smoothed best-response for exploration. We kept the softmax policy without further modification to preserve the "naturalness" of the learning dynamics, which is part of the motivation for studying independent learning in games [73]. A future direction of this work is to remove such an exponential dependence on by designing an improved exploration strategy.
3 Zero-Sum Stochastic Games
Moving to the setting of stochastic games, we consider an -horiite discounted two-player zero- sum stochastic game M = (S, .A?, p. R1. R2.7) where S is a finite state space, AA' (respectively. A²) is a fimite action space for player 1 (respectively, player 2), p represents the transition probabilities. in particular, p(s' aat, a²) is the probability of transitioning to state s' after player 1 taking action a and player 2 taking action a² simultaneously at state 8, Rı : S x AA' x A² + R (respectively, R2 S x A x A + R) is player I's (respectively, player 2's) reward function, and y E (0, 1) is the discount factor. Note that we have (s, a a²) + Rg(s, a², a²) = for all (s, "a²).. We assume without loss of generality that mäx,,a .a² [R (s, at, a²)l S 1, and denote Amax- max((A4), (44)).
Given a joint policy π = = where n² : :S + A(A"), i {1,2), we define the local function o E R lA'l of player as (s, a') E,, of (Sk, 44.44 So s, Ab a') for all (s,a'), where In addition, we define the global value function 2t Riis as of
the notation [-][]] indicate that the actions chosen according
to the joint policy
Ex-->"(--)) gg (s, At) for all s, and the expected value function U'(T', क x) E IR
as U'(T', (T)
Es.p. [o (S)], where Pa E (SS) is an arbitrary initial distribution on the states. The Nash gap in the case of stochastic games is defined in the following.
Definition 3.1 (Nash Gap in Zero-Sum Stochastic Games). Given a joint policy π = (a n²), the Nash gap NG( n² is defined as NG x²) Ei=12 (maxş. (A',, x- U'' ()).
Similar to the matrix-game setting, a joint policy π = ( 7 satisfying NG(=1,,7) n²2 = 0 is called a Nash equilibrium, which may not be unique.
Additional Notation. In what follows, we will frequently work with the real vectors in |S |S and IR. S) A'I1-- where E (1, To simplify the notation, for any x E R[ we use ar(s) to denote the | (A matrix with the (a', aaa")-ttt entry being a1ss a', a a). For any y E IR (11,41,, we use ys)) denote the |A4' dimeensooal vector with its a'-hh entry being y(s, at).
3.1 Value Iteration with Smoothed Responee Dynamies
Our learning dynamics for stochastic games (cf. Algorithm 2) build on the dynamics for matrix games studied in Section 2.1, with the additional incorporation of minimax value iteration, a well-known approach for solving zero-sum stochastic games [74).
Algorithmic Ideas. To motivate the learning dynamics, we first introduce the minimax value iteration. For E {1, let T I + "|AA""1-"" be an operator defined as
T'V)(s, a'as,aa,-=))) = Rs(s, a + 7E (((S)) So 3, Ab -áj=a'aa A' - =a
for all (s,a', 1) and R Given X R |A $1, we define val' RIA'IXIA R
val' (x))
max min {4-2) X X = min max (( EAAA 1)
{( 111
EA (EA(())
Then, the minimax Bellman operator B R + SS| defined as (B)) = vat' (T (Ti())))) (v)(
for all s E S, where (v)(ss) is an [A'] x |Aー matrix according to our notation. It is known that the operator (-) is a y - contraction mapping with respect to the norm [74], hence it admits a unique fixed point, which we denote by vç.
7

---

A common approach for solving sumo-sum stochastic games is to first implement the minimax value iteration f/+1 (ut) until (approximate) convergence to oi [75], and then solve the matrix for each state s to obtain an (approximate) game ma mink fEALA ( (1))
Nash equilibrium policy. However, implementing this algorithm requires complete knowledge of the underlying transition probabilities. Moreover, since it is an off- off-policy algorithm, the output is independent of the opponent's 's policy. Thus, it is not rational by the definition in [27]. To develop model-free and rational learning dynamics, let us first rewrite the minimax value iteration:
e = 0, where 0(s)= = max min (4 " TT' (PEA(A)=-'EAE EAA((---)
V
(5)
where é IR is dummy variable. In view of Eq. (5), we need to solve a matrix game with payoff matrix T (v:) for each state and then update the value of the game to 2i_1 (s). In light of Algorithm I, we already know how to solve matrix games with independent learning. Thus, what remains to do is to combine Algorithm I with value iteration. This leads to Algorithm 2, which presented from player i's perspective, where i E (1,
Algorithm 2 Value Iteration with Smoothed Best-Response (VI-SBR) Dynamics
1: Input: Integers K and T, initializations og 0 E RlSI, hbo 0 e RI and Td.u(-1s)
(A") for all E S. 2: for = 0, 1.... ...
-T' - do
3: for == 1....... K-16 do
4:
(s) = (s) + Ba Bx (g) (s)) for all s S
5:
Play Ai. ~ n (1|St) (against AF and observe Sk+1 ~ p(- Sk. Ab, AE²)
6:
ui,4+108 (s, = vi. (8, a²) + an ((x.4))((8 (R.(Se, Al. ) + yot
li A1)) for all (s,a*)
7:
end for
for all E S 9: Su Sk. 1.+1.0 ki x and 11400
8: (s) = (s) gi
TiKK
10: end for
Algorithm Details. For each state the inner loop of Algorithm is designed to solve matrix game with payoff matrices (vp) (s) and (x) for each state E S, which reduces to Algorithm when (1) the stochastic game has only one state, and (2) vt = v² = O. However, in general, since in and of are independently maintained by players and 2, the quantity
(',))ss, +
Epls' ss (z) (s
is in general non-zero during learning. As a result, the auxiliary matrix game (with payoff matrices T (v)) and (2(x)) (s)) state that the inner loop of Algorithm designed solve is not necessarily a zero-sum matrix game, which presents a major challenge in the finite-sample analysis, as illustrated previously in Section 1.2.
The outer loop of Algorithm 2 is an "on-policy" variant of minimax value iteration. To see this, note that, ideally, we would synchronize off1 (s) with -ं.x (s) T (s), which is an approximation of [B (s) val' (s)) by design of our inner loop. However, player has no access to K in independent learning. Fortunately, the q-function L' is precisely constructed (8)=, (s), as illustrated in Section 2.1, which leads to the outer loop of
-
as an estimate of Algorithm 2. Algorithm Line 8, we set Sn = SK to ensure that the initial state of the next inner loop is the last state of the previous one; hence Algorithm 2 is driven by single trajectory of Markovian samples.
3.2 Finite-Sample Analysis
We now state our main results, which, to the best of our knowledge, provide the first last-iterate finite-sample bound for best-response-lyp payoff-based independent learning dynamics zero-sum stochastic games. Our results are based on the following assumption.
8

---

Assumption 3.1. There exists joint policy (TT m such that the Markov chain {Sk induced by Te irredueible and aperiodic.
One challenge in our finite-sampl sample analysis is that the behavior policies used for taking the actions are time-varying, due to the best-response nature of the dynamics. Most, if not all, existing finite- behavior policies assume that the induced
sample guarantees of RL algorithms under time-variine Markov chain of any policy, or any policy encountered along the algorithm trajectory, is uniformly geometrically ergodic [41, 76, 77,59, 59, 78 78-80J. Assumption 3.1 is weaker, since it assumes only the existence of one policy that induces an irreducible and aperiodic Markov chain.
We consider using either constant stepsizes, i.e., 0% = and 3x = 3 - Ca, or diminishing
stepsizes of O(1/k) decay rate, i.e., ag a/(k + h) and Bx = 3/(k+ = Co, sar + h1), where
Ca.8 E (0, 1) is the stepsize ratio. In the stochastic- -amee setting, we redefine l, = [1 + (Amax
1) exp(2/[(1 - -)]]]]]]] which, analogous to the matrix-gamt setting, is a uniform lower bound on the entries of the policies generated by Algorithm 2 (cf. Lemma D.1). We next state our requirement for choosing the stepsizes.
Condition 3.1. When using either constant or diminishing stepsizes, we choose T S 1/(11 -) and 1 Cr (1-(1-)) -.-2r((1-7))) where o, x 4 the stepsize ratio Ca to satisfy Ca. S min 600, [S| Amax' 34 S A mas 144.4 ias
and Lp > O are defined in Appendix B.3. In addition, when using O/ a and BN: = 8, we require < 1/c, and 3 < 1, and when using ag a/(k: k + h) and 3x = B/(k + h), we require? B = 4. 1/ c/., and h > 1 such that ag 1/c, and Bo 1.
We next state the finite-sampe sample bound of Algorithm 2. For simplicity of presentation, we use S b to mean that there exists an absolute constant e > 0 such that a S. bc.
Theorem 3.1. Suppose that both players follow Algorithm 2, Assumption 3. is satisfied, and the stepsizes } and {8x} satisfy Condition 3.1. Then, we have the following results.
(1) When using constant stepsizes, there exists 23 = O(log(1/3)) such that the following inequality holds as long as K
Zg:
A T
11 11+7
T-1
A max LinK -20)
B
25
EING (1 2
1
-(1 7)3
2
T(1 - 7)1
:1
|S] Amax
loog (Amax)
+
20a 1/2
7) C
7)
Em
where Lin (I-7) + 2r (Ama))))) + Amax
4
(1-2)²
(2) When using Og = a/(k + h) and Bx = B/ + h). there exists ko > 0 such that the the following
inequality holds as long as K 2 ko:
E[NG(T x
A2 A2mnTT T
1 (1+
T-1 Lan A
a
ak
1/2
7 (log(Amx))
T(1 - 7)3
2
- (1-7)a M Ca.9
1/2
71-
where 2K = (K))
Remark. Analogous to [29, 15), our learning dynamics are symmetric between the two players the sense that there is time-scale separation between the two players, that is, they both implement the algorithm with the same stepsizes.
detailed proof sketch of Theorem 3.1 is provided Appendix B and the complete proof provided in Appendix D. Next, discuss the result in Theorem 3.1 (1). The bound in Theorem 3.1 (I) involves a value iteration error term εn an optimization error term Eg, a statistical error term Eg, and smoothing bias term E due to the use of smoothed best-response in the learning dynamics. Note that E would be the only error term we were able to perform minimax value iteration to solve
'hh proof works long as / 2. We here use
4 simplify the statement of the results.

---

the game. Since minimax value iteration converges geometrically, the term E1 also goes to zero at a geometric rate. Notably, the terms Eg and Eg are orderwise larger compared their matrix-gaa game counterparts, see Corollary 2.1.2. Intuitively, the reason is that the induced auxiliary matrix game (with payoff matrices T (s) and T (v}) that the inner loop of Algorithm 2 aims at solving does not necessarily have zero-sum structure (see the discussion in Section 3.1 after Algorithm 2). Consequently, the error due to such a "non-zero-sum" structure propagates through the algorithm and eventually undermines the convergence bound.
Recall that in the matrix game setting, we proved convergence to the Nash distribution (or the Nash equilibrium of the parrop-rrgularizer matrix game). In the stochastic-gant -ame setting, we do not have convergence to the Nash equilibrium of the is that, in order to have such a convergence, our outer loop should be designed to approximate the retropy-regularried minimax value iteration rather than the vanilla minimax value iteration as in Algorithm 2 Line 8. However, in the payoff-based setting, since each player does not even observe the actions of their opponent, it unclear how to construct an estimator of the entropy function of the opponent's ' policy, which is an interesting future direction to investigate.
stochastic game. The main reason
Although the transient terms in Theorem 3.1 enjoy a desirable rate of convergence (e.g.. geometric in T and 0(1 (11/K1/2) in K), the stepsize ratio C (which is exponentially small in 7) appears as ca.9 in the bound; see Theorem 3.1. Therefore, due to the presence of the smoothing bias (i.e., the term E on the RHS of the bound in Theorem 3.1 (1)), to achieve E[NG x x )1 S c, the overall sample complexity can also be exponentially large in e e-1 This is analogous to Corollary 2.1 for zero-sum matrix games. As illustrated in detail in Section 2, the reason here is due to the exploration limitation of using softmax as a means for smoothed best response, which we kept without further modification to preserve the naturalness of the learning dynamics. Removing such exponential factors by developing improved exploration strategies is immediate future direction.
Finally, we consider the case where the opponent of player i (where E {1,2]) plays the game with a stationary policy and provide a finite-sample bound for player i to find the best response.
Corollary 3.1.1. |Rationality" ] Given i E {1, suppose that player followw the learning dynamics presented in Algorithm 2, but its opponent player -i follows stationary policy, denoted by π - Then, we have max;: U U - (T S Öww1 (2 and W2 are constants that are exponential in r but polynpomial in (S], Amax, and 1/(1- -r).
T
+
Wa + +)), where wi KV/2
Intuitively, the reason that our algorithm is rational is that it performs an on-policy update in RL. In contrast to an off-policy update, where the behavior policy can be arbitrarily different from the policy being generated during learning (such as in Q-leamnng [81]), in the on on-policy update for games, each player is actually playing with the policy that is moving towards the best response to its opponent. As result, when the opponent's policy is stationary, reduces to single-agent problem and the player naturally finds the best response (also up to smoothing bias). This is an advantage of using symmetric and independent learning dynamics. One challenge of analyzing such on on-policy learning dynamics is that the behavior policy is time-varying.
4 Conclusion and Future Directions
In this work, we consider payoff- based independent learning for zero-sum matrix games and stochastic games. In both settings, we establish the last-iterate finite-sample guarantees. Our approach, i.e., the coupled Lyapunov drift argument, provides a number of tools that are likely to be of interest more broadly for dealing with iterative algorithms with multiple sets of coupled and stochastic iterates.
Limitations and Future Directions. As mentioned before Corollary 2.1 and after Theorem 3. the convergence bounds involve constants that are exponential in r r-1, which arise due to the use of the smoothed best response to preserve the naturalness of the learning dynamics. An immediate future direction of this work is to remove such exponential factors by designing better exploration strategies. In the long term, we are interested to see if the algorithmic ideas and the analysis techniques developed in this work can be used to study other classes of games beyond zero-sum stochastic games.
According to the definition in [27]. a dynamics being rational means that the player following this dynamics will converge to the best response to its opponent when the opponent uses an asymptotically stationary policy. Since we are performing finite-sand sample analysis. we assume the opponent's policy is stationary. because otherwise, the convergence rate (which may be arbitrary) of the opponent's policy will also impact the bound.
10

---

Acknowledgement
The authors would like to thank the anonymous reviewers for the helpful feedback, especially for pointing out several related references. ZC acknowledges support from the PIMCO Postdoctoral Fellowship. KZ acknowledges support from the Northrop Grumman Maryland Seed Grant Program. EM acknowledges support from NSF CAREER Award 22401 10. AW acknowledges support from NSF Grants CNS-2146814, CPS-2136197, CNS-2106403, and NGSDI-2105648.
References
[1] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550(7676)3354, 2017.
[2] Shai Shalev-Shwarts Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. Preprint arXiv: 160000321 2016.
[3] Shangding Gu, Jakub Grudzien Kuba, Yuanpei Chen, Yali Du, Long Yang, Alois Knoll, and Yaodong Yang. Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence, 119:103905, 2023.
[4] Piotr Mirowski, Matt Grimes, Mateusz Malinowski, Karl Moritz Hermann, Keith Anderson, Denis Teplyashin, Karen Simonyan, Andrew Zisserman, Raia Hadsell, et al. Learning to navigate in cities without a map. Advances in neural information processing systems, 31, 2018.
[5] Lucian Busoniu, Robert Babuska, Bart De Schutter, al. A comprehensive survey of multia- gent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 38(2):156-172, 2008
[6] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[7] Gürdal Arslan and Serdar Yüksel. Decentralized Q-Learning for Stochastic Teams and Games. IEEE Transactions on Automatic Control, 62(4):1555 1558, 2017.
[8] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference Machine Learning, pages 5867-5876, 2018
[9] Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control, pages 256-266. PMLR, 2020.
[10] Yizhou Zhang, Guannan Qu, Pan Xu, Yiheng Lin, Zaiwei Chen, and Adam Wierman. Global convergence of localized policy iteration in networked multi-agent reinforcement learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-51, 2023.
[11] Michael Littman. Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the Eleventh International Conference International Conference Machine Learning, ICML'94 '94 page 157-163, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc.
[12] Michael Lituman. Friend-or- Q-learning in general-sumt games. International Conference on Machine Learning, volume 1, pages 322-328, 2001.
[13] Junling Hu and Michael P Wellman. Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4(Nov):1003911666)))))) 2003.
[14] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances neural information processing systems, 33:5527-5540, 2020.

---

[15] Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decen- tralized Q-learning zero-sum Markov games. Advances Neural Information Processing Systems, 1a:18832--8344 2021.
[16] Yu Bai and Chi Jin. Provable self algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
[17] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous-movv Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674-3682. PMLR, 2020.
[18] Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: Stationary points, convergence, and sample complexity. Preprint arXiv:2 106,00 2021.
[19] Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Mihailo Jovanovic. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, pages 5166- 5220. PMLR, 2022.
[20] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning. pages 7001-7010. PMLR, 2021.
[21] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-A A simple, efficient, decentralized algorithm for multiagent RL. In ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022.
[22] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of Markov cquilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory, pages 4180-4234. PMLR, 2023.
[23] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite-time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691- 1692. PMLR, 2018.
[24] R Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Conference on Learning Theory, pages 2803-2830, 2019.
[25] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asyn- chronous Q-learning: Sharper analysis and variance reduction. IEEE Transactions on Informa- tion Theory, 68(1):448-477 473, 2021.
[26] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of contractive stochastic approximation using smooth convex envelopes. Ad- vances in Neural Information Processing Systems, 33, 2020.
[27] Michael Bowling and Manuela Veloso. Rational and convergent learning in stochastic games. In International Joint Conference on Artificial Intelligence, volume 17, pages 1021-1026, 2001.
[28) David S Leslie and Edmund J Collins. Convergent multiple-timescales reinforcement learning algorithms in normal form games. The Annals of Applied Probability, 1334):123 2003.
[29] David S Leslie and Edmund J Collins. Individual Q Qllemniig in normal form games. SIAM Journal on Control and Optimization, 44(2):495-514 2005.
[30] Richard D McKelvey and Thomas Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1);6 1995.
[31] Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:27952-27664, 2021.
[32] Shicong Cen, Yuejie Chi, Simon Shaolei Du, and Lin Xiao. Faster last-iterate convergence of policy optimization zero-sum Markov games. In The Eleventh International Conference on Learning Representations, 2023.
12

---

[33] Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, and Yu Bai. Policy opti- mization for Markov games: Unified framework and faster convergence. Advances in Neural Information Processing Systems, 15:21886-21880 2022.
[34] Sihan Zeng, Thinh Doan, and Justin Romberg. Regularized gradient descent ascent for two- player zero-sum Markov games. Advances in Neural Information Processing Systems, 35:34546- 34558. 2022.
[35] Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret minimiza- tion and convergence to equilibria in general-sum Markov games. In International Conference on Machine Learning, pages 9343-9373. PMLR, 2023.
[36] Yulai Zhao, Yuandong Tian, Jason Lee, and Simon Du. Provably efficient policy optimization for two-player zero-sum Markov games. International Conference on Artificial Intelligence and Statistics, pages 2736-27666 2761. PMLR, 2022.
[37] Kaiqing Zhang, Xiangyuan Zhang, Bin Hu, and Tamer Başar. Derivative-free policy opti- mization for linear risk- and robust control design: Implicit regularization and sample complexity. Advances in Neural Information Processing Systems, 34:2949-29966 2021.
[38] Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum Markov games. In International Conference on Machine Learning, pages 307-366. PMLR, 2022.
[39] David S Leslie, Steven Perkins, and Zibo Xu. Best-response dynamics in zero-sum stochastic games. Journal of Economic Theory, 189:105095, 2020.
[40] Lucas Baudin and Rida Laraki. Smooth fictitious play in stochastic games with perturbed payoffs and unknown transitions. Advances in Neural Information Processing Systems, 35:20243-20256, 2022.
[41] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems, pages 8668-8678, 2019.
[42] Shangtong Zhang, R Tachet, and Romain Laroche, Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch. Journal of Machine Learning Research, 23(343):1-91, 2022.
[43] Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. SIAM Journal on Control and Optimization, 60(4):2095-2) 2214,, 2022.
[44] Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer, 2020.
[45] Zaiwei Chen, Sheng Zhang, Thinh T. Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning. Preprint arXiv: 1425, 2019.
[46] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3)
2018. 2018.
[47] George W Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation, 13(1):374-376, 1951.
[48] Julia Robinson. An iterative method of solving a game. Annals of Mathematics, pages 296-301, 1951.
[49] D. Fudenberg and D. Kreps. Learning mixed equilibria. Games and Economic Behavior, 5:320-367, 1993.
[50] Josef Hofbauer and William Sandholm, On the global convergence of stochastic fictitious play. Econometrica, 70(6):2265-22) 22994, 2002.
13

---

[51] James Hannan. Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
[52] Drew Fudenberg and David K Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19(5-7):1065-1068 1995.
[53] Josef Hofbauer and Ed Hopkins. Learning in perturbed asymmetric games. Games and Economic Behavior, 52(1):133-112, 2005.
[54] Jeff S Shamma and Gürdal Arslan. Unified convergence proofs of continuous-time fictitious play. IEEE Transactions on Automatic Control, 49(7):1337-11141 2004.
[55] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning. and Games. Cambridge University Press, 2006.
[56] Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global conver- gence of multi-agent policy gradient in Markov potential games. In International Conference on Learning Representations, 2022.
[57] Sarath Pattathil, Kaiqing Zhang, and Asuman Ozdaglar. Symmetric (optimistic) natural policy gradient for multi-agent learning with parameter convergence. In International Conference Artificial Intelligence and Statistics, pages 5641-5685 PMLR, 2023.
[58] Chen- Yu Wei, Chung- thung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. In Conference on Learning Theory, pages 4259-4299. PMLR, 2021.
[59] Ziyi Chen, Shaocong Ma, and Yi Zhou. Sample efficient stochastic policy extragradient algorithm for zero-sum Markov game. In International Conference on Learning Representations, 2021.
[60] Muhammed O Sayin, Kaiqing Zhang, and Asuman Ozdaglar. Fictitious play in Markov games with single controller. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 919-936, 2022.
[61] Lucas Baudin and Rida Laraki. Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. In International Conference on Machine Learning, pages 1664-1690 PMLR, 2022.
[62] Chinmay Maheshwari, Manxi Wu, Druv Pai, and Shankar Sastry. Independent and decentralized learning in Markov potential games. Preprint htt.::2225.4499000 2022.
[63] Eyal Even-Dar and Yishay Mansour. Learning rates for Q-learning Journal of Machine Learning Research, 5(Dec):1-25, 2003.
[64] Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approxima- tion and Q-learning. In Conference on Learning Theory, pages 3185-3205. PMLR, 2020.
[65] Zaiwei Chen, Siva Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A Lya- punov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Research, 2023.
[66] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, pages 1-48, 2022.
[67] Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning. IEEE Transactions on Information Theory, 2023.
[68] Srihari Govindan, Philip Reny, Arthur J Robson, et al. A short proof of Harsanyi's purification theorem. Games and Economic Behavior, 45(2):369-374, 2003.
[69] Richard S Sutton, Learning to predict by the methods of temporal differences. Machine learning, 3(1):9 1988.
14

---

[70] Josef Hofbauer and Sylvain Sorin. Best response dynamics for continuous zero-sum games. Discrete and Contimuous Dynamical Systems Series B, 6(1):215, 2006.
[71] Tianyi Lin, Zhengyuan Zhou, Wenjia Ba, and Jiawei Zhang. Doubly optimal no-regret online learning in strongly monotone games with bandit feedback. Preprini urXiv:2112.02856 2021.
[72] Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. In International Conference Artificial Intelligence and Statistics,, pages 172 272-235. PMLR, 2023.
[73] Drew Fudenberg and David K Levine. The Theory of Learning in Games, volume 2. MIT press. 1998.
[74] Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 19010):0055-1100, 1953.
[75] Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. math, 3(1):133-181, 1922.
[76] Sajad Khodadadian, Thinh T Doan, Justin Romberg, and Siva Theja Maguluri. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions Automatic Control, 2022.
[77] Ziyi Chen, Yi Zhou, Rong-Rong Rong Chen, and Shaofeng Zou. Sample and communication--fficcenn decentralized actor-critic algorithms with finite-time analysis. International Conference on PMLR, 2022.
Machine Learning, pages
[78] Tengyu Xu and Yingbin Liang. Sample complexity bounds for two timescale value- reinforcement learning algorithms. In International Conference on Artificial Intelligence and Statistics, pages 811-819. PMLR, 2021.
[79] Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617- 17628, 2020.
[80] Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-664, 2021.
[81] Christopher JCH Watkins and Peter Dayan, Q-learning Machine learning, 8(3-4):279-292. 1992.
[82] Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
[83] Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum Markov games with a large number of players sample-efficiently? In International Conference on Learning Representations 2022.
[84] Weichao Mao, Lin Yang, Kaiqing Zhang, and Tamer Başar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning, pages 15007-15049. PMLR, 2022.
[85] Qiwen Cui, Kaiqing Zhang, and Simon Du. Breaking the curse of multiagents in a large state space: RL in Markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2651-2652. PMLR, 2023.
[86] Chen- Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems, pages 4987-4997, 2017.
[87] Kaiqing Zhang, Sham Kakade, Tamer Başar, and Lin Yang. Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33:1 18:1166-1117 2020.
15

---

[88] Gen Li, Yuejie Chi, Yuting Wei, and Yuxin Chen. Minimax-optimman multi-agen RL in Markov games with generative model. Advances in Neural Information Processing Systems, 35:15353- 15367, 2022.
[89] Qiwen Cui and Simon S Du. When are offline two-player zero-sum Markov games solvable? Advances in Neural Information Processing Systems, 35:25779-225 25791,, 2022.
[90] Qiwen Cui and Simon S Du. Provably efficient offline multi-agent reinforcement learning via strategy wwie bonus. Advances in Neural Information Processing Systems, 35:11739-11751, 2022.
[91] Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning. pages 17117-27142. PMLR, 2022.
[92] Zuguang Gao, Qianqian Ma, Tamer Başar, and John R. Birge. Sample complexity of decentral- ized tabular Q-learning for stochastic games. 2023 American Control Conference (ACC), pages 1098-1103, 2023.
[93] David A Levin and Yuval Peres. Markov Chains and Mixing Times, volume 107. American Mathematical Soc., 2017.
[94] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-Dyamiic Programming. Athena Scientific, 1996.
[95] John M Danskin. The Theory of Max-Min and Its Application to Weapons Allocation Problems, volume 5. Springer Science & Business Media, 2012.
[96] Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. Preprint arXiv: Tttv:1704.0000 704.00805, 2017.
[97] Amir Beck. First-order methods in optimization, volume 25. SIAM, 2017.
[98]
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. 10th Innovations Theoretical Computer Science, 2019.
[99] Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, and Atsushi Iwasaki. Last- iterate convergence with full and noisy feedback in two-player zero-sum games. In International Conference on Artificial Intelligncce and Statistics, pages 7999-800 8028. PMLR, 2023.
16

---

A Extended Related Work
Continued from Section 1.3, we here discuss several other existing works that are relevant.
Recently, there has been an increasing study of MARL with sample efficiency guarantees recently [16, 82, 20, 17, 21, 83, 84, 22, 85]. Most of them focus on the finite-horizon episodic setting with online exploration, and perform regret analysis, which differs from our last-iterate finite- sample analysis under the stochastic approximation paradigm. Additionally, these algorithms are episodic due to the finite-horizon nature of the setting and are not best-response-lype independent learning dynamics that are repeatedly run for infinitely long, which can be viewed as a non-equilibrating adaptation process. fact, the primary focus of this line of work self-play setting where all the players can be controlled to perform centralized learning [86, 16, 82, 20, 17]. Beyond the online setting, smite-sample efficiency has also been established for MARL using a generative model [87, 88] or offline datasets [89-91, 67]. These algorithms tend to be centralized in nature and focus on equilibrium computation, instead of performing independent learning.
Finite- sample complexity has also been established for policy gradient methods, popular RL approach when applied to solving zero-sum stochastic games [14, 36-38]. However, ensure convergence, these methods are asymmetric in that the players update their policies at different timescales, e.g., one player updates faster than the other with larger stepsizes, or one player fixes its policy while waiting for the other to update. Such asymmetric policy gradient methods are not independent, as some implicit coordination is required to enable such a timescale separation across agents. This style of implicit coordination is also required for the finite-sample analysis of decentralized learning in certain general-sun stochastic games, c.g., [92], which improves the asymptotic convergence in [7]. In contrast, our learning dynamics only require the update of each player's 's policy to be slower than the update of their g-functions, but crucially we do not assume a time-scale separation between the two players, making our learning dynamics symmetric.
B Proof Sketch of Theorem 3.1
In this section, we present the key steps and technical ideas used prove Theorem 3.1. The core challenge here is that Algorithm 2 maintains 3 sets of iterates (Lg', h. { J. and {ufH), which are coupled. The coupling of their update equations means that it not possible to separately analyze them. Instead, we develop a coupled Lyapunov drift approach to establish the finite-sample bounds of Algorithm 2. Specifically, we first show that the expected Nash gap can be upper bounded by a sum of properly defined Lyapunov functions, one for each set of the iterates (i.e., the r-functions, the policies, and the g-functions). Then, we establish a set of coupled Lyapunov drift inequalities one for each Lyapunov function. Finally, we decouple the Lyapunov drift inequalities to establish the overall finite-sample bounds. We outline the key steps in the argument below.
To begin with, we show in Lemma D.I that the g-functions {gi,.} and the o-functions {w]} generated by Algorithm 2 are uniformly bounded from above in e. -nom by 1/(1 (1) and the entries of the policies (mf,r) ) are uniformly bounded below by & > 0. This result will be frequently used in our analysis. We next introduce the Lyapunov functions we use to analyze Algorithm 2. Specifically, for any 1, k 2 0, let C. E RISS|A441 be defined as T (8) = (s) for all E S. Let
frum (t) = |l + o2l, (t = Σ lll lllo,
1=1.2
(y(t,k) ()) = Σ Σ
-
Σ
llai - -
1= 1,,888
Cx(t,)) max SES
Σ (AA)
max
T Tu(u²) - ru(a(u()))
Note that Lxum (t) is introduced to deal with the fact that the induced matrix game the inner loop of Algorithm 2 is designed to solve may not be a zero-sum game due to independent learning. See the discussion in Section 1.2 and the paragraph after Algorithm 2. At the core of our argument is the following inequality (cf. Lemma D.4):
NG (T xT.K)= S 1-7 (2Caum (T) + Lc) + C (T, K) + 27 (Ag(Amax)),
(6)
17

---

which motivates us to bound all the Lyapunov functions.
B.1 Analysis of the Outer Loop: u-Function Update
Motivated by Eq. (6), need to bound Caum (T') and (T")). To achieve that, establish Lyapunov drift inequalities for them. Specifically, we show in Lemmas D.5 and D.6 that
Cu(t +1 (t,(t) + 4.amm (t) 2 (t, K) + (t, + 67 (0gga))))
Drift
Additive Ervor
Laam(t + +) S (tmm + (t,
A 0.
(8)
Drift
Additive
Suppose that the Additive Errors in the previous two inequalities were only functions of of and o? then these two Lyapunov drift inequalities can be repeatedly used obtain convergence bound for Laum (T) and (T)). However, the coupled nature of Eqs. (7) and (8) requires us to analyze the policies and the q-functions in the inner loop, and establish their Lyapunov drift inequalities.
B.2 Analysis of the Inner Loop: Policy Update
As illustrated Section 2.1 and Section 3.1, for each state s, the update equation of the policies can be viewed as discrete and stochastic variant of the smoothed best-response dynamics for solving matrix games [29]. Typically, the following Lyapunov function is used to study such dynamics [53]:
(x (x
E max ('EA(A)
((A' -n²'T
X,1' - Tv(A") rV(L")),
where X1 and X2 are the payoff matrices for player and player 2, respectively, and v(-) is the entropy function. Specialized to our case, given a joint e-function (v', v²) from the outer loop* and state S, we would like to use
Ve. (s),
Σ max ((A ('''-((ss) (T)))))) ((s) + Tv(fE) - Tu(T((s)))
(TEA(A))
Lyapunov function. Note that max,es (m (s) (t, A sequence of properties (e.g., strong convexity, smoothness, etc.) regarding the Lyapunov function Vx Vx(,,) is established in Lemma D.7. In the end, we show in Lemma D.8 that
33 4
E, [C (t, + 1)}
E, [. k1]
Drift
32
max BK (t,
16.42 max: 3k Lsum (t)
+ 2L,
(10)
73 7)2
Additive Errors
where [-] stands for conditional expectation conditioned on the history up to the beginning of the t-th outer loop. To interpret the above, suppose that we were considering the continuous-time smoothed best-response dynamics. Then, the additive error term would disappear in the sense that the derivatviv of the Lyapunov function along the trajectory of the ODE is strictly negative. Thus, the three terms in the Additive Errors can be interpreted as (1) the discretization error in the update equation, (2) the stochastic error the q-function estimate, and (3) the error due to the non-zero-sum structure of the inner-loop auxiliary matrix game.
B.3 Analysis of the Inner Loop: q-Function Update
Our next focus is the q-function update. The q-function update equation is in the spirit as TD-learning in RL, and a necessary condition for the convergence of TD-leamnng is that the behavior
'Due to the nested-logy structure of Algorithm 2, conditioned on the history up to the beginning of the t-th outer loop, the e-functions of and of are constants.
18

---

policy (i.e., the policy used to collect samples) should enable the agent to sufficiently explore the environment. To achieve this goal. since we show in Lemma D.1 that all joint policies from the algorithm trajectory have uniformly lower-bounded entries (with lower bound l, > 0), it is enough to restrict our attention to a "soft" policy class TT, := (x = (m², ming (a (8) 2
f. m 2 x² (a 2 {-}- The following lemma, which is an extension of [10, Lemma 4], establishes a uniform exploration property under Assumption 3.1.
To present the result, we need the following notation. Under Assumption 3.1, the Markov chain induced by the joint policy Th has a unique stationary distribution 14b E (SS) [93], the mini- mum component of which is denoted by Mb,min- In addition, there exists Ps (0, 1) such that max.es | (s. -) po(-))lyy I 2 for all k Z [93], where Pr. the transition probability matrix of the Markov chain [Sk] under Ty. We also define the mixing time in the following. Given a joint policy = (T >) and an accuracy level > O, the 17 mixing time of the Markov chain
{Sk} induced by x is defined as
max (s. - (+ s sn). EES
b,, = min k 220- 0
(11)
where Px is the r-induced transition probability matrix and jor is the stationary distribution of { under æ. provided that it exists and is unique. When the induced Markov chain mixes at a geometric rate, it is easy to see that xx,n = (log(1/n))
Lemma B.1 (An Extension of Lemma 4 in [10]). Suppose that Assumption 3.1 is satisfied. Then have the following results.
(1) For any x (m², x²) 11, the Markov chain } induced by the joint policy is irreducible and aperiodic, hence admits a unique stationary distribution M E (SS).
(2) It holds that su, max.es ||P (s,-) - px(-) S 2p for any 2 O. where Pr
2n vo.min and rb == min(k 2 0 pk (s, > O, 4 (s)s As result, we have Pb
tm S ta
t(lr, m)) = sup =En
(12)
where we recall that lay is the 7 mixing time of the Markov chain (Sa} induced by wh-
(3) There exists Lp 2 (which was used in the statement of Theorem such that
||m - |=l111 S ( max (s) - n (8)]l + max aES
SES ||T (s) (s)111
for all = (x (r)),²),, )), = (T 2)) E 1T
(4) Pmin := infren, min,es Mm (s) >
Remark. Lemma B.1 (I), (3), and (4) were previous established [10, Lemma 4]. Lemma B. (2) enables
the explicit dependence of the "uniform mixing time" on the margin E, and the mixing time of the benchmark exploration policy Th.
In view of Lemma B.1 (2), we have fast mixing for all policies in II, if (i) the margin & is large, and (ii) the Markov chain {Sx) induced by the benchmark exploration policy He is well-behaved. By "well-behaved" we mean the mixing time is small (i.e., small fx,,,) and the stationary distribution is relatively well-balanced (i.e., large min) Point (i) agrees with our intuition as large margin encourages more exploration. To make sense of point (ii), since π (a]ss)
(a)s))))) for all and a = , .²), we can write æ as a convex combination between ग. and some residual policy 7: (-1s)= - (-1ssss (mm()s) + (1 - (-(ss for all E S. Therefore, since any E 11, has portion of the benchmark exploration policy n, in it. it makes intuitive sense that fast mixing of {S²} } under ne implies, to some extent, fast mixing of {Sk) under
II,. Note that, as the margin & approaches zero, the uniform mixing time in Lemma B.1 (2) goes to infinity. This is not avoidable in general, as demonstrated by simple MDP example constructed in Appendix E.
We define e = Mminnrs which was used in the statement Theorem 3.1. With Lemma B. in hand, are now able to analyze the behavior of the funcctions. We model the q- fufnction update
19

---

stochastic approximation algorithm driven by time-inhomogennous Markovian noise, and use the norm-square function
-(()())-
-
1,1.2
as the Lyapunov function to study its behavior. Note that (t, = Ei=12 E. E. T' (s) The key challenge to establishing a Lyapunov drift incquality is to control a difference of the form
(e' Sk, Ar' , - A
(13)
for any q¹ [ and i [1, where (-) is some appropriately defined operator that cap- tures the dynamics of the update equation; see Appendix D.5.2 for its definition. In the term (13), the random tuple (S,, 4 ,S+11) is the k-th sample from the aameiinhomoeeneoee Markov chain {(Sx, Ai. (S+11)320 generated by the time-varying joint policies { Jx20 and (S, i-, is random tuple such that S px((),, A ~ (-)),, A T (-[S), and S' ~ p( A A' A- where (+x+) denotes the unique stationary distribution of the Markov chain [Sa) induced by the joint policy тk- Lemma B.1 implies that 14t exists and is unique.
In the existing literature, when {(Se, AL. ()+) sampled either in an i.i.d. manner or forms an ergodic time-homogeneous Markov chain, there are techniques that successfully bound the term (13) 194, 24, 23]. To deal with time-innomee aonn--ihooogecouuss Markovian noise, building upon existing conditioning results [23, 24, 41, 76] and also Lemma B.I, we develop a refined conditioning argument to show that
(13) = O
Zk
On
(See Lemma D.11)
n=
where zn = L(F,,, ) is a uniform upper bound on the 34 - the mixing time (i.e., the uniform mixing time with accuracy Sg, see Eq. (12)) of the Markov chain {S.]a20 induced by an arbitrary joint policy from the algorithm trajectory. Suppose that we are using diminishing stepsizes of OL/kk) decay rate (similar results hold for using constant stepsizes). Then, the uniform mixing property from Lemma B.1 (2) implies that 2 = (llog(1/k)). As result, we have lim (13) s lim 2k Σ _ on O, which provides us way to control the term in (13). After successfully handling (13), are able establish Lyapunov drift inequality of L.g(1,
BK
E, (t, 1)] < - ExC + Cozka6Ok=21.ee -- + ((,,(t)
(14)
4
Drif
Additive Erroes
where Co is a simplify the notation. See Lemma D.12 for more details. When & is large, be shown that Okk k-1 < 200 [65, Appendix 1.8).
constant, and we use the notation 0sk == Σ kk 0% to
B.4 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 g-functions in Eqs. (7), (8), (10), and (14), respectively. The last challenge is to find a way of using these coupled inequalities to derive the finite-sample bound, To elaborate, we first restate all the Lyapunov drift inequalities in the following:
C.(t [ 1) (t) + S (t) + (t, K) + 2C (t, K) + Gr log( Amax),
(15)
S (t + < 7 (t) + 22, K),
(16)
(1, 1)] <(1 (1- 3.-338/4)B,,
Ci + B, + B (I),
(17)
E. (t, 1)] s (1 (1--c c, c,,,) R)] S,E, k) Cs
(18)
To decouple the Lyapunov inequalities stated above, our high-level ideas are (1) using the Lyapunov drift inequalities in combined way instead of in separate manner, and (2) a bootstrapping procedure
20

---

where we first derive crude bound and then substitute the crude bound back into the Lyapunov drift inequalities derive a tighter bound. We next present our approach.
For ease of presentation, for a scalar-valued quantity W that is a function of l and/or t, we say W oz (1) if Tim W = O and W (1 if - W = O. The explicit convergence rates of the (1) term and the (1) term will be revealed in the complete proof in Appendix D.6, but is not important for the illustration here.
Step 1. Adding up Eq. (17) and (18), using Condition 3.1, and then repeatedly using the resulting inequality, obtain:
[t, S B. k) + (t, = 0& (1) + ((1) (t), A tt
(19)
Step 2. Substituting the bound for E, (t, k]] in Eq. (19) into Eq. (18) and repeatedly using the resulting inequality, and we obtain:
[4, K)] = ox (1) + (co,,)) 2m (1), L1,
which in turn implies (by first using Jensen's ' inequality and then taking total expectation) that:
(1,, K]] ox (1) + Occ2, 1/2 (E( (f)], V t,
(20)
where we recall that Ca, / is the stepsize ratio. The fact that we are able to get factor of (ca..) in front of TE| (u) (t)] is crucial for the decoupling procedure.
Step 3. Taking total expectation on both sides of Eq. (16) and then using the upper bound of B /2 (t, K]] we obtained in Eq. (20), we obtain
EfSsum (t + 1)] - (7 Ol E(L + ok (1), tt. By choosing C that O ((c2,))
1/2 S (1 - 7)/2, the previous inequality implies
E[CCum (t + 1)] S 1-7
[[[Cum (t)] + (I()), Vt,
(21)
which can be repeatedly used to obtain
E[Csum [t)] 00 (1) + o1).
(22)
Substituting the previous bound on B[Csum (t) into Eq. (19), we have
max(E[[.)) (t, K)] B[C, X)I) or(1) + o1))
(23)
Step 4. Substituting the bounds we obtained for (t, K)], EtC, K)], and Bi (t) in Eqs. (22) and (23) into Eq. (15), and then repeatedly using the resulting inequality from 0 to / T, we have
(T), = (z)) (())
Now that we have obtained finite-sample bounds for (T)) ([Cam(() EEC K)). and E[C, K)], using them Eq. (6), we finally obtain the desired finite-sample bound for the expected Nash gap.
Looking back at the decoupling procedure, Steps 2 and 3 are crucial. In fact, in Step we already obtain a bound on E, Cg (t, J. where the additive error is (tm)m_))m However, directly using this bound on E, CC, (t, k)] in Eq. (16) would result in expansive inequality for Ef (t)]- By performing Step 2, we are able to obtain a tighter bound for (t, k)], with the additive error 1/2 [[ (4) Furthermore, we can choose Co,,8 to be small enough so that after using the being (C,,,)
bound from Eq. (20) in Eq. (16), the additive error (c (E( (t)] is dominated by the negative drift in Eq. (21).
C Proof of Theorem 2.1
The proof divided into 4 steps. Appendix C.I, we prove an important boundedness property regarding the iterates generated by Algorithm 1. In Appendices C.2 and C.3, we analyze the evolution of the policies and the q-functions by establishing the negative drift inequalities with respect to their associated Lyapunov functions. In Appendix C.4, we solve the coupled Lyapunov drift inequalities to prove Theorem 2. Moreover, we prove Corollary 2.1.1 in Appendix C.5. The statement and proof of all supporting lemmas used in this section are presented in Appendix C.6.
21

---

C.1 Boundedness of the Iterates
In this subsection, we show that the q-functions generated by Algorithm are uniformly bounded from above, and the entries of the policies are uniformly bounded from below. The following lemma needed establish the result.
Lemma C.1. For any {1,2) and q' RIAI", we have
min [a, (g')))((())) > (Amax - 1) exp(2111 (100T)) + EAA
Proof of Lemma C.I. Given i E {1, for any o² E RRAA' and a' E A', we have exp(a'(a')/1
(o,()')((a') Exee (xp((((aa)T))
Eaxpseep((y --
(14:) 1) exp +1
IV (Amax 1) exp(2
Since the RHS of the previous inequality does not depend on a', we have the desired inequality. m
We next derive the boundedness property in the following lemma.
Lemma C.2. It holds for all h: 2 0 and i (1,2) that | S and min (a(a 2 l,.
where l, = [[Amaxx - 1) 1) exp (2/T) + 1|-
Proof of Lemma C.2. We prove the results by induction. Since dó and To is initialized uniform distribution on A'', we have the base case. Now suppose that the results hold for some A 2 0. Using the update equation for of Algorithm Line 5, we have
19 = [(1 au I (ai= )á + ( (A AF (ax(lad(a")) (a'),, a au R2 D)
<
for any af E A', where the last line follows from the induction hypothesis || llx < and Ra a-)) & for all at), As for Thtn using the update equation for o in Algorithm
Line 3, have
( = (L-BA)TT('ss + Bxla (ai))(aa)
Bx
2 (1 - (1-Ba)er + (Amax - exp TT) +
(Lemma C.I)
2 (1 - Ba)er + Bale
(1lgé S 1 by induction hypothesis)
lx-
The induction is complete.
C.2 Analysis of the Policies
Let VR A(A)) A(AP) + IR be the regularized Nash gap defined as Vn(ui vn(
- = Σ max {(it -²) Rap- + rv((T") - Tr(n")}
11 ('EA(A))
where v(.) is the entropy function. A sequence of properties regarding VR(,,) are provided in Lemma C.7. For simplicity of notation, we use V, V)V.) (respectively, V2Vn(; to represent the gradient with respect the first argument (respectively, the second argument).
22

---

Lemma C.3. It holds for all &. 2 0 that
+ BI +11 - (1- Bk 2
lox
Σ
E
Bilgi
R
21,
4
1=12
where we recall that L, T/L, + Amax/T.
Proof of Lemma C.3. Using the smoothness property of VR((.)) (cf. Lemma C.7 (1)) and the update equation Algorithm Line 3, we have for any 2 that
Vn(# x) & Vn = + BA (V2Vn(T - 0z(()) - xx²))
+ (V +)) (g o - m|) + T.r.8%
Σ
(10
Till2
1=1,2
S + + 34 ( m or (B2rk) - mp))
+ Bu V1 [1)
- -mp)
+ 3u (V) - (
+ By (
(9h)
o, 37(R1TT + 2L,
8k
V (R(
+48
1
A
Σ 1=122
l1
R,T 112 1
T62
33
where the last line follows from Lemma C.7 (2) and (3). Taking expectations on both sides of the previous inequality and using the condition that Ca,9 os we have
Ps < min(
f.r
(cf. Condition 2.1),
3242
11 11- 8k P[VR(TE41) 1111
(1-2 E[
xf) + Las Σ
Blllgh RGT '121 2I, 18
4
1=12
The proof is complete.
C.3 Analysis of the g-Functions
We study the q-functions generated by Algorithm 1 through stochastic approximation framework.
For i (1,2), let Fi RRId' A' A- RIA' be an operator defined
(1' a a, (aa)) 1 (aj=a') (Ra a ) o (abt), (g', ai, a) and a'.
Then, Algorithm Line be compactly written as
g oe + aq F (gi. Al. A5
(24)
Given joint policy (Λt ,,,,,)), let F R RAA R|4'1 be defined as
(1 = BAiNai(),A fur ( (F'(F A-)] diag(m (R,
Then, Eq. (24) can be viewed as a stochastic approximation algorithm for solving the slowly time-varying equation F (q") =0
Lemma C.4. The following inequality holds for all k 2 0:
(1 (1-
L,ax
3 EEV ([))) 16a
Σ Elllg441 RITiiIl 1.2
Σ
Ellli
RIT
2
1,1
Proof of Lemma C.4. For any A 2 and i {1,2), we have
M R 1
-114641 - dt. + q - R&T + RATE Remiilll
=1le441 1ill3 lg ROT $12 + |RiT RAT 112 2(gh-11 gt. oh R.T
23

---

+ +2(gh+1 gh: R RRTTE+1 + 2 - R 9: -R ')
aLll (gh: Al. ) + 1191 & ' R, (9k ) - Tx ') 112
+ 20 Fixx (1i). lh - R ) + 20x 20x (Fi Al. Ax Fxx (0ke qh RG )
2x 1 (gk. A/e " (rr
Tx²x) ') - 23p (Ri (or (4x )
T ") 9k R (Algorithm Lines 3 and 5)
S aafll Al. A 112 + 11 - R $113 + 321 R,(o, (qk
Tx )
(gk) dh RRTE + 20x F (1k)s 0k - R. " + 20x (F' (ghe A Az²) m2
+ 20r [r) (uk: A/e A3 ||2| R2, (o- (4xx ') - Tx 1212
23k || R2 (o 1i-mg th (T')) 1112|16 R 2122
(Cauchy-Schwanl inequulllll
< a P2 (1hr: A/.. A/ + 11 R $133 + f Rr (1k =x T
+ 20 ( F (4k), gh - R. + 20 FF (ghe A AE Fr, (gk), oh RoT
ag
|EF (gh: A )13 + a3 cx c1 (o, (gn - T 1)1
+
C1
8x
+
R 1) मh ' + c2,3 R 11
02
(This follows from the AM-GM inequality, where c1, 02 > 0 can be arbitrary.)
a =(02+
onSe)
| IF (ek Ai. 11 (1 025 llgh R
C1
+ 2ax (gtt) ok - RITT + 2ax (F' (4k: A A
F+, (gk) gt - -ReT "
+ 8 Bx
+ axBker) || 12 (9 k 113-
C2
Taking expectations on both sides of the previous inequality, we have
Bllad+11
0 +
Ei|l FlIFF
(gke 1/e 1 + (1 + c2 Billi Ri [12]
Bx
+ angBec) )
+ 20 (gf)) ot R "11 + 0 +
| (gx ) x 112)
e2
where the term B[FF (g.. A conditional expectations. To proceed, observe
Fr -
(g)),,
R,T '11 vanishes due to the tower property of
Σ 1(Ai=aa) (Ri(A), - (AA))) ?
E|| (1h, Al. A 1- IE
L''EA'
(a(R AT. -a(
[[[[RR(aa, AF") [1)((a)))
< 4
(Lemma C.2)
and
EK(P te (o R&T = B((diag(TT)) (R;T) - -g).
- -f R(TE)))
I EE1l1 R 112).
(Lemma C.2)
In addition, we have
Billa, Tx 1121 < 2BI1oo σr (R + +2I11o, (R_smt))
T $121
(a² + 12 > 2ab)
2
Ell - R BIVR(TK, 21),
< 72
24

---

where the last line follows from Lemma C.6. Using the previous 4 inequalities all together, we obtain
agSk
ElllA+11 RIT
S
(1
26-0x + C22kk) Ellld
R
C1
44
8k
8/ +
+axBkc1
B|Vi((T TR)
T
2
8k
max
8/
+
+
Ellgx* i
x
22
Summing up the previous inequality for E {1,2]. we have
Σ
Billat+1
1=1,2
$ (1 11- 2k 623kx +
24
max
+
3k
oz oxBECI) ))
Σ
Elll
g
R
72
C2
11122
8.2
BR
B[Vu((Tk +1)l + (a
max
+
02
2A_ max
2
2
E Blllak ReT $ $12)
72
1=1,2
842
209
max
2 +
E(Vn(Tk x1)
+ 16
(Choosing co
Ba. and
6,00 22%
t,kk
a.kk
Bk V xl) + 16a
1
Elll
R
11 +
2
4
Am
1,2
where the last line follows from Ca.3 S min( The proof is complete.
and 30 S 1284 (ef. Condition 2.1).
SA
428
C.4 Solving the Coupled Lyapunov Inequalities
For simplicity of notation, denote (k()) = Ei=1, Elllet RuTT'113 and (*))) E[Va(TT) m
Then, Lemmas C.3 and C.4 state that
3k 1
(k) + 4ax Cx(k) + 20,
Lx (k + 1)
2
and
(k(k) + 3B Ln (A:) 16a
c + -
1
2
Adding up the previous two inequalities, we obtain
(1
31
(x(k) + +LL, + (1- Lax
Cy(k: +1+ (k++)) 1)s
(.((k) + 16a
4
4
3k
1
(C+(k) (k)) +2,,0% 160
(25)
4
where the second inequality follows from Ca,8 $ e, (cf. Condition 2.1).
Constant Stepsizes. When using constant stepsizes, i.c., an and 3g = B, repeatedly using Eq. (25), we have for all & 2 0 that
+
+ Cx)() <
+ + + + 64a +L.
1 7)
h (4 + 27 log(Amax) + -A2ma)) + SL, + 64a
<
25

---

Bm (1 B
64x Co,3
+ 88,
where the second inequality follows from
(0) 2r log Amax); and (0 2A
Theorem 2.1 (1) follows by observing that (k) (k) 2 C EING, m
Diminishing Stepsizes. Consider using ag 1++h and Be A+ Recursions of the form presented in Eq. (25) have been well studied in the existing literature for the convergence rates of
9
iterative algorithms [44, 24, 65]. Since 3 > 4, using the same line of analysis as in [65, Appendix A.2], we have
3/4 k+ h
(k) + Lx(()x S Bin
+ (64eI,, + 21/ee1//eeeee (c, k+ h
Theorem 2.1 (2) follows by observing that (k) + (k) 2 (1:) E x2]]-
C.5 Proof of Corollary 2.1.1
We use Theorem 2.1 (1) to derive the sample complexity. and choose , = Ca, with Co.3 satisfying Condition 2.1. To achieve E|NG,(T m I in view of Theorem 2.1 (1), it is sufficient that
B
8K/4
8L, c g.
64a/ca,9 S 3
3
which implies B = Oc). It follows that K = 0 (c
C.6 Supporting Lemmas
Lemma C.5. For any (1, and pi. 12 (ut A(A*) min pl(a') 2 Lx}. we have
1 1
[V](())) vu(u5)ll S e, Il pbl22- l2
Proof of Lemma C.5. For any i E {1,2} and n² E A(A') such that Ein l,, the Hessian of u(.) satisfies
1
1Ay &
Hessian, (n²) diag (n²)-² min 1 S
Therefore, the gradient of the negative entropy functioo Vv(-) is 2.- Lipschitz continuous with respect to ||-1|2 on the set (u² E A(At) ming 2 &)), which implies the /.- smoothness of v(.).
Lemma C.6. For i E {1,2}, we have all 4³ E A(A') and f f A(A-)) that
2
2
||o, 12112 < VRlu' ,p²),
Proof of Lemma C.6. Recall that the negative entropy v(-) is 1-strongly concave with respect to ||- Therefore, given i E {1,2), fix nr the function
{(a' -Ta) Rape + Tu((() -TV((')
max (EA((A))
is r-strongly convex with respect to u². As a result, by the quadratic growth property of strongly convex functions, we have
2
||ا [|op(Ray 1² 1 < T (EA(AA)
((p--ut) w²) R.p Tv(fF) rv(1²) - Vvn(u',p
max
26

---

Denote II, =
x A(A?) min x ra(a)) 2 & aa = 2 4
Lemma C.7. The function VR(:,) has the following properties.
(1) The function Vnlp' 1x2) is L - smooth on II where L, = 2, + A
(2) It holds for any (n² ,22) E 11, that
(V.VRlu' 1²), o, (R p²))+ (V2VR(u', ,1²), o, (R21") 12) -VR(m",
(3) For any g¹ TR A-l and 9² E ERlAR,, we have for all (1² .12) II, that
(ViValu' (1)),o((1) - -o-(R11²)) + (V2Vn(l'* 1²), - o, (R2
A
$ 2 Valm',u + +4 Fl +
llg' - Ríp 11..
Proof of Lemma C.7. Recall the definition of VR(.s)) in the following:
Vnlu' ,p²) = E
{ ((") Rap "t + -v)l)))
max A'EAIA)
By Danskin's theorem [95], we have
ViVR('' (0)(m),,²)== - -VVu('')+ (R,2)
V2VR('', ,1²) - +Vu(n+)+
both of which will be frequently used in our analysis.
(1) For any (nr2, (p), (Tt n=7) E 7, we have
Vn,Vn n²²) - ViVn(m", 122112
|/ -Vu(nt) (R2) TaaTor T [22 ) (R2) Too "R )l1
$ =l(Va(n') Vu(ue) }|| + Relllllo, (Reu') o (Ryp )||
| 12
$ 8, 11
-122112 +
1 7 112
A
I| x=
1,
where the second last inequality follows from Lemma C.5 and (-) being 1 , -Lipschitz continuous with respect to || ll [96], and the last inequality follows from [Ral|2 E (1,2). Similarly, we also have
\A111A4311 Amax for
A2 A2
VV2V V2Vn(T 12Vn(r2,11113
T lr
+
11 1|p2- -122
It follows from the previous two incqualities that
[VVR(a u²)) VVR(A,, ,
=IV 122) - ViVn(p' x²) VVVVa VeVa(='.
12
2
<
max
Σ 1n - 1/112
e
T
112
which implies that VR(;)) )) is an L, - smooth function on II, [97], where L, = E
42 A
(2) The result follows from Lemma D.7 by setting X, R. í E {1,2), and by observing that R + (R2)² T 0.
27

---

(3) Using the formula of the gradient of Va(-, in the begining of the proof, we have
(Vi ViVulu' or))) (r(
(-~Ve((l) + (R ), or (g') (B(p()) or (qt)
(VVV(o,(BBB))) (s - o, (Ra
+ (o, (B2 x22 T (q") o, (R)
(This follows from the order optimality condition: Ryp² (VV((o,(B11²)) =0)
< (u(or(R(n)) - Vulu 1l2
TC1
lo- or (11
201
2
+
lor ) - x² 112
2
[R o, (RI
202
(This follows from AM-GM inequality, where c1, 02 >> 0 can be arbitrary)
7
10, 1o, (Ri1²) - +
C 114
R112112
201
2T
|ot(R211 - 1²)111 + 02 B2
+
114
11,2211
(Lemma C.S)
202
27
1
VR(H 122) ) +
C1
114 1112212
113 + 22 121122113
lla R1 (Lemma C.6)
TC2
2r
2T
4 11 +
R2112
1 4
Valut (2))
+
11 - 11
Tl?
73
where the last line follows by choosing C1 = and c2 +. Similarly, we also have
?
4
(VeValu' 12), (VeValu'.")),ooG"" or ( S Vn(n' 122+ + =l? 11g2 Rep 11
/2 11 11 R2fl 1214'112 4
Summing up the previous two inequalities, we obtain
(ViVR(u', nx2), ar (g')
or (B(())))) + (V2VR(u :2), (q²) o, (Rzh²))
44 max
$ VRlw' 1n
+
Σ
11a2 21
33
1.1.2
where we used |Ral12 S Amaax for i E {1,2).
D Proof of Theorem 3.1
We begin by introducing summary of notation in Appendix D.1. In Appendix D.2, we establish an important boundedness property regarding the q-functions, value functions, and the policies generated by Algorithm 2. In Appendix D.3, we bound the Nash gap in terms of the Lyapunov functions. In Appendices D.4 and D.5, analyze the outer loop and the inner loop of Algorithm 2 and establish the Lyapunov drift inequalities. Finally, in Appendix D.6, we solve the coupled Lyapunov inequalities to obtain the finite-sample bound. The proof of all supporting lemmas are provided in Appendix D.7, and the proof of Corollary 3.1.1 is provided in Appendix D.8.
D.1 Notation
We begin with summary of the notation that will be used in the proof.
(1) Given a pair of matrices (X, BIAINAA " and pair of distributions (ut
A(4 we define
Vx p²)
Σ max {(it - u²)T Xtp + TV(p') re(u')}
(26)
1= ((E(()))
28

---

where v(() is the entropy function. Note that Vx (+--) is similar to Va(; defined in Appendix
C.2 in the setting of matrix games. However, we do not assume that X1 + X2 =0
(2) Given a pair of value functions (v+, e²) and state S, when X; T (T (1, write (t+) for (x(s))
(3) For any joint policy (x x²) and state 8, given i E (1,2). we define of - = maxe: o (+), of = ming- " (+), w (,() = ming. ax-r,a(s)) and (
maxg-1 Ug ( (b). Note that we have r2, + v²2.. = and o + v2 = because of the zero-sum structure.
(4) For i E 21, denote of the unique fixed point of the equation B (v') = v², where (.) is the minimax Bellman operator defined in Section Note that we have 1_ + 0. 0.
(5) For any f, k 2 0 and E (1,2), let The E RRSIIA be defined as ( T (s)) for all E S. In addition, let
Crum (t) !ll1 + boo
L.(t) = Σ 1 el
(t) Σ Σ - i= 1,5
1 - T.1112 Σ
1=1,2
(t, max #ES
(s),
which will be the Lyapunov functions we use in the analysis.
(6) Given k 12, denote Sk,, Ei= Sg and 0kk &22 Lk=kk ag.
(7) Recall that 2 (((,,8k) is the uniform mixing time defined in Lemma B.1 (2), where & is the uniform lower bound of the policies. When using constant stepsizes, is not function of k, and is simply denoted by 2g. Observe that, due to the uniform geometric mixing property established in Lemma B.1 (2), we have 2 (llo(kk) when using O(1/k) stepsizes and 2 = (log(11/)) when using constant stepsizes. Let kg min k defined because 2 grows logarithmically with k.
2 2k. which well
D.2 Boundedness of the Iterates
We first show in the following lemma that the q-functions and the y-functions generated by Algorithm 2 are uniformly bounded from above, and the policies uniformly bounded from below. In the context of stochastic games, we redefine & = [1 + (Amax - 1) exp(2/((1 7))])]-
Lemma D.1. For all t, is and (1,2), 2), we have (I) [oo S 1/(1 -7) and N S 11/(1 7),
and (2) minges, a (a a () 2 Ey.
Proof of Lemma D.1. The proof uses induction arguments. Let i E {1,2}.
(1) Given 2 0, we first show by induction that, if || bloe S ب and |0g,,lloo S - we have 11 I -- for all k 2 0. The base case 19 I --y holds by our assumption. Suppose that 11 o1.00 S + for some k 2 0. Then, by Algorithm Line 6, we have for all (s, a²) that
1 (s.
= (s, + au (8.) (R,,,, A7') + (ef(S))1) - (Sk. Ab)
$ as ((,,at)
(s,
+ az 1l ((.0)) R, (S Al. A +
1
2
$ (1 - a ((s,a')=
+ au
1 ((.a(
(27)
1-
1
29

---

where Eq. (27) follows from the induction hypothesis 1 loe S I- our assumption that lotiloo S - and mäx aa [Ra(s, a', a S 1. The induction now complete and we have l - for all k whenever ||u| lcc - - and |o0 - -
We next again use induction show that ||v|| =o S - and 4oooloo S T for all 2 0. Our initialization ensures that I| S - and l| - Suppose that ||o|]l S T- and 1 al $ 1, for some 2 0. Using the update equation for e't1 (ef. Algorithm 2 Line 8) and the fact that 1 S 1-y for all le 2 0 (established in the previous paragraph), have for all E S that
1-y
|0(41(0]1= =
Σ E'EAA
oं. (a (d.x(a'ss)ii
1 < Σ ='. $ 1-7' a'EAt
which implies ||u|+1ll 11 S - Moreover, we have by Algorithm 2 Line 9 that l19 = 1 ol I 1-7" The induction is now complete and we have || I 1-y and l1g I - for all 2 0.
(2) We first use induction to show that, given / 2 0, if min vio 8) 2 l,, then we have ming,a' (a' s) 2 ly for all 10, .K.. Since min,,a Ti,oaaa $) 2 l, by our assumption, we have the base case. Now suppose that min T (a s) 2 & for some
k 2 0. Then we have by Algorithm 2 Line that
-ं. Ti (a' 8) (1 - 11-3))Te, 8) ((or(()
2 (1- -1 Bx)er + BaLe
E,
where the inequality follows from (1) the induction hypothesis, and (2) a, (gL (a) 2 by, which follows from Lemma D.I (I) and Lemma C.I. The induction is complete.
We next again use induction to show that ming,a Ti,0(a' (a' s) 2 E for all E {0. 10.1.... (T). Since ming,a vo |s) is initialized as a uniform policy, we have the base case. Now suppose that min TL. {) 2 l for some O. Since this implies that min T/, $) 2 e for all E (0, 1,...... K}, and in addition, T/ = मं,x according to Algorithm 2 Line we have ming, क o4410 8) 2 l,. The induction is complete.
D.3 Bounding the Nash Gap
Our ultimate goal is to bound the Nash gap
NG T... -7
Σ 111
max (T' ( (aTx))T()))
(28)
We first bound the Nash gap using the value functions of the output policies from Algorithm 2. Lemma D.2. It holds that
Σ
max U' -T.K) Unt, (T,x)
of Ty
(29)
1=1.
1=1,2
Proof of Lemma D.2. Using the definition of the expected value functions, we have
Σ
max uax ( U (T). TT,K)
1
30

---

max Esuup n².
[o' [o', + (S)
esd
(5))
Esmpo
max
(S) - ve
miiii (5))
(Jensen's 's inequality)
T m,trr
1,2
Σ
Essupo
Paitiii (5)
edd
m x (s)])
TT, =.
1,12
The next lemma bounds the RHS of Eq. (29) using the actual iterates generated by Algorithm 2. Lemma D.3. It holds for E {1,2} that
S 1 1-9 (2C (T) + CT) C. (T, 27 log (Amax))
Proof of Lemma D.3. For any E S and i E (1,2), we have
(s)
vt
(8)
(s)
2
mh k TT (s)
(s)
21
r.re (s)
p. 1e (s)
x
(s)
(s)(s)
vd
7 x (s)
1=1,2
Since the RHS of the previous inequality does not depend on s, we have for E {1,2) 2) that
S
Σ 1=12
(30)
T
It remains to bound the RHS of the previous inequality. Observe that for any S and E (1,2).
we have
v. (5) V
(8)
(8)
TTK.I*
ve -s (6) v² (8)
max ('E((A))
(4') (T')TTiC
(s)TT]((())
max
min
(1 T())))(()))))=
(-AAA(A-)) )
('A((A))
<
max (
(1t) (T))T(((
(s) - max
(W W'EA(AY)
+ max w'EA(Ai)
(4')
(s)
max HEAA
min
(c)))(a
max M'EA(AY)
(u()
(5)
+ max (1²) (O)) M'EA(A))
max (n (1 A'EA(A))
+ max ('EA(A))
(M)TT((
max min ()
FEAiA 1) (n+)
31

---

min (u') (1)) (s)p H (EA()))~TEA(1
max
max PEE())) (--(((--))
min
(1') T (1))
(31)
We next bound each term on the RHS of the previous inequality.
The 1st Term on the RHS of Eq. (31). Using the definition of T(),, we have
max (
(T))((T((
(s) - T' (c)) G.TT (s, aa -
(s)-
< max
8,0" ,a
max s,a
B (2i) - 22 -,
(Si)
So = s. Ab = -''Ap" = a-1
max E (S))) - vi -
(si)
So = s, A = a' Ap¹ = a-j
5,a" aa=
The 2nd Term on the RHS of Eq. (31). Using the definition of Ti(), we have
max (4') (EE((AY)
(W)TT((
max (e') (()))))) M'D(AY)
(nt) (v2))s) - ((A)))))
max r EAAA))))
[T a (
s max
s, a
S 7 I| -
The 3rd Term on the RHS of Eq. (31). Bounding the third term requires more effort. To begin with, we decompose it in the following way:
max (4 (1t)) - max min M'EA(A)) --A(A- T
(AEA(AA)
(it)
min Tt. (T) (54) E-(A---
max w ('EA(A))
(x:T) (1T (17))) +
min -- ( (s)
max
Σ max 1= E'A(())
(1t
(32)
We next bound each term on the RHS of the previous inequality. For the first term, we have by definition of (-() that
(UT (s) + min (W-))
(4 TT) x())
max FEAIA 1)
M-EAAA -j)
max ---EA(A-)
(0T (
max (n
( (T) (Tx
EA(A-1)
(07)) (s) + (s) )TT)
max
--'EA(A-9)
$ max T
(1T (s.a T (u+ (s. a', a-
3aai,a-
E [UT (Si) + of S So = s, Ab = a², A = ag -1
= y max
8,0* at
S > ||'' i + +fll
32

---

For the second term on the RHS of Eq. (32), using the Lyapunov function Ve,o(.)) (defined in Appendix D.I), we have
Σ max 112 HEA(A))
(wT)) (1F))))
E ('E((1))
(p' [(xx()) +
max
1=122
Σ max ('E((())
{(ui-
- -u(Exx)(((
+ 2r log( Amax)
Σ (T))))))))))))))))))))))))) 11,2
S Vona(TT, (s), (x),)()
TT. (s)) + 2r log( Amax)
max (v
) + T TT (1T') (8, t)
+ s,ai,a-i
S ( (s), T (s) + 2r log( (max)) + 71107- + uT 11.0
Using the previous two inequalities together in Eq. (32), we obtain
max ('A((A) (c)))
min (n') T (cb))s)
max P-
I ( 7.. (s) + 27 1o + + ll oo + 2T
(33)
The 4th Term the RHS of Eq. (31). Using the definition of T+)-,, have
max min (1))(s)) max min (E
(()))s()))))
M'EA(A)) μ - EA(AA-9
max min EAAA 1) -s)
wiEA(At)
max
-
8,0" ,a
7/lut v loc
Finally, using the upper bounds we obtained for all the terms on the RHS of Eq. (31), we have
b w TTKK
0. + max sES
... - vt + 2 " 22yle
Vi (8), - (s)) 2r log (Amax)
3/|0,
-- x 11 2/ v || 21121 1lo
+ max Voy TT (8), T (s)) 2r log Ammax).
Rearranging terms and using Lam (t) and L, (t, k) to simplify the notation, we obtain
1 (T) + 21luz 1l + LT, K) + 2r log log(Anax))
Summing up both sides of the previous inequality for E (1, we have
Σ b
2
(2C (T) + (T) - (T, + 27 (ma(A)))))
1.1
Using the previous inequality in Eq. (30), we have the desired result.
33

---

Combining the results in Lemma D.2 and Lemma D.3 in Eq. (28), we have the following result, which bounds the Nash gap in terms of the Lyapunov functions defined in Appendix D.I.
Lemma D.4. It holds that
NG NG( o 77
1-y (2C + (.() + (T, K) + 2r log(Amax)) (Amux))
The next step is bound the Lyapunov functions, which require analyze the outer loop and inner loop of Algorithm 2.
D.4 Analysis of the Outer Loop: e-Function Update
We first consider (t) and establish one-step Lyapunov drift inequality for it.
Lemma D.5. It holds for all t 2 that
Co + 1) S (t) + (t) + 2 + 4C, K) + 6r log
(34)
Proof of Lemma D.5. For i {1, 2), using the outer-loop update equation (cf. Algorithm Line 8) and the fact that 13' (vt ) = ur. we have for any 2 0 and s E S that
u (8) v. (s) = (() T d (() (s)
= (v)( B¹ (s)) + (5) (c))
Since the minimax Bellman operator have from the previous inequality that
(-) is c-ootracttoon mapping with respect to || ll,o,
(s) (s)) z (vt) B (v:) + (s) (s) BB (v))
$ (x)) - (B: Il. + (s) (s) (f) - B (v))
<> || v. l- af (s) (c))
(35)
It remains bound the second term the RHS of Eq. (35). Using the definition of (+),,, have
(x) Ta (s) (x))
(8) (Txx (s)
max min T()))())))))))) MEA(A')
max (n') (W) -ं.x(8 T (()x (EAAA)))
max (4 (W)TTOO max min W'EA(A))
-- (T'
$ max (n'- -(.x (())))) (())(A))
+
di,x(s))
+ max (4:) (1))))) - max (E TT
min
(
(c)) - -i
+ + (f)x
+ oz oo + 37 loolloAAmmnn (mm())))))
where the last line follows from Eq. (33). Using the previous inequality in Eq. (35), we obtain
| villoo Ilvi villoo + max SES
(1))))))) (
+ max Ve (s), - x (s)) + 2/|lu + of + 3r (max).
#ES
Summing up both sides of the previous inequality for E (1, [1, we have
C. + 1) < (t) 4Cmm(() 4C, (t, K) + 67 log (Amx))
34

---

Σ max wES
(T
& (s)
To bound the last term the RHS of the previous inequality, observe that 1l
Σ max SES
(s)
- x
= Σ
1l
qi
1-1,2
1=1,2
Σ
di
1=1,2
1/2
11
gi
(a² + z 2ab)
$ / K).
(36)
Therefore, we have
(L 1) S (1) + 4m. (1) + / K) + 4L, (1, K) + 67 log( (max)-
The proof is complete.
We next establish one-step Lyapunov drift inequality for Suum (t) in the following lemma. 1/2
Lemma D.6. It holds for all t. 2 0 that L (t + 1) S Smm (t) + 2. (t. K).
Proof of Lemma D.6. Using the outer-loop update equation (cf. Algorithm 2 Line 8), we have for any 2 0 and s E S that
1 (s) + 2 (s))
Σ
1m1.2
Σ Fip (8)
1,2
Σ (8 1=122
max eES
(T))))
122
(o)) +) +T (0, as,
max
(a-)
Σ max
llc. (v:) mi (s)l 7l1o oz lolo
sES
1=1
where the last line follows from the definition of T'(). Since the RHS of the previous inequality does not depend on s, we have
||ot1 + 124 I slllut of loo +
Em ll (s) (s 1=1,2
may
The result follows from using Eq. (36) to bound the last term the RHS of the previous inequality and then using Lxum (4) and (t, k) to simplify the notation.
D.5 Analysis of the Inner Loop
In this section, we establish negative drift inequalities for the Lyapunov functions Ct k) and C, (t, k), which are defined in terms of the f-functions and the policies updated in the inner loop of Algorithm 2. For ease of presentation, we write down only the inner loop of Algorithm 2 in Algorithm 3, where we omit the subscript I, which used as the index for the outer loop. Similarly, we will write (k) for (,, k) and C=(k) for CI,1, k). All results derived for the q-functions and policies of Algorithm 3 can be directly combined with the analysis of outer loop Algorithm 2 using conditioning argument together with the Markov property.
35

---

Algorithm 3 Inner Loop of Algorithm 2: from Player i's Perspective
1: Input: Integer K, initializations % and Tû. and v-function of from the outer loop. Note that
we have 1 0c I 1
1-7' ||00 S I-y. and ming, mo(a' s) 2 & due to Lemma D.I.
2: for k = 0. 1, ....................... K do
3: (8) = (s) (x(or(g(())) - xs)) for all & &E S
4: Sample A m- (-1 Sk), and observe Sk+1 p(- Sk, Ai. Ag
5: (s.") (s, a²) +ox ((SA.A))((sa')) (Ri(Se, A A + (Sk+1) o (S A3)
for (s,a*) E S x A'
6: end for
7: Output: 4k and Ti
D.5.1 Analysis of the Policies
We consider { ] generated by Algorithm and use Vx(--) defined Appendix D. the Lyapunov function to study them. For simplicity of notation, use V=. (respec- tively, V2Vx(,, (-:)) D) to denote the gradient with respect to the first argument (respectively, the sec- ond argument). Recall that Lemma D.1 implies that TT (Tt, mt) E II, for all & 2 0. where II {(T), x²) E A(A') x A(AP) min,' (a²) 2 by, min (a²) 2 E, }. The following lemma establishes the properties of Vx(;,)).
Lemma D.7. The function Vx(:,-) has the following properties.
(1) For E [1,2), fix p= & A(A the function Vx(p², μ () as a function of pt is strongly convex with respect to || 112.
(2) Vx(x)) is L, - smooth on II,, where L, =2 2 max(||X, 12211 + 1| + X. llx).
(3) It holds for any (n', ,1² E A(A x A(A2) that
(VIVx(m ( ox), - (VaV('u''',,
-12)
7 Vx(u* 12) X1 + X 1
16
(4) For any wt IRAA and x² B8 AR we have for all (1²) 122) 11, that
(ViVx(u' , or) (u') - o. (X1 + (V2V oz)),,, (u²) or (Xzu'))
8 ( 1 max(
(|x X1 11,, (xllz)
2
S $ Vxlu 122
||ue X.su 11
Proof of Lemma D.7. To begin with, we have by Danskin's 's theorem [95] that
VxV 12) = - (X1 + xX)x2²² - <Vv(p') + X2 or (Xzu').
(37)
Similar result holds for (
(1) It is clear that the function Vx (:)) is non-negative. The strong convexity follows from the following two observations.
The negative entropy -v(-) strongly convex with respect to || l|a [97, Example 5.27].
(ii) Given i 21,2). the function maxp-1Ea(A-1) {( x + +=(ā=t)) function of p² is the maximum of linear functions in n², and therefore is convex.
It follows that, for any E 2), the function Vx (w n²) is T strongly convex in p with respect to || ||2 uniformly for all n²
36

---

(2) For any (4', ,x), (7) , E II we have by Eq. (37) that
V (1² .12) V (7' ,
||xX X2 )x² - -p²) + [(V((k)) Vv(aa)) + X2 (o= or (Xzje 1)1|2
S |X, + 112l22222 + (z.
[|X=li - |m' -
(38)
where Eq. (38) follows from Lemma C.5 and the Lipschitz continuity of (-) [96]. Similarly, we also have
12) - V2Vx(n' "2Vx("',a>)) .1a)1
-
11
$ ||x + x Ilallu*
12 +
1
-2
&
T
Using the previous? 2 inequalities, we have the following result for the full gradient of Vx (1 .):
VVx 122 - VVx 13)l
VI
(1 122)
VIV 11 +1| VVV , - V2Vx(m",
|x_:11] 2
-
Σ
2
T +
- - 2||X, + xI,1 $7- ((a + 6)2 - 2a² + 26²)
ex
121
$ 2 (6, max(1 (|| 11 11
1| X2 11
Σ 1ل 112.
The previous incquality implics that Vx(+,- is an L, -mooth function on I1, [97]. where
I, = (E max , 22211 | +X] 12
E
(3) Using the formula for the gradient of Vx(.,)) in Eq. (37), we have
(VIVx "=Vx((''4''), ,x)), - =m))
(-(X; - -x,)p² (Vv(2') + X o, (X2x') ), o,, -k²)
=(-(X, xx,)p² 1 ~Vv(p') x,] or (X2p o, (X112) -1²)
+X,,² + (VV
-1²)
(39)
= =(Vu(o,(X11)) -
- -12) -2²) (x
+ (10((8_))--13)3x////((()x1=1-1
-
where Eq. (39) is due to the first order optimality condition X1p2++ (X,x²) = Topro- ceed, observe that the concavity of v-) and the optimality condition X2 (Vv"))(X('²)) 0 together imply that
-w) (Vu(o,(X11²)) - - (Vv(nt) -
- (Volo) - sv(u²) - v(o,(X111²) - (Vulo,
(Vulo,
(X113)))
(Coneavity of v(-))
=r(m²> ~(o,(X111)) 1 (X n¹¹ -o (X1n²))
(nt)T X,p² + rv(m²))
max { Xxp2 + ru(ii))
(LE((A))
Therefore, we have from the previous? 2 incqualities that (ViVx(m) (2), o, (X,1²) -m²)
37

---

I (x+t) x1p² + =T(H")
max {(At) T "xHH² + rx(())
+ (or 110))11(((000 [2((o(XXx1) - -1-).
Similarly, we also have
(V2Vx(m "1), (= 122
$ (1²2 X212 + TT((²) )2E((d))
max {(A2) T X22 + rv(h))}
+ +O,, - (1(r) (X2xx)) -1²).
Adding up the previous inequalities, we obtain
(ViVx(u* (All",,"),,,,,,) (X - n²) + W22
- 122
I - Vx(ue, + (o, x [0,
+ (o, (X2H1))
- -1²)
I - -V(uu' + ||, (X11²) ~ + x xx
(X2rd,
12212
I Vx((", x²) + 2 - Xx2 112
x
(40)
where the last line follows from (X2=') - 12l12 S ||o, (X2p²) 1|1 + 11 S 2. Using Lemma D.7 (1) together with the quadratic growth property of strongly convex functions, we have
V2 VT
11o((x11²) - 12 S
Vx 12)1/22
It follows that
(V.V>(n' ox)), - n²) + (V2V (1² ox 12))
S - -Vx(n' 112) + (x1 - /¹ ||2|| + X2 112
S -Vx(H' .12) 2v
Vx Vx('' (H', ,,31/21 |1 + x 112
VF
S ? Vx(u n²) + Xi + x, 12.
16
where the last line follows from a² + 12 2 2ab.
(4) For any u' E Bl441 using the formula of the gradient of Vx((,-) from Eq. (37), we have
( μ22 (u))
= (-((X, +
-r (X(12²))
=(-(XI + - (rr
or (u
+(XIn² (() (x,1)(
(First order optimality condition)
=((Vu(o;(X113) - (udu)),,(())--
+ax((X211) -1²) (2(o,(ut)
$ (iIVVi,,((X113 10 (X²x1)) 121 (12ll2) 1lo+ (o+))=) - o, (X112))l2
T &
10- (x=(()))p)) - 22 + (N21tt) --2 /21121/xalaa) - -1ut-X x1121112
V2 (1 + ||aalla] (x(R*) - 1X122l2
-
Ex
Vx(u', ,13) + 8 (1) Er [1Xall2) 2 ||u² x1nu21B. 16
where the third last inequality follows from the 1. -moothnnss of v(-) on II,, the second last inequality follows from Lemma D.7 (1) together with the quadratic growth property of strongly
38

---

convex functions, and the last inequality follows from a² + 2 2ab. Similarly, we also have for any u² E IR IRlA1 that
<V2Vx (,),o-(())) - or or((x11
8 ( [xallee 2 -x21'11
Vx 12)
16
Adding up the previous two inequalities, we obtain
(ViVx(n' ,1²), o))))r(()) - (X max (|1X ||x2l12)
+ (V2Vx(4', (1,(4,,,)),, 1z)), - or (x(222))
8 ( e, S 8 Vxll (²)
2
Σ
1| X:p 11
1=122
The proof is complete.
With the properties of (x(:,-) established in Lemma D.7, we now use it as a Lyapunov function to study (Th. = generated by Algorithm 3. Specifically, using the smoothness of (x---) (cf. Lemma D.7 (2)), the update equation in Algorithm 3 Line 3, and Lemma D.7 (3) and (4), we have the desired one-step Lyapunov drift inequality for L (k)), which is presented in the following.
Lemma D.8. The following inequality holds for all & 2 0:
(1 (1- 33p
(k) + 16A2 3x
(x
l|u + 1.
T
32 A2 maxx 3k
7 7 7)2 (k) + +L,
Proof of Lemma D.8. We will use (t.) (see Lemma D.I) as the Lyapunov function study the evolution of ( (s), =s)) To begin with, we identify the smoothness parameter of V (+, (t. +)- Using Lemma D.7 (1) and the definition of Vo, (:)), we have
max |x, 12
X2 (
L, =
T
XX, l12) + +|| + X3
max max(1 (s) I13. (s)))
7
+ (17((()))) T12))
2
+
e,
T
A
2Amax
S
2
+
e,-
7(1 7)
(This follows from (v) a V (s.a', and i (1,2}.)
T
Therefore, (s, ) is an I., - smooth function on ПT. Using the smoothness of Vo,a(: :), for any E S, we have by the policy update equation (cf. Algorithm 3 Line 3) that
(S)
$
mi()))
L Σ (ll((a(())) ())))
+ +Bx +
(utce//100000333////ddd///11111d -((()))
BR (1DF
Bx (44T
38x
168
4
39

---

88k
(1.2)
(s)
Σ (s) - (1))))) -
&
T
where the last line follows from Lemma D.7 (3) and (4). Since max [TT - T-7 and
(e)
12 < A |1o + 0 olo0
have
Ve,o (Tte Tk+1 (s))
3,3k
Va, (T) =b(()) + 163, A2 max || + 1111300
4
83g
1
+
Amax
Σ
(g)
(s) 2
&
T(1
3,3k
16,3 max 1 + 1
max VoL (T) (s)))) + sES
4
83k
Amax
2
+
Σ
Σ
lob(() (s))) 2h.
Er
T(1 - 7)
(=1,2
1
3/3x
C (k)) +
16,3g max
||0 +
+ 8, ( e
+ 7(1 -(--)) )
Amax 2² Lg(lb) + 21,
4
Since the RHS of the previous inequality does not depend on s, we have
Cz 1)5
1
33&
(k)
16,3,-42 max
1/u + 2
T
83
1
Amax
2
7(1 ((1-7) (g( + 2L, 12
7
e,
33
(k: + 16,3 max u| + 12112
1
T
32 maxx 3k
Ck(k)) +2L,
(- - 7)2
where the last line follows from T $ 1/(11 7)
D.5.2 Analysis of the q-Functions
In this section, we consider of generated by Algorithm 3. We begin by reformulating the update of the q-function as a stochastic approximation algorithm for estimating a time-varying target. For
i (1,2), fixing of E TR|S| let Ft. : R(SI[44 x S x A' x A- S RSSIAA be defined as (g' 80. on an si)(ss a²) = -1 ((c.a"))(000))) (Ri a a5¹) + yo' (s1) - o' (su. df))
for all (q', sp, ap: ao s1) and (s, a²). Then Algorithm 3 Line 5 can be compactly written as
le+1 = gi + +a Sk. Ale, A, Sk+1).
(41)
Denote the stationary distribution of the Markov chain { induced by the joint policy F = (m) m by μa E A(S), the existence and uniqueness of which is guaranteed by Lemma D. and Lemma B. (1). Let F ISIA4' + |I
be defined
F((a") Eo (+) (-1.))) '~oT ((11)). Sp 1S. 5) [F' S A5' 45', SS)]
for all q¹ E R S11A4, Then, Eq. (41) can be viewed as a stochastic approximation algorithm for solving the (time-varying) equation Fg = with time-innomen innommomgoeeuuus Markovian noise {(St. AL, A (x21))220 We next establish the properties of the operators F+(-) and FG(-) in the following lemma.
40

---

Lemma D.9. The following properties hold {1,2}.
(1) It holds that || (qi, so, a/. (00",,)) - -F sp, aj. o5 - l1 - L2l2 for any (qi.
and (So, og Ov $1).
(2) holds that || F (0, 80, oy ao 81 s1)ll2 S - for all (s0, ab. an .1).
.1).
(3) FE(4)) = has a unique solution Th which is given as (p(s) (T) all 8.
(4) It holds that (F (gt) of Φ S -cllli - for all (g),9)), where Gr = MminfT. See Lemma for the definition of Mmin-
Proof of Lemma D.9. (1) For any (4i Φ and (so, ag. ao s1), we have
(F 80, aor "o 81) .1) - F F' 80, ab. a0 01)13
Σ (IF (g): S0, a0, ag s1)]({,,a) (F s0, ag. a (1)(s,)) a'))
(a.a")
(so, ab) - (50, abl)²
S ll 1/.l.
(2) For any (so, ab. an ; $1), we have
|| (0, so. ab a s1)1 (1F so, a si)l(s,
(a.a*)
= (Ro df ") + 70'()))))
S (1 7)2
where the last line follows from ||00 < 1/(1 - 7) and R2 ab. 2. S 1.
3 We first write down the explicitly the operator (-). Using the definition of Ti(),, we have
(s) = (=)() (s) (s) - d((s)), v
Since (s) 2 Pmiin > (cf. Lemma B.1 (4)) and diag(=ī (8)) has strictly positive diagonal entries (cf. Lemma D.I) for all E S and 0, the equation F (g") 0 has unique solution
T. E [R)A,,4 which given as
(s)s (s)) VsES.
(4) Using the expression of (.), we have for any lी of e RIS|IA4 that
(qi (6) (FF(ot)
Σ (a
(b((s
< min pn (8) (a' 2
sat
Mmine 11 1/11
(Lemma B.1 and Lemma D.1)
c7l1gi o/ l2.
The proof is complete.
Next, we establish a negative drift inequality for (k)). Using || as a Lyapunov function, we have by Eq. (41) that
Blllg4+1 Th+ 11
Elllgh+1
oi of क + th 2.+11133
41

---

Elllgt th 12 + Blll 22 + Blll% +2+111
+ 2a F Fi
+ +2a, (1t Sk. Al. , -
,S++1)
= (g) [k
+ 2E - x+11) (qi-1 - 9
+ 2 - (Th 9k+1)l
2 (1 20 )BBllg 0 l - BBllg++11 (ell))+B1 + 2+116
+ 2 - 4041) (
+ 2 - -ot) (ah 1k+1)]
+ 20 (B((B((((()) (1is Sk. Akr A Sk+1) =((r (gk Tc
(42)
where the last line follows from Lemma D.9 (4). The terms Blllgh+1 - d..
Te+1 1
E[ - - (gh+1 - -.),.. xx) T ( T on the RHS of Eq. (42) are bounded in the following lemma.
Lemma D.10. The following inequalities hold for all k 2
(1) Ell x1 v 1|5) Amszaa
(1-7)²
(2) (llT 11+1 5 18 Amar D
(3) Elghh11
gh. T Tht1il S 18 3
(1-1)²
(4) Elgh - Te. Th Thti
17|8 A2
T133 +
A
[
r(1
TO
Proof of Lemma D.10. (1) For any t 2 0, using Eq. (41) and Lemma D.9 (1), we have
19 vill a'll Sr, Al. , S5+ 1)
=a (gk: Sk, Al, , F', Se, Ak, Ab, (5+,
F" (0, Sk. Al. A
S
1oA1l22 + 0
1
1 1-7)
2
//S|Amax
S 0
(l S - by Lemma D.I)
1
1
4|5) a
(1 71-
The result follows by taking expectation on both sides of the previous inequality.
(2) For any k 2 0, using the definition of qR in Appendix D.1, we have by Lemma D.9 that
1 -
Σ IT() Te (s))11
=33 IIT( (+) - कं (3))
$ 32 ((1 (s)) (s)122)
4|5]Amax
(1-
The result follows by taking expectation on both sides of the previous inequality.
42

---

(3) For any k 2 O, we have
4|S|Amaxax (1 (1-
(g gie Th - S 11 Aalll - 2411l2 -
where the last inequality follows from Part (1) and Part (2) of this lemma. The result follows by taking expectation on both sides of the previous inequality.
(4) For any k 2 0, we have
(ale - The Th Tkt1)
3x Σ (gk(s) - (k), ((1))))000 (6)) Tx (s)))
ci 3x 11
T
Bx Σ. (T)) (g (b) (s))
(43)
201
where > 0 is arbitrary positive real number. We next bound the second term the RHS of the previous inequality. For any & E S, we have
IT (T)) (a)) Ty (s))]l2 (T (s)) (g (s)) + +or ( (e (1))()()) -E (s))))
(T( oz (s)) or(0x (s)))llz
(TT (o (S) (s)) T (s))]l2
Since the softmax operator o-(+) is Liptiiitz continuous with respect to ||-I|a [96, Proposition 4], we have
B1 s IT (s) (5) (gT"(s))
or (s))
Amax
7(1 7) |1 (ss In (s)
We next analyze the term B2. Using Lemma D.7 (1) and the quadratic growth property of strongly convex functions, we have
B2 (T)
(s))ll T mh (s)ll2
< (o
V2Amax Vo. ( 1/
$ (F(1->)
Combine the upper bounds we obtained for the terms B₁ and Bz, we obtain
Σ (T( कx (s)))1
$ > (B) + +B)²
2 >
( B3)
A
2A2 2
2 Σ
1 (s)) - Th (x)]111 +
(x) m2()))
72(1 - 7)2
7(1 - 7)²
2 2
Tx '11 + 4 2
< 72 - 7)3 11
7(1 - Cx (k).
Coming back to Eq. (43), using the previous inequality, we have
1 Th. Th g
43

---

11.1l9 - -
8x Bx 1 (T)
(0x (6)) T (s)))
2
201
Ci Be 19 211
A A Pk
2 maxe 3k
119
9x
(k).
2
C17
7)2
CTT(1 7)2
Choosing c1
32|S|
mng in the previous inequality and then taking expectation both sides, 7(1-7)
we obtain
17|S|Ammax
AR [L(.(())
Bit The The
[h+1)] S
Bllea
T. +
5(1 - 7)2
16
The proof is complete.
We next consider the last term on the RHS of Eq. (42), which involves the difference between the operator F (gk Sk, A Ap SS41)) ) and its expected version (g and hence can be viewed as the stochastic error due to sampling. The fact that the Markov chain [(Sk. A Sk+1)} is tume-inhomogeneuus presents challenge in our analysis. To overcome this challenge, observe that: (1) the policy (hence the transition probability matrix of the induced Markov chain) is changing slowly compared to the g-function; see Algorithm Line 3, and (2) the stationary distribution as function of the policy is Lipschitz (cf. Lemma B.1 (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 following. Similar ideas were previous used in [23, 24, 65, 41, 76] for
finite-sample analysis of single-agent RL algorithms. Recall that we use A
kk=k, On to
kz
simplify the notation.
Lemma D.11 (Proof in Appendix D.7.2). The Phllowwng inequality holds for all k: 2 zk
BI(F (cke Sk, Age AT P((D)) (dl -105 1k 24, R-1
41-
where is the mixing time of the Markov chain {Sn]n2o induced by the joint policy mh = (TT m with accuracy BRi see Eq. (11).
When using constant stepsize, we have 24 = 230 = (a log (1/ Since the two stepsizes and B differ only by multiplicative constant Ca.8. we have lim 2,@a = 0. Similarly, we also have lim 26 = O when using diminishing stepsizes.
Using the upper bounds we obtained for all the terms the RHS of Eq. (42), we have the one-step Lyapunov drift incquality for gf. Following the same line of analysis, we also obtain the one-step inequality for yz Adding up the two Lyapunov drift inequalities, we arrive at the following lemma. Lemma D.12. The following inequality holds for all le 2 2/ and E {1,2):
100 Amax 3x (+))+ (1 7)2 2k
Elc, + 1)] s (1 -xc+)) B(C,
4
Proof of Lemma D.12. For E {1,2]. we have from Eq. (42), Lemma D.10, and Lemma D.11 that
4|S) Amax
Ellgg4+1 - |1 < (1 - c Blllgg - 12 +
(a + 20r + +B)
(1 7)2
34|S|A22 3R
+ Bk BkC,(K)]
34
+ 7(1 7)2
Elllgt
qh 11]]
7)
34/S|A2 m 8k
Bk EL (k)
1 20cc, +
Billgh 1 +
7(1 7)
8
50]S|Amma
+ - 7)2
O OC R-11
44

---

where the second inequality follows from 5y. = Ca,30p with Ca. S 1. Since
CrT(1 - 7)2
Ca,
(Condition 3.1)
34 max
we have
3R [[C+(())] + 50]S|Amax
Bll Th+1 S (1 0xc, El 16
8
(1-7)²
Summing up the previous inequality for i = 1, we have
3
1 Amax
Cl k + 1)] - (1 - axc, (k), +
BIc, (1:]
(1 (1-7)) 7)² 2,02000mkkk-
4
D.6 Solving Coupled Lyapunov Drift Inequalities
We first restate the Lyapunov drift inequalities from previous sections. Recall our notation Ly (f, k) E 1 E 12. (t, k) = max,es (T, (s). xs)x (uum(t) = |ali + of loo, and (t( Ei= |ll| of loo Let F, be the history of Algorithm 2 right before the t-th outer-loop iteration. Note that of and of are both measurable with respect to Fe. In what follows, for ease of presentation, write E, for E[- Fel.
Lemma D.5: It holds for all / 2 0 that (t + 1) S (c) + 4. (t) + ( + 4C, + 6r (og(Amax).
(44)
Lemma D.6: It holds for all t 2 that
Saum (1 + 1) S 7 (1) + 222 (2,))/(1111 K).
(45)
Lemma D.8: It holds for all t, k 2 0 that
E, + + 1)] S (1 38p (t, 1642 max BR Cum (t)²
32 maxx 3k
+
/2 7)2 (k( + +2L,
(46)
Lemma D.12: It holds for all : 2 0 and k: 2 2 that
3r
+ 100|S| Amax
E, (t, k + 1)] < (1 - 02 (t, k]]
Ct,
4
(1 7)2
(47)
1 &
Adding up Eqs. (46) and (47), we have by Ca.8 S miní that
Cr) (cf. Condition 3.1)
1,7/3
12842 228
Bx
+1]
Ee + (t,
2
16 16 max
BN
Lum (1)2 + 102 Amax
(48)
7)2
D.6.1
Constant Stepsize
When using constant stepsizes, i.c., 04 ar 3k = ca, repeatedly using Eq. (48) from 2g to k we have
(t,,,(, + (t,t (1- (1-2) k-
(t,
45

---

16A2
Cuum (1) [04[S|Amas
zza.
(49)
7
(1 2
We next bound & (t, 0) + Ct, 0). For i {1,2), we have
(t, = max Vo, ( (+), n (
max Σ max (1r (()))) + =v((() - (v())((s))
1=1.2
$ 2
max
(T) a', a )) + 2r (max)))))
s,a _a=
im 1,2
< (1 1 7)
+ 2T log( (Amax),
and
8|S| Amax
(t, Σ
19:.0 h
(Lemma D.1)
(1-
(1 - 7)2
112
follows that
+ 8|8|Amax
- +t,
S (1 7)
+ 2r (max))
Lin-
(1 - 7)2
Using the previous inequality in Eq. (49), we have
B
k-
1642
Cam (t) + 204|S|Ames
(t, + (t, < Lin
1
+
max
(1 7)2 2スa, (50)
2
which implies
E, < Lin (1
3
k-zB
16A2 max C Stmmt)²= + 204|5|An
2/
2
(1 - 2c,,
Substituting the previous inequality on IE, [C (t, k)] into Eq. (47), we have
151|S| Amax zza² + BLin 1 (1- 2
B k-
[t,C, k 1)] (1 -cc,) E. (1,
(1 (1-7)2
4.A Csum (t)².
Repeatedly using the previous inequality, since ca,9 S Cr (cf. Condition 3.1), we have
Ee(Cg(t, S Lin (1 c=a))==0p BTin(k - 28)
B k-2
4A2 4 C
Crum (t) + 151 A
(1 - 732c, aga,
CGT
which implies (by using Jensen's 's inequality) that
k-2g-1
31/2
L 1/2 2/2
E, (t,, < 1/2 (1 caa)
2
+
1
1-
2
2
24 max
1/2
Lram (t) + 1/2 1/22
0.
2/2
1/2
/2/1
11/2
(1 7)2//2
Substituting the previous bound on E, (C, (1, k)2/2) into Eq. (45) and then taking total expectation, we have
K K-ag
El.Sum (t + 11] 5 7 (t) + 2L2122 (1 c,a) 1 3 + 3/112 L//// 1/2 - -20
(1-
(1- 0
2
46

---

4.A mmxx a.
a..
1/2
Crum (t)+ 26 (6]511//2Ab1
2/a2/2
C/ 21/2
(1 7)c//2
1 1+7 ?
k km
frum (1) + 21 (1 caa)
2
in
K-zg-1
81/2 2 - 2/)2/22 1
3 2
26|5|1/2AA12
(1 ?/] 23a2/22
where the last line follows from Co. I repeatedly using the previous inequality, we have for all k 2 0 that
) (cf. Condition 3.1). Since 1 + vblloo S T
64. mex
K-5a
2
1 (1+
4 1/2 (1 caa)
E[[sum (f) - 1 7
7
2
1 1-7 7
K-28-1
2,3 2/31/11
1/2 (K- - 1/2
1 3
52 A
in
1/2 20a 1/2
1-7
2)
(1- 10-7)
R-20-1
2
[1+7]
61 (K - 2g) 2/2
(
9
+
1-7 7
2
1 1-7
2
+ 52|S| 1/2
Anax
(1 (1-7) 2/3 1/2
(51)
Now we have obtained saite- bounds for Lt, k), L (t, k), and (t). The next step is to use them in Eq. (44) to obtain finite-sample bounds for L.((). Specifically, using Eq. (44), Eq. (50), and Eq. (51), we have
EL + D)J S [0] + 4B[Csum (1) + 2B|C2/2
(1, K) + 4E|C K)] + G7 (mmx))
S (t)] + 21 in (1 c)
1/2
K-28
K K-ag-1
+ 1//
1/2
(K- - -2) (1
99
26 0//511/2A//2/
280 1/2
im
2
(1 ()-7)///2
1/2
(1-
K-z8
|16|S|A Amax
+ 4Lin
2zaa + 6T log (0ggx)
2
(1 - con,,
K-ag-
266 max
+
t
798 max
1/22 1 -2z) 1/2
1
7(1 72
2
71-
2
6916|5|1/ 1/2 1//2
2ga 1/2
(1 (1c/)
< [0] + 1223|5| Amax
(1-7) 70,000000 23 1/2 + GT log(/oogsss Amaax)
K K-18-1
266 max
1 11+
805A22 20 Lin(K - 20) 1/2
3
+ 7(1 7)
max 71-))2
(1-2
1
2
2
Repeatedly using the previous inequality from 0 to T - and then using (0) -
I- we have
1
(T) - 270.42 T (1 +
T-1
max
7(1 - 7)
2
K-zg-1
805.42 max Lin(K - 22))12
8
+
T(1 - 7333
2
1223|S| Amaa
67 lolllgAAaann (Amax)
+ (1 - 33
230 1/2 +
?
47

---

Our next step is to use the bounds we obtained for (t, k), C. (t, (t, (t),, and Sum in Lemma D.4. For simplicity of presentation, we use S to mean that there exists numerical constant such that S cb. Using the previous inequality, Eq. (50), and Eq. (51), we have
8
8T (Ag()))))
N 7, 77. 7 1 Suum (T) + (T(
+
1 1-7 Cx (T, +
1-7
1-7 7
K-28-1
A max T
(1+7
T-1
A A (K 2/2 1/2
(1
T(1 - 7)3
2
7(1-7) - 7)
2
|S] Amax
:log(Amax)
2za 1/2
(1 717
The proof of Theorem 3.1 (1) is complete.
D.6.2 Diminishing Stepsizes
Consider using linearly diminishing stepsizes, i.e., On -+th. Bx = 0
kth and B = Ca, Repeat-
edly using Eq. (48), we have for all k 2 kn min(k' 1 2 zxe } that
k-1
3m
204 S Amax (1 7)2
Bm
E. (C. (1, K) (c,),)) s Lin
II
1
m=ku
m=n+
E,
16.4 max
pm
Sam (t)²
On
1
T
2
n=
m=n+1
Eg
Next, we evaluate the terms {Ê, Jisjss. Terms like {Ê, hissa have been well studied in the existing literature [24, 44, 65]. Specifically, we have from [65, Appendix A.2.] and | 4 that
< ko + h ε k h
64ez
Es S
and Eg S 2.
(k h)
It follows that
ko h 3264e|S|Ammn
32A2 max 2 +
C(,, < Lin
Caum (1)2
k +
(1 - c3)
which implies
(t,, Lin ho + h +
3264e|S|A
32A2 Laum(t)² (t)
-7)cc00 af +
Caum
(52)
Using the previous inequality E₁ Cr, (t, k)] in Eq. (47), we have
100|S|Amas
E, E, A + 1)] & (1 - axer) Eg Lt, (t. R:]]
(1 (1-7) 7)2
La 816e|S|Amme
8 BK
Lrum ())
40kk
(1 7)2
1017eTan|S|An A.l. 2.0
(1 (.CC)) Eg Log (t,):]]
(1 Pakoo
8 8k
maxx
Caum (1)²
Repeatedly using the previous inequality starting from ko, since ac, 2 1 (cf. Condition 3.1), we have
E, (t, < Lin An + h
4068.2 2 Tin | zaas +
8A2 SApaxca. Crum (sum(t)?
+
t: + (1 2
CT
48

---

which implies (by using Jensen's 's inequality) that
ku + h 7: + 1
1/2
1 A
1/2
3A a.B
1/2 Sau (1). (53)
(,(4,((,))) - L -
1/2
+
1/2 1/2 (1 (1-7)c7
C
///21/2
ko
Taking total expectation on both sides of the previous inequality and then using the result in Eq. (45), we have
ElCcum (t + 1)] S 7 B[ (1) + 2Lm
1/2
1/2 Kth
kn + h
+ 1/2 1/2 2KOK
A
1/2
K
(1 7)0
kg
1/2
6 maxcraa C.
Ssum (t)
C7 2/221/2
130c 1//2 | A/ 1/2 in
7 +
E [| (t)
O
2
(1 (1-7)e7
1/2
c- 14412 max
where the last line follows from C,,3 I inequality starting from O, we have
(cf. Condition 3.1). Repeatedly using the previous
1+ + 260e 1/2
1/0 A 1/2
2
E [[ (4) S 1-7
2KO
(54)
(1 (1- 2- 0kko
1/2
The next step to bound (t). Recall from Eq. (44) that
Et + 1)] S (t) + 4um 2E, [// (t, K)] + 4E, (t, K)] + log(Agm
Using Eqs. (52), (53), and (54) the previous inequality, we have Et + 1)] - [t), + 4B[Csum (t)
22[C2/ K)] 4B|C, + 67 (Amm)))
L30 1/2
1/2 1/2
S [0)
(1-7)c+
1/2
Okko
1/2 2KO K
4Lina
13056e S|Amax
+
+ akk
a + 6T log (Amx))
(1 (1-7)- 7)2c0,
522A2
(1+7
t
67860cI |/2 A/2 5/2
1/2
+ 7(1 - -2
2K a
2
- Te
1/2 kkk
522A
1 (1+7)
15056eLin A 1/2
S [t)
1/2 2k
7(1 7)2
2
2a Ca.9
+ 67 log mmax))
Repeatedly using the previous inequality starting from 0 to T we have
5264 T
1 1+7
T-1
15056e [8|Amax ax + (1-7)3a)) 3a ca.8
67 log( Amax)
(T) S 7(1 7)
2
1 1-?
Finally, using the previous inequality, Eq. (52), and Eq. (54) in Lemma D.4, we obtain
APhaxT T
+
T-1
Lm S
2 1/2 7 Tlog( (maxx
E x1xx)== S 7(1 7)3
+
0 +
2
(1 - 7- Ca.3
1/2
(1 7)2
The proof of Theorem 3.1 (2) is complete.
D.7 Proof of All Supporting Lemmas
D.7.1 Proof of Lemma B.1
Lemma B.1 (1), (3), and (4) are identical to [10, Proposition 3]. We here only prove Lemma B.1 (2). Consider the Markov chain } induced by my. Since {Sa is irreducible and aperiodic, there exists
49

---

positive integer such that Pry has strictly positive entries [93, Proposition 1.7]. Therefore, there exists 66 E (0, 1) such that
Prt (s. òopu((s))
for all (s, ). In addition, the constant ps introduced after Assumption 3.1 is explicitly given as Pb cxp(-66/ (8)//r)). The previous two equations are from the proof of the Markov chain convergence theorem presented in [93, Section 4.3]. Next, we consider the Markov chain {Sa} induced by an
arbitrary π 7, Since
Ta(als) = (a'ls)
S 22
Va= Ya=(a', (a',a and 8,
<[ass)
n² (a' (T (a'{s)
we have for any 8,8' E S and k: 2 that
ph (s,5')
Σ pk-l (s, so Pas (50.
Σ
p (s, 80) Σ Tbb
pk-
ma
mb(a55))
Σ
pk-1 (8, 80)
T (a|50) ((also))a(sp Pa(o.
m
T0)
30
aEA
pk-1 1 (s, so)
Σ
T(also)
T6
80
aEA
pk- p
90
P PP),s') 2 Since the previous inequality holds for all and s', we in fact have PPpk S Pk-11, (which is an entry-wise inequality). Repeatedly using the previous inequality, we obtain
22k ph
P
which implies
pr (s, 2 f pry (s,
2. p (s')
8, 2r. (6(5²)
p (8') 11 (8')
2 l. ub. Men (s'). Following the proof of the Markov chain convergence theorem in [93, Section 4.3], we have ) ///ro-1,
|| (s.-) - (-)llv I (1 - 6,62T0 (o.
s S, π E II,.
(55)
Since Amax 2 (otherwise there is no decision to make in this stochastic game), we have & < }.2 follows that - 2 Mb, > 1/2. Using the previous inequality in Eq. (55), we have
sup max | (8, Mx (v S 2(1 5, (o. ) k/ro
hEN,, #ES
2 exp
(- (-ōge Me.mikkrr
27hh Ho.inn
-2pb
(Recall that Ps = exp(- (5p(--5/rr))
2p
We next compute the mixing time. Using the previous inequality and the definition of the total variation distance, we have
sup max (8, (+ in WEll, SES
as long as
log(2/1) log(1/ps)
log(2/n)
bapen
k
22 Hb.min log(1/Pb)
2rb ph
50

---

D.7.2 Proof of Lemma D.11
For any h. 2 2b, we have
EI(F (gk, Sky Ar (kk+1) - F (9k 9xll
(I (ak Sk: Ag. Ag Sk+1) =e (9k- (9k-24 T6
N1
EI(F (gh 2o Sk. Al. A Sk+1) Ph-zz ( ( -6
N2
[[( (1h 2x Sk, A/. A Sk+1)
Fhiza (1h e) ( Tk
No
EI(F" (gk. Sk. Ak. AF Sk++) F
(sk-zu- Skr Ab. Ab Su41)) T g
N4
[[[ (gk Fa (ak
Tk))
(56)
No
To bound the terms Ni to N₂ on the RHS of the previous inequality, the following lemma is needed.
Lemma D.13. For any positive integers K1 S k2, we have (1) 1l th. 1l S
200g 1 and (2)
1-
max,es || (s) Tie [s)]] I k2
Proof of Lemma D.13. For any E [K1, 12 1), we have by Eq. (41) that
20k
11 0x1120 onxl (1k: Sk. Ag. AE Sk+1) S 1-
follows that |1 - T 11100 5 2 Similarly, for any t E [k1, - 1] and s E S, we have
(1) - n|(s))li = 30 (gl(()) (s)) ( S 2
which implies max,ee || (s) - mii (s)ll1 S 2 12-
We next bound the terms N1 to Ns. Let Fs be the alagebrra generated the sequence of random variables (So, Ai, Api, ... St-1, A A 1 5x).
The Term Ni. Using the tower property of conditional expectations, we have
N1
E[(F Sn. Ag. A Sk+1) - Fi-z, (gh-=,)) T (gh
- Tk-2w?1
E[[EFF' -u St, Ag. A Sk+1) [x==2.] k- (9h- s0s-02))1 1) (1/liho Th-2al
[F (1h- Sk. A Ao' Sk+1 Fx-zzll Fk (9h- sa )11 11ah-s Th-oa llol (57)
2
E[I FL (gk 2 Se, Ar. , ,k+1) [F-22,] - F 2x ( [2
(Lemma D.1)
1-7
2
ElILF ) Fk-2. (gk (gk==,))li ||1]
1 1- 7
+ 1-7
FF (ci Se, A A Sk+1) | [Fk=zq]= Fi [b]]
(58)
We next bound the terms on the RHS of the previous inequality. Observe that
(( Fi-za ( 1l
Σ (ss,,a)))
1F (gk -
((s,
3.a"
Σ
[y (1i'(ai (gh-eg A,A',A-i,S') - ER (F'h S,A' A ('))"')(ssaa)]
3.a"
51

---

where we use Ex to denote ( ()., - (5.-)))) for ease of presentation. To proceed, recall the following equivalent definition of total variation distance between probability measures P2:
1 sup
Il1 P22l1v
Ep, - 1.plf---.1l]ll
2 Al
It follows that
[ A, (') a²) [Bx-z A
< max
(1h a a,"",, (8)
8,0*
13) uk- (T) (a (a' (a 133]
(1 114k- - Mk- + max (}) - मंं =s (s)l + max || (s) - Tp-zz (s)]l,
2hp
mmx || Th- (s)ll max u (s) TE-z (
(Lemma B.1)
? 8 SLiBk-zee.ee
(Lemma D.13)
1
Therefore, we have
(1 oh (sk- M11 = Σ [[ (ak (( (F oz (s,
8|S| Amax Tep 1p3kk-z0
2n.k -0.
<
(59)
remains to bound the second term on the RHS of Eq. (58). Recall that we denote Ps E || as the transition probability matrix of the Markov chain {Sk} induced by joint policy n. Using the definition of conditional expectations, we have
[IE (qk- Sk. Ale, AF". Sk+1) FR-zzl
Fi
k+zz
Σ
Paj-en
80) me(s)
Σ mt(a'(s) Σ
-H (s
j=k+1
p(s'ls,, a's''ssaa,ee a 9,
2
Σ
Pay-ox
(5)-2) (x(())
(Lemma D.9)
BES
j=b+1
k-t
2
Σ SES
II
Pry-se
(Sk-2u5
P (Sk-za 8)
1 1-7 ?
j=k+1
+
pat (Su- 8) pa(ss|
k
2
II
Pr.
pet n2
2p 2k
(60)
1
1=
where the last line follows from Lemma B.1 (2). Observe that
k-
++1+
k- E+
Pay
p
Σ
P
pt-1 Rk
Pay
pt me
s=k+1
52

---

II j=b+1
Pay os (Prx
Pxx P
2+ II j=k+1
Pry-u =k
TR 211- Paplloo P P 1100
me
P P1-- Prellocs
Since Px as a function of 1-Lipschitz continuous with respect the foe -orm, we have
k+
II j=k+1
PRI-Eu
max [k-(41(s) (s)ll1 sES
Tu
26
(1 - ax (s)ll + ( (1)
max SES
I 42
(Lemma D.13)
Using the previous inequality in Eq. (60), we have
| (gk- 26 Sk. A Ar Sk+1)) 1) Fk-ea] (gi 111
1 1-7 Bk k-1 + 2pp7)
(4zz,)- 20,k- + 3k)
(Definition of zı))
1 ?
102g k
(#k 2 1)
1
Using the previous inequality and Eq. (59) together in Eq. (58), we obtain
Ni 16Lp|S|Annn Amax 1n-xxB-=aahe - k-1 + 20 3k -1 36Lp AlI RM
(1 7)2
(1 7)2
- (1-7)2
The Term N2. For any l 2 2ko we have by Lemma D.13 that
N2 S |=]| (gk- Sr. Al. Ag ,8+11) ) Fi-zx (0h-zw))la l1llllk gi [loo]
20k- Bill I (ak- Sk, Ale Ar Sk-1)l1 + || - 1l1].
(61)
1-7
Using the definition of (-),)) we have
(gk- Se, A A Sk++1]l1
Σ ((maa)))= (S). (5 Ale, A + you - (S2. At)
8,0*
(S Al. A
7o (St+1) (Sk, Ab)
7
<1
+
1-7
1-7
2
(62)
1-7
Moreover, have by Jensen's 's inequality that
Fi (ak- 2u 11
S
(63)
1 1-
Using Eqs. (62) and (63) together in Eq. (61), we have
801--2,,k11
N₂ <
71-
53

---

The Term N3. For any & 2 2g, we have
N3 S |||| (gk n2 Sk. Al. Ag S8+1) - FF ( z1)ll 1 - Tclloo
[ F (1k Sk, Alc, Az Sk+1)lla + 1F ( 111)) | th [00
B - - 11o0
(Eqs. (62) and (63))
Observe that
1 00ll000 = max
(T)))()) - (t)l
$ES
x max #ES
(r)) (+) - (8)]l
2,3 -
1 1-7
where the last line follows from Lemma D.13 and
1 T- (T(,')(,,''a
(s))li)
S max 8,0",a
Therefore, we have
83k-
N3 S (1 (1-7)² 7)
The Term N4. For any h: 2 zR. we have
N₂ S E (gk Sk. ALe AE' Sk+1) - Fr (1k- 2,, Sk. Ak, Ab, Ab'. Sk+1)ll llgt - |o]
2
< - 1 (a Sk, A Sk+1) F² F ( Sr. Al. A 1k+1)11
where the last line follows from Lemma D.I. Using the definition of Ft (.), we have
[F Se, Ai. A Sk+1) - F (gh 2x Sk, A A Sk+1)ll Σ ((s.a') ((s,a))=(8.,11)) l (Sx, A of. (Sx, At)
8,a
9h =o (Sk: Ate (S At)
< 19 =z - d oo
20k 20
(Lemma D.13)
follows that
40%-2
N4 S 71-
The Term No. For any h: > ZR. we have
N₂ E ||| (g Pi-za (1h (n 11llla [clloo)
< Ell F (gfk)
Fr (111
(Lemma D.1)
?
< 1-
Ell Fr (gi)) Fi-za (gh))1 1 + +11 (9h) Fx-z, (gk-
16Lp|S S) A
2
Fi (gf [l1]]
(64)
(1-
1-7
where the last line follows from the same analysis as we obtain Eq. (59). As for the second term on the RHS of Eq. (64), using the definition of (.), we have
[P (at) Pi-za fdd-swll1-
Σ
-k- (s)
Tk- (a (s) a²) -h-22 (s,
#ES
54

---

11 zh -
20 - -v
(Lemma D.13)
Using the previous inequality in Eq. (64), we obtain
No (allp|S|Amax// Bgck-1
400 2k.
(1 7)2
(1 (1-7)²
Combining the upper bounds we derived for the terms Ní to No. in Eq. (56), we have
- Sk. A A Sk+1)
Fk(0))
(gk [.]]
36T
21:1 Amx
88k-2H. -k.
4a 2x,
(1 (1-2) 7)2
(1 - (1-
11-
(1 - 7)2
16I.p1 ( Bk- spikk
40
(1-7)2
7)
60 Al.mmx -2..
k-
16 2/ N-
+
(1-7)2
7) )2
172,00-24.6611
(1 (1-
where the last line follows from 3 = Ca.9 S 601,p15)A (cf. Condition 3.
1
D.8 Proof of Corollary 3.1.1
The following proof idea was previous used in [15] to show the rationality of their decentralized Q-learning algorithm.
Observe that Theorem 3.1 can be easily generalized to the case where the reward is corrupted by noise. Specifically, suppose that player takes action a' and player -ł takes action a= Instead of assuming player i receives a deterministic reward Rs(s, aa", a aa)),, we assume that player receives a random reward r'(s, a", a {), where = (= is finite set) is random variable with distribution [4g(8) (*), and is independent of everything else. The proof is identical as long as y + r = 0, and the reward is uniformly bounded, i.e., max,,a* i. [r a², ",) < co. Now consider the case where player i's opponent follows stationary policy . - We incorporate the randomness of player -i's action into the model and introduce a fictitious opponent with only action a". In particular, let the random reward function be defined as jit (8, a², a", A-1) = R2 at, A-) for all (s, a²), where A- -- (-[ss, and let pss' 8, a', a²) Σ,, "(a =1o) p(s a²; a s). Now the problem can be reformulated player playing against the fictitious player with single action a", with reward function &² (i E (1) and transition probabilities p. Using the same proof for Theorem 3.1, we have the desired samile bound.
E On the Mixing Time of MDPs with Almost Deterministic Policies
Consider an MDP with two states $1, $2 and two actions 01 02. The transition probability matrix Pi of taking action 0₁ is the identity matrix Iz, and the transition probability matrix P2 of taking action d2 is P2 = [0, 1; 1, 0). Given a E (1/2, 1), let T. be a policy such that <aals)) = a and T (agls) easy to see that
for any 82), Denote P. the transition probability matrix under va. It is
1-a a
Pa
Since P., a doubly stochastic matrix, and has strictly positive entries, has a unique stationary distribution μ 1 /2.
We next compute lower bound of the mixing time of the -induced Markov chain. Let e1 = [1, 0] be the initial distribution of the states, and denote [Ix, - xx] T as the distribution of the states at time step k. Then we have
Ib+1 I&a + (1 xx) a)
55

---

(2a 1)ra + +1-
(2a 1)k+120 200 +
Σ (1 (1-a) 1)8-i
(2a 1)6+11
+
follows that
114 pk - -1 snj
bT
mill
max 1
k20
min
[|] Po - -1 sn}
k20
min {2a 1)a s 2n}
k20
log(1/21)
1,
log(1/( | (00--1] 1))
which implics lima-11 fa.n = oc. Therefore, as the policies become deterministic, the mixing time of the associated Markov chain approach infinity.
F Numerical Simulations
We first conduct numerical simulations to investigate the impact of choosing different т, which is used define the softmax operator Algorithms I and 2. Our thcoretical results indicate that there is an asymptotically non-vanishing bias due to using positive т. Intuitively, since a softmax policy always has strictly positive entries while 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 zero-sum matrix game. Let
N
17
R1 = -1
1
1 -1
0
be the payoff matrix for player 1, and let R2 - where N > a tunable parameter. Note that this matrix game has unique Nash equilibrium, which goes to the joint policy n² = (1/3, 2/3, 0), n² (0, 2/3, 1/3) as + co. In our simulations, we use constant stepsizes ag = 0,5 and 3g = 0.01 and run Algorithm 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 To enable fair comparison, functiio to compute the softmax, that is, instead of directly using o, (9) in Algorithm 1, we use a, (gf// [l As we can see in Figure 1, increases, the asymptotic error also increases, which consistent with our theoretical results.
k in Figure for different temperatures
the normalized
F1 Comparison with the Optimistic Multiplicative-Weige Update
The Optimistic Multiplicative-Wiieee
Update (OMWU) was recognized as popular learning algorithm for zero-sum matrix games [98]. Since OMWU in the payoff-based setting (or noisy- feedback setting) may not have last-iterate convergence [99], enable fair comparison, we will compare OMWU in the noiseless setting (which does enjoy last-iterate convergence [98]) with smoothed-best response dynamics. We start by writting down the algorithm.
OMWU: With initializations =] of (respectively, -ă. mi) that live in the interior of the probability simplex ((A') (respectively, )). OMWU updates (TT m iteratively according to
(a exp [iT ((a)) ((a)) R (a'))
(a4)(a')
Va' EAiE (1,2),
Eaica of (ā') exp 2n RaT (ā') - 1) R.T 1 (a))))
where 77 E (0, 1) is the stepsize.
56

---

50
0.01
45
0.1
40
== 0.2
35
== 0.5
Nash Gap
30
25
15
10
5
1000
Number Iterations
Figure 1: The Nash Gap for Different Temperatures т
OMWU
1.8
DSBR
1.6
1.4
Nash Cap
1.2
0.8
0.4
0.2
Number Iterations
Figure 2: The Nash Gap as Function of the Number of Iterations A
The Discrete Smoothed Best-Response Dynamics (DSBR): With arbitrary initializations m ((A') and Tă E A(A?), the discrete smoothed best-response dynamics update (T]. =t) iteratively according to
MK+ = (1- (1-Bx) + BRo, (RITE)) Vie [1,2},
where BR is the stepsize.
We perform two sets of numerical simulations to compare OMWU and DSBR. Our first experiment implemented on the pock-paper-scissor game, where the payoff matrix player
R1
-1
0
1
and R2 T. As we see in Figure 2, the convergence rates of OMWU and DSBR are comparable. However, DSBR seems to more stable compared with OMWU. Note that while we use softmax policies in DSBR, since the rock- seck-pape--scisorr game has unique Nash equilibrium, which is also the unique Nash equilibrium of the entropy-regullrized matrix game for any temperature 0, there is smoothing bias and the Nash gap under DSBR does converge to zero.
57

---

OMWU DSBR
1.8
1.6
1,4
Nash Cap
1.2
0.8
0.4
0.2
Number Iterations
Figure 3: The Nash Gap as Function of the Number of Iterations k
0.2
OMWU DSBR
0.15
Nash Gap
0.05
-0.05
600
850
700
750
800
Number of Iterations
k
Figure 4: The Asymptotic Behavior of Figure 3
In our second numerical simulation, set the payoff matrix of player be
N
R1
1
,
0
and R2 = - where we choose N 100. Note that as N -> xo, the unique Nash equilibrium goes to n= = (1/3,2/3 0), .2 = (0, 2/3, 1/3). In this case, we also see from Figure 3 that DSBR more stable compared with OMWU. However, since in this case, the Nash equilibrium has zero entries, due to the use of softmax policies, DSBR suffers from an asymptotically non-vanishing bias. This is clear from Figure 4, which plots the asymptotic behavior of Figure We see that OMWU converges to zero while the Nash gap from DSBR converges positive real number.
58


Reviews:
[{"review_id": "U3Cfk9NLLi", "reviewer": "Reviewer_Tp2P", "summary": "The authors focus on the problem of finite-sample convergence analysis of independent best-response-type learning dynamics in two-player zero-sum stochastic games. The dynamics are payoff based and stimulate the Shapley operator (that is known to be a contractive). Under the assumption that for any pair of policies, the induced Markov chain is irreducible and aperiodic, it is shown that in expectation the Nash gap is at most epsilon after 1/eps steps of the algorithm. Finally the authors provide results rationality type results (i.e., on the regret when the one player follows the dynamics and the other plays a stationary policy).", "questions": "Can you please explain if your results carry over for other settings like Markov potential Games?", "limitations": "Not applicable", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I think that the result of 1/eps rate is quite interesting and surprising (I would expect a rate of 1/eps^2). Moreover the techniques seem highly non-trivial (design of a novel Lyapunov type function).", "weaknesses": "Sometimes the write-up is not self-contained, but this is because of the limited space. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging comments about our work.\n\n**Question:** Can you please explain if your results carry over for other settings like Markov potential Games?\n\n**Response:** For potential games, it was shown in Swenson et al. (2018) that continuous best-response dynamics provably converges to a pure-strategy Nash equilibrium with an exponential rate. Since our learning dynamics is a discrete, smoothed, and stochastic variant of the best-response dynamics, it should converge for potential games when the stepsizes are appropriately chosen, while the analysis and the rate of convergence might be largely different. Rigorously proving this result could be an interesting future direction.\n    \nIn the Markovian setting, recall that the outer loop of our learning dynamics is an approximation of minimax value iteration, which works because minimax value iteration converges due to the contraction property of the minimax Bellman operator. For Markov potential games (MPGs), it is unclear if value iteration leads to convergence. However, since there exists a potential function for MPGs, existing results mostly use the gradient-based method, which works because the potential function naturally serves as a Lyapunov function. See for example Ding et al. (2022); Zhang et al. (2022). \n\nSwenson, B., Murray, R., \\& Kar, S. (2018). On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 56(4), 2734-2767.\n\nDing, D., Wei, C. Y., Zhang, K., \\& Jovanovic, M. (2022, June). Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning (pp. 5166-5220). PMLR.\n\nZhang, R., Mei, J., Dai, B., Schuurmans, D., \\& Li, N. (2022). On the global convergence rates of decentralized softmax gradient play in markov potential games. Advances in Neural Information Processing Systems, 35, 1923-1935. \n\n"}, {"review_id": "CHEekLGbn0", "reviewer": "Reviewer_r3LS", "summary": "Authors propose algorithms for learning the Nash equilibrium in two-player games and two-player stochastic games. The algorithm for games is effectively a single-time scale algorithm (Doubly smoothed best response dynamics). While , the algorithm for stochastic games (Double smoothed best response dynamics with value iteration) is a two-time scale approach. They show that these algorithm is independently implemented by each agent without any communication requirement and the rewards are based on actual payoffs obtained after each each action, rather than the full information setting. Also, they also show that the players reach a policy that is a best-response of the other players' (stationary) policies.\n\n", "questions": "See weaknesses.", "limitations": "They have mentioned the limitations in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The aim to reach convergence in last-iterate in zero-sum games and stochastic zero-sum games through independent learning is a challenging problem and the authors provide not only a finite sample guarantee, but also in addition, that the learned policies are best-responses to the stationary policies of other agents and achieve \"rational\" learning (Bowling and Veloso ' 2001). Also, the assumption about existence of a joint policy that induces an irreducible and aperiodic Markov chain is relatively weaker than other existing assumptions, that assume any policy always induces such an irreducible and aperiodic Markov chain or any policy created by the algorithm's trajectory is uniformly geometrically ergodic. They use coupled Lyapunov drift inequalities to guarantee convergence and finite sample guarantees.", "weaknesses": "1) If the game has a non-interior Nash, do you still get convergence? Lemma D.1 seems to say that all strategies are played with a probability lower bounded by a certain value.\n2) Is there any hope of getting a stronger probabilistic guarantee for at least the two-player zero-sum games setting? Essentially to understand the convergence of the iterates (in distribution or w.h.p)? instead of an expected sense as derived in this paper).\n3) Authors state that prior two-time scale approaches might require implicit coordination amongst players, however, their algorithm for the stochastic games is also two-time scale and it would help if they could clarify how they are able to avoid this in the algorithm and how they make up for this in the analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging comments about our work. We next provide a point-by-point response to the reviewer's comments.\n\n**Comment:** If the game has a non-interior Nash, do you still get convergence? Lemma D.1 seems to say that all strategies are played with a probability lower bounded by a certain value.\n\n **Response:** We want to clarify that, regardless of whether a Nash equilibrium is interior or not, our finite-sample bound always holds. However, the finite-sample bound in general does not imply asymptotic convergence to *zero*. Specifically, observe that in either Theorem 2.1 or Theorem 3.1, the last term on the right-hand side of the bound (which we call the smoothing bias in our paper) is asymptotically nonvanishing, and is proportional to $\\tau$, which is the temperature used in defining the softmax operator. This term captures the error between the output of the algorithm and a Nash equilibrium because a Nash equilibrium can potentially be a pure strategy (i.e., a non-interior Nash) while our learned policies are always stochastic.\n\n**Comment:** Is there any hope of getting a stronger probabilistic guarantee for at least the two-player zero-sum games setting? Essentially to understand the convergence of the iterates (in distribution or w.h.p)? instead of an expected sense as derived in this paper).\n\n **Response:** In zero-sum matrix games, the policies produced from our algorithm do enjoy mean-square convergence to the Nash distribution, denoted by $(\\pi_\\tau^1,\\pi_\\tau^2)$. Recall that the Nash distribution is the unique minimizer of the regularized Nash gap defined right before Corollary 2.2.1; see also (Leslie and Collins 2005) for the definition of the Nash distribution. The uniqueness part follows from the regularized Nash gap being a strongly convex function (thanks to the regularizer). Therefore, by the quadratic growth property of strongly convex functions, we have $\\sum_{i=1,2} \\lVert  \\pi^{i}-\\pi_{\\tau}^{i} \\rVert^2\\leq c RNG(\\pi^1,\\pi^2) $ for some constant $c>0$, which, after combined with Corollary 2.1.1., provides the mean-square convergence of $(\\pi_k^1,\\pi_k^2)$. \n\nA mean-square bound implies a high probability bound via the Markov inequality (while the tail is polynomial instead of sub-Gaussian). Investigating whether a high probability bound (with sub-Gaussian or sub-exponential tail) is achievable or not is a future direction. Also by Markov inequality, mean-square convergence implies convergence in probability, which in turn implies convergence in distribution because the limit point $(\\pi_\\tau^1,\\pi_\\tau^2)$ is deterministic. We will include this result as a corollary in our next version.\n\nLeslie, D. S., & Collins, E. J. (2005). Individual Q-learning in normal form games. SIAM Journal on Control and Optimization, 44(2), 495-514.\n\n**Comment:** Authors state that prior two-time scale approaches might require implicit coordination amongst players, however, their algorithm for the stochastic games is also two-time scale and it would help if they could clarify how they are able to avoid this in the algorithm and how they make up for this in the analysis.\n\n**Response:** To clarify, in Lines 620 - 628, we say that the proposed learning dynamics in these results are two time-scale in the sense that there is a time-scale separation between the two players. Specifically, one player is updating much faster than the other, making the learning dynamics *asymmetric* between the two, which also indicates implicit coordination. In contrast, our learning dynamics only require the update of each player's policy to be slower than the update of their $q$-functions, but crucially we do not assume a time-scale separation between the players, making our learning dynamics *symmetric*. We will clarify this point in our next version."}, {"review_id": "LtxOzEVP0l", "reviewer": "Reviewer_zACq", "summary": "This paper studied a best-response type learning dynamics in two-player zero-sum stochastic games called doubly smoothed best-response dynamics. The dynamics uses smoothed value function updates with softmax smoothed best-response, and combines minimax value iteration. Ths dynamics is payoff-based, convergent, rational, and symmetric. The author also provided the first finite-sample analysis of these type of dynamics, showing convergence to Nash equilibrium up to smoothing bias. ", "questions": "1. Do Algorithm 1 and 2 provide sublinear regret guarantee for one player when the other player might be an adversary? ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Finite-sample analysis (or convergence rates analysis) for payoff-based (or noisy bandit feedback-based) learning dynamics in stochasitc games is an interesing question with practical importance. This paper contributes to this area by the first finite-sample analysis of a payoff-based best-response-type independent learning dynamics for zero-sum stochastic games. \n2. This paper is well-written and easy to follow. I appreciated it that the authors provided detailed discussion and high-level ideas of the algorithm and proof sketch for the main results.", "weaknesses": "The claim that the proposed dynamics is *convergent* and *rational* seems not rigorous since the smoothing bias $\\tau$ persists over time and no convergence to exact Nash equilirium or best response is really proved. One possible fix might be introducing a decreasing parameter $\\tau_t$ so that exact convergence can be shown. This might significantly slow down the convergence of other bias terms because of the exponetionally dependence on $\\tau$. The proposed dynamics is thus very slow in terms of convergence to Nash equilirium and this is a weakness of the current work. \n\nMinor comments:\n\n1. Line 277, $Q(s,a^{i}, a^{-i})$ has not been defined.\n2. Under Line 284: one term should be $R^i(s, a^{i}, a^{-i})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the nice comments about our presentation. We next provide a point-by-point response to the reviewer's comments.\n\n**Comment:** The claim that the proposed dynamics is convergent and rational seems not rigorous since the smoothing bias  persists over time and no convergence to exact Nash equilirium or best response is really proved. One possible fix might be introducing a decreasing parameter  so that exact convergence can be shown. This might significantly slow down the convergence of other bias terms because of the exponential dependence on $\\tau$. The proposed dynamics is thus very slow in terms of convergence to Nash equilirium and this is a weakness of the current work. \n\n**Response:** Please see the response to the common comments from the reviewers in the beginning of this page.\n\n**Comment:** Minor comments: Line 277,  $Q(s,a^i,a^{-i})$ has not been defined. Under Line 284: one term should be $R(s,a^i,a^{-i})$.\n\n**Response:** In Line 277, we use $Q$ as a dummy variable to introduce the notation. We will change the notation to avoid confusion in the next version. $R(a,a^i,a^{-i})$ is a typo, we will correct it in our next version. \n\n**Comment:** Do Algorithm 1 and 2 provide sublinear regret guarantee for one player when the other player might be an adversary?\n\n**Response:** For simplicity of illustration, consider the matrix-game setting. Our learning dynamics is closely related to the celebrated smoothed fictitious play for zero-sum games in the sense that their corresponding ODE is the same, which is the continuous smoothed best-response dynamics $\\dot{\\pi}^i=\\sigma_\\tau(R^i\\pi^{-i})-\\pi^i$, $i\\in \\{1,2\\}$. It was shown in the existing literature \n(Benaïm and Faure 2013) that smoothed fictitious play (with a diminishing sequence of temperatures $\\{\\tau_k\\}$) is consistent, which implies that the average regret goes to zero asymptotically. See (Benaïm and Faure 2013) Definition 1.1 for the definition of consistency and (Benaïm and Faure 2013) Theorem 1.8 for the result. Since our learning dynamics is a discrete and stochastic variant of the smoothed best-response dynamics, it is conceivable that our learning dynamics can also be consistent. Rigorously proving the result and explicitly characterizing the rate at which the regret goes to zero are interesting future directions.\n\nBenaïm, M., \\& Faure, M. (2013). Consistency of vanishingly smooth fictitious play. Mathematics of Operations Research, 38(3), 437-450."}, {"review_id": "d3ROQLpWow", "reviewer": "Reviewer_bFVC", "summary": "The authors propose a doubly smoothed best-response dynamics for two-player zero-sum Markov games, with matrix games as the degenerate case. Upper bounds of Nash Gap with bias and regularized Nash Gap without bias are presented.", "questions": "Please see the Weakness section.", "limitations": "Yes, there is no potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The technical sections are concrete and solid. The idea of simultaneously smoothly updating in the value (q) space and the policy (simplex) space appears novel. In such a way, each player is facing a much more stable environment than simply smoothing in the value space. As a consequence, the convergence results are natural outcomes of such an algorithmic design. Moreover, the Assumption 3.1 makes the results more appealing in a sense that it deviates from typically made assumptions in RL analysis.", "weaknesses": "Some major concerns:\n\n(1) The \"first form of smoothing\" in the policy space is very similar to the mixed strategy in fictitious self-play but not exactly the same. In fictitious self-play, the policies are mixed in the way of having $1-\\alpha_k$ vs $\\alpha_k$ probabilities to select the old policy vs the new best response. In comparison, here the authors simply averaged two stochastic strategies. Even with the explanations provided in the paper, it is still not very clear to me why the authors would want to deviate from the classical practice in learning Markov games (or extensive form games), which is backed by enormous amount of practical implementations.\n\n(2) While the authors claim that the learning dynamics are independent for the two players, the learning rates of them are tied through a constant, which makes the claim somewhat questionable. Please elaborate more about your definition of being \"independent\".\n\n(3) The bound for Nash gap is somewhat weak. Apart from the term $\\ell_\\tau$ that is exponential in $\\tau$, the constant $c_2$ also has both $O(\\tau)$ and  $O(\\tau^{-1})$ terms, which requires balancing. Overall, I think a corollary with the best choice of $\\tau$ is highly desirable to at least let readers to directly evaluate the strength of the bound.\n\n(4) The bound of regularized Nash gap is not at all surprising -- it appears rather standard in minimax (saddle point) optimization with regularized geometry. So the real emphasis should be the Nash gap itself. Although I see the authors discuss the natural difficulty for softmax policy algorithms to converge without bad dependencies on the temperature $\\tau$, it still feels quite vague why this is the case -- I believe a deeper illustration with math will greatly strengthen the paper -- it won't make the Nash gap look as unsatisfying as it appears now.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the nice comments about our learning dynamics and the presentation of our technical sections. We next provide a point-by-point response to the reviewer's comments.\n\n**Comment:** The \"first form of smoothing\" in the policy space ... \n\n**Response:** To our knowledge, fictitious play refers to the learning dynamics where each player estimates its opponent's policy by taking an empirical average of the opponent's historical actions and then best responds to that estimated policy. It is not entirely clear to us whether the fictitious self-play (the reviewer refers to) is the same as the fictitious play we illustrated above. We would greatly appreciate it if the reviewer can provide more information or pointers to the references. \n\nOn the other hand, it seems that the learning dynamics the reviewer describes (\"the policies are mixed in the way of having  $(1-\\alpha_k)$ vs $\\alpha_k$  probabilities to select the old policy vs the new best response\") is exactly what we are doing here. Using zero-sum matrix games for illustration, the new policy from our policy update equation is a convex combination of the old policy and the new best response (estimated through the $q$-function): \n\n$\\pi_{k+1}^i=\\pi_k^i+\\beta_k(\\sigma_\\tau(q_k^i)-\\pi_k^i)=(1-\\beta_k)\\pi_k^i+\\beta_k\\sigma_\\tau(q_k^i)$, \n\nwhich can exactly be interpreted as w.p. $1-\\beta_k$ taking actions according to the old policy and w.p. $\\beta_k$ taking actions according to the new best response (up to a smoothing using softmax). The reason that we choose the convex combination parameter to be $\\beta_k\\ll \\alpha_k$ (which is the stepsize for the $q$-function) is to ensure that the policies are evolving in a slower time scale.\n\n**Comment:** While the authors claim that ... \n\n**Response:** Our learning dynamics is independent in the sense that to carry out the algorithm, each player only needs to use its local information, i.e., its own actions and the realized payoffs. We agree with the reviewer that for our algorithm to achieve provable guarantees, the stepsizes used by the two players should be of the same order. We will clarify this in our revised manuscript. That being said, this type of conditions on stepsizes are actually common in the existing literature studying independent learning dynamics. For example, even for asymptotic convergence, the results in Leslie and Collins (2005), Sayin et al (2021) require the stepsizes used by the two players to be of the same order.\n\nLeslie, D. S., & Collins, E. J. (2005). Individual Q-learning in normal form games. SIAM Journal on Control and Optimization, 44(2), 495-514.\n\nSayin, M., Zhang, K., Leslie, D., Basar, T., & Ozdaglar, A. (2021). Decentralized Q-learning in zero-sum Markov games. Advances in Neural Information Processing Systems, 34, 18320-18334.\n\n**Comment:** The bound for Nash gap is somewhat weak ... \n\n**Response:** Please see the response to the common comments from the reviewers in the beginning of this page.\n\n**Comment:** The bound of regularized Nash gap is not at all surprising ...\n\n**Response:** We agree with the reviewer that the finite-sample bound is qualitatively similar to existing work studying saddle point optimization problems. However, there are two major differences of this work in terms of the algorithm and the sampling. One is that almost all existing results studying saddle point problems in optimization use gradient-based method (including mirror descent), while our learning dynamics is best-response type, which is more natural in the game setting. Second, the sample collection process in learning is significantly different from that in optimization. In particular, to estimate the marginalized payoff to the opponent, our learning dynamics introduces the $q$-function, which is updated using an asynchronous stochastic approximation algorithm based on the realized payoffs. The fact that the update for the $q$-function is asynchronous is the main reason for us to have a constant that is exponential in $\\tau$ in the bound, which we will illustrate in more detail in the next paragraph. To our knowledge, for payoff-based best-response learning dynamics, there are no existing results that provide last-iterate finite-sample analysis.\n    \nWe next provide a detailed elaboration on why we have an exponential dependence on $\\tau$ in the bound. For simplicity of illustration, consider the zero-sum matrix game setting. The update equation for the $q$-functions in Algorithm 1 performs asynchronous update as only one component (which corresponds to the action taken at time step $k$) of the $q$-function is updated in the $k$-th iteration. Therefore, suppose an action is never taken in the algorithm trajectory, we cannot hope for convergence as the specific component of the $q$-function is never updated during learning. Similarly, suppose an action is rarely taken in the learning dynamics, we would expect the overall convergence rate to be slow. Therefore, the finite-sample bound should depend on the minimum frequency of taking actions in the learning process. This is captured by the quantity $\\min_{1\\leq k\\leq K}\\min_{a^i}\\pi_k^i(a^i)$, which is lowered bounded in Lemma D.1. Due to the exponential nature of softmax functions, the lower bound is also exponential in $\\tau$, which eventually leads to the exponential dependence in $\\tau$ in the finite-sample bound. \n\nWe will add this discussion with more mathematical details to the next version of this work.\n\n"}]

Author rebuttal:
We thank all reviewers for their time and effort in reviewing this work. We here provide the response to the common comments raised by the reviewers. The point-by-point response to each reviewer's individual comments is provided under the corresponding review.

**Common Comments:** 

*Major comment from Reviewer zACq:* The claim that the proposed dynamics is convergent and rational seems not rigorous since ...

*The (3)rd comment from Reviewer bFVC:* The bound for Nash gap is somewhat weak ...

**Our Response:** We agree with the reviewers that the convergence bound is not asymptotically vanishing because of the presence of the smoothing bias, which will be made clear in the next version. In the next version, we will also explicitly choose the temperature $\tau$ to provide an overall (possibly slower) rate of convergence to a Nash equilibrium. The consequence of having slow convergence to a Nash equilibrium is due to having a constant that is exponential in $\tau$ in the bound, which dominates other terms that are polynomial in $\tau$. We have acknowledged this as a weakness of this work in the conclusion section. 
    
In general, we believe that achieving a sharp (polynomial) last-iterate convergence to a Nash equilibrium (without regularization) with best-response learning dynamics is a much more challenging problem. Recall that for fictitious play (which is the simplest best-response dynamics, and inspires our algorithm design), while Samuel Karlin conjectured an $\mathcal{O}(1/k^{1/2})$ rate of convergence in 1959, the state-of-the-art provable rate of convergence is $\mathcal{O}(1/k^{1/(m+n-2)})$ (where $n=|\mathcal{A}^1|$ and $m=|\mathcal{A}^2|$) provided in Shapiro, H. N. (1958). Note that this provable rate, while being polynomial, is *dimension* dependent, and hence can be arbitrarily slow when $m$ and $n$ are large. Therefore, establishing dimension-independent polynomial rate of convergence for fictitious play remains as an *open problem* for more than $70$ years. Compared with fictitious play, our algorithm is payoff-based (more challenging than fictitious play where the opponent's actions can be observed), and achieves $1/K$ rate of convergence to the regularized Nash, while achieving a worse rate of convergence to the true Nash. This, to some extent, also reflects the challenge in establishing dimension-independent polynomial rate of convergence for best-response type learning dynamics. 

That being said, this work provides **the first last-iterate finite-sample analysis of best-response independent learning dynamics** in the literature. Investigating the possibility of achieving an improved rate of convergence is a compelling future direction.     

Shapiro, H. N. (1958). Note on a computation method in the theory of games. Communications on Pure and Applied Mathematics, 11(4), 587-593


Meta-review: This paper examines examines the problem of payoff-based equilibrium learning in two-player zero-sum games. The authors analyze two settings: finite games (which is intended as a "warm-up"), and then, stochastic games. In both settings, they provide a finite-sample convergence rate analysis assuming that players only observe the rewards that they observed in-game.

This paper was discussed extensively by the reviewers, area chairs and senior area chairs. Initially, the reviewers were reluctant and raised a number of concerns, several of which were addressed by the authors' rebuttal, ultimately leading to a positive reassessment.

At the same time, during the discussion phase, the following issues emerged:
- Contrary to what the authors state, the idea of what they call the "doubly smoothed best response" (DSBR) dynamics has been around in the literature for some twenty years now (from the work of Leslie and Collins, 2003). In fact, the basic idea of this algorithm is well-known in the field (see e.g., the classical treatments of Bertsekas & Tsitsiklis, 1996, and Sutton & Barto, 1998), so this cannot be claimed as a contribution of the paper.
- Regarding the novelty of the analysis, the authors stated in the discussion phase that they employed the Lyapunov function of Hofbauer and Hopkins (2005). However, they make no mention of this in the paper, and instead suggest that "there is no off-the-shelf Lyapunov function" so they had to design it from scratch.

Since the base algorithm used by the authors has been around for so long (and the same is true for the core elements of the authors' Lyapunov analysis), the paper has to be thoroughly revised to clarify that these algorithmic developments are not due to the authors (this includes the abstract, the introduction, the "design" paragraphs in Section 1.1, the relevant parts of Section 1.2 (where no mention is made of the work of Hofbauer & Hopkins), Section 1.3 (the algorithm they use has been used extensively, in both games and RL), the motivation they provide in Section 2.1, the name of the algorithm, etc. The extension of the algorithm to the stochastic game is likewise natural and straightforward, so the corresponding parts should be toned down as well.

These concerns would require extensive revision work to be addressed, definitely more than what would be considered a "minor revision" (i.e., a revision not requiring a second round of reviewing). At the same time, the authors' finite-sample analysis (especially in the setting of stochastic games) does appear novel, and provides a step forward in our understanding of equilibrium learning in zero-sum (stochastic) games.

Thus, taking everything into account (and despite the above limitations), the paper's analysis and results provide a number of fruitful insights into an active research field. In view of this, the committee's view is that the merits of the paper outweigh its flaws, hence my "accept" recommendation. At the same time, I should stress that this decision is made with the understanding that the authors commit to revise their paper as indicated above for the camera-ready phase. With this proviso, I am happy to recommend acceptance.

**References for the authors:**
1. Josef Hofbauer and Ed Hopkins, *Learning in perturbed asymmetric games,* Games and Economic Behavior 52 (2005), no. 1, 133–152.
2. David S. Leslie and E. J. Collins, *Convergent multiple-timescales reinforcement learning algorithms in normal form games,* The Annals of Applied Probability 13 (2003), no. 4, 1231–1251.
3. Richard S. Sutton and A. G. Barto, *Reinforcement learning: An introduction,* MIT Press, Cambridge, MA, 1998.
Decision: Accept (poster)