Pessimism Meets Invariance: Provably Efficient Offline Mean-Field Multi-Agent RL⇤
Year: 2022

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 O(Hde↵/ p N), where de↵ is the effective dimension of the function class for parameterizing the value function, but independent on the number of agents. Numerical experiments are provided.

text: p N), where de↵ is the effective dimension of the function class
for parameterizing the value function, but independent on the number of agents. Numerical experiments are provided.

heading: 1 Introduction
text: 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-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 of 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 interchangeable/indistinguishable (Yang et al., 2018; Carmona et al., 2019; Li et al., 2021). Accordingly, the interaction among agents can be captured by some mean-field quantity such as the empirical distribution of states, and therefore each agent only needs to find the best response to the so-called “mean-field 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 (NeurIPS 2021).
existing offline reinforcement learning (RL) algorithms and theories all focus on the single agent settings, and no algorithms and theories have been developed for MARL under the offline settings, regardless of the mean-field regime or not.
To bridge such a critical gap, we propose the first pessimistic algorithm – named SAFARI (peSsimistic meAn-Field vAlue iteRatIon) 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-embedding 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 a 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 a data-dependent upper bound on the suboptimality of SAFARI for MFMARL 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 O(H2de↵/ p N), where de↵ 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 on mean-field multiagent 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.

heading: 2 Related Work
text: • Mean-Field MARL. Existing literature has proposed various mean-field approximation approaches to model the population behavior of the agents for MARL with a large number, even infinitely many homogenous agents. Yang et al. (2017) investigate a mean-field game with deterministic linear state transitions, and reformulate it as a mean-field MDP, where the mean-field state lies in finitedimensional probability simplex. Yang et al. (2018) propose a 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 MDP from the perspective of mean-field control. As the mean-field 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 a 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-field MARL, the solution concept of mean-field game is the Nash equilibrium,
which corresponds to a pair of a local policy ⇡⇤ of the representative agent and a mean-field state d⇤ satisfying the following two properties: (i) when the 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); Elie 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-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 to datasets that are possibly not well-explored. Moreover, as 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 a 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 a 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 et 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 et al. (2019a,b); Tang et al. (2019); Zhang et al. (2020b); Chen and Jiang (2019); Kallus and Uehara (2019, 2020); Jiang and Huang (2020); Uehara et al. (2020); Duan et al. (2020); Yin and Wang (2020); Yin et 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 et al., 2020a; Gulcehre et al., 2020). In light of this, there is a line of recent works that proposes various pessimism-based 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 et 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 is 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 finite-dimensional linear function approximation. In 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-dimensional 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 2 H be elements in a Hilbert space, we denote hu, vi as the inner product, and u⌦v as the outer product satisfying (u⌦ v)w = u hv, wi. For a scalar a, we denote {a}+ = max{0, a}. We use O(·) to hide absolute constants and log factors.

