Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model
Authors: Gen Li
Yuejie Chi
Yuting Wei
Yuxin Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Markov games
sample complexity
Nash equilibrium
coarse correlated equilibrium
adversarial learning
Follow-the-Regularized-Leader

Abstract: This paper studies multi-agent reinforcement learning in Markov games, with the goal of learning Nash equilibria or coarse correlated equilibria (CCE) sample-optimally. All prior results suffer from at least one of the two obstacles: the curse of multiple agents and the barrier of long horizon, regardless of the sampling protocol in use. We take a step towards settling this problem, assuming access to a flexible sampling mechanism: the generative model. Focusing on non-stationary finite-horizon Markov games, we develop a fast learning algorithm called Q-FTRL and an adaptive sampling scheme that leverage the optimism principle in online adversarial learning (particularly the Follow-the-Regularized-Leader (FTRL) method). Our algorithm learns an $\varepsilon$-approximate CCE in a general-sum Markov game using  
$$ \widetilde{O}\bigg( \frac{H^4 S \sum_{i=1}^m A_i}{\varepsilon^2} \bigg) $$ 
samples, where $m$ is the number of players, $S$ indicates the number of states, $H$ is the horizon, and $A_i$ denotes the number of actions for the $i$-th player. This is minimax-optimal (up to log factor) when $m$ is fixed. When applied to two-player zero-sum Markov games, our algorithm provably finds an $\varepsilon$-approximate Nash equilibrium with a minimal number of samples. Along the way, we derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities, which might be of independent interest. 

Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model
Gen Li UPenn
Yuejie Chi CMU
Yuting Wei UPenn
Yuxin Chen UPenn
Abstract
This paper studies multi-agent reinforcement learning in Markov games, with the goal of learning Nash equilibria or coarse correlated equilibria (CCE) sample- optimally. All prior results suffer from at least one of the two obstacles: the curse multiple agents and the barrier of long horizon, regardless of the sampling pro- tocol in We take step towards settling this problem, assuming access to flexible sampling mechanism: the generative model. Focusing on non-stationary finite-horizon Markov games, develop fast learning algorithm called Q- FTRL and an adaptive sampling scheme that leverage the optimism principle in online adversarial learning (particularly the -eroowtth-Regularizeeeeee (FTRL) method), Our algorithm learns an é-approximate CCE in a general-sum Markov game using
0 (
samples, where is the number of players, S indicates the number of states, H is the horizon, and A, denotes the number actions for the i-th player. This is minimax-optimal (up log factor) when is fixed. When applied player zero-sum Markov games, our algorithm provably finds an e-approximate Nash equilibrium with minimal number of samples. Along the way, we derive refined regret bound for FTRL that makes explicit the role of variance-type quan- tities, which might be of independent interest.
two-
Introduction
The thriving field of multi-agen reinforcement learning (MARL) studies how group of interacting agents make decisions autonomously in shared dynamic environment [80]. The recent develop- ments in game playing [66, 9], self-driving vehicles [58], and multi-robot control [45] are prime examples of MARL in action. In practice, there is no shortage of situations where the agents in- volved have conflict of interest, and they have to act competitively in order to promote their own benefits (possibly at the expense of one another). Scenarios of this kind are frequently modeled via Markov games (MGs) [59, 42), framework that has been fruitful playground to formalize and stimulate the studies of competitive MARL.
In view of the irreconcilable competition between individual players, solutions of competitive MARL normally take the form of certain equilibrium strategy profiles, which are perhaps best epito- mized by the concept of Nash equilibrium (NE) [49]. In Nash equilibrium, gain can be realized through a unilateral change assuming no coordination between players and hence no player has incentives to deviate from her current strategy/policy. A myriad of research has been conducted surrounding NE, which spans various aspects like existence, learnability, computational hardness, and algorithm design, among others [59, 20, 12, 53, 52, 22, 42, 28, 50, 33). Given that finding NE is notoriously expensive in general (except for special cases like two-player zero-sum MGs) [20, 21), several more tractable solution concepts have emerged in the studies of game theory and MARL,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

prominent example being the coarse correlated equilibrium (CCE) [47]. A key compromise made in the CCE that it permits the players to act in an coordinated fashion, which contrasts sharply with the absence of coordination in the definition of NE.
One critical challenge impacting modern MARL applications is data efficieney. The players involved often have minimal knowledge about how the environment responds to their actions, and have to learn the dynamies and preferable actions by probing the unknown environment. For MARL to expand into applications with enormous dimensionality and long planning horizon, the learning algorithms must manage to make efficient use of the collected data. Nevertheless, how learn NE and/or CCE with optimal sample complexity remains by and large unsettled even when it comes to the most basic setting: two-player zero-sum Markov games, as we shall discuss below.
Example: inadequacy in learning two-player zero-sum Markov games. To facilitate concrete comparisons, let us review two representative algorithms aimed at learning NE in two-player zero- sum MGs. These algorithms have been studied under two drastically different sampling protocols, and we shall discuss the shortfalls of the cutting-edge sample complexity results. In two-player zero-sum MG, we denote by S the number of states and H the horizon or effective horizon, whereas A and A denote respectively the number of actions for the max-player and the min-player.
Model-based methods under either a generative model or online exploration. Assuming access generative model (so that one sample arbitrary state-action tuples), Zhang al. [79] investigated a natural model-based algorithm, which performs planning (e.g.. value iteration) on an empirical MG derived from samples produced non-adaptively by the generative model. Focusing
on stationary discounted infinite-horizon MGs, their algorithm finds an e-approximate NE with
H A2 22
samples.
(1)
In parallel, Liu et al. [43] studied non-stationary finite-horizon MGs with online exploration, and obtained similar sample complexity bounds, i.e.,
or (H
samples
episodes
for learning e-approximate NE. While these bounds achieve minimax-optimal dependency on the horizon H, a major drawback emerges - commonly referred to as the curse of multiple agents; namely, these results scale proportionally with the total number of joint actions (i.e., II A,), a quantity that blows up exponentially with the number of players.
V-learning for online exploration settings. Focusing on online exploration settings, Bai et al. [5], Jin et al. [31] proposed algorithm called V-learning that leverages the advances in online adversarial learning (c.g., adversarial bandits) to circumvent the curse of multiple agents. This algorithm provably yields e-approximate NE in non-stationary finite-horizon MGs using
H 5H + A2)
HH ((AS(A + A2)
samples
or
episodes,
22
E2
which effectively brings down the sample size scaling (2) from A (i.e., the number of joint actions) to A₁ + A2 (i.e., the sum of individual actions). It is worth pointing out, however, that this theory appears sub-optimal in terms of the horizon dependency, it is a factor of H² above the minimax lower bound.
Key issues and our main contributions. While the above summary focuses on two-player zero- sum MGs, it unveils a fundamental issue surrounding the sample efficiency of learning equilibria; that is, all existing results in this front irrespective of the sampling mechanism in use fall short of overcoming at least one of the two major hurdles: (i) the curse of multiple agents, and (ii) the barrier of long horizon. A natural question to pose is:
Question: can we learn a Nash equilibrium in a two-player zero-sum Markov game in sample-optine and cmmputation-efffcieen fashion?
To settle this favorably, both of the above hurdles need to be crossed simultaneously. Moving beyond two-player zero-sum MGs, it is not surprising to see that general-sum multi-player MGs have to grapple with the aforementioned two hurdles as well. Thus, the following question also comes into mind when learning CCE (a compromise due to the general intractability of learning NE);

---

Question: can we learn coarse correlated equilibrium in multi playtr general-sum Markov game in a sample-optimal and computation-effen eeffccienn fashion?
Note that these questions remain open regardless of the sampling scheme in use.
This paper takes first step towards solving the problem by assuming access the most flexi- ble sampling protocol: the generative model (or simulator). In stark contrast to the single-agent case where uniform sampling of all state-action pairs suffices [3. 38], the multi-agent scenario re- quires one to take samples intelligently and adaptively, crucial step to avoid inefficient use of data (otherwise one cannot hope to break the curse of multiple agents). With the aim of computing an e-approximate equilibrium in a non ntn-stationary finite-horizon MG, we come up with a computation- ally efficient learning algorithm (accompanied by an adaptive sampling strategy) that accomplishes this goal with no more than
H' SSAS(A)
samples
(learning e-NE in two-player zero-sum MGs)
(4)
H
m
samples
(learning E-CCE in multi pllytr general-sum MGs)
drawn from the generative model. Encouragingly, this sample complexity bound matches the min- imax lower limit (up to a logarithmic factor) as long as the number of players m 2 2 is a fixed constant or grows only logarithmically in problem parameters. Our sample complexity theory is valid for the full e-range (i.e.. any & E (0. H)); this unveils that no burn-in cost is needed for our algorithm to achieve sample optimality, which lends itself well to sample-hungry applications.
The proposed algorithm is inspired by two key algorithmic ideas in RI. and bandit literature: (i) optimism in the face of uncertainty (by leveraging upper confidence bounds (UCBs) in value timation), and (ii) online and adversarial learning (particularly the Mhalow--th-Regularizeee Leader (FTRL) algorithm). Note that the optimal design of bonus terms typically based on certain data-driven variance estimates - is substantially more challenging than the single-agent case, as it requires intricate adaptation in response to the policy changes of one another as well as compatibility with the FTRL dynamics. Two points are worth emphasizing (which will be made precise later on):
The efficacy of FTRL in breaking the curse of multiple agents has been illustrated in Jin et al. [31], Song et al. [63], Mao and Başar [44]. To improve horizon dependency, one needs to exploit connections between the performance of FTRL and certain variances. Towards this, develop a refined regret bound for FTRL that unveils the role of variance-style quantities, which was previously unavailable.
The bonus terms entail Bernstein style variance estimates that mimic the variance-style quantities appearing in our refined FTRL regret bounds, and are carefully chosen so as to ensure certain decomposability over steps. This is crucial in optimizing the horizon dependency.
Additionally, the policy returned by our algorithm is Markovian (i.e., the action selection probability depends only on the current state and step fi), and the algorithm can be carried out in a decentralized manner without the need of directly observing the opponents' actions.
Notation. Let us also gather several convenient notation that shall be used multiple times. For any positive integer we write [n] == {1. n}. We shall abuse notation and let 1 and 0 denote the all-one vector and the all-zero vector, respectively. For a sequence {ax J&z1 C (0, 1]. we define
0. IT (1 az); if < <i<k
k = 0
(5)
O'k:
if
for any 1 S i S h. For a given vector I E RSA (resp. y E RSAB), we denote by a(s,a) (resp. y(s, a, b)) the entry of z (resp. y) associated with the state-action combination (s, a) (resp. (s, a. b)). as long as is clear from the context. Next, consider any two vectors a = [aglisien 6) indicate that a, by (resp. a; S bi) holds for all i; we allow scalar functions to take vector-valued arguments in order to denote entrywise operations (e.g., a² [at]ısisn and a² (a:)i<;s>); and denote by a b [abbllsiin the Hadamard product. For a finite set A (1,... A). denote by A(A) for E RA Σ, 2; 1; 2 0) the probability simplex over A. For any function f with domain A (or B). we adopt the notation
and b- [b:] [b]lssinn We use a S b (resp.
E= = E. (a))s(a)
and
Var= = Σ. ((a)([(a) ²
(6)
3

---

2 Background and models
In this section, we introduce the basics for Markov games, as well as the solution concepts of Nash equilibrium and coarse correlated equilibrium.
Markoy games. A non-stationary finite-horizon multi-player general-sum Markov game, denoted by MG {S, (Aisisism II, P.r). involves m players competing against each other, and consists of several key elements to be formalized below. Recall that A(S) represents the probability simplex over the set S.
S {I, ... .S} is the state space of the shared environment, which comprises S different states. For each 1 S i S m, let A, {1. .A,)) represent the action space of the i-th player, which contains A, different actions. Here and below, we denote
A Ai x Am
and
A II (1sism).
Throughout the paper, we shall often use the boldface letter a E A (resp. a-; E AA-;) to denote a joint action profile of all players (resp. a joint action profile excluding the i-th player's action).
Hl stands for the horizon length of the Markov game.
P {Pa]ingH with PA S x A + A(S) - denotes the probability transition kernel of the probability of .MG transitioning from state s to state s' at step h when the joint action profile taken by the players is a.
MG.. Namely, for any (s, a, h, s') E S Ax [H] x S, we let Pa (s' s, a) indicate
r = hriahssssh.sssss - with ruh : :S A + [0. 1 represents the (deterministic) reward function. Namely, for any (s, h) E S x Ax [H] ri,h a) stands for the immediate reward the i-th player gains state s step h, the joint action profile is a. Here and throughout, we assume normalized rewards in the sense that (s) E [0, for any (8, (s,a, h, E x A x [H] x [m]]
As an important special case, a two-player zero-sum Markov game - denoted by MG
{s, (2),,A2), H, P.r) satisfies 72,6 - for all h E [H]. Following the convention, assume that ri,h 2 0 for all h [H], and refer to the first (resp. second) player the max-player (resp. the min-player).
Markov policies. This paper focuses on the class of Markov policies, such that the action selection strategies of the players are determined by the current state s and the step number h, without de- pending on previously visited states. To begin with, let n; { IIshhH represent the policy of the i-th player. Here, T., (- s) E A(A)) for any (s, h) E S x [H]. where TT, s) indicates the probability of the i-th player selecting action in state
step h. The joint Markov policy can be defined analogously: we let π = (T.,..... Tm) : S x [H] + A (.A) represent a joint Markov policy
of all players, where the joint actions of all players in state and step h are chosen according the distribution specified by (- (- [s) = (TI,,,,-- Tm, (- [ E ((A). For any given joint policy m, employ T-; to represent the policies of all but the i-th player, and let --i, denote the policies of all but the i-th player at step h. All policies are assumed throughout to be Markovian, except our brief remarks on non-Markovian policies in Section 3.2.
Additionally, a joint policy и is said to be a product policy if Ti...., Tm are executed in a statistically independent manner (namely, under policy the players take actions independently), and shall adopt the notation π = ग x ... X T. to indicate that ı a product policy.
Value functions. Consider a Markovian trajectory ((sh, an) higggt. where 8n E S is the state at step h and a₁ E A is the joint action profile step h. For any given joint policy æ and any step h E [H], we define the value function ViJ S R of the i-th player under policy follows:
H
V.T (s) = I
Σ I=sh
Tea (5t, a:) sh
E
(8)
'The careful reader might immediately note that P2,6 S 0, thus falling outside our assumed range for the reward function. This, however, can be easily addressed by enforcing a positive global shift to P2,4 without changing the learning process.

---

where the expectation is taken over the Markovian trajectory {(h,. an)} with the m players jointly executing policy ग. that is, conditional on S/. we draw aj (-(-1sh) and then s Pa.
(8, (h, a..).
In addition, consider the case where (i) all but the i-th player executes the joint policy π-1 and (ii) the i-th player executes policy zi independently from the other players; we shall denote by V x== the resulting value function under this joint policy Ti m--. By optimizing over all T//. we can further define
i,b
max T/ ((A)
ViA
VTTX*-((s) (s),
V(s,h,)) E S [H] x [m].
It is known that there exists at least one policy, denoted by (T : S x [M] + A(A,) and
commonly referred to as the best-response policy, that simultaneously attain ViA. V() (s) for all
E [H] and all s E S. It is worth emphasizing that the best-response policy oं (m-s) is the best among all policies of the i-th player executed independently of T- Furthermore, if we freeze - then the Bellman optimality condition for the i-th player can be expressed as [8]
VeA Vis
max a:EA:
[ran(s,a) + (Pa(-1 Verti
(I0)
for all (s, h, i) E S [H] [m]] where the joint action profile is composed of a; for the i-th player and a_, for the remaining ones.
Equilibria of Markov games. In a multi-agent Markov game, each player wishes to maximize its own value function. Due the competing objectives. finding some sorts of equilibria e.g., the Nash equilibrium [48] and the coarse correlated equilibrium [47, 2] becomes a central topic in the studies of Markov games. Let us introduce these solution concepts below.
Nash equilibrium. A product policy equilibrium of MG if the following holds:
... Tm is said to be a (mixed-straaeey) Nash
(T) (s), for all (s, E S x [m].
(11)
In other words, conditional on the opponents' current policy and the assumption that all players take actions independently, no player can harvest any gain by unilaterally deviating from its current policy.
Coarse correlated equilibrium. A joint policy is said to be coarse correlated equilibrium of MG if
for all (s, i) E S [m]. While CCE also ensures that no unilateral deviation (performed independently from others) is beneficial, its key distinction from the definition of NE lies in the fact that it allows the policy to be correlated across the players. Any NE of MG is, self-evidently, also CCE.
ViT(() V,'"'(ss,,
(12)
In practice, it might be challenging to compute an "exact" equilibrium, and instead one would seek to find approximate solutions. Towards this end, we find it helpful to define the sub-optimality gap of policy æ as follows (measured in an based manner)
gap(=) == max gap(T;5),
(13a)
where
gap(T::) max 1st5m
(s) (s)
(13b)
With this sub-optimality measure in place, a product policy π = कi ... X Tm is said to be an E-approximate NE - more conciscly, e-Nash - if the resultant sub-optimality gap obeys gap(=) < e. Similarly, joint (and possibly correlated) policy π is said to be an e-approximate CCE or more concisely, e-CCE if gap((T) <
Generative model/ simulator. In reality, we oftentimes do not have access to perfect descriptions (e.g., accurate knowledge of the transition kernel P) of the Markov game under consideration; in- stead, one has to learn the true model on the basis of data samples. When comes to the data gener- ating mechanism, this paper assumes access to generative model (also called a simulator) [35, 34]:
5

---

in each call to the generative model, the learner can choose an arbitrary (s, a. E x [ and obtain an independent sample generated based on the true transition kernel:
s,)
In words, generative model facilitates query of arbitrary sate-action-stee tuples, which helps al- leviate the sampling constraints arising in online episodic settings for exploration. The goal of the current paper to compute an e-approximate equilibrium (either NE CCE) of Mg with few samples as possible, i.e., using minimal number of calls to the generative model.
Sample-efficient learning with a generative model
In this section, we put forward an efficient algorithm aimed at learning an s-approximate equilibrium with the assistance of generative model, and demonstrate its sample optimality for the full e-range.
3.1 Algorithm description
We now describe the proposed algorithm, which is inspired by the optimism principle and the FTRL algorithm for online/adversarial learning. Following the dynamic programming approach [8], our algorithm employs backward recursion from step h H back to h = 1: in fact, we shall finish the sampling and learning processes for step h before moving backward to step h - 1. For each h, the i-th player calls the generative model for K rounds, with each round drawing SA, independent samples; as a result, the total sample size is given by KSH Σi=1 A,. what follows, let us first introduce some convenient notation that facilitates
exposition of the algorithm.
Notation. Consider any step E ( any player E [m]. and any data collection round [K]. The algorithm maintains the following iterates, whose notation is gathered here with their formal definitions introduced later.
Ve, E R$ represents the final estimate of the value function at step h by the i-th player; in particular, we set V1 =
Q E SA: represents the Q-function estimate of the i-th player at step h after the k-th round of data collection.
ai E SA. stands for a certain "one-step-look-aheadd" Q-function estimate of the i-th player at step h using samples collected in the k-th round.
r E RSS, denotes the sample reward vector for step h received by the i-th player in the k-th round.
P. E SAA denotes the empirical probability transition matrix for step constructed using the samples collected by the i-th player in the k-th round.
B., E R denotes the bonus vector chosen by the i-th player step during final value estima- tion.
E., S + ((A,) denotes the policy iterate of the i-th player at step h before the beginning of the k-th round of data collection; in partieular, set nij, A. to be uniform, namely, Ti (a: 1/A, for any (s, a.) S A,,
Crucially, the above objects are all constructed from the perspective of a single player, and hence resemble those needed to operate "single-agent" MDP (as opposed to MARL). As such, the com- plexity of storing/updating the above objects only scales with the aggregate size of the individual action space, rather than the size the product action space.
Main steps of the proposed algorithm. As mentioned above, our algorithm collects multiple rounds of independent samples for each h. In what follows, let describe the proposed proce- dure for the i-th player in the k-th round for step h.
1. Sampling and model estimation. For each as) x Ai draw an independent sample as follows
Sy.h. Pa [s, h,,,,,,, and
Tkd.baaa
(14a)

---

where h,k, 8, az) = h, s, E A consists of independent individual actions drawn from
ak(ki h, 8, az) (-18) (+)) and
as 11 8, 8,0) = di.
(14b)
These samples then employed construct the sample reward vector r.A RSA., and empirical probability transition kernel P. E TAA such that
11, if Sh
(s, ai) = Tki. and
(s'
(14c)
0, else
for all as,,,'s)) s') S A, S. Note that the i-th player only needs to compute (14c), without the need of directly observing the other players' actions.
2. Q-function estimation. Following the dynamic programming approach, we first compute the "one- step-look-ahead" Q-function estimate follows
- rf + P.,,, Vin+iI-
(15)
We then adopt the update rule of Q-learning:
U = an) Q,,7 audin
(16)
where < ag < is the learning rate. Applying (16) recursively and using the quantities defined in (5), easily arrive at the following expansion:
&
Qi Σ agg
(17)
3. Policy updates. Once the Q-estimates are updated, we adopt the exponential weights strategy to update the policy iterate of the i-th player as follows
exp (76+11/ ( a:))
(a; EvEA, exp (T++1 Q (s, n i.
k+1
v(s.a;) ES A.,
(18)
where 76+11 O is another learning rate associated with policy updates (to be specified shortly). fact, this subroutine implements the Follow-the wew.ee---ggglaieed-eeaaaee strategy [56]:
{ (M, QZ, +
_F(W)
1
#
(-13) = arg min HEA(A.)
(19)
Mh+1
= where the regularizer F(-) is chosen to be the negative entropy function F(u)
EneA, p(a) log (u(a)).
After carrying out K rounds of the above procedure, our final policy estimate मे S [H] + A(A)
and the value estimate V S + IR for step h are taken respectively to be
(s)(s) min
Σ a (=tn((1)) cin(..)) Ben(s), H h 11+1 and
(20a)
K
m
(a 8) = Σ O II m
(20b)
for any (s, a [ai...., aml) SxA, where {or } is defined in (5) and (s,A(s) > is some bonus term (taking the form some data-driven upper confidence bound) to be specified momentarily. is worth pointing that the final policy (20b) takes the form of mixture of product policies. In the special case of two-player zero-sum MGs, we can alternatively output product policy
(two-player zero-sum MGs)
के
72,
(21)
where for each i = 1, we take म. (ar,hisnSH with मE Σk1
ag K
Ti

---

Algorithm 1: Q-FTRL.
Input: number of rounds for each step, learning rates {au} (cf. (22)) and (m++1) (cf. (23)).
// set initial value estimates 0, and initial policies uniform distributions.
Initialize: for any e [m] and any (s,a,, e A [H], set ViH+1(s) (s,(s, and 1 (a: 1/4,.
for H do
for k = 1 to K do
for = 1 to m do
// draw independent samples, and construct empirical models.
(r), P. sampling(i, h, क (T).)))(m)) /* see Algorithm 2. */
// update Q-estimates with upper confidence bounds.
Compute L., =f, P V.N+1, and update O according to (16).
// update policy estimates using FTRL.
k++ Update iihh
according to (18).
// output the final value estimate for step h.
for = to m do 10
Update Vi, according to (20a), where Bi, is given in (24),
if MG is two-player zero-sum Markov game then
K & output: #1 x f2., where for any i 1,2, म. (Rs, with Tan Ex= ok "i,h"
12
if Mg is multi-player general-sum Markov game then
output: {mn)skhH. where n = Σ a - ( x x a mb.
14
The whole procedure is summarized in Algorithm 1.
Choices of learning rates. Thus far, have yet specified the sequences of learning rates, which we describe now. The learning rates associated with Q-function updates are set to be rescaled linear, namely.
Ca log K
k: 1,2,...
(22)
h: 1 co log K'
for constant Ca 2 24. In addition, the learning rates associated with policy updates chosen to be:
log K Og H
T
= 1,2,...
(23)
Choices of bonus terms. remains to specify the bonus terms, which are selected based on fairly intricate upper confidence bounds. This constitutes a key and perhaps the most challenging component of our algorithm design. Specifically, we take
log 3 KSS. A.
Var Var (cEn(o.)) H
BLn(s)
Okk
(24)
K
any h)) E [m] x x [H], where Cb is some sufficiently large constant; see also (6) for the definition of the variance-style quantity. As in previous works, the bonus terms, which are chosen carefully in a data-driven fashion, need to compensate for the uncertainty incurred during the estimation process.
3.2 Main results
As it turns out, the proposed algorithm is tractable and provably sample-efficient. We begin by characterizing its sample complexity when learning Nash equilibria in two-player zero-sum MGs,

---

Algorithm 2: Auxiliary function sampling (i, h Ta (egn)))lm))
Initialize: F= e IRA,, and P = 0 RSA:XS.
2 for (s, a4) A, do
Draw independent sample from the generative model: sy,a, pn( |s, a(s, a:)). where ((s, a.) (s, a,)lisism is composed of independent individual actions drawn from
and Set F(s, a;) = Ti, (s, and P(s',a, |s, (s)a;)= = 1. Return: (r, P).
as)),a)) ind my (8) (i + i)
ai(s, at-
(25)
and then shift attention to learning CCE in multi-player general-sum MGs (given the intractabilityy of learning NEs in general).
Theorem 1 (NE for two-player zero-sum MGs). Consider two-player zero-sum Markov game, and consider any E E (0, H] and any < 1. Suppose that
Ox H log" (KS(At+Aa) K
(26)
E²
for some large enough universal constant Qk O. With probability at least 8, the product policy TT x T2 computed by Algorithm I is an 8-approximate Nash equilibrium, i.e., its sub-optimality gap (cf. (13)) obeys gap m x R2) S.
Theorem (CCE for multi-player general-sum MGs). Consider an m-player general-sum Markov game, and consider any (0, H) and any 8 <
Suppose that
Cx 3 log" ( (KS A1) KZ
(27)
6²
for some large enough universal conslant Ox O. With probability at least - 8, the joint policy returned by Algorithm 1 is an E-approximate CCE, i.e., its sub-optimality gap (cf. (13)) obeys gap
Theorems 1-2 establish sample complexity upper bounds for the proposed algorithm, which we take a moment to interpret as follows. The proofs of these two theorems are postponed to Appendix C in the supplementary material.
Sample complexity. When a generative model is available, Theorems 1-2 assert that the total num- ber of samples (i.e., KSH Σ, A,) needed for Algorithm to work
1 H (0( ((A))aa))) 0 H
for learning an s-NE in two-player zero-sum MGs;
Ex 5m
(28)
S S1 g2
for learning an s-CCE in multi-player general-sum MGs.
As far as we know, our theorems deliver the first results that uncover the plausibility of simultane- ously overcoming the long-horizon barrier and the curse of multi-agents. Let us compare (28) with prior art.
NE in two-player zero-sum MGs. First, consider learning s-NE policies in two-player zero-sum MGs. In comparison to Zhang et al. [79] (cf. (1)), our result reveals that what ultimately matters is the total number of individual actions (i.e., A₁ A2) as opposed to the total number A₁ A2 of possible joint actions: additionally, our results exhibit improved horizon dependency (by factor of H compared Bai al. [5], Jin et al. [31] (see (3)), although we remark that the online sampling protocol therein is clearly more restrictive than generative model.
CCE in multi- lilti--plyer general-sun -um MGs (for a fixed m). Similar messages carry over to the task of learning multi-playe general-sum MGs when the number of players m is fixed constant. Liu et al. [43] provided the first non-asymptotic result on learning CCE in the exploration setting; the model-based algorithm studied therein learns e-CCE using
H 52
A
H S2
A
δ
samples
or
δ
episodes
(29)
22
82

---

which is sub-optimal in terms of the dependency on both H and S and suffers from the curse of multiple agents. more recent strand of works focused on type of online RL algorithms called V- learning, which exploited the effectiveness of adversarial learning subroutines in overcoming the curse of multi-agents [44, 63, 31 along this line, the state-of-the-an sample complexity bound is [31]:
S1 maxisism A.)
Ô S (1'S 0 maxicism O A
samples
or
episodes,
(30)
which remains suboptimal in terms of the horizon dependency. As a drawback of these works, the policy returned by V-learning is non-Markovian, an issue that has been recently addressed by Daskalakis et al. [23] at the price of much higher sample complexity. It is worth emphasizing that all these works assume the online exploration setting as opposed to the scenario with generative model.
Minimax optimality. To assess the tightness of our result (28), it is helpful to look at the information-theorriic limit. Following the minimax lower bound for single-agent MDPs [3, 41], one can develop a minimax sample complexity lower bound for Markov games (w.r.. finding either an e-NE or an E-CCE) that scales as
H$S maxisism A
(minimax lower bound)
(31)
22
modulo some logarithmic factor; see Appendix E.3 in the supplementary material for formal state- ment and its proof. Taking this together with (28) confirms the minimax optimality of our algorithm (up to logarithmic terms) when the number m of players is fixed grows only logarithmically in problem parameters.
No burn-in sample size and full e-range. It is noteworthy that the validity of our sample com- plexity bound (28) is guaranteed for the entire range of e-levels (i.c., any E (0, H)). This feature is particularly appealing in the data-starved applications, as it implies that there is no burn-in sample size needed for our algorithm to work optimally.
Miscellaneous properties of our algorithm. Finally, we would like to remark in passing that our learning algorithm enjoys several properties that might be practically appealing. For instance, the output policies are Markovian in nature, which depend only on the current state and step number h. This is enabled thanks to the availability of the generative model, which allows us to settle the sampling and learning process for step h + 1 completely before moving backward to step h; in contrast, the online sampling protocol studied in Bai et al. [5], Jin et al. [31] cannot be implemented in this way without incurring information loss. In addition, our algorithm can be carried out in a decentralized fashion (except that the final estimate needs to aggregate policy iterates from all players), with each player acting in symmetric yet independent manner (without the need of knowing each other's 's individual action). Our algorithm is also "rational" in the sense that it converges to the best-response policy of a player if all other players freeze their policies. All this is achieved under minimal sample complexity with the aid of the generative model.
4 Discussion
The primary contribution of this paper has been to develop a sample-optima paradigm that simulta- neously overcomes the curse of multiple agents and optimizes the horizon dependency when solving multi-player Markov games. This goal was not accomplished in any of the previous works, regard- less of the sampling mechanism in use. The adoption of the adversarial learning subroutine helps break the curse of multiple agents compared to the prior model-basch approach [79, 43], whereas the availability of the generative model in conjunction with the variance-aware bonus design improves horizon dependency compared to Bai et al. [5], Jin et al. [31].
Acknowledgements: Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the Google Research Scholar Award, the AFOSR grant FA9550-22- 1-019,, the ONR grant N00 1 1-2354, and the NSF grants CCF-2221009 CCF-1907661.
IIS-221871 13 and IIS IIS-2218773. Y. Wei supported in part by the the NSF grants CCF-2106778, DMS-2147546/200 award DMS-2143215. Y. Chi are supported in part by the grants ONR CCF-2106778 and
and CAREER NSF and CAREER award ECCS-1818571, Part of this work was done while G. Li, Y. Wei and Y. Chen were visiting the Simons Institute for the Theory of Computing.
10

---

References
[1] A. Agarwal, S. Kakade, and I.. F. Yang. Model-based reinforcement learning with generative model minimax optimal. Conference on Learning Theory, pages 67-83. PMLR, 2020.
[2] R. J. Aumann. Correlated equilibrium as an expression of Bayesian rationality. Econometrica: Journal of the Econometric Society, pages 1-18, 1987.
[3] M. G. Azar, R. Munos, and H. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91(3):325-349 2013.
[4] Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pages 551-560. PMLR, 2020.
[5] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play, Advances in neural information processing systems, 33:2159-21777 2020.
[6] A. Beck. First-order methods in optimization. SIAM, 2017.
[7] C. L. Beck and R. Srikant. Error bounds for constant step-size Q-learning. Systems & control letters, 61012):1233-1208, 2012.
[8] D. P. Bertsekas. Dynamic programming and optimal control (4th edition). Athena Scientific, 2017.
[9] N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456):885 890, 2019.
[10] S. Cen, Y. Wei, and Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34, 2021.
[11] S. Cen, Y. Chi, S. Du and L. Xiao. Faster last-iterate convergence of policy optimization in zero-sum markov games. arXiv preprint arX1v:2210.010550, 2022.
[12] X. Chen, Y. Cheng, and B. Tang. Well-supported versus approximate Nash equilibria: Query complexity of large games. arXiv preprint 1rX10:151,.00785, 2015.
[13] Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. Finite-sample analysis of stochas- tic approximation using smooth convex envelopes. arXiv preprint 00X0442002.00874, 2020.
[14] Z. Chen, S. Ma, and Zhou. Sample efficient stochastic policy extragradient algorithm for zero-sum Markov game. In International Conference Learning Representations, 2021.
[15] Z. Chen, D. Zhou, and Q Gu. Almost optimal algorithms for two-player Markov games with linear function approximation. arXiv preprint arXiv:2102.07400 2021.
[16] Z. Chen, D. Zhou, and Q. Gu. Almost optimal algorithms for two-player zero-sum linear mixture Markov games. In International Conference on Algorithmic Learning Theory, pages 227-261. PMLR, 2022.
[17] Q. Cui and S. Du. When is offline two-player zero-sum Markov game solvable? arXiv preprint arXiv:2201.03522 2022.
[18] Q Cui and S. S. Du. Provably efficient offline multi-agent reinforcement learning via strategy- wise bonus. arXiv preprint Xww.::220060005999 2022.
[19] Q Cui and L. F. Yang. Minimax sample complexity for turn-based stochastic game. In Uncer- tainty in Artificial Intelligence, pages 1496-1504. PMLR, 2021.
[20] C. Daskalakis. On the complexity of approximating a nash equilibrium. ACM Transactions on Algorithms (TALG), 9(3):1-35, 2013.
[21] C. Daskalakis, P. Goldberg, and Papadimitriou. The complexity of computing Nash cquilibrium. SIAM Journal on Computing, 39(1):15--259 2009.

---

[22] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for com- petitive reinforcement learning. In Advances in Neural Information Processing Systems, vol- ume 33, pages 5527-5540, 2020.
[23] C. Daskalakis, N. Golowich, and K. Zhang. The complexity of markov equilibrium in stochas- tic games. arXiv preprint arXiv:2204.03990 2022.
[24] Z. Dou, Z. Yang, Z. Wang, and S. Du dap-dependent bounds for two-player markov games. In International Conference on Artificial Intelligence and Statisties, pages 432 455, 2022.
[25] S. S. Du, S. M. Kakade, R. Wang, and L. F. Yang. Is a good representation sufficient for sample efficient reinforcement learning? In International Conference Learning Representations, 2020.
[26] E. Even-Dar and Y. Mansour. Learning rates for Q-learning, Journal of machine learning Research, 1(Dec):1-25, 2003.
[27] D. A. Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100- 1 118, 1975.
[28] T. D. Hansen, P. B. Miltersen, and U. Zwick. Strategy iteration is strongly polynomial for 2-player turn-based based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1-16, 2013.
[29] Z. Jia, L. F. Yang, and M. Wang. Feature-based q-learning for two-player stochastic games. arXiv preprint arXiv:
[30] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873, 2018.
[31] C. Jin, Q Liu, Y. Wang, and T. Yu. V-learnin--a simple, efficient, decentralized algorithm for multiagent RL. arXiv preprint 1rXiv:2110.1455:5 2021.
[32] Y. Jin and A. Sidford. Towards tight bounds on the sample complexity of average-reward MDPs. In International Conference on Machine Learning, pages 5055-5064. PMLR, 2021.
[33] Y. Jin, V. Muthukumar, and A. Sidford. The complexity of infinite-horizon general-sum stochastic games. arXiv preprint arXiv:2204.04186. 2022.
[34] S. Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London, 2003.
[35] M. Kearns, Y. Mansour, and A. Y. Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine learning, 49(2-3):193-22) 100999322,,2222 2002.
[36] K. Khamaru, A. Pananjady, F. Ruan, J. Wainwright, and M. Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Mathematics of Data Science, 1(1):1013 2021.
[37] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[38] G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. In Advances in Neural Information Processing Systems, volume 33, 2020.
[39] G. Li, C. Cai, Y. Chen, Gu, Y. Wei, and Chi. Q-learning minimax optimal? tight sample complexity analysis. arXiv preprint arXiv:2102.06544 2021.
[40] G. Li, L.. Shi, Y. Chen, Y. Gu, and Y. Chi. Breaking the sample complexity barrier regret- optimal model-free reinforcement learning. Advances in Neural Information Processing Sys- tems, 34, 2021.
[41] G. Li, I.. Shi, Y. Chen, Y. Chi, and Y. Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.0522 2022.
12

---

[42] M. L. Littman. Markov games framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[43] Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010, 2021.
[44] W. Mao and T. Başar. Provably efficient reinforcement learning in decentralized general-sum Markov games. Dynamic Games and Applications, pages 1-22, 2022.
[45] L. Matignon, L. Jeanpierre, and A.-I Mouaddib. Coordinated multi-robot exploration under communication constraints using decentralized markov decision processes. In Tiveny-siith AAAI conference artificial intelligence, 2012.
[46] W. Mou, C. Li, M. J. Wainwright, L. Bartlett, and M. I. Jordan. On linear stochastic ap- proximation: Fine-grate fine-grained arXiv:2004.0m 04719, 2020.
and non-asymptotic concentration. arXiv preprint
[47] H. Moulin and J.-P. Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3):201- 221, 1978.
[48] J. Nash. Non-cooperative games. Annals of mathematics, pages 286-295, 1951.
[49] J. F. Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-44 49, 1950.
[50] A. Ozdaglar, M. O. Sayin, and K. Zhang. Independent learning in stochastic games. arXiv preprint arXiv:2111.11720 2021.
[51] A. Pananjady and M. J. Wainwright. Instance-dependent -bunnds for policy evaluation in tabular reinforcement learning. IEEE Transactions on Information Theory, 67(1):566-585 2020.
[52] J. Perolat, B. Scherrer, B. Piot, and O. Pietquin. Approximate dynamic programming for two- player zero-sum Markov games. In International Conference on Machine Learning, pages 1321-1329. PMLR, 2015.
[53] A. Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In Annual Symposium on Foundations of Computer Science (FOCS), pages 258-265, 2016.
[54] M. Sayin, K. Zhang, D. Leslie. T. Basar, and A. Ozdaglar. Decentralized Q-learning in zero- sum Markov games. Advances in Neural Information Processing Systems, 34, 2021.
[55] S. Shalev-Shwartz. Online learning: Theory, algorithms, and applications. 2007.
[56] S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@
in Machine Learning, 4(2):107-194, 2012.
[57] Shalev-Shwartz and Y. Singer. A primal-dual perspective online learning algorithms. Machine Learning, 6952)115--14,, 2007.
[58] S. Shalev-Shwartz, S. Shammah, and A. Shashua. Safe, multi-agent, reinforcement learning for autonomous driving, arXiv preprint arXiv:1610 2016.
[59] I.. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[60] A. Sidford, M. Wang, X. Wu, L.. Yang, and Y. Ye. Near-optimal time and sample complex- ities for solving Markov decision processes with generative model. In Advances in Neural Information Processing Systems, pages 5186-5196, 2018.
[61] A. Sidford, M. Wang. X. Wu, and Y. Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. In Symposium on Discrete Algorithms, pages 770-787. SIAM, 2018
13

---

[62] A. Sidford, M. Wang, L. Yang, and Y. Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intel- ligence and Statistics, pages 2992-3002. PMLR, 2020.
[63] Z. Song, S. Mei, and Y. Bai. When can we learn general-sum Markov games with a large number of players sample-effccientyy arXiv preprint arXiv:2/ 10.04/84, 2021.
[64] Y. Tian, Y. Wang, Yu, and S. Sra. Online learning in unknown markov games. Interna- tional conference machine learning, pages 10279-10288. PMLR, 2021.
[65] S. Vaswani, L. F. Yang, and C. Szepesvári. Ncar-optimal sample complexity bounds for con- strained MDPs. arXiv preprint wwXiv:22060062777 2022.
[66] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, Chung, D. H. Choi, R. Powell, Т. Ewalds, and P. Georgiev. Grandmaster level in Starcraft II using multi-agent reinforcement learning. Nature, 575(7782)3350-354, 2019.
[67] M. Wainwright. Stochastic approximation with cone-contractive operators: Sharp fxo bounds for Q-learning. arXiv preprins arXiv:1905.0626; 2019.
[68] M. J. Wainwright. Variance-reduced Q-learning is minimax optimal. arXiv preprini arXiv: 2019.
[69] B. Wang, Y. Yan, and J. Fan. Sample-efficient reinforcement learning for linearly- parameterized mdps with generative model. Advances in Neural Information Processing Systems, 34, 2021.
[70] C.-Y. Wei, Y.TT. Hong, and C.-J. Lu. Online reinforcement learning in stochastic games. Ad- vances in Neural Information Processing Systems, 30, 2017.
[71] C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Last-iterate convergence of decentralized op- timistic gradient descent/ascent in horizon competitive Markov games. Conference on Learning Theory, pages 4259-4299, PMLR, 2021.
[72] G. Weisz, P. Amortila, and C. Szepesvári. Exponential lower bounds for planning in MDPs with rincarly-eealizablee optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
[73] Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultancous-move Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages
PMLR, 2020.
[74] Y. Yan, G. Li, Y. Chen, and Fan. Model-based reinforcement learning is minimax-optimal for offline zero-sum markov games. arXiv preprint 2xXi:22006040444, 2022.
[75] L. Yang and M. Wang, Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004, 2019.
[76] Y. Yang and C. Ma. o(t-)) convergence of oggimnstc--oloov..l--eeellrleeed in two- player zero-sum markov games. arXiv preprint arXiv:2209. 2022.
[77] A. Zanette, M. J. Kochenderfer, and E. Brunskill. Almost horizon-free structure-aware best policy identification with generative model. Advances in Neural Information Processing Systems, 32, 2019.
[78] A. Zanette, A. Lazaric, M. J. Kochenderfer, and Brunskill. Provably efficient reward- agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 1756-11766. 2020.
[79] K. Zhang, S. Kakade, T. Basar, and Yang. Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances Neural Information Processing Sys- tems, 33, 2020.
14

---

[80] K. Zhang, Z. Yang, and T. Başar. Multi-agen reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[81] R. Zhang, Q. Liu, H. Wang, C. Xiong, N. Li, and Y. Bai. Policy optimization for Markov games: Unified framework and faster convergence. arXiv preprint arXiv:2206. 026400 2022.
[82] Y. Zhao, Y. Tian, J. D. Lee, and S. S. Du Provably efficient policy gradient methods for two-player zero-sum Markov games. arXiv preprint arXiv:2102.08900 2021.
[83] H. Zhong, W. Xiong, Tan, L. Wang. T. Zhang, Z. Wang, and Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. arXiv preprint arXiv:2202.07511, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contri- butions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This is theoretical work that we do not foresee any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experimental results (cither in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were cho- sen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments mul- tiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 'e us-
ing/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable infor- mation or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "zX2wog4Q9MX", "reviewer": "Reviewer_1o3R", "summary": "This work focuses on closing the sample complexity gap in learning two-player zero-sum Markov games. With previous results suffering either the curse of multi-agent or a loose horizon-dependency, this work breaks both barriers simultaneously in the setting of a generative model and approaches the optimal rate up to logarithmic factors. The algorithm design benefits from two core ideas: the optimism to tackle the uncertainty of the environment and the adversarial learning (FTRL in particular) to overcome the non-stationary environment from each player's perspective. The core technique that contributes to the tight sample complexity is the data-driven Bernstein-style bonus.", "questions": "**I am overall very satisfied with this work. The following questions are more from my own curiosities.**\n- [27] mentions that its result is loose due to two reasons (see the illustration below their Thm 4). One reason is the incremental update and use of the learning rate therein. Another reason is that [27] did not have a variance-aware analysis. The improvement over the second point is clear in this work. I am wondering how this work addresses the first point. Especially, is the generative model alleviate the first point directly? Or the learning rate chosen in this work (different from which in [27]) plays a critical role?\n- Regarding the variance-aware design, I noticed that it is considered in both the confidence-bound design and the learning rates for FTRL (i.e., $\\eta$). I am wondering about the reason for each individual consideration. Hopefully, the authors can give some intuitive explanations.\n- Additionally, for the confidence bound, the update of the Q value and the V value uses two different confidence bounds. They share similar formats but it will still be helpful if the authors can illustrate their relationships. \n- Another question regarding this work and [27] is that the output policy in [27] is typically non-Markovian, I am wondering whether the authors can give some illustration on why this work can output a Markov policy. I did not find much emphasis on this point and wonder whether there is any particular reason that outputting a Markov policy is straightforward in this work.", "limitations": "Yes, the authors have addressed the limitation of this work and there is no major negative societal impact given its theoretical nature.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- (S) While many advances in learning in MGs have been made in recent years, how to achieve the optimal sample complexity remains open even in the \"simplest\" case of two-player zero-sum games and generative models, as considered in this work. The progress of this work largely contributes to a deeper understanding of this problem and should inspire future works.\n- (S) The techniques utilized in this work nicely improve previous ones. While optimism and adversarial learning in MG have been investigated in MGs [27], this work nicely spots that the looseness of the previous result is due to the failure of considering variance-type bounds. While similar ideas of using Bernstein-type bounds to sharpen the horizon-dependency are philosophically well-recognized in RL, this work still skilfully implements it in the context of MGs and combines it with adversarial learning.\n- (S) While this work is heavy in theory, the major design intuitions are given and the results are illustrated clearly, which is a joy to read.\n- (S) The tools developed in this work, especially the variance-type bound for FTRL should be of independent usage and may benefit other studies beyond MGs.\n- (W) If have to say something about weakness, the design idea of this work is similar to that of [27] although this work successfully incorporated the variance-type analysis (which is lacking in [27]). Also, the assumption of the generative model is somewhat limited. However, I still believe that compared with [27], sufficient contributions are made even assuming the generative model.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WUYY-QZgR3K", "reviewer": "Reviewer_H3Nw", "summary": "This paper studies the problem of finding the Nash equilibria in two-player zero-sum Markov games with a generative model. The authors established a minimax optimal sample complexity in this setting.\n", "questions": "1. The previous method (V-learning) only updates V functions and thus breaks the curse of multiagents. So I am curious about that why the proposed algorithm, which updates Q functions, can break the curse of multiagents.\n\n2. Because the proof is too long, I did not read the proof in its entirety. Can the authors briefly describe the general idea of ​​the proof? I also encourage the authors to add a proof sketch. \n\n3. I hope the authors make more comments on why this method cannot be applied to the online setting.\n\nI will consider increasing the score if the authors can address the above concerns.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " I think this problem is very interesting for the RL committee. But perhaps for too technical reasons, the paper is hard to follow. I hope the authors can make more comments to make the paper clearer. See the questions below for details.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0CqTjIZa62m", "reviewer": "Reviewer_VUwp", "summary": "This paper provides a new algorithm for learning a Nash equilibrium in a zero-sum Markov game and proves that the sample complexity is much tighter than in the previous works, in a sense that the bound is nearly optimal.", "questions": "None.", "limitations": "The limitations have been stated clearly in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The algorithm and the theoretical results seem novel and appealing. As stated in the paper, it is proven that the proposed algorithm overcomes (i) the curse of multiple agents, and (ii) the curse of horizon. The results seem sound and significant.\n2. The paper is well structured and well written. The notation is clear and easy to follow.\n\nWeaknesses:\n1.  The \"main results\" section is short, and the theoretical results are not explained clearly. How do we get to Theorem 1? Since this is a theoretical paper, I think an outline of the proof is needed here to help the readers to get the idea quickly.\n2. Eq. (27) makes sense to me. However, it is a bit risky to say that the bound proven in the paper is \"nearly improvable\" without proof.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept