Year: 2020

Abstract:
Model-based algorithms—algorithms that explore the environment through building and utilizing an estimated model—are widely used in reinforcement learning practice and theoretically shown to achieve optimal sample efficiency for singleagent reinforcement learning in Markov Decision Processes (MDPs). However, for multi-agent reinforcement learning in Markov games, the current best known sample complexity for model-based algorithms is rather suboptimal and compares unfavorably against recent model-free approaches. In this paper, we present a sharp analysis of model-based self-play algorithms for multi-agent Markov games. We design an algorithm Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games that is able to output an -approximate Nash policy in Õ(HSAB/ ) episodes of game playing, where S is the number of states, A,B are the number of actions for the two players respectively, and H is the horizon length. This significantly improves over the best known model-based guarantee of Õ(HSAB/ ), and is the first that matches the information-theoretic lower bound Ω(HS(A + B)/ ) except for a min {A,B} factor. In addition, our guarantee compares favorably against the best known model-free algorithm if min {A,B} = o(H), and outputs a single Markov policy while existing sampleefficient model-free algorithms output a nested mixture of Markov policies that is in general non-Markov and rather inconvenient to store and execute. We further adapt our analysis to designing a provably efficient task-agnostic algorithm for zero-sum Markov games, and designing the first line of provably sample-efficient algorithms for multi-player general-sum Markov games.

heading: 1 INTRODUCTION
text: This paper is concerned with the problem of multi-agent reinforcement learning (multi-agent RL), in which multiple agents learn to make decisions in an unknown environment in order to maximize their (own) cumulative rewards. Multi-agent RL has achieved significant recent success in traditionally hard AI challenges including large-scale strategy games (such as GO) (Silver et al., 2016; 2017), real-time video games involving team play such as Starcraft and Dota2 (OpenAI, 2018; Vinyals et al., 2019), as well as behavior learning in complex social scenarios (Baker et al., 2020). Achieving human-like (or super-human) performance in these games using multi-agent RL typically requires a large number of samples (steps of game playing) due to the necessity of exploration, and how to improve the sample complexity of multi-agent RL has been an important research question.
One prevalent approach towards solving multi-agent RL is model-based methods, that is, to use the existing visitation data to build an estimate of the model (i.e. transition dynamics and rewards), run an offline planning algorithm on the estimated model to obtain the policy, and play the policy in the environment. Such a principle underlies some of the earliest single-agent online RL algorithms such as E3 (Kearns & Singh, 2002) and RMax (Brafman & Tennenholtz, 2002), and is conceptually appealing for multi-agent RL too since the multi-agent structure does not add complexity onto the model estimation part and only requires an appropriate multi-agent planning algorithm (such as value iteration for games (Shapley, 1953)) in a black-box fashion. On the other hand, modelfree methods do not directly build estimates of the model, but instead directly estimate the value functions or action-value (Q) functions of the problem at the optimal/equilibrium policies, and play the greedy policies with respect to the estimated value functions. Model-free algorithms have also
been well developed for multi-agent RL such as friend-or-foe Q-Learning (Littman, 2001) and Nash Q-Learning (Hu & Wellman, 2003).
While both model-based and model-free algorithms have been shown to be provably efficient in multi-agent RL in a recent line of work (Bai & Jin, 2020; Xie et al., 2020; Bai et al., 2020), a more precise understanding of the optimal sample complexities within these two types of algorithms (respectively) is still lacking. In the specific setting of two-player zero-sum Markov games, the current best sample complexity for model-based algorithms is achieved by the VI-ULCB (Value Iteration with Upper/Lower Confidence Bounds) algorithm (Bai & Jin, 2020; Xie et al., 2020): In a tabular Markov game with S states, {A,B} actions for the two players, and horizon length H , VI-ULCB is able to find an -approximate Nash equilibrium policy in Õ(H4S2AB/ 2) episodes of game playing. However, compared with the information-theoretic lower bound Ω(H3S(A+B)/ 2), this rate has suboptimal dependencies on all of H , S, and A,B. In contrast, the current best sample complexity for model-free algorithms is achieved by Nash V-Learning (Bai et al., 2020), which finds an -approximate Nash policy in Õ(H6S(A + B)/ 2) episodes. Compared with the lower bound, this is tight except for a poly(H) factor, which may seemingly suggest that model-free algorithms could be superior to model-based ones in multi-agent RL. However, such a conclusion would be in stark contrast to the single-agent MDP setting, where it is known that model-based algorithms are able to achieve minimax optimal sample complexities (Jaksch et al., 2010; Azar et al., 2017). It naturally arises whether model-free algorithms are indeed superior in multi-agent settings, or whether the existing analyses of model-based algorithms are not tight. This motivates us to ask the following research question:
Question: How sample-efficient are model-based algorithms in multi-agent RL?
In this paper, we advance the theoretical understandings of multi-agent RL by presenting a sharp analysis of model-based algorithms on Markov games. Our core contribution is the design of a new model-based algorithm Optimistic Nash Value Iteration (Nash-VI) that achieves an almost optimal sample complexity for zero-sum Markov games and improves significantly over existing modelbased approaches. We summarize our main contributions as follows. A comparison between our and prior results can be found in Table 1.
• We design a new model-based algorithm Optimistic Nash Value Iteration (Nash-VI) that provably finds -approximate Nash equilibria for Markov games in Õ(H3SAB/ 2) episodes of game playing (Section 3). This improves over the best existing model-based algorithm by O(HS) and is the first algorithm that matches the sample complexity lower bound except for a Õ(min {A,B}) factor, showing that model-based algorithms can indeed achieve an almost optimal sample complexity. Further, unlike state-of-the-art model-free algorithms such as Nash V-Learning (Bai et al., 2020), this algorithm achieves in addition a Õ( √ T ) regret bound, and outputs a simple Markov policy (instead of a nested mixture of Markov policies as returned by Nash V-Learning).
• We design an alternative algorithm Optimistic Value Iteration with Zero Reward (VI-Zero) that is able to perform task-agnostic (reward-free) learning for multiple Markov games sharing the same transition (Section 4). For N > 1 games with the same transition and different (known) rewards, VI-Zero can find -approximate Nash policy for all games simultaneously in Õ(H4SAB logN/ 2) episodes of game playing, which scales logarithmically in the number of games. • We design the first line of sample-efficient algorithms for multi-player general-sum Markov games. In a multi-player game with M players and Ai actions per player, we show that an nearoptimal policy can be found in Õ(H4S2 ∏ i∈[M ]Ai/
2) episodes, where the desired optimality can be either one of Nash equilibrium, correlated equilibrium (CE), or coarse correlated equilibrium (CCE). We achieve this guarantee by either a multi-player version of Nash-VI or a multi-player version of reward-free value iteration (Section 5 & Appendix C).
Due to space limit, we defer a detailed survey of related works to Appendix A.

heading: 2 PRELIMINARIES
text: In this paper, we consider Markov Games (MGs, Shapley, 1953; Littman, 1994), which are also known as stochastic games in the literature. Markov games are the generalization of standard Markov Decision Processes (MDPs) into the multi-player setting, where each player seeks to maximize her own utility. For simplicity, in this section we describe the important special case of twoplayer zero-sum games, and return to the general formulation in Appendix C.
Formally, we consider the tabular episodic version of two-player zero-sum Markov game, which we denote as MG(H,S,A,B,P, r). HereH is the number of steps in each episode, S is the set of states with |S| ≤ S, (A,B) are the sets of actions of the max-player and the min-player respectively with |A| ≤ A and |B| ≤ B, P = {Ph}h∈[H] is a collection of transition matrices, so that Ph(·|s, a, b) gives the distribution of the next state if action pair (a, b) is taken at state s at step h, and r = {rh}h∈[H] is a collection of reward functions, where rh : S × A × B → [0, 1] is the deterministic reward function at step h.1 This reward represents both the gain of the max-player and the loss of the min-player, making the problem a zero-sum Markov game.
In each episode of this MG, we start with a fixed initial state s1. At each step h ∈ [H], both players observe state sh ∈ S , and pick their own actions ah ∈ A and bh ∈ B simultaneously. Then, both players observe the actions of their opponent, receive reward rh(sh, ah, bh), and then the environment transitions to the next state sh+1 ∼ Ph(·|sh, ah, bh). The episode ends when sH+1 is reached.
Policy, value function. A (Markov) policy µ of the max-player is a collection of H functions {µh : S → ∆A}h∈[H], each mapping from a state to a distribution over actions. (Here ∆A is the probability simplex over action set A.) Similarly, a policy ν of the min-player is a collection of H functions {νh : S → ∆B}h∈[H]. We use the notation µh(a|s) and νh(b|s) to represent the probability of taking action a or b for state s at step h under Markov policy µ or ν respectively.
We use V µ,νh : S → R to denote the value function at step h under policy µ and ν, so that V µ,ν h (s) gives the expected cumulative rewards received under policy µ and ν, starting from s at step h:
V µ,νh (s) := Eµ,ν [∑H h′=h rh′(sh′ , ah′ , bh′) ∣∣∣ sh = s] . (1)
We also define Qµ,νh : S × A × B → R to be the Q-value function at step h so that Q µ,ν h (s, a, b) gives the cumulative rewards received under policy µ and ν, starting from (s, a, b) at step h:
Qµ,νh (s, a, b) := Eµ,ν [∑H h′=h rh′(sh′ , ah′ , bh′) ∣∣∣ sh = s, ah = a, bh = b] . (2)
For simplicity, we define operator Ph as [PhV ](s, a, b) := Es′∼Ph(·|s,a,b)V (s′) for any value function V . We also use notation [DπQ](s) := E(a,b)∼π(·,·|s)Q(s, a, b) for any action-value function Q. By definition of value functions, we have the Bellman equation
Qµ,νh (s, a, b) = (rh + PhV µ,ν h+1)(s, a, b), V µ,ν h (s) = (Dµh×νhQ µ,ν h )(s)
1We assume the rewards in [0, 1] for normalization. Our results directly generalize to randomized reward functions, since learning the transition is more difficult than learning the reward.
for all (s, a, b, h) ∈ S ×A×B× [H], and at the (H + 1)th step we have V µ,νH+1(s) = 0 for all s ∈ S.
Best response and Nash equilibrium. For any policy of the max-player µ, there exists a best response of the min-player, which is a policy ν†(µ) satisfying V µ,ν
†(µ) h (s) = infν V µ,ν h (s) for any
(s, h) ∈ S× [H]. We denote V µ,†h := V µ,ν†(µ) h . By symmetry, we can also define µ †(ν) and V †,νh . It is further known (cf. (Filar & Vrieze, 2012)) that there exist policies µ?, ν? that are optimal against the best responses of the opponents, in the sense that
V µ ?,† h (s) = supµ V µ,† h (s), V †,ν? h (s) = infν V †,ν h (s), for all (s, h).
We call these optimal strategies (µ?, ν?) the Nash equilibrium of the Markov game, which satisfies the following minimax equation 2:
supµ infν V µ,ν h (s) = V
µ?,ν?
h (s) = infν supµ V µ,ν h (s).
Intuitively, a Nash equilibrium gives a solution in which no player has anything to gain by changing only her own policy. We further abbreviate the values of Nash equilibrium V µ ?,ν?
h andQ µ?,ν? h as V ? h
and Q?h. We refer readers to Appendix D for Bellman optimality equations for (the value functions of) the best responses and the Nash equilibrium.
Learning Objective. We measure the suboptimality of any pair of general policies (µ̂, ν̂) using the gap between their performance and the performance of the optimal strategy (i.e., Nash equilibrium) when playing against the best responses respectively:
V †,ν̂1 (s1)− V µ̂,† 1 (s1) = [ V †,ν̂1 (s1)− V ?1 (s1) ] + [ V ?1 (s1)− V µ̂,† 1 (s1) ] Definition 1 ( -approximate Nash equilibrium). A pair of general policies (µ̂, ν̂) is an - approximate Nash equilibrium, if V †,ν̂1 (s1)− V µ̂,† 1 (s1) ≤ . Definition 2 (Regret). Let (µk, νk) denote the policies deployed by the algorithm in the kth episode. After a total of K episodes, the regret is defined as
Regret(K) = K∑ k=1 (V †,ν k 1 − V µk,† 1 )(s1).
One goal of reinforcement learning is to design algorithms for Markov games that can find an -approximate Nash equilibrium using a number of episodes that is small in its dependency on S,A,B,H as well as 1/ (PAC sample complexity bound). An alternative goal is to design algorithms for Markov games that achieves regret that is sublinear in K, and polynomial in S,A,B,H (regret bound). We remark that any sublinear regret algorithm can be directly converted to a polynomial-sample PAC algorithm via the standard online-to-batch conversion (see e.g., Jin et al. (2018)).

heading: 3 OPTIMISTIC NASH VALUE ITERATION
text: In this section, we present our main algorithm—Optimistic Nash Value Iteration (Nash-VI), and provide its theoretical guarantee.

heading: 3.1 ALGORITHM DESCRIPTION
text: We describe our Nash-VI Algorithm 1. In each episode, the algorithm can be decomposed into two parts.
• Line 3-13 (Optimistic planning from the estimated model): Performs value iteration with bonus using the empirical estimate of the transition P̂, and computes a new (joint) policy π which is “greedy” with respect to the estimated value functions;
2The minimax theorem here is different from the one for matrix games, i.e. maxφminψ φ>Aψ = minψmaxφ φ >Aψ for any matrix A, since here V µ,νh (s) is in general not bilinear in µ, ν.
• Line 16-19 (Play the policy and update the model estimate): Executes the policy π, collects samples, and updates the estimate of the transition P̂.
At a high-level, this two-phase strategy is standard in the majority of model-based RL algorithms, and also underlies provably efficient model-based algorithms such as UCBVI for single-agent (MDP) setting (Azar et al., 2017) and VI-ULCB for the two-player Markov game setting (Bai & Jin, 2020). However, VI-ULCB has two undesirable drawbacks: the sample complexity is not tight in any of H , S, and A,B dependency, and its computational complexity is PPAD-complete (a complexity class conjectured to be computationally hard (Daskalakis, 2013)).
As we elaborate in the following, our Nash-VI algorithm differs from VI-ULCB in a few important technical aspects, which allows it to significantly improve the sample complexity over VI-ULCB, and ensures that our algorithm terminates in polynomial time.
Before digging into explanations of techniques, we remark that line 14-15 is only used for computing the output policies. It chooses policy πout to be the policy in the episode with minimum gap (V 1 − V 1)(s1). Our final output policies (µ
out, νout) are simply the marginal policies of πout. That is, for all (s, h) ∈ S × [H], µouth (·|s) := ∑ b∈B π out h (·, b|s), and νouth (·|s) := ∑ a∈A π out h (a, ·|s).