heading: 3 Mean-Field Multi-Agent RL
text: We consider a Multi-Agent Reinforcement Learning (MARL) problem with m+ 1 agents and time horizon H . For the i-th agent (also known as the Representative Agent (RA)), at step h, we denote si,h 2 S and ai,h 2 A as 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 on its individual state, but the states of m other agents. Furthermore, we assume that the interaction of the representative agent to the other agents is permutation invariant, i.e., the influence of all the other agents is modeled using the empirical distribution of states bds,h = 1m P m
j 6=i sj,h 2 M(S). To this end, we define the transition kernel ph : S ⇥M(S)⇥A 7! M(S), the (deterministic) reward function rh : S ⇥M(S)⇥A 7! R, and the policy ⇡h : S ⇥M(S) 7! M(A) all depending on a “meta state” denoted as b!h = (si,h, bds,h) 2 S ⇥M(S). For simplicity, we denote ⌦ = S ⇥M(S) as the meta state space. Remark 1. The empirical distribution of states bds,h is naturally permutation invariant and evolves according to the transition kernel ph and policy ⇡h. To see this, suppose each agent takes the same policy ⇡h at step h. Then at step h+ 1, the state sh+1,j of the j-th agent is sampled from the distribution ph(· | sh,j⇥ bds,h, ah,j), where ah,j is determined by policy ⇡h(· | sh,j⇥ bds,h). Collecting m states sh+1,j for j 6= i induces the empirical distribution of states bds,h+1.
We now define several important notions in MARL. Given a policy ⇡, the value function V ⇡ h : ⌦ 7! R at step h  H for a representative agent is
V ⇡ h (!) = E⇡
" HX
i=h
ri(!i, ai) !h = !
# , (1)
where E⇡ denotes the expectation over the randomness in trajectories induced by policy ⇡. The action-value function (Q-function) Q⇡
h : ⌦⇥A 7! R is defined as
Q ⇡ h (!, a) = E⇡
" HX
i=h
ri(!i, ai) !h = !, ah = a
# .
By definition, V ⇡ h and Q⇡ h are related via V ⇡ h (!) = R A Q ⇡ h (!, a)⇡(a|!)da 4= hQ⇡ h ,⇡iA. Next, we define the Bellman operator and conditional transition operator. At each step h  H , the Bellman operator denoted as Bh is
(Bhg)(!, a) = E [rh(!h, ah) + g(!h+1) | !h = !, ah = a] (2) = rh(!, a) + (Phg)(!, a),
where g is a function defined on ⌦, and Ph is referred to as the conditional transition operator.
Mean-Field MARL As the number of agents goes to infinity, the empirical distribution of states bds converges to a (continuous) limit ds. Then the mean-field MARL problem for a representative agent is defined as a tuple (⌦,A, H, P, r), where ⌦ and A are the meta state space and action space, respectively, H is the horizon, P = {ph}Hh=1 : ⌦ ⇥ A 7! M(S) is the transition kernel, and r = {rh}Hh=1 is the reward function defined on ⌦⇥A. Following Remark 1, the transition of ds is also determined by P = {ph}Hh=1. To tackle the infinite-dimensional joint distribution of states, we embed the meta state-action space ⌦ ⇥ A into a reproducing kernel Hilbert space (RKHS). Specifically, denote ⌅ = S ⇥ S ⇥ A and let K : ⌅ ⇥ ⌅ 7! R be a symmetric positive kernel. The corresponding feature mapping of kernel k is denoted as , which verifies h (·), (·)i = K(·, ·) can be infinite dimensional. For any (!, a) 2 ⌦⇥A, we define mean embedding as
µ(!, a) = Es0⇠ds [ (s, s0, a)]. (3) Based on the embedding, we parameterize the reward rh and Markov transition ph as linear functionals of µ(!, a) in RKHS HK induced by kernel K, i.e.,
rh(!, a) = hµ(!, a), ✓hi , ph(!0 | !, a) = hµ(!, a), vh(!0)i , (4)
where ✓h, vh are understood as “weights” and have bounded Hilbert norm (see Assumption 3). Such a parameterization encodes a 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 in HK . Proposition 1. Suppose the reward function rh and the transition kernel ph is parameterized in HK by (4) for h = 1, . . . , H . Then for any g : ⌦ 7! R, the Bellman operator (Bhg) and conditional transition operator (Phg) defined in (2) can be written as
(Bhg)(!, a) = hµ(!, a), wgi , (Phg)(!, a) = hµ(!, a), wg + ✓hi , where wg depends on the function g.
The proof is provided in Appendix C.1, which follows from pure algebraic manipulation. From the perspective of policy learning in mean-field MARL, Proposition 1 motivates us to estimate the Bellman operator Bh in HK , and then optimize the estimated Q-function to obtain a policy. We introduce the detailed learning procedure in Section 4 (Algorithm 1).

