A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
Authors: Qinghua Liu
Tiancheng Yu
Yu Bai
Chi Jin
Venue:  (2021)
Keywords: Reinforcement learning theory
Markov games
model-based RL
task-agnostic RL
multi-agent RL

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 single-agent 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 \emph{Optimistic Nash Value Iteration} (Nash-VI) for two-player zero-sum Markov games that is able to output an $\epsilon$-approximate Nash policy in $\tilde{\mathcal{O}}(H^3SAB/\epsilon^2)$ 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 $\tilde{\mathcal{O}}(H^4S^2AB/\epsilon^2)$, and is the first that matches the information-theoretic lower bound $\Omega(H^3S(A+B)/\epsilon^2)$ 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^3)$, and outputs a single Markov policy while existing sample-efficient 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.

Under review as a conference paper at ICLR 2021
A SHARP ANALYSIS OF MODEL-BASED REINFORCE- MENT LEARNING WITH SELF-PLAY
Anonymous authors Paper under double-blind review
ABSTRACT
Model-based algorithms- algorithms that explore the environment through build- ing and utilizing an estimated model are widely used in reinforcement learning practice and theoretically shown achieve optimal sample efficiency for single- agent 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- agget Markov games. We design an algorithm Optimistic Nash Value Iteration (Nash- VT) for two-player zero-sum Markov games that is able to output an e-approximate Nash policy in 8(H3 S SAB/e ) episodes of game playing, where S' is the number of states, A, B are the number of actions for the two players respectively, and is the horizon length. This significantly improves over the best known model-based guaran- tee of O AB AB/e2) 2), and is the first that matches the information-theorrii lower bound ( S(ASS(A ((A + B))²²) except for a min (A, B} factor. In addition, our guarantee compares favorably against the best known model-free algorithm if min (4, B) = of ) and outputs single Markov policy while existing sample- efficient model-free algorithms output nested mixture of Markov policies that is in general non-Markov and rather inconvenient to store and execute. We further adapt our analysis designing a provably efficient task-agnostic algorithm for zero-sum Markov games, and designing the first line of provably sample-efficient algorithms for multi- mullti-playr general-sun sum Markov games.
INTRODUCTION
This paper is concerned with the problem of multi-agent reinforcement learning (multi-agent RL), in which multiple agents learn to make decisions 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 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 principle underlies some of the earliest single-agent online RL algorithms such as E3 (Kearns& & Singh, 2002) and RMax (Brafman & Tennenholtz, 2002), and is conceptu- ally 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, model- free 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/cquilibrium policies, and play the greedy policies with respect to the estimated value functions. Model-free algorithms have also

---