heading: 3.1.1 OVERVIEW OF TECHNIQUES
text: Auxiliary bonus γ. The major improvement over VI-ULCB (Bai & Jin, 2020) comes from the use of a different style of bonus term γ (line 8), in addition to the standard bonus β (line 7), in value iteration steps (line 9-10). This is also the main technical contribution of our Nash-VI algorithm. This auxiliary bonus γ is computed by applying the empirical transition matrix P̂h to the gap at the next step V h+1 − V h+1, This is very different from standard bonus β, which is typically designed according to the concentration inequalities.
The main purpose of these value iteration steps (line 9-10) is to ensure that the estimated values Qh and Qh are with high probability the upper bound and the lower bound of the Q-value of the current policy when facing best responses (see Lemma 20 and 22 for more details) 3. To do so, prior work (Bai & Jin, 2020) only adds bonus β, which needs to be as large as Θ̃( √ S/t). In contrast, the inclusion of auxiliary bonus γ in our algorithm allows a much smaller choice for bonus β—which scales only as Õ( √ 1/t)—while still maintaining valid confidence bounds. This technique alone
brings down the sample complexity to Õ(H4SAB/ 2), removing an entire S factor compared to VI-ULCB. Furthermore, the coefficient in γ is only c/H for some absolute constant c, which ensures that the introduction of error term γ would hurt the overall sample complexity only up to a constant factor.
Bernstein concentration. Our Nash-VI allows two choices of the bonus function β = BONUS(t, σ̂2):
Hoeffding type: c( √ H2ι/t+H2Sι/t), Bernstein type: c( √ σ̂2ι/t+H2Sι/t). (3)
where σ̂2 is the estimated variance, ι is the logarithmic factors and c is absolute constant. The V̂ in line 7 is the empirical variance operator defined as V̂hV = P̂hV 2 − (P̂hV )2 for any V ∈ [0, H]S . The design of both bonuses stem from the Hoeffding and Bernstein concentration inequalities. Further, the Bernstein bonus uses a sharper concentration, which saves anH factor in sample complexity compared to the Hoeffding bonus (similar to the single-agent setting (Azar et al., 2017)). This further reduces the sample complexity to Õ(H3SAB/ 2) which matches the lower bound in allH,S, factors.
Coarse Correlated Equalibirum (CCE). The prior algorithm VI-ULCB (Bai & Jin, 2020) computes the “greedy” policy with respect to the estimated value functions by directly computing the Nash equilibrium for the Q-value at each step h. However, since the algorithm maintains both the upper confidence bound and lower confidence bound of the Q-value, this leads to the requirement
3We remark that the current policy is stochastic. This is different from the single-agent setting, where the algorithm only seeks to provide an upper bound of the value of the optimal policy where the optimal policy is not random. Due to this difference, the techniques of Azar et al. (2017) cannot be directly applied here.
Algorithm 1 Optimistic Nash Value Iteration (Nash-VI)
1: Initialize: for any (s, a, b, h), Qh(s, a, b)← H , Qh(s, a, b)← 0, ∆← H , Nh(s, a, b)← 0. 2: for episode k = 1, . . . ,K do 3: for step h = H,H − 1, . . . , 1 do 4: for (s, a, b) ∈ S ×A× B do 5: t← Nh(s, a, b). 6: if t > 0 then 7: β ← BONUS(t, V̂h[(V h+1 + V h+1)/2](s, a, b)). 8: γ ← (c/H)P̂h(V h+1 − V h+1)(s, a, b). 9: Qh(s, a, b)← min{(rh + P̂hV h+1)(s, a, b) + γ + β,H}.
10: Q h (s, a, b)← max{(rh + P̂hV h+1)(s, a, b)− γ − β, 0}. 11: for s ∈ S do 12: πh(·, ·|s)← CCE(Qh(s, ·, ·), Qh(s, ·, ·)). 13: V h(s)← (DπhQh)(s); V h(s)← (DπhQh)(s). 14: if (V 1 − V 1)(s1) < ∆ then 15: ∆← (V 1 − V 1)(s1) and πout ← π. 16: for step h = 1, . . . ,H do 17: take action (ah, bh) ∼ πh(·, ·|sh), observe reward rh and next state sh+1. 18: add 1 to Nh(sh, ah, bh) and Nh(sh, ah, bh, sh+1). 19: P̂h(·|sh, ah, bh)← Nh(sh, ah, bh, ·)/Nh(sh, ah, bh). 20: Output (µout, νout) that are the marginal policies of πout.
to compute the Nash equilibrium for a two-player general-sum matrix game, which is in general PPAD-complete (Daskalakis, 2013).
To overcome this computational challenge, we compute a relaxation of the Nash equilibrium— Coarse Correlated Equalibirum (CCE)—instead, a technique first introduced by Xie et al. (2020) to address reinforcement learning problems in Markov Games. Formally, for any pair of matrices Q,Q ∈ [0, H]A×B , CCE(Q,Q) returns a distribution π ∈ ∆A×B such that
E(a,b)∼πQ(a, b) ≥ max a? E(a,b)∼πQ(a?, b), E(a,b)∼πQ(a, b) ≤ min b? E(a,b)∼πQ(a, b?). (4)
Intuitively, in a CCE the players choose their actions in a potentially correlated way such that no one can benefit from unilateral unconditional deviation. A CCE always exists, since Nash equilibrium is also a CCE and a Nash equilibrium always exists. Furthermore, a CCE can be computed by linear programming in polynomial time. We remark that different from Nash equilibrium where the policies of each player are independent, the policies given by CCE are in general correlated for each player. Therefore, executing such a policy (line 17) requires the cooperation of two players.

heading: 3.2 THEORETICAL GUARANTEES
text: Now we are ready to present the theoretical guarantees for Algorithm 1. We let πk denote the policy computed in line 12 in the kth episode, and µk, νk denote the marginal policy of πk for each player.
Theorem 3 (Nash-VI with Hoeffding bonus). For any p ∈ (0, 1], letting ι = log(SABT/p), then with probability at least 1−p, Algorithm 1 with Hoeffding type bonus (3) (with some absolute c > 0) achieves:
• (V †,ν out 1 −V µout,† 1 )(s1) ≤ , if the number of episodesK ≥ Ω(H4SABι/ 2+H3S2ABι2/ ).
• Regret(K) = ∑K k=1(V †,νk 1 − V µk,† 1 )(s1) ≤ O( √ H3SABTι+H3S2ABι2).
Theorem 3 provides both a sample complexity bound and a regret bound for Nash-VI to find an -approximate Nash equilibrium. For small ≤ H/(Sι), the sample complexity scales as Õ(H4SAB/ 2). Similarly, for large T ≥ H3S3ABι3, the regret scales as Õ( √ H3SABT ), where T = KH is the total number of steps played within K episodes. Theorem 3 is significant in that it
improves the sample complexity of the model-based algorithm in Markov games from S2 to S (and the regret from S to √ S). This is achieved by adding the new auxiliary bonus γ in value iteration steps as explained in Section 3.1. The proof of Theorem 3 can be found in Appendix F.1.
Our next theorem states that when using Bernstein bonus instead of Hoeffding bonus as in (3), the sample complexity of Nash-VI algorithm can be further improved by a H factor in the leading order term (and the regret improved by a √ H factor).
Theorem 4 (Nash-VI with the Bernstein bonus). For any p ∈ (0, 1], letting ι = log(SABT/p), then with probability at least 1− p, Algorithm 1 with Bernstein type bonus (3) (with some absolute c > 0) achieves:
• (V †,ν out 1 −V µout,† 1 )(s1) ≤ , if the number of episodesK ≥ Ω(H3SABι/ 2+H3S2ABι2/ ).
• Regret(K) = ∑K k=1(V †,νk 1 − V µk,† 1 )(s1) ≤ O( √ H2SABTι+H3S2ABι2).
Compared with the information-theoretic sample complexity lower bound Ω(H3S(A + B)ι/ 2) and regret lower bound Ω( √ H2S(A+B)T ) (Bai & Jin, 2020), when is small, Nash-VI with Bernstein bonus achieves the optimal dependency on all of H,S, up to logarithmic factors in both the sample complexity and the regret, and the only gap that remains open is a AB/(A + B) ≤ min {A,B} factor. The proof of Theorem 4 can be found in Appendix F.2.
Comparison with model-free approaches. Different from our model-based approach, a recently proposed model-free algorithm Nash V-Learning (Bai et al., 2020) achieves sample complexity Õ(H6S(A + B)ι/ 2), which has a tight (A + B) dependency on A,B. However, our Nash-VI has the following important advantages over Nash V-Learning: 1. Our sample complexity has a better dependency on horizon H; 2. Our algorithm outputs a single pair of Markov policies (µout, νout) while their algorithm outputs a generic history-dependent policy that can be only written as a nested mixture of Markov policies; 3. The model-free algorithms in Bai et al. (2020) cannot be directly modified to obtain a √ T -regret (so that the exploration policies can be arbitrarily poor), while our model-based algorithm has the √ T -regret guarantee. We comment that although both Nash-VI and Nash V-Learning have polynomial running time, the later enjoys a better computational complexity because Nash-VI requires to solve LPs for computing CCEs in each episode.

heading: 4 REWARD-FREE LEARNING
text: In this section, we modify our model-based algorithm Nash-VI for the reward-free exploration setting (Jin et al., 2020b), which is also known as the task-agnostic (Zhang et al., 2020b) or reward-agnostic setting. Reward-free learning has two phases: In the exploration phase, the agent first collects a dataset of transitions D = {(sk,h, ak,h, bk,h, sk,h+1)}(k,h)∈[K]×[H] from a Markov game M without the guidance of reward information. After the exploration, in the planning phase, for each task i ∈ [N ], D is augmented with stochastic reward information to become Di = {(sk,h, ak,h, bk,h, sk,h+1, rk,h)}(k,h)∈[K]×[H], where rk,h is sampled from an unknown reward distribution with expectation equal to rih(sk,h, ak,h, bk,h). Here, we use r
i to refer to the unknown reward function of the ith task. The goal is to compute nearly-optimal policies forN tasks underM, given the augmented datasets. There are strong practical motivations for considering the reward-free setting. First, in applications such as robotics, we face multiple tasks in sequential systems with shared transition dynamics (i.e. the world) but very different rewards. There, we prefer to learn the underlying transition independent of reward information. Second, from the algorithm design perspective, decoupling exploration and planning (i.e. performing exploration without reward information) can be valuable for designing new algorithms in more challenging settings (e.g. with function approximation).
Due to space limits, we defer the description of our algorithm Optimistic Value Iteration with Zero Reward (VI-Zero, Algorithm 2) to Appendix B and only state its theoretical guarantees here. The following theorem claims that the empirical transition P̂out outputted by VI-Zero is close to the true transition P, in the sense that any Nash equilibrium of theM(P̂, r̂i) (i ∈ [N ]) is also an approximate
Nash equilibrium of the true underlying Markov gameM(P, ri), where r̂i is the empirical estimate of ri computed using Di.
Theorem 5 (Sample complexity of VI-Zero). There exists an absolute constant c, for any p ∈ (0, 1], ∈ (0, H], N ∈ N, if we choose bonus βt = c( √ H2ι/t + H2Sι/t) with ι = log(NSABT/p) and K ≥ c(H4SABι/ 2 + H3S2ABι2/ ), then with probability at least 1 − p, the output P̂out of Algorithm 2 has the following property: for any N fixed reward functions r1, . . . , rN , a Nash equilibrium of Markov game M(P̂out, r̂i) is also an -approximate Nash equilibrium of the true Markov gameM(P, ri) for all i ∈ [N ].
Theorem 5 shows that, when is small, VI-Zero only needs Õ(H4SAB/ 2) samples to learn an estimate of the transition P̂out, which is accurate enough to learn the approximate Nash equilibrium for any N fixed rewards. The most important advantage of reward-free learning comes from the sample complexity only scaling polylogarithmically with respect to the number of tasks or reward functions N . This is in sharp contrast to the reward-aware algorithms (e.g. Nash-VI), where the algorithm has to be rerun for each different task, and the total sample complexity must scale linearly in N . In exchange for this benefit, compared to Nash-VI, VI-Zero loses a factor of H in the leading term of sample complexity since we cannot use Bernstein bonus anymore due to the lack of reward information. VI-Zero also does not have a regret guarantee, since again without reward information, the exploration policies are naturally sub-optimal. The proof of Theorem 5 can be found in Appendix G.1.
Connections with reward-free learning in MDPs. Since MDPs are special cases of Markov games, our algorithm VI-Zero directly applies to the single-agent setting, and yields a sample complexity similar to existing results (Zhang et al., 2020b; Wang et al., 2020). However, distinct from existing results which require both the exploration algorithm and the planning algorithm to be specially designed to work together, our algorithm allows an arbitrary planning algorithm as long as it computes the Nash equilibrium of a Markov game with known transition and reward. Therefore, our results completely decouple the exploration and the planning.
Lower bound for reward-free learning. Finally, we comment that despite the sample complexity in Theorem 5 scaling asAB instead ofA+B, our next theorem states that unlike the general rewardaware setting, this AB scaling is unavoidable in the reward-free setting. This reveals an intrinsic gap between the reward-free and reward-aware learning: An A + B dependency is only achievable via sampling schemes that are reward-aware. A similar lower bound is also presented in recent work (Zhang et al., 2020a) for the discounted setting with a different hard instance construction.
Theorem 6 (Lower bound for reward-free learning of Markov games). There exists an absolute constant c > 0 such that for any ∈ (0, c], there exists a family of Markov games M( ) satisfying that: for any reward-free algorithm A using K ≤ cH2SAB/ 2 episodes, there exists a Markov gameM ∈ M( ) such that if we run A onM and output policies (µ̂, ν̂), then with probability at least 1/4, we have (V †,ν̂1 − V µ̂,† 1 )(s1) ≥ .
This lower bound shows that the sample complexity in Theorem 5 is optimal in S, A,B, and . The proof of Theorem 6 can be found in Appendix G.3.

heading: 5 MULTI-PLAYER GENERAL-SUM GAMES
text: We adapt our analysis to multi-player general-sum games and present the first lines of provably efficient algorithms. Concretely, we design two model-based algorithms Multi-Nash-VI and MultiVI-Zero (Algorithm 3 and Algorithm 4) that can find an ( -approximate) {NASH, CE, CCE} equilibrium for any multi-player general-sum Markov game in Õ(H4S2 ∏m i=1Ai/
2) episodes of game playing, where Ai is the number of actions for player i ∈ {1, . . . ,m} (Theorem 15 and Theorem 16). Due to space limit, we defer the detailed setups, algorithms and results to Appendix C.

heading: 6 CONCLUSION
text: In this paper, we provided a sharp analysis of model-based algorithms for Markov games. Our new algorithm Nash-VI can find an -approximate Nash equilibrium of a zero-sum Markov game in Õ(H3SAB/ 2) episodes of game playing, which almost matches the sample complexity lower bound except for the AB vs. A + B dependency. We also applied our analysis to derive new efficient algorithms for task-agnostic game playing, as well as the first line of multi-player generalsum Markov games. There are a number of compelling future directions to this work. For example, can we achieve A + B instead of AB sample complexity for zero-sum games using model-based approaches (thus closing the gap between lower and upper bounds)? How can we design more efficient algorithms for general-sum games with better sample complexity (e.g., O(S) instead of O(S2))? We leave these problems as future work.

