Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus
Authors: Qiwen Cui
Simon Shaolei Du
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-agent reinforcement learning
offline reinforcement learning
reinforcement learning theory

Abstract: This paper considers offline multi-agent reinforcement learning. We propose the strategy-wise concentration principle which directly builds a confidence interval for the joint strategy, in contrast to the point-wise concentration principle which builds a confidence interval for each point in the joint action space. For two-player zero-sum Markov games, by exploiting the convexity of the strategy-wise bonus, we propose a computationally efficient algorithm whose sample complexity enjoys a better dependency on the number of actions than the prior methods based on the point-wise bonus. Furthermore, for offline multi-agent general-sum Markov games,  based on the strategy-wise bonus and a novel surrogate function, we give the first algorithm whose sample complexity only scales $\sum_{i=1}^m A_i$ where $A_i$ is the action size of the $i$-th player and $m$ is the number of players. In sharp contrast, the sample complexity of methods based on the point-wise bonus would scale with the size of the joint action space $\Pi_{i=1}^m A_i$ due to the curse of multiagents. Lastly, all of our algorithms can naturally take a pre-specified strategy class $\Pi$ as input and output a strategy that is close to the best strategy in $\Pi$. In this setting, the sample complexity only scales with $\log |\Pi|$ instead of $\sum_{i=1}^m A_i$.

Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus
Qiwen Cui
Simon S. Du
Paul G. Allen School of Computer Science
Paul G. Allen School of Computer Science Engineering
Engineering
University of Washington
University of Washington ssduêcs wwshington.
qwcui@cs washington. edu
Abstract
This paper considers offline multi-agent reinforcement learning. We propose the strategy-wise concentration principle which directly builds confidence interval for the joint strategy, contrast the point-wise concentration principle that builds a confidence interval for each point in the joint action space. For two two-player zero-sum Markov games, by exploiting the convexity of the strategy-wist bonus, we propose a computationally efficient algorithm whose sample complexity enjoys better dependency on the number of actions than the prior methods based on the point-wise bonus. Furthermore, for offline multi-agent general-sum Markov games, based on the strategy-wi wwie bonus and a novel surrogate function, we give the first algorithm whose sample complexity only scales Ex= A, where A, is the action size of the i-th player and m is the number of players. sharp contrast, the sample complexity of methods based on the point-wise bonus would scale with the size the joint action space I1 A, due to the curse multiagents. Lastly, all naturally take pre-specified strategy class II input and output a strategy that is close to the best strategy in II. In this setting, the sample complexity only scales with log II] instead of Σm As.
of our algorithms
Introduction
Multi-agent reinforcement learning (MARL) is about decision making in multi-agent system under uncertainty, which has achieved significant success solving a wide range of tasks such as GO [Silver et al., 2017], Poker [Brown and Sandholm, 2019] and autonomous deriving SShalev-Shwartz et al., 2016]. One standard setting in MARL is multi-player general-sum Markov games where each player deploys policy maximize its total reward while the evolution of the environment depends on the policies all the players [Zhang et al., 2021a]. During the learning process, each player needs identify the environment dynamics as well compete/cooperate with other agents.
One emerging subarea is offline MARL, where plenty of empirical works have been done while the theoretical understanding is still largely missing [Pan et al., 2021, Jiang and Lu, 2021, Meng et al., 2021]. Offline RL has received tremendous attention because in various practical scenarios, it is expensive to acquire online data while offline log data is accessible.
The offline single-agent RL well studied in the literature. Researchers have identified the minimal dataset coverage assumption, single policy coverage (the dataset only needs to cover an optimal policy), under which one can learn a near-optimal policy efficiently. Furthermore, they have developed algorithms with minimax sample complexity [Xie et al., 2021b, Li et al., 2022]. For offline MARL, recent works showed that single policy coverage is not sufficient and unilateral coverage is necessary for learning Nash equilibrium (NE) strategy, i.e., the dataset covers all the joint strategies that only differ from an NE at one player [Cui and Du, 2022, Zhong et al., 2022]. This condition is also
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sufficient for two-player zero-sum Markov games with sample complexity ((AB) (ignoring other quantities), where A, B are the number of actions for each player [Cui and Du, 2022]. However, is still unclear if it is sufficient for multi-player general-sum Markov game.
One major challenge in MARL is the curse of multiagents [Jin et al., 2021a]. Suppose the number of actions for player is A3 and there are m players. Then the joint action space is of size [[ Aj, which grows exponentially with the number of players m. As result, any algorithm that depends linearly on the cardinality of the joint action space can hardly be applied to real-world scenarios. In online MARL, Jin et al. [2021a] [a] and Song et al. [2021] show that finding the coarse correlated equilibrium, which is a weaker equilibrium notion than NE, only requires Ümmaxjejm) A₃) samples, thus breaking the curse of multiagents. In this paper, we study the following question:
Can we find NE in offtine m-player general-sume Markov game with unilateral coverage and without the exponential dependence the number of players?
In this paper, we answer this question in the affirmative. We highlight our contributions below.
1.1 Main Novelties and Contributions
1. Strategy concentration principle. We propose the strategy strategy-wise concentration principle. Point-wise concentration is a standard technique in computing the confidence interval for each state- action pair [Azar et al., 2017, Liu et al., 2021, Xie et al., 2021b, Cui and Du, 2022]. However, the straightforward extension to MARL suffers from the curse of multiagents as the NE can be a mixed strategy. Different from the point-wise concentration technique, strategy-wit wwis concentration directly estimates each strategy. which allows a righter confidence interval that can avoid the dependence on the joint action space. We give technical overview in Section 1.2. In addition, we show that the strategy-wise confidence bound is always a convex function so that the empirical best response stralegy can always be a deterministic strategy, which is critical to the computational efficiency.
2. Improved algorithm for offline two-player zero-sum Markov games. For offline two-player monximin-optimizatiin ttpp
zero-sum Markov games, we utilize its special structure to develop algorithm. Though the nonlinear strategy-wiss bonus breaks the bilinear structure of the zero-sum game, show that by solving maximin optimization problem can still output a good strategy. In addition, we can solve it efficiently using any black-box algorithms for tupschitz-continnnn optimization. Our sample complexity improves the AB factor in Cui and Du [2022] to (A + B).
convex
3. The first algorithm for offline multi- pallti-playrrree general-sum Markov games. For multi-player general-sum Markov games, we develop a surrogate function to approximate performance gap and then show that the minimizer of the surrogate function approximates NE well. The surrogate function is constructed by optimistic best response values and pessimistic values. Interestingly, to our knowledge, this is the first time that optimism has been used in offline RL algorithms. Our result validates that unilateral coverage is sufficient for general-sum Markov games and our sample complexity rate scales with Ö A₂) (ignoring other parameters), thus breaking the curse of multiagents.
Incorporating pre-specified strategy class. Lastly, our algorithm allows exploiting the prior knowledge about the NE strategy with an adaptive sample complexity bound. Pre-specified policy class has been widely used in empirical works where the policy class is parameterized by neural networks (e.g., Mnih et al. [2016], Haarnoja et al. [2018], Lowe et al. [2017]), and single-agent RL theory as well (e.g., Auer et al. [2002]. Agarwal et al. [2021]). but has not been investigated in take a step to incorporate prior knowledge in the MARL setting.
MARL theory. In this paper, Our performance guarantee only depends on the logarithmic covering number of the pre-specified strategy class, which is always upper bounded by Ejem) Ay. but can be smaller. To the best of our knowledge, this is the first paper that considers pre-specified strategy class in MARL theory.
1.2 Technical Overview of Strategy-wise Concentration
To give some intuition about this technique, let consider toy problem. Suppose there are m random variables {ar )m and we want to obtain a pessimistic estimate of their average x = Eie(m x² x'/m.
We have n/m observations for each I². The point-wise concentration estimate corresponds to
2

---

estimating each z' and then aggregating the results. The pessimistic estimate of x² would be S - O(Vm//) where T' is the empirical mean, and the aggregated mean of these pessimistic estimates would be - concentration estimate corresponds to directly using all the samples to estimate the average of { i== and obtain the pessimistic estimate as ã ((I//)) This example shows that the point-wise estimate will lead to an extra m factor. In MARL, m is the cardinality of the joint action space, which implies that point-wiss concentration can be exponentially worse than strategy-wis wwie concentration. Note that this is not an issue in single-agent MDP as the optimal policy is always deterministic but leads to severe suboptimality in the multi-agent case where NE can be mixed strategy.
where T is the empirical mean of all data. The strategy-wise
1.3 Related Work
Online Multi-agent RL. Markov games can be solved via dynamic programming when the rewards and transition dynamics are given [Hansen et al., 2013, Perolat et al., 2015]. If the environment is unknown, reinforcement learning algorithms are applied with different sampling oracles. One particular line of research is online Markov games, including two-player zero-sum Markov games [Liu et al., 2021, Dou et al., 2021, Xie al., 2020, Bai et al., 2020, Huang et al., 2021] and multi multi-player general-sum Markov games [Zhong et al., 2021, Mao et al., 2021, Jin et al., 2021 2021a, l, Song et al., 2021]. J.. Rubinstein [2016] proves an exponential (in the number of players) lower bound for learning the NE strategy in m-player general-sum game while others show that the correlated equilibrium and coarse correlated equilibrium admit poly (, [ Aj. ... -)-smplle complexity algorithms [Mao et al., 2021, Jin et al., 202 20 Song et al., 2021]. Our upper bounds for m-player general games depend polynomially on all parameters, which do not contradict the hardness result in Rubinstein [2016] because the assumptions on the offline dataset provide additional information about the NE.
Offline Single-agent RL. The simplest dataset assumption for offline RL is uniform coverage, i.e., the dataset covers all the state-action pairs. This assumption dates back to Szepesvári and Munos [2005]. The minimax sample complexity has been well studied for both tabular case and function approximation [Xie and Jiang, 2021, Yin et al., 2020, 2021, Ren et al., 2021J. Recently it has been shown that only covering the optimal policy is sufficient for offline RL under different settings [Rashidinejad et al., 2021, Yin and Wang, 2021, Xie et al., 202 lb. Jin et al., 202 lb, Uehara and Sun, 2021, Zanette et al., 2021, Xie et al., 202 These works design provably efficient algorithms based on the principle of pessimism.
Offline Multi-agent RI. Offiine MARL theory is still a primary stage. Previous works mostly focused on uniform coverage assumption, i.e. all state-action pairs or all policies are covered [Sidford et al., 2020, Cui and Yang, 2021, Zhang al., 2020, 2021b, Abe and Kaneko, 2020, Subramanian et al., 2021]. Recently, Cui and Du [2022] and Zhong et al. [2022] show that the unilateral coverage assumption is the minimal dataset coverage assumption for learning NE in Markov games. In addition, [Cui and Du, 2022] proposes a pessimism-type algorithm with A(ABBFCCT*)) sample complexity for tabular two-player zero-sum Markov game and [Zhong et al., 2022] provides similar algorithm for linear two-player zero-sun sum Markov games.
2 Preliminaries
Notations. We use D(X) to denote the single point distributions over the finite set X. For example, D(A) to represent the policies that deterministically choose one of the actions in A. We use TJA E A(4,) as a concise notation of (-Is) and (s,ss a) to denote (r a), which will be defined in the following section. We use -j in subscript to denote all the players except player j. We use bold letter to denote vectors, e.g. is vector and aj is the j-th element of a. We let
O(-) hide absolute constants and Ö()) hide polylog terms as well. The LI norm of a vector in Rd is ||a]] = Ein laz|- We denote the projection as projia, (x) == maxfa, min(b,x)) x
Multi General-sum Markov Game A multi-player general-sum Markov game is described by tuple 9- = (S, A = [[y=(m) P, R, H), where S is the state space with cardinality S, m is the number of players, Ag is the action space of player j with cardinality Aj. P (P1, Pa. PH) with P. E R Sx 4xx9 being the (unknown) transition matrix at timestep h E [M]. R
RR (-1sh, H with RA (-1sh, a,) being distribution on [0, 11mh with mean ry (sh, an) [0. 11
3

---

as the (unknown) reward distribution at timestep h. At timestep h, all players choose their actions simultaneously and a reward vector is sampled from the reward distribution rv Rd (-1sk, ap). where 8 is the current state and as [1h,1, a ; (hh.m) is the joint action. Each player j receives its own reward Thi with support on [0, 1] and mean rh. an). The state then transits to 8h+1 following the distribution of (- 8%. a.,) The game terminates at timestep H + 1. We assume that the initial state $ is fixed because for a stochastic initial state, one can add so as the initial state instead and it transits to 81 following the initial distribution.
We denote a joint strategy as π (T1, TT..... , T.)) where Ty (T1, Te.j.".. TH..) and The S + (AA,) is the strategy of player j at timestep h where A(A,) is the probability simplex over Aj. We use f1 to denote the set of all the possible joint strategies. We define the state value function and state-action value function under strategy π for each player E [m]:
H
Viy E Ex Σ (rcs(sc.au) a.)
Shc
( an) := Ex
Σ
Ne. (3), ar)
Shs au
where the expectation is over the randomness of the environment and the joint strategy л. For fixed player j. if all the other player's strategies are fixed, then player j can play the best response strategy to maximize its own total reward. We define т to be the strategy for all players except player j and define the best response value to be V..j (5%) == maxa, Vi"3""''ssh (sh).
It is well- that Nash equilibrium strategy exists for general-sum Markov games. Note that there could be multiple NE strategies with different value functions. We use the following performance gap to evaluate a strategy π:: Gap(T) == E}e(m) [V1. (81) - VT, (s1) This metric is always non-negative and we say π is an e-approximate NE if and only if Gap(T)) S.
Two-player Zero-sum Markov Game. A general-sum Markov game becomes a two-player zero-sum Markov game if there are only two players and the reward T4 ~ (-1s, a2) always satisfies Th,1 = 0 for all h [H) s E S,aj aj E A1 and 02 E A2. Following the literatures on two-player zero-sum Markov games, we use slightly different notations for this setting. There is only one reward function r shared by both players, which is the reward funetion (ri, ) for player and the target of player is to minimize the total reward. We denote μı and v/ 22 to be the strategy for each player, a = a1 and b = 02 to be the action for each player, ITmax IΙ, and Immia = Iī2 to be the strategy class for each player to remove extra subscripts. One can derive the performance gap under (s1).
the new notations for two-player zero-sum Markov games: Gap(T) == Ví"" (s1)
Offline Markoy Game In offline RL, the dataset is collected beforehand and no further sampling is allowed. Here we consider offline multi palltr-payerrge general-sun sum Markov game. The framework for offline two-player zero-sum Markov game is similar with the slightly different notations as we mentioned.
H 1,1 that We assume that the algorithm has access to an offline dataset D = {(>) ali r/, 1
satisfies Assumption 1. The assumption states that the dataset is independently generated from the underlying Markov game, which is used in [Jin et al., 2021b, Zhong et al., 2022]. The target of offline Markov game is to find a strategy π with as small performance gap as possible by utilizing the dataset D. One closely related assumption is that the dataset is generated from some behavior strategy [Xie et al., 2021b, Cui and Du, 2022]. Though this kind of dataset does not satisfy Assumption directly due to the dependence within the trajectory, we can construct a compliant dataset by using the subsampling technique in Li et al. [2022] while the number of samples is still of the same order. Assumption 1. The dataset D is compliant with the multi multi-playee general-sum markov game, i.e.,
PD( = s/ a = (s = s Sh. = sni a a (D = att) RA = r(sh s/i an af)). [m],
kk
for all h E [H] and k E [n]. In addition, all tuples (s); at, r/. s sh.+1) 1) are independent.
Pre-specified Policy Class. We also consider the case when we know that the NE is possibly in a given subset of full We denote this subset as II and our target is to find the best strategy in II. Note that we do not assume NE is indeed in IT. In addition, by choosing II = ffull we can recover the the covering number.
standard setting. To measure the complexity of II, Definition 1. (Covering Number) For any error level eeover and strategy class II we define
NII,, <cover) =
Σ II
(((TT,)()) (oover)),
aES, be (C)

---

Algorithm 1 Strategy-wise Bonus + MaxiMin Optimization (SBMM)
Input: offline dataset D.
Initialization: + (8) = V H++1(*) = 0 for all & E S. for time h H, H I,.... .......... do
#Player
Approximately solve ". argmax a pe minygED(B) ( where V (8) is defined by (4) and (5) and H satisfies (10).
Solve 2i argmin Vi (s) and set (s(s) = p W (0)).
#Player
Approximately solve vi argmin (ge maxp(ED(A) 12 (s), where Vitii (s) is
defined by (8) and (9) and vi satisfies (11).
Solve Ti argmax HA E(AA) Vil 1hh (s) and set Vi projoo. Vhin (0)
end for Output nutputt (1, D).
where (+) ( (1s)) II} is a subset of ((As) and ((TIn.j(s), ccover) is an Enower -Coerrigg of (8) with respect to the LI norm || -l11-
Our performance guarantee will only have logarithm dependence on N N(II, Ecover). As J is subset of (AA)), we always have (II, Ecover)) I Ō(C)Ejm) A, log(1/ (cover)))) and if II is a finite set, we have log(AN (cover)) I lo (see Appendix B.1 for the proof). In this paper we will choose Ccover Eye(m) AymH+n? which only leads to logarithm dependence these quantities. In later sections, we will omit Coover to simplify the notation.
For any joint strategy т, call (n'), Rーj)) for any strategy r' and j [m]] unilateral strategy of т. Previous works show that only covering an NE is not sufficient, and covering all the unilateral strategies of an NE is necessary for learning the NE in Markov games [Cui and Du, 2022, Zhong et al., 2022]. We use unilateral coefficient to quantify how the dataset covers all the unilateral strategies of a strategy æ. If we assume that the dataset is sampled from some (unknown) distribution, i.c.
(sh, as)) ~ (----) -) for all h E [H], we can define the population unilateral coefficient.
Definition 2. For any strategy n. the population unilateral coefficient is defined C(T) 2 (s).aa)
maxb.j.r 18 ay
as))
Cui and Du [2022] provide a sample complexity result for zero-sum Markov games with dependence on C(T*). We can also define the empirical unilateral coefficient using the empirical distribution.
Definition 3. Define the empirical dataset distribution d,, a) ms,s,)) a))n, for all h [H]s E S, a E A. where n4, (s, a) is the number of times that as, appears in the dataset for timestep h. For any strategy the empirical unilateral coefficient is defined ((T) ==
3 (sn.
maxp.je' A9, (sp.saa)))
The empirical unilateral coefficient can lead to dataset-dependent bound that has no dependence on the underlying distribution of the dataset. In addition, ((T)) can be bounded by 2C(TT) (Proposition I) so results based on ((T) directly transfer to C(T). Note that ((T) and C'(T) are both unknown to the algorithm and only appear in the analysis and theorems.
Proposition 1. Suppose Pmiin ming, (d.
(s. a): (s 0}. If 2 with probability 1 1- 5, for all strategy have 2C(T) 2 (TT).
8 (S A, H/8)
Puiia
3 An Improved Algorithm for Offline Two-player Zero-sum Markov Game
In this section, we propose a new algorithm for offline zero-sum Markov game based on two novel techniques, i.e., strategy-wise concentration and ioxiiinnoptimizzaion-basss algorithm. We then show that this algorithm computationally efficient and can (almost) find the best strategy strategy class II with favorable sample complexity.
5

---

Let us first define some notations. Given dataset D = {(s o by. rh sftt s(+1)) we denote
nu (s. a. b) Ex=1 ((sh a bb)) (s, b)) and (s)(s) f(a,b) A x nn(s, a, b) + 0).
If (s, a, b) o O, set
a)) = Ek=i r ((s az
a by) = (s, a, b))
(1)
(n(
Pr(s'ss,a,bb) Ei=1 1 ((5 ai by +1+1) (s, a, (,,
(2)
Thh (n, a)
otherwise we have
(s, 0, 0, P, a, b) =0
(3)
Based on this empirical Markov game, we can perform calle-iteration-type algorithm. Here we describe our algorithm for player For each timestep h, we first compute the the state-action values based on the estimates at timestep h h 1:
(s, a, b) = as, + (
Then instead of adding the bonus on state-action estimates directly to ensure pessimism as used in Cui and Du [2022] and Zhong et al. [2022], we first estimate the state value functions for strategy 1 vg and then add the bonus on them instead.
Vil 2 (s) Eag dr (8, bn, v2),
(5)
where
(b)
by uh v/))= =
Σ
Iog(N(II)c++ vi/n,
(6)
(8, a,
(a,
with 32 1og22ABSSH// We also present the bonus from point-wise concentration used in Cui and Du [2022] to better compare them, ipoint (8, 1h, vf) = H H (1 17 (1()) mn(s,a.
As a concrete example, if 1i and of are uniform distribution on A and B, then by (8, Mig v/) is smaller than bpoint (s, /f, we solve the following optimization problem
vf,) for an order of VAB. Finally to obtain the pessimistic value estimate,
V vs(s)
max 2 Ell (8) D())(
min 12 (s).
Here recall that D(B) represents all the deterministic strategies in B. Our algorthm is similar for player 2 with the following Q and V estimation:
an Fr (s. a. + (P,(s,
Hi((a, $ (s)s))
(8)
VHL. (s) = Eng.o (s, a, b) + by (s, (s, ph, v1)).
(9)
The additional H1((a, b) & K. (s)) term in (8) compared with (4) is to compensate the underestimate by (3).
3.1 Computational Efficiency
For computational efficiency, we start with the following characterization about our bonus.
Proposition 2. Vull. .7 (s) ) is concave and Vili 1 (s) convex w.r.t He, and vf, respectively.
Proposition 2 explains why the inner minimization in (7) is over the deterministic strategy class as the minimum of a concave function over the probability simplex is achieved at the vertexes, i.e. deterministic strategies. The proof of Proposition is provided in Appendix B.2.
Previous works solve the NE (saddle point) of 4 (s) as the point-wise bonus maintains the bilinear structure [Cui and Du, 2022, Zhong et al., 2022]. Though here 12 (s) no longer enjoys

---

the strong duality, we will show that solving the maximin problem is enough to obtain a good strategy for player I. As the inner minimization is only on feasible set of size B. this problem can be solved efficiently by using projected gradient descent [Bubeck et al., 2015]. We assume that we solve the maximin and the minimax optimization problem to copt oopt-mptiml,,ty, i.e.
min (ED((B
V
h
(s)
min Ag Ell (+) (ED((B
max
V (s) copt: h
(10)
V (AED(A)
max
(8) min "I "gelg" (AE((A)
max
V ' (8) Capt.
(11)
In Appendix B.2 we show that projected gradient descent can output an fopt-minimizer with (H Hl / (WV((((())))))))))))))))))))))))
iterations, where each iteration consists of a gradient computation and projection onto the probability simplex. We note that if we set Copt to An. then the optimization error is always of a smaller order term compared to the statistical error.
3.2 Sample Complexity Guarantees for SBMM
For the statistical guarantee, we will first provide assumption-free bounds in the sense that it holds for arbitrary compliant dataset [Jin et al., 2021b, Yin and Wang, 2021]. We define the uncertainty at timestep h and state under strategy 1 and vi;
(n,s, (s. ph: v/)) == 2b, (s, M + + H
(a(a)
(a.b)
Proposition 3. Suppose π output is the output of Algorithm! 1. With probability 1 5, have
Gap(e n output) <
H Gap(x) + Ey, Σ bi ,K0) k/) +Bp' Σ
H
min (A.P)E ( -eeet"eeeeeee Dedddet
max
ba 1/ vn) + 2H Copt.
Proposition shows that our algorithm can find the best strategy in with an additional error of the expected total uncertainty under some unilateral strategies and an extra optimization error term 2H Copt- Then we derive bounds with unilateral coefficients.
Theorem 1. Suppose π output is the output of Algorithm 1. With probability - 8, we have
Gap(routput) S min xell
Gap(T) + 4H² V (llog(((T)(((M)) HH
Theorem directly implies the following corollary.
Corollary 1. If II I1 then with probability 1 - 8. have Gap(noutput)
Ō( O( H ())()) + 21HEopt Tf E 11. then with probability 1 8, we have
Gap(rootput) ō(v H (o + 2HH
Since Ö(T)) can be bounded using C(x) (Proposition 1), we have the following theorem.
Theorem 2. Suppose output is the output of Algorithm 1. With probability 5, we have
Gup(r I min Gaa((T) 4H² ( ( HSSA HS(A+ B)C(z)/n +20lm)mm222HHm. +pp
welf
In addition, suppose Pmin = min. a, ds a, b) > 0} and if 2 have Gap(T) & min Gaa((T) + 8H2 (oogsoo
8 $log(SABHI/) we
Pmiio
cap
Theorem shows that there will be an additional lower order term S(A + B)C(n)/n, which can be interpreted as the rate of the empirical dataset distribution converges the population distribution. In addition, for large enough n (log(SABH/8) there is no lower order term. Here n > Slog(SABH/5)
Puin serves as a warm-up cost so that the empirical support is the same as the true support da. A similar analysis is used in Yin and Wang [2021]. With refined analysis, we can show that there is no lower order term for the standard settings IT I7 in two-player zero-sum Markov games and IT dett for turn-based Markov games. Note that turn-aaeed Markov games always have deterministic NE.
Puin
7

---

Corollary 2. If II = II then with probability 1 - 8. we have Gap(T Ö(VHAS(A ()C((*))n)) copt In addition, for turn-based two-player zero-sum Markov games, we can set II Ildct and we have Gap( = Ō( ((((+((()))) + cot
Corollary 2 improves the AB dependence in the previous zero-sum Markov games result [Cui and Du, 2022] and matches the result for turn-based Markov games [Cui and Du, 2022] up to an extra vH factor. The additional H factor is due to the Hoeffding-Vy bonus and we believe it can be removed with more sophisticated Bernstein-type bonus.
4 Algorithms and Analyses for Multi-player General-sum Markov Game
In this section, we propose the first provably efficient algorithm for offline multi-playe general-sum Markov game. We will use the strategy-wise bonus to achieve a sample complexity that does not scale with [[) Aj. However, in general-sum games there is no saddle point structure, so we can no longer use the maximin--ppimizzaion---yy algorithm. Instead, our algorithm utilizes a novel surrogate function to approximately minimize the performance gap.
1 Given dataset D = {(* a ry, 1 1R,b=1 we denote na (s. = Ei=ı 1 ((5) a (s, a))
and (s) {a (1.s a) o 0}. If (s, a) O, we set
(8, Ek=1 k ((s alt = (s) (n
Ek 1 ((s a/, s/+,1) 1)+ = as,
nh (s, a)
ni (8,
(12)
otherwise we have ( a) = 0, Pr(s'(s,a) O.
Based on this empirical multi-player Markov game, æ via policy evaluation (Algorithm 2 in Appendix). We describe Algorithm for the pessimistic estimate. For player j. strategy and timestep h. we first compute the state-action value estimates:
estimate the value of arbitrary strategy
(s, = ( a) + < ().
(13)
Then we estimate the state value functions and add the strategy-wise bonus to ensure pessimism.
(T) projjo, --+1 (1a (s,
(5. a) (s,(sT/))
(14)
Ii Tha(az}² mn(s,a)
where (s, Th) =H
S loog(N(L))) + Vi/n,
(15)
(Eki((s)
with L = 32 log 16 [[] A AymSHn/0). Here the strategy-wise pessimism can remove the [[ Aj dependence as explained in the previous section. By dynamic programming from timestep H timestep 1 we can obtain the pessimistic estimate VT (s1). Compared with the bonus function (6) in zero-sum Markov game, there is an extra S factor in (15) because here we need to perform con-
centration on ( (Ph a), VTT...)) for all x while in (4) we only need to analyze (Pr (s, a, b), Va+1 for a single VA+1- We use an additional c-covering on T& which leads to the extra S.
We use Algorithm 3 (in Appendix) to compute the optimistic value of the best response strategy. For given player j. strategy т-j used by all the other player and timestep h, we first compute the optimistic state-action value estimate:
Q (s, a) (s, +
Hifa (s))
(16)
Then we compute the optimistic value for deterministic strategies for player j:
Var(s,aj) =Ba -Ba_,-oh- "s, a_,) + bn(s, Aj: -/)
(17)
Here with a slight abuse of the notation, we use aj to denote the deterministic strategy of player that chooses action aj at state and timestep h. Finally we the maxi- mum over all the deterministic strategies to be the best response value function: V...-ion:V..--166 = projjo. H --41] (max.,eA, EAA (s,
8

---

By dynamic programming we can obtain the optimistic estimate V (s1) at the initial state. Note that we only consider the deterministic strategies for player j. Thanks the convexity of the bonus (s, m,), the best response with respect V (s) also in the deterministic strategy class in zero-sum Markov games. The following proposition connects Algorithm 2 and Algorithm 3:
V Proposition 4. For any strategy R-j E I -j.h h E [H] and E S. we have Vn. (s) max,, Vi.j P(s).
Based on Algorithm and Algorithm 3, we propose a surrogate minimization algorithm for multi- player general-sum Markov game, Suppose (s1) and Vi.j '(s1) are pessimistic and optimistic estimates, then we have
Gap(T) =
Σ JE(m]
(81) (s) < Σ Vi3 (s)) - (s)
jE(m]
The RHS can serve as the surrogate function and SBSM (Algorithm in Appendix) outputs the minimizer of it in II. From the computational perspective, Algorithm 2 and Algorithm 3 are both efficient while Algorithm 4 needs enumerate II for the worst case. This computational hardness agrees with the PPAD-hardness for computing approximate NE even in full information general-sum game [Daskalakis, 2013]. However, if TI is well structured, Algorithm 4 may be computationally efficient and we leave it to future work. Here we assume T ouuput is an exact solution while it is straightforward incorporate optimization error as in the previous section.
4.1 Sample Complexity Guarantees for SBSM
We still begin with assumption-fre free bound as the previous section. We define the uncertainty at timestep h and state under strategy æ: by (s,s, T 2b, TT) + H Engx, (5) (a).
Proposition 5. Suppose ooupuut is the output of Algorithm 4. With probability 1 - ô, we have
Gap(n out I min Gap(T) + rell
Σ
13
(sn. The "h.-,) ,) + mBx Σ ba (sh, x
m)
Proposition 5 has similar structure as Proposition with slight difference in the expected uncertainty terms. Then we will bound using the unilateral coefficients.
Theorem 3. Suppose nutput is the output of Algorithm 4. With probability - 8, we have
Gap(roulput)
min
Gap(#) + SmH ((T) log(N (II))//) TET
Theorem 3 directly implies the following corollary, which shows that the sample complexity of offline multi-agent RL only scales linearly with respect to the number of the players.
Corollary 3. If II fu with probability 1 5, have Gap( Gup(routputt
Ö(V HAS2 Eje(m) A,C(**)/m) if II, then with probability 1- 8, have Gap(routput) Ö(V H (TT))
Similarly we have the following theorem and corollary for the population unilateral coefficient.
Theorem 4. Suppose outpput is the output of Algorithm 4. If STI A, H/8) with proba-
Puiia
bility - we have Gup(uoutput) I min Gap(T) + 22 /C((m log (N
IfTI Tfull with probability 8, we have Corollary Suppose n 2 8 blog(S)) $llg(S1l,c A, H/8)
Pmin
Gap(touuputt) σlv H Σ jElm) A,C(T*)/n) If E II, then with probability 1 - 8, we have
Gap(T Õ(v HTS (oNSsooo(((I))C/771/
Conclusion
In this work, we studied offline MARL. With novel strategy-wise bonus, we remove the exponential dependence on the number of players. We use different algorithm frameworks for zero-sum Markov games and general-sum Markov games due to their different properties.

---

Here we list several open problems for future work. One direction is to find the minimax sample complexity for offline Markov games, i..., if the (II) term necessary. Another direction is to design computationally efficient algorithms for finding (coarse) correlated equilibrium in general-sum Markov games. Lastly, we only focus on the tabular setting serving as a start point. It is important to study MARL with reasonable function approximation.
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 exploitabllity-cvauuttoo in two-player zero-sum markov games. arXiv preprint arXiv:2007.02141, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 176, 2021.
Peter Auer, Nicolo Cesa- Bianchi,, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing. 32((1):88777) 2002.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play, Advances in neural information processing systems, 33:2159-2170,, 2020.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Qiwen Cui and Simon S Du When is offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03522 2022.
Qiwen Cui and Lin F Yang. Minimax sample complexity for turn-based stochastic game. In Uncertainty in Artificial Intelligence, pages 1496-1504. PMLR, 2021.
Constantinos Daskalakis. On the complexity of approximating nash equilibrium. ACM Transactions on Algorithms (TALG), 13):1-33,, 2013.
Zehao Dou, Zhuoran Yang, Zhaoran Wang, and Simon S Du. Gap-dependent bounds for two-player markov games. arXiv preprint arXiv:2107.0063: 2021.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 6061):1-16. 2013.
Baihe Huang, Jason Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approxima- tion in zero-sum markov games. arXiv preprint 2rXiv22107.47002 2021.
Jiechuan Jiang and Zongqing Lu. Offline decentralized multi-agent reinforcement learning. arXiv preprint 1rXiv:2108.018.. 2021.
10

---

Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021b.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model- offline reinforcement learning. arXiv preprint arXi::2204.05275, 2022.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettive environments. Advances in neural information processing systems, 30, 2017.
Weichao Mao, Tamer Basar, Lin F Yang, and Kaiqing Zhang. Decentralized cooperative multi-agent reinforcement learning with exploration. arXiv preprint arXiv:2110.05700. 2021.
Linghui Meng, Muning Wen, Yaodong Yang, Chenyang Le, Xiyun Li, Weinan Zhang, Ying Wen, Haifeng Zhang, Jun Wang, and Bo Xu. Offline pre-trained multi-agent decision transformer: One big sequence model conquers all starcraftii tasks. arXiv preprint 2XXi:2112.00244 2021.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pages 1928-1937. PMLR, 2016.
Ling Pan, Longbo Huang, Tengyu Ma, and Huazhe Xu. Plan better amid conservatism: Offline multi-agent reinforcement learning with actor rectification. arXiv preprint arXiv:2111.11188, 2021.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, pages PMLR, 2015.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34, 2021.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances neural information processing systems, 34, 2021.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 258-265. IEEE, 2016.
Shai Shalev-Shwarte Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint 1rXiv:1610.03295, 2016.
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 9902-3002. PMLR, 2020.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou. Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of without human knowledge. nature, 550(7676):544-59) 2017.
Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum markov games with a large number of players sample-effiiinnly? arXiv preprint a 2021.
Jayakumar Subramanian, Amit Sinha, and Aditya Mahajan. Robustness and sample complexity of model-based marl for general-sum markov games. arXiv preprint arXiv:2110.02355. 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 preprint arXiv:2107.06226, 2021.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. Conference on learning theory, pages 3674-3682. PMLR, 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11 11404-11413, PMIR, 2021.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistrr pessimism for offline reinforcement learning. Advances in neural information processing systems, 6666,,3-699,, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34, 2021b.
Ming Yin and Yu-Xiang Wang. Towards instancc-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34, 2021.
Ming Yin, Yu Bai, and Yu- Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.0376)) 2020.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in nearal information processing systems, 34, 2021.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34, 2021.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent zero-sum markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33: 166-1178 2020.
Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. 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 multiagent reinforcement learning with networked agents. IEEE Transactions on Automatic Control, 66(12):5925-50) 5940, 2021b.
Han Zhong, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Can reinforcement learning find stackelberg-natt nash equilibria in general-sum markov games with myopic followers? arXiv preprint 12Xiv:2112.13521, 2021.
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 arXhv:2202.05511, 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 describe 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]
12

---

2. If you are 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 or 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 (c.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 (e.g., type of GPUs, internal cluster, 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 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 identifiable information 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, 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]
13


Reviews:
[{"review_id": "hkMpx7N42M", "reviewer": "Reviewer_ctbY", "summary": "While there is an extensive literature on both multi-agent reinforcement learning (MARL) and offline RL separately, this work explores a setting that combines the two. In the MARL setting, the size of the joint action space grows exponentially with the number of agents, which is a key challenge in this subarea. This paper investigates how to tackle this problem and whether we can find a Nash equilibrium strategy in the offline MARL setting given unilateral coverage. \nSpecifically, to construct a confidence interval for each state-action pair in the offline MARL setting, the authors proposes to estimate each strategy separately to circumvent the dependence of the joint action space which grows exponentially with the number of agents. Besides, based on this, the authors also develop two different algorithm frameworks under the tabular case for both the offline two-player zero-sum Markov games as well as the offline multi-player general-sum Markov games separately. \n\n", "questions": "The analysis of this paper is based on a pre-specified policy class that contains the NE. The structure of the strategy class is a critical component in the proposed algorithm frameworks, which is especially true for the efficient computation of the surrogate function in the multi-player general-sum Markov game setting. Is a principled approach for structuring the strategy class? \nIn addition, while the strategy-wise bonus can avoid the exponential dependence of the number of players, what the potential downsides or limitations of this approach compared to point-wise estimations? ", "limitations": "The authors has addressed some potential limitations. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper helps to improve our current understanding of algorithms for the offline MARL under the tabular setting. The major contribution is the proposed strategy-wise bonus, which firstly estimates the state value functions for a strategy and then add the bonus on them. However, if the strategies are complicated and therefore the class space not well structured, the calculation for state value functions for the strategy could be challenging. \n\nGiven this, for the two-player zero-sum Markov games, the proposed framework utilizes a strategy-wise bonus as well as maximin-optimization-type algorithm. For the multi-player general-sum Markov game, as there is no saddle point structure, this paper proposes a surrogate function to minimize the performance gap, which, however, requires to enumerate the strategy class in the worst case and thus not computationally efficient. \n\nAnother concern regarding the current version is that the data assumption adopted in this work (Assumption 1) assumes that the all the tuples in the logged dataset are independent, while this is not true in most real-world scenarios. As in many real-world applications, this assumption is very restrictive on the dataset and therefore usually does not hold. To derive practical algorithms based on the theoretical analysis and test the efficacy of the proposed methods in practice, the work should consider the impact of the violation of this assumption on the algorithm performance. \n\n\n\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": "X64_8GxD4i", "reviewer": "Reviewer_1W3v", "summary": "In this paper, the authors study the offline multi-agent RL. They propose the strategy-wise concentration principle in contrast to the point-wise concentration principle in existing works. By the new concentration principle, they propose novel algorithms with strategy-wise bonuses for both zero-sum and general-sum games, which achieve better sample complexities than the existing works. The sample complexity of the new method does not scale with the size of the joint action space. Moreover, the proposed algorithms can take a pre-specified strategy class as input and output a strategy that is close to the best strategy in such a class. ", "questions": "I have a small question regarding this strategy-wise concentration method. Is it possible to apply such a strategy-wise bonus to the online Markov game setting?", "limitations": "I was not able to find the discussion of the limitation. It would be much better if the authors can explicitly summarize the limitation of their work in the conclusion section or in the checklist.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper proposes novel algorithms with the strategy-wise bonus, which leads to better sample complexities than the existing works. I think it is an important contribution to the theoretical analysis of the offline Markov games as the new sample complexity result does not scale with the size of the joint action space. In addition, the writing of this work is good in general and this paper is well structured. \n\nHowever, I was not able to find the discussion of the limitation in the paper although the author answered yes in the checklist. It would be much better if the authors can explicitly summarize the limitation of their work in the conclusion section or in the checklist.\n\nBesides, is it possible to apply such a strategy-wise bonus to the online Markov game setting?", "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": "OgcrHRq7dCk", "reviewer": "Reviewer_5fGy", "summary": "This paper considers offline multi-agent reinforcement learning.", "questions": "The sample complexity for multi-agent general sum MDP is exponential.", "limitations": "The sample complexity for multi-agent general sum MDP is exponential.", "rating": 4, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The sample complexity for multi-agent general sum MDP is at least $N = \\prod_{i=1}^m A_i$, where $A_i$'s denote the effective action space size for each agent (i.e., the number of actions obeying $\\pi_i(a) > 0$).\nSpecifically, to ensure $\\hat{C} < \\infty$, one needs at least $N$ samples such that ${\\hat{d}}h(s, a) > 0$ when $d_h^{\\pi}(s, a) > 0$.\nIn addition, the assumption $C < \\infty$ implies there are at least $N$ actions satisfying $d_h(s, a) > 0$, which leads to $1/p_{\\min} \\ge N$.\nHence, all results for the multi-agent case in Section 3.2 exhibit an exponential dependence on the number of agents, except the case that almost all agents will choose only one action.\n\nOn the other hand, it is well known to find the NE for multi-agent case is computationally hard. Then is it possible to compute CCE effectively for offline multi-agent RL?", "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