Under review as a conference paper at ICLR 2021
Table Sample complexity (the required number of episodes) for algorithms find e-approximate Nash equlibrium policies in zero-sum Markov games: VI-explore and VI-UCLB by Bai & Jin (2020), OMVI-SM by Xie (2020), and Nash Q/V-learning by Bai al. (2020). The lower bound was proved by Jin al. (2018); Domingues al. (2020).
Task-
VT- Regret
Algorithm
Sample Complexity
Output Policy
Agnostic
VI-explore
Yes
AB/
VI-ULCB
Yes
A(H²²
Model -based
single Markov policy
OMVI-SM
Yes
A(H
Algorithm
Yes
O(H+SAB/²)
Algorithm
Yes
0(HÁSAB/2)
Model
Nash Q-learning
O(H"SAB/E)
nested mixture of Markov policies
-free
Nash V-learning
((H+S(A+))/C)
Lower Bound
0(1'S(A+
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 recent line of work (Bai & Jin, 2020; Xie et al., 2020; Bai et al., 2020), 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 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 e-approximate Nash equilibrium policy in Ó S2AB/e" episodes of game playing. However, compared with the information- theoreetic lower bound 22 S(A+ ()++)) this rate has suboptimal dependencies on all of H, S, and A, B. In contrast, the current best sample complexity for model-free a algorithms is achieved by Nash V-Learning (Bai et al., 2020), which finds an e-approximate Nash policy (H + B)(+) episodes. Compared with the lower bound, this is tight except for pHly(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-efficien are model- bosee- 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 Markov games. Our contribution is the design of 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 model- based approaches. We summarize our main contributions as follows. A comparison between our and prior results can be found in Table I.
We design new model-based algorithm Optimistic Nash Value Iteration (Nash-VI) that provably finds e-approximate Nash equilibria for Markov games in S AB) episodes of game playing (Section 3). This improves over the best existing model-based algorithm by O(HS) and the first algorithm that matches the sample complexity lower bound except for a Ó(min (A, B}) factor, showing that model-based algorithms Further, unlike ofte-of-thhear model-free algorithms such as Nash V-Learning (Bai et al., 2020), this algorithm achieves in addition a Õ(VT) regret bound, and outputs simple Markov policy (instead of nested mixture of Markov policies returned by Nash V-Learning).
indeed achieve almost optimal sample complexity.
2

---

Under review as a conference paper at ICLR 2021
We design alternative algorithm Optimistic Value Iteration with Zero Reward (VI-Zero) that is able to perform task task-agnostic (reward-free) learning for multiple Markov games sharing the same transition (Section 4). For N > games with the same transition and different (known) rewards, VI-Zero can find c-approximate Nash policy for all games simultaneously in episodes of game playing, which scales logarithmically in the number of games.
log N/22)
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 A; actions per player, we show that an near- optimal policy can be found in Ö(H* S² ]IE[M]] A,/e²) 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 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.
PRELIMINARIES
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 max- imize her own utility. For simplicity, in this section we describe the important special case of two- player 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). Here H is the number of steps in each episode, S is the set of states with S < S. (A, B3) are the sets of actions of the max-player and the min-player respectively with collection of transition matrices, so that IP,, (-|s, a, b) step h, and
|A| S A and [B] S B, P = (Th [[=]) gives the distribution of the next state if action pair (a, is taken at state (rn)Ne[H is a collection of reward functions, where r'A S x A x B + [0, 1] is the deterministic reward function at step h.' 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 81. At each step h E [H]. both players observe state 8h E S, and pick their own actions On E A and by E B simultaneously. Then, both players observe the actions of their opponent, receive reward ry (Sh, an by), and then the environment transitions to the next state sh+1 ~ PA (- an, bn). The episode ends when s 8H+1 is reached.
Policy, value function. A (Markov) policy j of the max- mlx-player is a collection of H functions {uA S + AAtne(M. each mapping from state to a distribution over actions. (Here Au is the probability simplex over action set A.) Similarly, a policy v of the min-player is a collection of H functions (v) S A A probability of taking action a or b for state at step h under Markov policy μ or v respectively.
We use the notation (a(ss)) and vn (b|s) represent the
We use V.t.": S gives the expected cumulative rewards received under policy μ and v. starting from s at step h:
R denote the value function step h under policy μ and v, so that V.l (s)
V.lli (8) == E,, - The (Sk', ( bbr) 8h,
We also define Qh:"" S x A x B + IR to be the Q-value function at step h so that Q (s. a, b) gives the cumulative rewards received under policy μ and v. starting from (s, a, b) at step h:
(s. b) Eu,,
E**..
rhe axe, bw) 8n = s, ag a, by = b
(2)
For simplicity, we define operator Pr, as [PA a, b) = E.-ra(-ss.add Vss) for any value func- tion V. We also use notation [s) := (. ()> (s, a, b) for any action-valus function Q. By definition of value functions, we have the Bellman equation
0 (s,, a, b) = (rn + PA (H.4)) b))
V.l (s) = (D,, x Qh (s)
We 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.
3

---

Under review as a conference paper at ICLR 2021
for all (s, E Axxxx [H], and the (H + 1)th step we have V (s) = 0 for all S.
Best response and Nash equilibrium. For any policy of the max-player μ4, there exists a best response of the min-player, which policy ut (n) satisfying Vi (6) (s) inf, V/ (s) for any (s, h) E S [ We denote V Vau (w), By symmetry, we can also define yu (v) and Vi further known (ef. (Filar & Vrieze, 2012)) that there exist policies n², y² that are optimal against the best responses of the opponents, in the sense that
V = sup, V/t (s),
Vil (s) = inf, V (s): for all (s, h).
We call these optimal strategies (u",v*) the Nash equilibrium of the Markov game, which satisfies the following minimax equation 2:
sup, infy VA V. (s) inf, sup, Via Vi (s).
Intuitively, a Nash equilibrium gives solution which no player has anything to gain by changing only her own policy. We further abbreviate the values of Nash equilibrium Vid .u" and Q ," as V and Qi We refer readers 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 (ū, 2) using the gap between their performance and the performance of the optimal strategy (i.e., Nash equilibrium) when playing against the best responses respectively:
(s1) (()) = (x1) (+)) + [vr(s)) (x1)
Definition (e-approximate Nash equilibrium), A pair of general policies (A, 1) is an e- approximate Nash equilibrium, if vt (s)) v (s1) <.
Definition (Regret). Let (1²², v²) denote the policies deployed by the algorithm in the kmhh episode. After total of K episodes, the regret is defined as
Regret(K) E Cvtttt (7*+))(s))
One goal of reinforcement learning is to design algorithms for Markov games that can find an e-approximate Nash equilibrium using number of episodes that is small in its dependency S, A,A,B. B, H as well as 1/c (PAC sample complexity bound). An alternative goal is to design algo- rithms 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 polynomial-sample PAC algorithm via the standard online-to-batch conversion (see e.g., Jin et al. (2018)).
3
OPTIMISTIC NASH VALUE ITERATION
In this section, we present our main algorithm Optimistic Nash Value Iteration (Nash- VD), and provide its theoretical guarantee.
3.1 ALGORITHM DESCRIPTION
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 IP, and computes new (joint) policy which is "greedy" with respect to the estimated value functions:
'The minimax theorem here is different from the one for matrix games, i.c. max, ming & Av ming max, o² Anh for any matrix A, since here V/)i(s) (s) is in general not bilinear in u.v.
4

---

Under review as a conference paper at ICLR 2021
Line 16- 16-19 (Play the policy and update the model estimate): Executes the policy x, 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 not tight in any of H, S. and A, B dependency, and its computational complexity is PPAD-complete (a com- plexity class conjectured to be computationally hard (Daskalakis, 2013)).
As we elaborate in the following, technical aspects, which allows it to significantly improve the sample complexity over VI-ULCB, and ensures that our algorithm terminates in polynomial time.
Nash-Vi VI algorithm differs from VI-ULCB in few important
Before digging into explanations of techniques, we remark that line 14-15 is only used for computing the output policies. It chooses policy лh to be the policy in the episode with minimum gap (V1 V, (s1). Our final output policies (n4TH, : are simply the marginal policies of TT.. That is, for all hs, E S x [H), Pi (1(s) EBE "h (., blbs), and (-1s) EnEA "h (a, 118).
3.1.1 OVERVIEW OF TECHNIQUES
Auxiliary bonus 7. The major improvement over VI-ULCB (Bai & Jin, 2020) comes from the use of a different style of bonus term y (line 8), in addition to the standard bonus 3 (line 7), in value iteration steps (line 9-10). This is also the main technical contribution of our Nash- VI algorithm. This auxiliary bonus 7 is computed by applying the empirical transition matrix Ps to the gap the next step Va+1- KA+1. This is very different from standard bonus B, 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 Qn and Q₁ 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 B, which needs to be as large as é( /S/t), In contrast, the inclusion of auxiliary bonus y in our algorithm allows much smaller choice for bonus 3-which scales only as ((V1/t)- while still maintaining valid confidence bounds. This technique alone brings down the sample complexity to Ö(H' SAB/ ) removing an entire factor compared to VI-ULCB. Furthermore, the coefficient in is only c/ H for some absolute constant 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, 82):
Hoeffding type: c(v (12ltt/t+ H2
Bernstein type: c(Vo21/t + St/t). (3)
where 82 is the estimated variance, is the logarithmic factors and is absolute constant. The V in line 7 is the empirical variance operator defined V P, 2 (P, v)² for any V E [0, HJS. The design of both bonuses stem from the Hoeffding and Bernstein concentration inequalities. Fur- ther, the Bernstein bonus uses sharper concentration, which saves an H factor in sample complexity compared to the Hoeffding bonus (similar to the single-agent setting (Azar et al., 2017)). This fur- ther reduces the sample complexity to Ö(H which matches the lower bound in all H.S.C factors.
Coarse Correlated Equalibirum (CCE). The prior algorithm VI-ULCB (Bai & Jin, 2020) com- putes the "greedy" policy with respect to the estimated value functions by dircetly 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
We remark that the current policy is stochastic. This is different from the single-agent setting, where the algorithm only seeks to provide upper bound of the value of the optimal policy where the optimal policy is not random. Due to this difference, the techniques of Azar al. (2017) cannot be directly applied here.
5

---

Under review as a conference paper at ICLR 2021
Algorithm Optimistic Nash Value Iteration (Nash-VI)
1: Initialize: for any (s, a, b, h), Qu (s, a) + H, 2, ()) + 0. A+ + H, b) t 0.
2: for episode k = 1,..., K do
3: for step h = H,
1....... ..... do
4: for (s. o. b) E x x B do
5: f (s.
6: if / > then
7:
3 BONUS(I, V (V h+1 + L (/2 b)).
8:
- (c/H)PP/VV h+1 - (s,,))s,
9:
Qn(s,a.b) min((ra P +, (,, max((r) +PhKn4z)(s,a,b) -
10:
11:
for 8 & do
12:
(T(:;1s)) f- CCE(C, (s, , ;.), 2, (s)
13:
(s(s) + (ID (s). if (V - (11) < A then
(s)s) + (n)
A (V (s1) and Tu for step h = I..... H do take action (an, bn) (- 1ss,), observe reward ra and next state 8h+1- add to NA an, bn) and (s On bn. 11
16:
18:
19:
Pa(-Isn, an, an,bh) <- Nn (sh; on bh, b). -)NN // (Sh, abs bn)- Output (f0m,, you) that are the marginal policies of n
20:
to compute the Nash equilibrium for a two-player general-sum matrix game, which is in general cPopllomplete (Daskalakis, 2013).
To overcome this computational challenge, we compute a relaxation of the Nash equilibrium- Coarse Correlated Equalibirum (CCE)-instead, technique first introduced by Xie al. (2020) to address reinforcement learning problems in Markov Games. Formally, for any pair of matrices Q Q E [0, H. AxB. CCE(Q,Q) returns distribution
Axx such that
[a Q(a, 2 max E(a.))==Q((a'
(a Q(a, b) S min Q(a, (*).
Intuitively, in a CCE the players choose their actions a potentially correlated way such that no one benefit from unilateral unconditional deviation. A CCE always exists, since Nash equilibrium 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.
3.2 THEORETICAL GUARANTEES
Now we are ready present the theoretical guarantees for Algorithm 1. We let n² denote the policy computed in line 12 in the th episode, and μ²*, 1/ denote the marginal policy of n² for each player.
Theorem (Nash-V VI with Hoeffding bonus). For any p E (0, 1), letting = log(SABT /p), then with probability least Algorithm I with Hoeffding type bonus (3) (with some absolute 0) achieves:
(Vil.em") - -V (s1) I e, the number of episodes K (H SABI/2 AB /c).
Regret(K) EK ( -vp" ")())))))))))))))))))))) S OWNESABBT ABB).
Theorem 3 provides both a sample complexity bound and regret bound for NI to find an c-approximate Nash equilibrium. For small c < H/(Si), the sample complexity scales as O(H'SAB/²² Similarly, for large T> H3 ABt3, the regret scales as O(VH'SABT) where T = KH is the total number of steps played within K episodes. Theorem is significant in that it

---

Under review as a conference paper at ICLR 2021
improves the sample complexity of the model-based algorithm in Markov games from S to S (and the regret from S to vS). This is achieved by adding the new auxiliary bonus in value iteration steps as explained in Section 3.1. The proof of Theorem 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-V 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 E (0, 1) letting = AATT(BBT)j /p), then with probability least p. Algorithm I with Bernstein type bonus (3) (with some absolute
c > 0) achieves:
(Viti VI" (81) S e, if the number of episodes K 2 S AB?
Regret(K) Ex=I(V ((("()(s)) S OVVISAABT: ABE)).
Compared with the information theorrtic sample complexity lower bound QH + B)r/²² and regret lower bound ([VHHS(( B)T) (Bai & Jin, 2020), when e 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, recently proposed model-free algorithm Nash V-Learning (Bai et al., 2020) achieves sample complexity S(H + B),/²), which has tight (A + B) dependency on A, B. However, our Nash-Vi VI has the following important advantages over Nash V-Learning: 1. Our sample complexity has a bet- ter dependency horizon H: 2. Our algorithm outputs single pair of Markov policies (n4TT, vom) while their algorithm outputs a generic
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 V -regrett (so that the exploration policies can be arbitrarily poor), while our model- based algorithm has the -r-rrgret guarantee. We comment that although both Nash-VI and Nash V- V-Learning have polynomial running time, the later enjoys a better computational complexity because Na requires to solve LPs for computing CCEs in each episode.
4 REWARD-FREE LEARNING
In this section, we modify our model-based algorithm VI for the reward-free exploration setting (Jin et al., 2020b), which is also known the task-agnostic (Zhang et al., 2020b) or reward-agnostic setting. Reward-free fewerd-free learning has two phases: In the exploration phase, the agent first collects a dataset of transitions D = {(Sk,h, ag.h, game M without the guidance of reward information. After the exploration, in the planning phase, for each task E [N], D augmented with stochastic reward information to become D' = [(*,,,, 0g,b, bR 8R, (RR,A) (())))(K)x(())) where TK,A is sampled from an unknown re- ward distribution with expectation equal to r (Sk,,, ag,h, bk.)). Here, we use p to refer to the unknown reward function of the 7t task. The goal is to compute nearly-optime policies for N tasks under M. given the augmented datasets.
(R.)))))) from Markov
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 Four outputted by VI-Zero is close the true transition IP, in the sense that any Nash equilibrium of the (MP P4) (i [N] is also an approximate
7

---

Under review as a conference paper at ICLR 2021
Nash equilibrium of the true underlying Markov game M(P, r"), where f is the empirical estimate of r' computed using D'
Theorem 5 (Sample complexity of VI-Zero). There exists an absolute constant c, for any p E (0, 1], EE (0, H). N E N. if we choose bonus B₁ = c( H/t/tttttt H2/t/) with = and K c(HASABBfe²
S² ABi /e), then with probability least 1- p. the ouiput poou of Algorithm 2 has the following property: for any N fixed reward functions r'....,,", a Nash equilibrium of Markov game M(Touut (*) is also an e-approximate Nash equilibrium of the true Markov game M(P, r²) for all E [N].
Theorem 5 shows that, when is small, VI-Zero only needs O(H*))B/²) samples learn an estimate of the transition Pout, 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 polylogarihhmicaly 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 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 informa- tion, the exploration policies are naturally sub-optimal. The proof of Theorem 5 can be found in Appendix G.I.
Connections with reward-free learning in MDPs. Since MDPs are special cases of Markov games, algorithm VI-Zero directly applies to the single-agent setting, and yields sample com- plexity 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 spe- cially designed to work together, our algorithm allows an arbitrary planning algorithm as long as it computes the Nash equilibrium of 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 as AB instead of B, our next theorem states that unlike the general reward- aware setting, this AB scaling unavoidable in the reward-free frre 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 different hard instance construction.
Theorem 6 (Lower bound for reward-free learning of Markov games). There exists absolute constant e > O such that for any E (0, c), there exists a family of Markov games Mcc) satisfying that: for any reward-free algorithm 2 using K S cH2SABje AB] episodes, there exists Markov game M E Me() such that if we run A on M and oulput policies (fr, D), then with probability at least 1 1/4, we have (Vi.0- v C
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.
MULTI-PLAYER GENERAL-SUM GAMES
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 Multi- VI-Zero (Algorithm 3 and Algorithm 4) that can find (e-approximate) (NASH, CE, CCE) equi- librium for any multi-play player general-sum Markov game in O(H II As/e)) episodes of game playing, where A, is the number of actions for player E (1...., m) (Theorem 15 and Theorem 16). Due to space limit, defer the detailed setups, algorithms and results Appendix C.
8

---

Under review as a conference paper at ICLR 2021
6 CONCLUSION
In this paper, we provided a sharp analysis of model-based algorithms for Markov games. Our new algorithm VI can find an e-approximate Nash equilibrium of zero-sum Markov game in Ö(H SAB/²) 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 algorithmss for task-agnostic game playing, as well as the first line of multi-player general- sum Markov games. There are number of compelling future directions to this work. For example, can we achieve A + 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 ((5)))? We leave these problems as future work.
REFERENCES
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272, 2017.
Yu Bai and Chi Jin, Provable self-play algorithms for competitive reinforcement learning. arXiv preprint XXXv:2002.04017, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. arXiv preprint net::2006.2000) 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Confer- ence on Learning Representations, 2020. URL sttps:://peereee/// net forum?id- SkxpxJBKWS.
Kimmo Berg and Tuomas Sandholm. Exclusion method for finding nash equilibrium in multi- player games. In Proceedings of the 2016 International Conference on Autonomous Agents Multiagent Systems, pp. 1417-1418 2016.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(0ct):213-231, 2002.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5713-5723, 2017. 2017.
Constantinos Daskalakis. On the complexity of approximating nash equilibrium. ACM Transac- tions on Algorithms (TALG), 9(3):23, 2013.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. arXiv preprint
0rXiv:2010003531, 2020.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly poly- nomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1-16. 2013.
Junling Hu and Michael P Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov):1039-1069, 2003.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563-1600 2010.
Zeyu Jia, Lin F Yang. and Mengdi Wang. Feature-based qelearning for two-player stochastic games. arXiv preprint arXiv: 1906.0006900 0066000433, 2019.

---

Under review as a conference paper at ICLR 2021
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably effi- cient? In Advances in Neural Information Processing Systems, pp. 4868 4878, 2018.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. arXiv preprint arXiv:1912.01112. 2019.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. arXiv preprint
2020a.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. arXiv preprint 20Xiv:2002.02794, 2020b.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, -9(2-3):209-233 232, 2002.
Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Linear last-iterate convergence for matrix games and stochastic games. arXiv preprint arXiv:2006.09517 2020.
Michael L Littman. Markov games framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Michael L Littman. Friend-or-foe q-learning in general-sum games. In ICML, volume 1, pp. 322- 328, 2001.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
OpenAl. Openai five. https:
openai..pp......mmm wtt.://cc/ccpaaeaeeee five/, five/,2018. 2018.
Ian Oshand and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv:1608.02733 027322 2016
Ian Oshand, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. arXiv preprint arXiv: 1402.0635, 2014.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. arXiv preprint arXiv:1905.07773. 2019.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin F Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. arXiv preprint arXiv:1908. 1071, 2019.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Julian Schritwieserr, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-3555 2017.
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model- free reinforcement learning. In International Conference on Machine Learning, pp. 881-888, 2006.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforeement learning. Nature. 575(7782):50-335, 2019.
Ruosong Wang, Simon Du Lin F Yang, and Ruslan Salakhutdinov. On reward -eward--ree reinforcement learning with linear function approximation. arXiv preprint arXiv:2006.1 /274 2020.
10

---

Under review as a conference paper at ICLR 2021
Chen-Yu Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems, pp. 4987-4997, 2017, 2017.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. arXiv preprint arXiv:2002.07066, 2020.
Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári. Online learning in markov decision processes with adversarially chosen transition probability distributions. In Advances in neural information processing systems, pp. 2508-2516 2013.
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.07461, 2020a.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. arXiv preprint arXiv:2006.0944 2020b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. arXiv preprint arXiv:2004. 10019, 2020c.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in neural information processing systems, pp. 1583- 1591, 2013.

---

