Year: 2021

Abstract:
We introduce algorithms based on natural actor-critic and analyze their sample complexity for solving two player zero-sum Markov games in the tabular case. Our results improve the best-known sample complexities of policy gradient/actorcritic methods for convergence to Nash equilibrium in the multi-agent setting. We use the error propagation scheme in approximate dynamic programming, recent advances for global convergence of policy gradient methods, temporal difference learning, and techniques from stochastic primal-dual optimization. Our algorithms feature two stages, requiring agents to agree on an etiquette before starting their interactions, which is feasible for instance in self-play. However, the agents only access to joint reward and joint next state and not to each other’s actions or policies. Our complexity results match the best-known results for global convergence of policy gradient algorithms for single agent RL. We provide numerical verification of our methods for a two player bandit environment and a two player game, Alesia. We observe improved empirical performance as compared to the recently proposed optimistic gradient descent-ascent variant for Markov games.

text: We introduce algorithms based on natural actor-critic and analyze their sample complexity for solving two player zero-sum Markov games in the tabular case. Our results improve the best-known sample complexities of policy gradient/actorcritic methods for convergence to Nash equilibrium in the multi-agent setting. We use the error propagation scheme in approximate dynamic programming, recent advances for global convergence of policy gradient methods, temporal difference learning, and techniques from stochastic primal-dual optimization. Our algorithms feature two stages, requiring agents to agree on an etiquette before starting their interactions, which is feasible for instance in self-play. However, the agents only access to joint reward and joint next state and not to each other’s actions or policies. Our complexity results match the best-known results for global convergence of policy gradient algorithms for single agent RL. We provide numerical verification of our methods for a two player bandit environment and a two player game, Alesia. We observe improved empirical performance as compared to the recently proposed optimistic gradient descent-ascent variant for Markov games.

heading: 1 INTRODUCTION
text: We study two-player zero-sum Markov game framework which is a key model with broad applications in competitive reinforcement learning (RL), robust RL, and many others Zhang et al. (2019a; 2021). This framework is introduced by Shapley (1953) as stochastic games and popularized in RL with Littman (1994). In its basic form, two agents with competing interests interact in an environment where the reward and the state transition depend on the actions of both players. Even with this simplicity, such systems achieved impressive success in game-playing and robotics (Kober et al., 2013; Silver et al., 2017; Mnih et al., 2015; Vinyals et al., 2019; Brown & Sandholm, 2019).
While value-based methods offer near-optimal guarantees (Sidford et al., 2020; Bai et al., 2020; Bai & Jin, 2020; Xie et al., 2020; Tian et al., 2020), policy gradient (PG) methods, including actor-critic (AC) and their natural counterparts natural PG (NPG) (Kakade, 2001) and natural AC (NAC) (Peters & Schaal, 2008), only have limited guarantees, despite their model-free and easy-to-implement structure, flexibility and generality (Schulman et al., 2015; 2017; Wang et al., 2016).
The PG methods (Kakade, 2001; Sutton et al., 2000) directly optimize the value function in the policy space— a non-convex optimization problem even in the basic single agent, tabular setting. Intriguingly, recent results demonstrate globally optimal convergence of PG methods by identifying a hidden convexity structure for single agent RL (Agarwal et al., 2020; Cen et al., 2020; Mei et al., 2020; Bhandari & Russo, 2019; 2021; Xu et al., 2020b; Lan, 2021; Khodadadian et al., 2021b; Hong et al., 2020; Xu et al., 2020a; Khodadadian et al., 2021b), and multi-agent RL (MARL) (Daskalakis et al., 2020; Wei et al., 2021; Zhao et al., 2021).
The existing results on PG methods for tabular two-player zero-sum Markov games mostly focus on decentralized algorithms with sample complexities Õ(ϵ−12.5) (Daskalakis et al., 2020), Õ(ϵ−8), and even Õ(ϵ−4), yet with some limitations (Wei et al., 2021); see Section 1.1 for the details. With function approximation, Zhao et al. (2021) obtains Õ(ϵ−6) sample complexity when given access to unbiased sampling oracles of the value functions.
On the other hand, the best-known sample complexity for global optimality for single agent problem is Õ(ϵ−2) in the tabular case (Lan, 2021). As this complexity is achieved by value-based/modelbased methods in the multi-agent setting (Sidford et al., 2020; Zhang et al., 2020), one expects a similar complexity for policy-based methods. Our work precisely bridges this gap and develops policy gradient methods whose performance for MARL is closer to their single agent counterparts.
Contributions. We propose algorithms based on natural actor-critic (NAC) framework for solving two-player zero-sum Markov games in the tabular case. Our sample complexity results match the best-known ones for global optimality in the single agent setting (Lan, 2021; Khodadadian et al., 2021b; Hong et al., 2020; Xu et al., 2020b). In particular, we show that by using inner loops for policy evaluation and a carefully designed algorithm, the sample complexity to get an ϵ-approximate Nash equilibrium, is Õ(ϵ−2), by assuming a uniform lower bound on the policies. Without this assumption, we show Õ(ϵ−4) complexity.1
Surprisingly, we achieve these results—to our knowledge, for the first time with policy gradient methods—mostly by a careful adaptation of the recent results for policy gradient methods in single agent setting, temporal difference learning, two-stage error propagation framework of policy iteration (Perolat et al., 2015), and by employing techniques from stochastic primal-dual optimization.
These developments require a careful algorithm design and analysis. In particular, two-stage nature of the algorithm incurs biases between the stages that we have to control carefully. Obtaining Õ(ϵ−2) complexity requires a tighter analysis for both stages of the algorithm, with strict control on the aforementioned bias. Therefore, it requires more advanced techniques and algorithms, inspired from the stochastic primal-dual optimization literature. We explicitly highlight our important new techniques as insights in the sequel. The full proofs are included in the appendices.

heading: 1.1 RELATED WORKS
text: Policy gradient methods. There is growing interest in global convergence of PG methods in the single agent setting. Several works showed convergence rates of natural policy gradient (NPG) in the tabular setting by assuming access to exact value function oracle (Agarwal et al., 2020; Cen et al., 2020; Mei et al., 2020; Bhandari & Russo, 2019; 2021) or when value functions are estimated from the data (Shani et al., 2020; Xu et al., 2020b; Lan, 2021; Khodadadian et al., 2021b; Hong et al., 2020; Xu et al., 2020a; Khodadadian et al., 2021b). To our knowledge, the best sample complexity for NPG methods with inner loop for policy evaluation (which we refer to as NAC) is Õ(ϵ−2) and is due to (Lan, 2021). For single loop NAC with online policy evaluation, the best sample complexity is Õ(ϵ−4) as obtained in (Khodadadian et al., 2021b; Hong et al., 2020; Xu et al., 2020b) (see (Khodadadian et al., 2021a, Table 1)). For a general overview of results in MARL we refer to Zhang et al. (2019a).
Policy gradient methods for two-player zero-sum Markov games. With the positive results on global convergence of PG methods, translating these results to the competitive MARL has been the goal of many recent works. In particular, independent policy gradient methods with the agents interacting symmetrically has been considered in Daskalakis et al. (2020); Wei et al. (2021). The work of Daskalakis et al. (2020) built on Agarwal et al. (2020) by using REINFORCE estimator (Williams, 1992) and obtained sample complexity of Õ(ϵ−12.5) for reaching to one-sided Nash equilibrium. The algorithm of Wei et al. (2021) built on optimistic gradient descent-ascent (OGDA) method combined with a running estimate of the value function, obtaining Õ(ϵ−8) sample complexity for finding a policy pair with small duality gap. In addition, Wei et al. (2021) showed improved complexity Õ(ϵ−4) when restricted to Euclidean projections onto the simplex with metric subregularity assumption. There are two subtleties about this result: First, as pointed out in Daskalakis et al. (2020), metric subregularity constant can be arbitrarily small, resulting in degradation of the rate. Second, as also pointed out by Wei et al. (2021), this result is limited to Euclidean setting and cannot be extended to the NPG with softmax policy update, which requires projection with KL divergence. The algorithm can be seen similar to the gradient ascent algorithm in Agarwal et al. (2020). As
1In Appendix E, we design an algorithm based on single loop NAC with the complexity of Õ(ϵ−4) (and O(ϵ−7) without assuming lower bounded policies). Our results on this algorithm is, to our knowledge, the first finite-sample analysis of single loop NAC-based methods for two-player zero-sum Markov games.
x,y is the time that it takes to go from state s to state
s′ by using policy pair x, y (Wei et al., 2021, Assumption 1). ‡This Õ(ϵ−4) complexity by Wei et al. (2021) requires using Euclidean projections onto the simplex instead of softmax updates and depends on the metric subregularity constant. Hence it is not applicable to NPG.
shown in Agarwal et al. (2020) for single agent problems, NPG methods have much better convergence properties than Euclidean projected gradient ascent methods. For comparison with the works in Daskalakis et al. (2020); Wei et al. (2021), we also refer to Remark 2.1 and Table 1.
Another very related work to ours is by Zhao et al. (2021) which considered (i) tabular setting with exact value functions and (ii) online setting with function approximation, also using the error propagation scheme of Perolat et al. (2015). Building on Agarwal et al. (2020), this work showed Õ(ϵ−6) sample complexity with function approximation, with access to unbiased samples of the value functions. In contrast, we focus on the tabular setting and we do not assume access to unbiased value function oracles. Indeed, lack of unbiased samples for value functions required us to use new insights described in the sequel, to derive the tighter complexities Õ(ϵ−2) and Õ(ϵ−4). Policy gradient methods for linear quadratic regulator (LQR). For zero-sum LQR, Zhang et al. (2019b); Bu et al. (2019) showed global convergence of PG with exact value function oracles. These methods have a nested structure where one player computes best-response and the other does policy gradient updates. Recently, Zhang et al. (2021) built on Zhang et al. (2019b) to derive sample complexities when value functions are estimated from data.

heading: 2 PRELIMINARIES
text: Notation. We consider the tabular setting with finite state and action spaces denoted by S, A, B and the discount factor γ < 1. The policy of the min agent is x and the max agent is y, with action sets A,B, respectively. At state s, both agents take actions independent of each other: a ∼ x(·|s) and b ∼ y(·|s). Based on the actions, the environment transitions to the next state s′ ∼ P (·|s, a, b) and the agents receive reward |r(s, a, b)| ≤ 1. Given a policy pair x, y, we denote the induced steadystate distribution as ρx,y . Let U denote the uniform distribution for states that we also take as the initial state distribution for simplicity. We denote the probability simplex as ∆. Given a policy x, we sometimes use the notation xs for x(·|s) in the proofs. We use e(st) ∈ R|S| to denote the vector such that e(s) = 1 if s = st and e(s) = 0, if s ̸= st. We use the same notation for e(st, at). The value function for state s is defined as
V x,y(s) = Ex,y [ ∞∑ t=0 γtr(st, at, bt)|s0 = s ] ,
where Ex,y is over random variables st, at, bt for all t ≥ 0 as at ∼ x(·|st), bt ∼ y(·|st) and st+1 ∼ P (·|st, at, bt). Similarly, the action value function is defined as Qx,y(s, a, b) = Ex,y [ ∑∞ t=0 γ
tr(st, at, bt)|s0 = s, a0 = a, b0 = b]. With these definitions, we can state the formal problem. For all s ∈ S, we aim to solve
min x(·|s)∈∆ max y(·|s)∈∆
V x,y(s).
We denote the information needed in algorithms as oracles. We provide the background on NPG, NAC, TD(0) in Appendix A.
Nash equilibrium. We assume the existence of a pair of policies x⋆, y⋆ that are Nash equilibrium, namely, for all s, V x
⋆,y(s) ≤ V ⋆(s) := V x⋆,y⋆(s) ≤ V x,y⋆(s). We are interested in finding a onesided Nash equilibrium, similar to Daskalakis et al. (2020); Zhao et al. (2021); Zhang et al. (2019b);
Bu et al. (2019). As mentioned in Daskalakis et al. (2020), for the other player, one can re-run the algorithm by switching roles to have the guarantee for both players. In particular, for the initial state distribution U , we seek for xout such that
Es0∼U [max y V xout,y(s0)− V ⋆(s0)] ≤ ϵ.
It is easy to prove that this quantity on the LHS is 0 if and only if xout is a Nash equilibrium.
Interaction procedure. We use the interactions of the agents with the environment to estimate the value functions and related oracles for the running of the algorithm. At each interaction, agents have access to (si, ai, r(si, ai, bi), si+1) and (si, bi, r(si, ai, bi), si+1), respectively. In terms of access of agents, our oracle model is similar to Daskalakis et al. (2020); Wei et al. (2021). However, one difference is that we require a game etiquette: Our algorithms have two stages where the agents have to behave differently. As long as this etiquette is respected by the agents (for example embedded to players in the beginning of the game), they do not need further communication.
Softmax update rule/NAC. Given Kullback-Leibler divergence KL and action-value function Qxt ,
xt+1(·|s) = PKL(xt(·|s), Qxt(s, ·)) := arg min x(·|s)∈∆ ⟨Qxt(s, ·), x(·|s)⟩+KL(x(·|s), xt(·|s)), (1)
is known as NPG with softmax parameterization (Agarwal et al., 2020, Lemma 5.1). When there is a critic estimating Qxt , along with actor updating xt with NPG, this algorithmic framework is called natural actor-critic, in short, NAC. We focus on KL divergence for simplicity and its wide use. Our developments also hold for more general Bregman divergences as Zhan et al. (2021).
Assumption 1. There exists ρ such that, for any policy iterate pair xt, yt, for any state s, it holds that ρxt,yt(s) ≥ ρ > 0, where ρxt,yt is the stationary state distribution induced by the policy pair. Assumption2. There exist x, y such that, for any policy iterate pair xt, yt, for any state action tuple s, a, b, it holds that xt(a|s) ≥ x > 0, yt(b|s) ≥ y > 0.
Our rationale on the assumptions. Assumption 1 and 2 essentially mean positive definiteness of the sampling matrices in policy evaluation (see eqs. (30), (34) and (42)). To our knowledge, some form of this assumption is required in most of the existing work on temporal difference (TD) (including TD(0)) methods for policy evaluation (Bhandari et al., 2018; Xu et al., 2020b; Khodadadian et al., 2021a; Lan, 2021; Hong et al., 2020; Xu et al., 2020a; Wu et al., 2020; Zou et al., 2019) (see App. A). The complexity Õ(ϵ−2) requires Assumption 2 even for single agent problems (see (Lan, 2021, Rem. 1, Sec. 5.2)).
Remark 2.1. As summarized in Table 1, similar assumptions to Assumption1 are used in Daskalakis et al. (2020); Wei et al. (2021). In particular, each of these assumptions ensure that all action-state pairs are observed with nonzero probability throughout the game. Moreover, by additionally requiring Assumption 2, we can obtain the complexity Õ(ϵ−2), matching the single-agent counterpart.
Markovian bias. For simplicity, we assume that we sample from the steady state distribution of a given policy pair. During normal interaction with the environment, this is not the case and we obtain a single stream of data. Hence, TD(0) update is biased—commonly referred to as the Markovian bias. A large body of literature in the single agent literature showed that the effect of this bias in TD(0) update is essentially additive and can be handled by assuming uniform mixing of the induced Markov chain (Wu et al., 2020; Bhandari et al., 2018; Zou et al., 2019; Khodadadian et al., 2021b; Xu et al., 2020b;a). These analyses apply to our policy evaluation routines, extending them to the Markovian setting. For simplicity, we show our techniques with i.i.d. assumption and then illustrate how the extension with Markovian data follows with the uniform mixing assumption in Appendix D.
Error propagation for approximate dynamic programming. Perolat et al. (2015) proposed error propagation analysis for approximate version of generalized policy iteration for zero-sum Markov games (see Appendix C). The authors showed that the following two-stage algorithm converges:
• Stage 1: Given a fixed value function Vk−1, find the policy pair which is an ϵ-equilibrium.
min xs∈∆ max ys∈∆ ∑ a,b x(a|s)y(a|s)Qk−1(s, a, b) =: xsQsk−1ys, (2)
Algorithm 1 Reflected NAC with a game etiquette and ζ-greedy exploration
Require: PKL defined in (1) in Sec. 2. Exploration parameter ζ ≥ 0 (with equality if Assumption 2 holds). Subroutines Policy-Eval-V , Policy-Eval-θ, Policy-Eval-ν (see Alg. 2, 3, 4 and note βνn, β θ n, β ω n are potential step sizes for this routine). Initial policies
x0, y0, ȳ0. xk, yk denote outer, xt, yt denote inner loop’s iterate. 1: for k = 0, 1, . . . do 2: Stage 1 // Approximately solve a matrix game 3: for t = 0, 1, . . . , T − 1 do 4: [V̂ xk−1, V̂ y k−1] = [Policy-Eval-V (x k−1, yk−1, N, βωn ), Policy-Eval-V (x k−1, yk−1, N, βωn )]
// Both players compute their own estimations of Vk−1, denoted as V̂ x and V̂ y
5: [θ̂xt+1, θ̂ y t+1] = [Policy-Eval-θ(xt, yt, N, V̂ x k−1, β θ n),Policy-Eval-θ(xt, yt, N, V̂ y k−1, β θ n)] 6: xt+1(·|s) = PKL ( xt(·|s), η ( 2θ̂xt+1(s, ·)− θ̂xt (s, ·) )) 7: yt+1(·|s) = PKL ( yt(·|s),−η ( 2θ̂yt+1(s, ·)− θ̂ y t (s, ·)
)) 8: Output xk = 1T ∑T t=1 xt.
9: Stage 2 // Approximately find best response 10: for t = 0, 1, . . . , T − 1 do 11: ν̂t+1 = Policy-Eval-ν(xk, ȳt, N, β = βνn) 12: ȳt+1(·|s) = PKL(ȳt(·|s),−ην̂t+1(s, ·)) 13: Output yk = ȳt̂, where t̂ ∈ [T ] is selected uniformly at random.
Algorithm 2 VN = Policy-Eval-V (x, y, N, β) Require: Policy pair x, y, iteration counter N , step size β, initial value function estimate V0.
x̂(·|s) = (1− ζ)x(·|s) + ζ|A| , ŷ(·|s) = (1− ζ)y(·|s) + ζ |B| . 1: for n = 0, 1, . . . , N − 1 do 2: Sample sn ∼ ρx̂,ŷ(·), an ∼ x̂(·|sn), bn ∼ ŷ(·|sn), sn+1 ∼ P (·|sn, an, bn). 3: Vn+1 = Vn − βne(sn) ( Vn(sn)− r(sn, an, bn)− γVn(sn+1)
) where Qk−1(s, a, b) = r(s, a, b) + γ ∑ s′ P (s
′|s, a, b)Vk−1(s′). When it is clear from the context, we drop the subscript of Qk−1. This is a matrix game and is the sample-complexity bottleneck (Perolat et al., 2015). Let ϵg denote the accuracy and xk the output of this stage at iteration k:
E[Es∼U [max ys∈∆ (xk)sQsk−1y s − min xs∈∆ max ys∈∆ xsQsk−1y s]] = ϵk1 , (3)
where the outer expectation is over the randomness of the algorithm used to generate xk.
• Stage 2: This step finds an approximate best response. The fixed policy (xk), can be viewed as a part of the environment. Denote yk as the approximate best-response computed in this stage, at iteration k. The resulting value function Vk = V x
k,yk is fed to stage 1 in the next iteration. Let ϵe be the accuracy for this stage, yk the output of this stage:
E[Es∼U [max y
V x k,y(s)− V x k,yk(s)]] = ϵk2 , (4)
where the outer expectation is over the randomness of the algorithm used to generate yk. Then, Perolat et al. (2015, Theorem 1), Zhao et al. (2021) show that the following holds (see also Appendix C).
E[Es∼U [max y∈∆
V x K ,y(s)− V ⋆(s)]] ≤ |S|K 1− γ Õ ( sup k≤K ϵk1 + sup k≤K ϵk2 ) +O ( |S|γK 1− γ ) . (5)

heading: 3 REFLECTED NAC ALGORITHM WITH A GAME ETIQUETTE
text: Our approach. We introduce NAC-based algorithms (Konda & Tsitsiklis, 2000; Peters & Schaal, 2008) to solve these two stages in an alternating fashion to obtain an approximate Nash equilibrium, in view of (5). We leverage primal-dual algorithms to solve the matrix game in Stage 1
Algorithm 3 θ̂N = Policy-Eval-θ(x, y, N, V̂ , β) for player y
Require: x̂(·|s) = (1− ζ)x(·|s) + ζ|A| , ŷ(·|s) = (1− ζ)y(·|s) + ζ |B| . 1: for n = 0, 1, . . . , N − 1 do 2: Sample sn ∼ ρx̂,ŷ(·), an ∼ x̂(·|sn), bn ∼ ŷ(·|sn), sn+1 ∼ P (·|sn, an, bn). 3: θ̂n+1 = θ̂n − βne(sn, bn) ( θ̂n(sn, bn)− r(sn, an, bn)− γV̂ (sn+1)
) Algorithm 4 ν̂N = Policy-Eval-ν(x, y, N, β) for player y
Require: x̂(·|s) = (1− ζ)x(·|s) + ζ|A| , ŷ(·|s) = (1− ζ)y(·|s) + ζ |B| . 1: for n = 0, 1, . . . , N − 1 do 2: Sample sn∼ρx̂,ŷ(·), an∼ x̂(·|sn), bn∼ ŷ(·|sn), sn+1∼P (·|sn, an, bn), bn+1∼y(·|sn+1). 3: ν̂n+1 = ν̂n − βne(sn, bn) ( ν̂n(sn, bn)− r(sn, an, bn)− γν̂n(sn+1, bn+1)
) efficiently (Malitsky & Tam, 2020; Nemirovski et al., 2009) and NPG for the single agent problem in Stage 2. For estimating value functions that are used as oracles in these algorithms, we employ TD(0) (Tsitsiklis & Van Roy, 1997; Bhandari et al., 2018; Sutton, 1988). To our knowledge, the best complexities in the single agent setting are obtained with this approach (Lan, 2021).
Stage 1. In this step, at iteration k, we compute an approximate equilibrium of the matrix game (2). As Vk−1 is fixed, this is a standard matrix game and throughout this loop, we omit the dependence of Q on k and leave it implicit. Our discussion here is for x player and it would be symmetric for the y player. Due to its simplicity and generality, we use forward-reflected-backward (FoRB) algorithm (Malitsky & Tam, 2020).2 FoRB takes a reflected step rather than using Eb∼ytQ(s, ·, b) directly, which is the case in gradient descent-ascent (GDA). The FoRB update is
xt+1(·|s) = PKL(xt(·|s), η ( 2Eb∼ytQ(s, ·, b)− Eb∼yt−1Q(s, ·, b) ) ).
In standard matrix game notation, we can view θx⋆,t = Eb∼ytQ(s, ·, b) as the matrix-vector multiplication between the dual vector yt and game matrix Q. To get this oracle, we have to solve a linear equation by sampling the policies xt, yt. The linear equation is obtained by using the definition of Q, given after (2). However, the difficulty is that we do not have access to Vk−1. Given that Vk−1 is the value function of policies xk−1, yk−1, in Step 4, we use TD(0) to learn this value function and obtain a biased estimation V̂k−1 (see Algorithm 2). Using this estimation, we can then proceed to solve the linear equation by sampling the policies xt, yt to find an estimate for θx⋆,t = Eb∼ytQ(s, ·, b), in Step 5 (see Algorithm 3). This step is similar to stochastic approximation/SGD approaches (Nemirovski et al., 2009; Lan, 2021). Using the oracle, we perform one FoRB step for each player, in Steps 6 and 7.
As we detail in App. F, for Steps 4, 5 and corresponding policy evaluation routine Alg. 3, x agent only accesses st, r(st, at, bt), st+1 and its own action at to form the stochastic oracle and y accesses st, r(st, at, bt), st+1 and its own action bt. We have additional bias coming from the approximation of Vk−1 by V̂k−1, the estimation of which is important for getting our complexity results. We take special care for the stochastic dependency to make sure to decompose bias and variance of V̂k−1 estimate (See Insight 1). Markovian data would bring additional bias as mentioned before.
Remark 3.1. For the best complexity, we use fresh estimates of V̂k−1 at every iteration (see Algorithm 1 and Insight 4). This gives a tight bound for the bias to get the Õ(ϵ−2) complexity. This insight is in contrast to the black box view of Perolat et al. (2015), which uses an estimate of Vk−1 from the stage 2 within the stage 1. Our analysis behooves both agents to remember the output policies of stage 2 instead, so that they can recompute Vk−1 with a lower bias in the stage 1.
Stage 2. In this step, at iteration k, x player fixes its policy and y computes an approximate best response by solving the single agent problem in (4) by using NPG in (Lan, 2021; Agarwal et al., 2020). Value function Vk−1 that was used in stage 1 is precisely the value function of the policies outputted at this stage in iteration k − 1. For NPG update, y player needs Ea∼xk(·|s)Qx k,ȳt(·, a, ·).
2In principle, this part can be replaced with mirror-prox (Nemirovski, 2004) or OGDA.
This is the joint Q function after taking the expectation over the actions of player x. Since x player’s policy is fixed, we only use policy xk in this loop, whereas y player continue to update its policy ȳt.
We can write Bellman equation for learning this oracle and then use TD(0) as in Bhandari et al. (2018) (see Algorithm 4), which is similar to learning a Q-function. In particular, as long as st, at, bt, st+1 are sampled using the interaction procedure described earlier, there is no need for ȳt update to see the actions or policy of xk. A similar formulation for policy evaluation in MARL is considered in Perolat et al. (2018) in a slightly different setting.
Greedy exploration. If Assumption 2 does not hold, one way to lower bound the policies is to use ζ-greedy exploration which we incorporate into our algorithm. The idea of the analysis will be to pick the exploration parameters depending on the final accuracy. Since the bounds have inverse dependence with this parameter, using greedy exploration will result in a worse complexity compared to what we get when Assumption 1 holds. In the former case, we can take ζ = 0.