heading: A RELATED WORK
text: Markov games. Markov games (or stochastic games) are proposed in the early 1950s (Shapley, 1953). They are widely used to model multi-agent RL. Learning the Nash equilibria of Markov games has been studied in Littman (1994; 2001); Hu & Wellman (2003); Hansen et al. (2013); Lee et al. (2020), where the transition matrix and reward are assumed to be known, or in the asymptotic setting where the number of data goes to infinity. These results do not directly apply to the nonasymptotic setting where the transition and reward are unknown and only a limited amount of data are available for estimating them.
Another line of work assumes certain strong reachability assumptions under which sophisticated exploration strategies are not required. A prevalent approach is to assume access to simulators (generative models) that enable the agent to directly sample transition and reward information for any state-action pair. In this setting, Jia et al. (2019); Sidford et al. (2019); Zhang et al. (2020a) provide non-asymptotic bounds on the number of calls to the simulator for finding an approximate Nash equilibrium. Wei et al. (2017) studies Markov games under an alternative assumption that no matter what strategy one agent sticks to, the other agent can always reach all states by playing a certain policy.
Non-asymptotic guarantees without reachability assumptions. The recent work of Bai & Jin (2020); Xie et al. (2020) provide the first line of non-asymptotic sample complexity guarantees on learning Markov games without these reachability assumptions, in which exploration is essential. However, both results suffer from highly suboptimal sample complexity. The results of Xie et al. (2020) also apply to the linear function approximation setting. More recently, two model-free algorithms—Nash Q-Learning and Nash V-Learning—are shown to achieve better sample complexity guarantees (Bai et al., 2020). In particular, the Nash V-learning algorithm achieves the nearoptimal dependence on S, A and B. However, the dependence on H is worse than our results and the output policy is a nested mixture, which is hard to implement. We compare our results with existing non-asymptotic guarantees in Table 1.
We remark that the classical R-max algorithm (Brafman & Tennenholtz, 2002) also provides provable guarantees for learning Markov games. However, Brafman & Tennenholtz (2002) uses a weaker definition of regret (similar to the online setting in Xie et al. (2020)), and consequently their result does not imply any sample complexity result for finding Nash equilibrium policies.
Adversarial MDPs. Another way to model the multi-player bahavior is to use adversarial MDPs. Most work in this line considers the setting with adversarial rewards (Zimin & Neu, 2013; Rosenberg & Mansour, 2019; Jin et al., 2019), where the reward can be manipulated by an adversary arbitrarily and the goal is to compete with the optimal (stationary) policy in hindsight. Adversarial MDP with changing dynamics is computationally hard even under full-information feedback (Yadkori et al., 2013). Notice these results do not directly imply provable self-play algorithms in our setting, because the opponent in Markov games can affect both the reward and the transition.
Single-agent RL. There is a rich literature on reinforcement learning in MDPs (see e.g., Jaksch et al., 2010; Osband et al., 2014; Azar et al., 2017; Dann et al., 2017; Strehl et al., 2006; Jin et al., 2018). MDP is a special case of Markov games, where only a single agent interacts with a stochastic environment. For the tabular episodic setting with nonstationary dynamics and no simulators, the best sample complexity is Õ(H3SA/ 2), achieved by model-based algorithm in Azar et al. (2017) and model-free algorithms in Zhang et al. (2020c), respectively, where S is the number of states, A is the number of actions, H is the length of each episode. Both of them match the lower bound Ω(H3SA/ 2) (Jaksch et al., 2010; Osband & Van Roy, 2016; Jin et al., 2018).
Reward-free and task-agnostic exploration. Jin et al. (2020a) proposes a new paradigm of learning an MDP, which they called reward-free exploration. In this setting, the agent goes through a two-stage process. In the exploration phase the agent can interacts with the environment without knowing the reward function and in the planning phase the reward function is given and the agent needs output a policy. The goal is to make the output policy near optimal for any given reward function. A closely related setting is task-agnostic learning, where the reward function is determined at the very beginning but not revealed until the planning phase. Notice algorithms for task-agnostic
Algorithm 2 Optimistic Value Iteration with Zero Reward (VI-Zero) Require: Bonus βt.
1: Initialize: for any (s, a, b, h), Ṽh(s, a, b)← H , ∆← H , Nh(s, a, b)← 0. 2: for episode k = 1, . . . ,K do 3: for step h = H,H − 1, . . . , 1 do 4: for (s, a, b) ∈ S ×A× B do 5: t← Nh(s, a, b). 6: if t > 0 then 7: Q̃h(s, a, b)← min{(P̂hṼh+1)(s, a, b) + βt, H}. 8: for s ∈ S do 9: πh(s)← arg max(a,b)∈A×B Q̃h(s, a, b).

heading: 10: Ṽh(s)← (DπhQ̃h)(s).
text: 11: if Ṽ1(s1) < ∆ then 12: ∆← Ṽ1(s1) and P̂out ← P̂. 13: for step h = 1, . . . ,H do 14: take action (ah, bh) ∼ πh(·, ·|sh), observe next state sh+1. 15: add 1 to Nh(sh, ah, bh) and Nh(sh, ah, bh, sh+1). 16: P̂h(·|sh, ah, bh)← Nh(sh, ah, bh, ·)/Nh(sh, ah, bh). 17: Output P̂out.
learning can also be transferred to reward-free exploration by taking union bound w.r.t. different possible reward function. In Table 1, VI-explore (Bai & Jin, 2020) and Algorithm 2 can also be applied to this setting.
Jin et al. (2020a) also proposes an algorithm, which first finds a covering policy to maximize the probability to reach each state separately and then collects data following this policy. Zhang et al. (2020b) takes a different approach by first runs the optimistic Q-learning algorithm (Jin et al., 2018) with zero reward to explore the environment, and then they utilizes the trajectories collected to compute a policy in an incremental manner. Wang et al. (2020) follows a simialr scheme, but studies reward-free exploration in linear-parametrized MDPs.

heading: B OPTIMISTIC VALUE ITERATION WITH ZERO REWARD – VI-ZERO
text: We now describe our algorithm for reward-free learning in zero-sum Markov games.
Exploration phase. In the first phase of reward-free learning, we deploy algorithm Optimistic Value Iteration with Zero Reward (VI-Zero, Algorithm 2). This algorithm differs from the rewardaware Nash-VI (Algorithm 1) in two important aspects. First, we use zero reward in the exploration phase (Line 7), and only maintains an upper bound of the (reward-free) value function instead of both upper and lower bounds. Second, our exploration policy is the maximizing (instead of CCE) policy of the value function (Line 9). We remark that the Q̃h(s, a, b) maintained in the algorithm 2 is no longer an upper bound for any actual value function (as it has no reward), but rather a measure of uncertainty or suboptimality that the agent may suffer—if she takes action (a, b) at state s and step h, and makes decisions by utilizing the empirical estimate P̂ in the remaining steps (see a rigorous version of this statement in Lemma 27). Finally, the empirical transition P̂ of the episode that minimizes Ṽ1(s1) is outputted and passed to the planning phase.
Planning phase. After obtaining the estimate of tranisiton P̂, our planning algorithm is rather simple. For the ith task, let r̂i be the empirical estimate of ri computed using the ith augmented dataset Di. Then we compute the Nash equilibrium of the Markov gameM(P̂, r̂i) with estimated transition P̂ and reward r̂i. Since both P̂ and r̂i are known exactly, this is a pure computation problem without any sampling error and can be efficiently solved by simple planning algorithms such as the vanilla Nash value iteration without optimism (see Appendix G.2 for more details).

heading: C MULTIPLAYER GENERAL-SUM MARKOV GAMES
text: In this section, we extend both our model-based algorithms (Algorithm 1 and Algorithm 2) to the setting of multiplayer general-sum Markov games, and present corresponding theoretical guarantees.

heading: C.1 PROBLEM FORMULATION
text: A general-sum Markov game (general-sum MG) with m players is a tuple MG(H,S, {Ai}mi=1,P, {ri}mi=1), where H , S denote the length of each episode and the state space. Different from the two-player zero-sum setting, we now have m different action spaces, where Ai is the action space for the ith player and |Ai| = Ai. We let a := (a1, · · · , am) denote the (tuple of) joint actions by all m players. P = {Ph}h∈[H] is a collection of transition matrices, so that Ph(·|s,a) gives the distribution of the next state if actions a are taken at state s at step h, and ri = {rh,i}h∈[H] is a collection of reward functions for ith player, so that rh,i(s,a) gives the reward received by the ith player if actions a are taken at state s at step h.
In this section, we consider three versions of equlibrium for general-sum MGs: Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilibrium (CCE), all being standard solution notions in games (Nisan et al., 2007). These three notions coincide on two-player zero-sum games, but are not equivalent to each other on multi-player general-sum games; any one of them could be desired depending on the application at hand. Below we introduce their definitions.
(Approximate) Nash equilibrium in general-sum MG. The policy of the ith player is denoted as πi := { πh,i : S → ∆Ai } h∈[H]. We denote the product policy of all the players as π := π1 × · · · × πM , and denote the policy of the all the players except the ith player as π−i. We define V πh,i(s) as the expected cumulative reward that will be received by the i
th player if starting at state s at step h and all players follow policy π. For any strategy π−i, there also exists a best response of the ith player, which is a policy µ†(π−i) satisfying V µ†(π−i),π−i h,i (s) = supπi V πi,π−i h,i (s) for any (s, h) ∈ S × [H]. We denote V †,π−ih,i := V µ†(π−i),π−i h,i . The Q-functions of the best response can be defined similarly.
Our first objective is to find an approximate Nash equilibrium of Markov games. Definition 7 ( -approximate Nash equilibrium in general-sum MG). A product policy π is an - approximate Nash equilibrium if maxi∈[m] (V †,π−i 1,i − V π1,i)(s1) ≤ .
The above definition requires the suboptimality gap (V †,π−i1,i − V π1,i)(s1) to be less than for all player i. This is consistent with the two-player case (Definition 1) up to a constant of 2, since in the two-player zero-sum setting, we have V π1,1(s1) = −V π1,2(s1) for any product policy π = (µ, ν), and therefore (V †,ν1,1 − V µ,† 1,1 )(s1) ≤ 2 maxi∈[2] (V †,π−i 1,i − V π1,i)(s1) ≤ 2(V †,ν 1,1 − V µ,† 1,1 )(s1).We can similarly define the regret. Definition 8 (Nash-regret in general-sum MG). Let πk denote the (product) policy deployed by the algorithm in the kth episode. After a total of K episodes, the regret is defined as
RegretNash(K) = K∑ k=1 max i∈[m] (V †,πk−i 1,i − V πk 1,i )(s1).
(Approximate) CCE in general-sum MG. The coarse correlated equilibrium (CCE) is a relaxed version of Nash equilibrium in which we consider general correlated policies instead of product policies. Let A = A1 × · · · × Am denote the joint action space. Definition 9 (CCE in in general-sum MG). A (correlated) policy π := {πh(s) ∈ ∆A : (h, s) ∈ [H]× S} is a CCE if maxi∈[m] V †,π−i h,i (s) ≤ V πh,i(s) for all (s, h) ∈ S × [H].
Compared with a Nash equilibrium, a CEE is not necessarily a product policy, that is, we may not have πh(s) ∈ ∆A1 × · · · × ∆Am . Similarly, we also define -approximate CCE and CCE-regret below.
Definition 10 ( -approximate CCE in general-sum MG). A policy π := {πh(s) ∈ ∆A : (h, s) ∈ [H]× S} is an -approximate CCE if maxi∈[m] (V †,π−i 1,i − V π1,i)(s1) ≤ .
Definition 11 (CCE-regret in general-sum MG). Let policy πk denote the (correlated) policy deployed by the algorithm in the kth episode. After a total of K episodes, the regret is defined as
RegretCCE(K) = K∑ k=1 max i∈[m] (V †,πk−i 1,i − V πk 1,i )(s1).
(Approximate) CE in general-sum MG. The correlated equilibrium (CE) is another relaxation of the Nash equilibrium. To define CE, we first introduce the concept of strategy modification: A strategy modification φ := {φh,s(a) ∈ Ai : (h, s, a) ∈ [H]×S×Ai} for player i is a set of S×H injective functions from Ai to itself. Let Φi denote the set of all possible strategy modifications for player i.
One can compose a strategy modification φ with any Markov policy π and obtain a new policy φ π such that when policy π chooses to play a := (a1, . . . , am) at state s and step h, policy φ πwill play (a1, . . . , ai−1, φh,s(ai), ai+1, . . . , am) instead. Definition 12 (CE in general-sum MG). A policy π := {πh(s) ∈ ∆A : (h, s) ∈ [H]× S} is a CE if maxi∈[m] maxφ∈Φi V φ π h,i (s) ≤ V πh,i(s) holds for all (s, h) ∈ S × [H].
Similarly, we have an approximate version of CE and CE-regret. Definition 13 ( -approximate CE in Markov games). A policy π := {πh(s) ∈ ∆A : (h, s) ∈ [H]× S} is an -approximate CE if maxi∈[m] maxφ∈Φi(V φ π 1,i − V π1,i)(s1) ≤ .
Definition 14 (CE-regret in multiplayer Markov games). Let product policy πk denote the policy deployed by the algorithm in the kth episode. After a total of K episodes, the regret is defined as
RegretCE(K) = K∑ k=1 max i∈[m] max φ ( V φ π k 1,i − V πk 1,i )(s1).
Relationship between Nash, CE, and CCE For general-sum MGs, we have {Nash} ⊆ {CE} ⊆ {CCE}, so that they form a nested set of notions of equilibria (Nisan et al., 2007). Indeed, one can easily verify that if we restrict the choice of strategy modification φ to those consisting of only constant functions, i.e., φh,s(a) being independent of a, Definition 12 will reduce to the definition of CCE policy. In addition, any Nash equilibrium is a CE by definition. Finally, since a Nash equilibrium always exists, so does CE and CCE.