Under review as a conference paper at ICLR 2021
A RELATED WORK
Markoy 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 al. (2020), where the transition matrix and reward are assumed be known, or in the asymptotic setting where the number of data goes to infinity. These results do not directly apply to the non- asymptotic setting where the transition and reward are unknown and only a limited amount of data 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 (gen- erative models) that enable the agent to directly sample transition and reward information for any state-action pair. In this setting, Jia 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 e approximate Nash equilibrium. Wei et al. (2017) studies Markov games under 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 essen- tial. However, both results suffer from highly suboptimal sample complexity. The results of Xie al. (2020) also apply to the linear function approximation setting. More recently, two model-free algorithms-Nash Q-Learning and Nash V-Learning- ity guarantees (Bai et al., 2020). In particular, the Nash V-Jearning algorithm achieves the near- optimal 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.
shown to achieve better sample complex-
We remark that the classical R-max algorithm (Brafman Tennenholtz, 2002) also provides prov- able 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.
Aeresaaia 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 stochastic environment. For the tabular episodic setting with nonstationary dynamics and no simulators, the best sample complexity is (((SSA/e") 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 (Jaksch et al., 2010; Osband & Van Roy, 2016; Jin et al., 2018).
Reward-free and task-agnostic exploration. Jin et al. (2020a) proposes new paradigm of learn- ing 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 policy. The goal is make the output policy near optimal for any given reward func- tion. 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
12

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Optimistic Value Iteration with Zero Reward (VI-Zero)
Require: Bonus 3r.
1: Initialize: for any (s, a, b, h), (,, t- H. H, (x t 0.
2: for episode h = 1,...................... K do
3: for step h = H, H
do
4: for (s, a, b) E S x x B do
5: if 1 0 then
NN,s,, (s,a,
6:
7:
Qn a. min (PA Vn+1) a, 3r, H).
8:
for s E S do
9:
Th (8) +- arg (a.))a Qn(s,
10:
Vi, (s) (Da,, (x)
if (i(ss) < A then
12:
A A (s1) and pout + P.
13:
for step h = L..... H. do
14:
take action (an, bn) ~ (n((- 118)), observe next state 8h-1-
15:
add (s,, an, bn) and Nu On, bus 8h+1)-
Pn(-|on, sh, an, bn) < (8h, an, bay .) -) an, bn).
17:
Output Ioon
learning can also be transferred to reward-free exploration by taking union bound w.r.. different possible reward function. In Table 1, VI-explore (Bai & Jin, 2020) and Algorithm 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 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 al. (2020) follows simialr scheme, but studies reward-fie exploration in linear- parametrized MDPs.
B OPTIMISTIC VALUE ITERATION WITH ZERO REWARD - VI-ZERO
We now describe 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 reward- aware 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 (s, b) maintained in the algorithm no longer an upper bound for any actual value function (as it has no reward), but rather a measure of uncertainty suboptimality that the agent may suffer-if she takes action (a, b) at state and step h, and makes decisions by utilizing the empirical estimate P in the remaining steps (see rigorous version of this statement in Lemma 27). Finally, the empirical transition P the episode that minimizes V (81) 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 th task, let F be the empirical estimate of rd computed using the ith augmented dataset D'. Then we compute the Nash equilibrium of the Markov game M(P, fi) with estimated transition P and reward P'. Since both P and f are known exactly, this is 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).
13

---

Under review as a conference paper at ICLR 2021
C MULTIPLAYER GENERAL-SUM MARKOV GAMES
In this section, we extend both our model-based algorithms (Algorithm and Algorithm 2) to the setting of multiplayer general-sum Markov games, and present corresponding theoretical guarantees.
C.I PROBLEM FORMULATION
A general-sum Markov game (general-sum MG) with players is tuple MG S, 11 P, (r:), where H, denote the length each episode and the state space. Different from the two-player zero-sum setting, we now have different action spaces, where A, is the action space for the jH player and A A. We let a == (a1. 4m) denote the (tuple of) joint actions by all m players. P (ee is collection of transition matrices, so that (- a.) gives the distribution of the next state if actions are taken at state at step h, and r; = {rr,s he is a collection of reward functions for 7th player, so that (s, a) gives the reward received by the 5th player if actions a are taken at state s at step h.
In this section, consider three versions of equlibrium for general-sum MGs: Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilibrium (CCE), all being standard so- lution notions in games (Nisan 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 hand. Below we introduce their definitions.
(Approxinate) Nash equilibrium in general-sum MG. The policy of the 7th player is denoted as Ty = (hh, + AA, ) "e)"" We denote the product policy of all the players as x ==
TT πM and denote the policy of the all the players except the 7th player as π- We define VR, (s) as the expected cumulative reward that will be received by the 1th player if starting at state at step h and all players follow policy т. For any strategy T- there also exists a best response of the gth player, which is a policy ja (T- satisfying V/u1 (x-1),x--1 (8) = sup,, Vh (ss for any (a-1)=t- The Q-functions of the best response can be h) S x [H]. We denote Vita-= hi defined similarly.
Our first objective to find an approximate Nash equilibrium of Markov games.
Definition 7 (e-approximate Nash equilibrium in general-sum MG). A product policy a an e- approximate Nash equilibrium if maxse[m]] (vit.= (1.))s1) S
The above definition requires the suboptimality gap (Vl.-- (T.) to be less than for all player This is consistent with the two-player case (Definition 1) up constant 2, since in the two-player zero-sum setting, we have (s, - (s1) for any product policy (p, v), t.- - (s1) < 2(vit - 1 We can and therefore (V/t_²" - (si) S 2 max4e/21 (Vi similarly define the regret.
Definition 8 NNase-regret in general-sum MG). Let Th denote the (product) policy deployed by the algorithm in the 1tth episode. After a total of K episodes, the regret is defined as
k
t. V=* (s1).
Regret (K)
max [m(m
1,2
(Approximate) CCE in general-sum MG. The coarse correlated equilibrium (CCE) is relaxed version of Nash equilibrium in which consider general correlated policies instead of product policies. Let A = AA x ... x Am denote the joint action space.
Definition 9 (CCE in in general-sum MG). A (correlated) policy π = {m^(s) e AA: (h e
[M] x 8} is CCE if max Vi, ff. (s) (z) for all (s, h) E S [H].
Compared with Nash equilibrium, CEE is not necessarily product policy, that is, we may not have Th. (s) E A x ... x Am.. Similarly, we also define e-approximate CCE and CCE-regret below.
14

---

Under review as a conference paper at ICLR 2021
Definition 10 (e-approximate CCE in general-sum MG). A policy (T)(s) Aa: (h, [H] x S) is an c-approximate CCE if maxqe[m] (Vi, (s1 c.
Definition 11 (CCE-regret in general-sum MG). Let policy x& denote the (correlated) policy de- ployed by the algorithm in the ht episode. After total of K episodes, the regret defined as
K
-t max (V1, (e(m)
VI. (s1).
(Approximate) CE 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 @ = ( (a) E AA (h, 8, a) E [M] x S x A:} for player i is a set of $ x H injective functions from A; to itself. Let Φ; denote the set of all possible strategy modifications for player i.
One can compose strategy modification é with any Markov policy и and obtain new policy ΦoT such that when policy π chooses to play a := (aI...., am) at state and step h, policy & o wwill play (a1....: 0;-1, &h., (a;), 0.+1...., am) instead.
Definition 12 (CE in general-sum MG). A policy x == (s) E AA: (h, E [H] x S} is CE if maX44[m] max h, (8) (s) holds for all (s, h)) E [H].
Similarly, we have an approximate version of CE and CE-regret. Definition 13 (e-approximate CE in Markov games). A policy π == (s)(s) E AA: (h1 [H] x S} is an e-approximate CE max:e[m] maxşeu, (V1,t - (31 S
Definition 14 (CE-regret in multiplayer Markov games), Let product policy x² denote the policy deployed by the algorithm in the 1tth episode. After total of K episodes, the regret defined as
K
RE
Σ
max max ViSe (E(m]
-VT, (81).
Relationship between Nash, CE, and CCE For general-sum MGs, we have [Nash] S {CE} S (CCE), so that they form a nested set of notions of equilibria (Nisan 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., (a) being independent a, Definition 12 will reduce to the definition of CCE policy. In addition, any Nash equilibrium is CE by definition. Finally, since Nash cquilibrium always exists, so does CE and CCE.
C.2 MULTIPLAYER OPTIMISTIC NASH VALUE ITERATION
Here present the Multi-Nash- VI algorithm, which is extension of Algorithm for multi -lati-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 com- pute the Nash equilibrium of 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 sub- routine 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 program- ming. However, the policies found are not guaranteed to be 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 x denote the policy computed in line 11 of Algorithm 3 in the h episode.
Theorem 15 (Multi-Nash- VI). There exists an absolute constant e, for any E (0, 1], let = ABB//B/)p) then with probability at least 1 - p. Algorithm with bonus Br = // and SQUTLIBRIUS being one of of (NASH, CE, CCE) satisfies (repsectively):
15

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Multiplayer Optimistic Nash Value Iteration (Multi-Nash-VD)
1: Initialize: for any (s, a, h, a), (ha + H. Qr (8) + A + H, a)) t
a)
2: for episode k: = 1,..., K do
3: for step h = H,
A1 .,.,, do
4: for (s. a)
Am do
5: t - (s,
6: if f then for player i = 1,2,..., m do
7:
8:
(s, a) + min((ra, + (s)
9:
2, (3,a) + max -
3,,0).
10:
for E E do
11:
T + EQUILLIBRIUM( -) (nn (s, Qn,M(s,))) for player i .,, do
12:
13:
(s,(s) t (Dn, (s): (s,(()) - (Drr 2n,
14:
if [m (V,, 1,5- - -V,, (s)) < then
15:
A maxqe(m] (V1, (s)) and TH
16:
for step h = 1.... do
17:
take action an TT. (-1s)) observe reward ra and next state 8h+1- add to (sa, ax) and N₂ (S), ah. Sh+1).
18:
19:
(a (s) < N₂ (8h, an. 1/Nn((s an). Output x
ou an c-approximate (NASH,CE,CCE), if the number of episodes K S? A))./e).
2
Regret (Nash,, (K) SOW A)T.)).
In the situation where the EQUILIBRIUM subroutine is taken NASH, Theorem 15 provides the sample complexity bound of Multi-Nash- algorithm to find a e-approximate Nash equilibrium and its regret bound. Compared with our carlier result in two-player zero-sum games (Theorem 3), here the sample complexity scales as 52 instead of SH3 This is because the auxiliary bonus and Bernstein concentration technique do not apply here. Furthermore, the sample complexity is proportional to I[ A,, which increases exponentially as the number of players increases.
Runtime of Algorithm We remark that while the Nash guarantee the strongest among the three guarantees presented in Theorem 15, the runtime of Algorithm 3 in the Nash case is not guar- anteed to be polynomial and in the worst case PPAD-hard (due to the hardness the NASH sub- routine). In contrast, the CE and CCE guarantees are weaker, but the corresponding algorithms guaranteed to finish in polynomial time.
C.3 MULTIPLAYER REWARD-FREE LEARNING
We can also generalize VI-Zero to the multiplayer setting and obtain Algorithm 4, Multi VI VI-Zero, which is almost the same VI-Zero except that its exploration bonus B. larger than that of VI- Zero by V factor.
Similar to Theorem 5, we have the following theoretical guarantee claiming that any [NASH,CCE,CE] of the (f) (i [N]) is also an approximate (NASH,CCE.CE) of the true Markov game M(P, where pour is the empirical transition outputted by Algorithm 4 and şi is the empirical estimate of r'.
Theorem 16 Muuti--V-ZZero) There exists an absolute constant c, for any P E (0, 1]. E (0, H). N E N, if we choose bonus 3r = cv StSt with = (og(NSABT/p) and 2 C( At)t/e2), then with probability least 1 p, the output fown of Algorithm 4 has the following property: for any N fixed reward functions pl ..N...NN any (NASH, CCE, CE) of
16

---

using the Under review as a conference paper at ICLR 2021
Algorithm 4 Multiplayer Optimistic Value Iteration with Zero Reward (Multi-VI-Zerr)
1: Initialize: for any (s, h). (s a) - H, + -, (s, +... 0.
2: for episode k 1,.... K do
3: for step h = H. H 1,.... do
4: for (s E Ai
Am do
5: t (s,
6:
if then
7:
Qn (s, t min (Py, ( H)
8:
for s E do
9:
(8) arg ma xm ()(
10:
(s) f- (DA,, (s)
11:
if (s1) < A then
12:
A (s1) and Pour + P. for step h = 1..... do
13:
14:
take action an Tnl. (SA), observe next state 81+1. add to (8 as) and (sh, ah. Sh+1). Pa(-|sa, an) + (sn, as. 1/Na an). Output Pour
15:
16:
17:
Markov game M(Toow ft) is also e-approximate (NASH,CCE,CE) of the true Markov game M(P, r") for all i [N].
The proof of Theorem 16 can be found in Appendix H.2. It is worth mentioning that the empirical Markov game M( P may have multiple (Nash equilibria, that all of them are e-approximate (Nash equilibria, CCBii CCEs, CEs} of the true Markov game. Also, note that the sample complexity here is quadratic in the number of states because exploration bonus B / H2Si/t that is larger than usual by v3 factor.
and Theorem 16 ensures
D BELLMAN EQUATIONS FOR MARKOV GAMES
In this section, we present the Bellman equations for different types of values in Markov games.
Fixed policies. For any pair of Markov policy (n, v), by definition their values in (1) (2), we have the following Bellman equations:
(s, (rh + PA (41 (s,
VIL (s) Ja X Q4 (s)
for all (s, a. h) S Ax
H where (s) for all S.
Best responses. For any Markov policy l of the max-player, by definition, have the following Bellman equations for values of its best response:
( (s) (rx + PAV a,
V inf vEAg
(s) for all (s, b, E S Ax B [H], where (s) =
for all e
Similarly, for any Markov policy of the min-player, also have the following symmetric version of Bellman equations for values of its best response:
Qt"" (rn +
[x) sup (Duxe, ff:") (s). HEAA
for all (8, b, ES A B [H), where Vt.v (s) for all S.
17

---

Under review as a conference paper at ICLR 2021
Nash equilibria. Finally, by definition of Nash equilibria in Markov games, we have the following Bellman optimality equations:
Q8,8, a, b) =rr + Ih (s, Vi = sup inf
= inf sup (D (T)) rEAs μEda
μEdA rEA8
for all (8, a, h) E Ax x [ where V (8) = 0 for all E.
E PROPERTIES OF COARSE CORRELATED EQUILIBRIUM
Recall the definition for CCE in our main paper (4), we restate it here after rescaling. For any pair of matrices P.Q E [0, 1|mxm, the subroutine CCE(P, Q) returns a distribution E Anxm that satisfies:
E ((a.b)~ P(a,, max (a
(a Q(a,b) S min ((a ~x ((a
We make three remarks on CCE. First, a CCE always exists since a Nash equilibrium for a general- sum 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 rewritten as n + m linear constraints on E Anxms which can be efficiently resolved by standard linear programming algorithm. Third, CCE in general-sum games needs not to be Nash equilibrium. However, a CCE in pero-sum games is guaranteed to Nash equalibrium.
Proposition 17. Let CCE(Q, Q). and (p,v) be the marginal distribution over both players' actions induced by æ. Then (n, v) is a Nash equilibrium for payoff matrix Q.
Proof of Proposition 17. Let N be the value of Nash equilibrium for Q. Since π CCE(C, Q), by definition, we have:
(a, Q(a,))=n((a,b) 2 max (e, Q(a", b)) max Q N
E (aa s min [a, Qaa = min E. Ea~a Q(a,b)))"") N
This gives:
max E P ((a,b))
min Bang Q(a, N*
b*
which finishes the proof.
Intuitively, CCE procedure be used in Nash Q-learning for finding an approximate Nash equi- librium, because the values of upper confidence and lower confidence (Q and Q) will be eventually very close, that the preconditions of Proposition 17 becomes approximately satisfied.
F PROOF FOR SECTION 3 OPTIMISTIC NASH VALUE ITERATION
F.1 PROOF OF THEOREM? 3
We denote y Q+, Th n² and v 4 for values and policies at the beginning of the k-th episode. In particular, N7 (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. (5, (,,),,,,,)))) 8') is defined by the token. Using this notation, b).
we can further define the empirical transition by (s = N (1, a, b) = 0, we set (s' [s, a, b) 1/S.
As result, the bonus terms can be written as
1H2 (ss :( CV max
H (xx
(6)
'recall that (1tt ) the marginal distributions of x
18

---

Under review as a conference paper at ICLR 2021
C (s. a. - Ph (o+i)s,,,,))
for some large absolute constant C> 0.
Lemma 18. Let Cr be some large absolute constant. Define event En to be: for all h, b, s' and E [K].
H² max[NN a, b), 13
[1(P%) - a)) sa
min(Pn(s' b), P 8, a, b)fe max [ b),
(PA - Ph)( s,a,b)] sa
(
We have P(E1) 2 pp
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 here.
Consider fixed (x, a, b, h) tuple.
Let's consider the following equivalent random process: (a) before the agent starts, the environment samples ( s(2)..... ..... g( g(K) independently from (- b); (b) during the interaction between the agent and environment, the 7th time the agent reaches (s, a, 6, h). the environment will make the agent transit to s(i), Note that the randomness induced by this interaction procedure is exactly the same 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 this "easy" context. Denote by IP(") (. 8, a, b) the empirical estimate of (- 8, a, b) calculated using (s(1), s(2) ...... s(0). For fixed and s', by applying the Bernstein inequality and its empirical version, we have with probability at least - p/S² ABT,
min 8, 8,a,b), 10(! (s' 1 (,,,))) +
[(P, - 110) (106|ss,,,00) s,a, so
t
Now we can take a union bound over all s, a, b, h, s' and t e [K]. and obtain that with probability at least 1 p, for all s, a, h' and t [K].
min (s s, s,a,bl (l, |s,a, + 41)
[(P )/' ss so
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 least 1
We begin with an auxiliary lemma bounding the lower-order term.
Lemma 19. Suppose event Ea holds, then there exists absolute constant such that: if function g(s) satisfies [gl(s) S (Vi Vk (s)) for all 8, then
(P)) Pr)g(s,a,b))
H² (N,
min min(npp (P h41 a,, ah,
502
H
19

---

Under review as a conference paper at ICLR 2021
Proof. By triangle inequality,
PP Pn (F))g(8, a,
(P) (s') b)lgg((())
Σ (PA - (s'ss,, b)( b)(( - k54))(5)
(s + max (N, h+1 -
0
m as
(8)
Pk (5'1s,
(V - vb Khtnl((t)
H
[ b), 13
PR & h+1
v (s,,),
H
00
max vaxxNN (N a, b),
where (i) by the second incquality in event Ep and (ii) is by AM-GM inequality. This proves the empirical version. Similarly, we can show
H
( - Pn)a(s, a, b)1 s
H
(ax
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 Eo holds. Then for all h, s, a, b and k E [K]. we have
a o (s,a, OK as, > as, (1(()) 2 Vi v/t (s) 2 V/ (s) 2 (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 step. For any state 8:
Vh (s) = D xht 0h+1(s)
2 max D exot (h+)(s)
(9)
#
2 max D axct Qtur(()= = viva (s).
#
Similarly, we can show (s) S /
- (s). Therefore, we have: for all s,
v (s) 2 V/4 (s) 2 (itz(() 2 V 2 k (s).
Now consider an arbitrary triple (s, a, b) in the ht step. We have -//- (s)
min
(PAT) h+1 - Pa Vit** + + a),
(Pivte+ h+1 P. Pa + + (,)
min
(10)
min
(P Fa)(vtet V Vitt)ss,
(P
V
(4)
(B)
+ (8f + (s)
20

---

Under review as a conference paper at ICLR 2021
Invoking Lemma 19 with g = Vi+**
Vi+1
h+1
P ( 4-1
Vi (s,0,6)
S max (xx,
((4) - o By the first inequality in event Ep.
H
H2, [BB) =0] max [iaxx(NK (N b),
Plugging the inequalities above back into (10) and recalling the definition of S and the obtain (s, 2 Q (s,a,b). Similarly, we can show 2% a, b) S Q it (s,,,, O
Finally come to the proof of Theorem 3.
Proof of Theorem 3. Suppose event Eu holds. We first upper bound the regret. By Lemma 20, the regret can upper bounded by
E(vl (5t) vp ((+i) - (2)(
For brevity's sake, define the following notations:
A = (V/ (s7))
== A -(@t (sh an b%
(II)
ct = (T. h+1 Vh (5 a bb) A
Let Fh be the a-field generated by the following random variables:
as (/,r, r.)....em ULis ab by heja U(s
It's easy check t and < are martingale differences with respect to F With slight abuse of notation, use Bk to refer (t att bb) and N to refer (s at (.) in the following proof.
We have
A
-c
C 2%) (sh a/. by))
SCh 2 -2/h Pol (V h+1 V/ 1h+1) (sh at, by.)
(0)
Sch + 2 - -2/ + Pa ( h+1 - kh+n) ) (shi ani b%:
1² PA h+1 ( oh,bhh + max ( N/F. 1}
+ C2
(1))
5 ch + 2.3
Ps (V h+1 1b
vh+1)
(sh an bi)
PPa(V h+1 - (s az. bl:)
H2 max (N/, 1]
+ 2ozC
H
2020
CH2
H
<ch
1
Pn ((1 wh+z) (s) at bh) + 4020
mmxxx max(N max(N 11
H
=st
20ye
ch (1+
20yC'
A 4020 (N
TH²
H²
H
H
(max(Nk.)
max { (NH 11
21

---

Under review as a conference paper at ICLR 2021
where (i) and (ti) follow from Lemma 19.
Define C3 = + 202C and K = + ca/H. H. Recursing this argument for E [H] and summing
over k.
K
K
H
g +0
Mmax(NV/.11 (
12 max (N 11
)
E
h S
k=1
k=
h=1
By Azuma-Hoefidin inequality, with probability at least p.
ΣΣ " s (HHHK. 0 (HHTT
(12)
X - ④ HVHKi) = =O(VHTTI
By pigeon-hobe hole argument,
K
H1
No (8.0,b)
Σ
+ HSAB
Vn
k= 1=
max maxx
s,a.b,k: N (e,0,b)>0
m=
0o VHSABT + HSAB).
K
H
N (x.a.))
Σ
Σ
+ HSAB
max NN
b.0,bkk N (),0,))00
==1
<OSHAABL)
Put everything together. with probability at least other is for equation (12)),
2p (one comes from P(Eo) 2 1 p and the
K
(vi (0/) - ( S +
For the PAC guarantee, recall that we choose क =k" such that argming (v As result,
-i-Ve ktt (81).
(Vi
1 1 O(VH3SSABT.+ H Vir (s1) (V' (s1) K
which concludes the proof.
F.2 PROOF OF THEOREM
We use the same notation as in Appendix F.1 except the form of bonus. Besides, define the empirical variance operator
Vs. b) = Var " (ttla,)) V(s))
and the true (population) variance operator
V, a) = Var ((ll..) (ss)
for any function E S If N (8 a, b) O. we simply set V a.)) = H² regardless of the choice of V.
As result, the bonus terms can be written as
(V (V++1 + 1/2 a) +
H
as) :-
(13)
max(N) b),
(s, a,
for absolute constant C 0.
22

---

Under review as a conference paper at ICLR 2021
Lemma 21. Let oj be some large absolute constant. Define event Ej to be: for all h, a, b, s' and E [K].
V h+1 (s. a, b)c maxx b), max (
He
[[(P) - PA)
min(Pr('' a, b), ( b)bc
(P% - Ps) s,a. Sa
max p N a, 1)
max (s,
S1 m a, b),
[(P - Ph)( -P s,,)),, say
We have P(Fa) 21 - 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 E₁ holds. Then for all h, 8, a, b and ls E [K], we have
@ 2 o (s,a,b) 9 ((s, of (s,
(14)
[i(0)2 ((())v1)* v/"" (s) Vi (()2v1()
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) step and Q-values in the A -tth.
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 that we need to bound (B) more carefully.
First, by the first inequality in event E1.
(v
VAV V (s, b) (s,
H
KB)| 5o
(s a..
By the relation of V-values in the (h 1)th step.
( / V
(V
(P ( (s)
+ V ) 1
13
(15)
<AHP +
(V+
<AHPR (s,,a,,
23

---

Under review as a conference paper at ICLR 2021
which implies
VV h+1 (8, a, m (N (N (s, a, 6), 1}
(VRI(V*+ h+1 + V 1)2] + 4HP 4 h-1 V (itt)l(s,a.b) max (s,
(16)
VHI(T 1+1 1+1 1/21)/22(s,0
4tH (V h+1 ((t,)l(s,
[N (5, 6),
(s, b),
IAG
V h+1 1 (s,,, max (N a, 1)
PR h+1
vh+tl
4H2
+
H
m a, b). 1)
where (i) by AM-GM inequality.
Plugging the above inequalities back into (10) and recalling the definition of 8 and 7% completes the proof.
We need one more lemma to control the error of the empirical variance estimator:
Lemma 23, Suppose event Eg holds. Then for all h 8, a. b and k E [K], we have
VA Vor l(t,lss,,,b V K41 + Vk 1221)
H
<4HP, 1-1 V (,,,)
(
Proof. By Lemma 22, we have (*)) Vi (8) 2 vt()). As result,
VAllT+ h+1 h+ 1/2] VAVT (8, a, b)
V
- I (TV h+1 + Vb h+ 1//4 (A h+1 [3 a, b) - [ + 1)3/4 - b)
(PA (htt1) -P
(P )P
<1 -P. h+1 ) + [P 6+1 ) (V/
+ I(P (IP,, 1 3 1(PA
These terms can be bounded separately by using event Ey:
St V Max(NN((s, a, b), 1)
I(P) -
H PA)( s,a, S O(H2,
IPA (a((vh+))2 (V () (V.. h+1 (s,,,,,,,,,)))
St (),,
(PPt)t.)) (PrLt > (P: P
a, OHH2
((PA (PM V h+1 (s,,,,, (V ((,,,,),,
Combining with H
S 1+
H (...
completes the proof.
Finally come to the proof of Theorem 4.
24

---

Under review as a conference paper at ICLR 2021
Proof of Theorem 4. Suppose event Ej holds. We define A Sh abd ch as in the proof of Theo- rem As before we have
4 Sch + (1+
C3
PA PA h+1 - V (sh ah b)))
H
WILV h+1 + 2 a/ (%) max ( (sh ag. b/,),11 1}
H max ( off b%).
(17)
+ 4
By Lemma 23,
W h+1 + (h+t)/2[(s,, a) max max(N)(s b}
V a. + (s b),
HVP h+1 (8, b)
H2VS
max (s,
max aM
WAVE h+ (8, b) + (s,
PA A+1 Khnn (s,
H² max (s, b),
Sa
H
(18)
where e₁ is some absolute constant. Define es 402c + C3 and = cs/ H. Plugging (18) back into (17), we have
A Sn + KER + ch
N V (ot az U/) (s ag b%)
H
(19)
+
( a ())
N (5 a 17)
Recursing this argument
for h E [H] and summing over
K
K
K h b-1 + n g
k==
V. Va h+1 (0), ah bR) max m 1}
H² max m 1)
+ +
+
max No
1}
The remaining steps are the same as that in the proof of Theorem 3 except that we need bound the sum of variance term.
By Cauchy-Schward
K
"
V VA (s) a b
K
H
K
"
vn V (s)
of
max 13
h+1
m (5f of bt),
k=1
A=ıÆ=1
k=
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
p. we have
K H
Vn Vn (o of ( SHTT
Putting all relations together, we obtain that with probability at least - 2p (one p comes from P(E,) 2 1- p and the other comes from the inequality for bounding the variance term).
Regret (oeett(K= E(vli*
s O(V H AB:?).
Rescaling p completes the proof.
25

---

Under review as a conference paper at ICLR 2021
G
PROOF FOR SECTION 4 REWARD-FREE LEARNING
G.1 PROOF OF THEOREM 5
In this section, we prove Theorem for the single reward function case, i.e., The proof for multiple reward functions (N > 1) simply follows from taking union bound, that is, replacing the failure probability p by Np.
where T& and f* are our empirical estimate of the transition and the reward at the beginning of the k'th episode in Algorithm 2, respectively. We use 2 (s, a, b) to denote the number we have visited the state-action tuple (s. a, b) the h-th step before the k'th episode. And the bonus used in the k'th episode can be written as
Let (f**, ) be an arbitrary Nash-equilibrium policy of M = (Ps,
Ph), -P*t,ptt
(h(s, = -y
(s. (
H2,
H
(20)
mxx(Ng(s...,),1)))
where L Log(SABT/p)) and some large absolute constant.
We use Th and k to denote the empirical optimal value functions of M as following.
(s, a, b) V (s. (s, (s) = max D Q
(21)
Since (n* 2 is a Nash Nash- equilibrium policy of M we also have 17) x x
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 here.
Lemma 24. Let X, Z AA and Da be the d-dimensional simplex. Suppose X Y S Z,
where the inequality is entry-wise. Then
max min p X T PEAA
max min Yv S max Zij. MEA WEAB
(22)
Lemma 25. Let en be some large absolute constant such that of for all h, b, and k E [K].
S C. Define event Ey to be:
I[(P -
C1
1
10
max (s,
10th - ()),
C1
H²,
(23)
10
max (s, a, b),
|(Ph PA) [s,,,b]l
C1
(V
Py (s s, a, b)e
10
[Mmax(M
max(NN/ a, b),
We have P(E)) >
Proof. The proof is standard and folklore: apply standard concentration inequalities and then take union bound. For completeness, we provide the proof of the third one here.
Consider fixed (s, a, b, h) tuple.
Let's consider the following equivalent random process: (a) before the agent starts, the environment samples {s(1), (() . { independently from (- s, a, b): (b) during the interaction between the agent and environment, the ąth time the agent reaches (s, a, b, h), the environment will make the agent transit (()) 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 in the original problem. Therefore, it suffices prove the target concentration inequality in
26

---

Under review as a conference paper at ICLR 2021
this "easy' context. Denote by h 8, a, the empirical estimate of Px 8, a, b) calculated s(2), using { ......
,..., s(t)). For fixed and s', by the empirical Bernstein inequality, we have with probability at least 1 - p/S2ABT.
( 1 s Is,a, D)e
[(P, - ) (s, b,l.
+
t
Now we can take a union bound over all s, a, b, h, s' and & E [K], and obtain that with probability at least 1 p, for all 8, a, b, h and & [K].
( s, b)c + :
(PP, - PP 8, b)1 so
b)l
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 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 Ej (defined Lemma 25) holds. Then for all h, s, a, and [K], we have,
@h (R( 1 Qi a, - (s, a.
(24)
((())-((0)) (o).
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 h'th step.
Proof.
( (s,s, b)
S min {|(P - PA)V 10F (s) P (P a) H
min (sh(s.a,b) + (s,
(s, b), (50 @h,
(25)
where (i) follows from the induction hypothesis and event Er, and (ii) follows from the definition of Q By Lemma 24, we immediately obtain (s) (s) S (s).
Now, we are ready to establish the key lemma our analysis using Lemma 26.
Lemma 27. Suppose event Ej (defined Lemma 25) holds. Then for all h, s, a, and [K], we have
@h(s, b) 2t"²² (s, b) S an (s, (s) Viee (s)l an ()),,,)
(26)
and
1h a, b, - "s, b) S an (s,
(27)
[it((s) v/*,((s) S on (x),
where 0:#4 = 0 and or = [(1 + # Jant + + < 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 the conclusion holds for
27

---

Under review as a conference paper at ICLR 2021
(H + 1)'th step with a#+1 = 0. Now, assume the conclusion holds for (h + 1)'th step. For h'th step,
(B, -Q% (s, b]l
|I(0P) [I((P) -P h+1 a,, 1P2 (1
min
+ 1(7 rs) 6)1 (P V 11
(28)
H
min
|I(P)) - PN)( Vitt)](s,,, + (s.
+ ( 1+1 V/4 als b)].
(7h)
where the second inequality follows from the definition of event E₁.
We can control the term (7i) by combining Lemma 26 and the induction hypothesis to bound Ivt"** V I. and then applying the third inequality event E₁:
(Ti) S [ s,a, - (s s,a, b)]1 V
(s' s, - (s s.
b)] as
( ( + 1 - Vi
(29)
Σ [ 8, (8,, - Px 8, a, (.a,b)]((nn] + +1)
(ah+1 - 1) (P h+1) (s,,0,))
can + 1)H2St
H
[ a, b),
The term (T2) is bounded by directly applying the induction hypothesis
[[P V44 (s, a, b) < anti V b).
V
(30)
Plugging (29) and (30) into (28), we obtain
@h1 Qf: (s,a,) b),a,6)
1 <min { (1+ Jon+1+ H
H2b
I 1) +a1
a,)
ca(ant1 + 1)H²St
(31)
max(N) (8, a,a),,, (,b)),1)
(1+ Jant1+ + H
T h 1 (s, (
min
1 (1 H Jont1 + H
) (s,
where (i) follows from the definition of 8%, and (ii) follows from the definition of Ø5 Therefore, by (31), choosing as = [(1 + ))0++1 + #1 suffices for the purpose of induction.
Now, let's prove the inequality for V functions.
100 Vi. (s))
( max
(D (+) max (ID ue Qi )s)]
HEAA
HEA
(32)
(#2)
aap Q (s, a.b) b)] O.h a (s).
max a,b
where (i) follows from the definition of 1/ and viat and (ii) uses (31) and Lemma 24.
n
28

---

Under review as a conference paper at ICLR 2021
Theorem 28 (Guarantee for UCB-V VI from Azar al. (2017)). For any p (0, 1]. choose the exploration bonus B Algrothm 2 as (20). Then, with probability at least 1 p.
K
& SOVVHAAK + A13)
Proof of Theorem 5. Recall that out arg min (s). By Lemma 27 and Theorem 28, with probability at least 1 2p.
vtee (s) 1/2 (s) - <s( - (nn
(s)-Vm
1i (s) V/ (((
H-SAL
H AI2
(33)
<8V= - (s) <0lV
K
K
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 value iteration algorithm for MDPs that the maximum operator is replaced by the minimax operator in Line 7. We remark that the Nash equilibrium for two-player zero-sum game can be computed in polynomial time.
Algorithm Vanilla Nash Value Iteration
1: Input: model M (P,
2: Initialize: for all (s, a, b). (s+1(s,a,b) 0.
3: for step h H, 1,, do
4: for (s,a,, S x A B do
5:
a,) < [P V V an)
6: s do
7: (pn(: 8), (n(: 8)) <- NASH-TEROSS
8:
(s(s) + pn(: s) Qn.s.
9:
Output (A, D) + [.ān(. (s).mm)) (-))((((()))))))))) (N))
By recalling the definition of best responses in Appendix D, one directly see that the output policy (fi, D) is Nash equilibrium for M.
G.3 PROOF OF THBOREM 6
In this section, we first prove ((AB/c2) lower bound for reward-free matrix games, i.e., S И = 1, and then generalize it to ((SABI))/2) for the Markov games setting.
G.3.1 REWARD-FRES MATRIX GAMES
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:
1 M)() = { M M BAB with Mas = 2 + (1 - = (a*, E [A] x
[
(34)
where in matrix game M, the reward sampled from Bernoulli(MMa) if the max max-player picks the a'th row and the min-player picks the h'th column.
29

---

Under review as a conference paper at ICLR 2021
Min-player
action
1
b+
b
b
+
B
1
+
Max-player
a
+
+
(35)
a*
+
...
...
a
+
1
+
+
+
A
Above. visualize the hard instance by using + and to represent 1/2++c and 1/2-c, respectively. is direct to see that the optimal policy for the max-player is always picking the a" row and the optimal policy for the min-player is always picking the b' 'th column. If the max-player picks the ah'th row with probability smaller than 2/3, it is at least e/10 10 suboptimal.
Lemma 29. For any fixed matrix game M from Mi() and N E N, if an algorithm A can output a policy that is at most e/10 suboptimal with probability least p using most N samples, then there exists an algorithum A that can identify the best row in M 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 out- putted policy the guess for the best row. By simple calculation, can show A will output the best row M 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 algoritlum A using most N = AB/((00))) samples, there exists matrix game M in Mc() such that when running A on M, it will output a policy that is at least e/10 suboptimal for the max-player with probability at least 1/4,
suffices to prove the following claim:
Claim 31. for any algorithm À using at most N = AB/(10 samples, there exists matrix game M in M)(e such that when running A on M, it will fail identify the optimal row with probability at least 1/4.
Proof of Claim 31. WLOG, we assume Á is deterministic. Since this the reward-free setting, being deterministic means that algorithm Á will always pull each arm (a, b) for some fixed n(a, b) times and then output guess for a* which is function of the reward revealed.
Denote by L the reward revealed after algorithm Å's pulling. Denote by P. the probability induced by picking M uniformly at random from M){ and running Á on M. Denote by Pa,, the probability induced by running Á on M, whose indices of the special row and the special column are a and b, respectively. Denote by Po,s the probability induced by running A on M, whose thth column all 1/2 e and other columns are all 1/2 + e. We want to mention that the M we use to define Po.6 does not belong to Mi(e).
30

---

Under review as a conference paper at ICLR 2021
We have
P. (A(L)
#a)}
1
Σ (A(L(A() a)
Σ
|PP.,b -o,
AB
AB
1
2
2KL 0,6 P.bD)
A
AB
1
Σ
2n(a, b)[((
E) log
+
(
E)
log
2 +
(36)
A
AB
+
1
2
2
1
10
Σ
Vn((ab)e2
A
AB
a.6
1
100N
21
A
AB
Choosing N = AB/(10 concludes the proof.
G.3.2 REWARD-FREE MARKOV GAMES
Now let's generalize the (ABB/2) lower bound to 6(SABH² for reward-free Markov games.
We define the following family of MDPs:
3(c) (J(a", b*): (a*, (b) [A]#xS [B]
(37)
where MDP [a" b*) is defined as below:
States and actions: J(a" b*) is Emite-horizon MDP with S + states of length H + 1. There is fixed initial state So in the first step, S states {si....,ss s for the remaining steps. The two players have A and actions, respectively.
Rewards: there no reward in the first step. For the remaining steps (2...., H if the agent takes action (a, b) at state in the ht step, it will receive binary reward sampled from
Bernoulli (5 (1 ( 1aa + a 1, 1)11 - E
Transitions: Regardless of the current state, actions and index of steps, the agent will always transit to one of 81,...,88 uniformly at random.
direct to see that J(a", b*) is a collection of SH independent matrix games from Mc / H). Therefore, the optimal policy for the player is to always pick action a whenever it reaches state s; in the th step (h 2 2). other words, a7 is the unique optimal action for the step-state pair (h, i).
At high level, in order to find e-optimal policy for the above Markov game, need identify at least half the entries of a*, Therefore, the number of episodes should be at least
AB
S 2
ABSH2
θ
(c/H)2
2
Below we provide formal proof of this argument, which is almost the same 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 [a" bb)) from 3(c) and N E N, an algorithm A can output a policy that is at most e/ e/103 suboptimal with probability at least p using at most N samples, then there exists an algorithm A that can correctly identify at least SH |SH/500] entries of a" with probability at least p using most N samples.
31

---

Under review as a conference paper at ICLR 2021
Proof. Denote by the output policy for the max player. Denote by Z the collection of (h, i)'s in [H] x [S] such that Th-1 ( 8;) S 2/3.
Observe that each time the max player picks a suboptimal action, will incur an 2 suboptimality in expectation. As result, if is most -ubbptiilll must have
Σ (N.))
(1- mi-ma+i
8:))
2x
e
S
H
103
which implies |Z| S SH/500, that is, for at most [SH (SH/500 |500 different i's, a(a 8;) S 2/3. Therefore, we can simply pick argmax, Ta+1(a si) as the guess for ax Since policy ạ is at most e/10² suboptimal with probability at least p, we can correctly identify the optimal actions for least SH SH /500] 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 algorithm A interacting with the environment for most K = ABSHH/((0* episodes, there exists J E 3(E) such that when running A on J. will output a policy that is at least c/10² suboptimal for the max-player with probability at least 1/4,
it suffices to prove the following claim:
Claim 34. for any algorithm À interacting with the environment for at most ABSH (10+2) episodes, there exists J E -e() such that when running Å on J. it will fail to identify the optimal actions for at least /500 1 different (s, h) pairs with probability least 1/4.
Proof of Claim 34. Denote by P. (EE,) the probability (expectation) induced by picking Jaa b*) uniformly at random from 3(e and running on J. Denote by Yowrong the number of (s, ht) pairs for which Á fails to identify the optimal actions. Denote by error,, the indicator function of the event that Á fails to identify the optimal action for (h 1,
We prove by contradiction. Suppose for any J(e), A can identify the optimal actions for at least SH [SH/500] different (s, h) pairs with probability larger than 3/4. Then we have
3 X
SH
101SH
E. [wwrogg] < SH
500
400
Since [(n,))((P))(5))) T. [errora, E. [wrroug], there must exists (M, E [H) [S] such that
E. [errorw I 101/400. However, in the following, show that for every (h [M] x [S]. Á fails to identify the optimal action for the step-state pair (h (1+1) 1) with probability at least 1/3, which directly implies E. [crrora,, 1/3 for all (h, [H] x [S]. As result, we obtain contraction
and Claim 34 holds.
Now, let us prove that for every (h, E [H] x (S), E. (errorn,)] 2 1/6. WLOG, assume Á is episodes. In the following, we consider
deterministic and it runs for exactly K ABSH² a fixed (h', (') pair. For technical reason, we define MDP J J_(w.nn(a" (a", b²) as below:
((10 ABSH"/(10*e))
States, actions and transitions: same as J(a",
Rewards: there is no reward in the first step. For the remaining steps h E (2...., .....,H HHH1 11, if the agent takes action (a, b) at state s, in the th step such that (h 1, # (h',)'), will receive binary reward sampled from
Bernoulli (1 _ + (1-2-- (1-2- 1(a + 1 = by 1 4)
H
otherwise it will receive binary reward sampled from
Bernoulli ( + (1 (1-2- 2-b b 1 )
32

---

Under review as a conference paper at ICLR 2021
Intuitively, J- (1- ((a,""")) b") is the same J(a", b*) except that for the max player, all its actions at state sy in the 1/ step are equivalent. In other words, J-(N,ss (a", , b*) is independent of ,
To proceed, we need define the following notations: denote by n( b) the number of times A picks action b) at state 8y in the (h' + 11th step; denote by P(. [ (TE(- T(a",""" the probability (expectation) induced by running algorithm A on J(a", b"); similarly, we define P(. J-(N.Pr b))) (EI- J=( ( bD));; also recall that we denote by P.. (E,) the probability (expectation) induced by picking T(a", b*) uniformly at random from I(c) 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(I. the guess of Á for aic,y based on L.
First, that for any (a,b) E [A] [B], E[n(s, a) | 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 (raaa""")) are the same. For simplicity of notation, we denote this expectation by mi(a, b). Note that Ea,5 mla b) K/S because the agent always
reach state sy in the (h' + 1)th step with probability 1/5 regardless of the actions taken.
We have
P. (A(L) # a32
Σ
((((L) + awe [J(aa,b')
(AB)SH
(a (a*,b")E[AjS" x[B]S"
Σ
P(((L) + ahe IJ- bb))
(AB)SH
(an EEA]SH S [MasH
- (P = 1 P(L
P(L = ([(L==)((a',b))))
1
Σ
(AB)sH
(a bE) x (B]SH
||[[L = I I J-(ween(a"
PLL ([(aa,b")))
2
1
1
1
Σ (a+ (a*.b")e JEIA x BBBsS
(AB)SH
(PLL (J(r.e)(a*,bb)) PL = [((aa, b*)))
(38)
1
=1-
A
(AB)SH
(a D SH x(B3SH
2m bie 11
log
2 1f
1
log
2
+
17
2
+
H
2
H
2
H
=1
1
Σ
A
AB
(EAA)((B
1
1
1 +
2m(aa bh w
log
11
log
2 2
2
+ 1
2
H
1
10
22
2 1
Σ
m(a, b)
A
AB
H²
0,b
1
10c
m(a,b) b) =1 1
2
>
1--
AB
A
ABH
A
SABH2
a.b
Plugging in K SABH² (10 completes the proof.
33

---

Under review as a conference paper at ICLR 2021
H PROOF FOR APPENDIX C MULTI-PLAYER GENERAL-SUM MARKOV GAMES
H.1 PROOF OF THEOREM 15
HI1.1 NE VERSION
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, k,)):
@ (s, a) 2 Q.. 1, (s,a), 2h (s, S Qh (s,a),
(39)
V ha
(6), Vh (8) S Vi (s).
(40)
Proof. For each fixed k we prove this by induction from = H + 1 to h 1. For base case, we know at the (H + 1)-th step.VA=1 (s) = #ti (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,
Vis
The (8, a) -h (s. = |PVVhtas (s
PA v.
(s, + Be
A+11i
-PA
(
v n+1,
(s, a)
+
(1%
[6k Ph)
V (s, a) + B.
(1)
(B)
By induction hypothesis, for any s', (Vh+Li
(v
vitunt (5') 2 O. and thus (A) 2 0. By uniform
concentration (e.g., Lemma 12 in Bai & Jin (2020)), (B) I C CHSPP/NK a) = 3,. Putting
everything together we have Qh,s (5, a) 1. (s.a) 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 equi- librium,
vh. (s) D2,+ Qh. (s) maxiD uxak Th. (s).
By Bellman equation,
I hd
(s) = maxD uxnt Q (s).
Since by induction hypothesis, for any (s, a), Th (s, 2 o (s, a). As result, we also have v* h.s (s) > yto (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
Vyta vis (sh) S max (vi, - kt.) (sh)
max
notice the following propogation:
@Qh. (s) *+ = (4+n,)(s.a))
(s.
(41)
Dr,, (et. (x)))())
34

---

Under review as a conference paper at ICLR 2021
We can define O% and V recursively by V and
(x( - V4 (s,, 23 a))
(42)
(b) [xx, (Dr, (+).
Then we can prove inductively that for any k, h, and a we have
maax(Q" - 0 h.s (s, a) s (s)s,)), max V h, (s) (s).
(43)
Thus only need to bound
Σ K
(s). Define the shorthand notation
k=1
s = (5 a
A = (sh),
(44)
S Dz (sh) (sh a
ah) cx = PA a/))) A
We can check 5% and 5 martingale difference sequences. As result,
4 =D= 0h (s%)
c + @ (s att)
= ch 2 + P Tk
h+1 (s ah))
sch + 33 +P V/ (5h a
=ch + 33 + c A A+1
Recursing this argument for h E [f]] and taking the sum,
M 13T
(ch + 38 + + 0o
S
II A
i=1
H.1.2 CCE VERSION
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 for any h,
(s. a) 2 cliT (s.
s Q (s,a),
(45)
vh. (s) 2 v hi (8), Vh, (8) S Vili (s).
(46)
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, we know the (H 1)-th step. V...V/ (s)
y, #+ (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,
@he (8) a) 1. (s,a)=
p ht1.s
(8,
v Pa hti,i
(s, a) + 3
P
(
viti*t h4ii
(8, (8) a)
+
[ Pr
h+1. (s, a) + Br.
(A)
(B)
35

---

Under review as a conference paper at ICLR 2021
By induction hypothesis, for any 8', (v h+1,1
vtx= 1,115
(5') 2 O, and thus (A) 2 0. By uniform
concentration, (B) S C (H) = = Br. Putting everything together we have Qh, (8, a)
Q (s, 0. The second inequality be proved similarly.
Now assume inequality (45) holds for the h-th step, by definition of value functions and CCE,
Vh. (s) 13 Dh.s (s) = maxl px** Qn, (s).
By Bellman equation,
yta (8) = maxD uxn",
- (8).
Since by induction hypothesis, for any (8, a). Th, (8, 2 Q (s) As result, we also have VK. h. (s) 2 yi (s). which is exactly inequality (40) for the h-th step. The second inequality can be proved similarly.
H.1.3 CE VERSION
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 for any h,k,))
@he (8, 2 max (s, 2 (s, S Qhi (s,
(47)
v hee (s) 2 max h2s (s), Vha (8) I Vn (8).
(48)
Proof. For each fixed k we prove this by induction from H + 1 to h 1. For base case, we know the (H + 1)-th step,
V H+1, a (s) = max maxVeor*
bor*
H+1, (8) Now, assume the inequality (40)
holds for the (h 1)-th step, for the h-th step, by definition of the Q functions,
Qh, (s, a) max (s)
= -[BAT + (s, -
(s, a) + 33
h+1,
=PA V - maxV h+1,1 (8)
+
S Ph.
max maxi Voor
h+1, (8, + B.
(A)
(B)
By induction hypothesis, for any 8, (ViTLe max max ydox" h+1,i
(8') 2 0, and thus (A) 2 0. By
uniform concentration, (B) C (HHP Br. Putting everything together have Qh (s, a) maxQuen don (s, > 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 n, (8) D2 Qh (8) max dor 2h (8).
By Bellman equation,
max doot h, (8)
maxiD por max on (s).
36

---

Under review as a conference paper at ICLR 2021
Since by induction hypothesis, for any (8, a). Th (s, a) max (8, a). As a result, we also have V (s) maxVit inequality can be proved similarly.
dox (s), which is exactly inequality (40) for the h-th step. The second
@
L
H.2 PROOF OF THEOREM 16
In this section, 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 by Np.
H.2.1 NE VERSION
Let (f**, ) be an arbitrary Nash-equilibrium policy of M == -(3t, fh)), where T and fK are our empirical estimate of the transition and the reward at the beginning of the k'th episode in Algorithm Given an arbitrary Nash equilibrium x² of M we use @t,,, and V to denote its value functions of the i'th player at the h thth step in M
We prove the following two lemmas, which together imply the conclusion about Nash equilibriums in Theorem 16 in the proof of Theorem
Lemma 38. With probability
p. for any (h, 8, a, i, k), we have
@ a) Qi, a)l S as,,,,
(49)
(1Vt, (s) - (s).
Proof. For each fixed k, we prove this by induction from h = H + 1 to h = 1. For base case, know the (HI + 1)-th step, V/ & V Qi+1, Q7+1. 0. Now, assume the conclusion holds for the (h + 1)'th 'hth step, for the h'th step. by definition of the Q functions,
Th. (s, aa-a)-a - Qi.s (s.a)
P h ] (s) - PP vx
(s, a)
+ - -f)(s))) [((s,)
h+
PA (Vi+T, -V a)
Ppt Pn))
v (s, (s) + - - (s.
+
(A)
(B)
By the induction hypothesis,
(A) S Ph DE P
vita./ (s, s (s..))
By uniform concentration (e.g., Lemma 12 in Bai & Jin (2020)), (B) < SHH2//N(sss = Br. Putting everything together we have
@ (s, - @h, (s) I min (PA (s, a) + B, H (5 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 =*
Lemma 39. With probability 1 - p. for any (h, 8, a, i, k). we have
12, - Q - (s, a)l s @t.s.
(50)
(1/ V (s) - V (s).
37

---

Under review as a conference paper at ICLR 2021
Proof. For each fixed k, prove this by induction from h H + to h 1. For base case, know the (H + 1)-th step, V v conclusion holds for the (/ + 1) step, for the h step. by definition of the Q functions,
#H114 Qi+,, @u+1.i 0. Now, assume the
2hat (s, a)
:n (s,aa
Ph -
1 (8,
(8, a) + (ra(s, - (s,
1,2
Pa (Vita.. - p
[Pt - -Ph) V (s, () + (8, (s
htlie
(0, a)
+
(A)
(B)
By the induction hypothesis,
h+1, - m
(A) s Ph
(s, - (P) (s).
By uniform concentration, (B) 5 (SHPI/NN(saa)) B.. Putting everything together we have
@ntt (s,a) (s,a)
0h (s, a) s min (P. (P. + Br, B. = (s,
which proves the first inequality in (50). It remains to show the inequality for V functions also hold in h'th step.
Since x² is Nash-equilibrium policy, we have
4 R. (8) maxID ux* @h. (8)
By Bellman equation,
x h,
(s) = maxD uxan his (s).
Combining the two equations above, and utilizing the bound we just proved for Q functions, obtain
Vi, (s) - Vind
(8)
< maxlD
uxn# axnx Qi (8) maxxa 11
uxntt ah (s)
11
< max Q (s, a) V/ (s).
which completes the whole proof.
H.2.2 CCE VERSION
The proof is almost the same that for Nash equilibriums. We will reuse Lemma 38 and prove analogue of Lemma 39, The conclusion for CCEs will follow directly by combining the two lemmas in the proof of Theorem 5.
Lemma 40. With probability 1 p. for any (h, 8, a, k)), we have
Q (8, - (8, a) s (x)
(51)
vxtua(s) (s) V (s) < (s).
h,
Proof. For each fixed k. prove this by induction from h H + 1 to h 1. For base case, know the (H + 1)-th step, V* y gfft VHti, Q Q4
#+1,
Qutii 0. Now, assume the
38

---

-mxx) Under review as a conference paper at ICLR 2021
conclusion holds for the (h + 1) th step, for the h'th step. by definition of the Q functions,
m-rt (s,
Qh, (s, a)
Ph
V
h+1,
(8,a)
D P h+1,3
(s, + a)) - (
Virt
h+1i
Vh
1+11$
(x) +
Ph - 1p)
Vhti (8, (ra(s, (+)
(4)
(B)
By the induction hypothesis, (A) - (P), vk
h+1 (s)
By uniform concentration, (B) S /HH (s, 3r. Putting everything together we have
T (s, - Qh (8, a) < min (P + Br, } 2% (s)
which proves the first incquality in (51). It remains to show the inequality for V functions also hold in h' th step.
Since T is CCE, we have
V h,i
(s) 2 maxl ux* Di. (s)
Observe that = obeys the Bellman optimality equation, have
v
uxmt Qh i. (s).
h
P
Combining the two equations above, and utilizing the bound we just proved for Q functions, we obtain
Vitt (s) hit (s) I maxD uxr 2hi (s) -mxDD ux* Qh. (s)
P
max @h a) (s),
which completes the whole proof.
H.2.3 CE VERSION
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 P. for any (h, 8, a, i) and strategy modification & for player we have
Quoo (s, - (h, a) s a))
(52)
Vdox* (s) Vh, < (s).
Proof. For each fixed i we prove this by induction from = H + to h = 1. For base case, V& #+1,5 vdox" Q Q 0. Now, assume the conclusion holds for the (h + 1) step, for the h' h'th step, following exactly the same argument as Lemma 40, we can show
know the (H + 1)-th step,
Q (8, a)
Q (s, a) < min (P) a) + H (8,
which proves the first inequality in (52). It remains to show the inequality for V functions also hold in h' th step.
39

---

Under review as a conference paper at ICLR 2021
Since T" is CE, have
max (8)
on owr Ph (8),
b,
$a..
where the maximum is take over all possible injective functions from A; to itself.
Observe that ydoo" h,s
obeys the Bellman optimality equation, so we have
Vdor*
maxlD
on on Qui (s).
h,i
Tb.a
Combining the two equations above, and utilizing the bound we just proved for Q functions, we obtain
(8)
(8) = maxiD 6n,0
(8)
-maxll
di. ox Dh. (8)
h,z
on,-
S max 0% (8, a) (b),
which completes the whole proof.
40


Reviews:
[{"review_id": "yrLTFRF_ZF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-Summary \nThe authors consider self-play in tabular zero-sum episodic Markov game. In this setting, the goal is to learn an \\epsilon approximate of the Nash equilibrium of the Markov game while minimizing the sample complexity, i.e. the number of episode played by the agent.  They present Optimistic Nash \nValue Iteration (Nash-VI) that output with high probability a pair of policies that attains an \\epsilon approximate Nash equilibrium in O(H^3SAB/\\epsilon^2) episodes where H is the horizon, S the number of states,  A and B the number of actions for the max-player respectively min-player. This rate matches the lower bound of order \\Omega(H^3S(A+B)/\\epsilon^2) by Jin et al. (2018) up to a factor min(A,B). They extend this result to the multi-player setting with Multi-Nash-VI algorithm of sample complexity O(H^4S^2\\prod_i A_i/\\epsilon^2) where A_i is the size of the action space of player i. The authors also provide VI-Zero an algorithm for reward-free exploration of N-tasks in Markov game with a sample complexity of O(H^4SAB log N/\\epsilon^2) and a lower bound of order \\Omega(H^2SAB/\\epsilon^2).\n\n\n-Contributions\nalgorithmic: Nash-VI (significance: medium)\ntheoretical: Nash-VI sample complexity of order O(H^3SAB/\\epsilon^2) (significance: high)\nalgorithmic: VI-zero (significance: low)\ntheoretical: VI-zeros sample complexity of order O((H^4SAB log N/\\epsilon^2) (significance: medium)\nalgorithmic: Multi-Nash-VI (significance: medium)\ntheoretical:  Multi-Nash-VI sample complexity  of order O((H^4S \\Prod_i A_i/\\epsilon^2)  (significance: medium)\ntheoretical:  lower bound for the sample complexity of reward-free exploration in Markov game of order \\Omega(H^2SAB/\\epsilon^2)\n\n-Score justification/Main comments\nThe paper is well written. The authors use the same technical tool as Azar et al. 2017 to get a sharp dependence in the horizon H and the state space size S. Precisely they use Bernstein bonuses in combination with the Law of total variance in the Markov game to obtain the H^3 and only concentrate the empirical transition along the optimal value function to push the S^2 into second-order terms.\nI have mixed feelings concerning this paper. On one hand, I think the contributions deserve to be published on the other hand I not convinced by the proof. Indeed the proofs are dangerously close to a sketch of proofs (see specific comments below) when it is not the case (see proof of Theorem 6). Even if I think most of the issues are fixable, considering the number of corrections required, I would need to read the updated version to assert if the results are correct.\n\nThe algorithm that attains a dependence A+B instead of AB is almost adversarial, do you think it is possible to obtain the same result with a model-based algorithm that uses the stochastic assumption, or do you see a fundamental reason why it will be impossible? \n\n-Specific comments \nP1: What do you mean by information-theoretic lower bound?\n\nP2, Table 1: It could be interesting to compare these algorithms on a toy example. At least implement Algorithm 1 to prove it is feasible.\n\nP3: precise what is \\pi when you introduce D_{\\pi}Q\n\nP5: Which (estimation) error the bonus \\gamma is compensating precisely?\n\nP6, Algorithm 1: The definition of the empirical transitions and the bonuses are not clear when N_h(s_h,a_h,_b_h) = 0.\n\nP7, comparison with model-free approaches: could you also compare them in term of computational complexity.\n\nP12, Non-asymptotic […] assumptions: precise what do you mean by highly sub-optimal because at the end Algorithm 1 is also sub-optimal by a factor min(A,B).\n\nP15, (Approximate CE): I think that \\phi \\circ\\pi is not a good choice of notation since it is not really composition.\n\nP15, Th 15: Could we, as in the two-player, deduce a Nash equilibrium by only computing CCE and get a polynomial-time algorithm?\n\nP19,Lemma 19: I do not understand the statement of the lemma, since \\bar{V}^k_{h+1}-… is a random variable you need to precise in which sense the inequality |V|(s) \\leq … holds. In particular, considering how you use it in the sequel it is not almost surely. Furthermore in the proof, you need to deal with the case when N_h^k = 0 and you cannot apply the empirical Bernstein Bound from Maurer and Pontil like that since you have a random number of samples. An additional union bound over the possible value of N_h^k is required and you need to prove that conditionally to this choice the samples are independent…. \n\nP19, proof of Lemma 19: you need to precise which event you consider in order to be able to invoke Lemma 18. \nP20, top of the page: the two equalities are wrong in (10) they are inequality because of the clipping for the first one and because \\hat{p}_h^k (\\bar{V} ….) \\geq 0. What do you mean by “with high probability” exactly? And since it is Hoeffding inequality the second term in 1/n is not necessary.\n\nP21, proof of Theorem 3: Again you need to precise with the event you consider to be able to call Lemma 18 or 19 … and guarantee that this event is of probability at least 1-p. Currently, a lot of union bounds are hidden whereas they should be treated properly.  \n\\zeta_h^k and \\xi_h^k are martingales with respect to which filtration?\nWhen you apply Azuma-Hoeffding inequality you implicitly imply that you can upper-bound all the \\zeta_h^k \\xi_h^k by the same constant (moving the bi O outside the sum) but you cannot because they are not necessarily positive.\nFor the pigeon-hole argument again you should consider the case N_h^k=0\nAfter (12) it is \\sqrt(H^3SABT).\n\nP22, Lemma 20: same remarks as Lemma 18 and 19.\n\nP23, Lemma 21: Because of the big O after “these terms […] separately” it seems that the constants in Lemma 21 are wrong. Furthermore, here you apply Hoeffding inequality plus a union bound over an \\epsilon-net or control in KL to obtain the H^2\\sqrt{S/n} bounds. You need to explain this properly.  \n\nP24, proof of Theorem 4: same remark as for the proof of Theorem 3. For (i) it is not only the Law of total variation but also because of the Hoeffding Azuma inequality ( and in Azar et al. it is only proved for stationary transition).\n\nP27, proof of Theorem 6: since you only prove the theorem for H=S=1 you should only state this case and keep the general case as a conjecture. \nS=H=1 in Markov game (where there is nothing to learn) is not equivalent to a matrix game. What do you mean exactly by reward-free matrix game? The agent does not observe the rewards, but in this case, there is nothing to learn, no? I do not think it easily generalizes to the Markov games setting. Could you also obtain the factor \\log(N) in the lower bound?", "extra_scores": {}, "extra_text": {}}, {"review_id": "rVMW_pFElt2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\n\nThe 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).\n\nThe sample complexity of the zero-sum Markov game algorithm (Nash-VI), has a\nsample complexity that is closer to known lower-bounds than existing work, and which is better in the horizon dependency than the best model-free algorithm.\n\nIn this zero-sum setting, the improvement to existing work (VI-UCLB) are the following:\n-  use of an auxiliary bonus that is proportional to the gap of upper-confidence and lower-confidence value function, that allows to use much-smaller standard Hoeffding/Bernstein bonuses\n- use of a relaxed notion of equilibria when looking for the next policy given the Q functions of both player. This relaxed notion is introduced in Xie et al. 2020\n\nThe reward-free setting is simpler, in that it simply use greedy policies for each player, with each player maintaining artifical rewards based on Hoeffding bonuses.\n\nReview\n------\n\nThe paper is very well written and presents some exciting results. It is completely theoretical, but provides two different algorithms for two different settings, in both the two-player and n-player setting. The improvement in existing bounds is significant. I have only slight concerns:\n\n- The algorithmic contribution (Alg. 1) could be seen as incremental, as it changes two elements in known algorithm, one of which (coarse correlated equilibria), having been used for a similar purpose in a previous paper. Similarly, Alg 2. is at the end of the day a rather naive extension of zero-reward exploration in single player MDP. Yet the notion of auxiliary bonus is very original, and the reduction of complexity non-trivial.\n\n- The absence of experiments, even in toy setting, is regrettable. It is\nespecially true as the use of coarse correlated equilibria may be expensive, and\nI would have appreciated seing Alg. 1 implemented. As this is ICLR, extensions\nto function approximations would also be interesting. In particular, comparison\nwith model-free approaches would be welcome, as constants before the sample\ncomplexities may vary.\n\n- Some parts of the text could be further explained: in particular the\nintuitions behind coarse correlated equilibria, which is introduced only mathematically.\n\n- The paper theoretical content is rather heavy, which may make this manuscript more suitable for a journal venue, where it would be more thoroughly reviewed. I must admit that I could not proof read the entire appendix.\n\n I have several questions, as follow:\n\n- I do not understand the note \"Our results directly generalize to randomized reward\nfunctions, since learning the transition is more difficult than learning the reward.\" Could you elaborate on this aspect.\n\n- Is there any reason why we would like to use Hoeffding bonuses instead of Bernstein bonuses in the rewarded case ?\n\n- In the multi-player, rewarded case, it appears that using coarse correlated equilibrium instead of Nash equilibrium yields non-product policies, which is unfortunate. Is there any way that we could obtain product policies solving a relaxed notion of equilibria that would be computable in polynomial time ? Similarly, is there a foreseeable way in which $\\Pi A_i$ could be transformed in a sum ? Lower-bounds in this case are not discussed in this case, is there any ?", "extra_scores": {}, "extra_text": {}}, {"review_id": "NIY6vKLT76a", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe main contribution of the paper is a model-based algorithm called Nash-VI, enjoying simultaneously a regret bound of $\\widetilde O(\\sqrt{H^3SABT})$ after $T$ steps and a PAC-type sample complexity of $\\widetilde {\\mathcal O}(H^3SAB/\\epsilon^2)$ for finding an $\\epsilon$-approximate optimal policy. \n\nThe paper also presents an extension of Nash-VI to the case of reward-free exploration, which is called the VI-Zero algorithm. The sample complexity of VI-Zero depends logarithmically on the number of candidate reward functions, but has a worse dependence on $S$ than that of Nash-VI. \n\nMain Comments:\n\nThe paper is very well-organized and well-written. There are a number of minor easy-to-fix typos that are reported below. The paper overall delivers a clear presentation of algorithms and results, and expect for a few unclear sentences (listed below), it is very a nice read. \n\nOn the technical side, one strong aspect of Nash-VI is that its sample complexity (almost) matches the lower bound except for dependencies on the action set cardinalities. Achieving a near-optimal regret bound is another strong aspect. Finally, the main algorithm outputs a single Markov policy, and not a history-dependent policy. \n\nFor the MDP setup, it is already well established that model-based algorithms are minimax-optimal in terms of both regret and sample complexity. The paper makes a good step towards understanding the benefits of model-based algorithms for stochastic games, thus indicating that their sample complexity could almost match the existing minimax lower bound. \n\nIt turns out that the presented algorithms mostly rely on existing tools already developed for the MDP setup, which are by now fairly standard. That said, the paper does not present any fundamentally different technique than existing ones for MDPs. However, I believe suitably combining all these tools is not a trivial task and deriving such sharp sample complexities requires care. This is in particular true for bonus $\\gamma$ discussed in p. 5. Overall the paper conveys interesting messages advancing our understanding of model-based algorithms for stochastic games, and in my opinion is worth accepting.  \n\nI was unable to check the proofs in such a limited review period, but they appear correct to me. \n\nMinor Comments:\n\n- In p. 6 “during the training phase” please clarify. \n\n- In the statement: “would not hurt the overall sample complexity up to a constant factor”: Did you mean “would hurt the overall sample  complexity only up to a constant factor”\n\n- In p. 7, when referring to $\\mathcal M(\\mathbb P, r)$, it is not clear which reward function $r$ is. Does it one belonging to a set of reward functions? Please clarify.\n\nSome typos:\np. 1: with the problem multi-agent -> … the problem of multi-agent\np. 1: Model-free algorithms has -> … have\np. 3: Markov games is -> … are\np. 3: distribution of actions -> … over actions \np. 6: the policies … is -> … are\np. 6: such policy -> such a policy\np. 6: a $\\epsilon$-approximate -> an …\np. 8: since MDPs is a special case of -> since MDPs are special cases of \np. 8: rerunned -> rerun\n\nThanks for updating the paper in light of my earlier comments.\n\nAfter a long discussion with other reviewers and ACs, we concluded that the paper would require another complete review process in view of newly added proofs, which were unfortunately missing in the first round. My lowered score signals this to the ACs.\n\nI would like to highlight that I became very upset to find out that many important details were skipped and left as exercise to readers. While this would make sense for some repetitive details within a paper, it may not apply to non-trivial proof details, such as the generalization from 2 to arbitrary S or similar.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2cBYAIiwPj8", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study reinforcement learning in two-player (and more) Markov games, providing new algorithms and bounds. They reduce the dependence on horizon H and states S from H^4 S^2 to H^3 S, matching information theoretic lower bound for these factors.\n\nOverall, my impression is that the results are very valuable. In a short paper like this, it's difficult to convey (and absorb) the fundamental theoretical insights behind it.\n\nSome additional work should be done to improve the presentation (see below).\n\nDetailed edits:\n\n\"Model-free algorithms has also\" -> \"Model-free algorithms have also\"\n\n\"finds eps-approximate Nash equilibrium\" -> \"finds eps-approximate Nash equilibria\"\n\n\"multi-player general-sum Markov games\": I thought that's what we've been talking about since the beginning. Explain? Does \"multi-player\" mean more than two? Was it clear we were talking about only two up to this point?\n\n\"the runtime is PPAD-complete\" -> \"the algorithm requires solving a PPAD-complete problem\"??\n\n\"We remark that the current policy is random\" -> \"We remark that the current policy is stochastic\". (To me, \"is random\" reads as \"is chosen at random\".)\n\n\"in Azar, et al. Azar et al. (2017) can not\" -> \"of Azar et al. (2017) cannot\".\n\n\"In order to achieve so,\" -> \"To do so,\"\n\n\"needs to scale as large as\" -> \"needs to be as large as\". Also, shouldn't the big O here be a big theta? After all big O means \"is not bigger than\", so \"needs to be as large as not bigger than\" conveys no useful information.\n\n\"a relaxation of Nash equilibrium\" -> \"a relaxation of the Nash equilibrium\".\n\n\"Coarse Correlated Equalibirum (CCE) instead, a\" -> \"Coarse Correlated Equiliibrum (CCE)---instead, a\".\n\n\"Therefore, executing such policy requires the cooperation of two players during the training phase.\": Wouldn't it also require cooperation during any other phase as well? Also, shouldn't this observation be part of the problem definition? You are learning policies only in the setting where the algorithm is controlling both (all?) players. That's different from the earliest work (Rmax), which provided bounds even when the players are independent.\n\n\"using Bernstein bonus instead of Hoeffding bonus\" -> \"using a Bernstein bonus instead of a Hoeffding bonus\".\n\n\"with Bernstein bonus\" -> \"with the Bernstein bonus\"\n\n\"achieves optimal dependency\" -> \"achieves the optimal dependency\"\n\n\"pair of Markov policy\" -> \"pair of Markov policies\"\n\n\"can not\" -> \"cannot\" (throughout).\n\n\"into the reward-free exploration setting\" -> \"for the reward-free exploration setting\"\n\n\"Due to space limit\" -> \"Due to space limits\".\n\n\"comes from the sample complexity only scales\" -> \"comes from the sample complexity only scaling\".\n\n\"rerunned\" -> \"rerun\".\n\n\"any more\" -> \"anymore\"\n\n\"have regret guarantee\" -> \"have a regret guarantee\"\n\n\"Since MDPs is\" -> \"Since MDPs are\"\n\n\"both exploration\" -> \"both the exploration\"\n\n\"allows arbitrary\" -> \"allows an arbitrary\"\n\n\"in Theorem 5 scales\" -> \"in Theorem 5 scaling\"\n\n\"we defer the detailed setups\": Not just the details... you are claiming to provide Algorithms 3 and 4, which only appear there.\n\n\"How to design\" -> \"How can we design\"\n\n\"We would like to leave these as future work.\" -> \"We leave these problems as future work.\"?\n\n\"On the complexity of approximating a nash equilibrium\" -> \"On the complexity of approximating a Nash equilibrium\".", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers, AC, and PCs participated in a very thorough discussion. AC ultimately felt that the work was unfinished, and in particular that details in the proofs still needed work before publication.


Decision: Reject