heading: 4 Offline Pessimistic Value Iteration
text: In this section, we introduce our dataset and learning algorithm. We collect multiple trajectories of a representative agent in a mean-field MARL problem. Here the mean-field state distribution ds is prohibitive to trace. Instead, we only independently observe the states of a finite number of agents. Accordingly, the batched dataset DN,H consists of N trajectories of length H , within which the n-th sequence is ⌧n = (sn h 2 Sm+1, an h 2 A, rn h 2 R) H h=1
. Without loss of generality, we assume sh,0 is the state of the representative agent, and the reward function is bounded by 1, i.e., |rh(!, a)|  1 for any ! 2 ⌦, a 2 A. The collected trajectories are generated by some unknown behavior policy.
Recall bdsnh = 1 m
P m
j=1 s n h,j is the empirical state distribution induced by sn h . (We slightly alter the
notation to emphasize the empirical distribution is generated by the collection of m states sn h,1:m, while in the previous context, we use a general purpose notation bds,h.) We denote b!nh = snh,0 ⇥ bdsnh , and compute the empirical mean embedding of (b!n
h , a
n h ) as
µ(b!n h , a n h ) = E
s0⇠bdsn h
[ (sn h,0, s 0 , a n h )] = 1
m
P m
j=1 (s n h,0, s n h,j , a n h ).
Under mild conditions, the empirical mean embedding µ(b!n h , a n h ) concentrates around the infinite agent mean embedding µ(!n h , a n h ) defined in (3), where !n h is the infinite agent meta state. See a detailed error quantification in Lemma 3.
Pessimistic Value Iteration Our goal is to learn an 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 HK , 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
(bBh bVh+1) = argmin f
NX
n=1
⇣ f(µ(b!n
h , a
n h )) rn h bVh+1(b!nh+1)
⌘2 + kfk2
H , (5)
where 1 controls the regularization strength, bV is the estimated value function, and k·k H
denotes the Hilbert norm.
The solution to (5) can be written in a closed form. For notational simplicity, we define
K((!, a), ·) = Es0⇠ds [K((s, s0, a), ·)] with ! = s⇥ ds. Then we denote the Gram matrix Kh 2 RN⇥N as
[Kh]`,`0 = K((b!`h, a`h), (b!` 0 h , a ` 0 h )) 4 = E s1⇠ bd`h,s2⇠bd `0 h h (s` h,0, s1, a ` h ), (s` 0 h,0, s2, a ` 0 h )i
for `, `0 = 1, . . . , N. Meanwhile, for any (!, a), we denote feature vector h(!, a) =⇥ K((b!1
h , a 1 h ), (!, a)), . . . ,K((b!N h , a N h ), (!, a))
⇤> 2 RN . Then the estimated Bellman operator
bBh bVh+1 can be written as
(bBh bVh+1)(!, a) = h(!, a)>b↵h with b↵h = (Kh + I) 1[r1h + bVh+1(b!1h+1), . . . , rNh + bVh+1(b!Nh+1)]>,
(6)
We summarize the proposed SAFARI algorithm in Algorithm 1.
Algorithm 1 Pessimistic Mean-Field Value Iteration (SAFARI) Input: Dataset DN,H , coefficient , regularization coefficient . Initialize: Set bVH+1 = 0. for h = H,H 1, . . . , 1 do
Compute ⇤h = Kh + I . Estimate eQh(!, a) 4
= (bBh bVh+1)(!, a) = h(!, a)>b↵h as in (6). Set h(!, a) = · 1/2 K((!, a), (!, a)) h(!, a)>⇤ 1h h(!, a)
1/2. Let bQh(!, a) = min{ eQh(!, a) h(!, a), H h+ 1}+. Optimal policy b⇡h = argmax⇡h bQh(!, ·),⇡(· | !)iA. Set bVh(!) = h bQh(!, ·), b⇡h(· | !)iA.
end for Output: Estimated Q-function bQh, value function bVh, and optimal policy b⇡h for h = 1, . . . , H .
The quantity h quantifies the uncertainty in estimating the Bellman operator Bh bVh+1 using kernel ridge regression. We subtract h for estimating the Bellman operator to account for the spurious correlation in the experience data (see Technical Overview following Theorem 1 for a detailed explanation). We truncate bQh at H h+ 1, since the reward function is bounded by 1.