heading: C.2 MULTIPLAYER OPTIMISTIC NASH VALUE ITERATION
text: Here we present the Multi-Nash-VI algorithm, which is an extension of Algorithm 1 for multi-player general-sum Markov games.
The EQUILIBRIUM Subroutine. Our EQUILIBRIUM subroutine in Line 11 could be taken from either one of the {NASH,CE,CCE} subroutines for one-step games. When using NASH, we compute the Nash equilibrium of a one-step multi-player game (see, e.g., Berg & Sandholm (2016) for an overview of the available algorithms); the worst-case computational complexity of such a subroutine will be PPAD-hard (Daskalakis, 2013). When using CE or CCE, we find CEs or CCEs of the one-step games respectively, which can be solved in polynomial time using linear programming. However, the policies found are not guaranteed to be a product policy. We remark that in Algorithm 1 we used the CCE subroutine for finding Nash in two-player zero-sum games, which seemingly contrasts the principle of using the right subroutine for finding the right equilibrium, but nevertheless works as the Nash equilibrium and CCE are equivalent in zero-sum games.
Now we are ready to present the theoretical guarantees for Algorithm 3. We let πk denote the policy computed in line 11 of Algorithm 3 in the kth episode. Theorem 15 (Multi-Nash-VI). There exists an absolute constant c, for any p ∈ (0, 1], let ι = log(SABT/p), then with probability at least 1 − p, Algorithm 3 with bonus βt = c √ SH2ι/t and EQUILIBRIUM being one of {NASH,CE,CCE} satisfies (repsectively):
Algorithm 3 Multiplayer Optimistic Nash Value Iteration (Multi-Nash-VI)
1: Initialize: for any (s,a, h, i), Qh,i(s,a)← H , Qh,i(s,a)← 0, ∆← H , Nh(s,a)← 0. 2: for episode k = 1, . . . ,K do 3: for step h = H,H − 1, . . . , 1 do 4: for (s,a) ∈ S ×A1 × · · · × Am do 5: t← Nh(s,a); 6: if t > 0 then 7: for player i = 1, 2, . . . ,m do 8: Qh,i(s,a)← min{(rh,i + P̂hV h+1,i)(s,a) + βt, H}. 9: Q
h,i (s,a)← max{(rh,i + P̂hV h+1,i)(s,a)− βt, 0}.
10: for s ∈ S do 11: πh(·|s)← EQUILIBRIUM(Qh,1(s, ·), Qh,2(s, ·), · · · , Qh,M (s, ·)). 12: for player i = 1, 2, . . . ,m do 13: V h,i(s)← (DπhQh,i)(s); V h,i(s)← (DπhQh,i)(s). 14: if maxi∈[m](V 1,i − V 1,i)(s1) < ∆ then 15: ∆← maxi∈[m](V 1,i − V 1,i)(s1) and πout ← π. 16: for step h = 1, . . . ,H do 17: take action ah ∼ πh(·|sh), observe reward rh and next state sh+1. 18: add 1 to Nh(sh,ah) and Nh(sh,ah, sh+1). 19: P̂h(·|sh,ah)← Nh(sh,ah, ·)/Nh(sh,ah). 20: Output πout.
• πout is an -approximate {NASH,CE,CCE}, if the number of episodes K ≥ Ω(H4S2( ∏m i=1Ai)ι/ 2).
• Regret{Nash,CE,CCE}(K) ≤ O( √ H3S2( ∏m i=1Ai)Tι).
In the situation where the EQUILIBRIUM subroutine is taken as NASH, Theorem 15 provides the sample complexity bound of Multi-Nash-VI algorithm to find a -approximate Nash equilibrium and its regret bound. Compared with our earlier result in two-player zero-sum games (Theorem 3), here the sample complexity scales as S2H4 instead of SH3. This is because the auxiliary bonus and Bernstein concentration technique do not apply here. Furthermore, the sample complexity is proportional to ∏m i=1Ai, which increases exponentially as the number of players increases.
Runtime of Algorithm 3 We remark that while the Nash guarantee is the strongest among the three guarantees presented in Theorem 15, the runtime of Algorithm 3 in the Nash case is not guaranteed to be polynomial and in the worst case PPAD-hard (due to the hardness of the NASH subroutine). In contrast, the CE and CCE guarantees are weaker, but the corresponding algorithms are guaranteed to finish in polynomial time.

heading: C.3 MULTIPLAYER REWARD-FREE LEARNING
text: We can also generalize VI-Zero to the multiplayer setting and obtain Algorithm 4, Multi-VI-Zero, which is almost the same as VI-Zero except that its exploration bonus βt is larger than that of VIZero by a √ S factor.
Similar to Theorem 5, we have the following theoretical guarantee claiming that any {NASH,CCE,CE} of theM(P̂, r̂i) (i ∈ [N ]) is also an approximate {NASH,CCE,CE} of the true Markov gameM(P, ri), where P̂out is the empirical transition outputted by Algorithm 4 and r̂i is the empirical estimate of ri.
Theorem 16 (Multi-VI-Zero). There exists an absolute constant c, for any p ∈ (0, 1], ∈ (0, H], N ∈ N, if we choose bonus βt = c √ H2Sι/t with ι = log(NSABT/p) and K ≥
c(H4S2( ∏m i=1Ai)ι/
2), then with probability at least 1 − p, the output P̂out of Algorithm 4 has the following property: for any N fixed reward functions r1, . . . , rN , any {NASH,CCE,CE} of
Algorithm 4 Multiplayer Optimistic Value Iteration with Zero Reward (Multi-VI-Zero)
1: Initialize: for any (s,a, h), Ṽh(s,a)← H , ∆← H , Nh(s,a)← 0. 2: for episode k = 1, . . . ,K do 3: for step h = H,H − 1, . . . , 1 do 4: for (s,a) ∈ S ×A1 × · · · × Am do 5: t← Nh(s,a). 6: if t > 0 then 7: Q̃h(s,a)← min{(P̂hṼh+1)(s,a) + βt, H}. 8: for s ∈ S do 9: πh(s)← arg maxa∈A1×···×Am Q̃h(s,a).
10: Ṽh(s)← (DπhQ̃h)(s). 11: if Ṽ1(s1) < ∆ then 12: ∆← Ṽ1(s1) and P̂out ← P̂. 13: for step h = 1, . . . ,H do 14: take action ah ∼ πh(·, ·|sh), observe next state sh+1. 15: add 1 to Nh(sh,ah) and Nh(sh,ah, sh+1). 16: P̂h(·|sh,ah)← Nh(sh,ah, ·)/Nh(sh,ah). 17: Output P̂out.
Markov game M(P̂out, r̂i) is also an -approximate {NASH,CCE,CE} of the true Markov game M(P, ri) for all i ∈ [N ].
The proof of Theorem 16 can be found in Appendix H.2. It is worth mentioning that the empirical Markov gameM(P̂out, r̂i) may have multiple {Nash equilibria,CCEs,CEs} and Theorem 16 ensures that all of them are -approximate {Nash equilibria,CCEs,CEs} of the true Markov game. Also, note that the sample complexity here is quadratic in the number of states because we are using the exploration bonus βt = √ H2Sι/t that is larger than usual by a √ S factor.

heading: D BELLMAN EQUATIONS FOR MARKOV GAMES
text: In this section, we present the Bellman equations for different types of values in Markov games.
Fixed policies. For any pair of Markov policy (µ, ν), by definition of their values in (1) (2), we have the following Bellman equations:
Qµ,νh (s, a, b) = (rh + PhV µ,ν h+1)(s, a, b), V µ,ν h (s) = (Dµh×νhQ µ,ν h )(s)
for all (s, a, b, h) ∈ S ×A× B × [H], where V µ,νH+1(s) = 0 for all s ∈ S.
Best responses. For any Markov policy µ of the max-player, by definition, we have the following Bellman equations for values of its best response:
Qµ,†h (s, a, b) = (rh + PhV µ,† h+1)(s, a, b), V µ,† h (s) = infν∈∆B (Dµh×νQ µ,† h )(s),
for all (s, a, b, h) ∈ S ×A× B × [H], where V µ,†H+1(s) = 0 for all s ∈ S. Similarly, for any Markov policy ν of the min-player, we also have the following symmetric version of Bellman equations for values of its best response:
Q†,νh (s, a, b) = (rh + PhV †,ν h+1)(s, a, b), V †,ν h (s) = sup
µ∈∆A (Dµ×νhQ
†,ν h )(s).
for all (s, a, b, h) ∈ S ×A× B × [H], where V †,νH+1(s) = 0 for all s ∈ S.
Nash equilibria. Finally, by definition of Nash equilibria in Markov games, we have the following Bellman optimality equations:
Q?h(s, a, b) =(rh + PhV ?h+1)(s, a, b) V ?h (s) = sup
µ∈∆A inf ν∈∆B (Dµ×νQ?h)(s) = inf ν∈∆B sup µ∈∆A (Dµ×νQ?h)(s).
for all (s, a, b, h) ∈ S ×A× B × [H], where V ?H+1(s) = 0 for all s ∈ S.

heading: E PROPERTIES OF COARSE CORRELATED EQUILIBRIUM
text: Recall the definition for CCE in our main paper (4), we restate it here after rescaling. For any pair of matrices P,Q ∈ [0, 1]n×m, the subroutine CCE(P,Q) returns a distribution π ∈ ∆n×m that satisfies:
E(a,b)∼πP (a, b) ≥max a? E(a,b)∼πP (a?, b) (5)
E(a,b)∼πQ(a, b) ≤min b? E(a,b)∼πQ(a, b?)
We make three remarks on CCE. First, a CCE always exists since a Nash equilibrium for a generalsum game with payoff matrices (P,Q) is also a CCE defined by (P,Q), and a Nash equilibrium always exists. Second, a CCE can be efficiently computed, since above constraints (5) for CCE can be rewritten as n + m linear constraints on π ∈ ∆n×m, which can be efficiently resolved by standard linear programming algorithm. Third, a CCE in general-sum games needs not to be a Nash equilibrium. However, a CCE in zero-sum games is guaranteed to be a Nash equalibrium. Proposition 17. Let π = CCE(Q,Q), and (µ, ν) be the marginal distribution over both players’ actions induced by π. Then (µ, ν) is a Nash equilibrium for payoff matrix Q.
Proof of Proposition 17. Let N? be the value of Nash equilibrium for Q. Since π = CCE(Q,Q), by definition, we have:
E(a,b)∼πQ(a, b) ≥max a? E(a,b)∼πQ(a?, b) = max a? Eb∼νQ(a?, b) ≥ N?
E(a,b)∼πQ(a, b) ≤min b? E(a,b)∼πQ(a, b?) = min b? Ea∼µQ(a, b?) ≤ N?
This gives: max a? Eb∼νQ(a?, b) = min b? Ea∼µQ(a, b?) = N?
which finishes the proof.
Intuitively, a CCE procedure can be used in Nash Q-learning for finding an approximate Nash equilibrium, because the values of upper confidence and lower confidence (Q and Q) will be eventually very close, so that the preconditions of Proposition 17 becomes approximately satisfied.

heading: F PROOF FOR SECTION 3 – OPTIMISTIC NASH VALUE ITERATION

heading: F.1 PROOF OF THEOREM 3
text: We denote V k, Qk, πk, µk and νk 4 for values and policies at the beginning of the k-th episode. In particular, Nkh (s, a, b) is the number we have visited the state-action tuple (s, a, b) at the h-th step before the k-th episode. Nkh (s, a, b, s
′) is defined by the same token. Using this notation, we can further define the empirical transition by P̂kh(s′|s, a, b) := Nkh (s, a, b, s′)/Nkh (s, a, b). If Nkh (s, a, b) = 0, we set P̂kh(s′|s, a, b) = 1/S. As a result, the bonus terms can be written as
βkh(s, a, b) := C
(√ ιH2
max{Nkh (s, a, b), 1} +
H2Sι
max{Nkh (s, a, b), 1}
) (6)
4recall that (µkh, ν k h) are the marginal distributions of π k h.
γkh(s, a, b) := C
H P̂h(V
k h+1 − V k h+1)(s, a, b) (7)
for some large absolute constant C > 0.
Lemma 18. Let c1 be some large absolute constant. Define event E0 to be: for all h, s, a, b, s′ and k ∈ [K], |[(P̂kh − Ph)V ?h+1](s, a, b)| ≤ c1 √ H2ι max{Nkh (s, a, b), 1} , |(P̂kh − Ph)(s′ | s, a, b)| ≤ c1 √min{Ph(s′ | s, a, b), P̂kh(s′ | s, a, b)}ι max{Nkh (s, a, b), 1} + ι max{Nkh (s, a, b), 1}
. We have P(E1) ≥ 1− p.
Proof. The proof is standard and folklore: apply standard concentration inequalities and then take a union bound. For completeness, we provide the proof of the second one here.
Consider a fixed (s, a, b, h) tuple.
Let’s consider the following equivalent random process: (a) before the agent starts, the environment samples {s(1), s(2), . . . , s(K)} independently from Ph(· | s, a, b); (b) during the interaction between the agent and environment, the ith time the agent reaches (s, a, b, h), the environment will make the agent transit to s(i). Note that the randomness induced by this interaction procedure is exactly the same as the original one, which means the probability of any event in this context is the same as in the original problem. Therefore, it suffices to prove the target concentration inequality in this ’easy’ context. Denote by P̂(t)h (· | s, a, b) the empirical estimate of Ph(· | s, a, b) calculated using {s(1), s(2), . . . , s(t)}. For a fixed t and s′, by applying the Bernstein inequality and its empirical version, we have with probability at least 1− p/S2ABT ,
|(Ph − P̂(t)h )(s ′ | s, a, b)| ≤ O
 √
min{Ph(s′ | s, a, b), P̂(t)h (s′ | s, a, b)}ι t + ι t . Now we can take a union bound over all s, a, b, h, s′ and t ∈ [K], and obtain that with probability at least 1− p, for all s, a, b, h, s′ and t ∈ [K],
|(Ph − P̂(t)h )(s ′ | s, a, b)| ≤ O
 √
