Sample-efficient actor-critic algorithms with an etiquette for zero-sum Markov games
Authors: Ahmet Alacaoglu
Luca Viano
Niao He
Volkan Cevher
Venue: ICLR 2022 Submitted (2022)
Keywords: zero sum Markov-games
policy gradient
actor-critic
temporal difference

Abstract: We introduce algorithms based on natural policy gradient and two time-scale 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/actor-critic 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 literature. Our algorithms feature two stages, requiring agents to agree on an etiquette before starting their interactions, which is feasible for instance in self-play. On the other hand, the agents only access to joint reward and joint next state and not to each other's actions or policies. Our sample complexities also match the best-known results for global convergence of policy gradient and two time-scale actor-critic algorithms in the single agent setting. We provide numerical verification of our method 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.

Under review as a conference paper at ICLR 2022
SAMPLE-EFRICIENT ACTOR-CRITIC ALGORITHMS WITH AN ETIQUETTE FOR ZERO-SUM MARKOV GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce algorithms based 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/actor- critic methods for convergence to Nash equilibrium in the multi-agent setting. We use the error propagation scheme in approximate dynamic programming. re- cent advances for global convergence of policy gradient methods, temporal differ- ence learning, and techniques from stochastic primal-dual optimization. Our algo- rithms feature two stages, requiring agents to agree on an etiquette before starting their interactions, which is feasible for instance 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 conver- gence of policy gradient algorithms for single agent RI. We provide numerical verification of our methods for a two player bandit environment and two player game, Alesia. We observe improved empirical performance as compared to the recently proposed optimistic gradient descent-asee ascent variant for Markov games.
INTRODUCTION
We study two-player zero-sum Markov game framework which key model with broad applica- tions in competitive reinforcement learning (RL), robust RI., and many others /Zhng 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 environ- ment 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- planing and robotics (Kober et al.,
2013 (Slverr 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 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 (001) and natural AC (NAC) (Pe-
ters & Schaal 2008), only have limited guarantees, despite their model-free and sasy-to-implement
structure, flexibility and generality (Schulman 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- non-convex optimization problem even the basic single agent, tabular setting. Intriguingly, recent results demonstrate globally optimal convergence of PG methods by identifying
hidden convexity structure for single agent RI. (Agarwal et al.) 2020 (020,Cenn& et al., 2020 Mei et al.,
2020
Xu Bhandari & Russo 2019 [2021] Xu et al. 2020b [an 2021 Khodadadian et al. 2021b Hong
et al.
2020 Xu et al.
| 2020a Khodadadian et al. 2021b), and multi-agent RI. (MARL) (Daskalakis
al.
2020
Wei 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(E -12.5) (Daskalakis et al. 2020), Ō(6-8), and even Ō yet with some limitations (Wei et al. 2021); ; see Section 1.1 for the details. With function approximation, Zhao et al. (2021) obtains O ") sample complexity when given access to unbiased sampling oracles of the value functions.

---

Under review as a conference paper at ICLR 2022
On the other hand, the best-known sample complexity for global optimality for single agent problem is O(E=²) 2) in the tabular case (Lan 2021). As this complexity is achieved by balue-based/model- based 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 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.) 20216, Hong et al., [220]] Xu et al., (020b). In particular, we show that by using inner loops for policy evaluation and a carefully designed algorithm, the sample complexity to get an e-approximate Nash equilibrium, is Ö(E 2), by assuming a uniform lower bound on the policies. Without this assumption, we show Ö(E +) complexity
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 single agent setting, temporal difference learning, two-stage error propagation framework of policy itera- tion (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 Ō(-²)) 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 insights in the sequel. The full proofs are included in the appendices.
1.1 RELATED WORKS
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
cet al. 2020 Mei 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 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 (c-2) and is due to (Lan 2021). For single loop NAC with online policy evaluation, the best sample complexity is Ö -) as obtained in (Khodadadian et al. 2021bb Hong et al. 2020 Xu et al., 20206) (see (Khodadadian et al., 2021a Table I)). For a general overview 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 inter- acting symmetrically has been considered in Daskalakis et al. (2220): Wei et al. (202T). 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(e 12.5) for reaching to one-sided Nash equilibrium.
The algorithm of Wei et al. (2021) built optimistic gradient descent-ascent (OGDA) method combined with running estimate of the value function, obtaining Ō sample complexity for finding a policy pair with small duality gap. In addition, |Wii et al. (2021) showed improved com- plexity ( when restricted to Fuclidean 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. (02II) this result is limited 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
In Appendix B we design an algorithm based on single loop NAC with the complexity of Ô(c-") (and (c) 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.
2

---

Under review as a conference paper at ICLR 2022
Assumption
Complexity
Daskalakis et al.
(2020)
Sz,a,b { 0.*
Wei et al. (021)
maxa.y.e.s' T5
where μ > 0.1
Ö 4y-
2.
Section 3.1
Assumption
()
Section 3.1
Assumption
())
Table 1:
"In game with finite steps, Çs.a.b is the probability that the game will end at state 8, after taking
actions a, b (Daskalakis al. 2020 Section 2). "T is the time that it takes to go from state to state s' by using policy pair 2; (Wei ct al. 2021 Assumption 1). "This Ō(e=*) 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 is not applicable to NPG.
shown in Agarwal et al. 2020) for single agent problems, NPG methods have much better conver- gence 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 I and Table [
Another very related work to ours is by Zhao al. (202T) which considered (i) tabular setting with exact value functions and (ii) online setting with function approximation, also using the error propagation scheme Perolat et al. (2015). Building on AAgawal et al. (2020), this work showed Ö(c-)) sample complexity with function approximation, with access to unbiased samples of the value functions. In contrast, we focus 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 Ō(c-2) and O(E
Policy gradient methods for linear quadratic regulator (LQR). For zero-sum LQR, Zhang al. (209b);; Bu et al. (2019) showed global convergence of PG with exact value function oracles. These methods have 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.
2 PRELIMINARIES
Notation. We consider the tabular setting with finite state and action spaces denoted by S, A. B and the discount factor y < 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: b ~ s(-1s). Based on the actions, the environment transitions to the next state s' ~ P(-|s, o, b) and the agents receive reward [r(s, a, S 1. Given policy pair 2; y. we denote the induced steady- state distribution as pT Let 24 denote the uniform distribution for states that we also take as the initial state distribution for simplicity. We denote the probability simplex
z0-(s) and
A. Given a policy x, sometimes use the notation x= for <=|ss) in the proofs. We use e(s,) RISI to denote the vector such that e(s) = 1 if s 8, and e(x) = O, if 8 # 8t. We use the same notation for e(st, az). The value function for state is defined
V (s) E
Er'r(s ar be)
where Ery is over random variables 8t, an, for all 1 > 0 as oe ~ x((111), by ~ v(((st) and St+1 ~ P(-|s,, ag, bt). Similarly, the action value function is defined as QFA a, Ex,y 1E 7rr(st, ar, be) = 8, ag a, b, = bj. With these definitions, can state the formal problem. For all s E S, we aim to solve
max (T. x *(1)) VHE
min
We denote the information needed algorithms as oracles. We provide the background on NPG, NAC, TD(0) Appendix A
Nash equilibrium. We assume the existence of a pair of policies x" y² that are Nash equilibrium, namely, for all s. (s) < V*(s) == V= wy" (s) < y= (s). We are interested in finding a one-
sided Nash equilibrium, similar to Daskalakis et al. 2020 Zhao al. 2002) /hang al. (201b));
3

---

Under review as a conference paper at ICLR 2022
Bu et al. 2019)). As mentioned in Daskalakis et al. (2020), for the other player, one 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 Fout such that
Bx [max V V c. y
is easy to prove that this quantity on the LHS is 0 and only if Nout 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 (&t, a; r(s;, at, b;); 85+1) and (&i, b2, (88, 0g, b.). 8i+1). respectively. In terms of access of agents, our oracle model is similar to Daskalakis et al. (2020;; Wei et al. (02T). However, one difference is that we require game etiquelte: 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-Leible divergence KL and action-value function Q",,
x1+1(11s) (2k((x (2. (-Is), ( +)) == arg min (Q" (s.))))(((1s)) + (x)() (1)
x(++=)E
known as NPG with softmax parameterization (Agarall et al. 2020 Lemma 5.1). When there is critic estimating Q"*, along with actor updating 2, 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 P such that, for any policy iterate pair Itt yts for any state it holds that p (s) 2 p >>>>00 O, where p is the stationary state distribution induced by the policy pair.
Assumption There exist I, y such that, for any policy iterate pair It, Mo any state action tuple s, a, holds that xr(a)s) s) 2 2 0, (bbs) ) 2 y > 0.
Our rationale on the assumptions. Assumption] I and essentially mean positive definiteness of
the sampling matrices in policy evaluation (see eqs. 330 34p and (42). ). To our knowledge, some
form of this assumption is required in most of the existing work on temporal difference (TD) (in-
cluding TD(O)) methods for policy evaluation (Bhandari et al. 2018 Xu al. 2020b) Khodadadian
cet al. 2021a Lan 2021 Hong et al. 20200] Xu et al.) 2020a| Wu et al. 2020 Zou et al.) (019) (see
App. Ap. The complexity ((e-2) requires Assumption 2 even for single agent problems (see (Lan
2021
Rem. 1, Sec. 5.2)).
Remark 2.1. As summarized in Table similar assumptions to Assumption are used in Daskalakis et al. (2020): Wei et al. (2027). In particular, each of these assumptions ensure that all action-stadt state pairs are observed with nonzero probability throughout the game. Moreover, by additionally requir- we can obtain the complexity O(e-3) matching the single-agen agget counterpart. ing Assumption 2
Markovian bias. For simplicity, we assume that sample from the steady state distribution of given policy pair. During normal interaction with the environment, this is not the case and we obtain single stream of data. Hence, TD(0) update is biased coased-commonly referred 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., 20188 Zou et al. 2019) Khodadadian et al. 202 Xu al. 20206 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 fixed value function Vk-1, find the policy pair which is an c-equilibrium.
min max Ee E'
Σ 2(als)p(als))) =: ==x00 QQ-11";
(2)
4

---