heading: 3.1 MAIN RESULT
text: Theorem 3.2. (Overall performance bound with Assumption 1, 2) For Alg. 1 with ζ = 0,
E[Es0∼U [max y
V xk,y(s0)− V ⋆(s0)]] ≤ O (
K|S| T (1− γ)3 ) +O ( K|S|2(|A| ∨ |B|)
N(1− γ)5(ρ(1− γ))2
( 1
(ρmin{x, y})2 ∨ 1 (ρy(1− γ))2
)) +O ( γK ) .
In particular, the overall complexity is Õ(|S|3(|A| ∨ |B|)ϵ−2(1− γ)−12ρ−6y−2(min{x, y})−2).
In this bound, the first term is for solving the outer loops in stages 1 and 2. The second term is due to the bias and the variance of the stochastic oracles that we got by sampling the policies. The final term is due to approximating generalized policy iteration in the outermost loop (Perolat et al., 2015). Theorem 3.3. (Overall performance bound with Assumption 1, see App. G.2.2) Let Assumption 1 hold. Let ζ = (1−γ)
2ϵ |A|∨|B| in Alg. 1.
E[Es0∼U [max y
V xk,y(s0)− V ⋆(s0)]] ≤ O (
K|S| T (1− γ)3
) +O ( K|S|3(|A| ∨ |B|)6
N(1− γ)12ρ2ϵ2
) +O ( γK ) .
Consequently, the sample complexity is Õ(|S|4(|A| ∨ |B|)6(1− γ)−15ϵ−4ρ−2).
As summarized in Table 1, Theorem 3.3 matches the best-known existing complexity from Wei et al. (2021), without using the metric subregularity constant and without restricting to Euclidean projections. For natural policy gradient, this result improves Õ(ϵ−8) in Wei et al. (2021). We refer to Remark G.17 for a more detailed comparison. Moreover, Theorem 3.2 matches the best-known complexity in single agent RL under Assumption 1, 2.

heading: 3.2 CONVERGENCE ANALYSIS
text: Proof sketch. Next, we show how to obtain the required bounds for this final guarantee, in view of eq. (3), (4), (5). Our strategy is to characterize the error of each stage by using the outer/inner structure given in the algorithm. The innermost algorithms (see Alg. 2) are estimating the required oracles depending on value functions, by sampling the policies, and applying either SGD or TD(0).
As per (5), the next lemma will characterize the error of stage 1 (see (3)): solving the matrix game. A critical point to derive the fastest rate as observed by Lan (2021) in the single agent setting is to characterize the bias and variance separately. As the algorithm in Lan (2021) is akin to gradient descent, we extend the ideas there to the more complicated FoRB algorithm.
Insight 1. The existing analyses for stochastic FoRB are not suitable for us. In the stochastic variant in Malitsky & Tam (2020), deterministic oracle is computed at each iteration. Böhm et al. (2020) uses unbiased oracles with bounded variance and decreasing step size. In our case, we
have biased oracles and we use inner loops to decrease bias and variance. Next, we develop an analysis with constant step size and characterization of the bias and variance explicitly.
Lemma 3.4. (Bound for stage 1) Let Assumption 1, 2 hold. Denote xout = 1T ∑T
t=1 xt and yout = 1 T ∑T t=1 yt and let η = 1−γ 8 . Then, it holds that
E [ Es∼U [ max xs,ys xsoutQ sys − xsQsyout ]] = Õ ( 1 ηT ) +O ( 1 T T∑ t=1 E∥E[θt+1|xt]− θ⋆,t∥ )
+O
( η
T T∑ t=1
E∥θt+1 − θ⋆,t∥2 + E∥θt − θ⋆,t−1∥2 ) + 1
Tη E[Es∼U max z=(x,y) T∑ t=1 [E1,t(z)+E2,t(z)]].
Remark 3.5. When bias and variance are 0, this reduced to 1/T rate as in Zhao et al. (2021). Bounding ϵk1 (see (3)) is via bounding LHS of Lem. 3.4. This allows to bound the suboptimality thanks to (5). To this end, we bound the second term in RHS of Lem. 3.4 in Lem. 3.7 and the third term in Lem. 3.6.
We drop the superscripts from θ, V̂k−1 (see Alg. 1) as estimations are symmetric. For a free variable z = (x, y), define E1,t(z)+E2,t(z) = η⟨θt+1(·|s)−E[θt+1(·|s)|xt], x(·|s)−xt(·|s)⟩−η⟨θyt+1(·|s)− E[θyt+1(·|s)|yt], y(·|s)− yt(·|s)⟩. Insight 2. The last error term in the lemma involving E1,t, E2,t is due to the coupling between the free variables xs, ys and randomness of the algorithm. For this error, we adapt the “ghost iterate” trick from Nemirovski et al. (2009) for stochastic primal-dual algorithms (see Lemma F.6).
This lemma analyzes the behavior of FoRB for solving the matrix game with biased oracles. The bound therefore reflects the bias and variance of these oracles. For simplicity, we suppress some dependencies in the following bounds, however we include them in Thm. 3.2 and in the appendices.
Next is the the variance estimation, which is similar to Lan (2021), except handling the error term coming from V̂k−1 as in Insight 3. Apart from that subtlety, this part is similar to SGD-type analysis with a biased oracle, where we measure the squared distance of the iterate to the solution. Lemma 3.6. (Variance estimation for step 5) Let Assumption 1, 2 hold. Let βθn = 2ρmin{y,x}(n+n0) for n0 ≥ 1. Then, for Algorithms 1 and 3,
E∥θN − θ⋆,t∥22 ≤ O ( 1 N2 + 1 (ρmin{y, x})2 ( 1 N + E∥V̂k−1 − Vk−1∥2∞ )) .
Insight 3. Different from the standard critic analyses (Hong et al., 2020; Khodadadian et al., 2021b), we account for the additional bias coming from having V̂k−1 instead of real Vk−1 (see (2), Step 4). We exploit structure of the underlying problem to make sure the error term appears as E∥V̂k−1 −Vk−1∥2∞ in the bound instead of E∥V̂k−1 −Vk−1∥∞, which would deteriorate the rate.
The next estimation is critical for obtaining the complexity result. In particular, we bound the bias of θt+1. Since in Lemma 3.4, we need a tight bound for ∥E[θt+1|xt] − θ⋆,t∥ = ∥E[θN |xt] − θ⋆,t∥, we have to be careful with the additional bias from V̂k−1. This part is similar to SGD-type analysis with a biased oracle, where we measure the distance of the expectation of the iterate to the solution. Lemma 3.7. (Bias estimation for step 5)) Let Assumption 1, 2 hold, βθn = 2ρmin{x,y}(n+n0) , n0 =
O (
1 (ρmin{x,y})2
) . For Algorithms 1 and 3
∥E[θN |xt]− θ⋆,t∥2 ≤ O ( 1
N2 +
1
(ρmin{x, y})2 ∥E[V̂k−1|xt]− Vk−1∥2∞
) . (6)
Insight 4. The reason to use fresh estimates for V̂k−1 at each t as in Algorithm 1 is the result of this lemma (see Remark 3.1). Since the bias term in the algorithm’s analysis is ∥E[θN |xt]− θ⋆,t∥ in Lemma 3.4, we take the square root of the result of Lemma 3.7. If V̂k−1 is estimated before xt, then we will have E∥V̂k−1 − Vk−1∥ in the bound of Lemma 3.4, which will have the rate
O(1/ √ N). On the other hand, if we estimate V̂k−1 freshly as in Algorithm 1, then we will be able to use the improved bias bound ∥E[V̂k−1|xt]− Vk−1∥ ≤ O(1/N) as in the next lemma.
The next lemma is for the estimation of the value function Vk−1 using the policies xk−1, yk−1 with TD(0). Therefore, this is an analysis for TD(0), similar to Lan (2021).
Lemma 3.8. (Variance/Bias estimation for step 4)) Let Assumption 1, 2 hold and βωn = 2 ρ(1−γ)(n+n0) , with n0 = O ( 1 (ρ(1−γ))2 ) . The variance and bias of V̂k−1, computed as in Algorithm 1 satisfies
∥E[V̂k−1|xt, yt]− Vk−1∥22 ≤ O ( N−2 ) , E∥V̂k−1 − Vk−1∥22 ≤ O ( N−1(ρ(1− γ))−2 ) .
Unlike stage 1, the stage 2 (finding the best response) mirrors the single agent analysis closely. Due to space constraints, we defer the details to App. F. Combining Lemma 3.4 with the result of stage 2 (which is of the same order) in (5) gives Theorem 3.2. The main idea of Thm. 3.3 is to use ζ-greedy exploration to replace the policy values x, y (see Theorem 3.2, Lemmas 3.6, 3.7, 3.8), which might be 0 without Assumption 2 (see App.G.2.2).

heading: 4 NUMERICAL VERIFICATION
text: We validate our algorithm in tabular domains comparing against OGDA (Wei et al., 2021) and REINFORCE (Daskalakis et al., 2020). More results , implementation details and environment description are given in Appendix H. We emphasize that our main contribution is theoretical; the preliminary computational results are for verification purposes.
Observations. Both the domains challenge theoretical assumptions. Therefore, our best complexity result Õ(ϵ−2) from Theorem 3.2 does not apply in this setting. Similarly, the assumptions in Table 1 do not hold. The assumption of (Wei et al., 2021) and our Assumption 1 do not hold because in Alesia the players can only lose coins. Therefore the initial state cannot be reached in finite time from any state. Finally the assumption of Daskalakis et al. (2020) does not hold since in Alesia the game ends only when either one player wins or both players finish their coin budget. The game ends with probability 0 in all other cases. Thus, it follows that we cannot lower bound the termination probability at any state. Nevertheless, we observe that all the algorithms converge. Figures 1a,1b shows the value of the bandit player policies evaluated at the NE actions (a∗, b∗), i.e. x(a∗) and y(b∗). Reflected NAC converges faster than OGDA (Wei et al., 2021) and REINFORCE (Daskalakis et al., 2020). Similar conclusions arise from Figures 1c, 1d where we plot the suboptimality gap in Alesia.

heading: CONTENTS

heading: 1 Introduction 1
text: 1.1 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

heading: 2 Preliminaries 3

heading: 3 Reflected NAC algorithm with a game etiquette 5
text: 3.1 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Convergence analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

heading: 4 Numerical verification 9

heading: A Background on NPG and NAC 16

heading: B Basic results on RL and optimization 17

heading: C Error propagation framework 19

heading: D Markovian bias 20

heading: E Single loop NAC with etiquette 22
text: E.1 Proofs for stage 1 of single loop NAC with etiquette in . . . . . . . . . . . . . . . 22
E.1.1 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
E.1.2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
E.2 Proofs for stage 2 of single loop NAC with etiquette . . . . . . . . . . . . . . . . . 27
E.2.1 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
E.2.2 Theoretical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

heading: F Proofs for Reflected NAC with a game etiquette 31
text: F.1 Proofs for stage 1 of Reflected NAC with a game etiquette . . . . . . . . . . . . . 31
F.1.1 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
F.1.2 Theoretical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
F.2 Proofs for stage 2 of Reflected NAC with a game etiquette . . . . . . . . . . . . . 39