min{Ph(s′ | s, a, b), P̂(t)h (s′ | s, a, b)}ι t + ι t . Note that the agent can reach each (s, a, b, h) for at most K times, this directly implies that the third inequality also holds with probability at least 1− p.
We begin with an auxiliary lemma bounding the lower-order term.
Lemma 19. Suppose event E0 holds, then there exists absolute constant c2 such that: if function g(s) satisfies |g|(s) ≤ (V kh+1 − V k h+1)(s) for all s, then
|(P̂kh − Ph)g(s, a, b)| ≤c2 ( 1
H min{P̂kh(V
k h+1 − V k h+1)(s, a, b),Ph(V k h+1 − V k h+1)(s, a, b)}+
H2Sι
max{Nkh (s, a, b), 1}
) .
Proof. By triangle inequality,
|(P̂kh − Ph)g(s, a, b)| ≤ ∑ s′ |(P̂kh − Ph)(s′|s, a, b)||g|(s′)
≤ ∑ s′ |(P̂kh − Ph)(s′|s, a, b)|(V k h+1 − V k h+1)(s ′)
(i) ≤O ∑ s′ ( √ ιP̂kh(s′|s, a, b) max{Nkh (s, a, b), 1} +
ι
max{Nkh (s, a, b), 1} )(V
k h+1 − V k h+1)(s ′)  (ii)
≤O (∑ s′ ( P̂kh(s′|s, a, b) H +
Hι
max{Nkh (s, a, b), 1} )(V
k h+1 − V k h+1)(s ′)
)
≤O
( P̂kh(V k h+1 − V k h+1)(s, a, b)
H +
H2Sι
max{Nkh (s, a, b), 1}
) ,
where (i) is by the second inequality in event E0 and (ii) is by AM-GM inequality. This proves the empirical version. Similarly, we can show
|(P̂kh − Ph)g(s, a, b)| ≤ O
( Ph(V k h+1 − V k h+1)(s, a, b)
H +
H2Sι
max{Nkh (s, a, b), 1}
) ,
Combining the two bounds completes the proof.
Now we can prove the upper and lower bounds are indeed upper and lower bounds of the best reponses. Lemma 20. Suppose event E0 holds. Then for all h, s, a, b and k ∈ [K], we haveQ k h(s, a, b) ≥ Q †,νk h (s, a, b) ≥ Q µk,† h (s, a, b) ≥ Q k h (s, a, b),
V k h(s) ≥ V †,νk h (s) ≥ V µk,† h (s) ≥ V k h(s).
(8)
Proof. The proof is by backward induction. Suppose the bounds hold for the Q-values in the (h + 1)th step, we now establish the bounds for the V -values in the (h + 1)th step and Q-values in the hth-step. For any state s:
V k h+1(s) = Dπkh+1Q k h+1(s)
≥ max µ Dµ×νkh+1Q k h+1(s)
≥ max µ Dµ×νkh+1Q †,νk h+1(s) = V †,νk h+1 (s).
(9)
Similarly, we can show V kh+1(s) ≤ V µk,† h+1 (s). Therefore, we have: for all s,
V k h+1(s) ≥ V †,νk h+1 (s) ≥ V ? h+1(s) ≥ V µk,† h+1 (s) ≥ V k h+1(s).
Now consider an arbitrary triple (s, a, b) in the hth step. We have
(Q k h −Q †,νk h )(s, a, b) ≥min {
(P̂khV k h+1 − PhV †,νk h+1 + β k h + γ k h)(s, a, b), 0 } ≥min { (P̂khV †,νk h+1 − PhV †,νk h+1 + β k h + γ k h)(s, a, b), 0
} = min { (P̂kh − Ph)(V †,νk h+1 − V
? h+1)(s, a, b)︸ ︷︷ ︸
(A)
+ (P̂kh − Ph)V ?h+1(s, a, b)︸ ︷︷ ︸ (B)
+ (βkh + γ k h)(s, a, b), 0
} .
(10)
Invoking Lemma 19 with g = V †,ν k
h+1 − V ?h+1,
|(A)| ≤ O
( P̂kh(V k h+1 − V k h+1)(s, a, b)
H +
H2Sι
max{Nkh (s, a, b), 1}
) .
By the first inequality in event E0,
|(B)| ≤ O
(√ H2ι
max{Nkh (s, a, b), 1}
) .
Plugging the two inequalities above back into (10) and recalling the definition of βkh and γ k h , we obtain Q k
h(s, a, b) ≥ Q †,νk h (s, a, b). Similarly, we can show Q k h (s, a, b) ≤ Qµ k,† h (s, a, b).
Finally we come to the proof of Theorem 3.
Proof of Theorem 3. Suppose event E0 holds. We first upper bound the regret. By Lemma 20, the regret can be upper bounded by∑
k
(V †,ν k
1 (s k 1)− V µk,† 1 (s k 1)) ≤ ∑ k (V k 1(s k 1)− V k 1(s k 1)).
For brevity’s sake, we define the following notations: ∆kh := (V k h − V k h)(s k h), ζkh := ∆ k h − (Q k h −Q k h )(skh, a k h, b k h),
ξkh := Ph(V k h+1 − V k h+1)(s k h, a k h, b k h)−∆kh+1.
(11)
Let Fkh be the σ-field generated by the following random variables:
{(sji , a j i , b j i , r j i )}(i,j)∈[H]×[k−1] ⋃ {(ski , aki , bki , rki )}i∈[h−1] ⋃ {skh}.
It’s easy to check ζkh and ξ k h are martingale differences with respect to Fkh . With a slight abuse of notation, we use βkh to refer to β k h(s k h, a k h, b k h) and N k h to refer to N k h (s k h, a k h, b k h) in the following proof.
We have
∆kh =ζ k h +
( Q k
h −Q k
h
) ( skh, a k h, b k h ) ≤ζkh + 2βkh + 2γkh + P̂kh(V k h+1 − V k h+1) ( skh, a k h, b k h
) (i) ≤ζkh + 2βkh + 2γkh + Ph(V k h+1 − V k h+1) ( skh, a k h, b k h
) + c2 ( Ph(V k h+1 − V k h+1)(s k h, a k h, b k h)
H +
H2Sι
max{Nkh , 1} ) (ii)
≤ ζkh + 2βkh + Ph(V k h+1 − V k h+1) ( skh, a k h, b k h ) + 2c2C ( Ph(V k h+1 − V k h+1)(s k h, a k h, b k h)
H +
H2Sι
max{Nkh , 1}
)
≤ζkh + ( 1 + 2c2C
H
) Ph(V k h+1 − V k h+1) ( skh, a k h, b k h ) + 4c2C (√ ιH2
max{Nkh , 1} +
H2Sι
max{Nkh , 1}
)
=ζkh +
( 1 + 2c2C
H
) ξkh + ( 1 + 2c2C
H
) ∆kh+1 + 4c2C (√ ιH2
max{Nkh , 1} +
H2Sι
max{Nkh , 1}
)
where (i) and (ii) follow from Lemma 19.
Define c3 := 1 + 2c2C and κ := 1 + c3/H . Recursing this argument for h ∈ [H] and summing over k,
K∑ k=1 ∆k1 ≤ K∑ k=1 H∑ h=1 [ κh−1ζkh + κ hξkh +O (√ ιH2 max{Nkh , 1} +
H2Sι
max{Nkh , 1}
)] .
By Azuma-Hoeffding inequality, with probability at least 1− p, K∑ k=1 H∑ h=1 κh−1ζkh ≤ O ( H √ HKι ) = O (√ H2Tι ) ,
K∑ k=1 H∑ h=1 κhξkh ≤ O ( H √ HKι ) = O (√ H2Tι ) .
(12)
By pigeon-hole argument, K∑ k=1 H∑ h=1 1√ max{Nkh , 1} ≤ ∑ s,a,b,h: NKh (s,a,b)>0 NKh (s,a,b)∑ n=1 1√ n +HSAB
≤O (√ HSABT +HSAB ) ,
K∑ k=1 H∑ h=1
1
max{Nkh , 1} ≤ ∑ s,a,b,h: NKh (s,a,b)>0 NKh (s,a,b)∑ n=1 1 n +HSAB
≤O(HSABι).
Put everything together, with probability at least 1− 2p (one p comes from P(E0) ≥ 1− p and the other is for equation (12)),
K∑ k=1 (V †,ν k 1 (s k 1)− V µk,† 1 (s k 1)) ≤ O (√ H3SABTι+H3S2ABι2 ) For the PAC guarantee, recall that we choose πout = πk ? such that k? = argmink ( V k 1 − V k 1 ) (s1).
As a result,
(V †,ν k? 1 − V µk ? ,† 1 )(s1) ≤ (V k? 1 − V k? 1 )(s1) ≤ 1 K O (√ H3SABTι+H3S2ABι2 ) ,
which concludes the proof.

heading: F.2 PROOF OF THEOREM 4
text: We use the same notation as in Appendix F.1 except the form of bonus. Besides, we define the empirical variance operator
V̂khV (s, a, b) := Vars′∼P̂kh(·|s,a,b)V (s ′)
and the true (population) variance operator VhV (s, a, b) := Vars′∼Ph(·|s,a,b)V (s ′)
for any function V ∈ ∆S . If Nkh (s, a, b) = 0, we simply set V̂khV (s, a, b) := H2 regardless of the choice of V .
As a result, the bonus terms can be written as
βkh(s, a, b) := C  √√√√ ιV̂kh[(V kh+1 + V kh+1)/2](s, a, b)
max{Nkh (s, a, b), 1} +
H2Sι
max{Nkh (s, a, b), 1}  (13) for some absolute constant C > 0.
Lemma 21. Let c1 be some large absolute constant. Define event E1 to be: for all h, s, a, b, s′ and k ∈ [K],  |[(P̂kh − Ph)V ?h+1](s, a, b)| ≤ c1 √ V̂khV ?h+1(s, a, b)ι max{Nkh (s, a, b), 1} + Hι max{Nkh (s, a, b), 1} , |(P̂kh − Ph)(s′ | s, a, b)| ≤ c1 √min{Ph(s′ | s, a, b), P̂kh(s′ | s, a, b)}ι max{Nkh (s, a, b), 1} + ι max{Nkh (s, a, b), 1} , ‖(P̂kh − Ph)(· | s, a, b)‖1 ≤ c1 √ Sι
max{Nkh (s, a, b), 1} .
We have P(E1) ≥ 1− p.
The proof of Lemma 21 is highly similar to that of Lemma 18. Specifically, the first two can be proved by following basically the same argument in Lemma 18; the third one is standard (e.g., equation (12) in Azar et al. (2017)). We omit the proof here.
Since the proof of Lemma 19 does not depend on the form of the bonus, it can also be applied in this section. As in Appendix F.1, we will prove the upper and lower bounds are indeed upper and lower bounds of the best reponses.
Lemma 22. Suppose event E1 holds. Then for all h, s, a, b and k ∈ [K], we haveQ k h(s, a, b) ≥ Q †,νk h (s, a, b) ≥ Q µk,† h (s, a, b) ≥ Q k h (s, a, b),
V k h(s) ≥ V †,νk h (s) ≥ V µk,† h (s) ≥ V k h(s).
(14)
Proof. The proof is by backward induction and very similar to that of Lemma 20. Suppose the bounds hold for the Q-values in the (h+ 1)th step, we now establish the bounds for the V -values in the (h+ 1)th step and Q-values in the hth-step.
The proof for the V -values is the same as (9).
For the Q-values, the decomposition (10) still holds and (A) is bounded using Lemma 19 as before. The only difference is that we need to bound (B) more carefully.
First, by the first inequality in event E1,
|(B)| ≤ O √ V̂khV ?h+1(s, a, b)ι max{Nkh (s, a, b), 1} + Hι max{Nkh (s, a, b), 1}  . By the relation of V -values in the (h+ 1)th step,
|[V̂kh(V k h+1 + V k h+1)/2]− V̂khV ?h+1|(s, a, b)
≤|[P̂kh(V k h+1 + V k h+1)/2] 2 − (P̂khV ?h+1)2|(s, a, b)
+ |P̂kh[(V k h+1 + V k h+1)/2] 2 − P̂kh(V ?h+1)2|(s, a, b)
≤4HP̂kh|(V k h+1 + V k h+1)/2− V ?h+1|(s, a, b)
≤4HP̂kh(V k h+1 − V k h+1)(s, a, b),
(15)
which implies√ ιV̂khV ?h+1(s, a, b)
max{Nkh (s, a, b), 1}
≤ √√√√ ι[V̂kh[(V kh+1 + V kh+1)/2] + 4HP̂kh(V kh+1 − V kh+1)](s, a, b) max{Nkh (s, a, b), 1}
≤ √√√√ ιV̂kh[(V kh+1 + V kh+1)/2](s, a, b) max{Nkh (s, a, b), 1} + √√√√4ιHP̂kh(V kh+1 − V kh+1)](s, a, b) max{Nkh (s, a, b), 1}
(i) ≤ √√√√ ιV̂kh[(V kh+1 + V kh+1)/2](s, a, b) max{Nkh (s, a, b), 1} + P̂kh(V k h+1 − V k h+1) H +
4H2ι
max{Nkh (s, a, b), 1} ,
(16)
where (i) is by AM-GM inequality.
Plugging the above inequalities back into (10) and recalling the definition of βkh and γ k h completes the proof.
We need one more lemma to control the error of the empirical variance estimator:
Lemma 23. Suppose event E1 holds. Then for all h, s, a, b and k ∈ [K], we have
|V̂kh[(V k h+1 + V k h+1)/2]− VhV π k h+1|(s, a, b)
≤4HPh(V k h+1 − V k h+1)(s, a, b) +O
( 1 +
H4Sι
max{Nkh (s, a, b), 1}
) .
Proof. By Lemma 22, we have V k h(s) ≥ V π k h (s) ≥ V k h(s). As a result,
|V̂kh[(V k h+1 + V k h+1)/2]− VhV π k h+1|(s, a, b)
=|[P̂kh(V k h+1 + V k h+1) 2/4− Ph(V π k h+1) 2](s, a, b)− [(P̂kh(V k h+1 + V k h+1)) 2/4− (PhV π k h+1) 2](s, a, b)|
≤[P̂kh(V k h+1) 2 − Ph(V kh+1)2 − (P̂khV k h+1) 2 + (PhV k h+1) 2](s, a, b)
≤[|(P̂kh − Ph)(V k h+1) 2|+ |Ph[(V k h+1) 2 − (V kh+1)2]|
+ |(P̂khV k h+1) 2 − (PhV kh+1)2|+ |(PhV k h+1) 2 − (PhV k h+1) 2|](s, a, b)
These terms can be bounded separately by using event E1:
|(P̂kh − Ph)(V k h+1) 2|(s, a, b) ≤ H2‖(P̂kh − Ph)(· | s, a, b)‖1 ≤ O(H2
√ Sι
max{Nkh (s, a, b), 1} ),
|Ph[(V k h+1) 2 − (V kh+1)2]|(s, a, b) ≤ 2H[Ph(V k h+1 − V k h+1)](s, a, b),
|(P̂khV k h+1) 2 − (PhV kh+1)2|(s, a, b) ≤ 2H[(P̂kh − Ph)V k h+1](s, a, b) ≤ O(H2
√ Sι
max{Nkh (s, a, b), 1} ),
|(PhV kh+1)2 − (PhV k h+1) 2|(s, a, b) ≤ 2H[Ph(V k h+1 − V k h+1)](s, a, b). Combining with H2 √
Sι max{Nkh (s,a,b),1}
≤ 1 + H 4Sι
max{Nkh (s,a,b),1} completes the proof.
Finally we come to the proof of Theorem 4.
Proof of Theorem 4. Suppose event E1 holds. We define ∆kh, ζ k h abd ξ k h as in the proof of Theorem 3. As before we have
∆kh ≤ζkh + (
1 + c3 H
) Ph(V k h+1 − V k h+1) ( skh, a k h, b k h ) + 4c2C  √√√√ ιV̂kh[(V kh+1 + V kh+1)/2](skh, akh, bkh)
max{Nkh (skh, akh, bkh), 1} +
H2Sι
max{Nkh (skh, akh, bkh), 1}
 . (17)
