When are Offline Two-Player Zero-Sum Markov Games Solvable?
Authors: Qiwen Cui
Simon Shaolei Du
Venue: NeurIPS 2022 Accept (2022)
Keywords: zero-sum Markov game
offline reinforcement learning
reinforcement learning theory

Abstract: We study what dataset assumption permits solving offline two-player zero-sum Markov games. In stark contrast to the offline single-agent Markov decision process, we show that the single strategy concentration assumption is insufficient for learning the Nash equilibrium (NE) strategy in offline two-player zero-sum Markov games. On the other hand, we propose a new assumption named unilateral concentration and design a pessimism-type algorithm that is provably efficient under this assumption. In addition, we show that the unilateral concentration assumption is necessary for learning an NE strategy. Furthermore, our algorithm can achieve minimax sample complexity without any modification for two widely studied settings: dataset with uniform concentration assumption and turn-based Markov games. Our work serves as an important initial step towards understanding offline multi-agent reinforcement learning.

When are Offline Two-Player Zero-Sum Markov Games Solvable?
Qiwen Cui
Simon S. Du
Paul G. Allen School of Computer Science
Paul G. Allen School of Computer Science
Engineering
Engineering University of Washington ssduêcs esdu@cs.washingtorr washington.
University of Washington
qwcui@cs. washington.
Abstract
We study what dataset assumption permits solving offline two-player zero-sum Markov games. In stark contrast to the offline single-agent Markov decision pro- cess, we show that the single strategy concentration assumption is insufficient for learning the Nash equilibrium (NE) strategy in offline two-player zero-sum Markov games. On the other hand, we propose a new assumption named unilat- eral concentration and design pessimism-type algorithm that is provably efficient under this assumption. In addition, we show that the unilateral concentration as- sumption is necessary for learning NE strategy. Furthermore, our algorithm can achieve minimax sample complexity without any modification for two widely studied settings: dataset with uniform concentration assumption and turn-based Markov games. Our work serves as an important initial step towards understand- ing offline multi-agent reinforcement learning.
Introduction
Promising empirical advances have been achieved in reinforcement learning (RL., including mas- tering the game of Go [Silver et al., 2016), Poker [Brown al., 2017], real-time strategy games [Vinyals et al., 2019] and robotic control [Kober et al., 2013]. Notably, many of these successes lie in the domain of multi-agent reinforcement learning (MARL). MARL is about multiple agents interacting in a shared environment, and each of them aims to maximize its own long-term reward. During the learning process, each agent not only needs identify the environment dynamic but also needs to compete/cooperate with other agents. One important subarea of MARL is offline MARL. In many practical scenarios, we only have access to the offline data it too expensive to frequently change the policy [Zhang et al., 2021a]. While there are plenty of empirical works on offline MARL [Pan al., 2021, Jiang and Lu, 2021], the theoretical understanding is still very limited. In this work, we take an initial step towards understanding when offline MARL is provably solvable.
We consider two-player zero-sum Markov games, where two players simultaneously select actions over multiple time steps in a Markovian environment and the first player aims to maximize the total reward while the second player aims minimize it. In the offline setting, we have access fixed dataset collected by (possibly unknown) exploration policy and the target is to find (near-)Nash equilibrium (NE) strategy of the underlying two-player zero-sum Markov game.
One of the main difficulties offline RL distribution shift, i.c., the dataset distribution different from the distribution induced by the optimal policy. It is important to understand what is the minimal dataset distribution assumption that permits offline RI. For single-agent offline RI, is shown that the pessimism principle allows policy optimization with single policy concentration, i.e. the dataset only covers the optimal policy [Jin et al., 2021b, Zanette et al., 2021, Yin and Wang, 2021, Rashidinejad al., 2021]. This assumption is necessary is impossible learn the optimal
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

policy if it is not covered by the dataset. However, the dataset coverage assumption for MARL is still far from clear. In this work, we want answer the following question:
What is the minimal dataset coverage assumption that permits learning an NE strategy in offline two-player zero-sun Markov games?
Generally speaking, MARL is much more difficult than single-agent RL due to the following two reasons. First, MARL known to suffer from the non-stationary property, i.e. agents will affect the others during the learning process [Zhang al., 2021a]. Specifically, the performance may decline each agent simultaneously tries to improve its own policy depending on others' current policies. In addition, multiple agents incur complicated statistical dependence that makes the theoretical analysis difficult. A line of works study Markov games with online sampling oracle [Bai et al., 2020, Bai and Jin, 2020, Liu al., 2021] or generative model oracle [Sidford et al., 2020, Zhang et al., 2020, Cui and Yang, 2020], where specialized techniques are developed to tackle the above difficulties. In this paper, we give the first analysis on offline Markov games in the fundamental tabular setting.
1.1 Main Contributions
First, we propose an assumption named unilateral concentration, which posits that for all strategies 14, v, strategy pairs (n* 2)) and (J, v²) are covered by the dataset, where ja is the strategy for the first (max) player, is the strategy for the second (min) player, and (μ² ,²)) is an NE strategy. In Section 3, we prove that NE strategy is not learnable even if this assumption is only slightly violated. The intuition behind the hardness result is that identify an NE strategy, the algorithm has to compare it with strategy pairs that one player uses any other strategies as reference. This result also implies that the single strategy concentration, which is sufficient for offline single-agent RL, is not sufficient for offline MARL.
Second, we provide positive results showing that NE strategy is PAC learnable under the unilat- eral concentration assumption. Combined with the hardness results above, we conclude that uni- lateral concentration assumption is the necessary and sufficient dataset coverage assumption for solving offline zero-sum Markov games. Our algorithm is based on the pessimism principle that we maintain pessimistic estimates for both players, respectively. We show that our algorithm achieves
Õ(V CABHH33 performance gap under unilateral concentration assumption, where C* quan- tifies the coverage of the dataset, S is the number of states, A is the number of the max player's s actions, B the number of the min player's actions, H the horizon and n is the number of samples.
Third, we show that our algorithm is minimax optimal when the dataset satisfies stronger as- sumption, uniform concentration, or the Markov game is turn-based. These are two widely studied settings in the RL community. Uniform concentration assumes that all state-action pairs are covered by the dataset and surn-based Markov game is a variant of zero-sum Markov games where two play- ers select actions in turns instead of simultancously. Although uniform concentration is about the dataset structure and turn-based Markov games are about the environment structure, our algorithm can adapt to both of them without any modification and achieves minimax sample complexity.
Main Techniques. Our algorithm is motivated by the Bernstein-type bonus and reference advantage function techniques in Xie et al. [2021b] while we make novel adaptations, namely monotonic up- date and a self-bounding technique, to realize them in Markov games. The Monotonic update allows sandwich-type argument that bounds the reference function and further bounds the variance term. The bof-ddunn technique is utilized to bound the performance gap by itself and then solve the inequality derive the final bound on performance gap.
To summarize, (1) we identify the minimal dataset coverage assumption that allows learning the NE strategy in Markov games; (2) we propose pessimism-basee algorithm that achieves polynomial sample complexity based on novel Markov game techniques; and (3) we further show the algorithm is minimax optimal under the uniform concentration assumption in turn-based Markoy games.
1.2
Related Work
Here we focus the theoretical works on two-player zero-sum Markov games and offline RL.

---

Two-player zero-sum Markov games. Zero-sum Markov games have been widely studied since the seminal work [Shapley, 1953]. When the transition kernel is unknown, different sampling oracles are utilized to acquire samples, including online sampling [Bai and Jin, 2020, Xie et al., 2020a, Liu et al., 2021, Bai al., 2020, Jin al., 2021a, Song et al., 2021], generative model sampling [Sidford et al., 2020, Cui and Yang, 2020, Zhang et al., 2020, Jia et al., 2019]. For offline sampling oracle, Zhang et al. [2021b] and Abe and Kaneko [2020] consider decentralized algorithm with network communication and offline policy evaluation, both under the uniform concentration assumption. One concurrent work [Zhong et al., 2022] considers zero-sum Markov games with linear function approximation. They also show the single policy coverage is not sufficient and propose similar unilateral concentration assumption under which they give a provably efficient algorithm. On the other hand, under the unilateral concentration assumption, their sample complexity is worse than ours when specialized to tabular setting because they did not use Bernstein bonus. They show is impossible learn in all instances without unilateral concentration. However, they do not show that any assumption weaker than unilateral concentration makes learning impossible, which is a negative result proven in our paper. Lastly, our algorithm is minimax optimal for uniform concentration setting and turn-based Markov games while their algorithms are not.
Offline single-agent RL. Theoretical amalysis of offline RL can be traced back to Szepesvári and Munos [2005], under the uniform concentration assumption (analogue to Assumption 2.3). This assumption has been extensively investigated [Xie and Jiang, 2021, Xie et al., 2020b, Yin et al., 2020, 2021, Ren et al., 2021]. Recently, a line of works showed that the pessimism principle allows offline policy optimization under a much weaker assumption, single policy concentration, both in tabular case and with function approximation [Rashidinejad et al., 2021, Yin and Wang, 2021, Xie al., 2021b, Jin et al., 2021b, Uehara and Sun, 2021, Uehara et al., 2021, Zanette et al., 2021, Xie et al., 2021a]. One closely related work is Xie et al. [2021b], which utilizes the reference advantage function technique and Bernstein-type bonus to show minimax sample complexity Ö(SC* H3 /n) in finite-horizon MDP. We show that the counterpart of single policy concentration in zero-sum Markov games is insufficient for NE strategy learning and use the pessimism principle to design algorithm that works under the unilateral concentration assumption.
Preliminaries
2.1 Two-Player Zero-sum Markov Games
Zero-sum Markov games (MG) generalize single-agent MDP to two-agent case where one agent aims to maximize the total reward while the other one aims to minimize it. A tabular finite-horizon zero-sum Markov game is described by the tuple g = (S,A, B, P, r, H), where S is the state space, A is the action space of the first (max) player, B is the action space of the second (min) player, P = (P1, P2, Pn).. Ph. E R|SILA||B) vh E [H] is the (unknown) transition probability matrix for time step h, r (2,, .H.. terministic reward vector and H is the horizon length.' This paper focuses on the tabular setting where [8).1_A).am [B] are finite. At each timestep h and state 5h. if the max player chooses action an and the min player chooses action 6,. then the next state at timestep h + 1 follows the distribution Sh+11 P Sh, an. by) and both players receive a reward (sh, an, bn). Both players sequentially choose H actions and at each timestep, the action is chosen simultaneously and then it is revealed to both players. We assume that we have fixed initial state $1 and it is straightforward to generalize our results to the case where the initial state is sampled from a fixed distribution."
Yh E [H] is the (unknown) de-
Turn- based Markov games are an important subclass of (simulraneous-move Markov games, where the max player takes action first and the min player can take action after observing the opponent's action. It is widely studied setting [Sidford et al., 2020, Cui and Yang, 2020, Bai and Jin, 2020] and we will provide minimax sample complexity result for this setting in Section 4.3.
We denote a strategy pair as π = (H, where f (Hr P2, , MH ) pA S + A vh E [H] is the strategy of the first player and / = (21 1/2, .HH,, v/ : > A vh E [H] is the strategy of
"It is straightffrward to generalize ing the transitions rather than learning the rewards.
results stochastic rewards because the major difficulty is in learn
'Stochastic initial state is equivalent to an MDP with deterministic initial state by creating a dummy initial state which transits the next state following that initial state distribution.
3

---

the second player, where A is the probability simplex on the finite set X. A deterministic strategy strategy that maps state single point distribution. We define the state value function and state-action value function for strategy pair ι similarly as in single-agent MDP:
H
H
V/ (8h) = E
r(st oz, 84 8h (sh On; bn. = E Σ
Σ rss,, at bT) Sh, On by
the second player's 's strategy v is fixed, then the MG degenerates to an MDP and we call the optimal policy in this MDP the best response strategy br, (v). Similarly, best response for the second player. We will ignore the subscript in br and br2 when it is clear in the context. While the best response may not be unique, the best response value is always unique. For all h E {H)), 8h E S, we define
define the brz(p) as the
V (s%) (
max A ( (8%), V!!. (5%) -/ V/t.brlu) (5%) min V/ Vi (8h)-
It is well known that Nash equilibrium (NE) strategy n' = """","), i.e., a strategy pair such that no player can benefit from switching its own strategy, exists for zero-sum Markov games with a unique value function [Shapley, 1953J. In other words, je and v" are the best responses to each other. We define Vi Ve .²' for all h [H]. The following weak duality property holds for all strategy pairs (1,v) in MG:
h S V/ S V
h wh E [H].
For strategy pair π = (H, v), we can then define the corresponding duality gap as
Gap(z) (s) (7*((ss))
The duality gap is always non-negative and the NE strategy has zero duality gap Gap(#") = 0. Duality gap measures how well a strategy pair approximates the NE. We say a strategy pair an e-approximate NE if Gap(z) S.
2.2 Offline Two-Player Zero-Sum Game
In offline RL., we given an offline dataset D (sh, 07, by. rh, (1+1))eejn
kejW) and we cannot do any further sampling [Kakade, 2003]. We assume that the dataset is sampled from some exploration policy p (p1. P2. P.), Ph : S + A wh E [H] The target of offline MG is to find an approximate NE with small duality gap by utilizing the given dataset D. We use di (s, a, b) to denote the probability of s, a, b appears at timestep h in the trajectory generated by strategy for all E [ The dataset distribution df, (s, a, b) defined similarly.
state-action pair (s, a, b) at
timestep h is covered by strategy π if and only if dz (s, a, b) > 0. Strategy π is covered by dataset generated by exploration strategy p if and only if for all (s, a, b) covered by æ, it covered by p. In other words, we have
di as, oo, Vh E [H), e as,
(1)
The sample complexity guarantee will depend on this ratio.
Dataset Coverage Assumptions. Below we list three different dataset coverage assumptions for Markov games.
Assumption 2.1. (Single strategy concentration) One NE strategy (4", is covered by the dataset.
Assumption 2.2. (Unilateral concentration) For all strategies y and v, (1,2²) and (H²", v) are cov-
ered by the dataset, where (μ²,, v²) is one NE strategy.
Assumption 2.3. (Uniform concentration) For all E [H] and (s, (s, E S x A x B, (s, a, b) at timestep h is covered by the dataset.
Assumption 2.1 is the weakest assumption and is the most straightforward extension of the single policy concentration in single-agent RL [Rashidinejad et al., 2021]. Assumption 2.3 generalizes the uniform policy concentration in single-agent RL [Yin et al., 2020J. Assumption 2.2 is sandwiched
For simplicity we assume the exploration policy is Markovian. However, our analysis can be directly generalized to arbitrary dataset distribution. See Jin et al. [2021b] for discussions depesett bounds.

---

by Assumption 2.1 and Assumption 2.3 as Assumption 2.2 implies Assumption 2.1 and Assump- tion 2.3 implies Assumption 2.2. In this work, we will show that Assumption 2.2 the minimal dataset coverage assumption that allows NE learning and we provide sample complexity bounds that depends on the density ratio (1).8
Notations. We use Varp(s.a.b) (V) to denote the variance of the random variable (s'' where s' ~ P(-|s, a. b) and VVrr(V) E RSAB to denote a vector whose (s, a, b) component is Var (V). We define a V := max(a, b) and a A 6 == minfa, b}. In addition, if a is a vector and b is a scalar, the operation is taken on each element of a: [a b], at V b. For two vector a R", b E R", we use T E R to denote the element-wise division: [b_ au. In addition, if a is scalar, we still use E IR" to denote the element-wist division: [i] = a We use S, A, B to denote |S], [A], [8].
6
3 Impossibility Results
In this section, we show that assumption weaker than the unilateral concentration assumption (Assumption 2.2), which includes single strategy concentration (Assumption 2.1), allows learning the NE strategy. To begin with, we consider the deterministic unilateral concentration assumption. Assumption 3.1. (Deterministic unilateral concentration) For all deterministic strategy μ and v, (H, and (n* p) are covered by the dataset, where (μ", v²*) is one NE strategy.
Immediately we can tell that Assumption 3.1 is satisfied under Assumption 2.2. These two assump- tions are equivalent, which shown by Proposition 3.2, because any stochastic strategy can be viewed as combination of several deterministic strategies.
Proposition 3.2. If for all deterministic strategy I and v, (1,, v*) and (p", are covered by the dataset, then we have for all (possibly stochastic) strategy yl and v', (pl,v*) and (p", v/) are covered by the dataset.
For the hardness examples, we consider bandit games, i.c., Markov games with horizon H 1. The result can be generalized to arbitrary horizon by setting the reward to be 0 in horizons other than = 1. We consider class of bandit games and datasets such that Assumption 3.1 is almost satisfied while no algorithm can identify the NE strategy for all bandit games and datasets in this class. As Assumption 2.2 and Assumption 3.1 are equivalent, no assumption weaker than Assumption 2.2 allows NE strategy learning. A direct corollary is that single strategy concentration (Assumption 2.1) 1)ii is not sufficient for NE learning.
Theorem 3.3. Define class X of bandit game M and exploration strategy p that consists of all M and pairs satisfying that there exists at most one deterministic strategy or one deterministic strategy such that (H,v²) the density ratio is bounded
v²) or (je", ,D) is not covered and for all other deterministic strategies pl,,
di o (s, 2 + 2B, d,
di (s,a,b)
S 2A
d,
for all h [ For any algorithm ALG,, there exists (M, X such that the output of the algorithm ALG is at most a 0.25 0.25-approximate NE strategy no matter how many data are collected.
Proof. We consider bandit games with two actions for each player here. The action is A {az,ay for the first (max) player and B = {b2, bb) for the second (min) player. We construct the following two bandit games with deterministic rewards.
r(a1, b1) 0.25
r(an, b2) 0.5
r(ag, b1) = 0
r(az, b2) = 0.75
Bandit Game
Then the (unique) NE of the first bandit game is (a1,b) and the (unique) NE of the second bandit game is (a2, b2). Now we set the exploration strategy p to be uniform distribution on {(a1, b1), (01, b2), (a2, bz)}. We can verify that both bandit games with exploration strategy p is
'Note that there could be different minimal assumptions as the assumption set is partially ordered set. Here 'minimal' means Assumption 2.2 allows NE leamingg while no weaker assumption allows doing so.
5

---

r(a1, b1) r r(a, b1) = r r(az, b2) = 0.75
0.25
r(a1, b2) 0.5
Bandit Game 2
in the class defined in Theorem 3.3. Note that the dataset contains data on (#1, b1). (a1, b2), (az, b2) and no data on (a2, b1). It is impossible for algorithm to distinguish between these two bandit games as they are consistent on the given dataset and they all satisfy the dataset coverage assump- tion that only one action pair is not covered. With some calculations, we can show that the output of ALG is at most a a.p5-appro NE for one of the instances, which proves the theorem.
Remark 3.4. We can easily extend this instance to arbitrary action space by setting (as, by) for all i & {1,2), 2 E
(1,2), and (a: bz) = for all j & {1,2), i E (1,2), and the exploration strategy p be the uniform distribution on (a., by) such that (i,j) {(i.j)
[1, or j
{1,2}, (i, j) & 1)).
Remark 3.5. It is straightforward to verify that the hard instance in Theorem 3,3 also holds for turn- based Markov games. As result, no assumption weaker than Assumption 2.2 sufficient for NE learning in turn-based Markov games.
4 Provably Efficient Algorithm under Unilateral Concentration
In this section, we show that is indeed possible learn the NE with the unilateral concentration assumption. We propose novel algorithm called Pessimistic Nash Value Iteration (PNVI), which adapts the pessimism principle in single-agent RL to Markov games. Our sample complexity result depends on the following quantity named unilateral concentrability:
Definition 4.1. (Unilateral concentrability) For Nash equilibrium n², we define
" (s, (s a,,,,, d,
C= x =²= W²) (s..a...)).
min
max
By definition, C* is finite if Assumption 2.2 is satisfied. For the of the paper, nt denotes the Nash equilibrium that achieves the minimum here. Note that C* is not provided to the algorithm.
4.1 Hoeffding-type Algorithm with Data Splitting
To illustrate our main algorithm design ideas, we first propose algorithm with Hoeffding-type bonus and random data splitting. Given a dataset D { ah. bfg rhe st s)++)) n. k.h=1" we denote nA (s, a, b) Eh_ 1 ((sh; at, bb) (s, a, b)) to be the number of times that (s, a, b) is visited at timestep h. We set the empirical reward and the empirical transition kernel as
Ek=1 1 ((s) a
by = (s,a,b,s') Σ (( at. b7)) (s,a,b)
fn
b),
(2)
ny (s, a. 2 1, and (s, a, b) = o. (s a. a)b) = 1/S otherwise. In addition, we use n4 E RSAD to denote vector such that [nu]s.a,b ms, a,
Now we explain Algorithm in detail. First, we split the dataset into I/ small datasets {Dr} J with the same size. Then we use Dr to estimate the reward and the transition matrix at timestep h. The data splitting scheme is remove the dependence between each timestep. Then the value function is estimated via value-iteration-tyy algorithm. At each timestep, we maintain both opti- mistic and pessimistic estimates by adding/minusing a Hoeffding-tyy bonus. We use the following Hoeffding -tppe bonus:
H
by (Sh, an, bn.) = by (Sh, an, bn) = 41 Tep (s.
(3)
where + (ABB/)))))). Then we compute the pessimistic estimate Q and Q:
Qn (Th + (Ph. Mo+1)= 2.) vo, 1 (Th + (Pn Vn+z) + bn) A( - h + 1).
(4)

---

Algorithm Pessimistic Nash Value Iteration (PNVI)
Input: Offline dataset D {(sh,, aft bh, rh. + n.H
k Failure Probability 8.
Initialization: Set V H+1(+) V (-++(() O. Randomly split the dataset 'D into {Pa) with
[Pa] = n H. Set hh. Ph. in and on as (2) and (3) using the dataset Dn for all h E [M].
for time h H, H 1, ..... do
Set 2, (:) and Q (-.,)
(4).
Compute the NE of Q, (::))) as (1,, (,),)))))
Compute VA (-) Bang, b,y 2 (,
Compute the NE of Q (:,,,) as (14, (.))..)
Compute V.(+) = E Ba-Ta bnv (: a.
end for
Output / 122"""1""" 14 v= (1), 02, ,H), (VA)EE (Va)
Pessimistic estimate Qg is for the max player, which mimics the pessimism in single-agent RL. Qn using a positive bonus is for the min player, which is also kind of pessimism as the min player's target is to minimize the reward. We compute the NE strategy of the matrix game Q(s...) and
(ss, --) respectively and use the NE value to be the state value ((s) and (s).. Note that we only solve a zero-sum matrix game, which computationally efficient [Chen and Deng, 2006].
Remark 4.2. If we compute an eNB/ H-approximate NE of the matrix game Q(a,;,) and (88,;.)
at each timestep, then the performance gap will only be enlarged by Ō(ENE).
Theorem 4.3. Suppose Assumption 2.2 holds. For any 0 5 and strategy p. with probability 1 - 8, the pessimistic values Vn, and V of Algorithm satisfy
= (sh) V. (sw)) & (VVC-SABH .
-Ey..- [V((sa) - VE (sn)) S (VC'
for all h E [H), where 8h. is sampled from the trajectory following the strategy in the expectation.
Proof Sketch. For simplicity, only show the guarantee for the strategy j of the max player. First, we show that under good concentration event, the pessimistic value V,, is always smaller than the best response value of μ, i.e.
E & S. (s) (*) (s)
Second, we show that the performance gap of μ bounded by the expected sum of bonus under the strategy μ², i.e.
(s) V/ (8) (s)) VI (sn)
(s S 22
Σ (, at b.)lsh
Le
Finally, we define a concatenated strategy v/ = (V),-.. Ph-1,kmo"" Mx) and then we have
Ex [VT [sh)] S 2E
> Le( by).
As Assumption 2.2 suggests that (u",)") is well covered by the exploration strategy p. the expected sum of bonus can be bounded. See Appendix B for details.
Theorem 4.3 provides polynomial bounds on the error of the value estimates in Algorithm 1. can directly imply the following performance gap bound. In addition, it provides guarantees for the reference function that will be utilized in the next section.
Corollary 4.4. Suppose Assumption 2.2 holds. For any policy π (11, U) of Algorithm 1 satisfies Gap(T) < ( (VC*SABH+/n)
8 < 1, with probability 1-8, the output
Theorem 4.4 shows that the output strategy of Algorithm 1 is an θ (VC' -aprrxximate
NE, The parameter C* measures how the exploration strategy p covers the unilateral strategies (n",, p) and (n, v²) for all μ and v.
7

---

4.2 Bernstein-type Algorithm with Reference Advantage Function Decomposition
In this section, we will derive an improved performance gap bound Ō ( (VCSS/B///)) The extra H shaved by using Bernstein-type bonus and reference advantage decomposition technique motivated from Xie et al. [2021b]. However, we want emphasize that zero-sum Markov games are substantially different from MDP and require novel adaptation, which we will describe later.
Due to the space constraint, we put Algorithm 2 in Appendix A. Algorithm is different from Algorithm two aspects. First, we use the reference advantage decomposition
remove an H factor. The dataset is split into three subset with equal size Dref, Do. D1, and DD is further split into H subset with equal size (Dr.1 h=1- We run algorithm on dataset Dref and we can obtain pessimistic value estimate Yee and ref with guarantees by Theorem 4.3, Then we use dataset Do to estimate Ps Voo and dataset 1 to estimate Pv Vh+1). Second, we use a Bernstein-tye bonus to remove another H factor. Our updating formulas of Q, and Qn are
Q = 2 V [Fn, + (Pr.o Vief) -nno + (Pn,1
(Va+1 h+1 Vie bn (5)
0 = t A Fr. + (Pr.o h41) + on.p + (Pr.1 W4t1 Virel (++1) + bn,al,
where we truncate by the reference function ensure monotonic update that Q, and Q₁ are more
accurate pessimistic/opimissic estimate compared with the reference function 2xee and Q The bonus functions are defined as
Var An. (Vicf (it1)
Var Pr.o (Vhta)e
He. .n.o =c
H
bn.o =c
(7)
Aho V1
nao V1
nh.o V1
nhoo v
b =c Vara Pe.s (V
Var (V - Vitel
Hi
bb, =
1h,1 V1
Thh,1 v
10h11
71,,1
(8)
where c is some universal constant and Var Varp... (V), Var p.. (V), nh,0, uh,1 are all AA--dimension vectors and the operations element-wise.
Theorem 4.5. Suppose Assumption 2.2 holds. For any 0 < 8 < and n 2 C"SABH' with proba-
bility - 6, the outpul policy π = (n,, D) of Algorithm satisfies Gap(T) s Ō (VC*SABH>/) (
Remark 4.6. > SABH serves the burn-in cost, which is standard in the literature. See more detailed discussion Li et al. [2021].
Proof of Sketch. For simplicity only show the guarantee for the strategy μ of the max player. First we show that under good concentration event, the pessimistic value Vn, is always sandwiched by the reference value ree and the best response value of μl, i.c.,
(s) < (s) s V (s), Vh E [H],E
Second, show that the performance gap of μ bounded by the expected sum of bonus under the strategy 1="" i.e.,
H Σ
(it( - (s1) V (s)) VV, 2E 2
(sn an. bn) + bn, ( an bn)]
hm
Then we bound the first term by
H
Ey
Ls an kn) 0ō (
-K((s))
mm

---

where VVT""0 (s1) - Vi (81) is the square root of the term we want to bound. The second term can be bounded similarly. Finally solving the self-bounding inequality for Vi (s1) Vi (81) and have
Vi V (s1)
11"h
(s1) -V S = (VC
We utilizes Theorem 4.3 to provide guarantee for the error of the reference function and Vx (s) I (s(s) - Vi"" (s) bound the variance of the estimation error. See Appendix C for details.
As MDP are degenerated Markov games with one player having fixed action, Markov games inherit the lower bounds of MDP. Comparing with the lower bound ? (VC*SH3/n) [Xie et al., 2021b], our bound already tight in C", S, H. The extra AB factor from the Cauchy-Schward inequality and the fact that the NE of zero-sum Markov games can be mixed strategy while deterministic optimal policy always exists for MDP. is unknown whether the AB factor is removable and we leave it to future work.
4.3 Minimax Optimal Sample Complexity Bounds
In this section, we show that Algorithm 2 directly adapts to two popular settings, i.e. Assumption 2.3 (uniform concentration assumption) and turn-based Markov games. In addition, minimax sample complexity can be achieved under both settings. The proof is deferred to Appendix D.
Theorem 4.7. Sel dm min {dh (s, a, b)
[H], (8, (8,,,,)) E S x A x BJ. Suppose Assumption 1 and n 2 H-///, /dmm with probability - 6, the output policy π = (H. v)
2.3 holds. For any
of Algorithm 2 satisfies Gap(T) & Ō (VH3/(md.
This bound has no explicit dependence on AB because the Cauchy-Schwarz, inequality can be applied di instead of vdk (See the proof of Theorem D.1). As the lower bound á ((HH/(ndm)) for MDP [Yin and Wang, 2021] is the lower bound for Markov games, Algo- rithm 2 achieves minimax sample complexity under assumption 2.3.
Theorem 4.8. Suppose Assumption 2.2 holds for a turn surn-based Markov games. For any < and 2 C SH*, with probability 1 - 8, the output policy = (H.D) of Algorithum 2 satisfies Gap(T) S δ (VC*SH*IM)
As the lower bound is á ( (VC-S13/n) [Xie et al., 2021b], Algorithm 2 can achieve the minimax sample complexity for turn-based Markov games under assumption 2.2. The difference is due to tum-based Markov games always have pure NE strategies (See the proof of Theorem D.6).
5 Conclusion
In this work, we study the minimal dataset coverage assumption for NE learning in two-player zero- sum Markov games. We show that single strategy concentration not enough for NE learning. Instead, find a minimal coverage assumption for NE learning and design algorithm with sample complexity tight in C*, S, H under such assumption based on novel techniques. In addition, the algorithm can achieve minimax sample complexity in certain settings. We believe this work can shed new light on offline MARL.
Here we list several open problems for future work. One direction is to find the minimax sample complexity of offline Markov games under the unilateral concentration. Importantly, it is unclear whether AB factor can be reduced [Bai et al., 2020]. Another direction is to design efficient algo- rithms for offline MARL with large number of agents without sample complexity scales exponen- tially with the number of agents.

---

Acknowledgements
This work was supported in part by NSF CCF 2212261, NSF IIS 2143493, NSF DMS 2134106, NSF CCF 2019844 and NSF IIS 2110170.
References
Kenshi Abe and Yusuke Kaneko. Off-policy exploiaaility-cvaluttioo in two-player zero-sum markov games. arXiv preprint arXiv:2007.02141, 2020.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national Conference on Machine Learning, pages 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. arXiv preprint ar arXiv:2006.12007 2020.
Noam Brown, Tuomas Sandholm, and Strategic Machine. Libratus: The Superhuman Al for No- Limit Poker. In IJCAI, pages 5226-5228, 2017.
Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS(06), pages 261-272. IEEE, 2006.
Qiwen Cui and Lin F Yang. Minimax sample complexity for turn-based stochastic game. arXiv preprint arXiv:2011. 1.12677,1 2020.
Zeyu Jia, Lin F Yang, and Mengdi Wang. Feature-based q-learning for two-player stochastic games. arXiv preprint 1:Xiv:9906.044/ 00423, 2019.
Jiechuan Jiang and Zongqing Lu. Offline decentralized multi-agent reinforcement learning. arXiv preprint arXiv: 108.0/882.. 2021.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentral- ized algorithm for multiagent rl. arXiv preprint arXiv:2 10. 14555, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is Pessimism Provably Efficient for Offline RL? arXiv:2012. 15085 [cs, math, stat], May 2021b. URL http://arxiv oraeeiiiiorrreeeeeeee wrg.obggg/ao.... 2bs.2012. arXiv: 2012.15085.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey.
The International Journal of Robotics Research, 12(11))1238-1274 2013. Publisher: SAGE Publications Sage UK: London, England.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. arXiv preprint arXiv:0907.3740. 2009.
Ling Pan, Longbo Huang, Tengyu Ma, and Huazhe Xu. Plan better amid conservatism: Offline multi-agent reinforcement learning with actor rectification. arXiv preprint 1rXiv:2111.I1188, 2021.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism. arXiv:2103. /202/ [cs, math, stat), March 2021. URL http:://arxiii wwweiiivorrg//eo abs/2103 12021.
arXiv: 2103.12021
10

---

Tongzheng Ren, Jialian Li, Bo Dai, Simon S. Du, and Sujay Sanghavi. Nearly Horizon- Offline Reinforcement Learning. Stth:2103.14077 [cs, stat]. October 2021. URL http://ariiv. arg/abs/2105. 14077. arXiv: 2103.14077.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):
1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pages 2992-3002. PMLR, 2020.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George den Driessche, Julian Schrittwesser Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 10. 10.1038/nature 16661 URL attps://don org/ 10. 1038/ 1ww100/////ttt na9ure
2016. ISSN 1476-4687. doi:
Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum markov games with large number of players sample-efficiente
arXiv preprint arXiv:2110.04184, 2021.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Masatoshi Uehara and Wen Sun. Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage. arXiv:2107.06220 [cs, stat), October 2021. URL http://arxiv org/abs/ abs/ $107.06226 arXiv: 2107.06226.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation Learning for Online and Offline RL in Low-rank MDPs. arXiv:2110.0463 044.522222 [cs, stat], November 2021. URL http://arxiv. org/abs/2100 21622.11..0.16....111
arXiv: 10.04465..
Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathieu, Max Jaderberg, Wojeiech M Czarnecki, Andrew Dudzik, Aja Huang, Petko Georgiev, Richard Powell, and others. Alphastar: Mastering the real-time strategy game stareraft ii. DeepMind blog, 2, 2019.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultancous- move markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674 3682. PMLR, 2020a.
Tengyang Xie and Nan Jiang. Batch Value-function Approximation with Only Realizability. arXiv:2008. 04990 [cs, stat), June 2021. URL http://arxiv, httgg/bb/2000..000 arXiv: 2008.04990.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards Optimal Off-Policy Evaluation for Rein- forcement Learning with Marginalized Importance Sampling. arXiv: wttp:/906000999 [cs, stat], March 2020b. URL httt:://aree /ttp////rvvvvvv/ org/o/////o http:/b///19999 1906/ 03393. arXiv: 1906.03393.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances neural information processing systems, 34:6683-6694, 2021a
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. arXiv preprint 2021b.
Ming Yin and Yu-Xiang Wang. Towards Instance-Optimal Offline Reinforcement Learning with Pessimism. arXiv:21 10.00695 {es, stat), October 2021. URL http://aariiv..rr/aa//11... 08695. aivi 21 10.08695.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning. arXiv:2007.03700 [cs, stat], December 2020. URL http: /tat:i//rxxv.... org/aa//gooo abs/2007. 03760.
arXiv: 2007.03766

---

Ming Yin, Yu Bai, and Yu-Xiang Wang. Near- Near-Optimal Offline Reinforcement Learning via Double Variance Reduction. arXiv:2102.017 [cs. stat], February 2021. URL ittp://arxiv, orgz
arXiv: 2102.01748.
Andrea Zanette, Martin J. Wainwright, and Emma Brunskill. Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning. arXiv:2108.0881 [cs], August 2021. URL http:
// //arxiv.. org/ absaabssaaa 2208 08812. arXiv: 2108.08812.
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 rrXiv:2007.07461, 2020.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021a.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents. IEEE Transac- tions on Automatic Control, 2021b.
Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran 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
contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (c.g., code, data, models) 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 URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(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 to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wXntofXCrn1", "reviewer": "Reviewer_tuL7", "summary": "The paper proposes the unilateral concentration condition which provides a necessary and sufficient dataset coverage to learn an NE using offline methods. The paper proposes an algorithm that converges to an NE under these conditions and is minimax optimal.", "questions": "Q1: Would \"full concentration\" be a better term to use? \"Uniform\" seems to imply some sort of uniformity over policy or state space, but really it means full-support. Although, I suppose this term has been inherited from the single-agent RL community?\n", "limitations": "The main limitations \"uniform concentration\" or \"sequential Makov\" were clearly stated. Scaling factors is also discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Offline learning in multiagent domains is an important worthwhile area of study. Two-player zero-sum is an acceptable area to start.\n\nI found the first half of the paper well written. The second was difficult to follow (although my ignorance was a contributing a factor).\n\nSoundness:\n\nI am strongly convinced that the \"unilateral concentration condition\" claims are true. They seem intuitively true and the proofs are convincing.\n\nI am also convinced of the impossibility results.\n\nThe claims around the optimal offline algorithm are plausible. While I did not spot any errors in the proofs, the techniques used in this section are beyond my area of expertise and unfortunately the time constraints on reviewing did not allow me to fully grasp this section as thoroughly as I would have liked. I hope the other reviewers can vouch for the soundness of this section.\n\nComments:\n\nIt may be worth noting that the uniform concentration condition, while trivial, is not that uncommon in practice. For example, data generated using an epsilon-greedy strategy, common in value based methods, or policy gradient methods which are necessarily stochastic would generate data that is uniform concentration.\n\nRating:\n\nI will be willing to improve my rating if I felt more confident on the Section 4's soundness. I will remain open to other reviewers opinions on this matter and will be ready to improve my score with consensus. [Edit: consensus is that Section 4 is sound, improving my score from 4->6]\n\nMinor comment:\n* Line 25: “...two-players sequentially select actions…” - In Markov games players take actions simultaneously (over multiple time steps).", "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": "_Ilx5fWRZH1", "reviewer": "Reviewer_6SL9", "summary": "The paper studies the relevant offline MARL setting, which is relevant in practice, where only a small amount of data are given to the RL algorithm to infer a policy. The main contribution of the paper is to provide the necessary and sufficient assumption for learning a NE strategy in the offline Markov Game setting. This assumption is different from the one used in the single agent. In fact, in MDPs, the necessary assumption implies that one optimal policy is \"covered\" in the given dataset. However, in MGs, we need to see also the interaction between the NE policy and all the other agent's policies. \nAfter this result, the authors construct an algorithm based on pessimism that is provably efficient under this assumption. ", "questions": "See Weaknesses.", "limitations": "The paper is theoretical, so the main limitations are due to the applicability of the proposed method in practice.\n\n1. The state and action spaces are finite.\n2. The algorithm needs to compute at each step a NE for each state and time-step.\n3. The paper does not provide an experimental evaluation of the proposed algorithm. \n\nI think all of these limitations are reasonable since the main contribution of the paper is theoretical.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper, as far as I know, is the first one that tracts the offline zero-sum Markov Game problem.\n\n2. In the paper a necessary and sufficient condition for learning in offline zero-sum MG problems is given. The idea behind the proof is quite simple but, although the techniques used are not novel, the result is important for the ML community.\n\n3. The authors provide an algorithm that is provably efficient (although it does not match the lower bound in general).\n\n4. The paper is in general well-written and easy to follow. The authors spent space giving intuition about the different proof of the different theorems. I find this very helpful for a reader who does not want to read the full appendix.\n\nWeaknesses\n\nI think the paper has no important weaknesses. However, I list below the weaknesses.\n\n1. In the paper the authors prove that the Unilateral concentration assumption is the sufficient and necessary assumption to learn in offline MGs problem. However, the paper will become stronger if the authors would give some results that bound the approximation of the NE that the proposed algorithm can achieve when this assumption does not hold and when only the Single strategy concentration assumption holds. Do the authors have an intuition about it?\n\n2. Section 4.1 gives a first result when Hoeffding confidence intervals are used. However, the authors show that with Bernstein's confidence intervals they can improve the previous result. So, why do we need section 4.1? I suggest removing this section and putting in the main paper only Algorithm 2. Moreover, it is important that the reader does not have to go to the appendix to read the main algorithm.\n\n3. From sections 4.1 and 4.2, it is not clear what are the main challenges the authors faced to translate an offline RL algorithm to MGs. Could the authors list these technical challenges in their answer?\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": "V5GzH2L7Zh8", "reviewer": "Reviewer_wGFm", "summary": "This paper studies the learning of two player zero-sum Markov games from data. The results introduce a new condition \"Unilateral concentration\" which informally requires data of plays when one of the player follows a NE equilibrium. The authors show that this is necessary and sufficient condition for learnability. The authors provide a provable bound poly time algorithm under the condition, one weaker bound using Hoeffding inequality and another using empirical Bernstein bounds.\n", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The writing is clear and the results look solid to me. The proof sketches are helpful. I really did not find anything to complain other than few minor points that I state for a more rounded result. I must admit I am not very well versed in offline RL literature but the paper does a good job at comparing with related work.\n\nIt would have been good to have a few (even small) experiments - as the work is about learnability from data, it is surprising to not have any experiments.\n\nLittle better notation would make things easier to understand, especially for the variance of value function.\n\nThe second contribution in intro says \"necessary and sufficient dataset coverage assumption for solving offline Markov games\" it is important to be state zero-sum here - I know the paper title has zero-sum but this claim is broader.", "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": "GJ1tUql_bTa", "reviewer": "Reviewer_LCjP", "summary": "The paper proves a new assumption named unilateral concentration assumption as a necessary and sufficient dataset coverage condition for achieving optimal (NE) strategies in offline Markov game setting. A new Nash VI-based algorithm with pessimism is also proposed to achieve the minimax lower bound when the game is turn-based or under a stronger uniform concentration assumption. The results are novel and interesting with significant theoretical value.", "questions": "Is the sentence \"A direct corollary is that uniform concentration (Assumption 2.1) is not sufficient for NE learning.\" in Sec. 3 a typo? Assumption 2.1 is single strategy concentration.\n\nIn page 8 l260, the 'ref' subscripts are missed for reference function.\n\nFor data splitting scheme, is it the same as random sample without replacement for each timestep with a fixed sample buffer size? How will sampling with replacement affect the final results?", "limitations": "As is also noted by the authors, the remaining factor $AB$ in the bound of PNVI is unclear to be removable or not.\n", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has a clear description, arguments and proofs about the proposed assumptions and theorems. The motivation is clear. A sharper Bernstein bound is applied with a reference advantage technique from previous paper to make PNVI match the lower bound.\n\nFor the argument that no weaker assumption than unilateral concentration can ensure any algorithm to learn NE is true under the hypothesis that this is claimed for all games in the game class. And the proof is conducted by constructing a hard instance. However, from a more practical view, an assumption for a given game would allow a weaker assumption, since most games in the game class are not the hard instance. To this end, it would be interesting to see some weaker assumptions allowing existing any algorithm to learn NE for a certain game that is not hard instance. After all, the data coverage in practice is very hard to guarantee.", "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