heading: G Greedy exploration to remove Assumption 2 42
text: G.1 Single loop NAC with a game etiquette and ζ-greedy exploration . . . . . . . . . . 42
G.1.1 Stage 1 of single loop NAC with a game etiquette and ζ-greedy exploration (See Algorithm 8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
G.1.2 Stage 2 of single loop NAC with a game etiquette and ζ-greedy exploration (See Algorithm 8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
G.2 Reflected NAC with a game etiquette and ζ-greedy exploration . . . . . . . . . . . 52
G.2.1 Single agent result with ζ-greedy exploration . . . . . . . . . . . . . . . . 52
G.2.2 Reflected NAC with a game etiquette and ζ-greedy exploration in Algorithm 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

heading: H Additional Experiments 59
text: H.1 Environments description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
H.2 Hyperparameters selection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

heading: A BACKGROUND ON NPG AND NAC
text: Natural policy gradient and natural actor-critic. As we work in the tabular setting, in this paper, we focused on the natural policy gradient (Kakade, 2001) in softmax parameterization which admits a simple update rule. In particular, the update rule for NPG in single agent setting is (Agarwal et al., 2020, Lemma 5.1) πt+1(·|s) ∝ πt(·|s) exp(ηQπt(s, ·)), which is the closed form solution of the update in (1). To get a sample-based version of this algorithm, one needs to learn Qπt typically in an inner policy evaluation loop as in Lan (2021). This is also called natural actor-critic (NAC) since the actor updates the policy πt+1 and critic learns the value function Qπt .
Note that the update rule in (Agarwal et al., 2020, Lemma 5.1) is written with the advantage function, however, due to softmax parameterization, it is equivalent to the form we give.
We can also generalize (1), by using Bregman distances instead of the KL divergence
xt+1(·|s) = P(xt(·|s), Qxt(s, ·)) = arg min x(·|s)∈∆ ⟨Qxt(s, ·), x(·|s)⟩+D(x(·|s), xt(·|s)), (7)
Finally, for the formal setup of Bregman distances, we refer to Tseng (2008); Nemirovski et al. (2009). Throughout the paper, we focus on the case when D is KL divergence, so that the update rule corresponds to NPG rule. This choice corresponds to the distance generating function of D being strongly convex in ℓ1 norm which gives the standard inequality
D(x, y) ≥ 1 2 ∥x− y∥21, (8)
that is used frequently throughout the proofs.
Single loop NAC. Unlike the previous case, single loop NAC (Hong et al., 2020; Khodadadian et al., 2021b) does not have an inner loop for computing Qπt at iteration t. In contrast, single loop NAC keeps a running estimate for this oracle (which corresponds to one iteration of policy evaluation) and due to its two time-scale nature, still converges. In the tabular case, the simplest single loop NAC update takes the form
θt+1 = θt − βte(st, at) (θt(st, at)− r(st, at)− γθt(st+1, at+1)) (9) πt+1(·|s) ∝ πt(·|s) exp(ηtθt+1(s, ·)),
with properly selected βt, ηt, generally with ηt/βt → 0.
Temporal difference learning. For constructing state or action value functions from samples, we will use temporal difference learning and in particular TD(0) (Sutton, 1988; Bhandari et al., 2018; Tsitsiklis & Van Roy, 1997). This algorithm can be seen as a stochastic approximation scheme for solving a linear equation (Tsitsiklis & Van Roy, 1997; Lan, 2021). In particular, by denoting the stationary state distribution under π as ρπ , we define
Fπ(θ)(s, a) = ρπ(s)π(a|s) ( θ(s, a)− r(s, a)− γ ∑ s′,a′ P (s′|s, a)π(a′|s′)θ(s′, a′) ) .
First, we note that Fπ(θ⋆) = 0 where θ⋆ = Qπ . Under Assumption 1, 2 Fπ is strongly monotone (see (Bhandari et al., 2018, Lemma 3), (Lan, 2021, Section 5.2). The main tools to show this are Assumption 1, 2 and Bellman operator being γ-contraction. Then, one can use for example (Bauschke et al., 2011, Example 22.6, Example 20.7).
One can sample st ∼ ρπ , at ∼ π(·|st) and st+1 ∼ P (·|st, at), at+1 ∼ π(·|st+1) and one step of TD(0) corresponds to (9). Note that under i.i.d. assumption, the update in (9) is an unbiased estimate of the update that we would get by using the true operator Fπ . The results for TD(0) can be extended to Markovian setting without the i.i.d. assumption by using a uniform mixing assumption (Bhandari et al., 2018) (see also Appendix D).

heading: B BASIC RESULTS ON RL AND OPTIMIZATION
text: Some notation. We say that an operator θ 7→ F (θ) is λmin-strongly monotone if ⟨F (θ1) − F (θ2), θ1 − θ2⟩ ≥ λmin∥θ1 − θ2∥22 and λmax-Lipschitz if ∥F (θ1) − F (θ2)∥2 ≤ λmax∥θ1 − θ2∥2. These conditions can be defined with other norms, but we stick to ℓ2-norm for simplicity.
Lemma B.1. Define θt recursively as θt+1 = θt−βtF̃ (θt, ξt) where r(s, a, b) ≤ 1 and F̃ (θt, ξt) = e(s′, a′)(θt(s ′, a′)− r(s, a, b)− γθt(s′′, a′′)) and recall the definition of Qk(s, a, b) = r(s, a, b) + γ ∑
s′ P (s ′|s, a, b)Vk(s′). Then, it follows for any t, k
∥θt∥∞ ≤ 1
1− γ , ∥θt∥2 ≤ √ |S||A| 1− γ ,
∥V̂k−1∥∞ ≤ 1
1− γ ,
∥F̃ (θt, ξt)∥2 ≤ 3
1− γ ,
∥Qk(s, a, b)∥∞ ≤ 2
1− γ .
Proof. The first inequality is proven by induction, for example see (Khodadadian et al., 2021b, Lemma C.10). Following inequalities are either basic consequences of the first inequality or directly follow from definition.
A classical result that we use frequently in the proofs is performance difference lemma by Kakade & Langford (2002). The statement of the lemma is slightly different due to multi agent setting, but since one policy is held fixed while changing the other one, the original proof of the lemma extends straightforwardly. The proof for this case is given in Daskalakis et al. (2020). Lemma B.2 (Performance difference lemma. See Kakade & Langford (2002); Daskalakis et al. (2020)). For any policies x, y1, y2 and any state s0
V x,y1(s0)− V x,y2(s0) = 1
1− γ Es∼dx,y1s0 ⟨Ea∼x(·|s)Q x,y2(s, a, ·), y1(·|s)− y2(·|s)⟩
A standard result that we use is Lipschitzness of y 7→ V x,y(s0). For example, see (Hong et al., 2020, Lemma 7). We provide proofs as we use the precise constants and use them slightly differently than Hong et al. (2020). Lemma B.3. For any policies x, y1, y2,
∥V x,y1 − V x,y2∥∞ ≤ 2
(1− γ)2 max s ∥y1(·|s)− y2(·|s)∥1.
Proof. By the performance difference lemma Kakade & Langford (2002) and Cauchy-Schwarz inequality, for any s0,
V x,y1(s0)− V x,y2(s0) = 1
1− γ Es∼dx,y1s0 ⟨Ea∼x(·|s)Q x,y2(s, a, ·), y1(·|s)− y2(·|s)⟩
≤ 1 1− γ Es∼dx,y1s0 ∥Ea∼x(·|s)Q x,y2(s, a, ·)∥∞∥y1(·|s)− y2(·|s)∥1.
Next, we are going to further upper bound the right hand side using Lemma B.1
V x,y1(s0)− V x,y2(s0) ≤ 1
1− γ max s ∥Ea∼x(·|s)Qx,y2(s, a, ·)∥∞∥y1(·|s)− y2(·|s)∥1
≤ 2 (1− γ)2 max s ∥y1(·|s)− y2(·|s)∥1.
We take maximum over s0 to conclude.
Lemma B.4. We have
∥Qx,y1 −Qx,y2∥∞ ≤ 2γ
(1− γ)2 max s ∥y1(·|s)− y2(·|s)∥1.
Proof. We note that by the definition of Qx,y1 it follows that for all s, a, b
|Qx,y1(s, a, b)−Qx,y2(s, a, b)| = γ ∣∣∣∣∣∑ s′ P (s′|s, a, b) (V x,y1(s′)− V x,y2(s′)) ∣∣∣∣∣ . Jensen’s inequality, and the previous lemma gives the result.
Lemma B.5. Let zt be defined as for all s,
zt+1(·|s) = P (zt(·|s), ηtθt+1(s, ·)),
where P is defined in (1). In particular,
P(zt(·|s), θt+1(s, ·)) = arg min z(·|s)∈∆ ⟨ηtθt+1(s, ·), z(·|s)⟩+D(z(·|s), zt(·|s)).

heading: Then, it holds that for all s,
text: ∥zt+1(·|s)− zt(·|s)∥1 ≤ ηt∥θt+1∥∞.
Proof. By the update rule of zt, it holds for all z that (for example, see (Tseng, 2008, Property 1))
⟨∇D(zt+1(·|s), zt(·|s)) + ηtθt+1(s, ·), z(·|s)− zt+1(·|s)⟩ ≥ 0.
By plugging in z = zt and using three point identity gives
D(zt+1(·|s), zt(·|s)) +D(zt(·|s), zt+1(·|s)) ≤ ηt⟨θt+1(s, ·), zt(·|s)− zt+1(·|s)⟩.
By (8) and Cauchy-Schwarz inequality gives
∥zt+1(·|s)− zt(·|s)∥1 ≤ ηt∥θt+1(s, ·)∥∞.
The result follows by ∥θt+1(s, ·)∥∞ ≤ ∥θt+1∥∞.
Lemma B.6. We have that maxy V xk,y −V x⋆,y⋆ = 0 iff xk is in the set of Nash equilibrium points.
Proof. Recall that we say that (x⋆, y⋆) is a Nash equilibrium if for any x, y
x⋆Q x⋆,yy ≤ x⋆Qx⋆,y⋆y⋆ ≤ xQx,y⋆y⋆.
In particular, it is true when we plug in x = xk, y = yk.
Next, by definition of min operation, one can bound minx xQx,ykyk and by the definition of max operation, xkQxk,y⋆y⋆ ≤ maxy xkQxk,yy. In sum, we have
min x xQx,ykyk ≤ x⋆Qx⋆,ykyk ≤ x⋆Qx⋆,y⋆y⋆ ≤ xkQxk,y⋆y⋆ ≤ max y xkQ xk,yy (10)
Of course, by definition, for any x, y, V x,y = xQx,yy.
This is easy to see: let xk = x⋆ for any x⋆ which is a Nash equilibrium, then maxy V x⋆,y = V x⋆,y⋆ . Now assume that maxy V xk,y = V x⋆,y⋆ , then by (10) it must be that maxy V xk,y = V xk,y⋆ = V x⋆,y⋆ . Hence xk = x⋆.

heading: C ERROR PROPAGATION FRAMEWORK
text: Error propagation of generalized policy iteration for Markov games is given in Perolat et al. (2015).
Notation. We define the Bellman operators following Perolat et al. (2015) Tx,yV (s) = ∑ a,b x(a|s)y(b|s)r(s, a, b) + γ ∑ s′,a,b x(a|s)y(b|s)P (s′|s, a, b)V (s′)
TxV (s) = max y Tx,yV (s)
TV (s) = min x max y Tx,yV (s).
It is easy to derive that these operators are contractions in ℓ∞ norm with constant γ. See also Perolat et al. (2015); Zhao et al. (2021).
We find the one-sided Nash equilibrium as Daskalakis et al. (2020) and Zhao et al. (2021).
max y
V x,y(s)− V ⋆(s) ≤ ϵ.
This is in contrast to Wei et al. (2021) that shows the rate in the duality gap. Two phases are characterized in Perolat et al. (2015) as
• Phase 1: TxkVk−1 ≈ TVk−1. By using the definitions of T, Tx this corresponds to max
y Txk,yVk−1 −minx maxy Tx,yVk−1, (11)
where Tx,yVk−1(s) = ∑ a,b x(a|s)y(b|s)r(s, a, b) + γ ∑ s′,a,b x(a|s)y(b|s)P (s′|s, a, b)Vk−1(s′).
As Vk−1 is fixed, this will give a standard matrix game for all s. By using a stochastic algorithm, we are going to make the output xk to be an approximate solution in expectation, therefore we write
Emax y xskQ s k−1y s −min x max y xsQsk−1y s = ϵk1(s), (12)
where the expectation is over the randomness of the specific algorithm used to generate xk.
In our analysis, we bound the stronger quantity, which is called duality gap E [ max
y xskQ s k−1y s −min x xsQsk−1y s k
] ≥ ϵk1(s),
by the definition of a Nash equilibrium since minx xsQsk−1y s k ≤ minx maxy xsQsk−1ys.
• Phase 2: Vk ≈ (Txk)mVk−1. Since Txk is a contraction Perolat et al. (2015); Zhao et al. (2021), as m → ∞, for any V , TxkV → maxy V xk,y . Let us denote the best response as y∗k and the approximate best response as yk. We want to bound
V xk,y ∗ k(s)− EV xk,yk(s) = ϵk2(s), (13)
where the expectation is over the randomness of the algorithm used to generate yk.
Then (Perolat et al., 2015, Theorem 1) states that (where maxy xskQ s k−1y s − minx maxy x sQsk−1y s = ϵ′k(s), V
xk,y ∗ k(s)− V xk,yk(s) = ϵk(s))∑
s
µ(s) ( max
y V xk,y(s)− V ⋆(s)
) ≤ 2(γ − γ k)
(1− γ)2 C1,k,0∞ sup j∈[0,k−1] ∥ϵj∥21,σ
+ (1− γk)C0,k,0∞
(1− γ)2 sup j∈[1,k] ∥ϵ′j∥1,σ +
2γk
1− γ Ck,k+1,0∞ min(∥d0∥1,σ, ∥b0∥1,σ),
where
Cl,k,dq = (1− γ)2 γl − γk k−1∑ i=l ∞∑ j=i γjcq(j + d)
with
cq(j) = sup x1,y1,...,xj ,yj ∥∥∥∥d(µPx1,y1 . . . Pxj ,yj )dσ ∥∥∥∥ q,σ
For given state distributions µ, σ, let us define the concentrability coefficient Perolat et al. (2015):
sup j sup x1,y1,...,xj ,yj ∥∥∥∥µPx1,y1 . . . Pxj ,yjσ ∥∥∥∥ ∞ =: Cµ,σ < +∞.
In particular, by upper bounding cq(j) ≤ Cµ,σ for simplicity (one can also use the tighter bounds; we use the loose upper bounds for simplicity as they only affect the final bound slightly), the bound becomes∑
s
µ(s) ( max
y V xk,y(s)− V ⋆(s)
) ≤ 2kCµ,σ
1− γ sup j∈[0,k−1] ∥ϵj∥21,σ
+ kCµ,σ (1− γ) sup j∈[1,k] ∥ϵ′j∥1,σ + 2γkCµ,σ 1− γ ,
where we also used an estimation from (Zhao et al., 2021, Lemma 2).
One important point here is that we will be making sure the inequalities in these stages hold in expectation. This is also pointed out in Zhao et al. (2021) with a short explanation. We describe here the details needed to ensure that these bounds hold in expectation. For this, we have to track the analysis in Perolat et al. (2015) and in Scherrer et al. (2012) where the derivations in Perolat et al. (2015) build on. In particular, the relations in (Perolat et al., 2015, Lemma 1) are linear and therefore, would also hold in expectation. Then, in derivation of (Perolat et al., 2015, Theorem 1), the arguments in (Scherrer et al., 2012, Lemma 2, Lemma 3) are used. Tracking (Scherrer et al., 2012, Lemma 3), we see that after taking the total expectation, the bounds become∑
s
µ(s) ( Emax
y V xk,y(s)− V ⋆(s)
) ≤ 2kCµ,σ
1− γ sup j∈[0,k−1] ∥ϵj1∥21,σ
+ kCµ,σ (1− γ) sup j∈[1,k] ∥ϵj2∥1,σ + 2γkCµ,σ 1− γ , (14)
where ϵg,j and ϵe,j are as defined in (12), (13). Remark C.1. For simplicity, throughout the paper we take σ, µ to be the uniform distribution and hence replaced Cµ,σ by its worst case value |S|. As mentioned in Munos (2003), this value can be much smaller in general.

heading: D MARKOVIAN BIAS
text: As mentioned before, in this setting, the Markovian error is essentially additive in our arguments for policy evaluation steps, and can be bounded by using uniform mixing assumption. In particular, this assumption holds when the induced Markov Chain over the states, for any policy pair is aperiodic and irreducible (Lan, 2021; Khodadadian et al., 2021b). In this chapter, we give an informal explanation to illustrate how Markovian sampling can be incorporated into our proofs with the uniform mixing assumption. The main references for this kind of analysis is Lan (2021); Bhandari et al. (2018) for Algorithm 1 and Khodadadian et al. (2021b); Zou et al. (2019) for single loop NAC.
We are going to sketch the arguments for Appendix F.1 which will be applicable also to other policy evaluation routines.
Recall that by using the oracle for stage 1, we can write
F (θn)(s, a) = ρ xt,yt(s)xt(a|s) ( θn(s, a)− ∑ b yt(b|s)r(s, a, b)
− γ ∑ s′,b yt(b|s)P (s′|s, a, b)Vk−1(s′) ) , (15)
and F̃ (θn, ξn) = e(sn, an) ( θn(sn, an)− r(sn, an, bn)− γV̂k−1(sn+1) ) .
This time we have a Markovian data stream and we denote ξn = (sn, an, bn, sn+1). Unlike the i.i.d. case Eξn F̃ (θn, ξn) ̸= F (θn). Now we inspect the place in the proof of Lemma 3.6 where we used this estimation. Recall that the term we have
−⟨F̃ (θn, ξn), θn − θ⋆⟩,
where we take conditional expectation in Lemma 3.6. As we can no longer compute the expectation, we are going to identify the error term
−⟨F̃ (θn, ξn), θn − θ⋆⟩ = −⟨F (θn), θn − θ⋆⟩−⟨F̃ (θn, ξn)− F (θn), θn − θ⋆⟩︸ ︷︷ ︸ err(n) .
We now separate the error of V̂k−1 and identify the Markovian error, since we separately handled the error due to V̂k−1 in Lemma 3.6. Let us define F̆ (θn, ξn) = e(sn, an) (θn(sn, an)− r(sn, an, bn)− γVk−1(sn+1))
err(n) = −⟨F̆ (θn, ξn)− F (θn), θn − θ⋆⟩︸ ︷︷ ︸ ζ(θn,ξn) −⟨F̃ (θn, ξn)− F̆ (θn, ξn), θn − θ⋆⟩.
We notice that the last term in the above bound is simply −γ⟨e(sn, an)(Vk−1(sn+1) − V̂k−1(sn+1)), θn − θ⋆⟩ which can be bounded as in Lemma 3.6. Therefore we focus on the Markovian error which is defined as ζ(θn, ξn).
We will argue as in Bhandari et al. (2018). First, it is easy to see that as in Bhandari et al. (2018), θn 7→ F̆ (θn, ξn), θn 7→ F (θn) and θ 7→ θn − θ⋆ are all Lipschitz. Therefore, it follows for some constant C1 that |ζ(θn, ξn)− ζ(θn−τ , ξn)| ≤ C1∥θn − θn−τ∥2. By triangle inequality and using the update rule θn+1 = θn − βnF̃ (θn, ξn) along with Lemma B.1 give
ζ(θn, ξn) ≤ ζ(θn−τ , ξn) + 3C1 1− γ n−1∑ i=n−τ βi.
Next, we bound Eζ(θn−τ , ξn) as in Lan (2021). Let Fn−1 be the filtration generated by ξ0, . . . , ξn−1 and note that θn depends on the same randomness as Fn−1 for all n. In particular, by tower property,
Eζ(θn−τ , ξn) = E⟨F (θn−τ )− F̆ (θn−τ , ξn), θn−τ − θ⋆⟩ = E⟨F (θn−τ )− E[F̆ (θn−τ , ξn)|Fn−τ−1], θn−τ − θ⋆⟩ ≤ 2E∥F (θn−τ )− E[F̆ (θn−τ , ξn)|Fn−τ−1]∥ ≤ Cρτ ,
for some C, where the last bound can be derived the same as (Lan, 2021, Lemma 16) under the assumption that the induced Markov chain is aperiodic and irreducible.
Then, one can use the arguments in Bhandari et al. (2018) by picking τ ∼ τmix ∼ log(1/ϵ)log(1/ρ) if n > τmix and τ = n if n ≤ τmix and using the step size rule of βn which decays as 1/n, the same as Bhandari et al. (2018); Lan (2021) which will only add logarithmic spurious terms to the final complexity.
In the case of single loop NAC, the arguments are slightly more involved, however, they are wellstudied. In particular, Zou et al. (2019) introduced the technique to handle Markovian noise for SARSA. These arguments are used for single loop NAC in Khodadadian et al. (2021b); Wu et al. (2020); Xu et al. (2020a), which also applies in our setting for Algorithm 5, similar to how the above arguments apply in our setting for Algorithm 1.
Algorithm 5 Single loop NAC with a game etiquette
Require: V̂0 such that ∥V̂0 − V x0,y0∥2∞ ≤ ϵ for k = 1, 2, . . . do
Stage 1 for t = 0, 1, . . . , T − 1 do
Sample (st, at, bt, st+1), with policy pair xt, yt observe st, bt, r(st, at, bt), st+1 θxt+1 = θ x t − βte(st, at) ( θxt (st, at)− r(st, at, bt)− γV̂k−1(st+1)) ) θyt+1 = θ y t − βte(st, bt) ( θxt (st, bt)− r(st, at, bt)− γV̂k−1(st+1))
) [xt+1(·|s), yt+1(·|s)] = [P(xt(·|s), ηθxt+1(s, ·)), P(yt(·|s),−ηθ y t+1(s, ·))]
Output xk = 1T ∑T
t=1 xt. Stage 2 for t = 0, 1, . . . , T − 1 do
Sample (st, at, bt, st+1, bt+1) with policy pair xk, ȳt, observe st, bt, r(st, at, bt), st+1, bt+1 νt+1 = νt − βνt e(st, bt) (νt(st, bt)− r(st, at, bt)− γνt(st+1, bt+1)) ωt+1 = ωt − βωt e(st) (ωt(st)− r(st, at, bt)− γωt(st+1)) ȳt+1(·|s) = P(ȳt(·|s),−ηθt+1(s, ·)) Output yk = ȳt̂, V̂k = ωt̂+1, where t̂ ∈ [T ] is selected uniformly at random and Vk = V xk,yk .

heading: E SINGLE LOOP NAC WITH ETIQUETTE
text: Theorem E.1. Let Assumption 1, 2 hold and µ be a state distribution. For Algorithm 5, for the output of x-player
EEs0∼µ[max y
V xk,y(s0)]− V ⋆(s0) ≤ kCµ,σ
T 1/4(1− γ) {√ |S|(|A| ∨ |B|) (1− γ)2 + 1
λθmin(1− γ) + |S| √ |A| ∨ |B|
(1− γ)λθmin +
√ |S|(|A| ∨ |B|)
λωminλ θ min(1− γ)
+ |S| √ |A| ∨ |B|
(1− γ)3λθmin
+
√ |S||B| (1− γ)2 +
1
λνmin(1− γ)2 +
√ |S||B|
(1− γ)4
} +O ( γkCµ,σ 1− γ ) which gives Õ ( C4G|S| 4(|A|∨|B|)2
ϵ4(1−γ)20(λθminλωminλνmin)4
) sample complexity.
Proof. Inserting the results of Lemmas E.7, E.11 and E.14 to (14) gives the result.

heading: E.1 PROOFS FOR STAGE 1 OF SINGLE LOOP NAC WITH ETIQUETTE IN
text: In this part, we are going to formulate and present the results for solving stage 1 with single loop NAC. Unlike Zhao et al. (2021), we do not assume to have an unbiased access to Vk−1. Therefore, we have a stochastic oracle involving V̂k−1 which is an estimate of Vk−1. We characterize the error from this term and note that the goal of stage 2 will be to provide this oracle V̂k−1 with small error. Therefore, the results in this part will contain the error term E∥V̂k−1 − Vk−1∥2∞

heading: E.1.1 FORMULATION
text: Notation. The problem is for all s
min x(·|s) max y(·|s) ∑ a,b x(a|s)y(b|s)Qk−1(s, a, b) =: xsQsk−1ys,
where Qk−1(s, a, b) = r(s, a, b) + γ ∑ s′ P (s′|s, a, b)Vk−1(s′),
where we also defined xs, ys, Qs.
Here, Vk−1 is fixed (independent of x, y and iteration counter t), therefore the problem is standard matrix game, with a restricted access to game matrix Qk−1(s, a, b). In particular, Vk−1 ≈ V xk−1,yk−1 . For all s, the equilibrium condition is for all x, y
xs⋆Q s k−1y s ≤ xs⋆Qsk−1ys⋆ ≤ xsQsk−1ys⋆.
For lighter notation, we refer to Qk−1 as Q since it is fixed during the loop.
At iteration t of solving this matrix game, we will need the oracles Eb∼yt(·|s)Q(s, a, b) and Ea∼xt(·|s)Q(s, a, b) for the x player and y player, respectively. This part is symmetric.
Let us write the oracle for x variable by using the definition of Q(s, a, b) = Qk−1(s, a, b):
θx⋆,t(s, a) = Eb∼yt(·|s)Q(s, a, b) (16) = ∑ b yt(b|s)r(s, a, b) + γ ∑ s′,b yt(b|s)P (s′|s, a, b)Vk−1(s′).
Given the sampling matrix diag(xt) ⊗ diag(ρxt,yt) as in (Lan, 2021, Sec. 5.2), where ρxt,yt is the steady state distribution under xt, yt; for the critic, define the operator
F xt (θ)(s, a) = ρ xt,yt(s)xt(a|s)
[ θ(s, a)− ∑ b yt(b|s)r(s, a, b)
− γ ∑ s′,b yt(b|s)P (s′|s, a, b)Vk−1(s′) ] , (17)
which, by Assumption 1, 2 is strongly monotone with λθmin and we would like to find θ⋆,t such that F xt (θ x ⋆,t) = 0. By (16), θ x ⋆,t(s, a) = Eb∼yt(·|s)Q(s, a, b). Since sampling matrix is positive definite due to abovementioned assumptions, the solution of (17) is unique.
As we do not have access to true Vk−1, we have the stochastic operator with the estimate V̂k−1 and by sampling ξt = (st, at, bt, st+1), st ∼ ρxt,yt , at ∼ xt(·|st), bt ∼ yt(·|st), st+1 ∼ P (·|st, at, bt)
F̃t(θt, ξt) = e(st, at) ( θt(st, at)− r(st, at, bt)− γV̂k−1(st+1) ) .
By assuming we can sample from the stationary state distributions ρxt,yt ,
Eξt [ F̃t(θt, ξt) + e(st, at)γ (Vk−1(st+1)− Vk−1(st+1)) ] = Ft(θt) +
∑ s,a,b,s′ ρxt,yt(s)xt(a|s)yt(b|s)P (s′|s, a, b)e(s, a) ( Vk−1(s ′)− V̂k−1(s′) )
=: F (θt) + γPxt,yt(Vk−1 − V̂k−1) = F (θt) + δv,t, (18)
where we defined the matrix Pxt,yt .
Above, the first equality is due to
Eξt [e(st, at) (θt(st, at)− r(st, at, bt)− γVk−1(st+1))] = ∑
s,a,b,s′
Pr(s, a, b, s′)e(s, a) (θt(s, a)− r(s, a, b)− γVk−1(s′))
= ∑
s,a,b,s′
ρxt,yt(s)xt(a|s)yt(b|s)P (s′|s, a, b)e(s, a) (θt(s, a)− r(s, a, b)− γVk−1(s′))
= ∑ s,a ρxt,yt(s)xt(a|s)e(s, a) ( θt(s, a)− ∑ b yt(b|s)r(s, a, b)−γ ∑ s′,b yt(b|s)P (s′|s, a, b)Vk−1(s′) ) ,
where the last line is due to ∑ b,s′ yt(b|s)P (s′|s, a, b)θt(s, a) = θt(s, a) ∑ b,s′ Pr(s ′, b|s, a) =
θt(s, a) and∑ b,s′ yt(b|s)P (s′|s, a, b)r(s, a, b) = ∑ b yt(b|s)r(s, a, b) ∑ s′ P (s ′|s, a, b) = ∑ b yt(b|s)r(s, a, b).

heading: E.1.2 PROOFS
text: We will drop the superscript on θx, θy as the algorithms are symmetric, so we will only analyze one case.
Lemma E.2. Under Assumption 1, 2, let βt = 1λθmint1/2 and ηt = 1 t3/4 . Then for the critic computed in stage 1 of Algorithm 5,
1
T T∑ t=1 E∥θt+1 − θ⋆,t∥22 ≤ 2√ T ∥θ1 − θ⋆,t∥22 +
2(1 + log T )
(λθmin) 2(1− γ)2
√ T
+ 16|S||A|(1 + log T )√
T (1− γ)4 + 4γ2|S||A| (λθmin) 2 E∥V̂k−1 − Vk−1∥2∞.
Corollary E.3. Extracting only the dependence on λmin, |S|, |A|, γ, T gives
1
T T∑ t=1 E∥θt+1 − θ⋆,t∥22 ≤ 1√ T { O ( |S||A| (1− γ)2 ) + Õ ( 1 (λθmin) 2(1− γ)2 ) + Õ ( |S||A| (1− γ)4 )} + E∥V̂k−1 − Vk−1∥2∞O ( γ2|S||A| (λθmin) 2 ) .
Remark E.4. Different from the standard critic analyses, we have to account for the additional bias coming from only having V̂k−1 instead of real Vk−1.
Remark E.5. Important point here is to exploit strong monotonicity of Ft defined in (17), to make the error term E∥V̂k−1−Vk−1∥2∞ appear instead of the worse term E∥V̂k−1−Vk−1∥∞ which would deteriorate the complexity.
Remark E.6. With some extra work, we can obtain a step size βt not depending on λθmin, similar to Khodadadian et al. (2021b). We do not pursue this for brevity and keeping the analysis simple.
Proof. Let us recall θ⋆,t(s, a) = Eb∼yt(·|s)Q(s, a, b) (16) and that Ft(θ⋆,t) = 0 by the definition of Ft in (17). Moreover, θt+1 = θt − βtF̃t(θt, ξt). Analyzing the update rule of critic in the standard way (for example see (Hong et al., 2020, Proof of Thm. 3)), gives
∥θt+1 − θ⋆,t∥22 = ∥θt − θ⋆,t∥22 − 2βt⟨F̃t(θt, ξt), θt − θ⋆,t⟩+ β2t ∥F̃t(θt, ξt)∥22. (19)
We will take expectation w.r.t. to the sample ξt = (st, at, bt, st+1), conditioned on θt, xt, yt, and therefore on θ⋆,t and use st ∼ ρxt,yt . We also note (18) to separate the error due to V̂k−1 and derive
− βtEξt⟨F̃t(θt, ξt), θt − θ⋆,t⟩ = −βt⟨Ft(θt), θt − θ⋆,t⟩ − βt⟨δv,t, θt − θ⋆,t⟩
≤ −βt⟨Ft(θt), θt − θ⋆,t⟩+ βtγ
2
2λθmin ∥Pxt,yt(V̂k−1 − Vk−1)∥2 +
βtλ θ min
2 ∥θt − θ⋆,t∥2,
where Pxt,yt is the matrix denoting the probability matrix multiplying V̂k−1 − Vk−1 in (18) and δv,t = γPxt,yt(Vk−1 − V̂k−1) and we used Cauchy-Schwarz and Young’s inequalities. We can use standard inequalities to estimate ∥Pxt,yt(V̂k−1 − Vk−1)∥22 ≤ |S||A|∥Pxt,yt(V̂k−1 − Vk−1)∥2∞ ≤ |S||A|∥V̂k−1 − Vk−1∥2∞ and take Eξt in (19) by using the two estimations above to get
Eξt∥θt+1 − θ⋆,t∥22 = Eξt∥θt − θ⋆,t∥22 − 2βt⟨Ft(θt), θt − θ⋆,t⟩+ βtγ 2|S||A| λθmin ∥V̂k−1 − Vk−1∥2∞
+ βtλ θ min∥θt − θ⋆,t∥22 + β2tEξt∥F̃t(θt, ξt)∥22. (20)
For the inner product, we would use Ft(θ⋆,t) = 0 and strong monotonicity of Ft (an estimation similar to (Bhandari et al., 2018, Lemma 3)) to get
2βt⟨Ft(θt), θt − θ⋆,t⟩ = 2βt⟨Ft(θt)− Ft(θ⋆,t), θt − θ⋆,t⟩ ≥ 2βtλθmin∥θt − θ⋆,t∥22. (21)
Using this estimate, taking total expectation in (20) and using Young’s inequality on the term involving ∥θt − θ⋆,t∥2 gives,
E∥θt+1 − θ⋆,t∥22 ≤ (1 + α) (1− βtλθmin)E∥θt − θ⋆,t−1∥22
+(1+1/α)(1−βtλθmin)E∥θ⋆,t−θ⋆,t−1∥22+β2tE∥F̃t(θt, ξt)∥22+ βtγ 2|S||A| λθmin E∥V̂k−1−Vk−1∥2∞.
Picking α = βtλ θ min
2(1−βtλθmin) with ensuring βt ≤ 1λθmin due to βt choice, and using ∥θ⋆,t − θ⋆,t−1∥2 = ∥ ∑ b(yt(b|s) − yt−1(b|s))Q(s, a, b)∥2 ≤ √ |S||A|∥ ∑ b(yt(b|s) − yt−1(b|s))Q(s, a, b)∥∞ ≤
2 √ |S||A|/(1− γ)maxs ∥yt(·|s)− yt−1(·|s)∥1 with Lemma B.1 give
E∥θt+1 − θ⋆,t∥22 ≤ ( 1− βtλ θ min
2
) E∥θt − θ⋆,t−1∥22 + β2tE∥F̃t(θt, ξt)∥22
+ 8|S||A| (1− γ)2βtλθmin E ( max s ∥yt(·|s)− yt−1(·|s)∥1 )2 + βtγ 2|S||A| λθmin E∥V̂k−1 − Vk−1∥2∞.
We only need to show that E (maxs ∥yt(·|s)− yt−1(·|s)∥1)2 is small. This is easy since we use small step sizes ηt for the policy update. In particular, the update rule of xt will give by Lemma B.5
∥xt+1(·|s)− xt(·|s)∥1 ≤ ηt∥θt+1∥∞, and by the symmetrical update for yt, it holds that ∥yt+1(·|s)−yt(·|s)∥1 ≤ ηt∥θt+1∥∞ . This is a deterministic inequality holding for all s, so we can take its maximum over s, square it, use Lemma B.1 and plug it into the main inequality.
E∥θt+1 − θ⋆,t∥22 ≤ ( 1− βtλ θ min
2
) E∥θt − θ⋆,t−1∥22 + β2tE∥F̃t(θt, ξt)∥22
+ 8|S||A|η2t ∥θt+1∥2∞ βt(1− γ)2λθmin + βtγ 2|S||A| λθmin E∥V̂k−1 − Vk−1∥2∞.
We plug in the bounds from Lemma B.1 E∥θt+1 − θ⋆,t∥2 ≤ ( 1− βtλ θ min
2
) E∥θt − θ⋆,t−1∥2 +
2β2t (1− γ)2 + 8|S||A|η2t
βt(1− γ)4λθmin
+ βtγ 2|S||A| λθmin E∥V̂k−1 − Vk−1∥2∞.
Picking ηt = 1t3/4 and βt = 1 λθmint 1/2 , the recursion will be ut+1 ≤ (1− c0/
√ t)ut + c1 t C1 + c2√ t C2.
Therefore the final bound is
1
T T∑ t=1 E∥θt+1 − θ⋆,t∥2 ≤ 2√ T ∥θ1 − θ⋆,0∥2 +
4(1 + log T )
(λθmin) 2(1− γ)2
√ T
+ 16|S||A|(1 + log T )√
T (1− γ)4 + 4γ2|S||A| (λθmin) 2 E∥V̂k−1 − Vk−1∥2∞.
Lemma E.7. Denote xout = 1T ∑T t=1 xt and yout = 1 T ∑T t=1 yt. Let Assumption 1, 2 hold and ηt = 1
t3/4 . For the actor computed in stage 1 of Algorithm 5,
E [
max s,z=(x,y)
xsoutQ sys − xQsysout
] ≤ log |A||B|
T 1/4 +
4
(1− γ)2T 3/4 +
2
T T∑ t=1 E∥θxt+1 − θx⋆,t∥∞
+ 2
T T∑ t=1 E∥θyt+1 − θ y ⋆,t∥∞. (22)
Corollary E.8. By plugging in the bound for 1T ∑T
t=1 E∥θt+1 − θ⋆,t∥∞ from Lemma E.2 after Jensen’s inequality and by noting θxt and θ y t admit the same bounds, and by extracting only the dependence on λmin, |S|, |A|, γ, T gives
E [
max s,z=(x,y)
xsoutQ sys − xQsysout
] ≤ 1
T 1/4 Õ (√ |S|(|A| ∨ |B|) (1− γ)2 ) + 1 T 1/4 Õ (
1
λmin(1− γ)
)
+ √ E∥V̂k−1 − Vk−1∥2∞O ( γ √
|S|(|A| ∨ |B|) λθmin
) . (23)
Remark E.9. We make sure E∥V̂k−1 − Vk−1∥∞ is small by the estimation of V̂k−1 in stage 2, in Lemma E.14, Lemma E.11. Proof. Recall the notation xsQsys = ∑
a,b x(a|s)y(b|s)Q(s, a, b). First by definition of xout and the standard arrangement for duality gap, it holds for all s
xsoutQ sys − xsQsysout =
1
T T∑ t=1 ⟨Ea∼xt(·|s)Q(s, a, ·), y(·|s)⟩ − 1 T T∑ t=1 ⟨Eb∼yt(·|s)Q(s, ·, b), x(·|s)⟩
= 1
T T∑ t=1 [ ⟨Ea∼xt(·|s)Q(s, a, ·), y(·|s)− yt(·|s)⟩ − ⟨Eb∼yt(·|s)Q(s, ·, b), x(·|s)− xt(·|s)⟩ ] . (24)
We are going to bound the inner products in RHS. From the update rule of xt+1, for all s, x(·|s) ∈ ∆, it holds that (see (Tseng, 2008, Property 1))
⟨∇D(xt+1(·|s), xt(·|s)) + ηtθt+1(s, ·), x(·|s)− xt+1(·|s)⟩ ≥ 0.
By three point identity and using the notation
D(x(·|s), xt+1(·|s)) ≤ D(x(·|s), xt(·|s)) + ηt⟨θ⋆,t(s, ·), x(·|s)− xt+1(·|s)⟩ + ηt⟨θt+1(s, ·)− θ⋆,t(s, ·), x(·|s)− xt+1(·|s)⟩ −D(xt+1(·|s), xt(·|s)). (25)
We bound the inner products using Cauchy-Schwarz and Young’s inequalities and Equation (8), since x(·|s) ∈ ∆),
ηt⟨θt+1(s, ·)− θ⋆,t(s, ·), x(·|s)− xt+1(·|s)⟩ ≤ 2ηt∥θt+1 − θ⋆,t∥∞, ηt⟨θ⋆,t(s, ·), x(·|s)− xt+1(·|s)⟩ = ηt⟨θ⋆,t(s, ·), x(·|s)− xt(·|s)⟩+ ηt⟨θ⋆,t(s, ·), xt(·|s)− xt+1(·|s)⟩
≤ ηt⟨θ⋆,t(s, ·), x(·|s)− xt(·|s)⟩+ η2t 2 ∥θ⋆,t∥2∞ +D(xt+1(·|s), xt(·|s))
Using these estimations in (25) gives with θ⋆,t(s, ·) = Eb∼yt(·|s)Q(s, ·, b) gives
⟨Eb∼yt(·|s)Q(s, ·, b), xt(·|s)− x(·|s)⟩+ 1
ηt D(x(·|s), xt+1(·|s)) ≤
1 ηt D(x(·|s), xt(·|s))
+ 2∥θt+1 − θ⋆,t∥∞ + ηt 2 ∥θ⋆,t∥2∞.
We sum the inequality, use Lemma B.1 and maxx,xt D(x(·|s), xt(·|s)) ≤ log |A|.
1
T T∑ t=1 ⟨Eb∼yt(·|s)Q(s, ·, b), xt(·|s)− x(·|s)⟩ ≤ 1 η1T D(x(·|s), x1(·|s)) + log |A| T 1/4
+ 1
T T∑ t=1 2∥θt+1 − θ⋆,t∥∞ + ∑T t=1 ηt 2(1− γ)2T .
We use the same estimation for the other player, since it is symmetric, to bound the RHS of (24). Then, we take maximum of both sides w.r.t. s, z, take expectation and bring back superscripts of x, y to θt since we will have error from both players.