By Lemma 23,√√√√ ιV̂kh[(V kh+1 + V kh+1)/2](s, a, b) max{Nkh (s, a, b), 1}
≤O  √ ιVhV π k h+1(s, a, b) + ι
max{Nkh (s, a, b), 1} + √√√√HιPh(V kh+1 − V kh+1)(s, a, b) max{Nkh (s, a, b), 1} + H2 √ Sι max{Nkh (s, a, b), 1}  ≤c4 √ ιVhV πkh+1(s, a, b) + ι max{Nkh (s, a, b), 1} + Ph(V k h+1 − V k h+1)(s, a, b) H + H2 √ Sι max{Nkh (s, a, b), 1}
, (18)
where c4 is some absolute constant. Define c5 := 4c2c4C + c3 and κ := 1 + c5/H . Plugging (18) back into (17), we have
∆kh ≤κ∆kh+1 + κξkh + ζkh +O (√ ιVhV π k h+1(s k h, a k h, b k h)
Nkh (s k h, a k h, b k h)
+
√ ι
Nkh (s k h, a k h, b k h)
+ H2Sι
Nkh (s k h, a k h, b k h)
)} .
(19)
Recursing this argument for h ∈ [H] and summing over k, K∑ k=1 ∆k1 ≤ K∑ k=1 H∑ h=1 [ κh−1ζkh + κ hξkh
+O √ ιVhV πkh+1(skh, akh, bkh) max{Nkh , 1} + √ ι max{Nkh , 1} +
H2Sι
max{Nkh , 1} ]. The remaining steps are the same as that in the proof of Theorem 3 except that we need to bound the sum of variance term.
By Cauchy-Schwarz, K∑ k=1 H∑ h=1 √ VhV π k h+1(s k h, a k h, b k h) max{Nkh (skh, akh, bkh), 1} ≤ √√√√ K∑ k=1 H∑ h=1 VhV π k h+1(s k h, a k h, b k h) · K∑ k=1 H∑ h=1
1
max{Nkh (skh, akh, bkh), 1} .
By the Law of total variation and standard martingale concentration (see Lemma C.5 in Jin et al. (2018) for a formal proof), with probability at least 1− p, we have
K∑ k=1 H∑ h=1 VhV π k h+1(s k h, a k h, b k h)≤O ( HT +H3ι ) .
Putting all relations together, we obtain that with probability at least 1 − 2p (one p comes from P(E1) ≥ 1− p and the other comes from the inequality for bounding the variance term),
Regret(K) = K∑ k=1 (V †,ν k 1 − V µk,† 1 )(s1) ≤ O( √ H2SABTι+H3S2ABι2).
Rescaling p completes the proof.

heading: G PROOF FOR SECTION 4 – REWARD-FREE LEARNING

heading: G.1 PROOF OF THEOREM 5
text: In this section, we prove Theorem 5 for the single reward function case, i.e., N = 1. The proof for multiple reward functions (N > 1) simply follows from taking a union bound, that is, replacing the failure probability p by Np.
Let (µk, νk) be an arbitrary Nash-equilibrium policy of M̂k := (P̂k, r̂k), where P̂k and r̂k are our empirical estimate of the transition and the reward at the beginning of the k’th episode in Algorithm 2, respectively. We use Nkh (s, a, b) to denote the number we have visited the state-action tuple (s, a, b) at the h-th step before the k’th episode. And the bonus used in the k’th episode can be written as
βkh(s, a, b) := C
(√ H2ι
max{Nkh (s, a, b), 1} +
H2Sι
max{Nkh (s, a, b), 1}
) , (20)
where ι = log(SABT/p) and C is some large absolute constant.
We use Q̂k and V̂ k to denote the empirical optimal value functions of M̂k as following.Q̂ k h(s, a, b) = (P̂khV̂h+1)(s, a, b) + r̂kh(s, a, b),
V̂ kh (s) = max µ min ν
Dµ×νQ̂kh(s). (21)
Since (µk, νk) is a Nash-equilibrium policy of M̂k, we also have V̂ kh (s) = Dµk×νkQ̂kh(s). We begin with stating a useful property of matrix game that will be frequently used in our analysis. Since its proof is quite simple, we omit it here.
Lemma 24. Let X,Y,Z ∈ RA×B and ∆d be the d-dimensional simplex. Suppose |X−Y| ≤ Z, where the inequality is entry-wise. Then∣∣∣∣maxµ∈4A minν∈4B µ>Xν − maxµ∈4A minν∈4B µ>Yν
∣∣∣∣ ≤ maxi,j Zij . (22) Lemma 25. Let c1 be some large absolute constant such that c21 + c1 ≤ C. Define event E1 to be: for all h, s, a, b, s′ and k ∈ [K], |[(P̂kh − Ph)V ?h+1](s, a, b)| ≤ c1 10 √ H2ι max{Nkh (s, a, b), 1} , |(r̂kh − rh)(s, a, b)| ≤ c1 10 √ H2ι max{Nkh (s, a, b), 1} , |(P̂kh − Ph)(s′ | s, a, b)| ≤ c1 10 √ P̂kh(s′ | s, a, b)ι max{Nkh (s, a, b), 1} + ι max{Nkh (s, a, b), 1} . (23)
We have P(E1) ≥ 1− p.
Proof. The proof is standard and folklore: apply standard concentration inequalities and then take a union bound. For completeness, we provide the proof of the third one here.
Consider a fixed (s, a, b, h) tuple.
Let’s consider the following equivalent random process: (a) before the agent starts, the environment samples {s(1), s(2), . . . , s(K)} independently from Ph(· | s, a, b); (b) during the interaction between the agent and environment, the ith time the agent reaches (s, a, b, h), the environment will make the agent transit to s(i). Note that the randomness induced by this interaction procedure is exactly the same as the original one, which means the probability of any event in this context is the same as in the original problem. Therefore, it suffices to prove the target concentration inequality in
this ’easy’ context. Denote by P̂(t)h (· | s, a, b) the empirical estimate of Ph(· | s, a, b) calculated using {s(1), s(2), . . . , s(t)}. For a fixed t and s′, by the empirical Bernstein inequality, we have with probability at least 1− p/S2ABT ,
|(Ph − P̂(t)h )(s ′ | s, a, b)| ≤ O
 √
P̂(t)h (s′ | s, a, b)ι t + ι t . Now we can take a union bound over all s, a, b, h, s′ and t ∈ [K], and obtain that with probability at least 1− p, for all s, a, b, h, s′ and t ∈ [K],
|(Ph − P̂(t)h )(s ′ | s, a, b)| ≤ O
 √