heading: 5 Suboptimality of Policy Learned by SAFARI
text: We investigate the performance of the optimal policy b⇡ learned by Algorithm 1. Before we proceed, we state the following assumptions. Assumption 1 (Boundedness of Kernel). Kernel K(·, ·) is bounded, i.e., without loss of generality, we assume sup
⇠2⌅ |K(⇠, ⇠)|  1.
By Cauchy-Schwarz inequality, Assumption 1 implies for any ⇠1, ⇠2 2 ⌅, K(⇠1, ⇠2) p K(⇠1, ⇠1)K(⇠2, ⇠2)  1. Such an assumption holds for a rich family of commonly used kernels, e.g., RBF kernel and Laplacian kernel, and is a 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 : ⌅ 7! R be a square-integrable function. Then we define the integral operator TK as
(TKf)(⇠) = Z K(⇠, x)f(x)dx for ⇠ 2 ⌅.
By Mercer’s theorem (Hearst et al., 1998), TK has corresponding positive eigenvalues i and eigenfunctions ⌫i. Then the kernel K admits a decomposition
K(⇠1, ⇠2) = 1X
i=1
i⌫i(⇠1)⌫i(⇠2).
Assumption 2 (Spectrum of Kernel). The eigenvalue i satisfies one of the following three conditions:
1. (Finite Spectrum). There exists a positive integer , such that i = 0 for all i > .
2. (Exponential Decay). There exist positive constants C1, C2 and exponent > 0 such that i  C1 exp ( C2i ).
3. (Polynomial Decay). There exists a positive constant C and exponent 3 +O( 1 d ) such that
i  Ci , where d is the dimension of S ⇥ S ⇥A.
Furthermore, in (Exponential Decay) and (Polynomial Decay), we assume the eigenfunction ⌫i is uniformly bounded, i.e., sup
i k⌫ik1  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 (Finite 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 3 +O(1/d) in (Polynomial Decay) for technical simplicity, yet it is not restrictive: Laplacian kernel and neural tangent kernel both have a polynomial decay rate of = d (Bietti and Bach, 2020).
The last assumption imposes some regularity on the reward function and transition probabilities. Assumption 3 (Boundedness). The weights ✓h and vh in reward function rh and Markov transition kernel ph are bounded for any h = 1, . . . , H , respectively, i.e., k✓hkH  1 and R ⌦ kvh(x)kH dx p
de↵ , where de↵ = supKh log det(I +Kh/ ) is the effective dimension of HK with supremum over all Gram matrix Kh 2 RN⇥N .
The effective dimension describes the complexity of HK for parameterizing the MDP (Yang et al., 2020b), whose scale is closely related to the spectrum of kernel K. In the special case of K having a -finite spectrum as in Assumption 2, we have de↵ = O( ), which resembles the dimensionality of a finite dimensional Euclidean space.
We measure the pointwise suboptimality of the learned policy b⇡. We define the global optimal policy by the recursion,
⇡ ⇤ h = argmax
⇡
hQ⇤ h ,⇡i A , with Q⇤ h = BhV ⇤h+1, V ⇤h = hQ⇤h,⇡⇤hiA , and V ⇤ H+1 = 0.
Then the suboptimality of b⇡ is given as (b⇡;!) = V ⇡ ⇤
1 (!) V b⇡1 (!).
Our main result is provided in the following theorem, which upper bounds (b⇡;!). Theorem 1. Suppose Assumption 1 – 3 hold. For any 2 (0, 1), let b⇡h be the policy returned by Algorithm 1 with
m log(2/ ), = 1, =
8 >><
>>:
cmax{d, }H p log(max{d, }HN/ ) (Finite Spectrum)
cH q d (log(HN/ ))1+2/ (Exponential Decay)
cN d+1 d+ H p d log(HN/ ) (Polynomial Decay)
,
where d is the dimension of ⌅ = S ⇥ S ⇥ A and c is some constant depending on C,C1, C2 and Lebesgue measure of ⌅. Then for any meta state !, with probability at least 1 over the randomness of the dataset DN,H , we have
(b⇡;!)  2 HX
h=1
E⇡⇤ [ h(!h, ah) | !1 = !].
Theorem 1 indicates that the suboptimality of learned policy depends on the uncertainty quantifier h. The scale of h depends on how well the collected data explore the state-action space. Moreover, from a Bayesian learning perspective, h measures the eliminated uncertainty in estimating the Bellman operator given dataset DN,H (Jin et al., 2020b). To better understand the convergence of , we specialize Theorem 1 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 kfk
H =1
hf,E⇡̄[µ(!h, ah)⌦ µ(!h, ah)]fi cmin for any h = 1, . . . , H.
Recall that µ is the mean embedding in HK .
Assumption 4 says that the operator E⇡̄[µ(!h, ah)⌦ µ(!h, ah)] 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 . Corollary 1. Under the setting in Theorem 1, we additionally assume Assumption 4 holds. Then for N ⌦(log(de↵H/ )) sufficiently large, with probability 1 , we have
(b⇡;!) = O H 2 de↵
r log(de↵HN/ )
N
! .
Here de↵ is the effective dimension of RKHS HK , which takes value
de↵ =
8 ><
>:
max{d, } logN (Finite Spectrum) d(logN)1+1/ (Exponential Decay) dN d+1 d+ logN (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 d and , and converges at a rate of O(H2 max{d, }/ p N), which recovers the result of Corollary 4.5 in Jin et al. (2020b) on linear MDP. In (Exponential Decay) case, the convergence rate is O(H2d(logN)1+1/ / p N), 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 converges at a rate of O(H2dN 12d logN), which suffers from the curse of dimensionality without further assumptions on data.
No Curse of Many Agents The convergence of does not suffer from the curse of many agents. In particular, both Theorem 1 and Corollary 1 only impose a mild requirement on the number m of neighboring agents to be sampled. This is due to the permutation invariance in mean-field MARL, since the interactive influence of neighboring agents are captured by the distribution of states.
Technical Overview We briefly discuss the proof of Theorem 1 and Corollary 1. The full proof is deferred to Appendix A and B. We first decompose into three terms (see Lemma 1):
(⇡;!) = E1 + E2 + E3.
Here E1 = P H
h=1 Eb⇡[ bQh(!h, ah) (Bh bVh+1)(!h, ah) | !1 = !] reflects the uncertainty in estimating the Bellman operator. Note that the evaluating trajectory is generated by the learned policy b⇡, which has spurious correlation with the estimated Bellman operator; E2 =P
H h=1 E⇡⇤ [(Bh bVh+1)(!h, ah) bQh(!h, ah) | !1 = !] is the estimation error of Bellman operator again, yet it is evaluated by a trajectory generated by ⇡⇤. Compared to E1, E2 does not suffer from the spurious correlation between the learned policy and the estimated Bellman operator. Lastly, E3 = P H
h=1 E⇡[h bQh(!h, ·),⇡⇤h(· | !h) b⇡h(· | !h)iA | !1 = !] is the optimization error. By the optimality of b⇡, we immediately have E3  0.
In order to tackle E1 and E2, we properly choose h so that the event E = {|Bh bVh+1 bBh bVh+1|  h} happens with high probability. In fact, h is understood as the uncertainty quantifier of estimating Bh bVh+1 with high confidence 1 . Then we can show E1  0 conditioned on event E, meanwhile E2  2 P H
h=1 E⇡⇤ [ h(!h, ah) | !1 = !]. To this end, we reduce the upper bound of to bounding the uncertainty quantifier h, which allows us to leverage statistical tools. In particular, h consists of two types of statistical error: 1) covariate concentration error on mean embedding, i.e., finite agent empirical embedding µ(b!n
h , a
n h ) concentration error with respect to population counterpart
µ(!n h , a n h ); 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-normalizing processes (see Lemma 5).

heading: 6 Numerical Experiment
text: We perform experiments on the multi-agent particle environment (MPE, Lowe et al. (2017)), a popular benchmark used in prior work (Mordatch and Abbeel, 2018; Liu et al., 2020a). Here, we consider the
cooperative navigation scenario, where N agents must spread to cooperatively cover N landmarks across the map. Each agent is able to observe information about the k closest landmarks and agents, and receives a global reward r = P N
i=1 minj2[N ] kyi xjk2, where xi 2 R2 and yi 2 R2 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 E. Sample code is also available at .
Data Generation To receive optimal reward on cooperative navigation, individual agent must learn to coordinate their behaviors to each cover a different landmark. As a result, we generate data for the offline setting by training a MARL policy and collecting experience data after convergence. We use counterfactual multi-agent policy gradients (COMA) to address the problem of credit assignment by learning a joint critic that marginalizes out an individual agent’s action with a counterfactual baseline (Foerster et al., 2018). This, in turn, allows the agent-level policies to learn sufficient coordination by evaluating their individual impact on the team reward. Both the policy and critic networks are implemented as traditional MLPs, with 64 and 512 nodes in a 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.
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 1, with error bar computed over 3 independent random seeds, COMA-O performs the best. It is worth noting that COMA receives slightly lower rewards yet still performing significantly better than IAC with the same number of learnable parameters.
In Figure 2, we implement our SAFARI algorithm with varying number of agents on n = 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 to perform comparably to 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 as the number of agents increases, a behavior that is normally expected given the exponential growth of the joint state-action space.

heading: 7 Conclusion
text: This paper proposes a SAFARI (Pessimistic Mean-Field Value Iteration) algorithm in offline meanfield MARL. We prove a suboptimality bound O(H2de↵/ p N), and provide concrete rate of convergence under a 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 a longer technical report version.

heading: Acknowledgment
text: 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).

Review summaries:
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.

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.

The paper (mainly) provides a pessimism based offline RL algorithm for MF-MARL. It extends existing literature by 1. Generalizing pessimism based offline RL algorithms from single agent to MF-MARL 2. Considering MF-MARL from an offline regime It 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.

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.