heading: E.2 PROOFS FOR STAGE 2 OF SINGLE LOOP NAC WITH ETIQUETTE
text: Remark E.10. Stage 2 is asymmetric for both players. As we are computing best response to xk, x player’s policy remains fixed in this phase, it only computes V̂t−1 to be used in its next stage 1 step.
First, we are going to show that while running this step, y-player can construct its stochastic oracle without access to policy or actions of x-player. Then, as the best response problem is essentially a single agent problem where the other player is part of the environment, our proofs are similar to the results for single agent setting (Khodadadian et al., 2021b; Hong et al., 2020). Let us denote the approximate best response as ȳt̂. Main goal in this step is that we have to characterize explicitly the error ∥V̂k − V xk,ȳt̂∥ as it is used in the stage 2. Note that this is generally not done in single agent setting as the goal is to compute a policy. However, here our main goal is to have access to an oracle approximation Vk = V xk,ŷt̂ , rather than the output policy ȳt̂, therefore, we keep track of ωt that tracks this value function with an explicit error estimate (see Lemma E.11).

heading: E.2.1 FORMULATION
text: Notation. Here, the problem is to compute best response where the other player fixes its strategy. Let us fix xk and denote the best response as y∗k. Here, since xk is fixed, it is a part of the environment for y-player and single agent MDP analyses will go through. We only need to be careful to make sure the “gradient” for ȳt updates can be calculated by not knowing policy or actions of xk.
For NPG updates, we will need to compute at iteration t, ν⋆,t(s, b) = Ea∼xk(·|s)Qxk,ȳt(s, a, b). Writing the Bellman equation and using the definition of value functions
Qxk,ȳt(s, a, b) = r(s, a, b) + γ ∑ s′ P (s′|s, a, b)V xk,ȳt(s′)
= r(s, a, b) + γ ∑ s′ P (s′|s, a, b) ∑ a′,b′ xk(a ′|s′)ȳt(b′|s′)Qxk,ȳt(s′, a′, b′)
We note ν⋆,t(s′, b′) = Ea′∼xk(·|s′)Qxk,ȳt(s′, a′, b′) and take expectation of previous equality with a ∼ xk(·|s),
ν⋆,t(s, b) = ∑ a xk(a|s)r(s, a, b) + γ ∑ s′,a,b′ P (s′|s, a, b)xk(a|s)ȳt(b′|s′)ν⋆,t(s′, b′)
We use the sampling matrix (as (Lan, 2021, Sec. 5.2)) diag(ρxk,ȳt) ⊗ diag(ȳt) and define the operator
F νt (νt)(s, b) = ρ xk,ȳt(s)ȳt(b|s) [ νt(s, b)− ∑ a xk(a|s)r(s, a, b)
− γ ∑
s′,a,b′
xk(a|s)P (s′|s, a, b)ȳt(b′|s′)νt(s′, b′) ] ,
such that F νt (ν⋆,t) = 0. Strong monotonicity of F ν t with constant λ ν min follows from Assumption 1, 2, and that the operator Txkν(s, b) = ∑
a xk(a|s)r(s, a, b) + γ ∑
s′,a,b′ xk(a|s)P (s′|s, a, b)ȳt(b′|s′)ν(b′, s′) is γ contraction in ℓ∞ norm, (Zhao et al., 2021, Lemma 1) (Bauschke et al., 2011, Example 22.6 and 20.7). We define the stochastic operator after sampling ξt = (st, at, bt, st+1, bt+1) with st ∼ ρxk,ȳt , at ∼ xk(·|st), bt ∼ ȳt(·|st), st+1 ∼ P (·|st, at, bt), bt+1 ∼ ȳt(·|st+1),
F̃ νt (νt, ξt) = e(st, bt) (νt(st, bt)− r(st, at, bt)− γνt(st+1, bt+1)) ,
and as we assume we can sample st ∼ ρxk,ȳt , Eξt [F̃ νt (νt, ξt)] = F νt (νt). In particular, we see that as long as st, at, bt, st+1, bt+1 are estimated in the prescribed way, there is no need for ȳt update to see the actions or policy of xk for F̃ νt (νt, ξt) to be unbiased estimate of F ν t (νt). It only needs to see
its own actions bt, bt+1, r(st, at, bt) and st+1.
EξtF νt (νt, ξt) = ∑
s,a,b,s′,b′
Pr(st = s, at = a, bt = b, st+1 = s ′, bt+1 = b ′)e(s, b) [νt(s, b)− r(s, a, b)− γνt(s′, b′)]
= ∑
s,a,b,s′,b′
ρxk,ȳt(s)xk(a|s)ȳt(b|s)P (s′|s, a, b)ȳt(b′|s′)e(s, b) [νt(s, b)− r(s, a, b)− γνt(s′, b′)]
= ∑ s,b ρxk,ȳt(s)ȳt(b|s)e(s, b) [ νt(s, b)− ∑ a xk(a|s)r(s, a, b)
− γ ∑
s′,a,b′
xk(a|s)P (s′|s, a, b)ȳt(b′|s′)νt(s′, b′) ] . (26)
The same estimations as Lemma E.2, without the bias from V̂k−1, as we have unbiased samples will give Lemma E.11.
Let us define the corresponding operator for learning state-value function V xk,ȳt(s) = ∑ a,b xk(a|s)ȳt(b|s)r(s, a, b) + ∑ s′,a,b xk(a|s)ȳt(b|s)P (s′|s, a, b)V xk,ȳt(s′).
Similar to the Q function, we can define ω⋆,t = V xk,ȳt and the operator
Fωt (ωt)(s) = ρ xk,ȳt(s) ( ωt(s)− ∑ a,b xk(a|s)ȳt(b|s)r(s, a, b)
− γ ∑ s′,a,b xk(a|s)ȳt(b|s)P (s′|s, a, b)ωt(s′) ) .
By Assumption 1, 2, this operator is strongly monotone with λωmin, the justification of which is the same as the F νt operator defined above. We also note that F ω t (ω⋆,t) = 0. The corresponding stochastic operator is defined as
F̃ωt (ωt, ξt) = e(st) (ωt(st)− r(st, at, bt)− γωt(st+1)) , where st ∼ ρxk,ȳt , at ∼ xk(·|s), bt ∼ ȳt(·|s), st+1 ∼ P (·|s, a, b) and as we assume we can sample st ∼ ρxk,ȳt ,
Eξt [F̃ωt (ωt, ξt)] = Fωt (ωt).

heading: E.2.2 THEORETICAL RESULTS
text: First, we characterize the critic of stage 2 in Algorithm 5, denoted by νt, ωt for action value function and state value function, respectively. Lemma E.11. Let Assumption 1, 2 hold. Let βνt = 1λνmint1/2 , β ω t = 1 λωmint
1/2 and ηt = 1t3/4 . Then for the critic computed by stage 2 of Algorithm 5,
1
T T∑ t=1 E∥νt+1 − ν⋆,t∥2 = 1√ T { O ( |S||B| (1− γ)2 ) + Õ ( 1 (λνmin) 2(1− γ)2 ) + Õ ( |S||B| (1− γ)6 )} .
1
T T∑ t=1 E∥ωt+1 − ω⋆,t∥2 = 1√ T { O ( |S| (1− γ)2 ) + Õ ( 1 (λωmin) 2(1− γ)2 ) + Õ ( |S| (1− γ)6 )} .
Remark E.12. Using the same samples for θt and V̂t does not seem to cause a problem since the analysis in Lemma E.2 only takes conditional expectations conditioning on θt and uses that maxs ∥xt(·|s)− xt+1(·|s)∥2 is small directly by small step sizes η. Remark E.13. V̂t is not used in the stage 2, but it is estimated to be used in the stage 1 and also to make the bound of Lemma E.7 small since the bound implies E∥ωt̂+1 − V xk,yt̂∥2 = E∥V̂k−1 − Vk−1∥2 ≤ Õ ( 1/T 1/2 ) .
Proof. Let us recall ν⋆,t(s, b) = Ea∼xk(·|s)Qxk,ȳt(s, a, b) and ω⋆,t = V xk,ȳt .
We expand the squared norm ∥νt+1 − ν⋆,t∥22 = ∥νt − ν⋆,t∥22 − 2βt⟨F̃ νt (νt, ξt), νt − ν⋆,t⟩+ β2t ∥F̃ νt (νt, ξt)∥22. We take expectation w.r.t. the randomness of ξt = (st, at, bt, st+1, bt+1) and use from (26) that Eξt [F̃ νt (νt, ξt)] = F νt (νt). Eξt∥νt+1 − ν⋆,t∥22 = ∥νt − ν⋆,t∥22 − 2βt⟨F νt (νt), νt − ν⋆,t⟩+ β2tEξt∥F̃ νt (νt, ξt)∥22 By strong monotonicity and F νt (ν⋆,t) = 0, it follows that
2βt⟨F νt (νt), νt − ν⋆,t⟩ = 2βt⟨F νt (νt)− F νt (ν⋆,t), νt − ν⋆,t⟩ ≥ 2βtλνmin∥νt − ν⋆,t∥22.
We use this estimation and then Young’s inequality to obtain Eξt∥νt+1 − ν⋆,t∥22 ≤ (1− 2βtλνmin) ∥νt − ν⋆,t∥22 + β2tEξt∥F̃ νt (νt, ξt)∥22
≤ (1− βtλνmin) ∥νt − ν⋆,t−1∥22 + 2
βtλνmin ∥ν⋆,t − ν⋆,t−1∥22 + β2tEξt∥F̃ νt (νt, ξt)∥22 (27)
We now have to bound the second term on RHS. For this, we will use Lemma B.4, but first we have to transform the term into the form of Lemma B.4. We recall ν⋆,t(s, b) = Ea∼xk(·|s)Qxk,ȳt(s, a, b)
∥ν⋆,t − ν⋆,t−1∥2 ≤ √ |S||B|∥ν⋆,t − ν⋆,t−1∥∞
= √ |S||B|max
s,b ∣∣Ea∼xk(·|s) (Qxk,ȳt(s, a, b)−Qxk,ȳt−1(s, a, b))∣∣ ≤ √ |S||B|max
s,b Ea∼xk(·|s) ∣∣Qxk,ȳt(s, a, b)−Qxk,ȳt−1(s, a, b)∣∣ ≤ √ |S||B|∥Qxk,ȳt −Qxk,ȳt−1∥∞
≤ 2γ √ |S||B|
(1− γ)2 max s ∥ȳt(·|s)− ȳt−1(·|s)∥1
where the second inequality is by Jensen and the last inequality is by Lemma B.4.
As used in the proof of Lemma E.2, update rule of ȳt(·|s) gives ∥ȳt(·|s)− ȳt−1(·|s)∥1 ≤ ηt∥νt+1∥∞ by Lemma B.5. Using these estimates in (27) after taking total expectation gives
E∥νt+1 − ν⋆,t∥22 ≤ (1− βtλνmin)E∥νt − ν⋆,t−1∥22 + 8|S||B|γ2η2tE∥νt+1∥2∞
βtλνmin(1− γ)4
+ β2tE∥F̃ νt (νt, ξt)∥22. We get the result by using the same argument as the end of the proof of Lemma E.2, by also using Lemma B.1 to bound ∥F̃ νt (νt, ξt)∥22 and ∥νt+1∥2∞. The proof of the second inequality is exactly the same except that in (27), instead of ∥ν⋆,t − ν⋆,t−1∥ we will have ∥ω⋆,t − ω⋆,t−1∥ and we will therefore use Lemma B.3.
Next, we will upper bound V xk,ȳt − V xk,y∗k which is a single agent problem as xk is fixed and we showed in this section how to do the policy evaluation without knowing the actions of xk. The next lemma will be proven similar to single agent settings (Hong et al., 2020; Khodadadian et al., 2021b). Lemma E.14. Let Assumption 1, 2 hold. Let βνt = 1λνmint1/2 , β ω t = 1 λωmint
1/2 and ηt = 1t3/4 . Then for stage 2 of Algorithm 5,
1
T T∑ t=1 EEs0∼σ ( V xk,y ∗ k(s0)− V xk,yt(s0) ) ≤ log |B| (1− γ)T 1/4 +
2
(1− γ)3T 3/4
+ 2
T (1− γ) T∑ t=1 E∥νt+1 − ν⋆,t∥∞
≤ 1 T 1/4
{ O
(√ |S||B|
(1− γ)2
) + Õ ( √ 1
λνmin(1− γ)2
) + Õ (√ |S||B|
(1− γ)4
)} ,
where the second inequality follows by using the results in Lemma E.11.
Proof. By the update rule of ȳt+1 for all s, y(·|s) ∈ ∆, (see (Tseng, 2008, Property 1))
D(y(·|s), ȳt+1(·|s)) ≤ D(y(·|s), ȳt(·|s))− ηt⟨νt+1(s, ·), y(·|s)− ȳt+1(·|s)⟩ −D(ȳt+1(·|s), ȳt(·|s)) = D(y(·|s), ȳt(·|s))− ηt⟨ν⋆,t(s, ·), y(·|s)− ȳt+1(·|s)⟩ − ηt⟨νt+1(s, ·)− ν⋆,t(s, ·), y(·|s)− ȳt+1(·|s)⟩ −D(ȳt+1(·|s), ȳt(·|s))
We estimate the inner products by Cauchy-Schwarz, Young’s inequalities and Equation (8)
ηt⟨νt+1(s, ·)− ν⋆,t(s, ·), y(·|s)− yt+1(·|s)⟩ ≤ 2ηt∥νt+1 − ν⋆,t∥∞,
and
− ηt⟨ν⋆,t(s, ·), y(·|s)− ȳt+1(·|s)⟩ = −ηt⟨ν⋆,t(s, ·), y(·|s)− ȳt(·|s)⟩ − ηt⟨ν⋆,t(s, ·), ȳt(·|s)− ȳt+1(·|s)⟩
≤ −η⟨ν⋆,t(s, ·), y(·|s)− ȳt(·|s)⟩+ η2t ∥ν⋆,t∥2∞
2 +D(ȳt+1(·|s), ȳt(·|s)).
Consequently, by using the definition of ν⋆,t(s, b) = Ea∼xk(·|s)Qxk,ȳt(s, a, b)
⟨Ea∼xk(·|s)Q xk,ȳt(s, a, b), y(·|s)− ȳt(·|s)⟩+
1 ηt D(y(·|s), ȳt+1(·|s)) ≤ 1 ηt D(y(·|s), ȳt(·|s))
+ 2∥νt+1 − ν⋆,t∥∞ + ηt∥ν⋆,t∥2∞
2 . (28)
We sum the inequality and use maxy1,y2 D(y1(·|s), y2(·|s)) ≤ log |B| with KL divergence, to get
1
T T∑ t=1 ⟨Ea∼xk(·|s)Q xk,ȳt(s, a, b), y(·|s)− yt(·|s)⟩ ≤ 1 η1T D(y(·|s), ȳ1(·|s)) + 1 T 1/4 log |B|
+ 2
T T∑ t=1 ∥νt+1 − ν⋆,t∥∞ + ∑T t=1 ηt 2T (1− γ)2 . (29)
Let us recall that y∗k is a best response policy. By the performance difference lemma
V xk,y ∗ k(s0)− V xk,ȳt(s0) =
1
1− γ E s∼d xk,y ∗ k
s0
⟨Ea∼xk(·|s)Q xk,ȳt(s, a, ·), y∗k(·|s)− ȳt(·|s)⟩.
As xk and y∗k are independent of t and fixed throughout the loop, in (29) we plug in y = y ∗ k and take E s∼d xk,y ∗ k
s0
.
Algorithm 6 Reflected NAC with a game etiquette. (See Algorithm 1) Require: Subroutine Policy-Eval (see Algorithm 2, Algorithm 3, Algorithm 4 ). Initial policies x0, y0, ȳ0 for k = 0, 1, . . . do
Stage 1 for t = 0, 1, . . . , T − 1 do [V̂ xk−1, V̂ y k−1] = [Policy-Eval(xk−1, yk−1, N, β ω n ), Policy-Eval(xk−1, yk−1, N, β ω n )]
[θxt+1, θ y t+1] = [Policy-Eval(xt, yt, N, V̂ x k−1, β θ n),Policy-Eval(xt, yt, N, V̂ y k−1, β θ n)]
xt+1(·|s) = P(xt(·|s), η ( 2θxt+1(s, ·)− θxt (s, ·) ) )
yt+1(·|s) = P(yt(·|s),−η ( 2θyt+1(s, ·)− θ y t (s, ·) ) )
Output xk = 1T ∑T
t=1 xt. Stage 2 for t = 0, 1, . . . , T − 1 do νt+1 = Policy-Eval(xk, ȳt, N, β = βνn) ȳt+1(·|s) = P(ȳt(·|s),−ηνt+1(s, ·)) Output yk = ȳt̂, where t̂ ∈ [T ] is selected uniformly at random.
Algorithm 7 Policy-Eval (See Algorithm 2, Algorithm 3, Algorithm 4)
Require: Policy pair x, y, iteration counter N , oracle V̂k−1, step size β for n = 0, 1, . . . , N − 1 do
Sample sn ∼ ρx,y(·), an ∼ x(·|sn), bn ∼ y(·|sn), sn+1 ∼ P (·|sn, an, bn). if β = βωn then F̃ (ϕn, ξn) = e(sn) ( ϕn(sn)− r(sn, an, bn)− γϕn(sn+1) ) else if β = βθn then F̃ (ϕn, ξn) = e(sn, bn) ( ϕn(sn, bn)− r(sn, an, bn)− γV̂k−1(sn+1)
) else if β = βνn then
Sample also bn+1 ∼ y(·|sn+1). F̃ (ϕn, ξn) = e(sn, bn) ( ϕn(sn, bn)− r(sn, an, bn)− γϕn(sn+1, bn+1) ) ϕn+1 = ϕn − βnF̃ (ϕn, ξn)
Output: ϕN

heading: F PROOFS FOR REFLECTED NAC WITH A GAME ETIQUETTE

heading: F.1 PROOFS FOR STAGE 1 OF REFLECTED NAC WITH A GAME ETIQUETTE

heading: F.1.1 FORMULATION
text: For single loop actor-critic in the previous section, it was acceptable to do rough analysis since we used small step sizes. With inner-outer structure, as Lan (2021), we can do tighter analysis with constant step sizes for the outer loops (updates of x, y). Therefore, we can no longer use GDA that we used for single loop NAC, and the techniques from Lan (2021) are not sufficient as the algorithm therein would correspond to GDA in min-max setting. We will have to use a convergent algorithm for the matrix game solver, such as Mirror Prox (Nemirovski, 2004; Korpelevich, 1976) or FoRB ((Malitsky & Tam, 2020)) and extend the ideas from Lan (2021) to these more advanced algorithms to characterize the bias and variance separately. Also, we would have to do a tighter analysis for V̂k estimation.
To obtain the desired oracle θ⋆,t(s, b) = Ea∼xt(·|s)Q(s, a, b), as in (17),
Ft(θ)(s, b) = ρ xt,yt(s)yt(b|s) [ θ(s, b)− ∑ a xt(a|s)r(s, a, b)
− γ ∑ s′,a xt(a|s)P (s′|s, a, b)Vk−1(s′) ] . (30)
We recall that Ft is strongly monotone with λθmin under Assumption 1, 2. Moreover Ft is Lipschitz with λmax. We refer to Appendix E.1.1 for how the oracles in the algorithm can be computed without accessing to other agent’s policy or actions. Moreover, we do not put subscripts θx, θy as the estimations will be symmetric again.

