Pessimism Meets Invariance: Provably Efficient Offline Mean-Field Multi-Agent RL
Authors: Minshuo Chen
Yan Li
Ethan Wang
Zhuoran Yang
Zhaoran Wang
Tuo Zhao
Venue: NeurIPS 2021 Poster (2021)
Keywords: off-line multi-agent RL
mean-field approximation
pessimistic value iteration
sub-optimality bound

Abstract: Mean-Field Multi-Agent Reinforcement Learning (MF-MARL) is attractive in the applications involving a large population of homogeneous agents, as it exploits the permutation invariance of agents and avoids the curse of many agents. Most existing results only focus on online settings, in which agents can interact with the environment during training. In some applications such as social welfare optimization, however, the interaction during training can be prohibitive or even unethical in the societal systems. To bridge such a gap, we propose a SAFARI (peSsimistic meAn-Field vAlue iteRatIon) algorithm for off-line MF-MARL, which only requires a handful of pre-collected experience data. Theoretically, under a weak coverage assumption that the experience dataset contains enough information about the optimal policy, we prove that for an episodic mean-field MDP with a horizon $H$ and $N$ training trajectories, SAFARI attains a sub-optimality gap of $\mathcal{O}(H^2d_{\rm eff} /\sqrt{N})$, where $d_{\rm eff}$ is the effective dimension of the function class for parameterizing the value function, but independent on the number of agents. Numerical experiments are provided.

Pessimism Meets Invariance: Provably Efficient Offline Mean-Field Multi-Agent RL*
Minshuo Chen' Yan Li Ethan Wang' Zhuoran Yang? Zhaoran Wang? Tuo Zhao'
Georgia Tech University of California, Berkeley
Northwestern University
fmchen393, tourzhao@@gatech. edu
Abstract
Mean-Field Multi-Agent Reinforcement Learning (MF-MARL) is attractive in the applications involving a large population of homogeneous agents, it exploits the permutation invariance of agents and avoids the curse of many agents. Most existing results only focus on online settings, in which agents can interact with the environment during training. In some applications such as social welfare optimization, however, the interaction during training can be prohibitive even unethical in the societal systems. To bridge such gap. we propose SAFARI (peSsimistic meAn-Field vAlue iteRatlon) algorithm for off-line MF-MARL, which only requires a handful of pre-collected experience data. Theoretically, under a weak coverage assumption that the experience dataset contains enough information about the optimal policy, we prove that for an episodic mean-field field MDP with a horizon H and N training trajectories, SAFARI attains a sub-optimality gap of (HH2deett /N), where detr is the effective dimension of the function class for parameterizing the value function, but independent on the number of agents. Numerical experiments are provided.
Introduction
Significant progress has been made towards multi-agent reinforcement learning (MARL) for many prominent sequential decision making problems, such as social welfare optimization (Leibo et al., 2017), fleet control of autonomous vehicles (Shalev-Shwand Shwartz et al., 2016) and playing multiplayer online battle arena (MOBA) games (Berner et al., 2019). As the joint state and action space scales exponentially with the number agents, however, MARL becomes computationally expensive. One remedy is the mean-field regime when an extremely large number of homogenous agents are involved, e.g., social welfare optimization. The effect of each agent on the overall multi-agent system can become infinitesimal, and therefore all agents can be considered (Yang et al., 2018; Carmona et al., 2019; Li et al., 2021). Accordingly, the interaction among agents be captured by some mean-field quantity such the empirical distribution of states, and therefore each agent only needs to find the best response to the so-called "mean-fiele state", which avoids the curse of many agents.
Most existing results on mean-field MARL (MF-MARL) are for the online setting (Yang et al., 2018: Zhang et al., 2019), where the agents can interact with the environment during training. However, such interaction during training can be prohibitive for some important applications (Leibo et al., 2017: Mandel et al., 2014; Jaques et al., 2019; Levine et al., 2020). Taking social welfare optimization as an example, repeatedly conducting social experiments on human being can be unaffordable or even unethical in the societal systems. Therefore, we can only consider the offline settings, i.e.. we learn the optimal policy based on some pre-collected experience data (Levine et al., 2020). Unfortunately,
"Extension to online setting is provided in a longer technical report version, which is available upon request.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

existing offline reinforcement learning (RL) algorithms and theories all focus on the single agent settings, and no algorithmss and theories have been developed for MARL under the offline settings. regardless of the mean-field regime or not.
To bridge such critical gap, we propose the first pessimistic algorithm named SAFARI (peSsimistic mcAn--ield vAlue iteRatlon) for mean-field MARL, which can provably achieve sample efficiency under the offline setting. Our proposed algorithm contains two important components: (1) To incorporate the permutation invariance of the homogenous agents, we adopt a RKHS (Reproducing Kernel Hilbert Space) mean- geean-ebbediing approach for approximating value functions, which avoids the exponential blowup of the agents' state and action spaces; (2) We develop an uncertainty quantifier, and integrate it into the value iteration procedure as the penalty function. Such penalty function can effectively screen the "spuriously correlated trajectories", i.e., which possibly happen to appear in the experience data, but are actually unrelated to the optimal policy, but by chance induce large cumulative rewards and hence may potentially mislead the learned policy.
Theoretically, we establish data-dependent upper bound on the suboptimality of SAFARI for MF- MARL without the stringent assumptions on the sufficient coverage of the experience data (e.g., finite concentrability coefficients (Chen and Jiang, 2019) or uniformly lower bounded densities of visitation measure (Yin et al., 2020)). More specifically, we only assume that the experience data of N training trajectories contains enough information about the optimal policy. Then we prove that for an episodic MF-MARL problem with a horizon H, SAFARI attains a sub-optimality gap of (1H2dett/ / /VN). where deft is the effective dimension of the function class (RKHS) for parameterizing the value function and independent on the number of agents. In addition to the offline settings, our SAFARI algorithm can also be extended to MF-MARL under the online setting (OMPPO algorithm), which is of independent interest. Details are provided in a longer technical report version, which is available upon request.
The rest of this paper is organized as follows: Section 2 reviews related work mean-field multi- agent reinforcement learning and offline reinforcement learning for the single agent settings: Section 3 introduces our problem setup of the mean-field MARL regime; Section 4 introduces our proposed SAFARI algorithm: Section 5 establishes the theoretical guarantees for SAFARI; Section 6 presents numerical experiments on the multi-agent particle cooperative navigation scenario; Section 7 draws a brief conclusion.
2 Related Work
Mcan-Field MARL. Existing literature has proposed various mean-field approximation approaches model the population behavior of the agents for MARL with large number, even infinitely many homogenous agents. Yang et al. (2017) investigate a mean-field game with deterministic linear state transitions, and reformulate as a mean-field MDP, where the mean-field state lies in finite- dimensional probability simplex. Yang et al. (2018) propose mean-field approximation approach over actions, which approximates the interaction between any given agent and the population by the interaction between the agent's action and the averaged actions of its neighboring agents. Such an averaging approach over the local actions, however, is only applicable when a sparse graph over agents is given, which requires extensive prior knowledge. Carmona et al. (2019) investigate a mean-field field MDP from the perspective of mean-field control. As the mean-fiell state lies in a probability simplex and continuous in nature, they propose to discretize the joint state-action space such that conventional RL algorithms can be applied. Wang et al. (2020) investigate a mean-field MDP motivated by permutation invariance. They require a central controller managing the actions of all the agents, and therefore is restricted to handling the curse of many agents from the exponential blowup of joint state space. More recently, Li et al. (2021) investigate similar mean-field MDP, which allows agents to make their own local actions without resorting to a centralized controller. All these methods focus on the online settings. In comparison, our proposed SAFARI algorithm and theory focus on the offline settings.
RL for Mean-Field Game. Our work is also related to the literature that studies RL methods for mean-field games (Huang et al., 2003; Lasry and Lions, 2006a,b; Huang et al., 2007). Such a game can be viewed as the infinite-agent limit of general-sum Markov game with homogeneous agents, and the aggregated effect of the other agents is also summarized as a mean-field state. In contrast to mean feendfield MARL, the solution concept of mean-field game is the Nash equilibrium.