Under review as a conference paper at ICLR 2022
Algorithm Reflected NAC with game etiquette and (-greedy exploration
Require: pKL defined in Sec. Exploration parameter Ç 2 (with equality if Assump- Sollcc--val--e Policy Bolicc-vval-a (see and note 5% Sn. P are potential step sizes for this routine). Initial policies zo. No. Mo x of denote outer, 24, Yr denote inner loop's 's iterate.
tion 2 holds). Subroutines
Alg.
1: for = 0. 1....... do
Approximately solve matrix game 3: for = 0, 1,......77 T do
2: Stage
4:
V [-1 = cv---ya-V(aaa
N, (.) Policy- 1- -V ,, -, N, (2)) // Both players compute their own estimations of V denoted V/ and Lvv
08t1: 0p+1] [Policy-Eval-O(rr Ur, N, V 1 Polcy---a-lll Ut. N, 14 (-1))
5:
6:
*++1(118) PKL (zz(-11),, (0,+ 0g (,,
(8, 3++1(11s) DKL. (+(()s), 11 220% (s, 8% (s.
7:
8:
Output I² - + EE= St..
9:
Stage 2 Approximately find best response
10:
for = 0, do
P(41 Pollicy-Evll--e (x=" Dt. N, N, 3%
12:
(++1(-|s) = pkl (+r()))) (1,)))(8.)))
13:
Output y Vü. where i E [T] is selected uniformly at random.
Algorithm 2 Vy = Dolicy-Eval-V (x, y, N, B)
Require: Policy pair
iteration counter N, step size 8, initial value function estimate Vo- a(-1s) = (1 -1- (-((( + مीp. 0(-1s) = (1 ()u((1s) + T
1: for = 0, 1,..., N - do
2: Sample Sn ~ -pp ( On ~ ((-(sn)) bn ~ ((((1s)): Snt1 ~ P(.(sn, ane bn).
3: Va+1 Vn - (n (V (V) r(8ns an an, ba) (Vn(sn+1)
where QK-1 a, b) r(s, + P(s'ls, (s') When it is clear from the context, we drop the subscript of QA-1- This is a matrix game and is the cemple-complent bottleneck (Per-
olat et al. 2015). Let C denote the accuracy and x² the output of this stage at iteration k:
E[ mmx E*EA
min max x: Qi-ivy" = e.
x"EA y"E
where the outer expectation is over the randomness of the algorithm used generate x²
This step finds an approximate best response. The fixed policy (x*), can be viewed as part of the environment. Denote y* as the approximate best-response computed in this stage, at iteration The resulting value function V; V=* .** fed to stage in the next iteration. Let ea be the accuracy for this stage, y² the output of this stage:
Stage 2:
E E (max V** ((s) v= wf [s)] c
where the outer expectation over the randomness of the algorithm used to generate y² Then, Pero- lat et al. (0055 Theorem Zhao et al. (202T) show that the following holds (see also Appendix C
SKK Ö
+ sup & + + shh
B max V² (>",,(()) - V(s)- < 1-
sup kSk
E
(
1-7)
(5)
YEA
KSK
REFLECTED NAC ALGORITHM WITH GAME ETIQUETTE
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 equilib- rium, in view of (5). We leverage primal-dual algorithms to solve the matrix game in Stage
5

---

Under review as a conference paper at ICLR 2022
Algorithm 3 0y = Folicy-Eval-dee (x, y, N, V, B) for player y
Require: 2(-15) - (1 ())((1s) + 1 (1(ss) - (1 --)x(-11s) + [ل]
1: for = 0, .........4 N - do
2: Sample 8y ~ 0 (-), on ~ - bn ((-1sn), sn+1 P(- (nsnnannbbi bn).
3: 0,+1- = On - ene(sn Un) (0x (8n bn) - r(8n; ans bn) - 7 -V (8n+1))
Algorithm 4 i/ Policy-Bval-ule y, N, B) for player y
Require: 2(-18) = (1 ()x((11)) + TÂTO 0(1))) = (1 s)u((10) + [ल.
1: for 0,1,....,.. NN do
2: Sample Sn ph an ~ (1-(5))) ), bn ((-18,)) Su+1 ~ P(.)sm Ony bn), but1 ~ ((118)))).
3: Pat1= = On ( kn) (in (8 bn) - 188n any kn) yPn (Sn+1: bnt1))
efficiently Malitskk& & 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(O) Tsitsiklis & Van Roy, 1997 Bhandari et al.) 2018 |Sttonn 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 fixed, this a standard matrix game and throughout this loop, we omit the dependence of Q on l and leave it implicit. Our discussion here is for player and it would be symmetric for the y player. Due to its simplicity and generality, we use hewwardreflected-backkwe algorithm (Malitsky & Tam 2020 FoRB takes a reflected step rather than using Esny. Q(s,, directly, which is the case in gradient descent-ascent (GDA). The FoRB update is
(FoRB)
T:41 (-1s) = (x:(1(x)))))) 1) (2Ebny (s,, b) E
In standard matrix game notation, cation between the dual vector and game matrix Q. To get this oracle, we have to solve linear equation by sampling the policies Tt, 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 1 Given that Vx-1 is the value function of policies ==11, 1/a 1--1, in Step we use TD(0) to learn this value function and obtain a biased estimation Vr- (see Algorithm 2). Using this estimation, we can then proceed solve the linear equation by sampling the policies 2e; Mr to find an estimate for 0% Ea-y, Q(s, : b). in Step (see Algorithm
view 0% Bawy, Q(8, : b) as the matrix- multipli-
3) This step similar to stochastic approximation/SGin approaches (Ne-) mirovski 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 and corresponding policy evaluation routine Alg. 3 agent only accesses $t, r(tt, ag bt). $t+1 and its own action a to form the stochastic oracle and y accesses st, (Ss, az, bt), Sc+1 and its own action by. We have additional bias coming from the approximation of Vi-1 by V4-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 Va-1 estimate (See Insight Markovian data would bring additional bias as mentioned before.
Remark 3.1. For the best complexity, we use fresh estimates of Vi-1 at every iteration (see Algo- rithm 1 and Insight 4). This gives tight bound for the bias to get the Ö(c-2) complexity. This insight is in contrast to the black box view Perolat et al. (2015), which uses an estimate of Va-1 from the stage within the stage 1. Our analysis behwoves both agents to remember the output policies of stage 2 instead, so that they can recompute Vk-1 with lower bias in the stage 1.
Stage 2. In this step. at iteration k, 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 V that was used in stage is precisely the value function of the policies outputted this stage in iteration 1. For NPG update, y player needs Bana Q=* gx & (,, a,
In principle, this part can be replaced with mirror-prox Nemirovski 2004 OGDA.

---

Under review as a conference paper at ICLR 2022
This is the joint Q function after taking the expectation over the actions of player Since player's policy is fixed, we only use policy x² in this loop, whereas y player continue to update its policy Øt-
We can write Bellman equation for learning this oracle and then use TD(0) in Bhandari et al. (2188) (see Algorithm 4. which is similar to learning a Q-function. In particular, as long as $t, Ct. b,, St+11 are sampled using the interaction procedure described earlier, there is need for Vr update to see the actions or policy of x² A similar formulation for policy evaluation in MARL is considered in Perolat 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 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 holds. In the former case, we can take Ç 0.
3.1
MAIN RESULT
Theorem 3.2. (Overall performance bound with Assumption 2
For Alg. with Ç = 0,
K|S|
B Bigg ul maxx V/a..( (50) (so))] s
1
([1->)3
+0 K]STP(LA) [B)
1
(py - 7))² )) + 0 (-*).
((11-))(((1-)) 7)}²
(pmin y)))
In particular, the overall complexity ((IS) V [B])e 71 122 0 (minf2, (z. y}) -2).
In this bound, the first term is for solving the outer loops in stages 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 al. 2015
Theorem 3.3. (Overall performance bound with Assumption 7 see App. G.2.2) Let Assumption
hold. Let Ç = B
(1-2)²
Alg. 1
K|S| 7)1-733/ +
K| BId
EE B u [max (s.)) V* (s))l 50
N(1 - 22 +0(0*).
Consequently, the sample complexity is Ó(IS)*(IA])
16 2-
As summarized in Table I Theorem 3.3 matches the best-known existing complexity from Wei al.] (202I), without using the metric subregularity constant and without restricting to Euclidean projections. For natural policy gradient, this result improves Ö(E 5) in Wei al. 20021). We refer to Remark G.17 for more detailed comparison. Moreover, Theorem 3.2 matches the best-known complexity in single agent RI, under Assumption
3.2 CONVERGENCE ANALYSIS
Proof sketch. Next, show how to obtain the required bounds for this final guarantee, in view of eq. (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 ): solving the matrix game. A critical point to derive the fastest rate as observed by Lan (222 in the single agent setting is to characterize the bias and variance separately. As the algorithm in Lan 2021 is akin 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 20200, deterministic oracle is computed at each iteration. Böhm et al. 2020 uses unbiased oracles with bounded variance and decreasing step size. In our case, we
7

---

Under review as a conference paper at ICLR 2022
have biased oracles and we use inner loops to decrease bias and variance. Next, develop analysis with constant step size and characterization of the bias and variance explicitly.
Lemma 3.4.
(Bound for stage 1) Let Assumption hold.
Denote Tow = T Ei=1 Is and you =
Et Ut and let 1) 1_ 'The,, holds that
T
E
Egnil
max I Tom Q'v² - x² You
you
+
O
E
B 1001+1/22 0,,ell
me y
TTT
T
T
+0
7 T
E B 0.,011 Bl 00,1-212
+ E
1 Tn
max ==
E2,,
Remark 3.5. When bias and variance are O, this reduced 1/T rate as in Zhao al. 2021)
Bounding e (see (3)) is via bounding LHS of Lem. (.44 This allows to bound the suboptimality
thanks to To this end, we bound the second term RHS of Lem. 3.4 in Lem. 3.7 and the third
term in Lem. 3.6
We drop the superscripts from 0, V4-1 (see Alg. 1/(0, (-18) 0(0 (-1))==a))))] (11ss) 100--ax---a (-())))) (0"
1 as estimations are symmetric. For a free variable
z == (2r, y). define & +z))
(+1))l)))) v(1ss) ve(-1s))-
The last error term in the lemma involving E2, is due to the coupling between the free variables x² y and randomness of the algorithm. For this error, adapt the "ghost iterate" trick from Nemirovski et al. (2009) for stochastic primal-dual algorithms (see Lemma F.6).
Insight 2.
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 in the appendices.
Next is the the variance estimation, which is similar Lan (2021). except handling the error term coming from V/-1 as in Insight Apart from that subtlety, this part similar to SGD-type analysis with biased oracle, where we measure the squared distance of the iterate to the solution.
Lemma 3.6. (Variance estimation for step
5) Let Assumption
2 hold. Let 1 pmin(y ( (o)
for no 1. Then, for Algorithms and
El10N 00.el1 < O
N EI -
-V-- 11
N2 (pmin (y, xz)²
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 VE- instead of real Vx-1 (see (2)
Step We exploit structure of the underlying problem to make sure the error term appears
E k-1
V1 in the bound instead of 15] Vk-1- Vx-1lloc, which would deteriorate the rate.
The next estimation is critical for obtaining the complexity result. particular, we bound the bias of 0 Since in Lemma 3.4|, we need a tight bound for [|E[0+++ [xx]] - 0+.ell || [ar.] 0x.ell- we have to be careful with the additional bias from V--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
50) Let Assumption
7 hold, 18
quin Ey
2
no
O ((omittew1>>) ). For Algorithms 1 and
[[[0 - 02.el2 < o
1 N2
E V
[cr]] Vi- 11ce
(6)
(pmin (z. y))a
Insight The reason to use fresh estimates for Va-1 at each as in Algorithm 7 is the result of this lemma (see Remark R.7ark3.7]. Since the bias term in the algorithm's 's analysis is [[ - 0..el in Lemma 3.4 take the square root of the result of Lemma 3.7 If Vi-1 is estimated before St. then will have E V Vk-ill | in the bound of Lemma 3.4 which will have the rate
8

---

Under review as a conference paper at ICLR 2022
(LI On the other hand, we estimate 1 in Algorithm 1 then will be able to the improved bias bound [ V-- O(1/N) in the next lemma.
The next lemma is for the estimation of the value function V4- using the policies 2 y with TD(O). Therefore, this is analysis for TD(O), similar to Lan (202I).
Lemma 3.8. (Variance/Bias estimation for step 7 Let Assumption
hold and 5%
Min+no) with no (e(--11)))) The variance and bias of Vi-1. computed as in Algo-
rithm 7 Satisfies
S[VV-1lZ4:10 VA-1 10BSONN)) B V&- V o (g(1
Unlike stage the stage (finding the best response) mirrors the single agent analysis closely. Due to space constraints, we defer the details to App. Combining Lemma 3.4 with the result of stage
(which is of the same order) (5) gives Theorem 3.2 The main idea of Thm. 3.3 is to use Ç-greedy
exploration to replace the policy values z. (see Theorem 3.2
Lemmas 3.6 3.7 3.8)
which might
be 0 without Assumption (see App G.2.2p.
4 NUMERICAL VERIFICATION
We validate algorithm in tabular domains comparing against OGDA (Wei al. 2021 and REINFORCE (Daskalakis et al. 2020). More results implementation details and environment description are given in Appendix H We emphasize that main contribution is theoretical; the preliminary computational results are for verification purposes.
NENTORCE
0524
0GB4
RERFORGE
Conseeetaa 100
(a) Bandits player
(b) Bandits y player
(c) Alesia x player
(d) Alesia player
Figure 1: Bandits We plot the probability of action a" for the x policy and 6" for the y policy. Results are
averaged over 10 seeds. Alesia: Experiments in Alesia with length L = 3 and coin budget C' = 6. The
suboptimality gap the vertical axis max, (st)(s)) V (8o) for and minn V=t.((s)) V (**()) for where the initial state that is deterministic in Alesia. Results averaged over 5 seeds.
Observations. Both the domains challenge theoretical assumptions. Therefore, our best complexity result (c--2) from Theorem 3.2 does not apply in this setting. Similarly, the assumptions in Table do not hold. The assumption of (Wei et al., [22II) and our Assumption [ do not hold because in only lose coins. Therefore the initial state cannot be reached in finite time
Alesia the players 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, follows that we canmot lower bound the termination probability any state. Nevertheless, shows the value of the bandit player policies evaluated at the NE actions (a* f,*,1 b²), i.e. 22(a") and y(b*). Reflected NAC converges faster than OGDA (Wei al. 2021) and REINFORCE (Daskalakis et al. 2020). Similar conclusions arise from Figures Ic where we plot the suboptimality gap in Alesia.
observe that all the algorithms converge. Figures Ta 1b
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods markov decision processes. In Conference on Learning Theory, pp. 64-66 PMLR, 2020.

---

Under review as a conference paper at ICLR 2022
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national Conference on Machine Learning, pp. 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in Neural Information Processing Systems, 33, 2020.
Heinz H Bauschke, Patrick Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:I906.01 01786, 2019.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for fi- nite mdps. In International Conference on Artificial Intelligence and Statistics, pp. 2386-2394.
PMLR. 2021.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pp. 1691-1692. PMLR, 2018
Axel Böhm, Michael Sedlmayer, Ernö Robert Csetnek, and Radu loan Bot. Two steps at a time- taking gan training in stride with tseng's method. arXiv preprint arXiv:2006.08 09033, 2020.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019.
Jingjing Bu, Lillian Ratliff, and Mehran Mesbahi. Global convergence of policy gradient for sequential zero-sum linear quadratic dynamic games. arXiv preprint arXiv:1911.0444 2019.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint a7Xiv:2007.05/70, 2020.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Sajad Khodadadian, Zaiwei Chen, and Siva Theja Maguluri. Finite-sample analysis of off-policy natural actor-critic algorithm. arXiv preprint 172.v.2102.09318 2021a.
Sajad Khodadadian, Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite sample anal- ysis of two-time-scale natural actor-critic algorithm. arXiv preprint arXiv:2101.10506 2021b.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11)1228-1174, 2013.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008-1014. Citeseer, 2000.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00//35 0015,, 2021.
10

---

Under review as a conference paper at ICLR 2022
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994. pp. 157-163. Elsevier, 1994.
Yura Malitsky and Matthew K Tam. A without cocoercivity. SIAM Journal on Optimization, 30(2):1451-144 2020.
splitting method for monotone inclusions
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp- 6820-6829. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 5 518(7540):529-533 2015.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization submodular maximization. Journal Machine Learning Research, 21(105):1 2020.
Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, pp. 560-567, 2003.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems.
SIAM Journal on Optimization, 15(1):229-251, 2004.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal optimization, 19(4):1574- 1609, 2009.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, pp.
1329. PMLR, 2015.
Julien Perolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultaneous move multistage games. In International Conference on Artificial Intelligence and Statistics, pp. 919- 928. PMLR, 2018.
Jan Peters and Stefan Schaal. Natural actor-critie. Neurocomputing,
2008
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, and Matthieu Geist. Approximate modified policy iteration. In Proceedings of the 29th International Coference on International Conference on Machine Learning. pp. 1889-1896, 2012.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning. pp. 1889-188888 1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1777:07777 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5668-5675, 2020.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pp. 2992-3002. PMLR, 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 350(7676::54433555 2017.

---

Under review as a conference paper at ICLR 2022
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9 44, 1988.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural information Processing Systems, 12:1057-1063, 2000.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Provably efficient online agnostic learning in markov games, arXiv preprint arXiv:2010. /5000, 2020.
Paul Tseng, On accelerated proximal gradient methods for convex-coneave optimization. submitted to SIAM Journal on Optimization, 2008.
John Tsitsiklis and Benjamin Van Roy. An analysis temporal-ddiffrrence learning with function approximation. IEEE transactions automatic control, 42(5))674-69)) 1997.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350- 2019.
Ziyu Wang, Victor Bapst. Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay. arXiv preprint 1.11:222 2016.
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizz competitive markov games. 2021.
arXiv preprint
Ronald J Williams. Simple statistical
algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25 256, 1992.
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu, A finite time analysis of two time-scale actor critic methods. arXiv preprint arXiv:2005.0/3550 2020.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultancous- move markov games using function approximation and correlated equilibrium. Conference on Learning Thhoory pp. 3674-3682. PMLR, 2020.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for actor-critic algorithms. arXiv preprint arXiv:2004. 12956, 2020a.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.03557, 2020b.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejic Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear con- vergence. arXiv preprint arXiv:2105. 2021.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:1911.10633 2019a.
Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges to nash equilibria in zero-sum linear quadratic games. Advances in Neural Information Processing Sys- tems, 32, 2019b.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent in zero-sum markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33, 2020.
Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Provably efficient actor-critic for risk-sensitive and robust adversarial rl: A linear-quadratic case. In International Conference Artificial Intel- ligence and Statistics, pp. 2762-2772. PMLR, 2021.
Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon S Du. Provably efficient policy gradient methods for two-player zero-sum markov games. arXiv preprint 102.v:2102.08900 2021.
12

---

Under review as a conference paper at ICLR 2022
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. In Advances in Neural Information Processing Systems, volume 32, 2019.
13

---

Under review as a conference paper at ICLR 2022
CONTENTS
Introduction
Related works
2
Preliminaries
3
Reflected NAC algorithm with a game etiquette
Main Result
3.2
Convergence analysis
4
Numerical verification
Background on NPG and NAC
16
Basic results on RL and optimization
17
Error propagation framework
19
Markovian bias
20
Single loop NAC with etiquette
22
Proofs for stage single loop NAC with etiquette
22
E, 1.1
Formulation
22
2,2
Proofs
24
E.2
Proofs for stage of single loop NAC with etiquette
27
Formulation
27
H.2.2
Theoretical results
28
Proofs for Reflected NAC with game etiquette
31
Proots for stage of Reflected NAC with a game etiquette
31
F.
Formulation
................................
1.1.2
Theoretical results
32
F.2
Proofs for stage of Reflected NAC with game etiquette
................................
39
Greedy exploration to remove Assumption 2
42
G.1
Single loop NAC with game etiquette and (-greedy exploration
42
G.I.I Stage of single loop NAC with game etiquette and (-greedy exploration
(See Algorithm
42
G.1.2
Stage 2 of single loop NAC with game etiquette and (greedy exploration (See Algorithm
47
Reflected NAC with a game etiquette and <-greedy exploration
52
G.2.1 Single agent result with (-greedy exploration
52
14

---

Under review as a conference paper at ICLR 2022
G.2.2
Reflected NAC with game etiquette and <-rredy exploration in Algo-
rithm
54
Additional Experiments
59
H.1
Environments description
59
H.2
Hyperparameters selection.
59
15

---

Under review as a conference paper at ICLR 2022
A BACKGROUND ON NPG AND NAC
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 (001) in softmax parameterization which admits simple update rule. In particular, the update rule for NPG in single agent setting is (Agarwal al. 2020
Lemma 5.1)
(++1(-1s) & Tr(-|s) exp((Q"((ss.)
which is the closed form solution of the update in (T) To get a sample-based version of this algo- rithm, one needs learn QT typically in an inner policy evaluation loop in Lan (2021). This is also called natural actor-critic (NAC) since the actor updates the policy T4+1 and critic learns the value function Q
Note that the update rule in (Agarwal et al. 2020 Lemma 5.1) is written with the advantage function, however, due softmax parameterization, equivalent to the form we give.
We can also generalize by using Bregman distances instead of the KL divergence
1-+1(-1s) = ((xx(-ls). (s. = arg min (Q* (s, x),=(()))) + ((x((1ss) x(+b)EE
Finally, for the formal setup of Bregman distances, we refer to Tseng 2008); Nemirovski et al.
(209)) Throughout the paper, we focus the case when D is KI. divergence, so that the update
rule corresponds NPG rule. This choice corresponds to the distance generating function of D
being strongly convex in & norm which gives the standard inequality
D(r,y) 2 2 || - -y1l..
(8)
that is used frequently throughout the proofs.
Single loop NAC. Unlike the previous case, single loop NAC (Hong et al. 2020 Khodadadian ee al.
202 1b) does not have an inner loop for computing Q at iteration I. In contrast, single
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
loop NAC keeps running estimate for this oracle (which corresponds
0c+1 0, Bie(St, ar) (0i(s), at) r(si, (80(111, (-1s) x (e(+)s) exp(n0++1(8)
with properly selected 8., Nh- generally with n 33 + 0.
Temporal difference learning. For constructing state or action value functions from samples, will use temporal difference learning and in particular TD(0) (Sutton 1988 Bhandari et al.) 2018 Tsitsiklis & Van Roy 1997). This algorithm solving a linear equation (Tsitsiklis & Van Roy stationary state distribution under p", define
be seen stochastic approximation scheme for
1997
Lan 2021). In particular, by denoting the
FF (0)(s, p= (s)s())s)
(((()))))(()))) ((s,a) r(8,))
Σ ())11s.0)7(((11100
First, we note that F (0* O where 0+ Q Under Assumption 1 Fr is strongly monotone
(see (Bhandari et al. 2018 Lemma 3), (an 2021 Section 5.2). The mai tools show this are As- sumption
2 and Bellman operator being conttaaction. Then, one can use for example (Bauschke
al.
2011 Example 22.6, Example 20.7).
One can sample TD(O) 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(O) can be extended to Markovian setting without the i.i.d. assumption by using a uniform mixing assumption (Bhandari
p" a ~ T(-1:;) and 8141 P(-|st, at), a++1 T( (((18141) and one step of
al. 2018) (see also Appendix D).
16

---

Under review as a conference paper at ICLR 2022
B BASIC RESULTS ON RL AND OPTIMIZATION
Some notation. We say that an operator + F(O) is Amin-strongly monotone (F(01) F(82), 01 B2) Amin ||01 02ll3 and Amax- -Liscchip if [F((0)) F(02)ll2 I Amax || 0- These conditions can be defined with other norms, but we stick to f2-norm for simplicity.
Lemma B.1. Define Og recursively as Be+1 0₁ - F(t, {t) where r(s, b) S 1 and F(O),C)) = e(s', (O.((s a')ss,a)))))) - a. " ,a") and recall the definition of Qk(s, a, b) r(s, + E P(s'(s, a, b)Va(s"). Then, it follows for any t, k
110.llo - 1-7
v
V
110/122 <
1
1
11Vo-1llo $
1-
3
||((0,, S
1-9
2
[Qu(s, b)1l S
1-7
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 proof's 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 U1: 1/2 and any state so
E B (Bawa(-1as) Q=) (,,22ss,,,,) (s,a, y2(+1s))
standard result that we use Lipschitzness of y (sp). 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, 1/1 V2.
2
V 12.92 1oc S (1 71- max (-1s) (2(+)s)
Proof. By the performance difference lemma Kakade & Langford 2002 and Cauchy-Schwarz in- equality, for any 80.
va (80) 22.82 (xo) =
E Badd" vi (Barart o x= (s,a, ), (-18) - -2((1x))
1
1 7 E Bandr |Ba=z(+)s) 1m (s, a, 11 (2(+)s)]
Next, we are going to further upper bound the right hand side using Lemma B.I
Va.i Va.0((so)
V..V2 S max [Baz((1)) V (s. a, .lloolll) (-Is) s2(-1s)]lz
< (1 72
max (-1s) - (2(-1s)]11-
We take maximum So conclude.
17

---

Under review as a conference paper at ICLR 2022
Lemma B.4. We have
2y
1IQ - -Q || S
71- max |b (+1s) =2(-1s)]11.
Proof. We note that by the definition of Q it follows that for all 8, a
IQ (s, - ( a. =7 Σ (V vo.v2(s)))
Jensen's incquality, and the previous lemma gives the result.
Lemma B.5. Let 24 be defined as for all s.
2++1 (-18)
where P is defined in 4 In particular,
((zx(-18), 04+1(8,)) }) = arg min 1100+118,,),,00 + 2()(())),
=(-1))
Then, holds that for all s,
(++s) 2e 20(1s)]l1 S ne100-11ls.
Proof. By the update rule of 24, it holds for all that (for example, (Teeng 2008 Property 1))
V D (-1s), 2x(+ss) + 1 :), 2,2(()))) (+11(+)))) 2 O.
By plugging in = z and using three point identity gives
D( (+)),, (-1s)) + ((z((11)), 2+11 S n (0.41 2((1s) (+1()1)))
By and Cauchy-Schwaad inequality gives
(+++)(1|s)) 2((13)]11 S mell0+1(s, blo.
The result follows by [10 (s, loo S |10tt1lloc.
Lemma B.6. We have that max, V Vu..8- = 0 iff au is in the set of Nash equilibrium points.
Proof. Recall that we say that (x","") is a Nash equilibrium if for any x,
x. S. I T..Qu....... y & =Q y*-
In particular, true when we plug in x Fk. = Uk-
Next, by definition of min operation, one can bound min, xQui and by the definition of max operation, I Bu..a.a. y. I max, Zy Q In sum, we have
min x Q S x. S. yk x. ut.Qu.. y S xn Quall ye S max I 2
(10)
7
Of course, by definition, for any v, y, V = xQ*wy.
This is easy to see: let 3y = x. for any v. which a Nash equilibrium, then max, Ve.. Va..s. Now assume that max, V = Va.V. then by (10) it must be that max, VeEW VRL. 2. Hence Fę = T..
18

---

Under review as a conference paper at ICLR 2022
C
ERROR PROPAGATION FRAMEWORK
Error propagation of generalized policy iteration for Markov games is given in Perolat et al. (0055)
Notation.
We define the Bellman operators following Perolat al. 20155)
Tep V(s) Σ a.b
x(cls))((ls)r(s...))) +
Σ
st,0,b
(s)(s) = max Tx. y (s)
TV(s) min max (s).
is easy derive that these operators are contractions in 6o norm with constant 7, See also Perolat et al. 2015): ; Zhao et al. (202T).
We find the one-sided Nash equilibrium as Daskalakis et (2000) and Zhao al. (022)) max V (8)
I c.
This in contrast to Wei et al. 22021) that shows the rate in the duality gap. Two phases are characterized Perolat et al. 2015)
Phase Tzx Vx-1 == TV By using the definitions of T, Tu this corresponds to max T Ton.y Va-1 min max T2,y Va-1,
(11)
y
where
Te, Va-1
Σ x(als))(Uss)((sssba)
Σ =ldss s',a,b
As Vi-1 is fixed, this will give a standard matrix game for all By using stochastic algorithm, are going to make the output z4 to be an approximate solution in expectation, therefore we write
E ImaxxiQu
- min max x x Qi = (s).
(12)
where the expectation over the randomness of the specific algorithm used to generate zk. In our analysis, we bound the stronger quantity, which is called duality gap
max Qi min x 07 12 2 (s),
by the definition of Nash equilibrium since min, x Qi- S min, max, x Q2 19""
Phase Vi R (Tz, V Since Tи, is contraction Perolat et al. (2015): Zhao et al. 2021) as m + 00, for any V, Tı, V - max, V Let us denote the best response as V and the approximate best response as yk- We want to bound
V (s) -V (s) = (s),
(13)
where the expectation over the randomness of the algorithm used to generate yk-
Then PPeollat
al.
2015
Theorem 1) states that (where max, =1Q2=10"
ming max, x Q 1 (s), V.n.Bi (s) (s)=
Em(s) max (s). (*()) - 2(7 7²) C1,6D sup 1|,
(1 7)2
AE
+ (1 (1-
2
|lgll
k.1 min( i, 1/boll,.))
sup JELLM]
(1 7)2
1
where
(1 - 7)2 Σ
7" - n/th i=1 j=
19

---

Under review as a conference paper at ICLR 2022
with
d(ul 21.81
cg(s)=
sup 21.8t....,,, R.33
do
9.0
For given state distributions u, let define the concentrability coefficient Perolat al. (2015)
p 21.0 ...p.
sup 21: ر.
sup
=: Cp.p < +00.
In particular, by upper bounding (g( Cu 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
En(s) max (() (s)-
('()
2kCu.
||5 11,0
sup
7-7
jE(0,
+ h:Coo
||/] + 27
sup
(1- jE(1.A)
1-7
where also used estimation from (Zhao al.
2021 Lemma 2).
One important point here is that we will be making sure the inequalities these stages hold in expectation. This also pointed in Zhao al. (2021) with 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 Perolaa et 2015) and in SScherrrr al. (2012) where the derivations in Perolat et al. (2015) build on. In particular, the relations in (Perolat et al., [0155] Lemma 1) are linear and therefore, would also hold in expectation. Then, derivation of (Perolat et al. 2015, Theorem I), the arguments in (Scherrer et al. 20122 Lemma 2, Lemma 3) are used. Tracking (Scherrer et al. 2012 Lemma 3), we see that after taking the total expectation, the bounds become
2kCuu
Σ m(s) max (s) vs)) < 1-7 jE(U,K-1]
sup I
kCua
2n*Cue 1-7
(1-7)
sup
| +
(14)
JE(LA]
where Eg.j and 6o.j are defined in 12
Remark C.1. For simplicity, throughout the paper we take a, μ to be the uniform distribution and hence replaced Cu.o by its worst case value (S). As mentioned in Munos (2003), this value can be much smaller in general.
D MARKOVIAN BIAS
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 aperiodic and irreducible (Lan) 2021 Khodadadian et al., 20221b. In this chapter, we give an informal expla- nation 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 (202 1b; Bhandari et al. 20188) for Algorithm [ and Khodadadian et al. (2021b): Zou et al. (2019) for single loop NAC.
We going sketch the arguments for Appendix F.I which will be applicable also to other policy evaluation routines.
Recall that by using the oracle for stage we can write
F F(O.)(s, a) p= (s)s) (n. Σ (((bls))rss...b)
Σ 2c00s))(slss..0000l. (15)
20

---

Under review as a conference paper at ICLR 2022
and
F(O,. Sn) e(sn: a,) (Oa(sn) an) r(sn: Oni an)bn) - ~ (
This time have Markovian data stream and denote &n (5n, Uny Ony 8n+1) Unlike the i.i.d. case Eg, FO,, 5n) + F(On).
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, En), On 0+);
where we take conditional expectation in Lemma As we can no longer compute the expectation, we are going to identify the error term
(F En), 0n 0.) = (FF(O,), - -.)) (F((On) En) - F(On), 8n - -O))
err(n)
We now separate the error of Vk-1 and identify the Markovian error, since we sep- arately handled the error due to Vi-1 in Lemma 3.6 Let us define E()n.En)
e(Sn; (n)) (On (8n; (nn) r((n, on; bn) - -VVx-((8+11)
err(n) =FF((mn En) F(O.). On 0_) (FF(((F(n))))) En) F(Bn: 0.).
((b.)En))
We notice that the last term in the above bound simply -T(e(sn (V== (+n+1) Vk- (Sn+1))) )),0), On - 0.) which can bounded as Lemma 3.6. Therefore we focus on the Marko- vian error which is defined as [(0m2. En).
We will argue as in [Bhandari et al. (2018). First, it is easy to see that as in Bhandari et al. (2018), 8n + F( En), On + F(O,,) and + On - 0, are all Lipschitz. Therefore, follows for some constant C1 that
IC(0,, E.) - C(On-r, En) S Ci 10 022-112- By triangle inequality and using the update rule 0 On B,, (On. En) along with Lemma B.1 give
3C1 n
((On, S ((0n-7;6n)
+ 1- (=
Σ
3,
Next, we bound (C((n=7, En) as in Lan 2021 Let Fn be the filtration generated by Eo....g ,n.... En-1 and note that On depends on the same randomness as Fn-1 for all In particular, by tower property,
EC(On Ex) E(F(On-T) - F(On-7: En), An- En),0n-7 04)
-B(F(On-r) ( n-
(0n F/
On 0.)
- E (0n -. En) F Fnn
Cp
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 al. (2018) by picking T mis
log(1/e) log(1/p)
min and if n < mir and using the step size rule of 8, which decays as 1/n, the same as Bhandari et al. (2018) : Lan (021) 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 well- studied. In particular, Zou et al. (201)) introduced the technique handle Markovian noise for SARSA. These arguments are used for single loop NAC in Khodadadian et al. (2021b); WW et al. 2020): Xu et al. (2020a), which also applies in our setting for Algorithm S] similar to how the above arguments apply in our setting for Algorithm I
21

---

Under review as a conference paper at ICLR 2022
Algorithm 5 Single loop NAC with a game etiquette
Require: Vi such that IIVo V=0.v0 I S for 1,2,... do
Stage 1
for t = 0, ..... T do
Sample (st, b,, se+1); with policy pair Ir. observe by, r(se, Rc: 8141
Se41
0 of Bre(s,, (0) (s 0t) r(s,, ae, bb) (Vo-1(+(+1))
0% = 04 Bic(se, bi) (s,, by) - a(, -V4-1(8(+1))
[Tt+1(-1s) (6+1(11s]] (1))
P(ye(-1s), -100+t
Output 2i T Σt Stt-
Stage 2
for t 0, ..... T do
Sample (5t, az, br, s2-1. b(+1) with policy pair Iv. Dt. observe st, be, r(s,, ae be), se41, bi+1 M++1 Vt e , be) (v) b,) r5t,, ar bt) (1 b(+1))
W++1 wt - [Bre(st) (s)( r(st, at, by) - (w((5(2))
[++1(11s) (-))( -180+1(5..))
Output yı = Dr. Vx = wi+1 where E [T] is selected uniformly at random and V₂ Vanil
E SINGLE LOOP NAC WITH ETIQUETTE
Theorem E.1. Let Assumption hold and be state distribution. For Algorithm 3 for the output of x-player
k.C.o
VISI(IAIIE BD)
1
EE somp [max F (sn)] - (s0) S
T1/4(1- 77)
(1
(1-7)2
2 min (1 - 7)
S SI B
/SS((AA V [B])
1S| [SIVIA B
+
7)
A
min min (1
7)
3
min
V
1
V
+0 (**uno
+
(1 - 7)2
X (1 - 7)²
(1 - 7)
11-7
which gives Ô (m1)) (1IM11(
sample complexity.
(4(1-))20 Am Xu )4
Proof. Inserting the results of Lemmas
E.7
E.11
and
E.14 to 14 gives the result.
E. PROOFS FOR STAGE 1 OF SINGLE LOOP NAC WITH ETIQUETTE IN
In this part, we are going to formulate and present the results for solving stage with single loop NAC. Unlike Zhao et al. (2021). we do not assume to have an unbiased access to Va-1- Therefore, have stochastic oracle involving V4-1 which is an estimate of Va-1- We characterize the error from this term and note that the goal of stage 2 will be to provide this oracle Vi-1 with small error. Therefore, the results in this part will contain the error term EEIiV=1 V
E.1.1 FORMULATION
Notation.
The problem is for all s
min max Σ adals)y(lls)Q0-sssaaaa = QQ" 2(1ee) ((1+)) a.b
where 1x = r(s, r)s P(55)s.., P.
where also defined x², "²,"", Q
22

---

Under review as a conference paper at ICLR 2022
Here, Vk-1 is fixed (independent of 2, y and iteration counter t), therefore the problem is stan- dard matrix game, with restricted access to game matrix Qk- a, b). In particular, V4-1 R3 v 1:9h-1 For all the equilibrium condition is for all y
0 S 22 Q S x² Q2-2-10
For lighter notation, we refer to Qk-1 Q since it is fixed during the loop.
At iteration & of solving this matrix game, we will need the oracles (-1x) a, b) and ( Q(s a, b) for the z player and y player, respectively. This part symmetric.
Let us write the oracle for variable by using the definition of Q(s, Qu-1(s, a, b):
0 (s, a) B (s)) a()
(16)
Σ () + Σ
Given the sampling matrix (iag((r)) @ (M) as in Lan 2021 Sec. 5.2), where pr is the steady state distribution under ze, Mes for the critic, define the operator
(O)(() = p= (s))) (c)))s)((((ss) Σ (c
Σ (u(0s))(//1s (17)
which, by Assumption I is strongly monotone with Ag and we would like to find Oz,, such that (O", = By (16), the (s, a) (-))) 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 V/-1, we have the stochastic operator with the estimate V2-1 and by sampling & (st, at, be, 8141), St ~ pri.ll, a z1(((s)), b, yc(+(st), 8141 ~ P(. st, ae, by)
Fr(Oc, Ex) = e(st, ai) (Oc(s), a.) - r(s,, at bb) (V--1()411)
By assuming we can sample from the stationary state distributions pr..
Eg, (e(().E)) + c(se, 0e)7 (Ve- (86+1) - Va- (
= =F((O+) + Σ (1)
b)e(s, (Va-1(s') V vo-)(6') =: F(0)) + 7 m.m (V - Vz-1)
s,a.b,"
F(O,) + 6w.t: (18)
where we defined the matrix Pa..gr- Above, the first equality is due to
Eg. [e(st, a.) (fc(se, an) r(sn (V+11
b,ts,,,b,s))ele (O -r(s,,,)) -)),,a,)--7Ve-- -Vo-1(55)) s,a.bs'
Σ
r(s, (s) ((((sss)) -((s,,,))r(s,,,b))) 7Vo-1(s'))
s.a.b.s
((((()) () mn(bls)r(s, b) Eutt--nnnnnS/0000MM00SM Σ m (s) a) Oc(3, 8.0
where the last line is due to En,r vi 11 (, a) and
(), = 0, a) Es. Pr(s' bls,a) =
Σe, ( = P(5ll,,,,
23

---

Under review as a conference paper at ICLR 2022
E.1.2 PROOFS
We will drop the superseript on 8", , as the algorithms are symmetric, so we will only analyze one case.
Lemma E.2. Under Assumption 1 stage of Algorithm
let 3:
1 min 11/2 and mu 13/4 Then for the critic computed
T
2 VT
2 + 2(1 + 201+log1)
E 1e11 0.
0,
110
T
(A )2(1 - -/)2
16|S||||(1 + log 7)
4721S|1A|
+
+
BIIV V2
11-1
vT(1 - 7)
(Xmmi))
Corollary E.3. Extructing only the dependence on Amins |S), |Ab, T gives
|S|AA
|S||A|
B 0
00,11125
VT (1
+
(A )²(1 - -7)3
+
(1
7)
+
(X9 (Mmin))
Remark E.4. Different from the standard critic analyses, we have to account the additional bias coming from only having Vk-1 instead of real Vi-1-
Remark E.5. Important point here exploit strong monotonicity of F, defined in 117. make the error term E| - appear instead of the worse term E [V Vk-1ll which would deteriorate the complexiry.
Remark E.6. With some extra work, we can obtain a step size Bi not depending on X similar Khodadadian al. (2027b). We do not pursue this for brevity and keeping the analysis simple.
Proof. Let us recall (s, a) = Eb (-1ss) (s, b) 16) and that Fi.O..) = 0 by the definition of F, in 17 Moreover, 0.41 02 B, (0., &t). Analyzing the update rule of critic in the standard way (for example see (Hong et al. 2020 Proof of Thm. 3)), gives
|0++1 0.,e112 110 0,.e112 23, 23, Ex), 0,,) (01
(19)
We will take expectation w.r.t. to the sample (st, de, bt, 81+1). conditioned on 0,, ve, Vt, and therefore on fr,, and use st p We also note 18) separate the error due Vi-1 and derive
e, (O., O2 0.,)) = -B((F((())).e 0..e) Be ., Or 0.,)) |P (V V/- 1)12 Be 10, 0x.ell?.
Br2
< -FF((F.())).0) 00,s) +
21 min
where Ps..g. the matrix denoting the probability matrix multiplying Vi-1 V/-1 in 18 and Sv,t = -PP.. (Vę-1 Vz-1) and we used Schwarz and Young's 's inequalities. We can use
standard inequalities to estimate |Pa.. (Ve-1 V ll < [S||A|||Pr... (V--1 - V4 V/-1) 1)l <
[S||A||IV>- 113. and take Eg, in 199 by using the two estimations above get
S
Eg |10 - 0,,1113 = Ee, 110 0. 23, 0.,,) +
11 - 11-1122
X
3. i 110, 0g.el12 + L (.(e, (20)
For the inner product, would F,(0..) = and strong monotonicity of F, (an estimation similar to (Bhandari et al. 2018 Lemma 3)) to get
23, 0 0..)) (..(.. F.(O..),, O,,)) 2 23,2 1 -0..
(21)
24

---

Under review as a conference paper at ICLR 2022
Using this estimate, taking total expectation in 20 and using Young's inequality the term in- volving |00 0,,el? gives,
B E1 02,112 S (1 aa) AeAmin E 0. 0,,t-113
+ +1L+1/a)(1 Be ) -0,1--111 3 (O,, Ex]1
E Vk-1 V/x 1/
X
3.
Picking a = 2(1 -1 min)
due to Br choice, and using |10,, - 0,,0-1112 with ensuring 5, Σ Aimin
(bb(s)) - y4-1 (b)=)( 6) S ||S|| Es (yn(bss) ye- (bls( S
2 // - -7) max, (1)((-1s) 1)-1((1ss) with Lemma B.I give
B110,41 0x.el12 - (1
Bl[0, 0x.e-1 S F. (0,,, Ex)1 Bed
|| + (1 - B,
E max (1b((-1s) y1 y1-1 (-1)(1)))
E V
V/ 11
We only need to show that E (max, (-1s)- - -- (11 is small. This easy since we use small step sizes 7/c for the policy update. In particular, the update rule of xs will give by Lemma B.5
|| (-1s) x (-1+))] S 7h vel10z+111 1oo
and by the symmetrical update for yr. holds that I|ye- (-1s) 3e (+13)lI S n/ 10040001 bl This is a de- terministic 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.
BiAniin 2
El|0.+1 0m.e13 S
B110,
0x
12 + SA (.,,,
8|5|| A 1
3,
+
El V - V2-
B, - -
We plug in the bounds from Lemma B.1
B. min
2,3
8|S||A|1/
El10+11 0x,el12 S 1
El00, 8 1,,-1112
+
2
(1 (1-
3. 7) 1
30711511AA1
E V V4-
X
Picking 7/2
6 and B. x
11/z. 13/. the recursion will be u,+1 (1 cooo/// + C,
Therefore the final bound is
0c+1 - 0.,112 <
2 110 00,0112 vT
3
4(1 + log
T
(1 )2(1 - -7)2VT
16]S|[A|(1 + log 7))
+ 4 S
+
EI V V2-
VT(1 7)
(A
Lemma E.7. Denote Fem
Er De and your =
+
1- Vt. Let Assumption
hold and
For the actor computed stage of Algorithm 5
log |A||B]
4
T
max I Q' xQº Voun 5,2= (2.9)
+
Ell05+1
0. 00
T1/4
(1
2)73//4
2 T
+
Σ
E 0%
0 0% (22)
T t=1
25

---

Under review as a conference paper at ICLR 2022
Corollary E.8. By plugging in the bound for T Σi= B1 0x,eloo0 from Lemmna E.2 after Jensen's 's inequality and by noting 0g and of admit the same bounds, and by extracting only the dependence on Amins |S|. Al, y, gives
1 O
VISKIAIVBB)
1 O
max Tou Q¹ xQ" Your (2,=(2,))
S
T1/4
(1-
T1/4
Amin (1 - -7)
+ V
7V
PVSK(A V [B])
(23)
A
Remark E.9. We make sure BIIVV=1 1llo0 is small by the estimation of Vk-1 in stage 2,
in Lemma E.14 Lemma E.17
Proof. Recall the notation x QQQ"V"
E.,b x(dls)y(b(s)QQ(sss) a, First by definition of Fou and standard arrangement for duality gap, it holds for all
T
T Σ
om U² - xx' Q²
1
Σ
(10)
x(11))
T 2m1
T
tm1
T Σ a [Bo v(1ss) ve(-1s) (B Q(s. xl1s)) - xr(-1s))]_ (24)
We are going to bound the inner products in RHS. From the update rule of 2 for all xx-ss) A, it holds that (see (Tseng 2008 Property 1))
(V [ (+s), (-1s) + n. (s,,), xz41(118))
By three point identity and using the notation
((2((1)), < ss) + ni (() x++1(-13)) + (7 - 0,,((s, x(11) (-1s))
(25)
We bound the inner products using since 20-1s) A),
and Young's inequalities and Equation (
To (0c41((), (s, x,(s)))))))))))))))))))))))))x 2-11(113) < 2m|100+1 - 02,eloo, ne (o. ((((1s)) Iz+i (-15)) TI (0.,(((,,) x.(())))))))))))))))))))))))), x<(-(s) + T (0., x-(ss) Je+ (-16))
2 vi
S (0,,0,, ) x (011)) - (+1)) +
10.,111 + D(re+ (-1)) xe(+1))
Using these estimations in 25 gives with (s, :) = E (1)))(1)066 Q(5, b) gives
1
z(.(s) + ((0(11)) < ((x(11)),{((11))) (110) 21 ((
7)
+ +1110++1 0., 1lo0 + "t
2 0,,
We sum the inequality, use Lemma B.I and max,. ((a(-1s), - log |A].
1 Be (-1e) (l,) (), x(-16)) S m
+ log IA|
T1/4
ΣT 4h 2(1 - 2T
2 2| 0,,eloo
We use the same estimation for the other player, since it is symmetric, to bound the RHS of 24 Then, we take maximum both sides w.r.t 8, 2, take expectation and bring back superscripts of xr, Or since will have error from both players.
26

---

Under review as a conference paper at ICLR 2022
E.2 PROOFS FOR STAGE 2 OF SINGLE LOOP NAC WITH ETIQUETTE
Remark E.10. Stage 2 is asymmetric for both players. As we are computing best response to player's 's policy remains fixed in this phase, it only computes Vi-1 to be used in its next stage step.
First, we going to show that while running this step. y-player construct its stochastic oracle without access to policy or actions z-player. Then, as the best response problem is essentially 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/-- Main goal this step is that have characterize explicitly the error [|V
V= as it is used the stage 2.
Note that this is generally not done in single agent setting as the goal is to compute policy. How- ever, here our main goal is to have access an oracle approximation V2- = V rather than the output policy Dr. therefore, we keep track of Wt that tracks this value function with explicit error estimate (see Lemma
E.2. FORMULATION
Notation. Here, the problem is to compute best response where the other player fixes its strategy. Let us fix zy and denote the best response as y Here, since Zς is fixed, it 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 updates can be calculated by not knowing policy actions of Zg.
For NPG updates, we will need to compute at iteration 6, (=, b) = Eawas(-1a) Q (s, (s,a, b). Writing the Bellman equation and using the definition of value functions
Q Qu (s, b) r(s, a. b) + +7 Σ P(s'ls, b)
b) + Σ P(s'ls,a,b) b) a',6/
(a((d (s',
We note (.,((',)) = (l 0...011 (8', a', B') and take expectation of previous equality with a ~ n& (-1))
(s, = Σ ==(ab))((s
Σ
P(''ss P(s'ss, a, (60
s'a.b'
We use the sampling matrix (as operator
Lan
2021
Sec. 5.2)) diag(p*...)) & diag(N:) and define the
(1))(((s))) = p - (30
uc(s, - Σ cs((al))((s,a,b)
7 Σ s'
0. Strong monotonicity of F. with constant N follows 2 and that the operator Tr, v(,, y Es.a, I ()) P(alsss(( P(s s. a, by (b') (b')s')v(b', s') is contraction in too norm, (Zhao et al. 2021 Lemma 1) (Bauschke et al.] 2011, Example 22.6 and 20.7). We define the stochastic opera- tor after sampling & (st, o2, be, St+1, b(41) with st p a 2x(+(sc). b, (((-)s)), 8411 ~ P() at, b.), bet1 ~ (e(.
such that Ff (v.
from Assumption
E. Ex(lls))r (ss.s))ssss... b) +
FV = c(se, be) (pr(st, bt) r(st, Ct, b.) - (8111111,
and as we assume we can sample 8; ~ p Eg, [F (v), F²' (2:). In particular, we see that as long as St, de, be, St+1, bet are estimated in the prescribed way, there no need for ūe update to the actions or policy of ay for (y (Mt&&, be unbiased estimate of FY (vz). It only needs to
27

---

Under review as a conference paper at ICLR 2022
its own actions be, bu+1, r(5,, bb) and 81+1-
Bgg (2),
E
8, a, 0,841 = = b')e(s (uss,, r((s,,,) yes .6)]
a,a.b,'',b
Σ
p g (s))a(a)))) (awp://pppooooooaaaaaaaaaaaaaaad
-
s,a.b,s' b
Σ (3) (1)(ss) - =x(als)((s.a,b)
Σ d'a
I
(26)
The same estimations as Lemma E.2. without the bias from Vk- as we have unbiased samples will give Lemma E.11
Let us define the corresponding operator for learning state-value function
V (s) = Σ
(blals)) + Σ x puddss
a.b
s',a,b
Similar to the Q function, can define Wa,t Vaas and the operator
(w)))(( = pm.. (s) (wi(s) Σ a,
Σ In Ix(als) b)wr(s)))
s'a.b
By Assumption 1 this operator is strongly monotone with X the justification of which is the same the F. operator defined above. We also note that Fr (w.,c) O. The corresponding stochastic operator defined as
Fr (we, Ee) = E(st) (we(s)) r(sti ar be) - (we(s(+1))
where p" xx(-1s), by (-)- 8841 P(-|s, a, b) and assume we can sample 8, ~ p
RS, FF (we:: E()] (w.).
E.2.2 THEORETICAL RESULTS
First, characterize the critic of stage 2 in Algorithm 5 denoted by Vt, wa for action value function and state value function, respectively.
Lemma E.11. Let Assumption / 2 hold. Let BY for the critic computed by stage 2 of Algorithm
Bu
and nje
Then
Xu 177.
Au 117
(0
[S|[B]
+ |S||B]
}
E Bl - 12 VT (1
+ +
T
[1-
(Ne )2(n) 7)1-
(1 (1-
T
10
S
|S|
T
Bllwe1 w.lll
7)2 + +
+
7))6
Remark E.12. Using the same samples for 0 and V. does not seem to cause a problem since the analysis in Lemma E.2 only takes conditional expectations conditioning on 0r and uses that max, (-ss( Ze+ [ small directly by small step sizes 17.
Remark 1. V. is not used in the stage 2, but it is estimated to be used in the stage and also to make the bound of Lemma E.7 small since the bound implies Elllet1 - V.a. = V-IlV-111
Va-1l Ö (1/T1/2).
28

---

Under review as a conference paper at ICLR 2022
Proof. Let recall vs,,(s,b) b) Be (-1s) (11)) a), and wa,t V
We expand the squared norm
||t+1 p2,,1l2 ||l 1/, v4,,1 2/ (Fr (vr. E.). vn,)) + 1.1 (ve, E.) We take expectation w.r.t the randomness of &e- = (st, az, di, 8142, bx+1) and use from 26 that
Ee, (v,, 6x) = PY))..
Eg, 1| - - = || - vr.e112 - 23, (vi), us - Unse) + Be, Fy (Me, 2012 By strong monotonicity and (V..)) = 0, follows that
(PT 14- ve,a) (FF, (v,) - Fy' (Vo,)). vara)
2 Xmin 1 - V/, 11..
We use this estimation and then Young's 's inequality to obtain
Eg, [P++1 Ve, 11 = (1 28, (min) ||pz
V2,el12 + S. FV. E2)1
2
S (1 )mn) || 1- +
|| - 1 3. U (vs Ex)l (27)
3
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 (s, E (a Q QThhit (s,a, a, b)
||,., - 1111-112 & // - 12,0-111o0
B max (115) (s, a, -s. s,
S v [S|[B] max E (1)))()))) (s, a) (s.. s,b
< V/S||BIIlQ QRA:9e 1110
< (1 (1- max (1s( Øt (+1s)111
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 ūe (-1s) gives [ - ū (-1s) nelustalle
by Lemma B.5 Using these estimates in (27) after taking total expectation gives
El|pe+1 2e,1112 (1 Be Eliu v. +
B, min (1 7)
+ F (v,, E.
We get the result by using the same argument as the end of the proof of Lemma E.2 by also us- ing Lemma B.1 to bound [v,, 2:) and ||
The proof of the second inequality exactly the same except that in (7). instead of I Va,t- we will have ||w..r we,t-1/| ||| and we will therefore use Lemma B.3
Next, we will upper bound V - V which is single agent problem I& is fixed and we showed in this section how to do the policy evaluation without knowing the actions of vg. The next
lemma will be proven similar to single agent settings (Hong al. 2020 Khodadadian et al. 20216). Lemma E.14. Let Assumption hold. Let Sy miin 1172.
miin 217z and Ut
1374 Then
for stage 2 of Algorithm 5
T
EE,ona (VeL. - VRL (50)) V2L.U(8o)) S log
T
(1 T//4 (1 - 3/333/4
T
2
+ T(1
Ellp++1 - v1,
7)
1=1
1
(0
V V
+ Ō
VT
+ v B
(1 (1-7)4 }.
(1-7)²
X X (1
7)2 E.1l
where the second inequality follows by using the resulty in Lemmal
29

---

Under review as a conference paper at ICLR 2022
Proof. By the update rule of Di+1 for all (--ss) E A, (see (Tseng
2008
Property 1))
D(y(-ss), (+s)(+)s) - D(v(-1s), (+)ss) m (2) (((u(-ls).u ( -++1(11s)
1-11(-1)) (1)
- - )++1(1ss)) (1 (1())
We estimate the inner products by Cauchy-Sehwarz, Young's inequalities and Equation (
(e(2411s..)) - (.. (( 3++1(11s) _ 2m, ||+1 22,elloo
and
no (1)))(()))))1(11)) B(+1(11s) -nc (. [r(+)s)) - mn (, )++1(1s))
<-n )) s(11)) (-(s)) nē elle + ((Bc+((1s),
2
Consequently, by using the definition of (8, b) B (... (8.0,b)
(Banax(1s) Q St (s, as,,,D) (s. u(1s) -((1s)))(((ss)))) 1 D( 0(+1(11s)) = D(y((1s).
1
m
17t
na mll. (28)
+ + vx
We sum the inequality and use max D(y ((2)(11)))) S log [B] with KI. divergence, to get
1 Bawzy (-1a) (t.)) b). ve(-ss)) - D(y(-1s). +
T1/4 log B
T
miT
2
Σ -t=1 Tle 2T 7)2
Σ
|141 v.,1loo +
(29)
T
Let us recall that yi is best response policy. By the performance difference lemma
VzL.ii (8o) - V (500 = 1- sndd (Euwax(())) Q (s,a, :) vr((1) - (-15))
As Th and yt are independent of and fixed throughout the loop, in 29 plug in y y and take aoidao ot
30

---

Under review as a conference paper at ICLR 2022
Algorithm 6 Reflected NAC with game etiquette. (See Algorithm
Require: Subroutine Poli Policy-Eval (see Algorithm
Algorithm Algorithm 4) Initial policies
3o: yo: 5/0 for k = 0, do
Stage 1
for t 0, 0, ..... T do
[V V/ | 8:), P N,
10%+ [+1 [policy-Eval Fol. N, k- (h)
F441 () (20 0g
Me+1 = (-s() - 11 (8, 0 (s. -))))
Output 23z Σi=1 Zt.
Stage 2
for t = 0, ................................ T do
V141 = --PPoicc-Evvlll (ox, Dr, D, N, )5)) U++1 (-|s) = (-))( (8,))
Output yv Vr. where & (T) is selected uniformly at random.
Algorithm 7 Policy-Eva (See Algorithm
Algorithm
3 Algorithm
Require: Policy pair x, iteration counter N, oracle Va-1, step size | for 0, 1,,,,.., Sample 8n ~ (-) an ~ x((1sn), bn ~ v(-1sn), snt1 ~ P(- an bn).
do
if 3 A then
F(ón. 5. ((sn) (sn) - r(8n: an an, bn) (0((8n+))
else if 3 = 3% then
F( {n) e(sn; bn. (d (0 (sn, - r(sn, an bn) 7 7Vk- (8n+1))
else if 3% then
Sample also bn-1 ~ (((18n))).
F(on. e(Sn; bn) (n)((n
(on (Sn, bn) - r(8n; On bn) -0 (8 but1))
@n+1 = On- B, (nn::n)
Output: ΦN
F PROOFS FOR REFLECTED NAC WITH A GAME ETIQUETTE
F. PROOFS FOR STAGE OF REFLECTED NAC WITH A GAME ETIQUETTE
F.1.1 FORMULATION
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 xr y)- Therefore, we can no longer use GDA that we used for single loop NAC, and the techniques from Lan (202T) 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 Mirror Prox (Nemirovski, 2004 Korpelevich 1976) or FoRB (Malissy Tam 2020)) and extend the ideas from Lan (202 to these more advanced algorithms characterize the bias and variance separately. Also, would have to do tighter analysis for Vi estimation.
31

---

Under review as a conference paper at ICLR 2022
To obtain the desired oracle 0,,c(s, b) (a as in 17
p" ((00).))000x"0((((1((((
((.,)) (2a6))--3phh (5,
[r(ss) (.a. (30)
We recall that Fi is strongly monotone with X under Assumption Moreover Fi is Lipschitz with Amax We refer to Appendix [..II] for how the oracles in the algorithm can be computed without accessing other agent's policy or actions. Moreover, we do not put subseripts 0 8M as the estimations will be symmetric again.
F.1.2 THEORETICAL RESULTS
Theorem 3.2
Let Assumption
1 hold. For Algorithm 6 for the output of x-player
Cuok k
|S[(|A) V [B])
E. [max [max V=x.2( (50)) (1 (1-7)
y/
T( - 7)2
min (1 2
(1A)( 2
|/||A|
+
(1 min 2 7)2
(Amin) (Amin) 12(1 - ?
||||B|
V|S||B|
Ch.op
7) N2 N2 (A
(1- f
(1 -
Ca Ch (B)
which gives O
sample complexity.
(2 77 min Aran
We used Remark C.I to bound Cp,o 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 MMlitsky & Tam (2020); Nemirovsk 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.
will bound the variance and bias of 0 as an estimate of (s,((s, b) = Eawzz Qk- (s, o, b). As this routine is fixed, therefore we drop in an inner loop (indexed by n), the policies we sample, consequently
We first analyze the policy evaluation routine in Algorithm 6 In particular,
the subscript. The proofs of these lemmas will be similar to Lan 2021) except the additional bias we have due to VE-1-
Lemma 3.6
Let Assumption
hold. Let 80
X (n+no)) for no 2 1. Then, for Algorithmms
and 7
|S|A 22
S Ammin 1
E 0 0 0,,133
5
E V-
- V/2 11.
N )2 7)
Proof. Throughout this proof, B[-] will stand for conditional expectation B[.[ By the definition
of 0..
||0,1 -0.ee12 1|0,, 0.,111 - (F En), On - 0_.e) + (0.. 1.
We will take expectation E.G,, where En = (Sn, On, Un, 8841) is the sample at iteration n of Algo- rithm 7
E.. F(n. = F(O,)) + + (Ve-1 Va-1).
as in 188 where Pa.., was also defined. As we stated, we omit the dependence of F, to t as t is fixed throughout this loop. Thus,
Eg,, |0 - 0., 11 = 100, 00,113 - 23, (F(m)) On - 0z,))
-2,nn (Pr.. (Vk-1 12-1),,
1),0r 0n -Ox.)) + (00.
32

---

Under review as a conference paper at ICLR 2022
We strong monotonicity (with F(0..c) = 0) for the first inner product and Cauchy-Schwarz Schwarz and Young's s inequalities for the second inner product (exactly as in the proof' for policy evaluation with single loop NAC) to get
7m
Eg, ||001 02,e112 < (1 23m
110, On
|
(V
1)
+ Br No Mmi 100n - 0x.112 11 + Te, [(on:: En)
Bn 2 |
(11-Banmunn) 110,, 00,
|V - V1- + 8 E5, | En) 12, (31)
X
where we estimated || Pr.. (VR-1
1 as in Lemma E.2 We will use Lemma
B.1 to upper
bound [[ f.) S (1- We define O, such that O Amin) I - with O O
1. We multiply both sides of the inequality with θ, after taking total expectation, to get
1 02.e122 S E 02,t 0nnnrr1111A4
20n,/%
EIIVE-1
Va- 1l. + 71-
min
Summing the inequality gives
N Σ
20 5 7)2
N - - s Ool101 0..e112
BIIV V/- +
Ami
n=
n=1
Using the definition of 8, and setting @n. - Bn Amin) 0 gives O, = θ
(no (Moo)
Let us Og- θ and bounds from Lemma B.1 for 01 0z, 11
2no + A
8N
BllON 1 1 < (1 - (N + (NV + no 1) (N + na) + 7g 1)(1 - ?)
37
El| El| V2-11120-
+
(2
We now analyze the bias for 0.+1 in Algorithm 6 Let us remark that the bias analysis for Vi-1 in the next lemma is critical and it is the main reason that we get fresh estimates for Vk- 1 in this algorithm, in contrast to the stale estimation in the single loop NAC variant.
6x2 Xean
Lemma 3.7 Let Bn
where no
Then, for Algorithm 6 and its subroutine Al-
x (n+no)
gorithm
SAA
10|S][A| (Nhi.)) )2
|E[0 - 02 50
IE [V(V
Vo-
(32)
7
Remark F.1. Since the bias term the algorithm" analysis will be Lemma F:2) [ [2 On.ell
we will have to take the square root of the result of this lemma. If Vs-1 is estimated before It. then we will have in the main analysis E [V Va-ill which will have the rate VN. On the other hand,
1
if we estimate VR_ freshly as in Algorithm 6 then will be able to use the better bias bound
[[
V = (1/NN which seems be enough for our bound.
Proof. We are going to take expectation of the recursion
On+1 On - Br, (0 En),
first w.n.t sample En, where En is as the proof of Lemma 3.6
Ee, On+1 0n BnlEe, (0, En)
0 - (B, - BAy (Ve-1 - Vn-1),
where we used (18) where Ps., also defined.
33

---

Under review as a conference paper at ICLR 2022
We will now take expectation [[]] We note F and Par.gi linear
El0n+1 [xc] = E[ [2,] (E(e,((())))))) P.yPo... (B[Va-1121] Vx-1).
We denote On = E[On| [2) and = = ( [B[ [ - Vk-1) in the above equality which makes
the recursion an+ = fn - Bn F(B,) -3, 3, We then have
||0,+1 - 00,+113 = 10O,. 02,1112 23,, (Dn), On -0a.) - -2,n 0n 0z.t)
3/3
|| ((O.) ) + 3332,002 (33)
2
where we also used Young's inequality to split the term ((0)) + 8112.
By strong monotonicity and Lipschiteness of F along with F0.,,) = 0. 2B,, (F(O.), ,, 0n - 0...) = 23, (F( - F(0,,)) 8n 02,1) 2 2/3 1 min| 10, 0x.e113
(1 = (0,)) - F(O..)) - > 10 - 0,
By Cauchy-Schwarr and Young's inequalities, it follows that 23, (ō,0, On o,,)) 1
Bn Annii 10,
0,,e112
+
28m
101..
Using these three inequalities in (33 gives
A
3 In min + B8 max
3
2B,₂
|10z+1 01,e113
1
110, 0,, 0,, .,.112+
11012 + 1011.
2
2
Xa
We now use no
622
and An
2
estimate
(X 1z min
Muin ( (n+
3,3n (>
3
212 max
3
21 2
Bn 12
min
3 Anninn
2
2
Xmin (12 + +nn)
g 720
Therefore, the recursion is
20,
|0a+1 01.r113 2 (1 Mina) 110, 00,r
|18112 + 1112
X
This recursion is similar to
(31 in particular, by noting /3, S x and bounding ||0| simi-
lar to Lemma E.2
|Pa
[
Vi
[ar] V2 Va-1)113 < |S||A|||P P... (E[V-_1a - 1)-1) I
|S||
-
[re]
Vh-1 11
||0mt1 02,e11 - (1 - Br Amn)) 10,, - 01,e112 + 5,.1STIIA|
- V1-1112.
We finally define O, as in the end of the proof of Lemma gives O, θ no with , and sum to get the result.
3.6 in particular, 2₂ (1-3nnAmii)) = On-1
where O, O 1. We multiply both sides of the inequality
the 11)
We now have to estimate the bias and variance of the estimation of V/-1 in Algorithm very similar to Lan 2021). Unlike Lan (2021) that derived (11/N3) bound for the bias, are going derive a O*) bound which will be sufficient. Let us also note that the previous two lemmas had addi- tional bias not present in Lan (202T), however the next result does not have this bias and therefore the arguments in Lan 2022 would be enough. We provide a brief proof to be self-contained.
Let us recall that Va-1 you 1.34 1 and by sampling s, pth 1896 1, On Ix- (-1sn), bn
yk Vk-1(-1 ((11))), 8nt1 ~ P( an bn), the oracle
fr (Wns En) = e(sn) (wn(sn) r(sn, an bn) 7wn (wn( (8n+1)),
satisfics Bg, Fu (wr: En) = F (wn), where F is defined as
F (w) = 1 (s) (w())
Σ xz (al-nall))u--- b,
Σ = b)w(s')). (34)
s/.bbb
where Fi-,(V: (Vg-1) = and also as before F is strongly monotone with X We will drop the subscript of Fw since l is fixed in this loop.
34

---

Under review as a conference paper at ICLR 2022
6X-
Lemma 3.8
Let Assumption
hold and B
Amin (nooo
with no
(A (x
The variance and
bias of Vk computed as in Algorithm
satisfes
|S||A|
E EIWN - V/ 12-112250
+ N(1
71-2)2N2
2
|S||A]
BB [2n]] V
y)2
Proof. For the variance, have by taking expectation w.r.t. En
Be,, | - V/- 112 = I|wn V 2,3,, (w En)l. wn Vk-1) + Eg,, F (win En)l
By Eg,, SS,.F((uu (wn {n) F (w,), F (V O, and strong monotonicity of FW, similar to previous proofs for policy evaluation,
Ellwx+1 1 = (1 2B,, Xm Bl|wn V F En)
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
Wn-1 = Wn - F (wn).
We now unroll the expectation until xa and use linearity of F"
E(wi+ [2.]] [[wnn(Zra] 3,, F (R(unlare))-
Denoting wn (n [r)] gives the recursion Wn+1 wn Br F~ (#n), and therefore
||-n-1 V = || V 12 2,, (1% (wn) Bn Vi-1) ((x))
We will now use Lipschitzness and strong monotonicity of F and that F=(V+-1) 0 and similar to Lemma 3.7 we obtain the recursion
||0 V12
Amin + 32 ||0n
V4-1112.
By the choice of no and 8n. similar to Lemma 3.7 it holds that 2,n B X2 A 2 Bn AmAmin. By defining ,, the same way Lemmal 3.7 and summing the inequality gives the result.
Now 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 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 MnlMiitsk & Tam 2020), deterministic oracle also computed at each iteration. On the other hand, the analysis in Böhm et al. 2020) uses unbiased oracles with bounded variance and 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 "LLyapunov-ike" function
h 1 ((
(+1s) n(0,.c+1(ss)) 0c41(1, x(1s) E++1(-1s))
+ 2
(t))) x+((s)) (35)
We call this "Lyapunov-like" since it is not non-decreasing. Moreover, unlike Malitsky & Tam 2020), o, 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
1 7/(141 (-|s) IE(:+1 (-1))= zr(-1s)
6,, (100)1(11s)) (11)) v(-ss)).
35

---

Under review as a conference paper at ICLR 2022
Lemma F.2. [See Lemma 3.44 Let Assumption 2 T Ei=ı Vt and let 1j 8
hold. Denote Dou 7 Et= It and you
1-7
1 D4
EI grv
max Tour "' 1f x""""""
x² Q² Your O
+ O
E C1IE(0+41 0,,ell
1/T
T
T
1
BBI10++1111 O +110, 0 0,,--11 11? T
+ Tτ
max Σ ee + =2,1))
Remark F.3. When D is KI. divergence, we have max v1. D(y,, 1/22 & log [B] and equivalently for the other player. Therefore, we have the bound
log B 1 1-7/ )
V6 T
00.0
Ty
O
log |A| [og|AA1
Corollary F.4.
We use Lemmas 3.6
3.7
and F.6
v
|||A
VSSILA
T(1 T(1-)))
+0
+
[ - Va- 1l
(1
7)N
Xe Xaiin
+
|A||A/
1
+ |
BlIV% Vo-2113)
( min
)2( - 7)
(2 )2
We add the bound from Lemma
3.8
A
VSSIA A Xmin
VISIIA
T(1 -2) +0
7)N
(1 2
|S||A|
1
|S|IA
|S||AI
1
0
(1 (1-7)2N2
( )2( - 7
(M
N(1 7) [[1 7)
We now refine the bound by only including the dominant ferms
T(1 T(1 ( + +0
|S||si
No (1 - 7))
S N2 - (> )2 (A )2 (2 )² - 7
|S|2|A|2
+
Remark F.5. By Lemma 3.6 and Lemma 3.7 the second and third term will bring
O (++ E|(E[[A-1((rd Vn Vn- We will in the next lemma how handle error terms ex, ea and will use the bound derived earlier for B|[E(VA-1(0)) - Va-ill-
Proof. By the update rule, it follows for all and x(-18) AA, (V (-1s), 2x((ss)) + ((20441(8,)) - 0e(s, 1), x(11() 2141(118)) 2 o.
By three point identity,
D(z((1s), s D(a((ss)
+ (7( (s, ()), -)), 2(42(115)) (36)
We now manipulate the inner product by adding and subtracting 0,,+1
((20)++18. 01(8, )), x((ls)
= - ), - (141(11s))
+ m(0r+1 - (( -
= (n(041188.) - (s.,4 (1 -s (s. - xe(-
+
+ (n (.(())))))))))))) 2141 + (, - (37)
36

---

Under review as a conference paper at ICLR 2022
The first two inner products in the final inequality will telescope if we can replace ic+1 with f.,, in the second one. For this we have to be careful with bias and variance. Let us take the second inner product
((0
zx((ss) = (s,),, (s x(1ss) (1s)) +n(00++18,)) (x, ) (r(1ss [s)- - (=)))s)).
Now in this estimation, we will add and subtract terms involving
[2y]] to obtain
1(0 -) - (s(s,),, x(1s)) - (x(sss)
= n(0_. - (. - 2z
+ (B(00++1 12x1]] - 0,,, .01ss) - (+)ss + -00 - m=((1s))
-
S _n(0...(s.)) - 0, (..)))) -x
21y [ - 0. + e1 (38)
where the inequality is due to Stuchy-Schward 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
-(0+)(5:))00(())...)).) 2((1) -11 s 111100+2(5.) -1 (+|s)] I 2n² (100+1(5,)) - (s, )I& + (s,,,(s,-) - (5, )13 + 10.,.-((..)) - (s, )1&c]
+ - | - (-))(1 (39)
As (s) = EBrgge (-1s) (ss, a, 6), we have
(8,,, - lloo S max (((s,a,b)llu.. (--1(-1))ll= b,a
<
[Iv((-Is) yt- 1-1s(-])]l1,
(40)
where the second inequality is by Lemma B.1 and the first by Jensen. We join 38 (39). and in (37
(40)
((20++ (s (s, - S (0
0 -), ,, - xc+1 (-1s)
m100,((,,)) (s(ss x-1ss) =1(1s)) + 2n/|
- 0, + t1.
167²
+ 41)² [110+1] 1 + 110,,--1 - 0e112]] + (1- (1s) 1-1ss)1
1 + + (1( xz+1 (-1s) + 17 (0 , (s) z 1+1s)) (41)
(++1(11))) (-1s) < (1())2(11)) and similarly for the term involving difference of and y--1-
We note that by Equation (8). (-1s) re+1
We insert 44 into (36) by using the definition of 4;
(8. ((+1(()) x(-1s)) + $i+1 S $ + e1, + 2n)|E(0,,+ [x,] 0x.elloo
+ +47 [1|041 - 0, + ||0.,-1 - 0c11331
32n²2
+ (1 7) D(vr(- (-)((-ls)) (s) v1 2
We sum this inequality and use the definition of 0.,+1 to obtain
T
$6 +3
T-1
Eb (+18 Q(s,
b), x11 x(-1s)) <
+
e1,t
T
T
T 1=0
T
4n²
T Σ
2n|1E(0+1120) - 01, +
[11e211 - -0,,113 + +110,,-11 01113]]
T
T
t=0
1=1
1
32n²²
D (-1((110 (s), 1-1s) (((a((1))),xx-1(11))
T 1=
(1
7
37

---

Under review as a conference paper at ICLR 2022
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 01+1 instead of the true oracle. First, by the symmetric estima- tion the y player, we obtain the similar inequality. For making the comparison, denote the corresponding oracle as 8a (0 in the previous estimations correspond to (²). In particular 0% *,1+1 (s,
will
b) (--1))())))) (1, a, b), and the corresponding Lyapunov-lik function $
7 T
E B- (11 Q(s,) u(1((s)))) 1-+1(11s)
L
D
U.T
Σ t=
C2P
T
T
T
4np²
2n||B|6++1100
11 +
[100411
6 10, + -110,,1-1 0.11100
T
T
Σ T t= (1 7)2 (()(1))))
1
32n
1 (t-)))))()))))))
-
After summing up the two inequalities and recalling that we bound the RHS of (24 we pick v S "8 to cancel the last terms in the last lines of the estimations. Since we estimate 6, and 0 in the same way, their bounds as derived in Lemma 3.7 Lemma (3.mm 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 æ; y. take expectation w.r.t. state distribution and total expectation w.r.t. randomness in the algorithm and use the definitions of Zoot and yout to conclude the result.
For the error terms ci,t, 62,,, we will use the technique change the order of maximum and expec- tation from the literature of stochastic primal-dual methods (Nemirovski et al. 2009 Lemma 3.1, Lemma 6.1). Let recall their definitions:
6 (-00+1(-11)) E[00+1 s0-1s) (-ss)
2, 1 (-1s) E (1))a v(-ls))
We will derive the bound or e and the bound for e2, is symmetrical. Lemma F6. We have
T
log |AI
1 T
ER
ER
max
C1
Σ
A 0.+1
11.
T
T
Proof. First note that (-1s) - EiO-1 (-1))(=))) (1s) does not depend on x and by the tower property of conditional expectation,
EI ga 17 (00+1 E(0c+1 (+1))<=1), (-1ss)
LE,-- - ( ((0 (-1ss) O.
Therefore, we have to estimate
EF E max
(0c41 [1)0
Let (8, ( (1)(0+ (-1s) 1-
First, we note that Esnr(s, [ar]] = 0. Next, we
define the auxiliary "ghost" process
1++1(113) arg (in
D(x(-1s)
Note that 3t and 2, depend on the same randomness by definition of ă,, therefore conditioned on Its 3t is deterministic. Standard mirror descent analysis gives for any
(m, x-((s)) S ((a(11s), D(a((1s), (n.(s,)), (. [Ime(-1s)
38

---

Under review as a conference paper at ICLR 2022
We sum the inequality take maximum and then expectation
T
EI or max
(m, x((1s)) s D
+ t=1
EE E (-ne (8: (+(ss))))
T
EI ER me (-1)))
By the tower property and that T is deterministic conditioned E ), (c(-ss)) En= E[ (x)] O.
on we
have
Recall the definition of ne and use Young's inequality with Jensen's inequality to get El|ne(s, )11 E 110++ (-1s) - (-10+1(-1))
s 2Bn 16+ (-1s) - 0n,11:s + 2E, E(0
s 4E+)(100+1((16))) - 0.
F.2 PROOFS FOR STAGE OF REFLECTED NAC WITH A GAME ETIQUETTE
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 part of the environment. Therefore, the development in this part will be similar to Lan (202T). Let us restate that the main concern in this part was make sure that Th updates do not require seeing the policy 2y or the actions z-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 20211. 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 Vi, similar to Lemma 3.8 Let us recall the Bellman operator for the oracle Va,t (owzz(-l)) Quh. (,,a,)) that the update is using:
(r, b) = Σ (a(a)s)r(s,aab)) +
Σ P(s'l a, b) (a)s))( (b') ((.
"',a.''
We use the sampling matrix (as Lan 2021 operator
Sec. 5.2)) diag(p=t..t) s diag(Ue) and define the
(v))(ss) - (b(s)) b) Σ (xl(cls)((s,a,b)
Σ s'a.b
())n(11))))) WD]. (42)
such that Ff 0. Strong monotonicity of Fr follows from Assumption 1 and that the operator Tv(s, = E. xx (a)ss)))(ss a, + + Ex.a. 3e (a) 8) P(s'|s. a, b)p. (b')s Te s') being contraction in foo norm (Bauschke et al. 2011 Example 22.6 and 20.7). We define the stochastic (-1s))). 8141 P(-sst, az b.), be+1
operator after sampling St pek.i at (-(()))), Ve( (1+1)
= =((s)) be) (Pr(st, bt) r(st, ar b.) (5641,15
(pr, 5d] = F. (vt). In particular, as long as St, at be, 9 are estimated in the prescribed way, there no need for Dt update see the actions or policy of r& for Fy (ve, {t) be unbiased estimate of F. (v²).
and as we assume we can sample 9; ~ p Ee, [F
We note that unlike the NAC case, we are having an inner loop to estimate V.a.- At the point of view of this loop (runs from ..... N 1). VA,t e fixed.
Lemma E.7. Let Assumption
hold and Bn x to)) stage 2 in Algorithm 6 satisfies
|S||B]
Ellux - 2 5
+ N(1 - (2 }
(1 N
39

---

Under review as a conference paper at ICLR 2022
[ - ue 00 2|
(1 (1-7)223
Proof. For the variance, we have by taking expectation w.n.t En+ (5n an bns Snt1. bn+1)
Ee, Vu+1 Unst 1 l| u- 112 - 2/ (B... [F (vn, En)], ve,1) + Be [ (Uns En)12.
By Le, Fx (V En) = (vn), F. (v,,c) = O, and strong monotonicity of F?",
E P1++11 - ee,e112 = (1- 2,3,, (min) Eljy, r,,ell2 + 3 Ex (Vn.En)ll En)
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 En gives
Bg. Ma+1 = Vn - (vnn)
We now unroll the expectation until and use linearity of FV¹
E E[ 177] = Elun [We] Br, FP (EE (ue))
Denoting Pn = PP [e]] gives
Pa+11 v-, 112 1| Vv, (F (Vn), v..e) + (D.)
We will Lipschitzness and strong monotonicity of FŞ and that PV (v.,,) 0 and similar
to Lemma 3.7 we obtain the recursion
| - v1,e112 = (1 111-2:4 2,,,, + +B,)2n))) 110 - v2,
By the choice of ng and P... similar Lemma 3.7 holds that 2,3,./in Ba 2max 2 Bn, Nain By defining ,, the same way 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 hold and
O. For the stage 2 of Algorithm 6
1
ve (. (so) - -V0ki8t S
E.
E
D(y (-1s)
(1 - 7)T
snud
"kist
T
T
2
Ellva,
1111
+
E E||E[14+1130 - vl,e
2(1 7)2 T
1
1
T
1=1
Corollary F9. We use the bound from Lemma F7
to obtain
1
B
VISIIB
+0
+
(43)
T(1-
(1-7))
N(1 ((1-~))(WW
12
(1 (1-
Proof. By the update rule of ūt+1, follows for any 8, 17 TTeng
2008 Property 1)
D( < (()(1)). (((())))))(D)ii)) ( ( -o (-18)).
- (44)
We manipulate the inner product
-7(1441s (s, 0(-1s) De+1 (-1)) = = (1.,
(-)((()))))) (-1ss
= - 7.1(( (e(-1s)) - (1 - (+))(
-n(et11 (.) (+(ss)). (45)
40

---

Under review as a conference paper at ICLR 2022
By the performance difference lemma and using the definition of V4,1 Eawux Quanth E (.a,,).
Vak.8ct - Vak
Si (so) =
IE snnt3 Dets (leawz (-1=) (-1=)
Q0h.0t (1, as, a, a), Dc+1 - (c(-1s))
1 Y enddi Re11 (Vs,e(s, )) 0,t11(11))) (-1s))
E
E
(Mo+i(s,) D, 1-1s) (c(-1b))
7
+ (v,,((,,)) - u41 1, "...).. (++) - mn((1)))
(M++1 (-1s) Te((1s)) - (1le,((s,)) - (s,
2
B
7 smd
l1 (-16) Th (11)))
(46)
27
where the last step uses Cauchy-Schwarz and Young's inequalities.
Plugging in y = Dt in (44) and using Equation
gives
-7 ). (-ls) 3e+1(-1s) 2 D (-1s), Fe+1 (-1s) + (1))) ((((s)
2 11ū--1 1 (-s) 5. (11s)]1
which implies that (M++1 (s, (). - - श7 1 (-() 2 0.
Recall that d (s) (1 -1 Σr 7 PP 1st s|so), therefore 1 y S d (so) S
1. Using the two previous incqualities in 46 gives
1
(ve+1(s.). (-(sss) < V - (s).
11 (-1s) - -e (1((
21
+
2(1 77 ||,, - 12211220
We use the final inequality,
445 and in
to get
(s, 0.0(( [e(((s)) + D(((-1s), (-1s)) 1) s ((0((1s))
- -n (s) + 11²
2(1 - 7) I| - 14 - + -(V - m=-((,,),0) (-(+))) (47)
In view of the definition Ux E Banze( Qe..8e (,, a, :. performance difference lemma gives (1 (V( (so) - V=L. (so)) = E
snd (s,,(s,)) yi (-1s) - -v((ls)), Plugging in y = yi in 47
and taking E snde of both sides give
1/1 - (VV (8o) - ()s.B((so)) + enatty ((uu( (())))))())))) (s))
n22
< E
((vi(t1s), ((((s)) - V 8. (s) + 2(1 7) || Ve,t 11
+ ( - 1/+ (3, :), Te - (-() (48)
Now we take expectation w.r.t the randomness in the algorithm, use tower property. the fact that conditioned on T. (-(ss [e(-s)) is deterministic, Schwary inequality, 7(-1s) E A for any
y. S. After those steps, we note that d does not depend on t and sum the inequality over t to get the result.
41

---

Under review as a conference paper at ICLR 2022
Algorithm 8 Single loop NAC with a game etiquette and (-greedy exploration
Require: Vi such that IIVo V 1 Se for 1,2,... do
Stage 1
for t = 0, 1, ...., T 1 do
Sample (st, de, be, se+1), with policy pair dt, dr observe 8r, bi, r(5e, ae, bi), 80+1
0++ = og Bre(se, a.) (0f((e, ar) rss,, au bb) y
0+ = =O-- Bic(ss, be) (0 (st, b,) ar, b1) (V411(8411))
[1241(11s), )6+1(-1s]] = (2(((()))) 1 P(yc(-1s), -n (s,-))
Output 2% 2 Li=1 Zt.
Stage 2
for = 0, 1, .,.,,,, T do
Sample (st, Qr, be, Sc+1, b(+1) with policy pair Fy. it. observe st, bt, r(st, ae, bı), 8441, bi+1 Pi+1 = it- - e by) (5t, bi) r((st, a, by) (e b(t1))
W241 Wt (ree(s)) (5) r(s,, a, b,) yos, (s441)
(-1s = (-))((1)) (1,,))
Output yk = Uz. Vi = Wi+1. where E [7] is selected uniformly at random and V Vak.ee
G GREEDY EXPLORATION TO REMOVE ASSUMPTION 2
G.1 SINGLE LOOP NAC WITH 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 2027 Remark 1) in the single agent case. We are going to Ç greedy avoid Assumption
Let us define the modified policies with greedy exploration
5 [A
C [
(als) (1 1 ())sss))s)
(bls) - ()b(ss) +
Now are going to sample with the é., De and the algorithm will read Algorithm g
G.1.1 STAGE OF SINGLE LOOP NAC WITH GAME ETIQUETTE AND Ç-GREEDY EXPLORATION (SEE ALGORITIME
Let us recall the notation and introduce more notations. At iteration k solve
Q' b) = Q(s, b) = r(s,a,b) + Σ P(s'ls, b)
The problem is to find Fout, Yout such that
E max oou Q'v x Q'
x """
Now define
= -((,,.))
Σ a( 18th (6')
sample with greedy policies, at the stage will learn a 1 1. So will have the
oracle Vi-1 such that [ V || is small.
In this step, with the abovementioned oracle, we expect to learn
0= (5, a) Eaniy Q²
(s, b) Beaway (² b).
42

---

Under review as a conference paper at ICLR 2022
Let us continue with z-player and drop the superseript, (,,((5,a) a) (1
Σ (a,)
( (((ss) b)
b) (s').
6,
Therefore the operator is
(s, = -f (s))x((as) (,(s,a) - E (((b(s)r(s,a.b))
b
Σ 1/
(49)
As (r(+1s) 2 S/ and 0c(-ls) 2 S by definition, we have that P is strongly monotone with eT where @ is the lower bound given in Assumption which holds when the induced Markov chain is aperiodic and irreducible. Let us call this X 2TÅI-
We state the main result which follows by the results we will prove afterwards. Theorem G.2. Let Assumption ! hold. By combining Lemma [C.11 Lemma G.4 and their corre- sponding corollaries, can show Ö(E sample complexity for Algorithm
Proof. Insert Corollary G. and lemma G.11 into 14) to get the result.
Remark G.3. In single agent setting, Khodadadian al. (202 obtains Ö(e-5) with greedy exploration, to avoid Assumption Our estimate is an e factor away from this rate.
Below, we analyze the actor in the stage of Algorithm g
Lemma G.4. Let Assumption 7 hold and ne
(1+7)077+ S= 7:77.
Then, for the stage I of Algo-
rithm S
T
log |A|
log |A|
T
E max
Σ (Ennyg -x)))
5
2
Bll0i+
02,1
T
Tmn
Tirr
T
1=1
B
8yE(1A) [B])
ΣT 11
+
(1 7)
(1 11-7)3 7)3
2T 7)2
Corollary G.5. By using ne S. we get the bound
o AA
1
1
110 - -
+
+
(1-7)
T6/7
T
1=1
Corollary G.6. We can plug in the bound of 0 bound for the other player get
11, (see Corollary G.8
and use the same
AAI B
SSIA
SIIA
E max Fout Fou -2""=""' 2²= Your 5 2²
(T17
T1.577
+ T2/7
7)2 +
T1/7 - -7)
+
O(v
S||
vān 18 1 11 (50)
Plugging in the bound for the final term from Lemmal G.10
| B
SSIA
|S|IA
E max Fout Q² -===="" Your 50
29.0 "
11 2T17
T1.67
T2/7(1 -7)² TL/T(1 -7)
|S ISAVIAI
(51)
(1-7)1.3 1.5 (.5
which gives the ( complexity for stage I.
43

---

Under review as a conference paper at ICLR 2022
Proof of Lemma C.4 Let us denote x 22(+1s) and similarly for variables y, 2t, Dc. 8. Let us with our new notations
recall 24
T (Bawyy Q8, ),,"
T BBbng (,,,,))),) ;),,,²)
Font Q'1 x² I Yout =
T
1
(Buwar Q(s, vi) - (Bo-ge Q(8,,, -2,]]= (52)
T
We have to convert this to the game when the matrix is Q
T
Font O² - x² x²Q' Qoyyou
Σ
(Bawar (a, ).v² -vf - (B (+, -x7)
zi}
T
t=1
+ Σ Baawy (a, (2, vt) (Ebnyy
)1, -2, 2;)-
For the error terms note
(Banz; (a, Qa "1.88 - vi) s 2/1 -
2| loc
Σ P(s' (s, D (1V (e
27 max
a
2 1V V-
4 V
(53)
(1-
where the last step is due the Lipschitzness of the value function due to performance difference lemma and that the policies - 1 and Tx-1, yk-1 differ at most by Ç.
With the similar estimation for the other error term, have
Font Q'y vout + Σ (Buwat
vi) (Bornr (2' (1, xx - x;}}
8C( A|| V [B))
(54)
- 7)
Let us denote
= = Ebnny (:),)).
(55)
Note that this notation not consistent with previous sections. Here by 0.,. we mean the quantity we need to upper bound (54).
By the update rule of Ir, for any x
D(x", x & D(x", xz41) - D(17-1:2;) + 10 x241).
Let us estimate the inner product
nel0
x(+1) 10: xx x..)) + T/e (0ī x1t1)
= M/ (02,1,
10,11, x0 xz) + n (0i+1 02,,, x²" - rf) + m (0 - a(41)
As we will be actually learning 0r we will further manipulate the inner product
ne 100011,2" x(+1) = (0, (0),,. x" x²) + +T (0ām1 0; 02,, x" - -x²) + m7 (0", - 0% x 2;)
17 (0; x(t1)
44

---

Under review as a conference paper at ICLR 2022
Let us estimate the third inner product on RHS
Te ne(0.. n.t - ,² x= 2²) - 27p 11",, 10
= 2m max
(b)() - -
a
4n 1
Σ (e(bss) (.(b)s)
1 An
(1/1/BI (b(b)))
4n |BIS
(56)
1-7
We use this estimation and Cauchy-Schwarz and Young's inequalities to derive
00, + 4n, |
no 16 - 2(+1) I n0 x² - xz) + 2ne110%11
1 1-7
T 11
+
11. +
+
r141
11
2
We use this estimate in the main inequality with strong convexity of Bregman distance to get
49:5|B] ///
n of x²) Dix" xx) Dxx", x441) 2n.110++1
0,
1-7
2(1 7)2
We divide both sides by m. to get
(0 x - x²1) D(a m1) S D(#
1 .xt1) D(0",
+1102++ 02,ello +
4C|B]
1/8 2(1 7)2
7)
1-
We sum this inequality and (55) to get
log A
log |A| TTp
1
B (), - x²) s
+
Σ
0::1 10
Tmn
T
1=1
4C|BB (1 7)
ΣT T -== 7l
2T 7)
We next analyze the critic in stage I of Algorithm g
Lemma G.7. Let Assumption hold and 1)+ critic of stage of Algorithm
(147)077 C 7//7, 3r (1+7)0/738 2amm
Then, for the
[SIA T3/7
1512
E 0. 01,2-1133 0
+
+0
T4/7(1
7)
(2/7 (M
)2(1 7)2
8|S||A
| - Vda 112. (57)
(i
Corollary G.8. Recall that Ç 7-7 and do =P//AA/
1
E 0
0_.-111 112 112200 0
[STIA T3/7
+ +0
|15//1A12
- )
)
+ 1 (22/T11
T
TT/7(1
7)2
t=]
V 112 (58)
45

---

Under review as a conference paper at ICLR 2022
Proof of Lemma G.7 have that (see (49)
As sampling with Zt. V/ and learning (s,((s,a) Benug Q2 b),
Fc(O..;) = O.
We also denote
Et) e(se, (0, az) - r(st, a1, by) vVk-1),
where 8t, dt, di, 81+1 sampled according to Se, Vr.
Let us derive
|10+11 - 01,1112 110, - -0.,.11 28) -b..) Ff(l E.)l
Now, by i.i.d. sampling &t ~ Sr we have Pgg, (r,,,, Ex) (., 7 (Vz_1 -V -(be-1
as in 18 We have by strong monotonicity and F((O,,,) =0,
2g Et), 0,,,) (F((). 6, 0.,)) = 2B (F(()) - Fr((..)), - 228 0.
-...))
The recursion becomes
Eg. |10++11 - 0.,e113 < (1 (1- 23,2 min 110, - -0,,el12
2y 2. (V--1 vha- 1 1--1--1,, 1), 0 -0,1) + B, [[ E.)1
By Cauchy-SShward Schwarz and Young's inequalities for the inner product
-2 (V V 1:th 1),0, 0r.1) S 27/Bell Ps P3.. (vz- VV-I-VErr 1.60x 1)122100 - θ0,el1 11
Be
||0: 0..0113
/1872181141
1 V V 113
2
ig
The recursion then becomes
Ee, 10+100+1 0.,111 (1-30 11-33,2 min /2) 110- 0..e112 100--0,.113
3,8 1 A|
+
1.8-1.00-11 + S,E (F
8 min
By Young's inequality,
Eg, 11100+11 - 00,e113 - (1 3rimnin) 110: -
01,2-112-
6
110,, 01,1-1112
3,50
min
+ Be8~21511
1
1.0-1
1:00 1130 + ((
0
Now we have to bound |10 0,,t-11.: 11::
110., 00.e-1112 5 / |||| 11,,, 00,e-11100
v|S|| max 0,8
EB Q²'aa, Esneg (a,
< / S
max 1102 0822111
1-7
/ S max lIvi vi- II,
< 2
where we used 0r = (1-5) + C/ B/ To show that max, 11 vi ll1 is small, we use Lemma B.5 and Lemma B.1 and have the final bound for this quantity
|
110.: - 0.c-111 <
(1 7) m
46

---

Under review as a conference paper at ICLR 2022
By also bounding |IF((.. by Lemma B.1 and taking total expectation, the main recursion becomes
24|5|2|A|212 + (1 7)2 E B100111 - 00, - (1 - Be B BBI0,, - -2,1-111++ + Be (1 7)
2/3
8,3, 1
|B| - V 180 11
+
2
This inequality gives
T
1 +
ΣΣ
EI 1 -
(10) [100-0.,--0 00,1-112 - -100+1 - -O,,
1=1
T
24 24 1/
T
2
8|5||A|
+
| || V&h 1.00 112c. (59)
T 1= (
min m2 - 7)2
T
min (1 - 7)2
(A )2
t=1
Recall that 11t = (1+7)677 and Be-
For the summations, we have E n8/B3
(++7)4/7Xg min
O(T3/T min) )²), Et=1 3r O(T3/// / /> (min). By using B241 S Be. and denoting for simplicity
a: 11, - 0, 12 1o 0 S a, S -1 πল-pحz simple estimation gives
T
T
Σ
(16.- ,, 12 110 - 0x.1113) =
Σ
1
(a.
ax+1)
B 1=1
B
(1
Q0
a++1 +
at+1
Be
Be+1
BB41
3e
1
1
|S||A||
1
1
at
0++1 +
Be+1
(1 7)2
Be+1
Be
1
1
|S||A1|
1
01
aT+11
+
B1
br+1
(1 7)²
Be+1
Be
1
|S||A|
=0 (
|SS|A4/2~1/T Sauin
$
a1 +
B1
(1 713
(1 - 7)2
Plugging these estimations into (59
1
T
[S||A] T3/7
+ 0 |5|2|112
E 0
0-.1-11.
0
T4/7(1 (1 ))4) + T4/7( min )²(1 - 7)2
T
1=1
8//||||
+ (A 1 - V Sik 112c (60)
G.1.2 STAGE OF SINGLE LOOP NAC WITH A GAME ETIQUETTE AND {-GREEDY EXPLORATION (SEE ALGORITHM
We are now going to estimate numerical sequences from Mokhtari et al. 2020 Lemma G.9. (Lemma 19 in Mokhtari el al. numbers satisfying
V 1.0
First, we need the following lemma for 11
(020
Lei b 2 <> 1. Let de be a sequence of real
Φi 5 (1-
<1-
c tt+ Φ--1 +
(61)
(t + to )
for some [0, 1] and to 2 0. Then dr converges zero with the rate
di < max( (to + 1)a, b/(c-l(c) 1)) (t to + 1)a
47

---

Under review as a conference paper at ICLR 2022
For the stage 2, let 7/2 = (147)677 and 8r
2(147)9/55 and let us analyze the critic for Vk-1-
V/.
Lemma G.10. Let Assumption hold. Let i/t (147)077 and B 2p(147)777 and recall Wi+t
and Wa,t Vi and that take output yk yi in Algorithmm 8
T
Bl - wr,ell s00
=0,
1s|
(62)
T
21-
Proof. Let us develop similar recursion to previous lemma
||@++1 ,. 112 || :. 28, (Fr
(wr, Ei), w. + Bi (Wer, E
By taking expectation, using that ~ pfn.de, we have EE ( Et) ( and Fi (wxr) is strongly monotone with & as it only requires Assumption recursion becomes
We also have Fr (w.,.) O. The main
Ex, 10+++ w. 112 - - 23,p) ||ār - a. + 8 11 (ax, 6.)
By Young's s inequality for >
(1- (1-23: 20, R., . 112 (1-23.0)1+aa) -., (1-
w.,
3.p
Let us set such that (1 23xp) aa = (1- -.p), which gives the choice a =I-23,e² with the
requirement 2 > 0. Recall that since Ba 2p(t+7)4777 we have 230g < 1 and t 2 0. Note also that (1 (1 1/a) <
2 with out choice of a. Aig
The recursion now becomes
2
E| B| - @.,el12 11 $ (1 3ep) Bllas - w
El E 1-1 - 20,111 + 33E Fy (4,, E.)1
3ip
Let us estimate the second term RHS
[ 2x,e|12 S |511(ar011 Warlloo
= =|[1|[ V
11:00
4|51
S (1 - 7)
max 110:
12
To further upper bound this quantity, use the update V rule of ht. Lemma B.5 and Lemma B. to get for all | Fi-lll S I-y. We also use that
where the last inequality is by Lemma B.3
(b) (1 <) B
2|5 m
||,,t-1 - 3.
{1 - 33
Therefore, in the main inequality we have (after also bounding the last term by Lemma B.I
4/5/m
2,8
El|@++1 20,1113 - (1 (1-Bep) Bip) Ell(; 2.,t-112 +
(63)
B.p(1 - 7)3
-1-
Note that by the definitions of Be, Mr. we have
3
ni
2p
9 4p² + 7)8/7
Bip + + 7)4/7*
37
3,
3(t
7)8/77
Therefore, we have
- (1
8|58
18
Bllai W
12+
2(t + 7)4/7
3(1 - 7t + 7)4/7 4p2 - 7)2 + 7)8/7
48

---

Under review as a conference paper at ICLR 2022
Now, use Lemma G.9 with
@: = E w - 00,1112
8|5|
18
max
20
3(1 7)3² 40
7)3
C
2 > 1
to =
4/7,
gives
|S|
E
0
50 50
(1- + 7)4/T
Sum the inequality to get
T
T
15
E
T
T
(1 - 21- + 7)4/7
1=1
|5|73/7
0
(1 7)
1=1
|S| (1-7)8
The accuracy for the stage will follow similar proof to single agent settings. We would like to bound
VoLi
by sampling = (1 (1-(())) + 5/ and (z(b) = (1)- +
Let us define the oracles and the operators
(s,(s,b) = En En & as)
Fe(ee, (s) = piu. (s) (b|s)e(s, b) ())(s, -
where pranie a 22. 8े. s' P(-ls, v' 8 and
((( an (b)s) ()(())b) Σ (x(als)r(s,a.b)
Σ saa
P(s' ss a, ()
and therefore (P.,.)) 0 and F. is strongly monotone with pL/|B| Sy Nu
Lemma G.11. Let Assumption hold. Let us set the ( and ( Ti7.. Then for the actor of the stage 2 in Algorithm 8
y yau.vi (s). <0 50
+0 -0(1-17777
1 (11 Bl - Breellox)
T
( 11-7
( |BKC
+ 0
+0
(6/7(1- 7)33
Corollary G.12. By using Lemma G.13
get the overall rate (1/TT1/7)
49

---

Under review as a conference paper at ICLR 2022
Proof. By the update rule of the algorithm,
D(y", (i+1) - D(y", , D() D(T Fi) - Ti. 1it1113 8² Di-1)
= Dy"", vf) D(v D: - n (2 32 - Fi+1) - To - 12.. Fit1).
We now estimate the inner products by Cauchy-Schwarz, Young's inequalities and Lemma B.1
(0, 11" Vi+1) - -m 3/ Vi 7/ (0 .. V/6 vi+11
- 1F, 11.3" -Vi) + Th
11, 1 2 - 1
Th
1
-me ,0."" -0t) The (D ,, 97
1i2 +
1| 1t,,,133 + +2110
vi+a Il?
2
S -m (0 (2)
11
VE 11
7)2 + 21l0r
7i 11
2(1
Since (b) (1 () (b) + S/IB). 11 De 11 - O((BK). We join everyting in the main
inequality to get
Tc ) + Dyy F++) S D + 2 |1 0 11 +
1 O(IBI)) + 2(1 7)2
1-7
We recall the definition of D. (s, Eawdy Qun: (s, a,a,, b). By the performance difference lemma
V. - v (so)
E
tn (D Vis" 82),
1
s
where yf is the best response to Zg. Note that by Lemma B.3 Therefore, we have
BB V Vaa (50) V.L (8o) S (1-7)-
V vax (50) - ( <0
+0 (1-
1
Blipit1 - -Dh, -E2,lloo
(
|B|c
+ +
+ O (887(1- 7/33
(1 (1-7))
Finally due to Lemma B.3 ( -V (so) _ 0
(((AIvIBB) therefore the final inequality
T
V (i - (sx) 5 (011-))717
) +0
1
E
El - -z -f2,ello
T
|BC
+0
+ +0
(1 (1-7) 7)
T6/7 7/33
We finally analyze the critic for stage Lemma G.13. Let Assumption I hold. For the critic in stage 2 in Algorithm 8 let Br and recall Sy = B
Au (t+7)1/7
1
| ) +0
( (117)277277
1
Σ B - -
+0
(117737717
(64)
T
T3/7
Proof. By the same steps in Lemma G.10 can get similar inequality 66
Elpa411 2..1113 < (1- (e8mmi))) Elli, v.
4 4 S
2,37
v.1-1112
+
(65)
Be (1 - 7)3 (1 7)2
50

---

Under review as a conference paper at ICLR 2022
Equivalently,
1
23c
12
O
(66)
T
T3/T
T
(11- 7)
Xmin (1 -)2
We can estimate other terms
T
[S||B]
Bi - D_, 1
+ +0
+0
(67)
T
T3/7
(1-7)374/7
(1
(1
71-2)212/7
51

---

Under review as a conference paper at ICLR 2022
G.2 REFLECTED NAC WITH A GAME ETIQUETTE AND {-GREEDY EXPLORATION
In this section, we give a version of reflected NAC without 2 in a similar way described in (Lan 2021 Remark 1). This algorithm will be Algorithm | 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/ such that 11/- V 1s S
for L 0,1, 1.1...... ................................ T 1 do
Set (b(8) = (1 ()) - B/
Dt+1 = -PoLicy-Eval(u N)
M++1(1|s) =
Theorem G.14. Let Assumption 7 holdd For 1j > the iterates of Algorithm satisfies
T
(su) E[VV((s))]] 1 711 - -1) ooddy [D(ut*,,
T
T
+ T(1 7)
ER
|VT++ (s)
V (s)] +
11
Blli,, 11+1l.3.
B
enddy
(1- T
2 1
4n
4|Blc
E B (0 [v4] - 1x +
(68)
7 T
(1 (1-
(1 (1-7)3
Proof. Recall the definitions
V-, = Qui 0,,1 Q
Recall that the update rule of ve+1 implies v/++) S D(y", ,()) D(v vt) - 7117+1.8 1f and by plugging y = ye. we get
Div + D(vi+1: vi) S - -n Vi si+1)-
By 8
S - 10 vi.1) 11 vill S - 16 - -i-1)
1
1
|bb+1 22 117 (69)
2n
By performance difference lemma and Young's inequality
1 E sn (Q ,1441 -v²)
4u++1 (so) - V (so)s))
1
snd Mets (v., vi+1 - vi4
E Benditt
(Df 11+41111111 -vi) + (Vā, - -1 vi+1 wi²)
(D (D(+1,3(
-vi)
"
I 11+11133
2n 11 v/ v6l13]
1
? sma
2
Therefore, we get by using 69 and 7 -- S d (sv) 1
10441. - vř) S Vu++1 (s) - V (s) + 2m
1
vill?
")
|1 11411200 (70)
2(1 7)
52

---

Under review as a conference paper at ICLR 2022
We use again the definition of yt+
D vi+1) I D(v", vvt)
D(vi-1: v() 155 1² Vi+1)
Dyy .2() D vi) 7184+1, 32" -vi) - Vi -V(1)) (71)
Let us (70) and
(P 1+++1 1,33" 1/2) (12 10 -vi - n(p2+1 12,,, v1.)
on 71 to get (along with (8)
(1 - vi)
D(y vi 1) S D(v "("",8?? + +/ ( (VV++
-V)(ss)
n?
+ 2(1 - 7) ||u,, - 1/111183 - 7//0/11 - '². - vi) (72)
Since by performance difference lemma, (*()s) - V (80) = 1-7 E
aadt (V2 (V2, yh yi)) we
plug in y = y² and take expectation in 72 w.r.t. d%:
711 (V* y I E
syd Diy v22) D(y wit2) + nBB sndy [V (s) [V]ss]
1 | 113 -Raway [n - 1,,0-3²" - -vii)
2(1 7)
(73)
Next, we take expectation w.r.f. randomness in the algorithm and use tower property to get
17(1 (VV - BEV" (so))) & EE
[D(u** .0()) - D(y "(t"",,(++))
sodd
1/2
+ +BB siiii
[V (s) (s) + 2(1 Bllva, - 1110
-FR shdd [n<BB(U8+2 lucl -v 1² --i))- (74)
We also note that by Cauchy-Schwarz inequality -17(1) [3c]] 12,,0 31" wil) s 2111[(++119l)
Ux Ix--
By triangle inequality and Young's inequality
n 2(1 7) ||,,,
172
Pz+1 12. + 2m| En/|E(Pe+ilul
elo _ 1- |1, 1241
n
+ 1 |10,,1 ve,e113. + +2)l [vo] - 10, + 2nllue, 1l
< 2
4n²
1|0 11411130 + (1 71-
(max 1100 v(ll1)?
7
4n
+ 21y E8 1141111) elooo + (1 7)2
max 1101
y2 ll
where the last step used Lemma B.4 and definitions V/., Qu, Di,e Q as in (5). to get 10+- - Hell1 < BKG. With these estimations, 74
We use the estimation
becomes
V=0))) - (sa)) 5 17(1 - 7)
1
EE sn [D(r"*",,0 , D(y v/tt1)
2
+
EE
sond [Vu++1 - V (s)] +
(1 7) Bllpa,. in+ 1130
1- El|E[(,- [y:] - Ge,llox
7
4n/ 2222
+ B
+
(75)
(1 7)6
7)3
We sum over to conclude.
53

---

Under review as a conference paper at ICLR 2022
Note that will learn Pr,, by sampling with St. As in Appendix G.I.1. the strong monotonicity constant of the operator
ps (v) = p0: (b)) ((s. - r((,,)) - E P(slls, (10((11)))))))
is A = -1--)gg/(1 (see also Lan (2021)) Moreover, F (Va,t) O.
Lemma G.15, Let Assumption 7 hold and Bn Vain no) stage in Algorithm satisfies
|S||B|
ElleO 1 50
N(1 - 71) )2
||
| boll - 11 50
7)
Proof. We can use Lemma E.7 with v = v, Xmin Xmin and F(v, {) = (ss,b)-r(ss)) -e (/ where s ~~ pir b ~ (r(-ss), s ~ P(- b), b' ~ (o(1s') to get the result.
Corollary G.16. Let Assumption 7 hold. Let <= (1 - 7) / The sample complexity of Algo- rithm for obtaining globally optimal policy in single agent MDP is O(IB) [1((1 - -7))11 2 cA))
Proof.
T
V E( S
1111 - -[' E
D(v" (5))
T
swidy
T
+
EE
V (s) - y (s)] +
1
E Blld,.t 11211133
T(1
7)
enudi
(1 71-
1=1
1 7 T
4//
A|BIC
B [vr] -x,eloo +
(1-7)3 (76)
(1 71-
By using Lemma G.15 in the previous lemma with Stmnn = - // gives
1
T(1 - 7)2 (ML1
4n/ B|2c2
4|BKC
Σ V (5o) E[[V((80)) 50
+
(1 7)6 +
T
(1 7)3
+0
17
(1 | B
|B|2
+ (1 - 7)
B
(77)
(1 71-
2)
N(1 - pfpp²²
By picking 7 = (1-7) and ( = (1-7)3 / B), we get the complexity (1--)) 13 2
G.2.2 REFLECTED NAC WITH A GAME ETIQUETTE AND Ç-GREEDY EXPLORATION IN ALGORITHM IO
We first state the main result in the next corollary. As most of the results depend on previous sections, will make heavy use of those estimations and provide brief proof by highlighting the differences and extracting the error due to greedy exploration. Algorithm [ is repeated here for convenience.
Theorem 3.3 Let Assumption Choum use Remark C...and and use the estimates in these corollaries with 14). Then, the complexity for Algo-
Use the parameter choices from Corollaries G.20 and G.21
rithm 10 ([S))((AA ( -15 -1 -1))
54

---

Under review as a conference paper at ICLR 2022
Algorithm 10 Reflected NAC with game etiquette and (-greedy exploration
Require: PKL defined in in Section Exploration parameter <> 2 0 (equal to if Assumption 2
holds). Subroutine Pol Tcy--Bu Evval (see Algorithm Algorithm
Algorithm 4 Initial policies
2o: yo. 50 for k 0,1, do
Stage 1 for t
T 0. do Define ( = (1 (als) + T (k-1(bls) (1- () + c and
correspondingly for E2,t, Dk.e.
ME iz = [Policy Eva (8x -1 N, Policy N,,,,,,,,,, ([)] Policc
10=+1: 0/+11 = [Policy- Eval (#x,,) (orvallfxxii0 2k.0 N, Policyy-vaal 1r.1 N, V22 Vz- 3.)
2h (+) = PKL (2,,())) (g, 0g
( -PKL (t, -1 20 (1,,)) 0g
Output 23 + Σt= Tk.t.
Stage 2
for t = 0, 0. T- do
(a) = (1- (a) + L (b) = (1- (b) + c
[o] 1++1 = Policy- Eval (0k, Dr. N, = 3%) MR.41 (+) = pkl (oh, (-), (1,,41
Output y/: = FR.i. where f [T] is selected uniformly at random.
Theorem Extended form Let Assumption 7 hold. Use the parameter choices from Corollar- ies G.20 and G.27 use Remark C.Too.. and use the estimates in these corollaries with 14. Then the
suboptimality gap bounded as follows:
Caok: δ6
EE sorp [max V (so) V*((s)] S
(1- T(1-7)
y
+ (32(AAI|BI)) V
|S|[B]
|B12
B
Cparrh
+
(1 ()- + O
(1 2N
(1 11-7) 33 N(1 - "1)"1
Then, the complexity for Algorithm 10 is Ó(IS)((IAIV V -16
Remark G.17. This result does require Assumption 2 which makes set of assumptions similar to Wei et al. (202T)) which also used greedy exploration. Comparing with (Wei et al.) 2022] Corollary 5), result has the same -A dependence, better dependence
(1 1-7)- We note that
even though our dependence with |A| |B| seems worse compared to ( (Wei et al. 2021 Corollary 5),
the result in (Wei al. 2021 Corollary 5) has dependence C-10 where C the metric subregularity constant. This constant implicitly depends on dimensions of variables x, y, therefore it depends on
|A], ||, (S]. Euclidean projections on the simplex. As a result, the comparison with (Wei et al. [222] Corollary 5) in terms of [A], [B]
More importantly, this result in Wei al. (2021) does not cover NPG since it requires
( is not possible. On the other hand, the result of (Wei et al. [022] Corollary 4) without metric subregularity applies to NPG, and it can be compared with our result, in which case.
our sample complexity scales as --A whereas (Wei et al. 2021 Corollary 4) as c
Stage of Reflected NAC with game etiquette and (-greedy exploration in Algorithm 10 We first recall the discussion Appendix G.I.I and include here for easy reference. Let us recall the notation and introduce more notations. At iterationn k, we solve
Q' b) = Q(., b) r(s, a. b) + y Σ P(s' ((s'|s,a,b)) b)V 1.th (s').
The problem is to find Tout, Mout such that
E max 2 2¹ v8 x Q² You.
55

---

Under review as a conference paper at ICLR 2022
Now define
a, (a = Q(s, r(s, D, 1) (s'),
as we sample with policies with greedy exploration, at stage 2 we will learn V So we will have the oracle V such that |Va-1 18 is small. In this step, with the abovementioned oracle, we expect to learn
(s, a) = Pb-;; (" b), (s, b) = Bama; (a, b).
Let us continue with z-player and drop the superscript,
(s.( a) = (0)
= - (a,
Σ (r(lls)r(s, +7 ( id (5)).
b,s
Therefore the operator
F((O.) = (s){(((( (c(2,a) Σ (hs))r)s)
Σ (s (0)))))))))))))))))))))))))))))) (8)).
(78)
As 2r(+1s) lower bound of the stationary state distribution. Let us call this S =GTĀ-
2 TA] and 0c(-|s) 2 [B] we have that Fú is strongly monotone with ºTÅi where p is the
As in Lemma we introduce notation similar to Malitsky & Tam 2020), let define 4, which slightly different this time.
T = ((x",=(+1)
x(+1) + 70 0f+1.00
xlt1) + 2 D(1411,27)
(79)
We also the following error functions and recall the definitions
61,² 1/0c+1
2r(-1s))
62,t 100 (-18) -BI0 (114+1(11)))))) 2(-11)))
(s, a) = Esng, (a,
(s,(8,a) a) Eswyy
Lemma G.18. Let Assumption 1 hold. Let 17 = 1xx
Denote Tour = $ ET and Your
1 Et Ut. For stage in Algorithm 10
E.
x''
max "0rnn'
Q'y yf" x²Q""VVV Your 0
niT
+ +
T
E [1 0,,ell
T
T
+ 0
E 010+ 00.112 + Rell0 - 0 112
+
E. EEEr max
(e,, + +22,))
T
Tn
1=1
4<([A] V [BI 4C|B]
72
1
Remark G.19. The idea of this lemma is to extract the error due greedy exploration and make the errors due to policy evaluation depending on the policies with greedy exploration. In particular, 8.n1 learns a by sampling 2,, Dr- Therefore, we can utilize the results we derived earlier for policy evaluation steps.
56

---

Under review as a conference paper at ICLR 2022
Proof. We start from the quantity would like to bound. Recall from 24
"
x Q''QQVVV You
1
Σ
(eaaa; (a, T Σ R (,,b,,,)'))
T
T
1
[[Bamay (a(a))), - vi) - (Benys Q²(,, 1), -
T
+
[00 2,2 V² -vi)
(0 N.00 x=
-x]]]= (80)
We will drop the subscript of f to denote 4 for lighter notation and derive the part of z-player. The y-player case will be symmetrical.
By the definition of T++1,
Di .441) S D(I", x1) - D(1 + n((204+ -0,,2² - -x(-1)
(81)
We manipulate the inner products as Lemma F2
(20 - 02,0² x² - -((+1)
(0ū+1 0% 0,,4,1,0 xx m(t1) + (0it1 02 - -((t)) + (0", a(+1)
(0f+1 1-,,+1,05 x² x(41) (01+1 0f, x² x²)) (0i+1 02,05 xlt1)
+ (0h, x² xi-1)
10'+1 0² 0²,141,-" x² - x((1) + (0t,, 0r x² - -x²) + (0ī41 0% 02,1, x1))
+ (0: 0q. ot x + (0 (0",141.2* x² x141).
Note that the first two terms will be used while forming t; and 17 final term will be what we bound for (80). The third and fourth terms are the error terms. We first analyze the third term
(0i+1 8 02,02 x xz) = (E 02,0, x - x1)) + (0i41 - Eio [aa). x=" - -x²)
=(E(02 0% 20 xi) + EI, S 2| [ 0 00. + 01
Next, by Cauchy-Schwarz and Young's inequalities
1
(0i+1 02 at x)+1)= S 01100++ - 0e11. +
|| zi+il1
4n)
1
s 2111@1+1 00, 12:0 + Anl00. 11,0-11130 447100,t-1 - 0el1 + | ai+ 111
4n
167
1
< 22 11c +
llve - yc- 11.. + 40110,,-11 - 0.
+ D
72
211
where the last inequality is similar to 40 when 0, yr are replaced by 0, i. and we also used ||
06-1l11 < llvf -f-1ll1 along with 8
We collect all the estimations in (8T)
1
(0",,,+1, x= - -x(+1) + ((= x(t1) (0
02 x0 r.t1) S D(x", ((;),,))))
2 D(a x;))
1672
-0 - 0;,00 - =;) + +
2|
0x + (1 - 7) llve vi=
2n 21021 - 0..113. + 417 2118 Ô 0.,c-1112.
We use g and definition of क to get
( 1. x -i+1) ))= + 4. < b + 2| B| [zy] - 0.,elloc
2112110++1 00.113 2 : 112 2
1
D(x x(-1)
32nj² (1 (1-7)²
D(vi, vū
57

---

Under review as a conference paper at ICLR 2022
We finally estimate the bias term
[B [aa]] Pe, 1 | 0,,11 + +100,, 00,e1100
|| [i]] - 00, + B| Qi Esngs Qillo
|||00=1|z [m)] 0.,1 > + |BB of Qi Ebnyy Qil 0 + |Bbngg Qi Bb Qill
|1 - 0.,1 + 2 V [B]
B|
(1 7)²
1 1-7
where the last step is by (53) and (5)).
Inserting this estimate leads to
(02,+112" r(+1)= S o x ((+1) 22|1E(0++1 [aal]-0.pp 00,111o +2n110+41 - -O,,elis
32n
45([A] [BD
4C|
+ 41/10; - 11.0
D(a x
(1 7) -
+ 1
2n
(1 >)
As in Lemma F.2
derive the symmetrical inequality for the y-player and picking 7) 32n (1-7)² (D(vi vi-1) (ar z)=)) disappear.
will make the terms
We sum the inequality along with its y- y-player counterpart and insert into RHS of (80) to conclude.
Corollary G.20. Set < (1-7)² B and step sizes as from Lemmas 3.6 10 3.8 with de gS/(IAIV
[B], An = 5
c(1-2) [A|v Then, the complexity for stage I of Algorithm 10 is ((IS) V
(1)) -5
- -5- 922).
Proof. First, notice that both variance and bias terms in Lemma G.18 now learn &,,t, 04 by sampling dt, Dt- Therefore, from the point of view of policy evaluation, we can directly apply the results we derived earlier with strong monotonicity constants A = p [||[ V B)), Awin L- The bound in Lemma G. becomes
max a Fon Q² x² x²Q' Your = -0000 D'.3""
EIE gn
+ +0
T
EE IB 00+1 0n,ell
T/T
T
T
+ O
E
0.+1 -0, + E110; - 01,--11?
+ T'n
EE
and max
C1, + =2,1))
T 1=1
t=1
4E([ V BB)
4
7
1-7
By using Lemma 3.6
we can derive the variance of ê by sampling with ft, Dr
0l - 0,.el13 5o
|S|A
1
|S|A (A
El| D VK-1 - 113-
(1->) (1 7)2
For the final term in this bound, we use Lemma and -1-1-
3.8 to estimate V by sampling with Sx-1
|
E B - aa 1886
112
1
+
(1-7)2N2
N - 7) (Sm
For the bias of 8.t1, use Lemma
3.7
|S||A|
1
E + 1|2x] - - 5 0
E VK [2c]]
18 1133 1
(82)
11
(1-7)2N2
(Xe
min
58

---

Under review as a conference paper at ICLR 2022
On this bound, we use Lemma 3.8
|
[x]
V 50
(1 7)
Finally for the error terms 6 + 6, we use Lemma F.6
T
log |A|
1
T aNd max
EE
C
An B1 -0,,1133
T
Inserting these estimates and using 2
g5/(1A)
[B]), X = =
<(1 Remark F3 TAlviB
give
EESNO max a Q² x² x2Q"youu
$ Ô
1 )
+ 8c + Ö (
(1 (1-7)
which gives the final result.
Stage 2 of Reflected NAC with a game etiquette and <-greedy exploration in Algorithm 10 Recall that in Appendix F22 we extended the result Lan (202I) on single agent setting to the stage 2 of our algorithm. Since in the stage 2, Iy is fixed, it is part of the environment and therefore single agent analysis extends in 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. are similar
are 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| (see (Lan 2021
Remark 1)).
For brevity, we do not repeat the arguments in Appendix in this case. We summarize the result in the next corollary.
F2 to extend Appendix G.2.] for stage
(1-7)²c T and step size from Lemma F. with \
Corollary G.21. Let Assumption hold. Let
- (1-7)eC/IBB (see also Corollary G.16 The overall sample complexity for slage of Algorithm 10
(((A) [B])4][[[1 - 13 -13
Proof. is straightforward use the arguments in Appendix F2 result.
extend Appendix G.2. for this
H ADDITIONAL EXPERIMENTS
H.1 ENVIRONMENTS DESCRIPTION
Bandit environment. We first consider two player bandits problem with 100 arms. All the arms give zero reward except a" that has r(a") = - and with r(b*) = The reward of the two player game is ra,, r(a) r(b). In this environment there exists pure Nash Equilibrium given by b*}.
& 1a==a"
Alesia environment. We also test our algorithms 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 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.
H.2 HYPERPARAMETER SELECTION.
In the following report the hyperparameters chosen for the experiments to reproducibil- ity. In addition, we include an additional experiment on Alesia(L,C") with and = in Figure 2 Since the eigenvalues X > A unknown, cannot compute the values
59

---

Under review as a conference paper at ICLR 2022
of learning rates 8h P. used in the theoretical results. Therefore, we simply set the learning rate as 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 reports the chosen parameters. Table 2 Table 3 Table 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 1 0.0001. We observe that critical to choose small step size to tackle the high variance coming from the REINFORCE estimator.
Hyperparameter
Value 0.01 n
0.8/n
30
0.1/n
0.023
B
0.01/n
K
100
N
10
T
10
S
0
Table 2: Hyperparametets for Reflected NAC in the two players bandit environment
Hyperparameter
Value
"
0.005
02
0.01/L
T
1100
L
50
0.4
Table 3: Hyperparametets for OGDA in the two players bandit environment. The notation used for the hyperparameters matches the original OGDA formulation Wei et al. (2021)
Hyperparameter
Value
0.01 n
g
0.1 /
n
0.05
0.01/n /n
R
K
500
N
70
T
10
0 for and 0.2 for x
Table 4: Hyperparametets for Reflected NAC in Alesia(T, T., C) with and C 6,
60

---

Under review as a conference paper at ICLR 2022
Hyperparameter
Value
"
0.005
02
0.01/t
7
1000
L
3500
0.4
Table 5: Hyperparametets for OGDA in Alesia. The notation used for the hyperparameters matches the original OGDA formulation in Wei al. (2021)
ReflectedNAC OGDA
6.12
ReflectedNAC OGDA REINFORCE
Suboptinallty gag
Saboptmaalty gaga
8.19
REINFORCE
0.35
0.50
0.50
Environment steps 7000)
Environment steps 7000)
Figure 2: left: x player, right: y player. Experiments in Alesia with length L and coin budget C = 7. The suboptimality gap on y-axis is max, Va (su) V* (sa(s for z and as min, ya. (Pa)(ss) V (s.)) for y where &u is the initial state that deterministic in Alesia. Results are averaged over 5 seeds.
61


Reviews:
[{"review_id": "SFBwIUw3YPm", "reviewer": "Reviewer_HqK9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper develops a new NAC algorithm for solving zero-sum Markov games with finite-time convergence guarantees. Below are some major comments and questions.\n\n1. The proposed algorithm is stochastic (sample-based), and preserves the private information of both agents, but it requires both players to play asymmetric roles/updates. This would restrict its application to practical scenarios where two competing players are not willing to negotiate.\n\n2. After reading the paper for a while, I feel that the paper needs to be further polished. Dense notations are introduced and many of them are not clear from the context. For example, the parameters $\\beta_n^{\\omega}$, $\\beta_n^{\\theta}$, $\\beta_n^{\\nu}$ in Algorithm 1 is not clear until I read the Algorithm 2. It seems that these are just indicator parameters. In Algorithm 2, $\\phi_n$ is confusing. It seems to be a state function, a state-action function and a vector in line 4, lines 6 & 9 and line 11, respectively. I'm not sure which entries of $\\phi_n(\\cdot)$ or $\\phi_n(\\cdot,\\cdot)$ are updated in line 11. Moreover, $\\lambda_{\\min}^{\\theta}$, $\\lambda_{\\min}^{\\nu}$, $\\lambda_{\\min}^{\\omega}$ are not clearly defined. \n\n3. The authors presented the order of the complexity results that only emphasize the dependence on $\\epsilon$. While there are many other important problem-related parameters, I suggest the authors also explicitly mention the dependence of the complexities on, e.g., $|S|, |A|, (1-\\gamma)$. In particular, I am curious about the dependence of $\\lambda_{\\min}^{\\theta}$, $\\lambda_{\\min}^{\\nu}$, $\\lambda_{\\min}^{\\omega}$ on these parameters. For example, the complexity result established in Theorem 3.2 in the appendix seems to has dependence on $|S|^2, |A|^2, (1-\\gamma)^8, \\lambda_{\\min}^2$.\n\n4. The comparison to the complexity results of the existing literature may not be fair. For example, the authors claim that the sample complexity $\\tilde{\\mathcal{O}}(\\epsilon^{-4})$ in Theorem 3.3 matches the best-known result established in Corollary 5 of Wei et al. 2021. However, Wei 2021 adopts the policy distance measure while this paper adopts the one-sided function value gap. Also, Wei's result establishes a high-probability convergence guarantee, while this paper is in expectation. I am not sure if these results are directly comparable given these differences.\n\n5. The technical proof is largely based on the existing literature. Can the authors highlight their technical novelties?\n\nSome other comments/questions\n\n1. The introduction mentions that the value-based methods offer near-optimal guarantees which are lacking in policy-based methods. To motivate this study, it is better to also state the advantages of policy-based methods over value-based methods. \n\n2. In the introduction, the authors write \"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\". Could you further elaborate on the limited guarantees (e.g. lack of non-asymptotic complexity result, very high complexity, restrictive assumptions, etc)? \n\n3. What does the $x$ label \"Environment steps\" mean in Figures 1 & 2? Is it sample complexity?\n\n4. At the beginning of Section 2, do we need a lower bound on the reward $r(s,a,b)$? \n\n5. At the beginning of Algorithm 1, $\\mathcal{P}_{KL}$ is actually defined in Section 2. \n\n6. It is better to also provide a convergence rate for Theorem 3.3. \n\n7. The $y$ label of Figure 1 should be \"probability of optimal action\". ", "summary_of_the_paper": "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. ", "summary_of_the_review": "Overall, I think this paper has the potential to deliver a solid theoretical contribution to the literature of zero-sum Markov games. It needs to be further polished before being seriously considered for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RDrWU8F6Wbv", "reviewer": "Reviewer_TPgg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper analyzes an important multi-agent RL problem and obtains interesting theoretical results. As claimed by the authors, the results are novel for policy gradient methods in this game setup. While the paper is overall technically dense, the authors manage to clearly convey the main idea through well articulated insights/intuitions. The assumptions and results are explained, which is helpful for understanding the context without referring too much to the technical details. I didn't check the proofs, but the theoretical results seem solid. I agree that this paper primarily focuses on theoretical contributions and that the numerical verification is enough.\n\nOne small comment: could the authors add some remarks regarding the feasibility/difficulty of extending the results to the case of function approximation? For example, it was mentioned in page 3 that a sample complexity of epsilon^-6 was obtained with function approximation, under access to unbiased samples of the value functions. How would the proposed algorithm perform if under the similar oracle assumptions?", "summary_of_the_paper": "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. ", "summary_of_the_review": "I think the paper is well written and the technical contributions are important and solid.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ER1sGa2-DDt", "reviewer": "Reviewer_jDaF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major Comments:\n\nMy major concern is about the correctness of the main result (Theorem 3.2). The authors claim that they match the $O(\\epsilon^{-2})$ sample complexity of NAC in (Lan, 2021; Khodadadian et al., 2021b; Hong et al., 2020; Xu et al., 2020b). (Khodadadian et al., 2021b) has $O(\\epsilon^{-3})$ sample complexity. (Hong et al., 2020) has $O(\\epsilon^{-4})$ sample complexity. (Xu et al., 2020b) has $O(\\epsilon^{-3})$ sample complexity (see their updated arXiv version). To my knowledge, the only paper that has $O(\\epsilon^{-2})$ sample complexity of NAC is (Lan, 2021).\n\nThe reason that  (Lan, 2021) was able to obtain the $O(\\epsilon^{-2})$ sample complexity of NAC is the following. By using mirror descent and carefully designed step sizes (in fact, exponentially increasing step sizes), the actor enjoys an exponential convergence rate, resulting in $O(\\log(1/\\epsilon))$ sample complexity of the actor. This also makes intuitive sense in that when using rapidly increasing step sizes, the natural policy gradient algorithm becomes close to policy iteration, which has geometric convergence. As for the critic, it is well-known that the optimal sample complexity to achieve $E[ \\|V_k-V^\\pi \\| ]<\\epsilon$ is $O(\\epsilon^{-2})$. Therefore, the overall sample complexity of NAC in  (Lan, 2021) is $O(\\epsilon^{-2})$, which is essentially the sample complexity of the critic.\n\nIn this paper, the reason for obtaining the $O(\\epsilon^{-2})$ sample complexity is completely different from (Lan, 2021). First of all, the authors did not establish the geometric convergence of the actor, as evidenced by the $O(1/T)$ term in Theorem 3.2. As for the critic, it seems that the authors derive $O(\\epsilon^{-1})$ sample complexity. Unless I miss something important, I do not think that is possible. Consider an MDP with a single state and a single action, and the discount factor is zero. The reward is i.i.d. In this case, the policy evaluation problem essentially reduces to estimating the mean of a random variable with access to i.i.d. samples. Cramér–Rao bound implies that the sample complexity cannot be better than $O(\\epsilon^{-2})$. Without establishing the geometric convergence of the actor, I do not think one can achieve $O(\\epsilon^{-2})$ sample complexity of NAC.\n\nMinor Comments:\n\n(1) Assumption 2 cannot hold. Softmax policies cover all policies, including deterministic policies. Therefore, there is no a lower bound for all policies. \n\n(2) As a follow-up comment to (1), suppose that there is a unique deterministic optimal policy. Under Assumption 2, the agent can never find the optimal policy. This means that even when $K$, $T$, and $N$ go to infinity, there should still be some constant error term on the right hand side of Theorem 3,2, because of the fact that the agent is trying to find a deterministic policy under Assumption 2. Why is it not the case in Theorem 3.2?\n\n(3) In equation (2), it should be $y(b|s)$ instead of $y(a|s)$.\n\n----------After Author Feedback-----------\n\nI am now convinced about the correctness of the result, and have increased my score.\n", "summary_of_the_paper": "This paper considers the problem of solving zero sum Markov games using natural actor-critic algorithms. The authors derive $O(\\epsilon^{-2})$ overall sample complexity of the proposed algorithm, and conduct numerical experiments to verify the convergence of the algorithm. ", "summary_of_the_review": "As mentioned in my main review, my major concern is about the correctness of the result. Therefore I vote for rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6FTT1-UGYCp", "reviewer": "Reviewer_JFQa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The theoretical RL community will find the results presented in this paper interesting. Assumption 1 about stationary state distribution is common in many previous works on finite-time convergence bounds for RL algorithms. Although Assumption 2 is less common than 1, I think it is reasonable, and one of the results in this paper does not rely on Assumption 2. It is good to see the order of sample complexity can be improved much based on these assumptions. The authors also explain the intuitions behind their proofs well in Section 3.2.\n\nWeakness: Compared with the improvement on complexity bounds, the novelty of the algorithm design is relatively weak. The algorithm is designed based on the two-stage framework used in [Perolat et al., 2015], and NPG approach used in the second stage is standard because it is a single agent problem. There are multiple existing results that can be used to solve the equilibrium of a matrix game in the first stage, and the authors adopt FoRB algorithm [Malitsky & Tam, 2020]. If I understand correctly, the major challenge is that the theoretical results in [Malitsky & Tam, 2020] cannot be directly applied here.\n\nThere are also some minor presentation issues. The definition of \"Policy-Eval\" algorithm may cause confusion because it can take either 5 or 4 arguments, and the argument $\\beta_n^\\omega, \\beta_n^\\theta, \\beta_n^\\nu$ are only used to distinguish different functions of this algorithm. To improve readability, I suggest to separate \"Policy-Eval\" to three small procedures. Besides, the curve in the second subfigure of Figure 1 looks weird because the shaded area exceeds the lower bound 0 and upper bound 1 for probabilities. The implementation of this simulation needs to be double-checked.", "summary_of_the_paper": "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.", "summary_of_the_review": "The theoretical analysis of this work is interesting and new, but the framework and the two major components of the algorithms have been studied in prior work. This is a theoretical work, so the empirical novelty and significance does not apply.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed algorithms (based on natural actor-critic methods) to solve two-player zero-sum Markov games. The authors established theoretical support for the convergence properties--and hence sample complexity---of the proposed methods. The authors claimed, based on their theoretical results, that the proposed methods are sample-efficient. 

As the reviewers pointed out, the original submission focused on the dependency on epsilon without explicit dependency on other important parameters like S, A, B, etc. The revised version has made explicit the dependencies on all these problem parameters, which I appreciated. However, the sample complexity presented in the new version scales as either S^3 max{A,B} or S^4 * \max{A,B}^6 on the sizes of state space and action spaces, which are all huge. What is more, the sample complexities also rely on additional parameters like rho, x, y, which could all depend on S,A,B, etc. As a result, the resulting sample complexity bounds do not seem to imply sample efficiency. In addition, Assumptions 1 and 2 are somewhat unnatural to make.
Decision: Reject