heading: F.1.2 THEORETICAL RESULTS
text: Theorem 3.2. Let Assumption 1, 2 hold. For Algorithm 6, for the output of x-player
EEs0∼µ[max y
V xk,y(s0)− V ⋆(s0)] ≤ Cµ,σk (1− γ) Õ {
1
T (1− γ)2 + |S|(|A| ∨ |B|) λθmin(1− γ)2N
+ |S|2(|A|2 ∨ |B|2) (λθmin) 2N2(1− γ)2 + |S||A| (λθmin) 2(λωmin) 2(1− γ)2N
|S||B| (1− γ)4N2 + 1 N(1− γ)4(λνmin)2 +
√ |S||B|
(1− γ)2N
} +O ( Cµ,σγ k
(1− γ)
) ,
which gives Õ( C 2 µ,σ|S|(|A|∨|B|)
ϵ2(1−γ)8(λθminλωminλνmin)2 ) sample complexity.
We used Remark C.1 to bound Cµ,σ for the result in the main text.
Our theoretical results here bring together ideas from single agent NPG analysis of Lan (2021) and stochastic primal-dual optimization techniques from Malitsky & Tam (2020); Nemirovski et al. (2009). In particular, we will be using ideas from Malitsky & Tam (2020); Nemirovski et al. (2009) in the analysis we develop for extending ideas of Lan (2021) to the stage 1.
We first analyze the policy evaluation routine in Algorithm 6. In particular, we will bound the variance and bias of θt+1 as an estimate of θ⋆,t(s, b) = Ea∼xt(·|s)Qk−1(s, a, b). As this routine is in an inner loop (indexed by n), the policies we sample, consequentlyFt is fixed, therefore we drop the subscript. The proofs of these lemmas will be similar to Lan (2021), except the additional bias we have due to V̂k−1. Lemma 3.6. Let Assumption 1, 2 hold. Let βθn = 2λθmin(n+n0) for n0 ≥ 1. Then, for Algorithms 6 and 7,
E∥θN − θ⋆,t∥22 ≤ O (
|S||A| (1− γ)2N2 + 1
N(λθmin) 2(1− γ)2 + |S||A| (λθmin) 2 E∥V̂k−1 − Vk−1∥2∞
) .
Proof. Throughout this proof, E[·] will stand for conditional expectation E[·|xt]. By the definition of θn,
∥θn+1 − θ⋆,t∥22 = ∥θn − θ⋆,t∥22 − 2βn⟨F̃ (θn, ξn), θn − θ⋆,t⟩+ β2n∥F̃ θ(θn, ξn)∥22.
We will take expectation Eξn where ξn = (sn, an, bn, sn+1) is the sample at iteration n of Algorithm 7
Eξn F̃ (θn, ξn) = F (θn) + γPxt,yt(Vk−1 − V̂k−1),
as in (18) where Pxt,yt was also defined. As we stated, we omit the dependence of Ft to t as t is fixed throughout this loop. Thus,
Eξn∥θn+1 − θ⋆,t∥22 = ∥θn − θ⋆,t∥22 − 2βn⟨F (θn), θn − θ⋆,t⟩ − 2βnγ⟨Pxt,yt(Vk−1 − V̂k−1), θn − θ⋆,t⟩+ β2n∥F̃ (θn, ξn)∥22.
We use strong monotonicity (with F (θ⋆,t) = 0) for the first inner product and Cauchy-Schwarz and Young’s inequalities for the second inner product (exactly as in the proofs for policy evaluation with single loop NAC) to get
Eξn∥θn+1 − θ⋆,t∥22 ≤ ( 1− 2βnλθmin ) ∥θn − θ⋆,t∥22 + βnγ 2
λθmin ∥Pxt,yt(Vk−1 − V̂k−1)∥22
+ βnλ θ min∥θn − θ⋆,t∥22 + β2nEξn∥F̃ (θn, ξn)∥22
= ( 1− βnλθmin ) ∥θn − θ⋆,t∥22 +
βnγ 2|S||A| λθmin ∥Vk−1 − V̂k−1∥2∞ + β2nEξn∥F̃ (θn, ξn)∥22, (31)
where we estimated ∥Pxt,yt(V̂k−1 − Vk−1)∥22 as in Lemma E.2. We will use Lemma B.1 to upper bound ∥F̃ (θn, ξn)∥22 ≤ 2(1−γ)2 . We define Θn such that Θn(1−βnλmin) ≤ Θn−1 with Θ0 = Θ1 = 1. We multiply both sides of the inequality with Θn after taking total expectation, to get
ΘnE∥θn+1 − θ⋆,t∥22 ≤ Θn−1E∥θn − θ⋆,t∥22 + Θnβnγ 2|S||A| λθmin E∥V̂k−1 − Vk−1∥2∞ + 2Θnβ 2 n (1− γ)2 .
Summing the inequality gives ΘNE∥θN+1 − θ⋆,t∥22 ≤ Θ0∥θ1 − θ⋆,t∥22 + N∑
n=1
Θnβnγ 2|S||A|
λθmin E∥V̂k−1 − Vk−1∥2∞ + N∑ n=1 2Θnβ 2 n (1− γ)2 .
Using the definition of βn and setting Θn(1 − βnλmin) = Θn−1 gives Θn = Θ1 (n+n0)(n+n0−1)(n0)(n0+1) . Let us use Θ0 = Θ1 = 1 and bounds from Lemma B.1 for ∥θ1 − θ⋆,t∥22,
E∥θN − θ⋆,t∥22 ≤ 2n0(n0 + 1)|S||A|
(1− γ)2(N + n0)(N + n0 − 1) +
8N
(N + n0)(N + n0 − 1)(1− γ)2(λθmin)2
+ 3γ2|S||A| (λθmin) 2 E∥V̂k−1 − Vk−1∥2∞.
We now analyze the bias for θt+1 in Algorithm 6. Let us remark that the bias analysis for V̂k−1 in the next lemma is critical and it is the main reason that we get fresh estimates for V̂k−1 in this algorithm, in contrast to the stale estimation in the single loop NAC variant.
Lemma 3.7. Let βn = 2λθmin(n+n0) where n0 = 6λ2max λ2min
. Then, for Algorithm 6 and its subroutine Algorithm 7
∥E[θN |xt]− θ⋆,t∥2 ≤ O (
|S||A| (1− γ)2N2 + 10|S||A| (λθmin) 2 ∥E[V̂k−1|xt]− Vk−1∥2∞
) . (32)
Remark F.1. Since the bias term in the algorithm’s analysis will be ( Lemma F.2) ∥E[θN |xt]−θ⋆,t∥, we will have to take the square root of the result of this lemma. If V̂k−1 is estimated before xt, then we will have in the main analysis E∥V̂k−1−Vk−1∥ which will have the rate 1√N . On the other hand, if we estimate V̂k−1 freshly as in Algorithm 6, then we will be able to use the better bias bound ∥E[V̂k−1|xt]− Vk−1∥ = O(1/N) which seems to be enough for our bound.
Proof. We are going to take expectation of the recursion
θn+1 = θn − βnF̃ (θn, ξn),
first w.r.t. sample ξn, where ξn is as in the proof of Lemma 3.6
Eξnθn+1 = θn − βnEξn F̃ (θn, ξn) = θn − βnF (θn)− βnγPxt,yt(V̂k−1 − Vk−1),
where we used (18) where Pxt,yt was also defined.
We will now take expectation E[·|xt]. We note F and Pxt,yt are linear E[θn+1|xt] = E[θn|xt]− βnFt(E[θn|xt])− βnγPxt,yt(E[V̂k−1|xt]− Vk−1).
We denote θ̄n = E[θn|xt] and δ̄ = γPxt,yt(E[V̂k−1|xt]− Vk−1) in the above equality which makes the recursion θ̄n+1 = θ̄n − βnF (θ̄n)− βnδ̄. We then have
∥θ̄n+1 − θ⋆,t∥22 = ∥θ̄n − θ⋆,t∥22 − 2βn⟨F (θ̄n), θ̄n − θ⋆,t⟩ − 2βn⟨δ̄, θ̄n − θ⋆,t⟩
+ 3β2n 2 ∥F (θ̄n)∥22 + 3β2n∥δ̄∥22, (33)
where we also used Young’s inequality to split the term β2n∥F (θ̄n) + δ̄∥2. By strong monotonicity and Lipschitzness of F along with F (θ⋆,t) = 0,
2βn⟨F (θ̄n), θ̄n − θ⋆,t⟩ = 2βn⟨F (θ̄n)− F (θ⋆,t), θ̄n − θ⋆,t⟩ ≥ 2βnλθmin∥θ̄n − θ⋆,t∥22, β2n∥F (θ̄n)∥22 = β2n∥F (θ̄n)− F (θ⋆,t)∥22 ≤ β2nλ2max∥θ̄n − θ⋆,t∥22.
By Cauchy-Schwarz and Young’s inequalities, it follows that 2βn⟨δ̄, θ̄n − θ⋆,t⟩ ≤ βnλ θ min
2 ∥θ̄n − θ⋆,t∥22 +
2βn λθmin ∥δ̄∥22. Using these three inequalities in (33) gives ∥θ̄n+1 − θ⋆,t∥22 ≤ ( 1− 3
2 βnλ
θ min +
3 2 β2nλ 2 max
) ∥θ̄n − θ⋆,t∥22 +
2βn λθmin ∥δ̄∥22 + 3β2n∥δ̄∥22.
We now use n0 = 6λ2max (λθmin) 2 and βn = 2λθmin(n+n0) to estimate
3βn 2
( λθmin − βnλ2max ) = 3βn 2 ( λθmin − 2λ2max λθmin(n+ n0) ) ≥ 3βn 2 ( λθmin − 2λ2max λθminn0 ) = βnλ θ min.
Therefore, the recursion is ∥θ̄n+1 − θ⋆,t∥22 ≤ ( 1− βnλθmin ) ∥θ̄n − θ⋆,t∥22 +
2βn λθmin ∥δ̄∥2 + 3β2n∥δ̄∥22.
This recursion is similar to (31), in particular, by noting βn ≤ 1λθmin , and bounding ∥δ̄∥ 2 2 similar to Lemma E.2: ∥Pxt,yt(E[V̂k−1|xt] − Vk−1)∥22 ≤ |S||A|∥Pxt,yt(E[V̂k−1|xt] − Vk−1)∥2∞ ≤ |S||A|∥E[V̂k−1|xt]− Vk−1∥2∞
∥θ̄n+1 − θ⋆,t∥2 ≤ ( 1− βnλθmin ) ∥θ̄n − θ⋆,t∥2 +
5βn|S|||A| λθmin ∥E[V̂k−1|xt]− Vk−1∥2∞.
We finally define Θn as in the end of the proof of Lemma 3.6, in particular, Θn(1−βnλmin) = Θn−1 gives Θn = Θ1
(n+n0)(n+n0−1) n0(n0−1) , where Θ0 = Θ1 = 1. We multiply both sides of the inequality
with Θn and sum to get the result.
We now have to estimate the bias and variance of the estimation of V̂k−1 in Algorithm 6, very similar to Lan (2021). Unlike Lan (2021) that derived O(1/N3) bound for the bias, we are going to derive a O(1/N2) bound which will be sufficient. Let us also note that the previous two lemmas had additional bias not present in Lan (2021), however the next result does not have this bias and therefore the arguments in Lan (2021) would be enough. We provide a brief proof to be self-contained.

heading: Let us recall that Vk−1 = V xk−1,yk−1 and by sampling sn ∼ ρxk−1,yk−1 , an ∼ xk−1(·|sn), bn ∼
text: yk−1(·|sn), sn+1 ∼ P (·|sn, an, bn), the oracle
F̃ω(ωn, ξn) = e(sn) (ωn(sn)− r(sn, an, bn)− γωn(sn+1)) , satisfies Eξn F̃ω(ωn, ξn) = Fω(ωn), where Fω is defined as
Fωk−1(ω)(s) = ρ xk−1,yk−1(s)
( ω(s)− ∑ a,b xk−1(a|s)yk−1(b|s)r(s, a, b)
− γ ∑ s′,a,b xk−1(a|s)yk−1(b|s)P (s′|s, a, b)ω(s′) ) , (34)
where Fωk−1(Vk−1) = 0 and also as before F ω k−1 is strongly monotone with λ ω min. We will drop the subscript of Fω since k is fixed in this loop.
Lemma 3.8. Let Assumption 1, 2 hold and βωn = 2λωmin(n+n0) , with n0 = 6λ2max (λωmin) 2 . The variance and bias of V̂k−1, computed as in Algorithm 1 satisfies
E∥ωN − Vk−1∥22 ≤ O (
|S||A| (1− γ)2N2 + 1
N(1− γ)2λ2min
) ,
∥E[ωN |xt]− Vk−1∥22 ≤ O (
|S||A| (1− γ)2N2
) .
Proof. For the variance, we have by taking expectation w.r.t. ξn
Eξn∥ωn+1 − Vk−1∥22 = ∥ωn − Vk−1∥22 − 2βn⟨Eξn [F̃ω(ωn, ξn)], ωn − Vk−1⟩+ β2nEξn∥F̃ω(ωn, ξn)∥22.
By Eξn F̃ω(ωn, ξn) = Fω(ωn), Fω(Vk−1) = 0, and strong monotonicity of Fω , similar to our previous proofs for policy evaluation,
E∥ωn+1 − Vk−1∥22 = (1− 2βnλωmin)E∥ωn − Vk−1∥22 + β2nE∥F̃ω(ωn, ξn)∥22.
The end of the proof is the same as Lemma 3.6, except that we do not have here the additional bias term in Lemma 3.6. Therefore, the result follows.
For the bias, we will argue as in Lemma 3.7. Taking expectation of the recursion w.r.t. ξn gives
Eξnωn+1 = ωn − βnFω(ωn).
We now unroll the expectation until xt and use linearity of Fω
E[ωn+1|xt] = E[ωn|xt]− βnFω(E[ωn|xt]).
Denoting ω̄n = E[ωn|xt] gives the recursion ω̄n+1 = ω̄n − βnFω(ω̄n), and therefore
∥ω̄n+1 − Vk−1∥22 = ∥ω̄n − Vk−1∥22 − 2βn⟨Fωk−1(ω̄n), ω̄n − Vk−1⟩+ β2n∥Fω(ω̄n)∥22.
We will now use Lipschitzness and strong monotonicity of Fω and that Fω(Vk−1) = 0 and similar to Lemma 3.7, we obtain the recursion
∥ω̄n+1 − Vk−1∥22 = ( 1− 2βnλmin + β2nλ2max ) ∥ω̄n − Vk−1∥22.
By the choice of n0 and βn, similar to Lemma 3.7, it holds that 2βnλmin − β2nλ2max ≥ βnλmin. By defining Θn the same way as Lemma 3.7 and summing the inequality gives the result.
Now we analyze the outer algorithm for solving the matrix game in stage 1. The algorithm is based on FoRB from Malitsky & Tam (2020). The choice of this algorithm is due to its simple update with one projection and one oracle computation. We note that the existing analyses for stochastic versions of this algorithm are not suitable for us. In particular, in the stochastic variant in Malitsky & Tam (2020), deterministic oracle is also computed at each iteration. On the other hand, the analysis in Böhm et al. (2020) uses unbiased oracles with bounded variance and a decreasing step size. In our case, we will have biased samples and we will use inner loops to decrease bias and variance of this oracle. Therefore, we need to develop an analysis with constant step size and that characterizes the bias and variance explicitly.
Similar to Malitsky & Tam (2020), let us define the “Lyapunov-like” function
Φst+1 = D(x(·|s), xt+1(·|s)) + η⟨θ⋆,t+1(s, ·)− θt+1(s, ·), x(·|s)− xt+1(·|s)⟩
+ 1
2 D(xt+1(·|s), xt(·|s)). (35)
We call this “Lyapunov-like” since it is not non-decreasing. Moreover, unlike Malitsky & Tam (2020), Φt is not necessarily nonnegative. However, it is sufficient for our purposes as it is bounded. Note that we will also use the following error functions
e1,t = η⟨θt+1(·|s)− E[θt+1(·|s)|xt], x(·|s)− xt(·|s)⟩ e2,t = η⟨θyt+1(·|s)− E[θ y t+1(·|s)|yt], yt(·|s)− y(·|s)⟩.
Lemma F.2. [See Lemma 3.4] Let Assumption 1, 2 hold. Denote xout = 1T ∑T
t=1 xt and yout = 1 T ∑T t=1 yt and let η = 1−γ 8
EEs∼σ [ max xs,ys xsoutQ sys − xsQsyout ] = O ( Φs0 − ΦsT ηT ) +O ( 1 T T∑ t=1 E∥E[θt+1|xt]− θ⋆,t∥ )
+O
( 1
T T∑ t=1
ηE∥θt+1 − θ⋆,t∥2 + E∥θt − θ⋆,t−1∥2 ) + 1
Tη EEs∼σ max z T∑ t=1 [e1,t + e2,t]).
Remark F.3. When D is KL divergence, we have maxy1,y2 D(y1, y2) ≤ log |B| and equivalently for the other player. Therefore, we have the bound
Φs0 − ΦsT +Φs0,y − ΦsT,y ≤ O ( log |A|+ log |B|+ η
1− γ
) .
Corollary F.4. We use Lemmas 3.6, 3.7 and F.6,
Õ (
1
T (1− γ)
) +O ( √ |S||A|
(1− γ)N + √ |S||A| λθmin ∥E[V̂k−1|xt]− Vk−1∥∞ )
+O (
|S||A| (1− γ)2N2 + 1
N(λθmin) 2(1− γ)2 + |S||A| (λθmin) 2 E∥V̂k−1 − Vk−1∥2∞
) .
We add the bound from Lemma 3.8
Õ (
1
T (1− γ)
) +O ( √ |S||A|
(1− γ)N + √ |S||A| λθmin [ √ |S||A| (1− γ)N ])
+O (
|S||A| (1− γ)2N2 + 1
N(λθmin) 2(1− γ)2 + |S||A| (λθmin) 2
[ |S||A|
(1− γ)2N2 +
1
N(1− γ)2(λωmin)2
]) .
We now refine the bound by only including the dominant terms Õ ( 1
T (1− γ)
) +O ( |S||A|
λθmin(1− γ)2N ) +O ( |S|2|A|2
N2(1− γ)2(λθmin)2 + |S||A| (λθmin) 2(λωmin) 2(1− γ)2N ) Remark F.5. By Lemma 3.6 and Lemma 3.7, the second and third term will bring O (
1 N + E∥E[V̂k−1|xt]− Vk−1∥ ) . We will see in the next lemma how to handle error terms e1, e2
and will use the bound derived earlier for E∥E[V̂k−1|xt]− Vk−1∥.
Proof. By the update rule, it follows for all s and x(·|s) ∈ ∆,
⟨∇D(xt+1(·|s), xt(·|s)) + η(2θt+1(s, ·)− θt(s, ·)), x(·|s)− xt+1(·|s)⟩ ≥ 0.
By three point identity,
D(x(·|s), xt+1(·|s)) ≤ D(x(·|s), xt(·|s))−D(xt+1(·|s), xt(·|s)) + η⟨(2θt+1(s, ·)− θt(s, ·)), x(·|s)− xt+1(·|s)⟩. (36)
We now manipulate the inner product by adding and subtracting θ⋆,t+1
η⟨(2θt+1(s, ·)− θt(s, ·)), x(·|s)− xt+1(·|s)⟩ = η⟨θt+1 − θ⋆,t+1(s, ·), x(·|s)− xt+1(·|s)⟩ + η⟨θt+1(s, ·)− θt(s, ·) + θ⋆,t+1(s, ·), x(·|s)− xt+1(·|s)⟩
= η⟨θt+1(s, ·)− θ⋆,t+1(s, ·), x(·|s)− xt+1(·|s)⟩+ η⟨θt+1(s, ·)− θt(s, ·), x(s, ·)− xt(·|s)⟩ + η⟨θt+1(s, ·)− θt(s, ·), xt(·|s)− xt+1(·|s)⟩+ η⟨θ⋆,t+1(s, ·), x(·|s)− xt+1(·|s)⟩. (37)
The first two inner products in the final inequality will telescope if we can replace θt+1 with θ⋆,t in the second one. For this we have to be careful with bias and variance. Let us take the second inner product
η⟨θt+1(s, ·)− θt(s, ·), x(·|s)− xt(·|s)⟩ = η⟨θ⋆,t(s, ·)− θt(s, ·), x(·|s)− xt(·|s)⟩ +η⟨θt+1(s, ·)− θ⋆,t(s, ·), x(·|s)− xt(·|s)⟩.
Now in this estimation, we will add and subtract terms involving E[θt+1(s, ·)|xt] to obtain
η⟨θt+1(s, ·)− θt(s, ·), x(·|s)− xt(·|s)⟩ = η⟨θ⋆,t(s, ·)− θt(s, ·), x(·|s)− xt(·|s)⟩ + η⟨E[θt+1(s, ·)|xt]− θ⋆,t, x(·|s)− xt(·|s)⟩+ η⟨θt+1(s, ·)− E[θt+1(s, ·)|xt], x(·|s)− xt(·|s)⟩
≤ η⟨θ⋆,t(s, ·)− θt(s, ·), x(·|s)− xt(·|s)⟩+ 2η∥E[θt+1|xt]− θ⋆,t∥∞ + e1,t, (38) where the inequality is due to Cauchy-Schwarz and we use the definition of e1,t for the last term. Next, we use Cauchy-Schwarz and Young’s inequalities for the third inner product in RHS of (37) to derive
η⟨θt+1(s, ·)−θt(·|s), xt(·|s)−xt+1(·|s)⟩ ≤ η2∥θt+1(s, ·)−θt(·|s)∥2∞+ 1
4 ∥xt(·|s)−xt+1(·|s)∥21 ≤ 4η2 [ ∥θt+1(s, ·)− θ⋆,t(s, ·)∥2∞ + ∥θ⋆,t(s, ·)− θ⋆,t−1(s, ·)∥2∞ + ∥θ⋆,t−1(s, ·)− θt(s, ·)∥2∞ ] + 1
4 ∥xt(·|s)− xt+1(·|s)∥21. (39)
As θ⋆,t(s, a) = Eb∼yt(·|s)Q(s, a, b), we have
∥θ⋆,t(s, ·)− θ⋆,t−1(s, ·)∥∞ ≤ max b,a |Q(s, a, b)|∥yt(·|s)− yt−1(·|s)∥1
≤ 2 1− γ ∥yt(·|s)− yt−1(·|s)∥1, (40)
where the second inequality is by Lemma B.1 and the first by Jensen. We join (38), (39), and (40) in (37)
η⟨(2θt+1(s, ·)− θt(s, ·)), x(·|s)− xt+1(·|s)⟩ ≤ η⟨θt+1(s, ·)− θ⋆,t+1(s, ·), x(·|s)− xt+1(·|s)⟩ η⟨θ⋆,t(s, ·)− θt(s, ·), x(·|s)− xt(·|s)⟩+ 2η∥E[θt+1|xt]− θ⋆,t∥∞ + e1,t
+ 4η2 [ ∥θt+1 − θ⋆,t∥2∞ + ∥θ⋆,t−1 − θt∥2∞ ] + 16η2
(1− γ)2 ∥yt(·|s)− yt−1(·|s)∥21
+ 1
4 ∥xt(·|s)− xt+1(·|s)∥21 + η⟨θ⋆,t+1(s, ·), x(·|s)− xt+1(·|s)⟩. (41)
We note that by Equation (8), 14∥xt(·|s) − xt+1(·|s)∥ 2 1 ≤ 12D(xt+1(·|s), xt(·|s)) and similarly for the term involving difference of yt and yt−1.
We insert (41) into (36) by using the definition of Φt
η⟨θ⋆,t+1(s, ·), xt+1(·|s)− x(·|s)⟩+Φst+1 ≤ Φst + e1,t + 2η∥E[θt+1|xt]− θ⋆,t∥∞ + 4η2 [ ∥θt+1 − θ⋆,t∥2∞ + ∥θ⋆,t−1 − θt∥2∞ ] + 32η2
(1− γ)2 D(yt(·|s), yt−1(·|s))−
1 2 D(xt(·|s), xt−1(·|s)).
We sum this inequality and use the definition of θ⋆,t+1 to obtain
η
T T−1∑ t=0 ⟨Eb∼yt+1(·|s)Q(s, ·, b), xt+1(·|s)− x(·|s)⟩ ≤ Φs0 − ΦsT T + 1 T T−1∑ t=0 e1,t
+ 1
T T−1∑ t=0 2η∥E[θt+1|xt]− θ⋆,t∥∞ + 4η2 T T∑ t=1 [ ∥θt+1 − θ⋆,t∥2∞ + ∥θ⋆,t−1 − θt∥2∞ ] + 1
T T∑ t=0 32η2 (1− γ)2 D(yt(·|s), yt−1(·|s))− 1 2 D(xt(·|s), xt−1(·|s)).
We have to estimate the error terms in the last line. The terms in the second line will be the bias and variance arising from using θt+1 instead of the true oracle. First, by the symmetric estimation on the y player, we can obtain the similar inequality. For making the comparison, we will denote the corresponding oracle as θy (θ in the previous estimations correspond to θx). In particular θy⋆,t+1(s, b) = Ea∼xt+1(·|s)Q(s, a, b), and the corresponding Lyapunov-like function as Φst,y
η
T T−1∑ t=0 ⟨Ea∼xt+1(·|s)Q(s, a, ·), y(·|s)− yt+1(·|s)⟩ ≤ Φs0,y − Φsy,T T + 1 T T−1∑ t=0 e2,t
+ 1
T T−1∑ t=0 2η∥E[θyt+1|xt]− θ y ⋆,t∥∞ + 4η2 T T∑ t=1 [ ∥θyt+1 − θ y ⋆,t∥2∞ + ∥θ y ⋆,t−1 − θ y t ∥2∞ ] + 1
T T∑ t=0 32η2 (1− γ)2 D(xt(·|s), xt−1(·|s))− 1 2 D(yt(·|s), yt−1(·|s)).
After summing up the two inequalities and recalling that we bound the RHS of (24), we pick η ≤ 1−γ 8 to cancel the last terms in the last lines of the estimations. Since we estimate θt and θ y t in the same way, their bounds as we derived in Lemma 3.7, Lemma 3.6 will be the same, therefore in the bound we do not include both and simply put them under big-Oh. Next, we take maximum over x, y, take expectation w.r.t. state distribution σ and total expectation w.r.t. randomness in the algorithm and use the definitions of xout and yout to conclude the result.
For the error terms e1,t, e2,t, we will use the technique to change the order of maximum and expectation from the literature of stochastic primal-dual methods (Nemirovski et al., 2009, Lemma 3.1, Lemma 6.1). Let us recall their definitions:
e1,t = η⟨θt+1(·|s)− E[θt+1(·|s)|xt], x(·|s)− xt(·|s)⟩ e2,t = η⟨θyt+1(·|s)− E[θ y t+1(·|s)|yt], yt(·|s)− y(·|s)⟩
We will derive the bound or e1,t and the bound for e2,t is symmetrical.
Lemma F.6. We have
1 T EEs∼σ max x T∑ t=1 e1,t ≤ log |A| T + 1 T T∑ t=1 4η2E∥θt+1 − θ⋆,t∥2∞.
Proof. First note that ⟨θt+1(·|s) − E[θt+1(·|s)|xt], xt(·|s)⟩ does not depend on x and by the tower property of conditional expectation,
T∑ t=1 EEs∼ση⟨θt+1(·|s)− E[θt+1(·|s)|xt], xt(·|s)⟩
= EEs∼ση⟨E[θt+1(·|s)|xt]− E[θt+1(·|s)|xt], xt(·|s)⟩ = 0.
Therefore, we have to estimate
EEs∼σ max x T∑ t=1 η⟨θt+1(·|s)− E[θt+1(·|s)|xt], x(·|s)⟩.
Let nt(s, ·) = −η(θt+1(·|s) − E[θt+1(·|s)|xt]). First, we note that E[nt(s, ·)|xt] = 0. Next, we define the auxiliary “ghost” process
x̃t+1(·|s) = argmin x ⟨nt(s, ·), x(·|s)⟩+D(x(·|s), x̃t(·|s)).
Note that x̃t and xt depend on the same randomness by definition of x̃t, therefore conditioned on xt, x̃t is deterministic. Standard mirror descent analysis gives for any x
⟨nt(s, ·), x(·|s)⟩ ≤ D(x(·|s), x̃t(·|s))−D(x(·|s), x̃t+1(·|s)) + ⟨nt(s, ·), x̃t(·|s)⟩+ ∥nt(·|s)∥2∗.
We sum the inequality take maximum and then expectation
EEs∼σ max x T∑ t=1 ⟨−nt(s, ·), x(·|s)⟩ ≤ Es∼σD(x(·|s), x̃1(·|s)) + T∑ t=1 EEs∼σ⟨−nt(s, ·), x̃t(·|s)⟩
+ T∑ t=1 EEs∼ρ∥nt(·|s)∥2∞.
By the tower property and that x̃t is deterministic conditioned on xt, we have∑T t=1 E⟨nt(s, ·), x̃t(·|s)⟩ = ∑T t=1 E⟨E[nt(s, ·)|xt], x̃t(·|s)⟩ = 0.
Recall the definition of nt and use Young’s inequality with Jensen’s inequality to get
E∥nt(s, ·)∥2 = Eη2∥θt+1(·|s)− E[θt+1(·|s)|xt]∥2∞ ≤ 2Eη2∥θt+1(·|s)− θ⋆,t∥2∞ + 2Eη2∥θ⋆,t − E[θt+1(·|s)|xt]∥2∞ ≤ 4Eη2∥θt+1(·|s)− θ⋆,t∥2∞.