P̂(t)h (s′ | s, a, b)ι t + ι t . Note that the agent can reach each (s, a, b, h) for at most K times, this directly implies that the third inequality also holds with probability at least 1− p.
The following lemma states that the empirical optimal value functions are close to the true optimal ones, and their difference is controlled by the exploration value functions calculated in Algorithm 2.
Lemma 26. Suppose event E1 (defined in Lemma 25) holds. Then for all h, s, a, b and k ∈ [K], we have,  ∣∣∣Q̂kh(s, a, b)−Q?h(s, a, b)∣∣∣ ≤ Q̃kh(s, a, b),∣∣∣V̂ kh (s)− V ?h (s)∣∣∣ ≤ Ṽ kh (s). (24) Proof. Let’s prove by doing backward induction on h. The case of h = H + 1 holds trivially.
Assume the conclusion hold for (h+ 1)’th step. For h’th step,∣∣∣Q̂kh(s, a, b)−Q?h(s, a, b)∣∣∣ ≤ min
{∣∣∣[(P̂kh − Ph)V ?h+1](s, a, b)∣∣∣+ |(r̂kh − rh)(s, a, b)|+ ∣∣∣[P̂kh(V̂ kh+1 − V ?h+1)](s, a, b)∣∣∣ , H} (i)
≤ min { βkh(s, a, b) + (P̂khṼ kh+1)(s, a, b), H } (ii) = Q̃kh(s, a, b),
(25) where (i) follows from the induction hypothesis and event E1, and (ii) follows from the definition of Q̃kh. By Lemma 24, we immediately obtain |V̂ kh (s)− V ?h (s)| ≤ Ṽ kh (s).
Now, we are ready to establish the key lemma in our analysis using Lemma 26.
Lemma 27. Suppose event E1 (defined in Lemma 25) holds. Then for all h, s, a, b and k ∈ [K], we have {
|Q̂kh(s, a, b)−Q †,νk h (s, a, b)| ≤ αhQ̃ k h(s, a, b), |V̂ kh (s)− V †,νk h (s)| ≤ αhṼ k h (s),
(26)
and { |Q̂kh(s, a, b)−Q µk,† h (s, a, b)| ≤ αhQ̃ k h(s, a, b),
|V̂ kh (s)− V µk,† h (s)| ≤ αhṼ k h (s),
(27)
where αH+1 = 0 and αh = [(1 + 1H )αh+1 + 1 H ] ≤ 4.
Proof. We only prove the first set of inequalities. The second one follows exactly the same. Again, the proof is by performing backward induction on h. It is trivial to see the conclusion holds for
(H + 1)’th step with αH+1 = 0. Now, assume the conclusion holds for (h + 1)’th step. For h’th step,
|Q̂kh(s, a, b)−Q †,νk h (s, a, b)| ≤min { |[(P̂kh − Ph)(V †,νk h+1 − V ? h+1)](s, a, b)|+ |(P̂kh − Ph)V ?h+1(s, a, b)|
+ |(r̂kh − rh)(s, a, b)|+ |[P̂h(V̂ kh+1 − V †,νk h+1 )](s, a, b)|, H } ≤min { |[(P̂kh − Ph)(V †,νk h+1 − V
? h+1)](s, a, b)|︸ ︷︷ ︸
(T1)
+c1
√ H2ι
max{Nkh (s, a, b), 1}
+ |[P̂h(V̂ kh+1 − V †,νk h+1 )](s, a, b)|︸ ︷︷ ︸
(T2)
, H } ,
(28)
where the second inequality follows from the definition of event E1.
We can control the term (T1) by combining Lemma 26 and the induction hypothesis to bound |V †,ν k
h+1 − V ?h+1|, and then applying the third inequality in event E1: (T1) ≤ ∑ s′ |P̂kh(s′ | s, a, b)− Ph(s′ | s, a, b)||V †,νk h+1 − V ? h+1(s ′)|
≤ ∑ s′ |P̂kh(s′ | s, a, b)− Ph(s′ | s, a, b)| ( |V †,ν k h+1 − V̂ k h+1(s ′)|+ |V̂ kh+1 − V ?h+1(s′)| )
≤ ∑ s′ |P̂kh(s′ | s, a, b)− Ph(s′ | s, a, b)|(αh+1 + 1)Ṽ kh+1
≤ (αh+1 + 1) H (P̂khṼ kh+1)(s, a, b) + c21(αh+1 + 1)H 2Sι
max{Nkh (s, a, b), 1} .
(29)
The term (T2) is bounded by directly applying the induction hypothesis
|[P̂h(V̂ kh+1 − V †,νk h+1 )](s, a, b)| ≤ αh+1[P̂hṼ k h+1](s, a, b). (30)
Plugging (29) and (30) into (28), we obtain∣∣∣Q̂kh(s, a, b)−Q†,νkh (s, a, b)∣∣∣ ≤min { (1 + 1
H )αh+1 +
1
H [P̂khṼ kh+1](s, a, b) + c1
√ H2ι
max{Nkh (s, a, b), 1}
+ c21(αh+1 + 1)H 2Sι
max{Nkh (s, a, b), 1} , H } (i)
≤min {( (1 + 1
H )αh+1 +
1
H
) [P̂khṼ kh+1](s, a, b) + βkh(s, a, b), H } (ii)
≤ ( (1 + 1
H )αh+1 +
1
H
) Q̃kh(s, a, b),
(31)
where (i) follows from the definition of βkh , and (ii) follows from the definition of Q̃ k h. Therefore, by (31), choosing αh = [(1 + 1H )αh+1 + 1 H ] suffices for the purpose of induction.
Now, let’s prove the inequality for V functions.
|(V̂ kh − V †,νk h )(s)| (i) = | max
µ∈4A (Dµ,νkQ̂kh)(s)− max µ∈4A (Dµ,νkQ
†,νk h )(s)|
(ii)
≤ max a,b
[ αhQ̃ k h(s, a, b) ] = αhṼ k h (s),
(32)
where (i) follows from the definition of V̂ kh and V †,νk h , and (ii) uses (31) and Lemma 24.
Theorem 28 (Guarantee for UCB-VI from Azar et al. (2017)). For any p ∈ (0, 1], choose the exploration bonus βt in Algrothm 2 as (20). Then, with probability at least 1− p,
K∑ k=1 Ṽ k1 (s1) ≤ O( √ H4SAKι+H3S2Aι2).
Proof of Theorem 5. Recall that out = arg mink∈[K] Ṽ kh (s). By Lemma 27 and Theorem 28, with probability at least 1− 2p,
V †,ν out h (s)− V µout,† h (s) ≤|V †,νout h (s)− V̂ out h (s)|+ |V̂ outh (s)− V µout,† h (s)| ≤8Ṽ outh (s) ≤ O( √ H4SAι
K + H3S2Aι2 K ).
(33)
Rescaling p completes the proof.
G.2 VANILLA NASH VALUE ITERATION
Here, we provide one optional algorithm, Vanilla Nash VI, for computing the Nash equilibrium policy for a known model. Its only difference from the value iteration algorithm for MDPs is that the maximum operator is replaced by the minimax operator in Line 7. We remark that the Nash equilibrium for a two-player zero-sum game can be computed in polynomial time.
Algorithm 5 Vanilla Nash Value Iteration
1: Input: model M̂ = (P̂, r̂). 2: Initialize: for all (s, a, b), VH+1(s, a, b)← 0. 3: for step h = H,H − 1, . . . , 1 do 4: for (s, a, b) ∈ S ×A× B do 5: Qh(s, a, b)← [P̂hVh+1](s, a, b) + r̂h(s, a, b). 6: for s ∈ S do 7: (µ̂h(· | s), ν̂h(· | s))← NASH-ZERO-SUM(Qh(s, ·, ·)). 8: Vh(s)← µ̂h(· | s)>Qh(s, ·, ·)ν̂h(· | s). 9: Output (µ̂, ν̂)← {(µ̂h(· | s), ν̂h(· | s))}(h,s)∈[H]×S .
By recalling the definition of best responses in Appendix D, one can directly see that the output policy (µ̂, ν̂) is a Nash equilibrium for M̂.

heading: G.3 PROOF OF THEOREM 6
text: In this section, we first prove a Θ(AB/ 2) lower bound for reward-free matrix games, i.e., S = H = 1, and then generalize it to Θ(SABH2/ 2) for the Markov games setting.

heading: G.3.1 REWARD-FREE MATRIX GAMES
text: In the matrix game, let the max-player pick row and the min-player pick column. We consider the following family of Bernoulli matrix games:
M( ) = { M∈ RA×B withMab = 1
2 + (1− 2 · 1{a 6= a?&b = b?}) : (a?, b?) ∈ [A]× [B]
} ,
(34) where in matrix gameM, the reward is sampled from Bernoulli(Mab) if the max-player picks the a’th row and the min-player picks the b’th column.
Min-player
Max-player
action 1 . . . b? − 1 b? b? + 1 . . . B 1 + . . . + − + . . . + ... ... . . . ... ... ... . . .
... a? − 1 + . . . + − + . . . + a? + . . . + + + . . . + a? + 1 + . . . + − + . . . + ... ... . . . ... ... ... . . .
... A + . . . + − + . . . +
(35)
Above, we visualize the hard instance by using + and− to represent 1/2+ and 1/2− , respectively. It is direct to see that the optimal policy for the max-player is always picking the a?’th row and the optimal policy for the min-player is always picking the b?’th column. If the max-player picks the a?’th row with probability smaller than 2/3, it is at least /10 suboptimal.
Lemma 29. For any fixed matrix gameM from M( ) and N ∈ N, if an algorithm A can output a policy that is at most /10 suboptimal with probability at least p using at most N samples, then there exists an algorithm Â that can identify the best row inM with probability at least p using at most N samples.
Proof. We simply define Â as running algorithm A and choosing the most played row by its outputted policy as the guess for the best row. By simple calculation, one can show Â will output the best row inM with probability at least p.
Lemma 29 directly implies that in order to prove the desired lower bound for matrix games:
Claim 30. for any algorithmA using at mostN = AB/(103 2) samples, there exists a matrix game M in M( ) such that when running A onM, it will output a policy that is at least /10 suboptimal for the max-player with probability at least 1/4,
it suffices to prove the following claim:
Claim 31. for any algorithm Â using at mostN = AB/(103 2) samples, there exists a matrix game M in M( ) such that when running Â onM, it will fail to identify the optimal row with probability at least 1/4.
Proof of Claim 31. WLOG, we assume Â is deterministic. Since this is the reward-free setting, being deterministic means that algorithm Â will always pull each arm (a, b) for some fixed n(a, b) times and then output a guess for a? which is a function of the reward revealed.
Denote by L the reward revealed after algorithm Â’s pulling. Denote by P? the probability induced by pickingM uniformly at random from M( ) and running Â onM. Denote by Pa,b the probability induced by running Â onM, whose indices of the special row and the special column are a and b, respectively. Denote by P0,b the probability induced by runningA onM, whose b’th column are all 1/2 − and other columns are all 1/2 + . We want to mention that theM we use to define P0,b does not belong to M( ).
We have
P?(Â(L) 6= a?) ≥ 1
AB ∑ a,b P0,b(Â(L) 6= a)− 1 AB ∑ a,b ‖Pa,b − P0,b‖1
≥ 1− 1 A − 1 AB ∑ a,b √ 2KL(P0,b‖Pa,b)
= 1− 1 A − 1 AB ∑ a,b
√ 2n(a, b)[( 1
2 − ) log 1 2 − 1 2 + + ( 1 2 + ) log 1 2 + 1 2 − ]
≥ 1− 1 A − 10 AB ∑ a,b √ n(a, b) 2
≥ 1− 1 A − √ 100N 2 AB .
(36)
Choosing N = AB/(103 2) concludes the proof.

heading: G.3.2 REWARD-FREE MARKOV GAMES
text: Now let’s generalize the Θ(AB/ 2) lower bound to Θ(SABH2/ 2) for reward-free Markov games.
We define the following family of MDPs: J( ) := { J (a?, b?) : (a?, b?) ∈ [A]H×S × [B]H×S } , (37)
where MDP J (a?, b?) is defined as below:
• States and actions: J (a?, b?) is a finite-horizon MDP with S + 1 states of length H + 1. There is a fixed initial state s0 in the first step, S states {s1, . . . , sS} for the remaining steps. The two players have A and B actions, respectively.
• Rewards: there is no reward in the first step. For the remaining steps h ∈ {2, . . . ,H + 1}, if the agent takes action (a, b) at state si in the hth step, it will receive a binary reward sampled from
Bernoulli (1
2 + (1− 2 · 1{a 6= a?h−1,i&b = b?h−1,i}) H ) • Transitions: Regardless of the current state, actions and index of steps, the agent will
always transit to one of s1, . . . , sS uniformly at random.
It is direct to see that J (a?, b?) is a collection of SH independent matrix games from M( /H). Therefore, the optimal policy for the max player is to always pick action a?h−1,i whenever it reaches state si in the hth step (h ≥ 2). In other words, a?h−1,i is the unique optimal action for the step-state pair (h, i).
At a high level, in order to find an -optimal policy for the above Markov game, we need to identify at least half of the entries of a?. Therefore, the number of episodes should be at least
Θ
( AB
( /H)2
) × S
2 = Θ
( ABSH2
2
) .
Below we provide a formal proof of this argument, which is almost the same as that for the setting of reward-free matrix games.
We start by proving an analogue of Lemma 29.
Lemma 32. For any fixed matrix game J (a?, b?) from J( ) and N ∈ N, if an algorithm A can output a policy that is at most /103 suboptimal with probability at least p using at mostN samples, then there exists an algorithm Â that can correctly identify at least SH − bSH/500c entries of a? with probability at least p using at most N samples.
Proof. Denote by π the output policy for the max player. Denote by Z the collection of (h, i)’s in [H]× [S] such that πh+1(a?h,i | si) ≤ 2/3.
Observe that each time the max player picks a suboptimal action, it will incur an 2 /H suboptimality in expectation. As a result, if π is at most /103-suboptimal, we must have
1
S ∑ (h,i)∈Z (1− πh+1(a?h,i | si))× 2 H ≤ 103 ,
which implies |Z| ≤ SH/500, that is, for at most bSH/500c different i’s, π(a?i | si) ≤ 2/3. Therefore, we can simply pick argmaxa πh+1(a | si) as the guess for a?h,i. Since policy π is at most /103 suboptimal with probability at least p, we can correctly identify the optimal actions for at least SH − bSH/500c different (s, h) pairs also with probability no smaller than p.
Lemma 32 directly implies that in order to prove the desired lower bound for reward-free Markov games:
Claim 33. for any algorithmA interacting with the environment for at mostK = ABSH2/(104 2) episodes, there exists J ∈ J( ) such that when running A on J , it will output a policy that is at least /103 suboptimal for the max-player with probability at least 1/4,
it suffices to prove the following claim:
Claim 34. for any algorithm Â interacting with the environment for at mostK = ABSH2/(104 2) episodes, there exists J ∈ J( ) such that when running Â on J , it will fail to identify the optimal actions for at least bSH/500c+ 1 different (s, h) pairs with probability at least 1/4.
Proof of Claim 34. Denote by P? (E?) the probability (expectation) induced by picking J (a?, b?) uniformly at random from J( ) and running Â on J . Denote by nwrong the number of (s, h) pairs for which Â fails to identify the optimal actions. Denote by errorh,i the indicator function of the event that Â fails to identify the optimal action for (h+ 1, i).
We prove by contradiction. Suppose for any J ∈ J( ), Â can identify the optimal actions for at least SH − bSH/500c different (s, h) pairs with probability larger than 3/4. Then we have
E?[nwrong] ≤ 1 4 × SH + 3 4 × ⌊ SH 500 ⌋ ≤ 101SH 400 .
Since ∑
(h,i)∈[H]×[S] E?[errorh,i] = E?[nwrong], there must exists (h′, i′) ∈ [H] × [S] such that E?[errorh′,i′ ] ≤ 101/400. However, in the following, we show that for every (h, i) ∈ [H]× [S], Â fails to identify the optimal action for the step-state pair (h+1, i) with probability at least 1/3, which directly implies E?[errorh,i] ≥ 1/3 for all (h, i) ∈ [H] × [S]. As a result, we obtain a contraction and Claim 34 holds.
Now, let us prove that for every (h, i) ∈ [H] × [S], E?[errorh,i] ≥ 1/6. WLOG, we assume Â is deterministic and it runs for exactly K = ABSH2/(103 2) episodes. In the following, we consider a fixed (h′, i′) pair. For technical reason, we define MDP J−(h′,i′)(a?, b?) as below:
• States, actions and transitions: same as J (a?, b?).
• Rewards: there is no reward in the first step. For the remaining steps h ∈ {2, . . . ,H + 1}, if the agent takes action (a, b) at state si in the hth step such that (h − 1, i) 6= (h′, i′), it will receive a binary reward sampled from
Bernoulli (1
2 + (1− 2 · 1{a 6= a?h−1,i&b = b?h−1,i}) H
) ,
otherwise it will receive a binary reward sampled from Bernoulli (1
2 + (1− 2 · 1{b = b?h−1,i}) H
) .
Intuitively, J−(h′,i′)(a?, b?) is the same as J (a?, b?) except that for the max player, all its actions at state si′ in the h′ th step are equivalent. In other words, J−(h′,i′)(a?, b?) is independent of a?h′,i′ .
To proceed, we need to define the following notations: denote by n(a, b) the number of times Â picks action (a, b) at state si′ in the (h′ + 1)
th step; denote by P(· | J (a?, b?)) (E[· | J (a?, b?)]) the probability (expectation) induced by running algorithm Â on J (a?, b?); similarly, we define P(· | J−(h′,i′)(a?, b?)) (E[· | J−(h′,i′)(a?, b?)]); also recall that we denote by P? (E?) the probability (expectation) induced by picking J (a?, b?) uniformly at random from J( ) and running Â on J ; denote by L the whole trajectory of states, actions and rewards produced by algorithm Â in N episodes; with slight abuse of notation, denote by Â(L) the guess of Â for a?h′,i′ based on L.
First, note that for any (a, b) ∈ [A] × [B], E[n(s, a) | J−(h′,i′)(a?, b?)] is independent of (h′, i′,a?, b?) because the agent cannot observe any reward when interacting with the environment and the transition dynamics of different J−(h′,i′)(a?, b?)’s are the same. For simplicity of notation, we denote this expectation by m(a, b). Note that ∑ a,bm(a, b) = K/S because the agent always reach state si′ in the (h′ + 1) th step with probability 1/S regardless of the actions taken.
We have
P?(Â(L) 6= a?h′,i′)
= 1
(AB)SH ∑ (a?,b?)∈[A]SH×[B]SH P(Â(L) 6= a?h′,i′ | J (a?, b?))
≥ 1 (AB)SH ∑ (a?,b?)∈[A]SH×[B]SH ( P(Â(L) 6= a?h′,i′ | J−(h′,i′)(a?, b?))
− ∥∥P(L = · | J−(h′,i′)(a?, b?))− P(L = · | J (a?, b?))∥∥1)
= 1− 1 A − 1 (AB)SH ∑ (a?,b?)∈[A]SH×[B]SH∥∥P(L = · | J−(h′,i′)(a?, b?))− P(L = · | J (a?, b?))∥∥1 ≥ 1− 1 A − 1 (AB)SH
∑ (a?,b?)∈[A]SH×[B]SH√
2KL(P(L = · | J−(h′,i′)(a?, b?)),P(L = · | J (a?, b?)))
= 1− 1 A − 1 (AB)SH ∑ (a?,b?)∈[A]SH×[B]SH√
2m(a?h′,i, b ? h′,i)
[ ( 1
2 − H
) log 1 2 − H
1 2 + H
+ ( 1
2 + H ) log
1 2 + H 1 2 − H ] = 1− 1
A − 1 AB ∑ (a?i,h,b
? i,h)∈[A]×[B]√
2m(a?h′,i, b ? h′,i)
[ ( 1
2 − H
) log 1 2 − H
1 2 + H
+ ( 1
2 + H ) log
1 2 + H 1 2 − H ] ≥ 1− 1
A − 10 AB ∑ a,b √ m(a, b) 2 H2
≥ 1− 1 A − 10 ABH
√ AB ∑ a,b m(a, b) = 1− 1 A − √ 100K 2 SABH2 .
(38)
Plugging in K = SABH2/(104 2) completes the proof.

heading: H PROOF FOR APPENDIX C – MULTI-PLAYER GENERAL-SUM MARKOV GAMES

heading: H.1 PROOF OF THEOREM 15

heading: H.1.1 NE VERSION
text: In this section, we prove Theorem 15 (NE version). As before, we begin with proving the optimistic estimations are indeed upper bounds of corresponding value and Q-value functions. Lemma 35. With probability 1− p, for any (s,a, h, k, i):
Q k h,i (s,a) ≥ Q †,πk−i h,i (s,a) , Q k h,i (s,a) ≤ Qπ k h,i (s,a) , (39)
V k h,i (s) ≥ V †,πk−i h,i (s) , V k h,i (s) ≤ V π k h,i (s) . (40)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know at the (H + 1)-th step,V kH+1,i (s) = V †,πk−i H+1,i (s) = 0. Now, assume the inequality (40) holds for the (h+ 1)-th step, for the h-th step, by definition of the Q functions,
Q k h,i (s,a)−Q †,πk−i h,i (s,a) = [ P̂khV k h+1,i ] (s,a)− [ PhV †,πk−i h+1,i ] (s,a) + βt
=P̂kh ( V k h+1,i − V †,πk−i h+1,i ) (s,a)︸ ︷︷ ︸
(A)
+ ( P̂kh − Ph ) V †,πk−i h+1,i (s,a)︸ ︷︷ ︸
(B)
+ βt.
By induction hypothesis, for any s′, ( V k
h+1,i − V †,πk−i h+1,i
) (s′) ≥ 0, and thus (A) ≥ 0. By uniform
concentration (e.g., Lemma 12 in Bai & Jin (2020)), (B) ≤ C √ SH2ι/Nkh (s,a) = βt. Putting everything together we have Qkh,i (s,a) − Q †,πk−i h,i (s,a) ≥ 0. The second inequality can be proved similarly.
Now assume inequality (39) holds for the h-th step, by definition of value functions and Nash equilibrium,
V k h,i (s) = DπkQ k
h,i (s) = max µ Dµ×πk−iQ k h,i (s) .
By Bellman equation,
V †,πk−i h,i (s) = maxµ Dµ×πk−iQ †,πk−i h,i (s) .
Since by induction hypothesis, for any (s,a), Q k h,i (s,a) ≥ Q †,πk−i h,i (s,a). As a result, we also have V k
h,i (s) ≥ V †,πk−i h,i (s), which is exactly inequality (40) for the h-th step. The second inequality can
be proved similarly.
Proof of Theorem 15. Let us focus on the i-th player and ignore the subscript when there is no confusion. To bound
max i
( V †,πk−i 1,i − V πk 1,i )( skh ) ≤ max
i
( V k
1,i − V k 1,i ) ( skh ) ,
we notice the following propogation:(Q k h,i −Q k h,i )(s,a) ≤ P̂kh(V k h+1,i − V k h+1,i)(s,a) + 2β k h(s,a),
(V h,i − V h,i)(s) = [Dπh(Q k h,i −Q k h,i )](s).
(41)
We can define Q̃kh and Ṽ k h recursively by Ṽ k H+1 = 0 and{
Q̃kh(s,a) = P̂khṼ kh+1(s,a) + 2βkh(s,a), Ṽ kh (s) = [DπhQ̃kh](s). (42)
Then we can prove inductively that for any k, h, s and a we havemaxi (Q k h,i −Q k h,i )(s,a) ≤ Q̃kh(s,a),
max i
(V h,i − V h,i)(s) ≤ Ṽ kh (s). (43)
Thus we only need to bound ∑K k=1 Ṽ
k 1 (s). Define the shorthand notation βkh := β k h(s k h,a k h), ∆kh := Ṽ k h (s k h), ζkh := DπkQ̃kh ( skh ) − Q̃kh(skh,akh),
ξkh := PhṼ kh (skh,akh)−∆kh+1.
(44)
We can check ζkh and ξ k h are martingale difference sequences. As a result, ∆kh =DπkQ̃kh ( skh )
=ζkh + Q̃ k h ( skh,a k h ) =ζkh + 2β k h + P̂khṼ kh+1 ( skh,a k h
) ≤ζkh + 3βkh + PhṼ kh+1 ( skh,a k h
) =ζkh + 3β k h + ξ k h + ∆ k h+1.
Recursing this argument for h ∈ [H] and taking the sum,
K∑ k=1 ∆k1 ≤ K∑ k=1 ( ζkh + 3β k h + ξ k h ) ≤ O
S √√√√H3Tι M∏
i=1
Ai
 .

heading: H.1.2 CCE VERSION
text: The proof is very similar to the NE version. Specifically, the only part that uses the properties of NE there is Lemma 35. We prove a counterpart here. Lemma 36. With probability 1− p, for any (s,a, h, k, i):
Q k h,i (s,a) ≥ Q †,πk−i h,i (s,a) , Q k h,i (s,a) ≤ Qπ k h,i (s,a) , (45)
V k h,i (s) ≥ V †,πk−i h,i (s) , V k h,i (s) ≤ V π k h,i (s) . (46)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know at the (H + 1)-th step,V kH+1,i (s) = V †,πk−i H+1,i (s) = 0. Now, assume the inequality (40) holds for the (h+ 1)-th step, for the h-th step, by definition of the Q functions,
Q k h,i (s,a)−Q †,πk−i h,i (s,a) = [ P̂khV k h+1,i ] (s,a)− [ PhV †,πk−i h+1,i ] (s,a) + βt
=P̂kh ( V k h+1,i − V †,πk−i h+1,i ) (s,a)︸ ︷︷ ︸
(A)
+ ( P̂kh − Ph ) V †,πk−i h+1,i (s,a)︸ ︷︷ ︸
(B)
+ βt.
By induction hypothesis, for any s′, ( V k
h+1,i − V †,πk−i h+1,i
) (s′) ≥ 0, and thus (A) ≥ 0. By uniform
concentration, (B) ≤ C √ SH2ι/Nkh (s,a) = βt. Putting everything together we haveQ k h,i (s,a)− Q †,πk−i h,i (s,a) ≥ 0. The second inequality can be proved similarly.
Now assume inequality (45) holds for the h-th step, by definition of value functions and CCE,
V k h,i (s) = DπkQ k
h,i (s) = max µ Dµ×πk−iQ k h,i (s) .
By Bellman equation,
V †,πk−i h,i (s) = maxµ Dµ×πk−iQ †,πk−i h,i (s) .
Since by induction hypothesis, for any (s,a), Q k h,i (s,a) ≥ Q †,πk−i h,i (s,a). As a result, we also have V k
h,i (s) ≥ V †,πk−i h,i (s), which is exactly inequality (40) for the h-th step. The second inequality can
be proved similarly.

heading: H.1.3 CE VERSION
text: The proof is very similar to the NE version. Specifically, the only part that uses the properties of NE there is Lemma 35. We prove a counterpart here. Lemma 37. With probability 1− p, for any (s,a, h, k, i):
Q k h,i (s,a) ≥ max φ Qφ π k h,i (s,a) , Q k h,i (s,a) ≤ Qπ k h,i (s,a) , (47)
V k h,i (s) ≥ max φ V φ π k h,i (s) , V k h,i (s) ≤ V π k h,i (s) . (48)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we
know at the (H + 1)-th step,V k H+1,i (s) = max φ V φ πk H+1,i (s) = 0. Now, assume the inequality (40) holds for the (h+ 1)-th step, for the h-th step, by definition of the Q functions,
Q k h,i (s,a)−max φ Qφ π k h,i (s,a)
= [ P̂khV k h+1,i ] (s,a)− [ Phmax
φ V φ π
k
h+1,i
] (s,a) + βt
=P̂kh ( V k
h+1,i −max φ V φ π
k
h+1,i ) (s,a)︸ ︷︷ ︸
(A)
+ ( P̂kh − Ph ) max φ V φ π k
h+1,i (s,a)︸ ︷︷ ︸ (B) + βt.
By induction hypothesis, for any s′, ( V k
h+1,i −max φ V φ π
k
h+1,i
) (s′) ≥ 0, and thus (A) ≥ 0. By
uniform concentration, (B) ≤ C √ SH2ι/Nkh (s,a) = βt. Putting everything together we have Q k
h,i (s,a)−max φ Qφ π
k
h,i (s,a) ≥ 0. The second inequality can be proved similarly.
Now assume inequality (47) holds for the h-th step, by definition of value functions and CE,
V k h,i (s) = DπkQ k
h,i (s) = max φ
Dφ πkQ k h,i (s) .
By Bellman equation,
max φ V φ π
k
h,i (s) = max φ Dφ πkmax φ′
Qφ ′ πk h,i (s) .
Since by induction hypothesis, for any (s,a), Q k h,i (s,a) ≥ max φ Qφ π k h,i (s,a). As a result, we also have V k
h,i (s) ≥ max φ V φ π
k
h,i (s), which is exactly inequality (40) for the h-th step. The second
inequality can be proved similarly.

heading: H.2 PROOF OF THEOREM 16
text: In this section, we prove each theorem for the single reward function case, i.e., N = 1. The proof for the case of multiple reward functions (N > 1) simply follows from taking a union bound, that is, replacing the failure probability p by Np.

heading: H.2.1 NE VERSION
text: Let (µk, νk) be an arbitrary Nash-equilibrium policy of M̂k := (P̂k, r̂k), where P̂k and r̂k are our empirical estimate of the transition and the reward at the beginning of the k’th episode in Algorithm 4. Given an arbitrary Nash equilibrium πk of M̂k, we use Q̂kh,i and V̂ kh,i to denote its value functions of the i’th player at the h’th step in M̂k. We prove the following two lemmas, which together imply the conclusion about Nash equilibriums in Theorem 16 as in the proof of Theorem 5.
Lemma 38. With probability 1− p, for any (h, s,a, i, k), we have{ |Q̂kh,i(s,a)−Qπ k h,i(s,a)| ≤ Q̃kh(s,a),
|V̂ kh,i(s)− V π k h,i (s)| ≤ Ṽ kh (s). (49)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know at the (H + 1)-th step,V̂ kH+1,i = V πk H+1,i = Q̂ k H+1,i = Q πk
H+1,i = 0. Now, assume the conclusion holds for the (h+ 1)’th step, for the h’th step, by definition of the Q functions,∣∣∣Q̂kh,i (s,a)−Qπkh,i (s,a)∣∣∣
≤ ∣∣∣[P̂khV̂ kh+1,i] (s,a)− [PhV πkh+1,i] (s,a)∣∣∣+ ∣∣rh(s, a)− r̂kh(s, a)∣∣ ≤ ∣∣∣P̂kh (V̂ kh+1,i − V πkh+1,i) (s,a)∣∣∣︸ ︷︷ ︸
(A)
+ ∣∣∣(P̂kh − Ph)V πkh+1,i (s,a)∣∣∣+ ∣∣rh(s, a)− r̂kh(s, a)∣∣︸ ︷︷ ︸
(B)
By the induction hypothesis, (A) ≤ P̂kh ∣∣∣V̂ kh+1,i − V πkh+1,i∣∣∣ (s,a) ≤ (P̂khṼ kh+1)(s,a). By uniform concentration (e.g., Lemma 12 in Bai & Jin (2020)), (B) ≤ √ SH2ι/Nkh (s,a) = βt. Putting everything together we have∣∣∣Qπkh,i (s,a)− Q̂kh,i (s,a)∣∣∣ ≤ min{(P̂khṼ kh+1)(s,a) + βt, H} = Q̃kh(s,a), which proves the first inequality in (49). The inequality for V functions follows directly by noting that the value functions are computed using the same policy πk.
Lemma 39. With probability 1− p, for any (h, s,a, i, k), we have|Q̂ k h,i(s,a)−Q πk−i,† h,i (s,a)| ≤ Q̃ k h(s,a),
|V̂ kh,i(s)− V πk−i,† h,i (s)| ≤ Ṽ k h (s).
(50)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know at the (H + 1)-th step,V̂ kH+1,i = V πk−i,† H+1,i = Q̂ k H+1,i = Q πk−i,† H+1,i = 0. Now, assume the conclusion holds for the (h+ 1)’th step, for the h’th step, by definition of the Q functions,∣∣∣∣Q̂kh,i (s,a)−Qπk−i,†h,i (s,a)∣∣∣∣ =
∣∣∣∣[P̂khV̂ kh+1,i] (s,a)− [PhV πk−i,†h+1,i ] (s,a)∣∣∣∣+ ∣∣rh(s, a)− r̂kh(s, a)∣∣ ≤ ∣∣∣∣P̂kh(V̂ kh+1,i − V πk−i,†h+1,i) (s,a)∣∣∣∣︸ ︷︷ ︸
(A)
+ ∣∣∣∣(P̂kh − Ph)V πk−i,†h+1,i (s,a)∣∣∣∣+ ∣∣rh(s, a)− r̂kh(s, a)∣∣︸ ︷︷ ︸ (B)
By the induction hypothesis, (A) ≤ P̂kh ∣∣∣∣V̂ kh+1,i − V πk−i,†h+1,i ∣∣∣∣ (s,a) ≤ (P̂khṼ kh+1)(s,a). By uniform concentration, (B) ≤ √ SH2ι/Nkh (s,a) = βt. Putting everything together we have∣∣∣∣Qπk−i,†h,i (s,a)− Q̂kh,i (s,a)∣∣∣∣ ≤ min{(P̂khṼ kh+1)(s,a) + βt, H} = Q̃kh(s,a),
which proves the first inequality in (50). It remains to show the inequality for V functions also hold in h’th step.
Since πk is a Nash-equilibrium policy, we have
V̂ kh,i (s) = max µ Dµ×πk−iQ̂ k h,i (s) .
By Bellman equation,
V πk−i,† h,i (s) = maxµ Dµ×πk−iQ πk−i,† h,i (s) .
Combining the two equations above, and utilizing the bound we just proved for Q functions, we obtain ∣∣∣∣V̂ kh,i (s)− V πk−i,†h,i (s)∣∣∣∣ ≤ ∣∣∣∣maxµ Dµ×πk−iQ̂kh,i (s)−maxµ Dµ×πk−iQπk−i,†h,i (s) ∣∣∣∣ ≤ max
a Q̃kh(s,a) = Ṽ k h (s),
which completes the whole proof.

heading: H.2.2 CCE VERSION
text: The proof is almost the same as that for Nash equilibriums. We will reuse Lemma 38 and prove an analogue of Lemma 39. The conclusion for CCEs will follow directly by combining the two lemmas as in the proof of Theorem 5.
Lemma 40. With probability 1− p, for any (h, s,a, i, k), we haveQ πk−i,† h,i (s,a)− Q̂ k h,i(s,a) ≤ Q̃kh(s,a),
V πk−i,† h,i (s)− V̂ k h,i(s) ≤ Ṽ kh (s).
(51)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know at the (H + 1)-th step,V̂ kH+1,i = V πk−i,† H+1,i = Q̂ k H+1,i = Q πk−i,† H+1,i = 0. Now, assume the
conclusion holds for the (h+ 1)’th step, for the h’th step, by definition of the Q functions,
Q πk−i,† h,i (s,a)− Q̂ k h,i (s,a) ≤ [ PhV πk−i,† h+1,i ] (s,a)− [ P̂khV̂ kh+1,i ] (s,a) + ∣∣rh(s, a)− r̂kh(s, a)∣∣ ≤P̂kh ( V πk−i,† h+1,i − V̂ k h+1,i
) (s,a)︸ ︷︷ ︸
(A)
+ ( Ph − P̂kh ) V πk−i,† h+1,i (s,a) + ∣∣rh(s, a)− r̂kh(s, a)∣∣︸ ︷︷ ︸ (B) .
By the induction hypothesis, (A) ≤ (P̂khṼ kh+1)(s,a). By uniform concentration, (B) ≤ √ SH2ι/Nkh (s,a) = βt. Putting everything together we have
Q πk−i,† h,i (s,a)− Q̂ k h,i (s,a) ≤ min { (P̂khṼ kh+1)(s,a) + βt, H } = Q̃kh(s,a),
which proves the first inequality in (51). It remains to show the inequality for V functions also hold in h’th step.
Since πk is a CCE, we have V̂ kh,i (s) ≥ max
µ Dµ×πk−iQ̂ k h,i (s) .
Observe that V πk−i,† h,i obeys the Bellman optimality equation, so we have
V πk−i,† h,i (s) = maxµ Dµ×πk−iQ πk−i,† h,i (s) .
Combining the two equations above, and utilizing the bound we just proved for Q functions, we obtain
V πk−i,† h,i (s)− V̂ k h,i (s) ≤ max
µ Dµ×πk−iQ πk−i,† h,i (s)−maxµ Dµ×πk−iQ̂ k h,i (s)
≤ max a Q̃kh(s,a) = Ṽ k h (s),
which completes the whole proof.

heading: H.2.3 CE VERSION
text: The proof is almost the same as that for Nash equilibriums. We will reuse Lemma 38 and prove an analogue of Lemma 39. The conclusion for CEs will follow directly by combining the two lemmas as in the proof of Theorem 5. Lemma 41. With probability 1 − p, for any (h, s,a, i, k) and strategy modification φ for player i, we have Q φ πk h,i (s,a)− Q̂ k h,i(s,a) ≤ Q̃kh(s,a),
V φ π k
h,i (s)− V̂ k h,i(s) ≤ Ṽ kh (s).
(52)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know at the (H + 1)-th step,V̂ kH+1,i = V φ πk H+1,i = Q̂ k H+1,i = Q φ πk H+1,i = 0. Now, assume the conclusion holds for the (h + 1)’th step, for the h’th step, following exactly the same argument as Lemma 40, we can show
Qφ π k
h,i (s,a)− Q̂ k h,i (s,a) ≤ min { (P̂khṼ kh+1)(s,a) + βt, H } = Q̃kh(s,a),
which proves the first inequality in (52). It remains to show the inequality for V functions also hold in h’th step.
Since πk is a CE, we have V̂ kh,i (s) = max
φ̃h,s
Dφ̃h,s πkQ̂ k h,i (s) ,
where the maximum is take over all possible injective functions from Ai to itself.
Observe that V φ π k
h,i obeys the Bellman optimality equation, so we have
V φ π k
h,i (s) = max φ̃h,s
Dφ̃h,s πkQ φ πk h,i (s) .
Combining the two equations above, and utilizing the bound we just proved for Q functions, we obtain
V φ π k
h,i (s)− V̂ k h,i (s) = max
φ̃h,s
Dφ̃h,s πkQ φ πk h,i (s)−max
φ̃h,s
Dφ̃h,s πkQ̂ k h,i (s)
≤ max a Q̃kh(s,a) = Ṽ k h (s),
which completes the whole proof.

Review summaries:
This paper studies learning in stochastic games, which are extensions of Markov decision processes (MDPs) from the single-agent setup to the multi-agent one. Here the objective of each learner is to optimize her own reward function. Similarly to the case of MDPs, here one can devise learning algorithms with controlled sample complexity or regret (or both simultaneously) even when reward and transition functions are unknown. 

The authors introduce new algorithms to solve two-players zero-sum Markov games, as well as two-players Markov game in the reward-free setting. The approach is model-based, based on successive episods of planning and counting for updating the model estimate. It involves solving a matrix game at each iteration, looking for a notion of equilibria that is computable in polynomial time (unlike Nash equilibria) An extension to multi-player games is proposed for both reward and reward free setting (in the appendix).