---

which corresponds to a pair of a local policy x¹ of the representative agent and mean-field state d' satisfying the following two properties: (i) when the mean- mean-field state is set to d", ' is the optimal policy of the representative agent; and (ii) when all agents adopt æ²", the resulting mean-field state is d" Recently, there are many recent works developing RL. methods for solving mean-field games. See, e.g., Guo et al. (2019, 2020b,a); Fu et al. (2019); Anahtarcı et al. (2019); Anahtarci et al. (2020); Anahtarcı et al. (2020); Perrin et al. (2020); Elic et al. (2020); uz Zaman et al. (2020); Cui and Koeppl (2021) and the references therein. Most of these methods adopts a double-loop structure, where the inner loop finds the optimal local policy given the current mean field state and the outer loop updates the mean-field states. Moreover, these works often assume the data distribution is well-explored with either a generative model (Azar et al., 2012) or bounded concentrability coefficients (Munos, 2007). Our mean- mean-field MARL problem is similar to the inner-loop problem of finding the optimal local policy in mean-field games. In contrast to these existing works, our algorithm and theory can be applied datasets that possibly not well-explored. Moreover, mean-field MARL and mean-field games are different models, our work is not directly comparable to these works.
Offline Single-Agent RL. Our work is also closely related to the literature on offline single-agent RL, which often focuses on either policy evaluation or policy optimization. In particular, in policy evaluation, the goal is to estimate the value function of target policy, whereas in policy optimization, we aims to learn the optimal policy, which can be achieved via estimating the optimal value function. For both these tasks, in the offline setting, due to the lack of continuing exploration (Szepesvári, 2010), the distribution shift (Levine et al., 2020) is a fundamental challenge. That is, the trajectories in the dataset and those induced by the target policy or the optimal policy might have diverse distributions. Such a challenge is further exacerbated when function approximators are adopted to represent the desired value functions. To overcome such challenge, most of the existing theoretical works imposes certain well-exploration assumptions on the dataset. Some of commonly made assumptions include uniformly lower bounded visitation measure of the behavior policy, uniformly upper bounded importance sampling ratio, and bounded concentrability coefficients. See, e.g., Antos et al. (2007, 2008); Munos and Szepesvári (2008); Farahmand al. (2010, 2016); Scherrer et al. (2015); Jiang and Li (2016); Thomas and Brunskill (2016): Farajtabar et al. (2018); Liu et al. (2018); Xie et al. (2019); Nachum al. 22)19,,b; Tang et al. (2019); Zhang et al. (2020b); Chen and Jiang (2019); Kallus and Uchara (2019, 2020); Jiang and Huang (2020); Uchara et al. (2020); Duan et al. (2020); Yin and Wang (2020); Yin al. (2020); Nachum and Dai (2020); Yang et al. (2020a); Fu et al. (2020b); Fan et al. (2020); Xie and Jiang (2020a,b); Liao et al. (2020); Zhang et al. (2020a); Ren et al. (2021) and the references therein.
However, in practice, such assumptions on the dataset often fail to hold (Fujimoto et al., 2019; Agarwal et al., 2020; Fu al., 2020a; Gulcehre al., 2020). In light of this, there is a line of recent works that proposes various passimism-basse offline single-agent RL algorithms with empirical evidence or theoretical guarantees (Yu et al., 2020; Kidambi et al., 2020; Kumar et al., 2020; Liu et al., 2020b; Buckman et al., 2020; Jin et al., 2020b; Xiao et al., 2021). In particular, Liu et al. (2020b) propose a regularized variant of fitted Q-iteration (Antos al., 2007, 2008; Munos and Szepesvári, 2008). which is shown to attain the optimal policy within a restricted policy class without assuming the dataset well-explored. Moreover, with an arbitrary dataset, Buckman et al. (2020); Jin et al. (2020b); Xiao et al. (2021) identify the critical role of pessimism in achieving offline sample efficiency. Among these works, our work is particularly related to Jin et al. (2020b), which develops a pessimistic variant of the value iteration algorithm with inite-dimensional linear function approximation. comparison, our SAFARI algorithm extends such an algorithm to mean-field MARL and we propose to employ RKHS mean embedding for handling the difference between finite-agent empirical mean-field state and its infinite-agent counterpart. Moreover, our algorithm and analysis involve infinite- dimensiadi RKHS, which strictly generalizes those in Jin et al. (2020b).
Notation: Given a space X, we denote M(X) as the collection of probability distributions supported on X. Let u, v. w E ' be elements in a Hilbert space, we denote (u, u) as the inner product, and & as the outer product satisfying (u @ z)w= = u (v, w). For scalar a, we denote {a} + = max(0,a). a). We use O()) to hide absolute constants and log factors.
3

---