heading: F.2 PROOFS FOR STAGE 2 OF REFLECTED NAC WITH A GAME ETIQUETTE
text: Similar to single loop NAC variant, this part mirror closely the analyses for single agent setting, as the best response step is like a single agent problem where the other agent (fixed) can be seen as part of the environment. Therefore, the development in this part will be similar to Lan (2021). Let us restate that the main concern in this part was to make sure that ȳt updates do not require seeing the policy xk or the actions of x-player. As we showed that it is the case (in Appendix E.2.1), we will only provide the proofs here, with mostly using the arguments of Lan (2021). Therefore, the proofs in this part are included for being self-contained and for easy navigation. Therefore, they will be brief.
First, we will prove the bias and variance of the estimate νt, similar to Lemma 3.8. Let us recall the Bellman operator for the oracle ν⋆,t = Ea∼xk(·|s)Qxk,ȳt(·, a, ·) that the update is using:
ν⋆,t(s, b) = ∑ a xk(a|s)r(s, a, b) + γ ∑ s′,a,b′ P (s′|s, a, b)xk(a|s)ȳt(b′|s′)ν⋆,t(s′, b′)
We use the sampling matrix (as (Lan, 2021, Sec. 5.2)) diag(ρxk,ȳt) ⊗ diag(ȳt) and define the operator
F νt (νt)(s, b) = ρ xk,ȳt ȳt(b|s) [ νt(s, b)− ∑ a xk(a|s)r(s, a, b)
− γ ∑
s′,a,b′
xk(a|s)P (s′|s, a, b)ȳt(b′|s′)νt(s′, b′) ] , (42)
such that F νt (ν⋆,t) = 0. Strong monotonicity of Ft follows from Assumption 1, 2 and that the operator Tν(s, b) = ∑ a xk(a|s)r(s, a, b)+γ ∑ s′,a,b′ xk(a|s)P (s′|s, a, b)ȳt(b′|s′)ν(b′, s′) being γ contraction in ℓ∞ norm (Bauschke et al., 2011, Example 22.6 and 20.7). We define the stochastic operator after sampling st ∼ ρxk,ȳt , at ∼ xk(·|st), bt ∼ ȳt(·|st), st+1 ∼ P (·|st, at, bt), bt+1 ∼ ȳt(·|st+1) F̃ νt (νt, ξt) = e(st, bt) (νt(st, bt)− r(st, at, bt)− γνt(st+1, bt+1)) , and as we assume we can sample st ∼ ρxk,ȳt , Eξt [F̃ νt (νt, ξt)] = F νt (νt). In particular, as long as st, at, bt, st+1 are estimated in the prescribed way, there is no need for ȳt update to see the actions or policy of xk for F̃ νt (νt, ξt) to be unbiased estimate of F ν t (νt).
We note that unlike the NAC case, we are having an inner loop to estimate ν⋆,t. At the point of view of this loop (runs from n = 0, · · · , N − 1), ν⋆,t is fixed. Lemma F.7. Let Assumption 1, 2 hold and βn = 2λνmin(n+n0) stage 2 in Algorithm 6 satisfies
E∥νN − ν⋆,t∥22 ≤ O (
|S||B| (1− γ)2N2 + 1
N(1− γ)2(λνmin)2
) ,
∥E[νN |ȳt]− ν⋆,t∥22 ≤ O (
2|S||B| (1− γ)2N2
) .
Proof. For the variance, we have by taking expectation w.r.t. ξn = (sn, an, bn, sn+1, bn+1)
Eξn∥νn+1 − ν⋆,t∥22 = ∥νn − ν⋆,t∥22 − 2βn⟨Eξn [F̃ νt (νn, ξn)], νn − ν⋆,t⟩+ β2nEξn∥F̃ νt (νn, ξn)∥22.

heading: By Eξn F̃ νt (νn, ξn) = F νt (νn), F νt (ν⋆,t) = 0, and strong monotonicity of F νt ,
text: E∥νn+1 − ν⋆,t∥22 = (1− 2βnλνmin)E∥νn − ν⋆,t∥22 + β2nE∥F̃ νt (νn, ξn)∥22.
The end of the proof is the same as Lemma 3.6, except that we do not have here the additional bias term in Lemma 3.6. Therefore, the result follows.
For the bias, we will argue as in Lemma 3.7. Taking expectation of the recursion w.r.t. ξn gives
Eξnνn+1 = νn − βnF νt (νn).
We now unroll the expectation until yt and use linearity of F νt
E[νn+1|ȳt] = E[νn|ȳt]− βnF νt (E[νn|ȳt]).
Denoting ν̄n = E[νn|ȳt] gives
∥ν̄n+1 − ν⋆,t∥22 = ∥ν̄n − ν⋆,t∥22 − 2βn⟨F νt (ν̄n), ν̄n − ν⋆,t⟩+ β2n∥F νt (ν̄n)∥22.
We will now use Lipschitzness and strong monotonicity of F νt and that F ν t (ν⋆,t) = 0 and similar to Lemma 3.7, we obtain the recursion
∥ν̄n+1 − ν⋆,t∥22 = ( 1− 2βnλνmin + β2nλ2max ) ∥ν̄n − ν⋆,t∥22.
By the choice of n0 and βn, similar to Lemma 3.7, it holds that 2βnλνmin − β2nλ2max ≥ βnλνmin. By defining Θn the same way as Lemma 3.7 and summing the inequality gives the result.
We will now give a proof similar to (Lan, 2021, Theorem 2), (Agarwal et al., 2020) regarding the NPG algorithm for finding the best response.
Theorem F.8. Let Assumption 1, 2 hold and η > 0. For the stage 2 of Algorithm 6.
1
T T∑ t=1 V xk,y ∗ k(s0)−V xk,ȳt(s0) ≤
η (1− γ)T E [ E s∼d xk,y ∗ k
s0
D(y∗k(·|s), y1(·|s))−V xk,ȳ1(s)+V xk,ȳt+1(s) ]
+ η 2(1− γ)2 1 T T∑ t=1 E∥ν⋆,t − νt+1∥2∞ + 2 1− γ 1 T T∑ t=1 E∥E[νt+1|ȳt]− ν⋆,t∥∞
Corollary F.9. We use the bound from Lemma F.7 to obtain
Õ (
1
T (1− γ)2
) +O ( |S||B|
(1− γ)4N2 +
1
N(1− γ)4(λνmin)2
) +O ( √ |S||B|
(1− γ)2N
) . (43)
Proof. By the update rule of ȳt+1, it follows for any s, ȳ (Tseng, 2008, Property 1)
D(ȳ(·|s), ȳt+1(·|s)) ≤ D(ȳ(·|s), ȳt(·|s))−D(ȳt+1(·|s), ȳt(·|s))−⟨ηνt+1(s, ·), ȳ(·|s)−ȳt+1(·|s)⟩. (44)
We manipulate the inner product
−η⟨νt+1(s, ·), ȳ(·|s)−ȳt+1(·|s)⟩ = −η⟨νt+1(s, ·), ȳ(·|s)−ȳt(·|s)⟩−η⟨νt+1(s, ·), ȳt(·|s)−ȳt+1(·|s)⟩ = −η⟨ν⋆,t(s, ·), ȳ(·|s)− ȳt(·|s)⟩ − η⟨νt+1(s, ·), ȳt(·|s)− ȳt+1(·|s)⟩
− η⟨νt+1(s, ·)− ν⋆,t(s, ·), ȳ(·|s)− ȳt(·|s)⟩. (45)
By the performance difference lemma and using the definition of ν⋆,t = Ea∼xkQxk,ȳt(·, a, ·).
V xk,ȳt+1(s0)− V xk,ȳt(s0) = 1
1− γ E s∼d xk,ȳt+1 s0 ⟨Ea∼xk(·|s)Q xk,ȳt(s, a, ·), ȳt+1(·|s)− ȳt(·|s)⟩
= 1
1− γ E s∼d xk,ȳt+1 s0 ⟨ν⋆,t(s, ·), ȳt+1(·|s)− ȳt(·|s)⟩
= 1
1− γ E s∼d xk,ȳt+1 s0
[ ⟨νt+1(s, ·), ȳt+1(·|s)− ȳt(·|s)⟩
+ ⟨ν⋆,t(s, ·)− νt+1(s, ·), ȳt+1(·|s)− ȳt(·|s)⟩ ]
≥ 1 1− γ E s∼d xk,ȳt+1 s0
[ ⟨νt+1(s, ·), ȳt+1(·|s)− ȳt(·|s)⟩ − η
2 ∥ν⋆,t(s, ·)− νt+1(s, ·)∥2∞
− 1 2η
∥ȳt+1(·|s)− ȳt(·|s)∥21 ] , (46)
where the last step uses Cauchy-Schwarz and Young’s inequalities.
Plugging in ȳ = ȳt in (44) and using Equation (8) gives
−η⟨νt+1(s, ·), ȳt(·|s)− ȳt+1(·|s) ≥ D(ȳt(·|s), ȳt+1(·|s)) +D(ȳt+1(·|s), ȳt(·|s)) ≥ ∥ȳt+1(·|s)− ȳt(·|s)∥21,
which implies that ⟨νt+1(s, ·), ȳt+1(·|s)− ȳt(·|s)⟩ − 12η∥ȳt+1(·|s)− ȳt(·|s) ≥ 0. Recall that dxk,ȳt+1s0 (s) = (1− γ) ∑∞ t=0 γ tPrxk,ȳt+1(st = s|s0), therefore 1− γ ≤ dxk,ȳt+1s0 (s0) ≤ 1. Using the two previous inequalities in (46) gives
⟨νt+1(s, ·), ȳt+1(·|s)− ȳt(·|s)⟩ ≤ V xk,ȳt+1(s)− V xk,ȳt(s) + 1
2η ∥ȳt+1(·|s)− ȳt(·|s)∥21
+ η
2(1− γ) ∥ν⋆,t − νt+1∥2∞.
We use the final inequality, (45), and (8) in (44) to get
η⟨ν⋆,t(s, ·), ȳ(·|s)− ȳt(·|s)⟩+D(ȳ(·|s), yt+1(·|s))− ηV xk,ȳt+1(s) ≤ D(ȳ(·|s), yt(·|s))
− ηV xk,ȳt(s) + η 2
2(1− γ) ∥ν⋆,t − νt+1∥2∞ + η⟨ν⋆,t(s, ·)− νt+1(s, ·), ȳ(·|s)− ȳt(·|s)⟩. (47)
In view of the definition ν⋆,t = Ea∼xk(·|s)Qxk,ȳt(·, a, ·), performance difference lemma gives (1− γ)(V xk,y ∗ k(s0)− V xk,ȳt(s0)) = E
s∼d xk,y
∗ k
s0 ⟨ν⋆,t(s, ·), y∗k(·|s)− yt(·|s)⟩. Plugging in y = y∗k in (47) and taking E
s∼d xk,y
∗ k
s0
of both sides give
η(1− γ)(V xk,y ∗ k(s0)− V xk,ȳt(s0)) + E
s∼d xk,y
∗ k
s0
[ D(y∗k(·|s), ȳt+1(·|s))− ηV xk,ȳt+1(s) ] ≤ E
s∼d xk,y
∗ k
s0
[ D(y∗k(·|s), ȳt(·|s))− ηV xk,ȳt(s) +
η2
2(1− γ) ∥ν⋆,t − νt+1∥2∞ + η⟨ν⋆,t(s, ·)− νt+1(s, ·), ȳ∗k(·|s)− ȳt(·|s)⟩ ] . (48)
Now we take expectation w.r.t. the randomness in the algorithm, use tower property, the fact that conditioned on ȳt, y∗k(·|s)− ȳt(·|s) is deterministic, Cauchy-Schwarz inequality, ȳ(·|s) ∈ ∆ for any ȳ, s. After those steps, we note that dxk,y ∗ k
s0 does not depend on t and sum the inequality over t to get the result.
Algorithm 8 Single loop NAC with a game etiquette and ζ-greedy exploration
Require: V̂0 such that ∥V̂0 − V x0,y0∥2∞ ≤ ϵ for k = 1, 2, . . . do
Stage 1 for t = 0, 1, . . . , T − 1 do
Sample (st, at, bt, st+1), with policy pair x̂t, ŷt observe st, bt, r(st, at, bt), st+1 θ̂xt+1 = θ̂ x t − βte(st, at) ( θ̂xt (st, at)− r(st, at, bt)− γ ˆ̂ Vk−1(st+1)) ) θ̂yt+1 = θ̂ y t − βte(st, bt) ( θ̂xt (st, bt)− r(st, at, bt)− γ ˆ̂ Vk−1(st+1))
) [xt+1(·|s), yt+1(·|s)] = [P(xt(·|s), ηθ̂xt+1(s, ·)), P(yt(·|s),−ηθ̂ y t+1(s, ·))]
Output xk = 1T ∑T
t=1 xt. Stage 2 for t = 0, 1, . . . , T − 1 do
Sample (st, at, bt, st+1, bt+1) with policy pair x̂k, ˆ̄yt, observe st, bt, r(st, at, bt), st+1, bt+1 ν̂t+1 = ν̂t − βνt e(st, bt) (ν̂t(st, bt)− r(st, at, bt)− γν̂t(st+1, bt+1)) ω̂t+1 = ω̂t − βωt e(st) (ω̂t(st)− r(st, at, bt)− γω̂t(st+1)) ȳt+1(·|s) = P(ȳt(·|s),−ην̂t+1(s, ·)) Output yk = ȳt̂, ˆ̂ Vk = ω̂t̂+1, where t̂ ∈ [T ] is selected uniformly at random and Vk = V xk,yk .

heading: G GREEDY EXPLORATION TO REMOVE ASSUMPTION 2
text: G.1 SINGLE LOOP NAC WITH A GAME ETIQUETTE AND ζ-GREEDY EXPLORATION
Remark G.1. In this section, we see how to avoid Assumption 2 as mentioned in the main text. Essentially the idea is similar to Khodadadian et al. (2021b) and (Lan, 2021, Remark 1) in the single agent case. We are going to use ζ greedy to avoid Assumption 2.
Let us define the modified policies with greedy exploration
x̂t(a|s) = (1− ζ)xt(a|s) + ζ
|A| , ŷt(b|s) = (1− ζ)yt(b|s) +
ζ
|B| .
Now we are going to sample with the x̂t, ŷt and the algorithm will read as Algorithm 8.
G.1.1 STAGE 1 OF SINGLE LOOP NAC WITH A GAME ETIQUETTE AND ζ-GREEDY EXPLORATION (SEE ALGORITHM 8)
Let us recall the notation and introduce more notations. At iteration k, we solve Qs(a, b) = Q(s, a, b) = r(s, a, b) + γ ∑ s′ P (s′|s, a, b)V xk−1,yk−1(s′).
The problem is to find xout, yout such that
Emax xs,ys xsoutQ sys − xsQsysout.
Now we define Q̂s(a, b) = Q̂(s, a, b) = r(s, a, b) + γ ∑ s′ P (s′|s, a, b)V x̂k−1,ŷk−1(s′),
as we sample with greedy policies, at the stage 2 we will learn V x̂k−1,ŷk−1 . So we will have the oracle ˆ̂Vk−1 such that ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥ is small. In this step, with the abovementioned oracle, we expect to learn
θ̂x⋆,t(s, a) = Eb∼ŷst Q̂ s(a, b), θ̂y⋆,t(s, b) = Ea∼x̂st Q̂ s(a, b).
Let us continue with x-player and drop the superscript,
θ̂⋆,t(s, a) = Eb∼ŷt(·|s)Q̂ s(a, b) = ∑ b ŷst Q̂ s(a, b)
= ∑ b ŷt(b|s)r(s, a, b) + γ ∑ b,s′ ŷt(b|s)P (s′|s, a, b)V x̂k−1,ŷk−1(s′).
Therefore the operator is
F̂t(θ̂t)(s, a) = ρ x̂t,ŷt(s)x̂t(a|s) ( θ̂t(s, a)− ∑ b ŷt(b|s)r(s, a, b)
− γ ∑ s′,b ŷt(b|s)P (s′|s, a, b)V x̂k−1,ŷk−1(s) ) . (49)
As x̂t(·|s) ≥ ζ|A| and ŷt(·|s) ≥ ζ |B| by definition, we have that F̂t is strongly monotone with ρ ζ |A| where ρ is the lower bound given in Assumption 1, which holds when the induced Markov chain is aperiodic and irreducible. Let us call this λ̂θmin = ρ ζ |A| .
We state the main result which follows by the results we will prove afterwards. Theorem G.2. Let Assumption 1 hold. By combining Lemma G.11, Lemma G.4 and their corresponding corollaries, we can show Õ(ϵ−7) sample complexity for Algorithm 8.
Proof. Insert Corollary G.6 and lemma G.11 into (14) to get the result.
Remark G.3. In single agent setting, Khodadadian et al. (2021b) obtains Õ(ϵ−6) with greedy exploration, to avoid Assumption 2. Our estimate is an ϵ factor away from this rate.
Below, we analyze the actor in the stage 1 of Algorithm 8. Lemma G.4. Let Assumption 1 hold and ηt = 1(t+7)6/7 , ζ = 1 T 1/7
. Then, for the stage 1 of Algorithm 8
Emax 1
T T∑ t=1 ⟨Eb∼ystQ(s, ·, b), x s t − xs⟩ ≤ log |A| Tη1 + log |A| TηT + 2 1 T T∑ t=1 E∥θ̂st+1 − θ̂s⋆,t∥∞
+ 4ξ|B| (1− γ) + 8γξ(|A| ∨ |B|) (1− γ)2 +
∑T t=1 ηt
2T (1− γ)2 .
Corollary G.5. By using ηt, ζ, we get the bound
O
( |A| ∨ |B|
(1− γ)2T 1/7 +
1
T 6/7 +
1
T T∑ t=1 ∥θ̂t+1 − θ̂⋆,t∥∞
) .
Corollary G.6. We can plug in the bound of E∥θ̂t+1− θ̂⋆,t∥2 (see Corollary G.8 ) and use the same bound for the other player to get
Emax xs,ys xoutQ sys−xsQsyout ≤ Õ
( |A| ∨ |B|
(1− γ)2T 1/7 +
√ |S||A|
T 1.5/7 + |S||A| T 2/7(1− γ)2 + 1 T 1/7(1− γ)
) +
O( √ |S||A|T 1/7)E∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥∞. (50)
Plugging in the bound for the final term from Lemma G.10
Emax xs,ys xoutQ sys−xsQsyout ≤ Õ
( |A| ∨ |B|
(1− γ)2T 1/7 +
√ |S||A|
T 1.5/7 + |S||A| T 2/7(1− γ)2 + 1 T 1/7(1− γ)
) +
O
( |S| √ |A|
(1− γ)1.5ρT 1/7
) , (51)
which gives the O(ϵ−7) complexity for stage 1.
Proof of Lemma G.4. Let us denote xst = xt(·|s) and similarly for variables y, x̂t, ŷt, θ. Let us recall (24) with our new notations
xsoutQ sys − xsQsysout =
1
T T∑ t=1 ⟨Ea∼xstQ(s, a, ·), y s⟩ − 1 T T∑ t=1 ⟨Eb∼ystQ(s, ·, b), x s⟩
= 1
T T∑ t=1 [ ⟨Ea∼xstQ(s, a, ·), y s − yst ⟩ − ⟨Eb∼ystQ(s, ·, b), x s − xst ⟩ ] . (52)
We have to convert this to the game when the matrix is Q̂
xsoutQ sys − xsQsysout =
1
T T∑ t=1 [ ⟨Ea∼xst Q̂ s(a, ·), ys − yst ⟩ − ⟨Eb∼yst Q̂ s(·, b), xs − xst ⟩ ] + 1
T T∑ t=1 ⟨Ea∼xst [Q s(a, ·)− Q̂s(a, ·)], ys − yst ⟩ − ⟨Eb∼yst [Q s(·, b)−Q̂s(a, ·)], xs − xst ⟩.
For the error terms note
⟨Ea∼xst [Q s(a, ·)− Q̂s(a, ·)], ys − yst ⟩ ≤ 2∥Ea∼xst [Q s(a, ·)− Q̂s(a, ·)]∥∞ ≤ 2∥Qs − Q̂s∥∞ ≤ 2γmax
a,b | ∑ s′ P (s′|s, a, b)(V xk−1,yk−1(s′)− V x̂k−1,ŷk−1(s′))|
≤ 2γ∥V xk−1,yk−1 − V x̂k−1,ŷk−1∥∞
≤ 4γζ(|A| ∨ |B|) (1− γ)2 , (53)
where the last step is due to the Lipschitzness of the value function due to performance difference lemma and that the policies x̂k−1, ŷk−1 and xk−1, yk−1 differ at most by ζ.
With the similar estimation for the other error term, we have
xsoutQ sys − xsQsysout =
1
T T∑ t=1 [ ⟨Ea∼xst Q̂ s(a, ·), ys − yst ⟩ − ⟨Eb∼yst Q̂ s(·, b), xs − xst ⟩ ] +
8ζ(|A| ∨ |B|) (1− γ)2 . (54)
Let us denote θs⋆,t = Eb∼yst Q̂
s(·, b). (55) Note that this notation is not consistent with previous sections. Here by θ⋆,t we mean the quantity we need to upper bound (54).
By the update rule of xt, for any xs
D(xs, xst ) ≤ D(xs, xst+1)−D(xst+1, xst ) + ηt⟨θ̂st+1, xs − xst+1⟩.
Let us estimate the inner product
ηt⟨θ̂st+1, xs − xst+1⟩ = ηt⟨θ̂st+1, xs − xst ⟩+ ηt⟨θ̂st+1, xst − xst+1⟩ = ηt⟨θs⋆,t, xs − xst ⟩+ ηt⟨θ̂st+1 − θs⋆,t, xs − xst ⟩+ ηt⟨θ̂st+1, xst − xst+1⟩
As we will be actually learning θ̂s⋆,t, we will further manipulate the inner product
ηt⟨θ̂st+1, xs − xst+1⟩ = ηt⟨θs⋆,t, xs − xst ⟩+ ηt⟨θ̂st+1 − θ̂s⋆,t, xs − xst ⟩+ ηt⟨θ̂s⋆,t − θs⋆,t, xs − xst ⟩
+ ηt⟨θ̂st+1, xst − xst+1⟩.
Let us estimate the third inner product on RHS
ηt⟨θ̂s⋆,t − θs⋆,t, xs − xst ⟩ ≤ 2ηt∥θ̂s⋆,t − θs⋆,t∥∞ = 2ηt max a | ∑ b (yt(b|s)− ŷt(b|s))Q̂s(a, b)|
≤ 4ηt 1− γ ∑ b |yt(b|s)− ŷt(b|s)|
= 4ηt 1− γ ∑ b |ζ (1/|B| − yt(b|s)) | ≤ 4ηt|B|ζ 1− γ
(56)
We use this estimation and Cauchy-Schwarz and Young’s inequalities to derive
ηt⟨θ̂st+1, xs − xst+1⟩ ≤ ηt⟨θs⋆,t, xs − xst ⟩+ 2ηt∥θ̂st+1 − θ̂s⋆,t∥∞ + 4ηt|B|ζ 1− γ
+ η2t 2 ∥θ̂t+1∥2∞ + 1 2 ∥xst − xst+1∥21.
We use this estimate in the main inequality with strong convexity of Bregman distance to get
ηt⟨θs⋆,t, xst − xs⟩+D(xs, xst ) ≤ D(xs, xst+1) + 2ηt∥θ̂st+1 − θ̂s⋆,t∥∞ + 4ηtζ|B| 1− γ + η2t 2(1− γ)2 .
We divide both sides by ηt to get
⟨θs⋆,t, xst − xs⟩ + 1
ηt D(xs, xst ) ≤
1 ηt D(xs, xst+1) + 2∥θ̂st+1 − θ̂s⋆,t∥∞ + 4ζ|B| 1− γ + ηt 2(1− γ)2 .
We sum this inequality and use (55) to get
1
T T∑ t=1 ⟨Eb∼yst Q̂ s(·, b), xst − xs⟩ ≤ log |A| Tη1 + log |A| TηT + 2 1 T t∑ t=1 ∥θ̂st+1 − θ̂s⋆,t∥∞
+ 4ζ|B| (1− γ) +
∑T t=1 ηt
2T (1− γ)2 .
We next analyze the critic in stage 1 of Algorithm 8.
Lemma G.7. Let Assumption 1 hold and ηt = 1(t+7)6/7 , ζ = 1 T 1/7 , βt = 2(t+7)4/7λ̂θmin . Then, for the critic of stage 1 of Algorithm 8
1
T T∑ t=1 E∥θ̂t − θ̂⋆,t−1∥22 ≤ O ( |S||A| T 3/7 ) +O ( |S|2|A|2 T 4/7(1− γ)4 ) +O ( 1 T 4/7(λ̂θmin) 2(1− γ)2 )
+ 8|S||A| (λ̂θmin) 2 ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞. (57)
Corollary G.8. Recall that ζ = 1 T 1/7 and λ̂θmin = ρζ/|A|,
1
T T∑ t=1 E∥θ̂t − θ̂⋆,t−1∥22 ≤ O ( |S||A| T 3/7 ) +O ( |S|2|A|2 T 4/7(1− γ)4 ) +O ( 1 T 2/7(1− γ)2 ) + 8|S||A|T 2/7∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞. (58)
Proof of Lemma G.7. As we are sampling with x̂t, ŷt and learning θ̂⋆,t(s, a) = Eb∼ŷst Q̂ s(a, b), we have that (see (49)) F̂t(θ̂⋆,t) = 0.
We also denote F̃ (θ̂t, ξt) = e(st, at)(θ̂t(st, at)− r(st, at, bt)− γ ˆ̂Vk−1),
where st, at, bt, st+1 are sampled according to x̂t, ŷt.
Let us derive
∥θ̂t+1 − θ̂⋆,t∥22 = ∥θ̂t − θ̂⋆,t∥22 − 2βt⟨F̃ (θ̂t, ξt), θ̂t − θ̂⋆,t⟩+ β2t ∥F̃ (θ̂t, ξt)∥22.
Now, by i.i.d. sampling st ∼ ρx̂t,ŷt , we have Eξt F̃t(θ̂t, ξt) = F̂t(θ̂t)+γPx̂t,ŷt( ˆ̂ Vk−1−V x̂k−1,ŷk−1) as in (18). We have by strong monotonicity and F̂t(θ̂⋆,t) = 0,
2βtEξt⟨F̃ (θ̂t, ξt), θ̂t − θ̂⋆,t⟩ = 2βt⟨F̂ (θ̂t), θ̂t − θ̂⋆,t⟩ = 2βt⟨F̂ (θ̂t)− F̂t(θ̂⋆,t), θ̂t − θ̂⋆,t⟩ ≥ 2βtλ̂θmin∥θ̂t − θ⋆,t∥22.
The recursion becomes Eξt∥θ̂t+1 − θ̂⋆,t∥22 ≤ ( 1− 2βtλ̂θmin ) ∥θ̂t − θ̂⋆,t∥22
− 2γβt⟨Px̂t,ŷt( ˆ̂ Vk−1 − V x̂k−1,ŷk−1), θt − θ⋆,t⟩+ β2tEξt∥F̃ (θ̂t, ξt)∥22.
By Cauchy-Schwarz and Young’s inequalities for the inner product
−2γβt⟨Px̂t,ŷt( ˆ̂ Vk−1 − V x̂k−1,ŷk−1), θ̂t − θ̂⋆,t⟩ ≤ 2γβt∥Px̂t,ŷt( ˆ̂ Vk−1 − V x̂k−1,ŷk−1)∥2∥θ̂t − θ̂⋆,t∥2
≤ βtλ̂ θ min
2 ∥θ̂t − θ̂⋆,t∥22 + βt8γ 2|S||A| λ̂θmin ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞.
The recursion then becomes Eξt∥θ̂t+1 − θ̂⋆,t∥22 ≤ ( 1− 3βtλ̂θmin/2 ) ∥θ̂t − θ̂⋆,t∥22
+ βt8γ 2|S||A| λ̂θmin ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞ + β2tEξt∥F̃ (θ̂t, ξt)∥22.
By Young’s inequality,
Eξt∥θ̂t+1 − θ̂⋆,t∥22 ≤ ( 1− βtλ̂θmin ) ∥θ̂t − θ̂⋆,t−1∥22 +
6
βtλ̂θmin ∥θ̂⋆,t − θ̂⋆,t−1∥22
+ βt8γ 2|S||A| λ̂θmin ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞ + β2tEξt∥F̃ (θ̂t, ξt)∥22.
Now we have to bound ∥θ̂⋆,t − θ̂⋆,t−1∥22: ∥θ̂⋆,t − θ̂⋆,t−1∥2 ≤ √ |S||A|∥θ̂⋆,t − θ̂⋆,t−1∥∞
= √ |S||A|max
a,s |Eb∼ŷst Q̂ s(a, b)− Eb∼ŷst−1Q̂ s(a, b)| ≤ 2 √ |S||A| 1− γ max s ∥ŷst − ŷst−1∥1
≤ 2 √ |S||A| 1− γ max s ∥yst − yst−1∥1,
where we used ŷt = (1−ζ)yt+ζ/|B|. To show that maxs ∥yst −yst−1∥1 is small, we use Lemma B.5 and Lemma B.1 and have the final bound for this quantity
∥θ̂⋆,t − θ̂⋆,t−1∥22 ≤ 4 |S|2|A|2
(1− γ)4 η2t .
By also bounding ∥F̃ (θ̂t, ξt)∥22 by Lemma B.1 and taking total expectation, the main recursion becomes
E∥θ̂t+1 − θ̂⋆,t∥22 ≤ (1− βtλ̂θmin)E∥θ̂⋆,t − θ̂⋆,t−1∥22 + 24|S|2|A|2η2t βtλ̂θmin(1− γ)4 + 2β2t (1− γ)2
+ 8βt|S||A| λ̂θmin E∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞.
This inequality gives
1
T T∑ t=1 E∥θ̂t − θ̂⋆,t−1∥22 ≤ 1 T T∑ t=1 1 βtλ̂θmin ( ∥θ̂t − θ⋆,t−1∥22 − ∥θ̂t+1 − θ⋆,t∥22 ) + 1
T T∑ t=1 24|S|2|A|2η2t β2t (λ̂ θ min) 2(1− γ)4 + 1 T T∑ t=1
2βt
λ̂θmin(1− γ)2 + 8|S||A| (λ̂θmin) 2 ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞. (59)
Recall that ηt = 1(t+7)6/7 and βt = 2 (t+7)4/7λ̂θmin . For the summations, we have
∑T t=1 η 2 t /β 2 t =
O(T 3/7(λ̂θmin)2)), ∑T
t=1 βt = O(T 3/7/λ̂θmin). By using βt+1 ≤ βt, and denoting for simplicity at = ∥θt − θ⋆,t−1∥22 so 0 ≤ at ≤ |S||A| (1−γ)2 simple estimation gives T∑ t=1 1 βt ( ∥θ̂t − θ⋆,t−1∥22 − ∥θ̂t+1 − θ⋆,t∥22 ) = T∑ t=1 1 βt (at − at+1)
= T∑ t=1 [ 1 βt at − 1 βt+1 at+1 + ( 1 βt+1 − 1 βt ) at+1 ]
≤ T∑
t=1
( 1
βt at −
1
βt+1 at+1 + |S||A| (1− γ)2 ∣∣∣∣ 1βt+1 − 1βt ∣∣∣∣)
= 1
β1 a1 −
1
bT+1 aT+1 + |S||A| (1− γ)2 T∑ t=1 ( 1 βt+1 − 1 βt )
≤ 1 β1 a1 + |S||A| (1− γ)2βT+1 = O
( |S||A|T 4/7λ̂θmin
(1− γ)2
)
Plugging these estimations into (59)
1
T T∑ t=1 E∥θ̂t − θ̂⋆,t−1∥22 ≤ O ( |S||A| T 3/7 ) +O ( |S|2|A|2 T 4/7(1− γ)4 ) +O ( 1 T 4/7(λ̂θmin) 2(1− γ)2 )
+ 8|S||A| (λ̂θmin) 2 ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞. (60)
G.1.2 STAGE 2 OF SINGLE LOOP NAC WITH A GAME ETIQUETTE AND ζ-GREEDY EXPLORATION (SEE ALGORITHM 8)
We are now going to estimate ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞. First, we need the following lemma for numerical sequences from Mokhtari et al. (2020). Lemma G.9. (Lemma 19 in Mokhtari et al. (2020)) Let b ≥ 0, c > 1. Let ϕt be a sequence of real numbers satisfying
ϕt ≤ ( 1− c
(t+ t0)α
) ϕt−1 +
b
(t+ t0)2α , (61)
for some α ∈ [0, 1] and t0 ≥ 0. Then ϕt converges to zero with the rate
ϕt ≤ max(ϕ0(t0 + 1) α, b/(c− 1)) (t+ t0 + 1)α .
For the stage 2, let ηt = 1(t+7)6/7 and βt = 3 2(t+7)4/7ρ and let us analyze the critic for ˆ̂Vk−1.
Lemma G.10. Let Assumption1 hold. Let ηt = 1(t+7)6/7 and βt = 3 2ρ(t+7)4/7 and recall ω̂t̂+1 =
ˆ̂ Vk
and ω̂⋆,t = V x̂k, ˆ̄yt and that we take as output yk = ȳt̂ in Algorithm 8
E∥ ˆ̂Vk − V x̂k,ˆ̄yk∥2 = 1
T T∑ t=1 E∥ω̂t+1 − ω̂⋆,t∥2 ≤ O
( |S|
(1− γ)3ρ2T 4/7
) . (62)
Proof. Let us develop similar recursion to previous lemma
∥ω̂t+1 − ω̂⋆,t∥22 = ∥ω̂t − ω̂⋆,t∥22 − 2βt⟨F̃ωt (ω̂t, ξt), ω̂t − ω̂⋆,t⟩+ β2t ∥F̃ωt (ω̂t, ξt)∥22.
By taking expectation, using that st ∼ ρx̂k,ˆ̄yt , we have Eξt F̃ωt (ω̂t, ξt) = F̂ωt (ω̂t) and F̂t(ωt) is strongly monotone with ρ as it only requires Assumption 1. We also have F̂ωt (ω̂⋆,t) = 0. The main recursion becomes
Eξt∥ω̂t+1 − ω̂⋆,t∥22 ≤ ( 1− 2βtρ ) ∥ω̂t − ω̂⋆,t∥22 + β2tEξt∥F̃ωt (ω̂t, ξt)∥22.
By Young’s inequality for α > 0
(1−2βtρ)∥ω̂t− ω̂⋆,t∥22 ≤ (1−2βtρ)(1+α)∥ω̂t− ω̂⋆,t−1∥22+(1−2βtρ)(1+1/α)∥ω̂⋆,t−1− ω̂⋆,t∥22.
Let us set α such that (1− 2βtρ)(1 +α) = (1− βtρ), which gives the choice α = βtρ
1−2βtρ , with the
requirement 1 − 2βtρ > 0. Recall that since βt = 32ρ(t+7)4/7 , we have 2βtρ < 1 and t ≥ 0. Note also that (1− 2βtρ)(1 + 1/α) ≤ 2βtρ with out choice of α.
The recursion now becomes E∥ω̂t+1 − ω̂⋆,t∥22 ≤ ( 1− βtρ ) E∥ω̂t − ω̂⋆,t−1∥22 + 2
βtρ E∥ω̂⋆,t−1 − ω̂⋆,t∥22 + β2tE∥F̃ωt (ω̂t, ξt)∥22.
Let us estimate the second term on RHS
∥ω̂⋆,t−1 − ω̂⋆,t∥2 ≤ |S|∥ω̂⋆,t−1 − ω̂⋆,t∥∞ = |S|∥V x̂k,ˆ̄yt − V x̂k,ˆ̄yt−1∥∞
≤ 4|S| (1− γ)2 max s ∥ˆ̄yst − ˆ̄yst−1∥∞,
where the last inequality is by Lemma B.3. To further upper bound this quantity, use the update rule of ˆ̄yt, Lemma B.5 and Lemma B.1 to get for all s ∥ȳst − ȳst−1∥1 ≤ ηt 1−γ . We also use that ˆ̄yst (b) = (1− ζ)ȳst (b) + ζ/|B|
∥ω̂⋆,t−1 − ω̂⋆,t∥2 ≤ 2|S|ηt (1− γ)3
Therefore, in the main inequality we have (after also bounding the last term by Lemma B.1)
E∥ω̂t+1 − ω̂⋆,t∥22 ≤ ( 1− βtρ ) E∥ω̂t − ω̂⋆,t−1∥22 +
4|S|η2t βtρ(1− γ)3 + 2β2t (1− γ)2 . (63)
Note that by the definitions of βt, ηt, we have
βtρ = 3
2(t+ 7)4/7 , η2t βt = 2ρ 3(t+ 7)8/7 , β2t =
9
4ρ2(t+ 7)8/7 .
Therefore, we have E∥ω̂t+1−ω̂⋆,t∥22 ≤ ( 1− 3
2(t+ 7)4/7
) E∥ω̂t−ω̂⋆,t−1∥22+
8|S| 3(1− γ)3(t+ 7)4/7 + 18 4ρ2(1− γ)2(t+ 7)8/7 .
Now, we use Lemma G.9 with
ϕt = E∥ω̂t+1 − ω̂⋆,t∥22
b = max
( 8|S|
3(1− γ)3 ,
18
4ρ2(1− γ)2
) ≥ 0
c = 3
2 > 1
t0 = 7
α = 4/7,
gives
E∥ω̂t+1 − ω̂⋆,t∥22 ≤ O
( |S|
(1− γ)3ρ2(t+ 7)4/7 ) Sum the inequality to get
1
T T∑ t=1 E∥ω̂t+1 − ω̂⋆,t∥22 ≤ 1 T T∑ t=1 O
( |S|
(1− γ)3ρ2(t+ 7)4/7
)
≤ 1 T T∑ t=1 O ( |S|T 3/7 (1− γ)3ρ2 )
≤ O
( |S|
(1− γ)3ρ2T 4/7
)
The accuracy for the stage 2 will follow a similar proof to single agent settings. We would like to bound
V xk,y ∗ k − V xk,ȳt ,
by sampling x̂sk(a) = (1− ζ)xsk(a) + ζ/|A| and ˆ̄yst (b) = (1− ζ)ȳst (b) + ζ/|B|. Let us define the oracles and the operators
ν̂⋆,t(s, b) = Ea∼x̂skQ x̂k,ˆ̄yt(s, a, b).
F̃t(ν̂t, ξt)(s, b) = ρ x̂k,ˆ̄yt(s)ˆ̄yt(b|s)e(s, b) (ν̂t(s, b)− r(s, a, b)− γν̂t(s′, b′)) ,
where s ∼ ρx̂k,ˆ̄yt , a ∼ x̂sk, b ∼ ˆ̄yst , s′ ∼ P (·|s, a, b), b′ ∼ ˆ̄ys ′ t , and
F̂t(ν̂t)(s, b) = ρ x̂k,ˆ̄yt(s)ˆ̄yt(b|s) ( ν̂t(s, b)− ∑ a x̂k(a|s)r(s, a, b)
− γ ∑
s′,a,b′
P (s′|s, a, b)x̂k(a|s)ˆ̄yt(b′|s′)ν̂t(s′, b′) ) ,
and therefore F̂t(ν̂⋆,t) = 0 and F̂t is strongly monotone with ρζ/|B| = λ̂νmin. Lemma G.11. Let Assumption 1 hold. Let us set ηt = 1(t+7)6/7 , and ζ = 1 T 1/7
. Then for the actor of the stage 2 in Algorithm 8,
E 1
T T∑ t=1 V xk,y ∗ k(s0)− V xk,ȳt(s0) ≤ Õ ( 1 (1− γ)T 1/7 ) +O ( 1 1− γ E∥ν̂t+1 − ν̂⋆,t∥∞ ) +O ( |B|ζ
(1− γ)2
) +O ( 1
T 6/7(1− γ)3 ) Corollary G.12. By using Lemma G.13, we get the overall rate O(1/T 1/7).
Proof. By the update rule of the algorithm,
D(ys, ȳst+1) ≤ D(ys, ȳst )−D(ȳst+1, ȳst )− ηt⟨ν̂st+1, ys − ȳst+1⟩ = D(ys, ȳst )−D(ȳst+1, ȳst )− ηt⟨ν̂s⋆,t, ys − ȳst+1⟩ − ηt⟨ν̂st+1 − ν̂s⋆,t, ys − ȳst+1⟩.
We now estimate the inner products by Cauchy-Schwarz, Young’s inequalities and Lemma B.1
−ηt⟨ν̂s⋆,t, ys − ȳst+1⟩ = −ηt⟨ν̂s⋆,t, ys − ȳst ⟩ − ηt⟨ν̂s⋆,t, ȳst − ȳst+1⟩
≤ −ηt⟨ν̂s⋆,t, ys − ȳst ⟩+ η2t 2 ∥ν̂s⋆,t∥2∞ + 1 2 ∥ȳst − ȳst+1∥21 = −ηt⟨ν̂s⋆,t, ys − ˆ̄yst ⟩ − ηt⟨ν̂s⋆,t, ˆ̄yst − ȳst ⟩+ η2t 2 ∥ν̂s⋆,t∥2∞ + 1 2 ∥ȳst − ȳst+1∥21
≤ −ηt⟨ν̂s⋆,t, ys − ˆ̄yst ⟩+ ηt
1− γ ∥ˆ̄yst − ȳst ∥1 + η2t 2(1− γ)2 + 1 2 ∥ȳst − ȳst+1∥21
Since ˆ̄yst (b) = (1 − ζ)ȳst (b) + ζ/|B|, ∥ˆ̄yst − ȳst ∥1 ≤ O(|B|ζ). We join everyting in the main inequality to get
ηt⟨ν⋆,t, ys − ˆ̄yst ⟩+D(ys, ȳst+1) ≤ D(ys, ȳst ) + 2ηt∥ν̂st+1 − ν̂s⋆,t∥∞ + ηt 1− γ O(|B|ζ) + η
2 t
2(1− γ)2 .
We recall the definition of ν̂⋆,t(s, b) = Ea∼x̂skQ x̂k,ˆ̄yt(s, a, b). By the performance difference lemma
V x̂k,y ∗ k(s0)− V x̂k,ˆ̄yt(s0) =
1
1− γ E s∼d x̂k,y ∗ k
s0
⟨ν̂s⋆,t, y ∗,s k − ˆ̄y s t ⟩,
where y∗k is the best response to xk. Note that by Lemma B.3, V xk,y ∗ k(s0)− V x̂k,y ∗ k(s0) ≤ 2|B|ζ(1−γ)2 .
Therefore, we have
E 1
T T∑ t=1 V xk,y ∗ k(s0)− V x̂k,ˆ̄yt(s0) ≤ Õ ( 1 (1− γ)TηT ) +O ( 1 1− γ E∥ν̂st+1 − ν̂s⋆,t∥∞ ) +O ( |B|ζ
(1− γ)2
) +O ( 1
T 6/7(1− γ)3 ) Finally due to Lemma B.3, V x̂k,ˆ̄yt(s0)−V xk,ȳt(s0) ≤ O ( ζ(|A|∨|B|) (1−γ)2 ) , therefore the final inequality is
E 1
T T∑ t=1 V xk,y ∗ k(s0)− V xk,ȳt(s0) ≤ Õ ( 1 (1− γ)T 1/7 ) +O ( 1 1− γ E∥ν̂st+1 − ν̂s⋆,t∥∞ ) +O ( |B|ζ
(1− γ)2
) +O ( 1
T 6/7(1− γ)3
)
We finally analyze the critic for stage 2, Lemma G.13. Let Assumption1 hold. For the critic in stage 2 in Algorithm 8, let βt = 2λ̂νmin(t+7)4/7 and recall λ̂νmin = ρζ/|B|
1
T T∑ t=1 E∥ν̂t − ν̂⋆,t−1∥22 ≤ Õ ( 1 T 3/7 ) +O ( |S||B| (1− γ)3T 4/7 ) +O ( 1 (1− γ)2T 2/7 ) (64)
Proof. By the same steps in Lemma G.10, we can get a similar inequality to (63) E∥ν̂t+1 − ν̂⋆,t∥22 ≤ ( 1− βtλ̂νmin ) E∥ν̂t − ν̂⋆,t−1∥22 +
4|B||S|η2t βtλ̂νmin(1− γ)3 + 2β2t (1− γ)2 . (65)
Equivalently,
1
T T∑ t=1 E∥ν̂t − ν̂⋆,t−1∥22 ≤ Õ ( 1 T 3/7 ) + 1 T T∑ t=1 4|B||S|η2t β2t (λ̂ ν min) 2(1− γ)3 +
2βt
λ̂νmin(1− γ)2 . (66)
We can estimate other terms
1
T T∑ t=1 E∥ν̂t − ν̂⋆,t−1∥22 ≤ Õ ( 1 T 3/7 ) +O ( |S||B| (1− γ)3T 4/7 ) +O ( 1 (1− γ)2T 2/7 ) (67)
G.2 REFLECTED NAC WITH A GAME ETIQUETTE AND ζ-GREEDY EXPLORATION
In this section, we give a version of reflected NAC without Assumption2, in a similar way described in (Lan, 2021, Remark 1). This algorithm will be Algorithm 1 with nonzero ζ. Since this result is not derived in Lan (2021) for single agent MDP, we first derive it with single agent MDP.
G.2.1 SINGLE AGENT RESULT WITH ζ-GREEDY EXPLORATION
The algorithm will be Algorithm 9.
Algorithm 9 Single player case
Require: V̂0 such that ∥V̂0 − V x0,y0∥2∞ ≤ ϵ for t = 0, 1, . . . , T − 1 do
Set ŷt(b|s) = (1− ζ)yt(b|s) + ζ/|B| ν̂t+1 = Policy-Eval(ŷt, N) yt+1(·|s) = P(yt(·|s),−ην̂t+1(s, ·))
Theorem G.14. Let Assumption 1 hold. For η > 0, the iterates of Algorithm 9 satisfies
1
T T∑ t=1 [V ⋆(s0)− E[V yt(s0)]] ≤ 1 η(1− γ)T E s∼dy ⋆ s0 [ D(y⋆,s, ys1) ] + 1
T (1− γ) EE s∼dy ⋆ s0 [V yT+1(s)− V y1(s)] + η (1− γ)2 1 T T∑ t=1 E∥ν̂⋆,t − ν̂t+1∥2∞
+ 2 1− γ 1 T T∑ t=1 E∥E[ν̂t+1|yt]− ν̂⋆,t∥∞ + 4η|B|2ζ2 (1− γ)6 + 4|B|ζ (1− γ)3 (68)
Proof. Recall the definitions
ν⋆,t = Q yt , ν̂⋆,t = Q ŷt .
Recall that the update rule of yt+1 implies D(ys, yst+1) ≤ D(ys, yst )−D(yst+1, yst )− η⟨ν̂st+1, ys − yst+1⟩ and by plugging in y = yt, we get
D(yst , y s t+1) +D(y s t+1, y s t ) ≤ −η⟨ν̂st+1, yst − yst+1⟩.
By (8),
0 ≤ −⟨ν̂st+1, yst − yst+1⟩ − 1
η ∥yst+1 − yst ∥21 ≤ −⟨ν̂st+1, yst − yst+1⟩ −
1
2η ∥yst+1 − yst ∥21. (69)
By performance difference lemma and Young’s inequality
V yt+1(s0)− V yt(s0) = 1
1− γ E s∼d yt+1 s0 ⟨Qyt,s, yst+1 − yst ⟩
= 1
1− γ E s∼d yt+1 s0 ⟨νs⋆,t, yst+1 − yst ⟩
= 1
1− γ E s∼d yt+1 s0
[ ⟨ν̂st+1, yst+1 − yst ⟩+ ⟨νs⋆,t − ν̂st+1, yst+1 − yst ⟩ ] ≥ 1
1− γ E s∼d yt+1 s0
[ ⟨ν̂st+1, yst+1 − yst ⟩ − η
2 ∥νs⋆,t − ν̂st+1∥2∞ −
1
2η ∥yst+1 − yst ∥21
] .
Therefore, we get by using (69) and 1− γ ≤ dyt+1s0 (s0) ≤ 1
⟨ν̂st+1, yst+1 − yst ⟩ ≤ V yt+1(s)− V yt(s) + 1
2η ∥yst+1 − yst ∥21 +
η
2(1− γ) ∥ν⋆,t − ν̂t+1∥2∞. (70)
We use again the definition of yt+1
D(ys, yst+1) ≤ D(ys, yst )−D(yst+1, yst )− η⟨ν̂st+1, ys − yst+1⟩ = D(ys, yst )−D(yst+1, yst )− η⟨ν̂st+1, ys − yst ⟩ − η⟨ν̂st+1, yst − yst+1⟩. (71)
Let us use (70) and
−η⟨ν̂st+1, ys − yst ⟩ = −η⟨νs⋆,t, ys − yst ⟩ − η⟨ν̂st+1 − νs⋆,t, ys − yst ⟩
on (71) to get (along with (8))
η⟨νs⋆,t, ys − yst ⟩+D(ys, yst+1) ≤ D(ys, yst ) + η (V yt+1(s)− V yt(s))
+ η2
2(1− γ) ∥ν⋆,t − ν̂t+1∥2∞ − η⟨ν̂st+1 − νs⋆,t, ys − yst ⟩ (72)
Since by performance difference lemma, V ⋆(s0) − V yt(s0) = 11−γEs∼dy⋆s0 ⟨ν s ⋆,t+1, y ⋆,s − yst ⟩, we plug in y = y⋆ and take expectation in (72) w.r.t. dy ⋆
s0 ,
η(1− γ)(V ⋆(s0)− V yt(s0)) ≤ Es∼dy⋆s0
[ D(ys, yst )−D(ys, yst+1) ] + ηE s∼dy ⋆
s0
[V yt+1(s)− V yt(s)]
+ η2
2(1− γ) ∥ν⋆,t − ν̂t+1∥2∞ − Es∼dy⋆s0 [η⟨ν̂ s t+1 − νs⋆,t, ys − yst ]⟩
(73)
Next, we take expectation w.r.t. randomness in the algorithm and use tower property to get
η(1− γ)(V ⋆(s0)− E[V yt(s0)]) ≤ EEs∼dy⋆s0
[ D(y⋆,s, yst )−D(y⋆,s, yst+1) ] + ηEE
s∼dy ⋆
s0
[V yt+1(s)− V yt(s)] + η 2
2(1− γ) E∥ν⋆,t − ν̂t+1∥2∞
− EE s∼dy
⋆ s0
[η⟨E[ν̂st+1|yt]− νs⋆,t, ys − yst ]⟩. (74)
We also note that by Cauchy-Schwarz inequality −η⟨E[ν̂st+1|yt]− νs⋆,t, ys − yst ]⟩ ≤ 2∥E[v̂t+1|yt]− ν⋆,t∥∞. By triangle inequality and Young’s inequality
η2
2(1− γ) ∥ν⋆,t − ν̂t+1∥2∞ + 2η∥E[ν̂t+1|yt]− ν⋆,t∥∞ ≤
η2
1− γ ∥ν̂⋆,t − ν̂t+1∥2∞
+ η2
1− γ ∥ν̂⋆,t − ν⋆,t∥2∞ + 2η∥E[ν̂t+1|yt]− ν̂⋆,t∥∞ + 2η∥ν⋆,t − ν̂⋆,t∥∞
≤ η 2
1− γ ∥ν̂⋆,t − ν̂t+1∥2∞ +
4η2
(1− γ)5 (max s ∥ŷst − yst ∥1)2
+ 2η∥E[ν̂t+1|yt]− ν̂⋆,t∥∞ + 4η
(1− γ)2 max s ∥ŷst − yst ∥1,
where the last step used Lemma B.4 and definitions ν⋆,t = Qyt , ν̂⋆,t = Qŷt . We use the estimation as in (56), to get ∥ŷt − yt∥1 ≤ |B|ζ. With these estimations, (74) becomes
V ⋆(s0)− E[V yt(s0)] ≤ 1
η(1− γ) EE s∼dy ⋆ s0
[ D(y⋆,s, yst )−D(y⋆,s, yst+1) ] + 1
1− γ EE s∼dy ⋆ s0 [V yt+1(s)− V yt(s)]+ η (1− γ)2 E∥ν̂⋆,t− ν̂t+1∥2∞+ 2 1− γ E∥E[ν̂t+1|yt]− ν̂⋆,t∥∞
+ 4η|B|2ζ2
(1− γ)6 + 4|B|ζ (1− γ)3 (75)
We sum over t to conclude.
Note that we will learn ν̂⋆,t by sampling with ŷt. As in Appendix G.1.1, the strong monotonicity constant of the operator
F yt(ν)(s, b) = ρŷt(s)yt(b|s) ( ν(s, b)− r(s, b)− γ
∑ s′ P (s′|s, b)yt(b′|s′)ν(s′, b′)
)
is λ̂νmin = (1− γ)ρζ/(|B|) (see also Lan (2021)). Moreover, F yt(ν⋆,t) = 0.
Lemma G.15. Let Assumption 1 hold and βn = 2λ̂νmin(n+n0) stage 2 in Algorithm 9 satisfies
E∥ν̂N − ν̂⋆,t∥22 ≤ O
( |S||B|
(1− γ)2N2 +
1
N(1− γ)2(λ̂νmin)2
) ,
∥E[ν̂N |yt]− ν̂⋆,t∥22 ≤ O (
2|S||B| (1− γ)2N2
) .
Proof. We can use Lemma F.7 with ν = ν̂, λνmin = λ̂ ν min and F̃ (ν, ξ) = ν(s, b)−r(s, b)−γν(s′, b′) where s ∼ ρŷt , b ∼ ŷt(·|s), s′ ∼ P (·|s, b), b′ ∼ ŷt(·|s′) to get the result.
Corollary G.16. Let Assumption 1 hold. Let ζ = (1 − γ)3ϵ/|B|. The sample complexity of Algorithm 9 for obtaining globally optimal policy in single agent MDP is O(|B|4|S|(1−γ)−13ρ−2ϵ−4).
Proof.
1
T T∑ t=1 [V ⋆(s0)− E[V yt(s0)]] ≤ 1 η(1− γ)T E s∼dy ⋆ s0 [ D(y⋆,s, ys1) ] + 1
T (1− γ) EE s∼dy ⋆ s0 [V yT+1(s)− V y1(s)] + η (1− γ)2 1 T T∑ t=1 E∥ν̂⋆,t − ν̂t+1∥2∞
+ 2 1− γ 1 T T∑ t=1 E∥E[ν̂t+1|yt]− ν̂⋆,t∥∞ + 4η|B|2ζ2 (1− γ)6 + 4|B|ζ (1− γ)3 (76)
By using Lemma G.15 in the previous lemma with λ̂νmin = (1− γ)ρζ/|B| gives
1
T T∑ t=1 [V ⋆(s0)− E[V yt(s0)]] ≤ Õ (
1
T (1− γ)2
) + 4η|B|2ζ2
(1− γ)6 + 4|B|ζ (1− γ)3
+O
( η
(1− γ)2
( |S||B|
(1− γ)2N2 +
|B|2
N(1− γ)4ρ2ζ2
) + √ |S||B|
(1− γ)N
) . (77)
By picking η = (1−γ) and ζ = (1−γ)3ϵ/|B|, we get the complexity O(|B|4|S|(1−γ)−13ρ−2ϵ−4).
G.2.2 REFLECTED NAC WITH A GAME ETIQUETTE AND ζ-GREEDY EXPLORATION IN ALGORITHM 10
We first state the main result in the next corollary. As most of the results depend on previous sections, we will make heavy use of those estimations and provide a brief proof by highlighting the differences and extracting the error due to greedy exploration. Algorithm 1 is repeated here for convenience. Theorem 3.3. Let Assumption 1 hold. Use the parameter choices from Corollaries G.20 and G.21, use Remark C.1 and use the estimates in these corollaries with (14). Then, the complexity for Algorithm 10 is Õ(|S|4(|A| ∨ |B|)6(1− γ)−15ϵ−4ρ2).
Algorithm 10 Reflected NAC with a game etiquette and ζ-greedy exploration
Require: PKL defined in (1) in Section 1. Exploration parameter ζ ≥ 0 (equal to 0 if Assumption2 holds). Subroutine Policy-Eval (see Algorithm 2, Algorithm 3, Algorithm 4). Initial policies x0, y0, ȳ0 for k = 0, 1, . . . do
Stage 1 for t = 0, 1, . . . , T − 1 do
Define x̂k−1(a|s) = (1 − ζ)xk−1(a|s) + ζ|A| , ŷk−1(b|s) = (1 − ζ)yk−1(b|s) + ζ |B| and correspondingly for x̂k,t, ŷk,t. [ ˆ̂ V xk−1, ˆ̂ V yk−1] = [Policy-Eval(x̂k−1, ŷk−1, N, β ω n ), Policy-Eval(x̂k−1, ŷk−1, N, β ω n )]
[θ̂xt+1, θ̂ y t+1] = [Policy-Eval(x̂k,t, ŷk,t, N, V̂ x k−1, β θ n),Policy-Eval(x̂k,t, ŷk,t, N, V̂ y k−1, β θ n)] xsk,t+1(·) = PKL ( xsk,t(·), η ( 2θ̂xt+1(s, ·)− θ̂xt (s, ·) )) ysk,t+1(·) = PKL ( ysk,t(·),−η ( 2θ̂yt+1(s, ·)− θ̂ y t (s, ·)
)) Output xk = 1T ∑T t=1 xk,t. Stage 2 for t = 0, 1, . . . , T − 1 do x̂sk(a) = (1− ζ)xsk(a) + ζ |A| , ˆ̄y s k,t(b) = (1− ζ)ȳsk,t(b) + ζ |B|
ν̂t+1 = Policy-Eval(x̂k, ˆ̄yt, N, β = βνn) ȳsk,t+1(·) = PKL(ȳsk,t(·),−ην̂t+1(s, ·))
Output yk = ȳk,t̂, where t̂ ∈ [T ] is selected uniformly at random.
Theorem 3.3. Extended form Let Assumption 1 hold. Use the parameter choices from Corollaries G.20 and G.21, use Remark C.1 and use the estimates in these corollaries with (14). Then the suboptimality gap is bounded as follows:
EEs0∼µ[max y
V xk,y(s0)− V ⋆(s0)] ≤ Cµ,σk (1− γ) Õ {
1
T (1− γ)2
+ |S|2(|A| ∨ |B|)6
(1− γ)5ρ2ϵ2N + |S||B| (1− γ)3N2 + |B|2 N(1− γ)11ρ2ϵ2 +
√ |S||B|
(1− γ)N
} +O ( Cµ,σγ k
(1− γ) ) Then, the complexity for Algorithm 10 is Õ(|S|4(|A| ∨ |B|)6(1− γ)−15ϵ−4ρ2). Remark G.17. This result does not require Assumption 2, which makes our set of assumptions similar to Wei et al. (2021) which also used greedy exploration. Comparing with (Wei et al., 2021, Corollary 5), our result has the same ϵ−4 dependence, a better dependence on (1− γ). We note that even though our dependence with |A|∨|B| seems worse compared to (Wei et al., 2021, Corollary 5), the result in (Wei et al., 2021, Corollary 5) has dependence C−10 where C is the metric subregularity constant. This constant implicitly depends on dimensions of variables x, y, therefore it depends on |A|, |B|, |S|. More importantly, this result in Wei et al. (2021) does not cover NPG since it requires Euclidean projections on the simplex. As a result, the comparison with (Wei et al., 2021, Corollary 5) in terms of |A|, |B| is not possible. On the other hand, the result of (Wei et al., 2021, Corollary 4) without metric subregularity applies to NPG, and it can be compared with our result, in which case our sample complexity scales as ϵ−4 whereas (Wei et al., 2021, Corollary 4) as ϵ−8.
Stage 1 of Reflected NAC with a game etiquette and ζ-greedy exploration in Algorithm 10 We first recall the discussion in Appendix G.1.1 and include it here for easy reference. Let us recall the notation and introduce more notations. At iteration k, we solve
Qs(a, b) = Q(s, a, b) = r(s, a, b) + γ ∑ s′ P (s′|s, a, b)V xk−1,yk−1(s′).
The problem is to find xout, yout such that Emax
xs,ys xsoutQ sys − xsQsysout.
Now we define Q̂s(a, b) = Q̂(s, a, b) = r(s, a, b) + γ ∑ s′ P (s′|s, a, b)V x̂k−1,ŷk−1(s′),
as we sample with policies with greedy exploration, at stage 2 we will learn V x̂k−1,ŷk−1 . So we will have the oracle ˆ̂Vk−1 such that ∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥ is small. In this step, with the abovementioned oracle, we expect to learn
θ̂x⋆,t(s, a) = Eb∼ŷst Q̂ s(a, b), θ̂y⋆,t(s, b) = Ea∼x̂st Q̂ s(a, b).
Let us continue with x-player and drop the superscript,
θ̂⋆,t(s, a) = Eb∼ŷt(·|s)Q̂ s(a, b) = ∑ b ŷst Q̂ s(a, b)
= ∑ b ŷt(b|s)r(s, a, b) + γ ∑ b,s′ ŷt(b|s)P (s′|s, a, b)V x̂k−1,ŷk−1(s′).
Therefore the operator is
F̂t(θ̂t) = ρ x̂t,ŷt(s)x̂t(a|s) ( θ̂t(s, a)− ∑ b ŷt(b|s)r(s, a, b)
− γ ∑ s′,b ŷt(b|s)P (s′|s, a, b)V x̂k−1,ŷk−1(s) ) . (78)
As x̂t(·|s) ≥ ζ|A| and ŷt(·|s) ≥ ζ |B| , we have that F̂t is strongly monotone with ρ ζ |A| where ρ is the lower bound of the stationary state distribution. Let us call this λ̂θmin = ρ ζ |A| .
As in Lemma F.2, we introduce notation similar to Malitsky & Tam (2020), let us define Φ, which is slightly different this time.
Φst+1 = D(x s, xst+1) + η⟨θs⋆,t+1 − θ̂st+1, xs − xst+1⟩+
1 2 D(xst+1, x s t ). (79)
We also use the following error functions and recall the definitions
e1,t = η⟨θ̂t+1(·|s)− E[θ̂t+1(·|s)|xt], x(·|s)− xt(·|s)⟩ e2,t = η⟨θ̂yt+1(·|s)− E[θ̂ y t+1(·|s)|yt], yt(·|s)− y(·|s)⟩,
θ̂⋆,t(s, a) = Eb∼ŷtQ̂s(a, ·) θ⋆,t(s, a) = Eb∼ytQs(a, ·).
Lemma G.18. Let Assumption 1 hold. Let η = 1−γ8 . Denote xout = 1 T ∑T t=1 xt and yout = 1 T ∑T t=1 yt. For stage 1 in Algorithm 10
EEs∼σ [ max xs,ys xsoutQ sys − xsQsyout ] = O ( Φs0 − ΦsT ηT ) +O ( 1 T T∑ t=1 E∥E[θ̂t+1|xt]− θ̂⋆,t∥ )
+O
( η
T T∑ t=1
E∥θ̂t+1 − θ̂⋆,t∥2 + E∥θ̂t − θ̂⋆,t−1∥2 ) + 1
Tη EEs∼σ max z T∑ t=1 [e1,t + e2,t])
+ 4ζ(|A| ∨ |B|)
(1− γ)2 + 4ζ|B| 1− γ .
Remark G.19. The idea of this lemma is to extract the error due to greedy exploration and make the errors due to policy evaluation depending on the policies with greedy exploration. In particular, θ̂t+1 learns θ̂⋆,t, by sampling x̂t, ŷt. Therefore, we can utilize the results we derived earlier for policy evaluation steps.
Proof. We start from the quantity we would like to bound. Recall from (24)
xsoutQ sys − xsQsysout =
1
T T∑ t=1 ⟨Ea∼xstQ s(a, ·), ys⟩ − 1 T T∑ t=1 ⟨Eb∼ystQ s(·, b), xs⟩
= 1
T T∑ t=1 [ ⟨Ea∼xstQ s(a, ·), ys − yst ⟩ − ⟨Eb∼ystQ s(·, b), xs − xst ⟩ ] .
= 1
T T∑ t=1 [ ⟨θy⋆,t, ys − yst ⟩ − ⟨θx⋆,t, xs − xst ⟩ ] . (80)
We will drop the subscript of θ to denote θx for lighter notation and derive the part of x-player. The y-player case will be symmetrical.
By the definition of xt+1,
D(xs, xst+1) ≤ D(xs, xst )−D(xst+1, xst ) + η⟨2θ̂st+1 − θ̂st , xs − xst+1⟩. (81)
We manipulate the inner products as Lemma F.2
⟨2θ̂st+1 − θ̂st , xs − xst+1⟩ = ⟨θ̂st+1 − θs⋆,t+1, xs − xst+1⟩+ ⟨θ̂st+1 − θ̂st , xs − xst+1⟩+ ⟨θs⋆,t+1, xs − xst+1⟩
= ⟨θ̂st+1 − θs⋆,t+1, xs − xst+1⟩+ ⟨θ̂st+1 − θ̂st , xs − xst ⟩+ ⟨θ̂st+1 − θ̂st , xst − xst+1⟩ + ⟨θs⋆,t+1, xs − xst+1⟩
= ⟨θ̂st+1 − θs⋆,t+1, xs − xst+1⟩+ ⟨θs⋆,t − θ̂st , xs − xst ⟩+ ⟨θ̂st+1 − θs⋆,t, xs − xst ⟩
+ ⟨θ̂st+1 − θ̂st , xst − xst+1⟩+ ⟨θs⋆,t+1, xs − xst+1⟩.
Note that the first two terms will be used while forming Φst and Φ s t+1, final term will be what we bound for (80). The third and fourth terms are the error terms. We first analyze the third term
⟨θ̂st+1 − θs⋆,t, xs − xst ⟩ = ⟨E[θ̂st+1|xt]− θs⋆,t, xs − xst ⟩+ ⟨θ̂st+1 − E[θ̂st+1|xt], xs − xst ⟩
= ⟨E[θ̂st+1|xt]− θs⋆,t, xs − xst ⟩+ e1,t ≤ 2∥E[θ̂t+1|xt]− θ⋆,t∥∞ + e1,t.
Next, by Cauchy-Schwarz and Young’s inequalities
⟨θ̂st+1 − θ̂st , xst − xst+1⟩ ≤ η∥θ̂t+1 − θ̂t∥2∞ + 1
4η ∥xst − xst+1∥21
≤ 2η∥θ̂t+1 − θ̂⋆,t∥2∞ + 4η∥θ̂⋆,t − θ̂⋆,t−1∥2∞ + 4η∥θ̂⋆,t−1 − θ̂t∥2∞ + 1
4η ∥xst − xst+1∥21
≤ 2η∥θ̂t+1 − θ̂⋆,t∥2∞ + 16η
(1− γ)2 ∥yt − yt−1∥2∞ + 4η∥θ̂⋆,t−1 − θ̂t∥2∞ +
1
2η D(xst+1, x s t ).
where the last inequality is similar to (40) when θ, yt are replaced by θ̂, ŷt and we also used ∥ŷst − ŷst−1∥1 ≤ ∥yst − yst−1∥1 along with (8). We collect all the estimations in (81)
η⟨θs⋆,t+1, xs−xst+1⟩+D(xs, xst+1)+η⟨θs⋆,t+1− θ̂st+1, xs−xst+1⟩ ≤ D(xs, xst )− 1
2 D(xst+1, x s t )
+ η⟨θs⋆,t − θ̂st , xs − xst ⟩+ e1,t + 2∥E[θ̂t+1|xt]− θ⋆,t∥∞ + 16η2
(1− γ)2 ∥yst − yst−1∥21
+ 2η2∥θ̂t+1 − θ̂⋆,t∥2∞ + 4η2∥θ̂t − θ̂⋆,t−1∥2∞.
We use (8) and definition of Φst to get
η⟨θs⋆,t+1, xs − xst+1⟩+Φst+1 ≤ Φst + 2∥E[θ̂t+1|xt]− θ⋆,t∥∞
+ 2η2∥θ̂t+1 − θ̂⋆,t∥2∞ + 4η2∥θ̂t − θ̂⋆,t−1∥2∞ − 1
2 D(xst , x s t−1) +
32η2
(1− γ)2 D(yst , y s t−1).
We finally estimate the bias term
∥E[θ̂t+1|xt]− θ⋆,t∥∞ ≤ ∥E[θ̂t+1|xt]− θ̂⋆,t∥∞ + ∥θ̂⋆,t − θ⋆,t∥∞ = ∥E[θ̂t+1|xt]− θ̂⋆,t∥∞ + ∥Eb∼ystQ s t − Eb∼ŷst Q̂ s t∥∞
= ∥E[θ̂t+1|xt]− θ̂⋆,t∥∞ + ∥Eb∼ystQ s t − Eb∼yst Q̂ s t∥∞ + ∥Eb∼ŷst Q̂ s t − Eb∼yst Q̂ s t∥∞ ≤ ∥E[θ̂t+1|xt]− θ̂⋆,t∥∞ + 2ζ(|A| ∨ |B|)
(1− γ)2 + 2ζ|B| 1− γ ,
where the last step is by (53) and (56).
Inserting this estimate leads to
⟨θs⋆,t+1, xs − xst+1⟩ ≤ 1
η
( Φst − Φst+1 ) + 2∥E[θ̂t+1|xt]− θ̂⋆,t∥∞ + 2η∥θ̂t+1 − θ̂⋆,t∥2∞
+ 4η∥θ̂t − θ̂⋆,t−1∥2∞ − 1
2η D(xst , x s t−1) +
32η
(1− γ)2 D(yst , y s t−1) + 4ζ(|A| ∨ |B|) (1− γ)2 + 4ζ|B| 1− γ .
As in Lemma F.2, we can derive the symmetrical inequality for the y-player and picking η = 1−γ8 will make the terms 32η(1−γ)2 (D(y s t , y s t−1) +D(x s t , x s t−1)) disappear.
We sum the inequality along with its y-player counterpart and insert into RHS of (80) to conclude.
Corollary G.20. Set ζ = (1−γ) 2ϵ
|A|∨|B| and step sizes as from Lemmas 3.6 to 3.8 with λ̂ θ min = ρζ/(|A| ∨
|B|), λ̂ωmin = ρ, ζ = ϵ(1−γ)2 |A|∨|B| . Then, the complexity for stage 1 of Algorithm 10 is Õ(|S|
2(|A| ∨ |B|)6(1− γ)−5ϵ−4ρ2).
Proof. First, we notice that both variance and bias terms in Lemma G.18, now we learn θ̂⋆,t, θ̂ y ⋆,t by sampling x̂t, ŷt. Therefore, from the point of view of policy evaluation, we can directly apply the results we derived earlier with strong monotonicity constants λ̂θmin = ρζ/(|A| ∨ |B|), λ̂ωmin = ρ. The bound in Lemma G.18 becomes
EEs∼σ [ max xs,ys xsoutQ sys − xsQsyout ] = O ( Φs0 − ΦsT ηT ) +O ( 1 T T∑ t=1 E∥E[θ̂t+1|xt]− θ̂⋆,t∥ )
+O
( η
T T∑ t=1
E∥θ̂t+1 − θ̂⋆,t∥2 + E∥θ̂t − θ̂⋆,t−1∥2 ) + 1
Tη EEs∼σ max z T∑ t=1 [e1,t + e2,t])
+ 4ξ(|A| ∨ |B|)
(1− γ)2 + 4ξ|B| 1− γ .
By using Lemma 3.6, we can derive the variance of θ̂ by sampling with x̂t, ŷt
E∥θ̂N − θ̂⋆,t∥22 ≤ O
( |S||A|
(1− γ)2N2 +
1
N(λ̂θmin) 2(1− γ)2 + |S||A| (λ̂θmin) 2 E∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥2∞
) .
For the final term in this bound, we use Lemma 3.8 to estimate V x̂k−1,ŷk−1 by sampling with x̂k−1 and ŷk−1.
E∥ ˆ̂Vk−1 − V x̂k−1,ŷk−1∥22 ≤ O
( |S||A|
(1− γ)2N2 +
1
N(1− γ)2(λ̂ωmin)2
) ,
For the bias of θ̂t+1, we use Lemma 3.7
∥E[θ̂t + 1|xt]− θ̂⋆,t∥2 ≤ O
( |S||A|
(1− γ)2N2 + 10|S||A| (λ̂θmin) 2 ∥E[ ˆ̂Vk−1|xt]− V xk−1,yk−1∥2∞
) . (82)
On this bound, we use Lemma 3.8 ∥E[ ˆ̂Vk−1|xt]− V xk−1,yk−1∥22 ≤ O (
|S||A| (1− γ)2N2
) .
Finally for the error terms e1,t + e2,t, we use Lemma F.6
1 T EEs∼σ max x T∑ t=1 e1,t ≤ log |A| T + 1 T T∑ t=1 4η2E∥θ̂t+1 − θ̂⋆,t∥2∞.
Inserting these estimates and using λ̂θmin = ρζ/(|A| ∨ |B|), λ̂ωmin = ρ, ζ = ϵ(1−γ)2 |A|∨|B| , Remark F.3 give
EEs∼σ [ max xs,ys xsoutQ sys − xsQsyout ] ≤ Õ ( 1 T (1− γ) ) + 8ϵ + Õ ( |S|2(|A| ∨ |B|)6 (1− γ)5ρ2ϵ2N ) ,
which gives the final result.
Stage 2 of Reflected NAC with a game etiquette and ζ-greedy exploration in Algorithm 10 Recall that in Appendix F.2, we extended the result of Lan (2021) on single agent setting to the stage 2 of our algorithm. Since in the stage 2, xk is fixed, it is part of the environment and therefore single agent analysis extends in a straightforward fashion. In this section, similarly we use our results in Appendix G.2.1 for stage 2 of the algorithm. Note that our results in Appendix G.2.1 are similar to single agent results of Lan (2021), with the difference that we use ζ-greedy to avoid Assumption 2. Also recall that the single agent analysis in Lan (2021) requires Assumption 2 (see (Lan, 2021, Remark 1)).
For brevity, we do not repeat the arguments in Appendix F.2 to extend Appendix G.2.1 for stage 2 in this case. We summarize the result in the next corollary.
Corollary G.21. Let Assumption1 hold. Let ζ = (1−γ) 3ϵ
|A|∨|B| and step size from Lemma F.7 with λ̂ ν min =
(1−γ)ρζ/|B| (see also Corollary G.16). The overall sample complexity for stage 2 of Algorithm 10 is Õ((|A| ∨ |B|)4|S|(1− γ)−13ρ−2ϵ−4).
Proof. It is straightforward to use the arguments in Appendix F.2 to extend Appendix G.2.1 for this result.