3 Mean-Field Multi-Agent RL
We consider a Multi-Agent Reinforcement Learning (MARL) problem with m + agents and time horizon H. For the i-th agent (also known as the Representative Agent (RA)), at step h, we denote 84,h 8 and 0i A its state and action, respectively. We assume S and A are compact.
Different from single agent RL problem, the transition kernel, reward function, and policy of a representative agent in MARL depend not only its individual state, but the states of m other agents. Furthermore, we assume that the interaction the representative agent to the other agents permutation invariant, i.e., the influence of all the other agents is modeled using the empirical distribution of states dg.h m Σjzt 8'y, E M(S). To this end, we define the transition kernel Ph : M(S) x A + M(S), the (deterministic) reward function ry x M(S) x + R, and the policy Ta 8 x M(S) - M(A) all depending on a "meta state" denoted as Wn. = (5t,4 da,.) E S M(S) as the meta state space.
(SS). For simplicity, we denote
Remark 1. The empirical distribution of states da, is naturally permutation invariant and evolves according to the transition kernel Ph and policy Ty- To see this, suppose each agent takes the same policy at step h. Then at step h + 1, the state S4+1, of the j-th agent is sampled from the distribution pa(- 8n.5 x da (h.j). where an.j is determined by policy T |h.. xd.,)). Collecting m states S1+1, for j # induces the empirical distribution of states ds,b+1.
We now define several important notions in MARL. Given a policy क, the value function Vž 9 R at step &. H for a representative agent is
Vg (w) Ex Σ ra(wis a;) Wh
where Ex denotes the expectation over the randomness in trajectories induced by policy m. The action-value function (Q-function) QT, Q x A I is defined
()( E, Σ ri(ws, az) wh w. az
By definition, V and Q are related via Vg (w) = LA @7(w, ())(aa A (QT, x).A. Next, we define the Bellman operator and conditional transition operator. At each step h S H, the Bellman operator denoted as B, is
(Bag) a) = E [rn (Wh, as) + g(w++1) Wn = w, = Fn (w, a) (W, a),
(2)
where g is a function defined on Ω and P, is referred to as the conditional transition operator.
Field MARL As the number of agents goes to infinity, the empirical distribution of states d converges (continuous) limit dy- Then the mean-field MARL problem for representative agent is defined as tuple (2, H, P,r). where Q and A are the meta state space and action space, respectively, H is the horizon, P = {pr h==1 Ω A MMSS) is the transition kernel, and (r,)/= is the reward function defined Ω x A. Following Remark 1, the transition of d, is also determined by P {p
To tackle the
joint distribution of states, we embed the meta ataten space Ω x A into a reproducing kernel Hilbert space (RKHS). Specifically, denote E = S x S x A and let K : E x = + R be a symmetrie positive kernel. The corresponding feature mapping of kernel l is denoted vh, which verifies (15(-), vb(-)) = K(.,)) can be infinite dimensional. For any (w, a) E Ω x A, we define mean embedding as
p(w, a) = E,',,, (vss, s', a)].
Based the embedding, parameterize the reward r, and Markov transition Pa linear functionals of p(u, a) in RKHS Hi induced by kernel K, i.e.,
Th (w, a) (p(w, a), 0%), Pa(w' a) (ulw a), on (x(w)))
(4)

---

where 0, 2y are understood "weights" and have bounded Hilbert norm (see Assumption 3), Such a parameterization encodes rich family of functions, once the kernel is universal (Wang et al., 2020). By the definition of Q-function and value function, we can show that the Bellman operator can also be parameterized Hk-
Proposition 1. Suppose the reward function Th. and the transition kernel Ps. is parameterized in HK by (4) for h = 1,..., H. Then for any g : Q + R, the Bellman operator (Brg) and conditional transition operator (Pkg) defined in (2) can be written as
(Br.)) a) = (u(w, a), wg), (Pag) a) (p(w, a), wA + On),
where Wg depends on the function g.
The proof is provided in Appendix C.I, which follows from pure algebraic manipulation. From the perspective of policy learning in mean-field MARL, Proposition motivates us estimate the Bellman operator B,, in Hk. and then optimize the estimated Q-function to obtain a policy. We introduce the detailed learning procedure Section 4 (Algorithm
Offline Pessimistic Value Iteration
In this section, we introduce our dataset and learning algorithm. We collect multiple trajectories of a representative agent in a mean-field MARI. problem. Here the mean-field state distribution d, is prohibitive to trace. Instead, we only independently observe the states of finite number of agents. Accordingly, the batched dataset D NH consists of N trajectories length H, within which the n-th sequence is Tn {(8 E S oa A,, R)} Without loss of generality, assume $4,0 the state of the representative agent, and the reward function is bounded by i.e. [na(w, a) < 1 for any w E Ω2 a E A. The collected trajectories are generated by some unknown behavior policy.
Recall d=p m Σド= $h.j is the empirical state distribution induced by 8 (We slightly alter the notation to emphasize the empirical distribution generated by the collection of m states s 1mmm
while the previous context, we use general purpose notation da,k.) We denote Wj = 5h X dag. and compute the empirical mean embedding of (0), af) as
p(ag ag)) = E ب (s h. s', a[aa]]]] J ET ( S. a.)))))))))))...))))))))))
Under mild conditions, the empirical mean embedding μ( a.)) concentrates around the infinite agent mean embedding n[w"i a²) defined in (3), where wit the infinite agent meta state. See detailed error quantification in Lemma
Pessimistic Value Iteration Our goal is to learn optimal policy to be deployed for all the agents based on the experience data of the representative agent. The idea is to estimate the Q-function at each time step in the RKHS Hx. and then optimize the Q-function to obtain an optimal policy. In more detail, at step h < H, we estimate Bellman operator by optimizing the empirical mean squared Bellman error
(B = argmin Σ (f(u(O),a)) - - -1+1((07+)) +
(5)
where À > 1 controls the regularization strength, v is the estimated value function, and || denotes the Hilbert norm.
The solution to (5) can be written in closed form. For notational simplicity, we define Ki(w, a), :) Rgg ((s,,'',,) with w ==s xxd. de. Then denote the Gram matrix K₁, E NxN
[Knle = K( af), (of a aa (W 2ohh.:08, 81, ah), (0h 82, ag)) for e,l' I.....N.
N. [K [K(W]) ob), Meanwhile, for any (w,a), we denote feature vector (w( a (w) E RN Then the estimated Bellman operator
5

---

By Vi+1 can be written as
(Ba (BA (w,, a) T with on - (Kr + + |r| + (1+1(0 rx (
(6)
We summarize the proposed SAFARI algorithm in Algorithm 1.
Algorithm Pessimistic Mean-Field Value Iteration (SAFARI)
Input: Dataset HN coefficient 3, regularization coefficient Initialize: Set VH + = 0.
for h H, H 1..... do
Compute A₁ = K₁ + AT.
Estimate Qn a) - (B, Vh+1)(w, = = ān as in (6).
1/2 Set B 112 (Ww a), (w, - @n(w,)) a) A (w,
Let Qn a) = min (wi a) - (n(w,a), H - 11+
Optimal policy R/ argmax, (w, ) w))
Set (w) = (Qn(w,) )) Tn w)) end for
Output: Estimated Q-function Qi, value function Vn, and optimal policy मn for h I...., H.
The quantity Fa quantifies the uncertainty in estimating the Bellman operator B, V4+1 using kernel ridge regression. We subtract H for estimating the Bellman operator account for the spurious correlation in the experience data (see Technical Overview following Theorem for a detailed explanation). We truncate Qi at H - h + 1, since the reward function is bounded by 1.
5 Suboptimality of Policy Learned by SAFARI
We investigate the performance of the optimal policy f learned by Algorithm Before we proceed, we state the following assumptions.
Assumption (Boundedness of Kernel). Kernel K(s)) is bounded, i.e., without loss of generality, assume supge= [K(
By Cauchy-Schwarz inequality, Assumption implies for any &,1 E E. K(E,& < / (E,,, ( (
Such assumption holds for rich family of commonly used ker- nels, e.g., RBF kernel and Laplacian kernel, and is standard assumption in literature (Caponnetto and De Vito, 2007; Muandet et al., 2012).
The second assumption characterizes the spectrum of kernel K. We first introduce the integral operator induced by kernel K. Let f = + IR be square-integrable function. Then we define the integral operator Tk as
(Tk()(E) = ((E,)))(()))))) for E
By Mercer's theorem (Hearst al., 1998), Tx has corresponding positive eigenvalues a, and eigenfunctions v, Then the kernel K admits decomposition
K(E1, Σ (E)
Assumption (Spectrum of Kernel), The eigenvalue d; satisfies one of the following three condi- tions:
(Finite Spectrum). There exists a positive integer 7, such that a; = for all > 7.
(Exponential Decay). There exist positive constants Ci, C2 and exponent 7 such that 0, S C₁ exp (-C2i?).

---

3. (Polynomial Decay). There exists positive constant C and exponent 7 23+ ( such that S Ci7,, where d is the dimension of S x S x A.
Furthermore, in (Exponential Decuy) and (Polynomial Decay), we assume the eigenfunction o is uniformly bounded, i.c., sup, ||Pell $ 1.
As we will show in our theory, the decay rate of the spectrum significantly influences the performance of the proposed SAFARI algorithm. We give examples to better interpret the three categories above. In (Fimite Spectrum) case, by (4), the reward function and transition kernel is a linear function of a finite dimensional feature map. Such a parameterization is satisfied by linear MDP (Yang and Wang, 2019; Jin et al., 2020a). In (Exponential Decay) and (Polynomial Decay) cases, the feature map is infinite dimensional. For example, RBF kernel belongs to (Exponential Decay) case, while Laplacian kernel and neural tangent kernel belong to (Polynomial Decay) case. We assume 7y 2 3 + ((1/d) in (Polynomial Decay) for technical simplicity, yet it not restrictive: Laplacian kernel and neural tangent kernel both have polynomial decay rate of y = d (Bietti and Bach, 2020).
The last assumption imposes some regularity on the reward function and transition probabilities. Assumption (Boundedness). The weights 0g and Uj in reward function Th and Markov transition kernel Pa. are bounded for any h = i....,,... H, respectively, i.e., ||0, S and Sa (2))l dz I Vdeii, where delt su log det + /n/A) is the effective dimension of Hg with supremum over all Gram matrix K₁ E N
The effective dimension describes the complexity of H.x for parameterizing the MDP (Yang et al., 2020b), whose scale is closely related the spectrum of kernel K. In the special case of K having y-finite spectrum as in Assumption 2, we have def = O(v), which resembles the dimensionality of a finite dimensional Euclidean space.
We measure the pointwise suboptimality of the learned policy म. We define the global optimal policy by the recursion,
A = argmax (Qh, A) with Q = BB Vi+ V = (Qh, A and Vă++ = O.
Then the suboptimality of is given as SubOpt(R;ww) = V (w) - (w).
Our main result is provided in the following theorem, which upper bounds SubOpt(f:w),
Theorem 1. Suppose Assumption 33 hold. For any (0, 1), let Rn be the policy returned by Algorithm with
emaxfd, 7) /log (ax (d HN/8) (Finite Spectrum)
m 2 log(2/0), ==1, B = cH V (log(HN//)) 1+2/7
(Exponential Decay):
cN21 H (dlog(HN/)))
(Polynomial Decay)
where is the dimension of E S S and iss some constant depending on C, C1 C2 and Lebesgue measure of E. Then for any meta state w, with probability at least 1 - å over the randomness of the dataset DN. we have
H
SubOpt(T:w)) $
Σ B (h-TTh an) w1 = w].
1=1
Theorem I indicates that the suboptimality learned policy depends on the uncertainty quantifier In The scale of I,, depends on how well the collected data explore the state-action space. Moreover, from Bayesian learning perspective, Т₁ measures the eliminated uncertainty in estimating the Bellman operator given dataset D H (lin et al., 2020b). To better understand the convergence of SubOpt, we specialize Theorem under a weak data coverage assumption.
Assumption 4 (Weak Coverage). Suppose the dataset is collected under some behavior policy π such that there exists a constant Cmin 0 satisfying
inf (f. Ea [u(w,, an) @ p(wn, an)lf) 2 Cmin for any h = 1....,H
I =1
Recall that μ is the mean embedding in H.-

---

Assumption 4 says that the operator Ea [u([,, as) @ plwn, an) is positive definite. Intuitively, this requires that the collected data relatively well spread over the state-action space. We present the following Corollary providing a concrete convergence rate of SubOpt.
Corollary Under the setting in Theorem 1, we additionally assume Assumption 4 holds. Then for N 2 ((log(deaHHo) sufficiently large, with probability 1 6, we have
H2 dea log(den (og()R
SubOpt(f;w) = (HH
N
Here def is the effective dimension of RKHS Hk. which takes value
max(d, d, 7 log N
(Finite Spectrum) (Exponential Decay).
deft
d(log N)1-1/7 dN 2サ. log N
(Polynomial Decay)
Impact of Kernel Spectrum The spectrum of kernel K significantly influences the performance of the learned policy. In (Finite Spectrum) case, the effective dimension scales linearly with dimension and y, and SubOpt converges a rate of (12² max(d, ////// which recovers the result of Corollary 4.5 in Jin et al. (2020b) on linear MDP. In (Exponential Decay) case, the convergence rate is OH N) N)1+1/7// /VN), which is similar to (Finite Spectrum) case with additional logarithmic dependence on N. However, in (Polynomial Decay) case. the convergence rate is considerably slower, and relies heavily on the decay rate Consider, for instance, Laplacian kernel and NTK, whose spectrum decays with
d. Then SubOpt converges at rate of OHH²dN za log N), which suffers from the curse of dimensionality without further assumptions on data.
No Curse of Many Agents The convergence of SubQpt does not suffer from the curse of many agents. particular, both Theorem 1 and Corollary only impose a mild requirement on the number m of neighboring agents to be sampled. This is due to the permutation invariance in mean-fichl MARL, since the interactive influence of neighboring agents are captured by the distribution of states.
We briefly discuss the proof of Theorem I and Corollary 1. The full proof is deferred to Appendix A and B. We first decompose SubOpt into three terms (see Lemma I):
Technical Overview
SubOpt(T;w)) E E Eg-
Here & Ei= Eg Qu an) (B₁, Vn-1i) an) w1 w| reflects the uncertainty in estimating the Bellman operator. Note that the evaluating trajectory is generated by the learned policy म. which has spurious correlation with the estimated Bellman operator; & Ex= Er ((B, (h+1)(wh, an) - (un, W1 w] is the estimation error of Bellman oper- ator again, yet it is evaluated by a trajectory generated by π². Compared to &,, & does not suffer from the spurious correlation between the learned policy and the estimated Bellman operator. Lastly, E E A= optimality of म. immediately have Eg < O.
Ex ((Q (wh, :), (- wh) (. w))) w1 = w] is the optimization error. By the
In order to tackle El and εg, properly choose I's that the event E [ V
BB P <
In happens with high probability. fact, I, is understood as the uncertainty quantifier of estimating B, V1+1 with high confidence 1 - 5. Then we can show ε S O conditioned on event E, meanwhile & < 2 D E.,. [T', (win, ax) W1 = w]. To this end, we reduce the upper bound of Sub0pt to bounding the uncertainty quantifier П',, which allows us to leverage statistical tools. In particular, TT, consists of two types of statistical error: 1) covariate concentration error mean embedding, i.c., finite agent empirical embedding p( a²))) concentration error with respect to population counterpart n(wh, a;); ) 2) regression error in Bellman operator estimation. We bound 1) by concentration of empirical means in Hilbert spaces (see Lemma 3). In bounding 2), we exploit the closed form solution of kernel ridge regression and concentration of self- nelf-normalizing processes (see Lemma 5).
6 Numerical Experiment
We perform experiments on the multi-agent particle environment (MPE, Lowe et (2017)), popular benchmark used in prior work (Mordatch and Abbeel, 2018; Liu et al., 2020a). Here, consider the

---

cooperative navigation scenario, where N agents must spread to cooperatively cover N landmarks across the map. Each agent able observe information about the &t closest landmarks and agents, and receives global reward r = - Ei= minje[N] Ily: - 22112. where 2, E I2² and yi I2 are agent and landmark positions, respectively. Implementation of all environments follows from the official codebase of Liu et al. (2020a). See hyperparameter choices and more details in Appendix Sample code is also available at https:/ thub. com/wangen 1/offf welliin-eeeee pess imistic.
Data Generation To receive optimal reward on cooperative navigation, individual agent must learn to coordinate their be- haviors each generate data for the offline setting by training a MARL pol- icy and collecting experience data after convergence. We use counterfactual multi-agen policy gradients (COMA) to address the problem of credit assignment by learning a joint critic that marginalizes out an individual agent's s action with a counterfac- tual baseline (Foerster et al., 2018). This, in turn, allows the agent-level policies to learn sufficient coordination by evaluat- ing their individual impact on the team reward. Both the policy and critic networks are implemented as traditional MLPs, with 64 and 512 nodes in single hidden layer, respectively, and we use parameter sharing for policy networks. To sanity check the performance of COMA, we train the individual actor-critic (IAC) algorithm (Konda and Tsitsiklis, 2000), which applies the policy gradient to train independent actor-critics. Given the lack of an in-built coordination mechanism, IAC is expected to perform suboptimally on multi-agent settings.
-205
different landmark. As result,
380
COPA.
Figure 1: Training reward the 15 agent environment.
As all agents take the same action in the mean-field MARL formulation, COMA produces experiences by selecting the action that corresponds with the plurality vote (mode) of individual agent policy outputs. However, to demonstrate that this does not greatly inhibit convergence behavior, we train IAC and the original COMA implementation, labeled COMA-O, without this restriction. As demonstrated in Figure I, with error bar computed over 3 independent random seeds, COMA-O performs the best. is worth noting that COMA receives slightly lower rewards yet still performing significantly better than IAC with the same number of learnable parameters.
P5
Agp
SAPAT
COUA
LNC
10K
SACARI
Algorttann
Agattii
(a) agents
(b) 30 agents
(c) 100 agents
Figure 2: Average reward after training. COMA and IAC are evaluated off loaded pre-trained models.
In Figure 2, we implement our SAFARI algorithm with varying number of agents on 500 sample episodes of experience data. We evaluate the performance over a horizon H = 50 on 3 different random seeds. We observe that SAFARI is able perform comparably COMA in settings with m = 15, 30, and 100 agents. Due to mean-field permutation invariance, we see that the performance gap between SAFARI and COMA does not widen the number of agents increases, behavior that is normally expected given the exponential growth of the joint state-action space.
Conclusion
This paper proposes a SAFARI (Pessimistic Mean-Fiel Value Iteration) algorithm offline mean- field MARL. We prove suboptimality bound d /vN), and provide concrete rate conver- gence under weak data coverage assumption. The suboptimality bound is free of the curse of many agents due to the permutation invariance in mean-field formulation. We also extend to the online setting in longer technical report version.

---

Acknowledgment
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports. Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning).
References
YADKOR,, Y., PÁL., D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In NIPS, vol. 11.
AGARWAL, R., SCHUURMANS, D. and NOROUZI. M. (2020). An optimistic perspective on offline reinforcement learning. In International Conference Machine Learning.
ALTUN, Y. and SMOLA, A. (2006). Unifying divergence minimization and statistical inference via convex duality. In International Conference on Computational Learming Theory. Springer.
ANAHTARCI, B., KARIKSIZ, C. D. and SALDI, N. (2019). Fitted q-learning in mean-field games. arXiv preprint arXiv: 1912./39993330
ANAHTARCI, B., KARIKSIZ, C. D. and SALDI, N. (2020). Q-learning in regularized mean-field games. arXiv preprint urXiv:2003. 12151.
ANAHTARCI, B., KARIKSIZ,
and SALDI, (2020). Value iteration algorithm for mean-field
games. Systems & Control Letters, 143 104744.
ANTOS, A., SZEPESVÁRI, C. and MUNOS, R. (2007). Fitted Q-iteration in continuous action-space MDPs. In Advances in Neural Information Processing Systems.
ANTOS, A., ÁREP C. and MUNOS, R. (2008). Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 129.
AZAR, M. G., MUNOS, R. and KAPPEN, B. (2012). On the sample complexity of reinforcement learning with a generative model. arXiv preprint arXiv:1206.644 6461.
BERNER, C., BROCKMAN, G., CHAN, B., CHEUNG, V., DEBIAK, P., DENNISON, C., FARHI, D., FISCHER, Q., HASHME, S., HESSE, C. ET AL. (2019). Dota 2 with large scale deep reinforcement learning. arXiv preprint
1912.0668.
BIETTI, A. and BACII F. (2020). Deep equals shallow for relu networks in kernel regimes, arXiv preprint 1IXXx:20099.4397
BUCKMAN, J., GELADA, C. and BELLEMARE, M. G. (2020). The importance of pessimism in fixed-dataset policy optimization. arXiv preprint arXiv:2009.06799
CAL, Q., YANG, Z., JIN, C. and WANG, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning. PMLR.
CAPONNETTO, and DE VITO, E. (2007). Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7 331--368.
CARMONA, R., LAURIÈRE, M. and TAN, Z. (2019). Model-free mean-field field reinforcement learning: mean-field mdp and mean-field q-learning. arXiv preprint 1910v:1910.1200 12802..
CHEN, J. and JIANG, N. (2019). Informationn-theoreiec considerations in batch reinforcement learning. In International Conference on Machine Learning. PMLR.
CHOWDHURY, S. R. and GOPALAN, A. (2017). On kernelized multi-arme bandits. International Conference Machine Learning. PMLR.
CUI, K. and KOEPPI, H. (2021). Approximately solving mean field games via reguopy-r deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics. PMLR.
10

---

DUAN, Y., JIA, Z. and WANG, M. (2020). Minimax-opting off-policy evaluation with linear function approximation. In International Conference on Machine Learning.
ELIE, R., PÉROLAT, J., LAURIÈRE, M., GEIST, M. and PIETQUIN, O. (2020). On the convergence of model free learning in mean field games. In Proceedings of the AAAI Conference Artificial Intelligence, vol. 34.
FAN, J., WANG, Z., XIE, Y. and YANG, Z. (2020). A theoretical analysis of deep Q-learning. In Learning for Dynamics and Control.
FARAHMAND, A.-M., GHAVAMZADEH, M., SZEPESVÁRI, C. and MANNOR, S. (2016). Regularized policy iteration with nonparametric function spaces. Journal of Machine Learning Research, 17 4809-4874.
FARAHMAND, A., SZEPESVÁRI ÁRI, C. and MUNOS, R. (2010). Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems.
FARAJTABAR, M., CHOw, Y. and GHAVAMZADEH, M. (2018), More robust doubly robust off-policy evaluation. In International Conference on Machine Learning.
FOERSTER, J., FARQUHAR, G., AFOURAS, T., NARDELLI, N. and WHITESON, S. (2018). Coun- terfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32.
FU, J., KUMAR, A., NACHUM, O., TUCKER, G. and LEVINE, S. (2020a). D4RL: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219.
FU, Z., YANG, Z., CHEN, Y. and WANG, Z. (2019). Actor-critic provably finds nash equilibria of linear-quadratic mean-field games. In International Conference on Learning Representations.
FU, Z., YANG, Z. and WANG, Z. (2020b). Single-timescale actor-critic provably finds globally optimal policy. arXiv preprint arXiv:2008.0048.
FUSмотО, S., MEGER, D. and PRECUP, D. (2019). Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning.
GULCEHRE, C., WANG, Z., NOVIKOV, A., PAINE, T. L., COLMENAREJO, S. G., ZOLNA, K.,
AGARWAL, R., MEREL, J., MANKOWITZ, D., PADURARU, C. ET AL. (2020). RL Unplugged: Benchmarks for offline reinforcement learning. arXiv preprint arXiv:2006. 13888
GUO, X., HU, A., XU, R. and ZHANG, J. (2019). Learning mean-field games. arXiv preprint arXiv:1901.n 1901.0955.
GUO, X., HU, A., XU, R. and ZHANG. J. (2020a). A general framework for learning mean-field games. arXiv preprint arXiv:2003.06069.
GUO, X., XU, R. and ZARIPHOPOULOU, T. (2020b). Entropy regularization for mean field games with learning. arXiv preprint arXiv:2010.00145.
HEARST, M. A., DUMAIS, S. T., OSUNA, E.. PLATT, and SCHOLKOPE, B. (1998). Support vector machines. IEEE Intelligent Systems and their applications, 13 18-28.
HUANG, M., CAINES, P. F. and MALHAMÉ, R. P. (2003). Individual and mass behaviour in large population stochastic wireless power control problems: centralized and nash equilibrium solutions. In 42nd IEEE International Conference Decision and Control (IEEE Cat. No. 03CH37475), vol. IEEE.
HUANG, M., CAINES, P. E. and MALHAMÉ, R. P. (2007). Large-population cost-coupled LQQ problems with nonuniform agents: individual-mant behavior and decentralized varepsilon-Nast equilibria. IEEE transactions on automatic control, 52 1560-1571.
JAQUES, N., GHANDEHARIOUN A., SHEN, J. H., FERGUSON, C., LAPEDRIZA, JONES, N., GU, and PICARD, R. (2019). Way oof-py batch deep reinforcement learning of implicit human preferences in dialog, arXiv preprint

---

JIANG, N. and HUANG, J. (2020). Minimax value interval for off off-policy evaluation and policy optimization. In Advances in Neural Information Processing Systems.
JIANG, N. and LI, L. (2016). Doubly robust off aff-policy value evaluation for reinforcement learning. In International Conference on Machine Learning.
JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2020a). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory.
JIN, Y., YANG. Z. and WANG, Z. (2020b). Is pessimism provably efficient for offline RL? arXiv preprint arXiv:2012.1508
KALLUS, N. and UEIIARA, M. (2019). Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. arXiv preprint
KALLUS, N. and UEHARA, M. (2020). Doubly robust off aff-policy value and gradient estimation for deterministic policies. arXiv preprint arXiv:2006.03900
KIDAMBI, R., RAJESWARAN, A., NETRAPALLI, P. and JOACHIMS, T. (2020). MOReL: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05957.
KONDA, V. R. and TSITSIKLIS, N. (2000). Actor-critic algorithms. In Advances in neural information processing systems.
KUMAR, A., ZHOU, A., TUCKER, G. and LEVINE, S. (2020). Conservative Q-learning for offline reinforcement learning. arXiv preprint arXiv:2006.0477.
LASRY, J.-M. and LIONS, P.-L. (2006a). Jeux à champ moyen. i-le cas stationnaire. Comptes Rendus Mathématique, 343 619-625.
LASRY, J.-M. and LIONS, P.-L.. (2006b). Jeux à champ moyen. ii Horizon fini et contrôle optimal. Comptes Rendus Mathématique, 343 679-684.
LEIBO, Z., ZAMBALDI, V., LANCTOT, M., MARECKI, J. and GRAEPEL, T. (2017). Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint 1rxXiv:/702.03:2
LEVINE, S., KUMAR, A., TUCKER, G. and FU, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint arXiv:2005.0164::
LI, Y., WANG, L., YANG, J., WANG, E., WANG, Z., ZhAo, T. and ZHA, H. (2021). Permutation invariant policy optimization for mean-field multi-agent reinforcement learning: A principled approach. arXiv preprint arXiv:2105.0820 082668...
LIAO, P., QI, Z. and MURPHY, S. (2020). Batch policy learning in average reward Markov decision processes. arXiv preprint 17Xiv.2007.11771.
LIU, I.-J., YEH, R. A. and SCHWING, A. G. (2020a). Pic: permutation invariant critic for multi- agent deep reinforcement learning. In Conference on Robot Learning. PMLR.
LIU, Q., LI, L., TANG, Z. and ZHOU, D. (2018). Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems.
LIU, Y., SWAMINATHAN, A., AGARWAL, A. and BRUNSKILL, E. (2020b), Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.
LOWE, R., WU, Y., TAMAR, A., HARB, J.. ABBEEL, P. and MORDATCH, I. (2017). Multi-agent actor-critic for mixed cooperative-competiiie environments. arXiv preprint arXiv:1706.02275
MANDEL, T., LIU, Y.-E., LEVINE, S., BRUNSKILL, E. and POPOVIC, Z. (2014). Offline policy evaluation across representations with applications to educational games. In AAMAS.
MORDATCH, I. and ABBEEL, P. (2018). Emergence of grounded compositional language in multi- agent populations. In Thirty-second AAAI conference on artificial intelligence.
MUANDET, K., FUKUMIZU, K., DINU77O, F. and SCHÖI.KOPF, B. (2012). Learning from distribu- tions via support measure machines. arXiv preprint
12

---

MUNOS, R. (2007). Performance bounds in e--norm for approximate value iteration. SIAM journal on control and optimization, 46 541-561.
MUNOS, and SZEPESVÁRI, (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9 815-857.
NACHUM, O., CHOW, Y., DAI, B. and LI, L. (2019a). DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems.
NACHUM, O. and DAI, B. (2020). Reinforcement learning via Fenchel-Rockafelln duality, arXiv preprint arXiv:2001.01860
NACHUM, O., DAI, B., KOSTRIKOV, L., CHOw Y., LI, L. and SCHUURMANS, D. (2019b). AlgaeDICE: Policy gradient from arbitrary experience. arXiv preprint arXiv:
PERRIN, S., PÉROLAT, J., LAURIÈRE, M., GEIST, M., ELIE, R. and PIETQUIN, O. (2020). Fictitious play for mean field games: Continuous time analysis and applications. arXiv preprint arXiv:2007.03455.
REN, T., LI, J., DAI, B., DU, S. S. and SANGHAVI, S. (2021). Nearly horizon-free offline reinforcement learning, arXiv preprint arXiv:2103,
SCHERRER, B., GHAVAMZADEH, M., GABILLON, V., LESNER, B. and GEIST, M. (2015). Ap- proximate modified policy iteration and its application the game of Tetris. Journal of Machine Learning Research, 16 1629-1676.
SALLEV-SWARTZ. S., SHAMMAH, S. and SHASHUA, A. (2016), Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295.
SRINIVAS, N., KRAUSE, A., KAKADE, M. and SEEGER, M. (2009). Gaussian process optimiza- tion in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995..
SZEPESVÁRI, C. (2010). Algorithms for reinforcement learning. Morgan & Claypool.
TANG, Z., FENG, Y., LI, L.., ZHOU, D. and LIU, Q. (2019). Doubly robust bias reduction in infinite horizon off-policy estimation. arXiv preprint arXiv: 1910.07186.
THOMAS, P. and BRUNSKILL, E. (2016). Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning.
UEHARA, M., HUANG, J. and JIANG, N. (2020). Minimax weight and Q-function learning for off-policy evaluation. In International Conference on Machine Learning.
UZ ZAMAN, M. A., ZHANG, K., MIEHLING, E. and BACAR, T. (2020). Reinforcement learning in non-stationary discrete-time linear-quadratic mean-field games. In IEEE Conference Decision and Control (CDC). IEFE.
WANG, L., YANG, Z. and WANG, Z. (2020). Breaking the curse of many agents: Provable mean embedding q-iteration for mean-field reinforcement learning. In International Conference on Machine Learning. PMLR.
XIAO, C., WU, Y., LATTIMORE, T., DAI, B., MEI, J., LI, L., SZEPESVARI, C. and SCHUUR- MANS. D. (2021). On the optimality of batch policy optimization algorithms. arXiv preprint arXiv:2104.02293.
XIE, T. and JIANG, N. (2020a). Batch value-function approximation with only realizability, arXiv preprint XXX::2008.04999.
XIE, T. and JIANG, N. (2020b). Q' approxiaiiiioooon schemes for batch reinforcement learning: theoretical comparison. arXiv preprint arXiv:2003.08.
XIE, T., MA, Y. and WANG, Y.-X. (2019). Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances Neural Information Processing Systems.
13

---

YANG, J., YE, X., TRIVEDI, R., XU, H. and ZHA, H. (2017). Learning deep mean field games for modeling large population behavior. arXiv preprint arXiv:1711.03156.
YANG, L. and WANG, M. (2019), Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning.
YANG, M., NACHUM, O., DAI, B., LI, L. and SCHUURMANS, D. (2020a). Off-policy evaluation via the regularized Lagrangian. In Advances in Neural Information Processing Systems.
YANG, Y., LUO, R., LI, M., ZHOU, M., ZHANG, W. and WANG, J. (2018). Mean field multi-agent reinforcement learning. In International Conference on Machine Learning. PMLR.
YANG, Z., JIN, C., WANG, Z., WANG, M. and JORDAN, M. I. (2020b). On function approximation in reinforcement learning: Optimism in the face of large state spaces.
YIN, M., BAI, Y. and WANG, Y.-X. (2020). Near optimal provable uniform convergence in off-policy evaluation for reinforcement learning. arXiv preprint urXiv:2007.03760.
YIN, M. and WANG, Y.-.. (2020). Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference Artificial Intelligence and Statistics.
YU, T., THOMAS, G., YU, L.,, ERMON, S., Zou, J., LEVINE, S., FINN, C. and MA, T. (2020). MOPO: Model-based offline policy optimization. arXivv preprint 13X.v:2005.13239.
ZHANG, J., KOPPEL, A., BEDI, A. S., SZEPESVÁRI, C. and WANG, M. (2020a). Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems.
ZHANG, K., YANG, Z. and BAŞAR, T. (2019). Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:1911.106::
ZHANG, R., DAI, B., LI, L. and SCHUURMANS, D. (2020b). GenDICE: Generalized offline estimation of stationary values. In International Conference Learning Representations.
14


Reviews:
[{"review_id": "yZJPZagvHy4", "reviewer": "Reviewer_WSQ9", "summary": "The paper presents a method which uses Kernel mean embedding for mean-field based MARLwith  offline settings. Under a weak data coverage assumption, it shows a suboptimality bound in offline settings and extend the result to online settings. No experiments are included in this paper.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) I wonder if the weak data coverage assumption is too strict to implement, which means it needs to be tested in experiments. In addition, it would be better if there were comparisons with other algorithms in MARL.\n2) section 5 spend a lot of time to describe various assumptions made, but there is no any experimental verifications.\n3) in the online learning setting, we may have no information about the state of other agents. In such cases, what can we do?\n4) for eq.5, there is an i.i.d assumption for each kernel mean embedding u, which could be problematic.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "jWmfYh80fjh", "reviewer": "Reviewer_fQxx", "summary": "This paper studies the Mean-Field Multi-Agent RL problem in the offline regime where pre-collected data is available. Under the assumption that data provides “sufficient” information regarding the optimal policy, the authors propose SAFARI, a pessimistic algorithm, and prove sample complexity guarantees to achieve a certain sub-optimality gap. The obtained data-dependent guarantees do not depend on the (large) number of agents and scale linearly with the effective dimension of the function class (used to parametrize the value function). Moreover, the authors propose another algorithm OMPPO for the online setting and obtain similar sublinear (in $N$; for some kernels) regret guarantees. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Recently, both offline RL and mean-field games/RL have received a lot of attention and hence, I think that the paper is timely and considers an original idea of unifying these two problems. The need for offline RL in the mean-field MARL setting is clearly motivated in the paper. The obtained theoretical results are sound. The paper is also clearly written and the related work section nicely covers the existing literature. It would be great to see the performance of the proposed algorithms in simulations and experiments, but since this is a theoretical paper, I understand why this was not done.  \n\nI like how the mean embeddings come into play when parametrizing the reward and transition (also, later on, when concentration results for empirical mean embedding are invoked in the analysis). By having a feature mapping that depends on $\\mathcal{S} \\times \\mathcal{S} \\times \\mathcal{A}$, it is very convenient to invoke upper bounds on $d_{\\text{eff}}$ in the final results. However, I feel that this parametrization also has its disadvantages,  as under such parametrization, the reward function (also transition) is only averaged with respect to $d_s$, i.e., the dependency on $d_s$ is quite simple and can be thought of as averaging over a single contextual parameter. This is reflected in the main bounds where $d$ corresponds to the dimension of the $S \\times S \\times A$ (thinking of it in this way, it appears that the problem/algorithm is not much different than the single-agent setup with a contextual variable (or two agent setting), which is also reflected in the bounds). Alternatively, one can consider having a kernel that is defined over $\\mathcal{M}(S)$ instead of $S$ (i.e., $S \\times \\mathcal{M}(S) \\times A$), and allow for rewards and transitions that depend on $d_s$ in more complex ways. I’m wondering if the authors can briefly comment on this.         \n\n\nCan you comment on the assumption on line 238 that involves $v_h(x)$ and provide the intuition behind it? This assumption seems like an atypical one to me. How does it impact the analysis?   \n\nIt’d be great if the authors can comment on some of the implementation details of SAFARI. In particular, solving for the optimal policy $\\hat{\\pi_h}$ when the set of actions is infinite. Moreover, if I understood correctly (since it is not explicitly written in the algorithm) when searching for the optimal policy $\\hat{\\pi}_h$, one needs to solve the previous argmax problem for each $w \\in \\Omega$? How should this be done in practice given that $\\Omega$ contains $\\mathcal{M}(S)$ (i.e., space of probability distributions)?\n\nIn summary, I think this paper considers an interesting problem, provides further insights into the mean-field MARL, and contains some nice theoretical results/algorithms. \n\nMinor comments:\n\n-- Line 15-16: “we also propose a variant of our SAFARI algorithm”; I would argue that this is a new algorithm rather than a variant of SAFARI.\n\n-- Line 140: $d_{h+1,j}$; Should it be $s_{h+1,j}$ instead?\n\n-- Line 77: “these methods focus -on- the online setting”\n\n-- Line 304: “we denote $s_0$ as the representative agent” \n\n-- Line 196: “gram” -> “Gram”\n\n-- Equation 5: $\\alpha?$\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "besNOYFjhCG", "reviewer": "Reviewer_Jqk7", "summary": "The paper (mainly) provides a pessimism based offline RL algorithm for MF-MARL. It extends existing literature by\n1. Generalizing pessimism based offline RL algorithms from single agent to MF-MARL\n2. Considering MF-MARL from an offline regime\nIt also extends existing literature on online MF-MARL by converting the pessimism penalty to a optimistic bonus and showed the sample efficiency of the algorithm under this regime.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Originality: the key ideas behind SAFARI, as the authors mention in the paper, were first discussed in [1] (reference [70] in the paper itself) and the proof structure of theorem 1 largely follows the same paper. While MF-MARL is an interesting area and analyzing it from an offline perspective is indeed interesting, the proposed algorithm largely follows existing research on offline learning of linear MDPs. \n\n- Quality: theorems and claims are well supported by theory, which are meticulously proven in the appendix.\n\n- Clarity: well written paper with thoroughly explained proofs and very few (if any) grammatical errors. Easy to follow and clearly explained.\n\n- Significance: it should be noted that some benefits of the algorithm (e.g. no curse of multiple agents) are caused by the nature of the MF-MARL problem, rather than the proposed algorithm. Additionally, unlike the aforementioned [1], the paper does not demonstrate the sample efficiency of the algorithm in the offline regime (of course its efficiency in the online regime is well-demonstrated and should be somewhat indicative of the offline regime). However, combining MF-MARL with PEVI is an interesting idea and, especially in the context of social welfare optimization, offline RL algorithms are appreciated and necessary.\n\n[1] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL?525arXiv preprint arXiv:2012.15085, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: assumptions of the paper are clearly stated and the paper is entirely devoted to MF-MARL.\n\nSocietal impact: purely theoretical & no direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "bITSlMcW7_t", "reviewer": "Reviewer_yJWX", "summary": "The paper introduces an offline algorithm named SAFARI for solving Mean Field Games, using RKHS embedding of the infinite dimensional distribution of states. No experience are provided, but a bound on the efficiency of the method in terms of approximated value function is provided. This bound depends on the time horizon, the number of offline available trajectories as well as the effective dimension of the for parametrising the value function. It is valid whenever the set of available trajectories satisfies a natural weak coverage assumption. As a by-product, the authors also provide an online version of the algorithm.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Main comments:\n1. The offline learning of Nash equilibria in Mean Field Games is a relevant and new topic, up to my knowledge. The distribution embedding using RKHS approach seems rigorously treated and well chosen for this setting. The literature review is complete and accurate and the paper is overall well written and easy to read. \n2. Can you justify why your method is indeed approximating the Nash of an MFG and not the solution of a corresponding Mean Field Control problem? As you mainly focus on the underpinned value function, this may need clarification. \n3. You are using a metric indicating how close the induced approximated value function is from the optimal one, how does it translates in terms of quality of Nash (with a metric such as exploitability for example) or approximation of the state distribution, which is also a commonly used metric for evaluating the quality of a MFG solution.\n4. The class of MFG considered here is still unclear for me. The abstract mentions an episodic MFG while the main paper is less clear about that point. Which assumptions are present in your setting on the dynamics and reward structure, ensuring the existence and more importantly the uniqueness of the Nash? \n5. When using a Mean Field setting for solving MARL problems, one naturally  in an offline setting accumulates trajectories from the N-agents system,  which itself is an approximation of the MF limit. This probably goes beyond the scope of this paper but do these  additional errors fit in your approach? \n6. The theoretical results are interesting (I did not check everything) but could have been completed by experimental results, even in small dimensional settings. This would have been a good occasion to compare online and offline efficiency.\n\nTypo: l 128 \"an representative\";  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I may have missed it but did not clearly identify where the limitations of the proposed approach are presented in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers raised some concerns with regard to lack of experimental results in this paper. Despite that they agree that the paper considers an interesting and relevant problem and it provides non-trivial theoretical results in terms of sample complexity of the proposed pessimistic method. Please provide the simple illustrative experiments in the final version.
Decision: Accept (Poster)