heading: H ADDITIONAL EXPERIMENTS

heading: H.1 ENVIRONMENTS DESCRIPTION
text: Bandit environment. We first consider a two player bandits problem with 100 arms. All the arms give zero reward except a∗ that has r(a∗) = −1 and b∗ with r(b∗) = 1. The reward of the two player game is r(a, b) = r(a) + r(b). In this environment there exists a pure Nash Equilibrium given by x = 1{a = a∗}, y = 1{b = b∗}. Alesia environment. We also test our algorithms on Alesia(L, C) (Perolat et al., 2015). Alesia is a simultaneous move game where the two opponents try to move the wrestler to their extremity of the board of length L. At each turn, the “wrestler” moves one step in the direction of the player that bets the higher amount of coins from their budget of size C. The game ends when either one of the wrestler reaches extremity of the board or both players finish their budget.

heading: H.2 HYPERPARAMETERS SELECTION.
text: In the following we report the hyperparameters chosen for the experiments to ensure reproducibility. In addition, we include an additional experiment on Alesia(L,C) with L = 3 and C = 7 in Figure 2. Since the eigenvalues λθmin, λ ω min, λ ν min are unknown, we cannot compute the values
of learning rates βθn, β ω n used in the theoretical results. Therefore, we simply set the learning rate as Cn suggested by the lemmas and fine tune the hyperparameter C by grid search. Similarly for OGDA, we use grid search to replace the optimal learning rate given by (Wei et al., 2021, Theorem 2). Appendix H reports the chosen parameters. Table 2, Table 3, Table 4 and Table 5 summarize the best hyperparameters found for Reflected NAC and OGDA in the two environments: bandit and Alesia.
REINFORCE (Daskalakis et al., 2020) only needs two hyperparameters. We chose the exploration parameter ϵ = 0.1 and the step size η = 0.0001. We observe that it was critical to choose small step size to tackle the high variance coming from the REINFORCE estimator.

Review summaries:
This paper considers algorithms based on natural actor-critic for solving two player zero-sum Markov games in the tabular case. In particular,  the authors focus on the analysis of the sample complexity for a two-stage algorithm that solves a matrix game and a single agent problem, alternatively and iteratively. By combining and refining recent results for policy gradient methods, this paper manages to match the best-known results for global convergence of policy gradient algorithms for single agent RL. 

This paper studies the sample complexity of learning algorithms in two-player zero-sum tabular Markov games. The authors propose a two-stage algorithm that requires agents to agree on an etiquette, which means the agents have behave differently in two stages. Based on two assumptions on stationary state distribution and action exploration that are different from previous works, the authors show two finite-time convergence bounds, which improve much compared with existing results. The most challenging part of their proof is in bounding the approximation error in the first stage, which approximates the equilibrium of a matrix game. The authors also present some numerical results that can verify the performance of the proposed algorithm.

This work proposes a natural actor-critic (NAC) algorithm for two-player zero-sum Markov game in the tabular case. The algorithm is model-free, private, but asymmetric, and the convergence guarantee is established in terms of the expected one-sided Nash-equilibrium duality gap. Among the existing policy-based algorithms for the two-player zero-sum Markov game, this is the first work that claims to achieve the best-known sample complexities of policy gradient algorithms for single-agent RL.